Lambda-mu calculus

Short description: 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, for example, the type of 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:

1. A variable x.
2. An abstraction λx. M, where x is any variable 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

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

structural reduction

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

renaming

$[\alpha ]\mu \beta .t\to t[\alpha /\beta ]$

μη-reduction

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

These rules cause the calculus to be confluent.

Typed lambda-mu calculus

The lambda-mu calculus can be typed. The typed lambda-mu calculus is to classical propositional logic as the simply typed lambda calculus is to intuitionistic propositional logic.

Typed lambda-mu calculus can be presented in sequent calculus:$$\begin{array}{rl}\mathrm{\Gamma },x:\tau & ⊢x:\tau \\ \\ \frac{\mathrm{\Gamma },x:\sigma ⊢M:\tau }{\mathrm{\Gamma }⊢(\lambda x:\sigma .M):\sigma \to \tau }& \frac{\mathrm{\Gamma },⊢M:\sigma \to \tau \mathrm{\Gamma }⊢N:\sigma }{\mathrm{\Gamma }⊢(MN):\tau }\\ \\ \frac{\mathrm{\Gamma },\alpha :\mathrm{\neg }\sigma ⊢M:\mathrm{\perp }}{\mathrm{\Gamma }⊢(\mu \alpha :\mathrm{\neg }\sigma .M):\sigma }& \frac{\mathrm{\Gamma },\alpha :\mathrm{\neg }\sigma ⊢M:\sigma }{\mathrm{\Gamma },\alpha :\mathrm{\neg }\sigma ⊢([\alpha ]M):\mathrm{\perp }}\end{array}$$The first 3 rules are the same as simply typed lambda calculus. The next 2 are new to the lambda-mu calculus.

Curry–Howard correspondence

Simply typed lambda calculus, by the Curry–Howard correspondence, corresponds to purely functional programs that can only redirect their inputs.

A sequent $\mathrm{\Gamma }⊢t:\tau$ states that, within a program context $\mathrm{\Gamma }$, one can construct an object $t$ of type $\tau$.

The rule $\mathrm{\Gamma },x:\tau ⊢x:\tau$ states that, within a context that includes some $x:\tau$, one can construct an object $x$ with type $\tau$. This is obvious, by simply taking that same $x:\tau$.

The lambda-introduction rule $\frac{\mathrm{\Gamma },x:\sigma ⊢M:\tau }{\mathrm{\Gamma }⊢(\lambda x:\sigma .M):\sigma \to \tau }$ states that, if one can construct $M:\tau$ within a context of $\mathrm{\Gamma },x:\tau$, then one can construct $(\lambda x:\sigma .M):\sigma \to \tau$ within a context of $\mathrm{\Gamma }$. This object $(\lambda x:\sigma .M)$ is a function-object defined within the context of $\mathrm{\Gamma }$. It takes an object $x:\sigma$ as input, and internally reproduces the context of $\mathrm{\Gamma },x:\tau$, in which one then constructs $M:\tau$. This is a form of closure.

The lambda-reduction rule $\frac{\mathrm{\Gamma },⊢M:\sigma \to \tau \mathrm{\Gamma }⊢N:\sigma }{\mathrm{\Gamma }⊢(MN):\tau }$ is a reverse of the previous rule.

The typed lambda-mu calculus is similar to the simply typed lambda calculus, but it allows redirecing both the inputs and the outputs. The redirection of input is by lambda abstraction, or closure. The redirection of output is by mu abstraction, or call/cc, jumps, or control operators.

The negation symbol $\mathrm{\neg }$ denotes duality. Whereas $x:\sigma$ in the program context denotes an input from which an object with type $\sigma$ appears, $\alpha :\mathrm{\neg }\sigma$ denotes an output for an object with type $\sigma$ goes to.

$M:\mathrm{\perp }$ denotes a computational process that does not return any value, because its value would be returned to an output in context.

The address abstraction rule $\frac{\mathrm{\Gamma },\alpha :\mathrm{\neg }\sigma ⊢M:\mathrm{\perp }}{\mathrm{\Gamma }⊢(\mu \alpha :\mathrm{\neg }\sigma .M):\sigma }$ closes an output from context. This corresponds to catch in call/cc.

The address application rule $\frac{\mathrm{\Gamma },\alpha :\mathrm{\neg }\sigma ⊢M:\sigma }{\mathrm{\Gamma },\alpha :\mathrm{\neg }\sigma ⊢([\alpha ]M):\mathrm{\perp }}$ redirects the output of a process $M:\sigma$ to the output $\alpha$ in context. This corresponds to throw in call/cc.

The $\mu$ is a channel device. The address $\alpha :\mathrm{\neg }p$ is a channel that values of type $p$ can be transmitted along, and $[\alpha ]M$ represents transmittal of $M$ to $\alpha$, provided that $M$ is of type $p$.

Examples

Peirce's law $((p\to q)\to p)\to p$ is the type of the following term:$$\lambda x^{(p\to q)\to p}.\mu {\alpha }^{\mathrm{\neg }p}.[\alpha ]x(\lambda y^p.\mu {\beta }^{\mathrm{\neg }q}.[\alpha ]y)$$where we write $x^{\tau }$ for $x:\tau$, in order to save space.

Intuitively, one can understand this construction as follows. The program opens an input context $x:(p\to q)\to p$, and an output context $\alpha :\mathrm{\neg }p$. One way to satisfy the output requirement of $\alpha :\mathrm{\neg }p$ is to construct something of type $p\to q$, and give it to $x$. That something is $\lambda y^p.\mu {\beta }^{\mathrm{\neg }q}.[\alpha ]y:p\to q$. If $x$ takes this object without trying to use it, then it will return an object of type $p$, which can then be given to $\alpha$. Alternatively, $x$ might attempt to use it by providing it with an object $y:p$, which can then be given to $\alpha$ without ever replying an object of type $q$ to $x$.

The Łukasiewicz axiom is the type of the following term:$$\lambda x^{(p\to q)\to r}\lambda y^{r\to p}.\lambda z^s.\mu {\alpha }^{\mathrm{\neg }p}.[\alpha ]y(\mu {\beta }^{\mathrm{\neg }r}.[\beta ]x(\lambda u^p.\mu {\gamma }^{\mathrm{\neg }q}.[\alpha ]u))$$The double-negation translation corresponds to continuation-passing style. That is, the double-negation translation turns every formula provable in classical propositional logic into a provable formula in intuitionistic propositional logic. This corresponds to converting a program with catch/throw into a purely functional program that uses continuation-passing.

For example, the double-negation translation of Peirce's law $((\mathrm{\neg }\mathrm{\neg }p\to \mathrm{\neg }\mathrm{\neg }q)\to \mathrm{\neg }\mathrm{\neg }p)\to \mathrm{\neg }\mathrm{\neg }p$ is the type of the following term:$$\lambda x^{(\mathrm{\neg }\mathrm{\neg }p\to \mathrm{\neg }\mathrm{\neg }q)\to \mathrm{\neg }\mathrm{\neg }p}.\lambda {\alpha }^{\mathrm{\neg }p}x(\lambda y^{\mathrm{\neg }\mathrm{\neg }p}.\lambda {\beta }^{\mathrm{\neg }q}.y\alpha )\alpha$$Compare these two, in parallel:$$\begin{array}{rlrlrl}& \lambda x^{(p\to q)\to p}.& \mu {\alpha }^{\mathrm{\neg }p}.[\alpha ]& x(\lambda y^p.& \mu {\beta }^{\mathrm{\neg }q}.[\alpha ]& y)\\ & \lambda x^{(\mathrm{\neg }\mathrm{\neg }p\to \mathrm{\neg }\mathrm{\neg }q)\to \mathrm{\neg }\mathrm{\neg }p}.& \lambda {\alpha }^{\mathrm{\neg }p}.& x(\lambda y^{\mathrm{\neg }\mathrm{\neg }p}.& \lambda {\beta }^{\mathrm{\neg }q}.y\alpha )\alpha \end{array}$$The "jump to a different output" control behavior, as defined by $\mu \alpha \cdots [\alpha ]$, is translated into a pure lambda expression $\lambda \alpha \cdots \alpha$. Instead of allowing a jump to the address $\alpha :\mathrm{\neg }p$, one encodes the entire "the rest of the computation after the jumping to $\alpha :\mathrm{\neg }p$" as a single object, called the continuation object. This continuation object can then be called for as many times as one wants, as long as that continuation object remains in context.

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:

call-by-value beta reduction

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

right structural reduction

$V(\mu \alpha .t)\to \mu \alpha .t[[\alpha ](VN)/[\alpha ]N]$, 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:

$M(\mu \alpha .t)\to \mu \alpha .t[[\alpha ](MN)/[\alpha ]N]$

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

See also

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

External links

• Lambda-mu relevant discussion on Lambda the Ultimate.