On The Metric Nature of (Differential) Logical Relations

Ugo Dal Lago ORCID:0000-0001-9200-070X, Naohiko Hoshino ORCID:0000-0003-2647-0310, Paolo Pistone ORCID:0000-0003-4250-9051 · 2026

Read On The Metric Nature of (Differential) Logical Relations by Ugo Dal Lago ORCID:0000-0001-9200-070X, Naohiko Hoshino ORCID:0000-0003-2647-0310, Paolo Pistone ORCID:0000-0003-4250-9051 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-01317.txt.

Introduction

Dal Lago, Hoshino, and Pistone clarify the metric nature of differential logical relations. These methods measure distances between higher-order programs, where function-program distances are themselves functions relating input errors to output errors. They introduce quasi-quasi-metrics, showing the cartesian closed class of quasi-quasi-metric spaces mirrors the build of these relations. The cartesian closed shape yields a core lemma, a piecewise thought rule for program gaps. They also prove type-reading quasi-quasi-metric spaces satisfy forms of strong chain, closeness, and weak mirror rules.

Catalog record

CREATORUgo Dal Lago ORCID:0000-0001-9200-070X, Naohiko Hoshino ORCID:0000-0003-2647-0310, Paolo Pistone ORCID:0000-0003-4250-9051
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127859
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.01317

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On The Metric Nature of (Differential) Logical Relations Ugo Dal Lago ORCID:0000-0001-9200-070X, Naohiko Hoshino ORCID:0000-0003-2647-0310, Paolo Pistone ORCID:0000-0003-4250-9051 Abstract . Differential logical relations are methods to measure distances between higher-order programs where distances between functional programs are themselves functions , relating errors in inputs with errors in outputs. This way, differential logical relations provide a more fine-grained and contextual information of program distances. This paper aims to clarify the metric nature of differential logical relations. We introduce the notion of quasi-quasi-metrics and observe that the cartesian closed category of quasi-quasi-metric spaces reflects the construction of differential logical relations in the literature. The cartesian closed structure induces a fundamental lemma, which can be seen as a compositional reasoning principle for program distances. Furthermore, we investigate the quasi-quasi-metric spaces arising from the interpretation of types, and we prove that they satisfy variants of the strong transitivity condition and indistancy condition, as well as a weak form of the symmetry condition. In the last part of this paper, we introduce a notion of differential prelogical relations arising as a quantitative counterpart of the framework of prelogical relations. Roughly speaking, differential prelogical relations are quasi-quasi-metrics on the collection of programs. The poset of differential prelogical relations has the finest differential prelogical relation presented as a formal quantitative equational theory, while the poset lacks a coarsest differential prelogical relation. The absence of a coarsest differential prelogical relation contrasts with the situations of typed lambda calculi, where the contextual equivalences serve as the coarsest program equivalences. [a,b] [c] [d] 1. Introduction Program equivalence is a crucial concept in program semantics, and ensures that different implementations of a program produce exactly the same results under the same conditions, i.e., in any environment. This concept is fundamental in program verification, code optimization, and for enabling reliable refactoring: by proving that two programs are equivalent, developers and compiler designers can confidently replace one program with the other, knowing that the behavior and outcomes will remain consistent. In this respect, guaranteeing that the underlying notion of program equality is a congruence is of paramount importance. In the research communities mentioned above, however, it is known that comparing programs through a notion of equivalence without providing the possibility of measuring the distance between non-equivalent programs makes it impossible to validate many interesting and useful program transformations [ 28 ] . All this has generated interest around the concepts of program metrics and more generally around the study of techniques through which to quantitatively compare non-equivalent programs, so as, e.g., to validate those program transformations which do not introduce too much of an error [ 32 , 27 ] . What corresponds, in a quantitative context, to the concept of congruence? Once differences are measured by some (pseudo-)metric, a natural answer to this question is to require that any language construct does not increase distances, that is, that they are non-expansive . Along with this, the standard properties of (pseudo-)metrics, like the triangle inequality d(x,z)+d(z,y)\geq d(x,y) , provide general principles that are very useful in metric reasoning, replacing standard qualitative principles (e.g., in this case, transitivity \mathrm{eq}(x,z)\land\mathrm{eq}(z,y)\vdash\mathrm{eq}(x,y) ). Still, as already observed on many occasions [ 9 , 10 ] , the restriction to non-expansive language constructs with respect to some purely numerical metric turns out to be too severe in practice. On the one hand, the literature focusing on higher-order languages has mostly restricted its attention to linear or graded languages [ 32 , 2 ] , due to well-known difficulties in constructing metric models for full “simply-typed” languages [ 12 ] . On the other hand, even if one restricts to a linear language, the usual metrics defined over functional types are hardly useful in practice, as they assign distances to functions via a comparison of their values in the worst case. For instance, as shown in [ 9 ] , the distance between the identity function on \mathbb{R} and the sine function is typically \infty since their values grow arbitrarily far from each other in the worst case, even though their behaviour is very close near 0 . The differential logical relations [ 9 , 10 , 29 , 11 ] have been introduced as a solution to the aforementioned problems. In this setting, which natively works for unrestricted higher-order languages, the distance between two programs is not necessarily a single number. For instance, two programs of functional type are far apart according to a function itself, which measures how the error in the output depends on the error in the input, but also on the value of the input itself. This way, the notion of distance becomes sufficiently expressive of local differences, at the same time guaranteeing the possibility of compositional reasoning. This paradigm also scales to languages with duplication, recursion [ 10 ] , and works even in the presence of effects [ 11 ] . A similar idea targeting a graded type theory can be found in a recent work [ 35 ] . In the literature on program metrics, it has become common to consider quantale -valued metrics [ 22 , 38 ] . This means that, as for the differential logical relations, the distance between two programs belongs to some suitable algebra of “quantities”, i.e., a quantale. This has led to the study of different classes of quantale-valued metrics, each characterized by a particular formulation of the reflexivity condition and the triangle inequality. Among these, quasi-metrics [ 20 ] and partial metrics [ 5 , 23 ] have been explored for the study of domains, even for higher-order languages [ 17 , 26 ] . While the first obeys the usual triangle inequality, or the transitivity condition, the second obeys the strong transitivity condition d(x,y)+d(y,z)\leq d(x,z)+d(y,y) . The latter also takes into account the replacement of the standard reflexivity condition d(x,x)=0 by the left quasi-reflexivity condition d(x,x)\leq d(x,y) and the right quasi-reflexivity condition d(y,y)\leq d(x,y) , implying that a point need not be at distance zero from itself. A natural question is thus: do the distances between programs that are obtained via differential logical relations constitute some form of quantale-valued metric? In particular, what forms of reflexivity and transitivity do these relations support? The original paper [ 9 ] defined symmetric differential logical relations and gave a very weak form of triangle inequality. Subsequent works, relating to the more natural asymmetric case, have either ignored the metric question [ 10 , 11 ] or shown that the distances produced must violate both the reflexivity of quasi-metric and the strong transitivity of partial metrics [ 17 , 29 ] . This paper provides an answer to the above question, building a bridge between current methods for higher-order program distances and the well-established literature on quantale-valued metrics. More specifically, we introduce the notion of quasi-quasi-metrics , obtained by weakening the notion of partial metrics. The first “quasi” in the name “quasi-quasi-metric” comes from left quasi- reflexivity, and the second “quasi” means the absence of symmetry. The category \mathbf{Qqm} of quasi-quasi-metric spaces is cartesian closed, and the cartesian closed structure reflects the construction of differential logical relations. This implies that the construction of differential logical relations preserves the structure of quasi-quasi-metric spaces. We introduce a simply typed

Read the complete text