Skip to Main content Skip to Navigation
Reports

$\lambda\upsilon$, a calculus of explicit substitutions which preserves strong normalisation

Abstract : Explicit substitutions were proposed by Abadi, Cardelli, Curien, Hardin and Lévy to internalise substitutions into $\lambda$-calculus and to propose a mechanism for computing on substitutions. $\lambda\upsilon$ is another view of the same concept which aims to explain the process of substitution and to decompose it in small steps. $\lambda\upsilon$ is simple and preserves strong normalisation. Apparently that important property cannot stay with another important one, namely confluence on open terms. The spirit of $\lambda\upsilon$ is closely related to another calculus of explicit substitutions proposed by de Bruijn and called $C\lambda\xi\phi$. In this paper, we introduce $\lambda\upsilon$, we present $C\lambda\xi\phi$ in the same framework as $\lambda\upsilon$ and we compare both calculi. Moreover, we prove properties of $\lambda\upsilon$; namely $\lambda\upsilon$ correctly implements $\beta$ reduction, $\lambda\upsilon$ is confluent on closed terms, i.e., on terms of classical $\lambda$-calculus and on all terms that are derived from those terms, and finally $\lambda\upsilon$ preserves strong normalization of $\beta$-reduction.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074197
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 2:43:58 PM
Last modification on : Thursday, February 11, 2021 - 2:48:31 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:13:23 PM

Identifiers

  • HAL Id : inria-00074197, version 1

Collections

Citation

Zine-El-Abidine Benaissa, Daniel Briaud, Pierre Lescanne, Jocelyne Rouyer-Degli. $\lambda\upsilon$, a calculus of explicit substitutions which preserves strong normalisation. [Research Report] RR-2477, INRIA. 1995. ⟨inria-00074197⟩

Share

Metrics

Record views

226

Files downloads

231