Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T03:09:48.247Z Has data issue: false hasContentIssue false

Storage operators and directed lambda-calculus

Published online by Cambridge University Press:  12 March 2014

René David
Affiliation:
LAMA—Equipe de Logique, Université de Savoie, Campus Scientifique, 73376 Le Bourget du Lac Cédex, France, E-mail: david@univ-savoie.fr
Karim Nour
Affiliation:
LAMA—Equipe de Logique, Université de Savoie, Campus Scientifique, 73376 Le Bourget du Lac Cédex, France, E-mail: nour@univ-savoie.fr

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).

Information

Type
Research Article
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.)

Article purchase

Temporarily unavailable