On Storage Operators

From MaRDI portal



Abstract: In 1990 Krivine introduced the notion of storage operators. They are lambda-terms which simulate call-by-value in the call-by-name strategy. Krivine has shown that there is a very simple type in the AF2 type system for storage operators using G"odel translation from classical to intuitionistic logic. Parigot and Krivine have shown that storage operators play an important tool in classical logic. In this paper, we present a synthesis of various results on this subject.


\(\lambda\)-calculus as such is not a computational model. A reduction strategy is needed. In this paper, we consider \(\lambda\)-calculus with left reduction. This strategy has many advantages: it always terminates when applied to a normalizable \(\lambda\)-term and it seems more economic since we compute a \(\lambda\)-term only when we need it. But the major drawback of this strategy is that a function must compute its argument every time it uses it. This is the reason why this strategy is not really used. In 1990, \textit{J. L. Krivine} [Arch. Math. Log. 30, No. 4, 241-267 (1990; Zbl 0712.03009)] introduced the notion of storage operators in order to avoid this problem and to simulate call-by-value when necessary. This paper studies some properties of storage operators in pure and typed \(\lambda\)-calculus. We present in particular the results of Krivine, Parigot, and the author. For the entire collection see [Zbl 0899.00026].











This page was built for publication: On Storage Operators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247307)