Metric reasoning about λ-terms: The affine case
Raphaëlle Crubillé, Ugo Dal Lago · 2015
Terms of Church's λ-calculus can be considered equivalent along many different definitions, but context equiv-alence is certainly the most direct and universally accepted one. If the underlying calculus becomes probabilistic, however, equivalence is too discriminating: terms which have totally unrelated behaviours are treated the same as terms which behave very similarly. We study the problem of evaluating the distance between affine λ-terms. A natural generalisation of context equiv-alence, is shown to be characterised by a notion of trace distance, and to be bounded from above by a co inductively defined distance based on the Kantorovich metric on distributions. A different, again fully-abstract, tuple-based notion of trace distance is shown to be able to handle nontrivial examples.