Hostname: page-component-f554764f5-c4bhq Total loading time: 0 Render date: 2025-04-16T05:48:34.164Z Has data issue: false hasContentIssue false
  • English
  • Français

λν, a calculus of explicit substitutions which preserves strong normalisation

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Zine-El-Abidine Benaissa ,
Daniel Briaud ,
Pierre Lescanne  and
Jocelyne Rouyer-Degli
Zine-El-Abidine Benaissa
Affiliation:
Centre de Recherche en Informatique de Nancy (CNRS), France e-mail: [email protected]
Daniel Briaud
Affiliation:
Centre de Recherche en Informatique de Nancy (CNRS), France e-mail: [email protected]
Pierre Lescanne
Affiliation:
INRIA-Lorraine, Campus Scientifique, BP 239, F54506 Vandœuvre-lès-Nancy, France e-mail: [email protected]
Jocelyne Rouyer-Degli
Affiliation:
INRIA-Lorraine, Campus Scientifique, BP 239, F54506 Vandœuvre-lès-Nancy, France e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Explicit substitutions were proposed by Abadi, Cardelli, Curien, Hardin and Lévy to internalise substitutions into λ-calculus and to propose a mechanism for computing on substitutions. λν is another view of the same concept which aims to explain the process of substitution and to decompose it in small steps. It favours simplicity and preservation of strong normalisation. This way, another important property is missed, namely confluence on open terms. In spirit, λν is closely related to another calculus of explicit substitutions proposed by de Bruijn and called CλξΦ. In this paper, we introduce λν, we present CλξΦ in the same framework as λν and we compare both calculi. Moreover, we prove properties of λν; namely λν correctly implements β reduction, λν is confluent on closed terms, i.e. on terms of classical λ-calculus and on all terms that are derived from those terms, and finally λν preserves strong normalisation in the following sense: strongly β normalising terms are strongly λν normalising.

Type
Articles
Information
Journal of Functional Programming , Volume 6 , Issue 5 , September 1996 , pp. 699 - 722
Copyright
Copyright © Cambridge University Press 1996

References

Abadi, M., Cardelli, L., Curien, P.-L. and Lévy, J.-J. (1990) Explicit substitutions. Tech. rept. 54, Digital Systems Research Center. Preliminary version in Proc. of the 17th POPL conference,Orlando, FL, USA.CrossRefGoogle Scholar
Abadi, M., Cardelli, L., Curien, P.-L. and Lévy, J.-J. (1991) Explicit substitutions. J. Functional Programming, 1(4): 375–416.CrossRefGoogle Scholar
Barendregt, H. P. (1984) The Lambda-Calculus, its syntax and semantics. Studies in Logic and the Foundation of Mathematics. Elsevier.Google Scholar
Bourbaki, N. (1954) Éléments de mathématiques: Théories des ensembles. Vol. 1. Hermann & Cie.Google Scholar
Briaud, D. (1995) An explicit Eta rewrite rule. In: Dezani, M., editor, Int. Conf. on Typed Lambda Calculus and Applications.Google Scholar
Curien, P.-L. (1983) Combinateurs catégoriques, algorithmes séquentiels et programmation applicative. Thèse de Doctorat d'Etat, Université Paris 7.Google Scholar
Curien, P.-L. (1986a) Categorical combinators. Information and Control, 69: 188–254.CrossRefGoogle Scholar
Curien, P.-L. (1986b) Categorical Combinators, Sequential Algorithms and Functional Programming. Pitman.Google Scholar
Curien, P.-L. (1991) An abstract framework for environment machines. Theoretical Computer Science, 82: 389–402.CrossRefGoogle Scholar
Curien, P.-L., Hardin, Th. and Lévy, J.-J. (1992) Confluence properties of weak and strong calculi of explicit substitutions. RR 1617. INRIA, Rocquencourt.Google Scholar
Curry, H. B. and Feys, (1958) Combinatory Logic. Vol. 1. Elsevier.Google Scholar
de Bruijn, N. G. (1972) Lambda calculus with nameless dummies, a tool for automatic formula manipulation, with application to the Church–Rosser theorem. Proc. koninkl. nederl. akademie van wetenschappen, 75(5): 381–392.CrossRefGoogle Scholar
de Bruijn, N. G. (1978) A namefree lambda calculus with facilities for internal definition of expressions and segments. TH-Report 78-WSK-03. Technological University Eindhoven, Netherlands, Department of Mathematics.Google Scholar
Dershowitz, N. and Jouannaud, J.-P. (1990) Rewrite Systems. In: van Leeuwen, J., editor, Handbook of Theoretical Computer Science, Chapter 6, pp. 244–320. Elsevier.Google Scholar
Ehrhrard, T. (1988) Une sémantique catégorique des types dépendants. Application au calcul des constructions. Thèse de Doctorat d'Université, Universite Paris VII.Google Scholar
Field, J. (1990) On laziness and optimality in lambda interpreters: Tools for specification and analysis. Proc. 17th annual ACM symposium on Principles Of Programming Languages,Orlando, FL, USA.ACM.CrossRefGoogle Scholar
Hardin, T. (1992) Eta-conversion for the languages of explicit substitutions. In Kirchner, H. and Levi, G., editors, Proceedings 3rd International Conference on Algebraic and Logic Programming, (Volterra, Italy). Lecture Notes in Computer Science 632, pp. 306–321. Springer-Verlag.CrossRefGoogle Scholar
Hardin, Th. (1987) Résultats de confluence pour les règies fortes de la logique combinatoire catégorique et liens avec les lambda-calculs. Thèse de Doctorat d'Etat, Université Paris 7.Google Scholar
Hardin, Th. (1989) Confluence results for the pure strong categorical combinatory logic CCL: λ-calculi as subsystems of CCL. Theoretical Computer Science, 65: 291–342.CrossRefGoogle Scholar
Hardin, Th. and Lévy, J.-J. (1989) A confluent calculus of substitutions. France-Japan Artificial Intelligence and Computer Science Symposium.Google Scholar
Kamareddine, F. and Ríos, A. (1995) A λ-calculus à la de Bruijn with explicit substitutions. PLILP'95: Lecture Notes in Computer Science. Springer-Verlag.Google Scholar
Kamereddine, F. and Nederpelt, R. P. (1993) On stepwise explicit substitutions. Int. J. Foundations of Computer Science, 4(3): 197–240.CrossRefGoogle Scholar
Lescanne, P. (1992) Termination of rewrite systems by elementary interpretations. In: Kirchner, H. and Levi, G., editors, Proceedings 3rd International Conference on Algebraic and Logic Programming: Lecture Notes in Computer Science 632, Volterra, Italy. Springer-Verlag.Google Scholar
Lescanne, P. (1994) From λσ to λν, a journey through calculi of explicit substitutions. In: Boehm, H., editor, Proceedings of the 21st Annual ACM Symposium on Principles Of Programming Languages, pp. 60–69. Portland, OR, USA. ACM.Google Scholar
Lescanne, P. and Rouyer-Degli, J. (1994) The calculus of explicit substitutions λν. Tech. rept. RR-2222, INRIA-Lorraine.Google Scholar
Melliès, P.-A. (1995) Typed λ-calculi with explicit substitutions may not terminate. In: Dezani, M., editor, Int. Conf. on Typed Lambda Calculus and Applications.Google Scholar
Ríos, A. (1993) Contributions à l'étude des λ-calculs avec des substitutions explicites. Thèse de Doctorat d'Université, Universite Paris VII.Google Scholar
Rose, K. and Bloo, R. (1995) Deriving requirements for preservation of strong normalisation in lambda calculi with explicit substitution. Available as ftp://ftp.diku.dk/diku/users/kris/Explicit-PSN.ps.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.