A Partial Metric Semantics of Higher-Order Types and Approximate Program Transformations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

A Partial Metric Semantics of Higher-Order Types and Approximate Program Transformations

Résumé

Program semantics is traditionally concerned with program equivalence. However, in fields like approximate, incremental and probabilistic computation, it is often useful to describe to which extent two programs behave in a similar, although non equivalent way. This has motivated the study of program (pseudo)metrics, which have found widespread applications, e.g. in differential privacy. In this paper we show that the standard metric on real numbers can be lifted to higher-order types in a novel way, yielding a metric semantics of the simply typed lambda-calculus in which types are interpreted as quantale-valued partial metric spaces. Using such metrics we define a class of higher-order denotational models, called diameter space models, that provide a quantitative semantics of approximate program transformations. Noticeably, the distances between objects of higher-types are elements of functional, thus non-numerical, quantales. This allows us to model 19 contextual reasoning about arbitrary functions, thus deviating from classic metric semantics.
Fichier principal
Vignette du fichier
CSL 2021.pdf (620.06 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03009790 , version 1 (17-11-2020)

Identifiants

Citer

Guillaume Geoffroy, Paolo Pistone. A Partial Metric Semantics of Higher-Order Types and Approximate Program Transformations. CSL 2021 - Computer Science Logic, Jan 2021, Lubjana, Slovenia. ⟨10.4230/LIPIcs.CSL.2021.23⟩. ⟨hal-03009790⟩
144 Consultations
529 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More