On Generalized Metric Spaces for the Simply Typed Lambda-Calculus

Generalized metrics, arising from Lawvere's view of metric spaces as enriched categories, have been widely applied in denotational semantics as a way to measure to which extent two programs behave in a similar, although non equivalent, way. However, the application of generalized metrics to higher-order languages like the simply typed lambda calculus has so far proved unsatisfactory. In this paper we investigate a new approach to the construction of cartesian closed categories of generalized metric spaces. Our starting point is a quantitative semantics based on a generalization of usual logical relations. Within this setting, we show that several families of generalized metrics provide ways to extend the Euclidean metric to all higher-order types.

• This work has been funded by the ERC CoG 818616 "DIAPASoN".

2 Higher-Order Metric Semantics

Program metrics have been widely investigated to capture properties like program similarity and sensitivity. The fundamental idea is usually to associate types σ, τ with metric spaces, and programs f : σ → τ with non-expansive, or more generally Lipschitz continuous functions. This means that for all programs t, u of type σ, the distance between f (t) and f (u) does not exceed that between t and u by more than a fixed factor L (formally, d(f (t), f (u)) ≤ L • d(t, u)).