11:15 to 12:15
Seminar

Interaction equivalence

Adrienne Lancelot
11:15 to 12:15
Mireille-Delmas-Marty Amphitheater, Marcelin-Berthelot Site
Open to all, subject to availability
-

Abstract

Contextual equivalence is a standard notion of programme equivalence; it is an equational theory, being invariant under reduction and compositional. It seems natural to make contextual equivalence more intensional by taking into account the temporal cost of evaluating a programme. Such an equivalence is not an equational theory for an obvious reason: the temporal cost of computation is not invariant under reduction.

In the idealised case of untyped lambda-calculus, we introduce interaction equivalence. This equivalence takes into account the number of interaction steps between programmes and their execution context whilst ignoring internal computation steps, by proposing a syntactic construction inspired by game theory. We prove that interaction equivalence is an equational theory and characterise it via the theory 𝓑, induced by the Böhm tree equality. This is the first observational characterisation of this 𝓑-theory obtained without adding a discriminating power to contexts, such as non-determinism.

Interaction equivalence does not allow us to determine which programmes are better in terms of this notion of interaction cost. To do so, we must introduce a pre-order of interaction improvement. We characterise, via an asymmetric variant of the 𝓑 theory, exactly which optimisations are possible for lambda-terms.

To demonstrate these results, we have developed interaction-based refinements of the Böhm-out technique and type intersections, which are briefly presented in the talk.

Speaker(s)

Adrienne Lancelot

University of Bologna