Interaction Equivalence
Beniamino Accattoli, Adrienne Lancelot, Giulio Manzonetto, Gabriele Vanoni
Abstract
Contextual equivalence is the de facto standard notion of program equivalence. A key theorem is that contextual equivalence is an equational theory . Making contextual equivalence more intensional, for example taking into account the time cost of the computation, seems a natural refinement. Such a change, however, does not induce an equational theory, for an apparently essential reason: cost is not invariant under reduction. In the paradigmatic case of the untyped λ -calculus, we introduce interaction equivalence . Inspired by game semantics, we observe the number of interaction steps between terms and contexts but–crucially–ignore their internal steps. We prove that interaction equivalence is an equational theory and characterize it as B , the well-known theory induced by Böhm tree equality. It is the first observational characterization of B obtained without enriching the discriminating power of contexts with extra features such as non-determinism. To prove our results, we develop interaction-based refinements of the Böhm-out technique and of intersection types.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- Intersection types and (positive) almost-sure termination cites Consuming and Persistent Types for Classical Logic
- Higher Order Bayesian Networks, Exactly cites Intersection types and (positive) almost-sure termination
- A Metalanguage for Cost-Aware Denotational Semantics cites Recurrence extraction for functional programs through call-by-push-value
Builds on6
- Intersection types and (positive) almost-sure terminationUgo Dal Lago, Claudia Faggian, Simona Ronchi Della RoccaPOPL 2021 · 21 citations
- Recurrence extraction for functional programs through call-by-push-valueG. A. Kavvos, Edward Morehouse, Daniel R. Licata, Norman DannerPOPL 2020 · 20 citations
- Consuming and Persistent Types for Classical LogicDelia Kesner, Pierre VialLICS 2020 · 11 citations
- A Metalanguage for Cost-Aware Denotational SemanticsYue Niu, Robert HarperLICS 2023 · 5 citations
- Higher Order Bayesian Networks, ExactlyClaudia Faggian, Daniele Pautasso, Gabriele VanoniPOPL 2024 · 4 citations
Related papers
- The Space of InteractionBeniamino Accattoli, Ugo Dal Lago, Gabriele VanoniLICS 2021 · 4 citations
- Why Are Proofs Relevant in Proof-Relevant Models?Axel Kerinec, Giulio Manzonetto, Federico OlimpieriPOPL 2023 · 6 citations
- Taylor subsumes Scott, Berry, Kahn and PlotkinDavide Barbarossa, Giulio ManzonettoPOPL 2020 · 15 citations
- A Compositional Cost Model for the λ-calculusJames LairdLICS 2021
- The (In)Efficiency of interactionBeniamino Accattoli, Ugo Dal Lago, Gabriele VanoniPOPL 2021 · 13 citations
