Lambda-mu calculus

In mathematical logic and computer science, the lambda-mu calculus is an extension of the lambda calculus introduced by Michel Parigot.^[1] It introduces two new operators: the μ operator (which is completely different both from the μ operator found in computability theory and from the μ operator of modal μ-calculus) and the bracket operator. Proof-theoretically, it provides a well-behaved formulation of classical natural deduction.

One of the main goals of this extended calculus is to be able to describe expressions corresponding to theorems in classical logic. According to the Curry–Howard isomorphism, lambda calculus on its own can express theorems in intuitionistic logic only, and several classical logical theorems can't be written at all. However with these new operators one is able to write terms that have the type of, for example, Peirce's law.

The μ operator corresponds to Felleisen's undelimited control operator C and bracket corresponds to calling a captured continuation.^[2]

Formal definition

The three forms of expressions in lambda calculus are as follows:

1. A variable x, where x is any identifier.
2. An abstraction λx. M, where x is any identifier and M is any lambda expression.
3. An application (M N), where M and N are any lambda expressions.

In addition to the traditional λ-variables, the lambda-mu calculus includes a distinct set of μ-variables, which can be understood as continuation variables. The set of terms is divided into unnamed (all traditional lambda expressions are of this kind) and named terms. The terms that are added by the lambda-mu calculus are of the form:

1. [α]M is a named term, where α is a μ-variable and M is an unnamed term.
2. (μ α. t) is an unnamed term, where α is a μ-variable and t is a named term.

Reduction

The basic reduction rules used in the lambda-mu calculus are the following:

beta reduction

${\displaystyle (\lambda x.M)N\to M[N/x]}$ 

structural reduction

${\displaystyle (\mu \alpha .t)M\to \mu \alpha .t\left[[\alpha ](NM)/[\alpha ]N\right]}$ , where the substitutions are to be made for all subterms of ${\displaystyle t}$  of the form ${\displaystyle [\alpha ]N}$ .

renaming

${\displaystyle [\alpha ]\mu \beta .t\to t[\alpha /\beta ]}$ 

μη-reduction

${\displaystyle \mu \alpha .[\alpha ]M\to M}$ , if α does not occur freely in M

These rules cause the calculus to be confluent.

Variations

Call-by-value lambda-mu calculus

To obtain call-by-value semantics, one must refine the beta reduction rule and add another form of structural reduction:^[3]

call-by-value beta reduction

${\displaystyle (\lambda x.M)V\to M[V/x]}$ , where V is a value

right structural reduction

${\displaystyle V(\mu \alpha .t)\to \mu \alpha .t\left[[\alpha ](VN)/[\alpha ]N\right]}$ , where V is a value

This addition corresponds to the addition of an additional evaluation context former when moving from call-by-name to call-by-value evaluation.

De Groote's unstratified syntax

For a closer correspondence with conventional formalizations of control operators, the distinction between named and unnamed terms can be abolished, meaning that [α]M is of the same sort as other lambda-expressions and the body of μ-abstraction can also be any expression.^[2] Another variant in this vein is the Λμ-calculus.^[4]

Symmetric lambda-mu calculus

One can consider a structural reduction rule symmetric to the original one:^[1]

${\displaystyle M(\mu \alpha .t)\to \mu \alpha .t\left[[\alpha ](MN)/[\alpha ]N\right]}$ 

This, however, breaks confluence and the correspondence to control operators.

See also

• Classical pure type systems for typed generalizations of lambda calculi with control

References

1. Michel Parigot (1992). λμ-Calculus: An algorithmic interpretation of classical natural deduction. Lecture Notes in Computer Science. Vol. 624. pp. 190–201. doi:10.1007/BFb0013061. ISBN 3-540-55727-X.
2. de Groote, Philippe (1994). "On the relation between the λμ-calculus and the syntactic theory of sequential control". In Pfenning, Frank (ed.). Logic Programming and Automated Reasoning, 5th International Conference, LPAR'94, Kiev, Ukraine, July 16–22, 1994, Proceedings. Lecture Notes in Computer Science. Vol. 822. Springer. pp. 31–43. doi:10.1007/3-540-58216-9_27. ISBN 978-3-540-58216-8.
3. Ong, C.-H. L.; Stewart, C. A. (1997-01-01). "A Curry-Howard foundation for functional computation with control". Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '97. New York, NY, USA: Association for Computing Machinery. pp. 215–227. doi:10.1145/263699.263722. ISBN 978-0-89791-853-4.
4. Saurin, Alexis (2005). "Separation with Streams in the λμ-calculus". 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26–29 June 2005, Chicago, IL, USA, Proceedings. IEEE Computer Society. pp. 356–365. doi:10.1109/LICS.2005.48.

External links

• Lambda-mu relevant discussion on Lambda the Ultimate.