A strong call-by-need calculus - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Logical Methods in Computer Science Année : 2023

A strong call-by-need calculus

Résumé

We present a call-by-need λ-calculus that enables strong reduction (that is, reduction inside the body of abstractions) and guarantees that arguments are only evaluated if needed and at most once. This calculus uses explicit substitutions and subsumes the existing strong-call-by-need strategy, but allows for more reduction sequences, and often shorter ones, while preserving the neededness. The calculus is shown to be normalizing in a strong sense: Whenever a λ-term t admits a normal form n in the λ-calculus, then any reduction sequence from t in the calculus eventually reaches a representative of the normal form n. We also exhibit a restriction of this calculus that has the diamond property and that only performs reduction sequences of minimal length, which makes it systematically better than the existing strategy. We have used the Abella proof assistant to formalize part of this calculus, and discuss how this experiment affected its design. In particular, it led us to derive a new description of call-by-need reduction based on inductive rules.
Fichier principal
Vignette du fichier
main.pdf (430.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03409681 , version 1 (29-10-2021)
hal-03409681 , version 2 (02-08-2022)
hal-03409681 , version 3 (06-03-2023)

Identifiants

Citer

Thibaut Balabonski, Antoine Lanco, Guillaume Melquiond. A strong call-by-need calculus. Logical Methods in Computer Science, 2023, 19 (1), pp.39. ⟨10.46298/lmcs-19(1:21)2023⟩. ⟨hal-03409681v3⟩
207 Consultations
74 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More