An environment machine for the λμ-calculus
The goal of this paper is to demonstrate how Parigot's \(\lambda\mu\)-calculus [\textit{M. Parigot}, Lect. Notes Comput. Sci. 624, 190-201 (1992)] may act as a correct foundation for functional programming enriched with control operators. The \(\lambda\mu\)-calculus is an extension of the \(\lambda\)-calculus that provides classical logic with an algorithmic interpretation. The extension is twofold: on the one hand, new syntactic constructs (\(\mu\)-abstraction and naming) are given in order to encode classical proofs; on the other hand, the calculus is supplied with new notions of reduction in order to give algorithmic content to the double-negation rule of classical logic. Since Griffin's pioneering work [\textit{T. G. Griffin}, ``A formulae-as-types notion of control, in: Conf. Rec. 17th Ann. ACM Symp. Principles of Programming Languages, 47-58 (1990)], based on Felleisen's theory [\textit{M. Felleisen, D. P. Friedman, E. Kohlbecker} and \textit{B. Duba}, Theor. Comput. Sci. 52, 205-237 (1987; Zbl 0643.03011); \textit{M. Felleisen} and \textit{R. Hieb}, ibid. 103, 235-271 (1992; Zbl 0764.68094)], it is known how the notion of control in functional programming is related to classical logic through a correspondence akin to the Curry-Howard isomorphism. This analogy, however, is not sufficient to accept the \(\lambda\mu\)-calculus as a foundation for the notion of control. Indeed, most of the control operators existing in functional programming have been introduced for pragmatic reasons related to the way the functional programs are actually interpreted. Therefore, we must also justify the \(\lambda\mu\)-calculus on such a pragmatic basis before accepting it as an appropriate foundation. This is what we achieve in this paper by developing an environment machine for the typed \(\lambda\mu\)-calculus.
- A notation for lambda terms. A generalization of environments
- Classical natural deduction for S4 modal logic
- The \(\lambda \mu^{\mathbf{T}}\)-calculus
- Normalization proofs for the un-typed \(\mu\mu^\prime\)-calculus
- The differential \(\lambda \mu\)-calculus
- The next 700 Krivine machines
- A proof-theoretic foundation of abortive continuations
- A third-order representation of the -calculus
- A computational interpretation of the -calculus
- Classical logic, continuation semantics and abstract machines
- Böhm theorem and Böhm trees for the \(\varLambda \mu\)-calculus
- An estimation for the lengths of reduction sequences of the -calculus
- Programming and Proving with Classical Types
- Normalization in the simply typed -calculus
- A Logical Foundation for Environment Classifiers
- An abstract framework for environment machines
- A syntactic correspondence between context-sensitive calculi and abstract machines
This page was built for publication: An environment machine for the λμ-calculus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4236202)