Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-26T13:27:20.228Z Has data issue: false hasContentIssue false
  • English
  • Français

Storage operators and directed lambda-calculus

Published online by Cambridge University Press:  12 March 2014

René David  and
Karim Nour
René David
Affiliation:
LAMA—Equipe de Logique, Université de Savoie, Campus Scientifique, 73376 Le Bourget du Lac Cédex, France, E-mail: [email protected]
Karim Nour
Affiliation:
LAMA—Equipe de Logique, Université de Savoie, Campus Scientifique, 73376 Le Bourget du Lac Cédex, France, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Storage operators have been introduced by J. L. Krivine in [5] they are closed λ-terms which, for a data type, allow one to simulate a “call by value” while using the “call by name” strategy. In this paper, we introduce the directed λ-calculus and show that it has the usual properties of the ordinary λ-calculus. With this calculus we get an equivalent—and simple—definition of the storage operators that allows to show some of their properties:

• the stability of the set of storage operators under the β-equivalence (Theorem 5.1.1);

• the undecidability (and semidecidability) of the problem “is a closed λ-term t a storage operator for a finite set of closed normal λ-terms?” (Theorems 5.2.2 and 5.2.3);

• the existence of storage operators for every finite set of closed normal λ-terms (Theorem 5.4.3);

• the computation time of the “storage operation” (Theorem 5.5.2).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 60 , Issue 4 , December 1995 , pp. 1054 - 1086
Copyright
Copyright © Association for Symbolic Logic 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Abadi, M., Cardelli, L., Curien, P. L., and Levy, J. L., Explicit substitutions, Technical report 1176, INRIA, 1990, Journal of Functional Programming (to appear).Google Scholar
[2]Barendregt, H., The lambda calculus: its syntax and semantics, Studies in Logic and the Foundations of Mathematics, vol. 103, North Holland, Amsterdam, 1984.Google Scholar
[3]Böhm, C., Ciancaglini, M. Dezani, Peretti, A. and Della Rocca, S. Ronchi, A discriminator algorithm inside λ-β-calculus, Theoretical Computer Science, vol. 8, (1979), pp. 271–291.CrossRefGoogle Scholar
[4]Curien, P. L., The λρ-calculi: an abstract framework for closures, Technical report, LIENS—École Normale Supérieure, Paris, 1988.Google Scholar
[5]Krivine, J. L., Lambda calcul, évaluation paresseuse et mise en mémoire, RAIRO Informatique Théorique et Applications, vol. 25 (1991), pp. 67–84.CrossRefGoogle Scholar
[6]Krivine, J. L., Lambda calcul, types et modèle, Masson, Paris, 1990.Google Scholar
[7]Krivine, J. L., Opérateurs de mise en mémoire et traduction de Gödel, Archive for Mathematical Logic, vol. 30 (1990), pp. 241–267.CrossRefGoogle Scholar
[8]Nour, K., Opérateurs de mise en mémoire en lambda-calcul pur et typé, Thèse de doctorat, Université de Savoie, Chambéry, 1993.Google Scholar
[9]Nour, K., Strong storage operators and data types, Archive for Mathematical Logic (to appear).Google Scholar
[10]Nour, K., Opérateurs de mise en mémoire et types ∀-positifs, RAIRO Informatique Théorique et Applications, (submitted).Google Scholar
[11]Nour, K., Storage operators and ∀-positive types in system JJR, Preprint, LAMA Equipe de Logique, Université de Savoie, Chambéry, 1993.Google Scholar
[12]Nour, K., Opérateurs propres de mise en mémoire, Comptes Rendus de l'Académie des Sciences. Série I: Mathématiques, vol. 317 (1993), pp. 1–6.Google Scholar
[13]Nour, K., Preuve syntaxique d'un théorème de J. L. Krivine sur les opérateurs de mise en mémoire, Comptes Rendus de l'Académie des Sciences. Série I: Mathématiques, vol. 318 (1994), pp. 201–204.Google Scholar
[14]Scott, D. S., A system of functional abstraction, Unpublished manuscript, 1963.Google Scholar