$\lambda\upsilon$, a calculus of explicit substitutions which preserves strong normalisation
Résumé
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.