Abstract
Equational logic is central to reasoning about programs. What is the right equational setting for reasoning about probabilistic programs? It has been understood that instead of equivalence relations one should work with (pseudo)metrics in a probabilistic setting. However, it is not clear how this relates to equational reasoning. In recent work the notion of a quantitative equational logic was introduced and developed. This retains many of the features of ordinary logic but fits naturally with metric reasoning. The present chapter is an elementary introduction to this topic. In this setting one can define analogues of algebras and free algebras. It turns out that the Kantorovich (Wasserstein) metric emerges as a free construction from a simple quantitative equational theory. We give a couple of examples of quantitative analogues of familiar effects from programming language theory. We do not assume any background in equational logic or advanced category theory.
Introduction: Beyond Binary Equality
In classical computer science, equational logic provides a rigorous framework for proving program equivalence. Two programs are considered equal if they produce identical outputs for all possible inputs. While this binary "equal or not equal" approach works well for deterministic systems, it is increasingly brittle when applied to probabilistic programming.
Consider two programs where one returns a result with probability 0.99 and the other with 0.98. In a standard logical framework, these programs are simply "not equal." However, for most practical applications, they are nearly identical. Quantitative Equational Logic (QEL) addresses this by replacing the binary relation with a metric-based approach, allowing us to quantify how close two programs are.
Quantitative Equational Logic (QEL)
The fundamental innovation of QEL is the introduction of the quantitative equation: $$s =_\epsilon t$$ This statement asserts that the distance between terms $s$ and $t$ is at most $\epsilon$. To maintain the structural integrity of algebraic reasoning, the authors adapt classical axioms into quantitative forms:
- Triangle Inequality (Triang): If $s =_\epsilon u$ and $u =_{\epsilon'} t$, then $s =_{\epsilon + \epsilon'} t$.
- Non-Expansiveness (NExp): Applying a function to "close" inputs must result in "close" outputs. This ensures that computational errors do not amplify uncontrollably during computation.
- Continuity (Cont): An infinitary rule reflecting that if an equation holds for all values strictly greater than $\epsilon$, it must hold for $\epsilon$ itself.
The Categorical Perspective
To formalize these ideas, the research bridges logic with category theory, specifically by examining monads on the category of extended metric spaces (EMet). This transition allows "distance" to be treated with the same mathematical rigor that universal algebraists apply to "equality."
As shown in the diagrams above, the theory lifts the standard "trinity" of equational reasoning—equations, Lawvere theories, and monads—from the world of Sets to the world of Metric Spaces. The mapping from a set $X$ to its free algebra $\mathbf{T}_\mathcal{U}[X]$ preserves the essential structure while incorporating the metric constraints defined by the quantitative theory $\mathcal{U}$.
The Kantorovich Metric as a Free Construction
One of the most significant results of this work is the discovery that the Kantorovich (Wasserstein) metric—widely used in optimal transport and machine learning—is not merely an external tool for measuring probability distributions. Instead, it emerges as the unique metric arising from building a free algebra over a simple set of quantitative axioms known as Interpolative Barycentric Algebras.
By adjusting the quantitative axioms applied to these barycentric algebras (which model convex combinations like $p \cdot x + (1-p) \cdot y$), the logic can be "tuned" to represent different metrics, such as Total Variation or the Kantorovich metric. This suggests that these metrics are fundamental properties of the underlying algebraic structure of probability.
Key Results and Future Directions
The paper establishes a quantitative version of the Birkhoff Completeness Theorem, proving that any quantitative equation true in all models (semantics) can be derived using the proposed logical rules (syntax). Furthermore, it demonstrates that standard computational effects—such as exceptions or state updates—have natural quantitative analogues. For instance, the distance between two crashing programs might be measured by the difference in their execution times before failure.
Despite these advances, challenges remain. The current requirement for non-expansiveness (Lipschitz constant $\le 1$) is restrictive. Future research aims to relax these conditions to general Lipschitz continuity and to develop "quantitative term rewriting" systems for automated optimization of probabilistic code while tracking precision loss.
Summary updated