💻 computer science

On the Metric Nature of (Differential) Logical Relations

This paper clarifies the metric nature of differential logical relations by introducing quasi-quasi-metric spaces to model program distances, establishing a fundamental lemma for compositional reasoning, and demonstrating that while these spaces support a finest differential prelogical relation, they lack a coarsest counterpart unlike traditional contextual equivalences.

Original authors: Ugo Dal Lago, Naohiko Hoshino, Paolo Pistone

Published 2026-03-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ugo Dal Lago, Naohiko Hoshino, Paolo Pistone

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a software engineer trying to decide between two versions of a program. In the old days, the only question was: "Are they exactly the same?"

If the answer was "Yes," you could swap them without worry. If "No," you had to pick one and hope for the best. This is like checking if two apples are identical. But in the real world, programs are rarely exactly identical. One might be slightly faster, or one might produce a result that is off by a tiny fraction.

This paper is about a new way to measure how different two programs are, not just if they are the same or different. It's like moving from a "Yes/No" switch to a ruler that can measure the exact distance between two things.

Here is the breakdown of the paper's big ideas using simple analogies:

1. The Problem with "Standard" Rulers

Imagine you have two functions (programs that take an input and give an output).

Function A is the Identity function: It takes a number and gives it back unchanged ( $x \to x$ ).
Function B is the Sine function: It takes a number and gives you the sine of that number ( $x \to \sin(x)$ ).

If you use a standard ruler (a traditional metric) to measure the distance between these two functions, you look at the worst-case scenario. Since $\sin(x)$ and $x$ can get infinitely far apart as $x$ gets huge, the distance between them is infinity.

The Flaw: This tells you nothing about how they behave near zero. Near zero, $\sin(x)$ and $x$ are almost twins! A standard ruler is too blunt; it says "They are infinitely different" even when they are practically identical in a specific neighborhood.

2. The Solution: Differential Logical Relations (The "Smart Ruler")

The authors introduce a concept called Differential Logical Relations. Instead of giving you a single number (like "5 meters"), this method gives you a function that describes the distance.

Think of it like a dynamic map rather than a static ruler.

If you ask, "How different are these programs?" the answer isn't "Infinity."
The answer is: "The difference depends on where you are. If you are near zero, the difference is tiny. If you are near a million, the difference is huge."

This is incredibly useful because it allows programmers to say, "These two programs are different, but only in a way that won't break my system if I stay within this safe range."

3. The Mathematical Engine: "Quasi-Quasi-Metrics"

To make this "Smart Ruler" work mathematically, the authors had to invent a new kind of geometry. They call it Quasi-Quasi-Metrics.

Let's break down the weird name:

Metric: A way to measure distance.
Quasi-Metric: A distance that doesn't have to be fair. Usually, distance from A to B is the same as B to A. But in programming, changing Input A to B might be easy, but changing B back to A might be hard. So, the distance is asymmetric (one-way).
Quasi-Quasi-Metric: This adds a second twist. In standard geometry, the distance from a point to itself is always zero. But in this new math, the distance from a program to itself might not be zero!

The Analogy: Imagine you are measuring the "effort" to transform a shape.

If you have a perfect circle, the effort to keep it a circle is zero.
But if you have a slightly wobbly circle (a program with a tiny bug), the effort to "fix" it to be a perfect circle might be small, but not zero.
In this new math, the "self-distance" tells you how much "noise" or "error" exists inside the program itself.

4. The "Fundamental Lemma" (The Safety Net)

The paper proves a "Fundamental Lemma." Think of this as a safety guarantee.

It says: "If you build a complex program out of smaller, safe pieces, the whole program will be safe."

If you know the distance between two small inputs, and you know how your program transforms those distances, you can mathematically prove the distance between the final outputs.
This allows programmers to reason about errors compositionally. You don't have to test the whole giant machine; you just test the gears, and the math guarantees the machine works.

5. The Big Discovery: No "Perfect" Worst-Case

The most surprising part of the paper is in the conclusion.

In the world of standard program testing, there is a concept called Contextual Equivalence. This is the "coarsest" (most relaxed) way to say two programs are the same. It's the ultimate "Are they the same?" test. If they pass this, they are interchangeable in any situation.

The authors asked: "Is there a 'coarsest' way to measure the distance between programs?" (i.e., is there a single "Contextual Metric" that tells us the maximum possible difference between two programs in any situation?)

The Answer: No.

They proved that for these "Smart Rulers," there is no single worst-case metric.

Why? Because the "distance" between programs is so complex and dependent on the specific context (the input values) that you can't boil it down to one single "maximum difference" number or function that covers every possible scenario.
The Metaphor: Imagine trying to find the "maximum height" of a mountain range that changes shape every time you look at it. You can measure specific peaks, but you can't define one single "highest point" that applies to the whole range at once.

Summary

This paper does three main things:

Invented a new math (Quasi-Quasi-Metrics) to measure program differences more accurately than before.
Proved it works by showing that you can build complex distance measurements from simple ones (The Fundamental Lemma).
Found a limit: They discovered that while we can measure differences very precisely, we cannot define a single "maximum difference" metric for all programs. The complexity of software is too rich to be captured by one single "worst-case" ruler.

In everyday terms: We finally have a tool to measure how much a program is broken, not just if it is broken. But we learned that the universe of software is so vast and nuanced that there is no single "maximum error" that applies to everything.

1. Problem Statement

The paper addresses a fundamental gap in the quantitative analysis of higher-order programs. While program equivalence (qualitative) is well-understood via logical relations and contextual equivalence, program distance (quantitative) presents significant challenges:

Limitations of Standard Metrics: Traditional metrics (e.g., pseudo-metrics) often fail in higher-order settings because they require non-expansiveness (distance does not increase under function application). This is too restrictive for full simply-typed lambda calculi. Furthermore, standard metrics often rely on worst-case analysis (e.g., the distance between $id$ and $\sin$ on $\mathbb{R}$ is infinite), failing to capture local behavioral similarities.
Differential Logical Relations (DLR): DLRs were introduced to solve this by measuring distances between programs as functions (relating input errors to output errors) rather than single numbers. However, the underlying metric structure of DLRs was unclear. Previous attempts to model them as standard quasi-metrics or partial metrics failed because DLRs violate standard reflexivity (distance from a program to itself is not necessarily zero) and standard transitivity.
The Core Question: What is the precise metric nature of the distances generated by differential logical relations? Do they form a known class of quantale-valued metrics, and if so, what are their specific algebraic properties?

2. Methodology

The authors employ a combination of categorical semantics, quantale theory, and logical relations to formalize the metric structure of DLRs.

Quantales: They utilize quantales (complete lattices with a monoid structure) to generalize the notion of "distance" beyond real numbers, allowing distances to be functions or other algebraic structures.
Logical Relations Lifting: They analyze how logical relations are lifted from ground types to function types. They observe that standard reflexivity and transitivity do not lift directly to the differential setting.
Categorical Modeling: They construct a specific category, Qqm, of "quasi-quasi-metric spaces" and demonstrate that it is Cartesian Closed (CCC). This allows them to model the simply-typed lambda calculus ( $\Lambda_{Real}$ ) within this category.
Prelogical Relations: They extend the framework of prelogical relations (a generalization of logical relations) to the differential setting to investigate the lattice structure of program distances.

3. Key Contributions

A. Introduction of Quasi-Quasi-Metrics

The authors introduce a new class of quantale-valued metrics called quasi-quasi-metrics.

Definition: A ternary relation $r \subseteq X \times Q \times X$ $r \subseteq X \times Q \times X$ (where $Q$ $Q$ is a quantale) is a quasi-quasi-metric if it is:
1. Quasi-reflexive: If $(x, a, y) \in r$ , then $(x, a, x) \in r$ . (This weakens standard reflexivity $d(x,x)=0$ ).
2. Transitive: If $(x, a, y) \in r$ and $(y, b, z) \in r$ , then $(x, a \otimes b, z) \in r$ .
Naming: The first "quasi" refers to the lack of symmetry (as in quasi-metrics). The second "quasi" refers to the weakened reflexivity (as in quasi-preorders).
Significance: This structure naturally captures the behavior of DLRs, where the "distance" of a function to itself is not zero but a function describing its sensitivity (derivative).

B. The Category Qqm and Cartesian Closure

The paper proves that the category Qqm of quasi-quasi-metric spaces is Cartesian Closed.

Objects: Quasi-quasi-metric spaces.
Morphisms: Triples $(f, d, g)$ representing a function $f$ , a "derivative" $d$ (mapping input errors to output errors), and a target function $g$ .
Implication: The Cartesian closed structure of Qqm mirrors the construction of differential logical relations. This provides a rigorous categorical foundation for DLRs, showing they are not just ad-hoc constructions but arise naturally from the structure of the category.

C. The Fundamental Lemma

By interpreting the simply-typed lambda calculus $\Lambda_{Real}$ in the category Qqm, the authors derive the Fundamental Lemma for differential logical relations as a direct consequence of the categorical interpretation.

Result: For any well-typed term $t$ , the interpretation $(\llbracket t \rrbracket, \{|t|\}, \llbracket t \rrbracket)$ is a morphism in Qqm. Here, $\{|t|\}$ acts as the derivative, relating input errors to output errors.

D. Additional Metric Properties

The authors investigate specific properties of the quasi-quasi-metrics arising from type interpretations:

Left Strong Transitivity: They prove these metrics satisfy a variant of strong transitivity: $(\phi(y,y) \multimap \phi(x,y)) \otimes \phi(y,z) \leq \phi(x,z)$ . This is a crucial property distinguishing them from standard partial metrics.
Weak Symmetry: They identify a weak form of symmetry that holds for these spaces, linking the self-distance of a point to the symmetry of the relation.
Self-Indistancy: They show that if the distance between $x$ and $y$ is bounded by the self-distance of $x$ , then $x=y$ .

E. Differential Prelogical Relations and Lattice Structure

The authors introduce differential prelogical relations as type-indexed families of quasi-quasi-metrics satisfying the fundamental property.

Poset Structure: The set of differential prelogical relations forms a poset under inclusion.
Least Element: The poset has a least element (the finest metric), which corresponds to a quantitative equational theory (syntactic equality with quantitative bounds).
Absence of Greatest Element: Crucially, the authors prove that the poset lacks a greatest element.
- Significance: In qualitative program equivalence, the greatest element is contextual equivalence (the coarsest equivalence). The absence of a greatest differential prelogical relation implies there is no natural notion of "contextual metric" for $\Lambda_{Real}$ . The attempt to define a metric that captures all contextual differences fails because the fundamental lemma only provides a lower bound on self-distances, not an exact characterization.

4. Results

Formalization: DLRs are formally identified as morphisms in the category of quasi-quasi-metric spaces.
Categorical Bridge: The construction of DLRs is shown to be the categorical product/exponential structure of Qqm.
Metric Characterization: The distances in DLRs satisfy Left Strong Transitivity and Weak Symmetry, but not standard reflexivity or full symmetry.
Negative Result: There is no "contextual metric" (greatest differential prelogical relation) for the simply-typed lambda calculus, contrasting with the existence of contextual equivalence in qualitative semantics.

5. Significance

Theoretical Unification: The paper bridges the gap between the operational/relational approach of differential logical relations and the algebraic approach of quantale-valued metrics. It provides a solid mathematical foundation for reasoning about program distances in higher-order languages.
New Metric Paradigm: By introducing quasi-quasi-metrics, the authors offer a flexible framework that accommodates the non-zero self-distances (derivatives) inherent in differential analysis, which standard metrics cannot handle.
Limitations of Contextual Metrics: The proof that no greatest differential prelogical relation exists is a profound insight. It suggests that while we can define fine-grained syntactic metrics, defining a coarse-grained "contextual" metric that captures all observable behavioral differences is mathematically impossible in the current framework. This highlights a fundamental difference between qualitative equivalence and quantitative distance in higher-order computation.
Future Directions: The work opens avenues for applying topological and categorical methods from quantale theory to program analysis, and suggests that future work on contextual metrics may require rethinking the fundamental lemma or the definition of context distances.