An environment machine for the λμ-calculus

From MaRDI portal
Publication:4236202





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.











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)