$\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.
Type de document :
[Research Report] RR-2477, INRIA. 1995
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:43:58
Dernière modification le : samedi 17 septembre 2016 - 01:06:55
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:13:23



  • HAL Id : inria-00074197, version 1



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〉



Consultations de la notice


Téléchargements de fichiers