Extension of lambda calculus
In mathematical logic and computer science, the lambda-mu calculus is an extension of the lambda calculus introduced by Michel Parigot. 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.
Formal definition.
The three forms of expressions in lambda calculus are as follows:
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:
Reduction.
The basic reduction rules used in the lambda-mu calculus are the following:
 formula_1
 formula_2, where the substitutions are to be made for all subterms of formula_3 of the form formula_4.
 formula_5
 formula_6, 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:
 formula_7, where "V" is a value
 formula_8, 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. Another variant in this vein is the Λμ-calculus.
Symmetric lambda-mu calculus.
One can consider a structural reduction rule symmetric to the original one:
formula_9
This, however, breaks confluence and the correspondence to control operators.
References.
 ;templatestyles src="Reflist/styles.css" / ;