Lambda calculus definition

Lambda expressions are composed of

• variables ${\displaystyle v_{1}}$, ${\displaystyle v_{2}}$, ..., ${\displaystyle v_{n}}$, ...
• the abstraction symbols lambda '${\displaystyle \lambda }$' and dot '.'
• parentheses ( )

The set of lambda expressions, ${\displaystyle \Lambda }$, can be defined inductively:

1. If ${\displaystyle x}$ is a variable, then ${\displaystyle x\in \Lambda }$
2. If ${\displaystyle x}$ is a variable and ${\displaystyle M\in \Lambda }$, then ${\displaystyle (\lambda x.M)\in \Lambda }$
3. If ${\displaystyle M,N\in \Lambda }$, then ${\displaystyle (M\ N)\in \Lambda }$

Instances of rule 2 are known as abstractions and instances of rule 3 are known as applications.[1]

To keep the notation of lambda expressions uncluttered, the following conventions are usually applied.

• Outermost parentheses are dropped: ${\displaystyle M\ N}$ instead of ${\displaystyle (M\ N)}$
• Applications are assumed to be left associative: ${\displaystyle M\ N\ P}$ may be written instead of ${\displaystyle ((M\ N)\ P)}$[2]
• The body of an abstraction extends as far right as possible: ${\displaystyle \lambda x.M\ N}$ means ${\displaystyle \lambda x.(M\ N)}$ and not ${\displaystyle (\lambda x.M)\ N}$
• A sequence of abstractions is contracted: ${\displaystyle \lambda x.\lambda y.\lambda z.N}$ is abbreviated as ${\displaystyle \lambda xyz.N}$[3][4]

The abstraction operator, ${\displaystyle \lambda }$, is said to bind its variable wherever it occurs in the body of the abstraction. Variables that fall within the scope of an abstraction are said to be bound. All other variables are called free. For example, in the following expression ${\displaystyle y}$ is a bound variable and ${\displaystyle x}$ is free: ${\displaystyle \lambda y.x\ x\ y}$. Also note that a variable is bound by its "nearest" abstraction. In the following example the single occurrence of ${\displaystyle x}$ in the expression is bound by the second lambda: ${\displaystyle \lambda x.y(\lambda x.z\ x)}$

The set of free variables of a lambda expression, ${\displaystyle M}$, is denoted as ${\displaystyle \operatorname {FV} (M)}$ and is defined by recursion on the structure of the terms, as follows:

1. ${\displaystyle \operatorname {FV} (x)=\{x\}}$, where ${\displaystyle x}$ is a variable
2. ${\displaystyle \operatorname {FV} (\lambda x.M)=\operatorname {FV} (M)\backslash \{x\}}$
3. ${\displaystyle \operatorname {FV} (M\ N)=\operatorname {FV} (M)\cup \operatorname {FV} (N)}$[5]

An expression that contains no free variables is said to be closed. Closed lambda expressions are also known as combinators and are equivalent to terms in combinatory logic.

The meaning of lambda expressions is defined by how expressions can be reduced.[6]

There are three kinds of reduction:

• α-conversion: changing bound variables (alpha);
• β-reduction: applying functions to their arguments (beta);
• η-reduction: which captures a notion of extensionality (eta).

We also speak of the resulting equivalences: two expressions are β-equivalent, if they can be β-converted into the same expression, and α/η-equivalence are defined similarly.

The term redex, short for reducible expression, refers to subterms that can be reduced by one of the reduction rules. For example, ${\displaystyle (\lambda x.M)\ N}$ is a β-redex in expressing the substitution of ${\displaystyle N}$ for ${\displaystyle x}$ in ${\displaystyle M}$; if ${\displaystyle x}$ is not free in ${\displaystyle M}$, ${\displaystyle \lambda x.M\ x}$ is an η-redex. The expression to which a redex reduces is called its reduct; using the previous example, the reducts of these expressions are respectively ${\displaystyle M[x:=N]}$ and ${\displaystyle M}$.

Alpha-conversion, sometimes known as alpha-renaming,[7] allows bound variable names to be changed. For example, alpha-conversion of ${\displaystyle \lambda x.x}$ might yield ${\displaystyle \lambda y.y}$. Terms that differ only by alpha-conversion are called α-equivalent. Frequently in uses of lambda calculus, α-equivalent terms are considered to be equivalent.

The precise rules for alpha-conversion are not completely trivial. First, when alpha-converting an abstraction, the only variable occurrences that are renamed are those that are bound to the same abstraction. For example, an alpha-conversion of ${\displaystyle \lambda x.\lambda x.x}$ could result in ${\displaystyle \lambda y.\lambda x.x}$, but it could not result in ${\displaystyle \lambda y.\lambda x.y}$. The latter has a different meaning from the original.

Second, alpha-conversion is not possible if it would result in a variable getting captured by a different abstraction. For example, if we replace ${\displaystyle x}$ with ${\displaystyle y}$ in ${\displaystyle \lambda x.\lambda y.x}$, we get ${\displaystyle \lambda y.\lambda y.y}$, which is not at all the same.

In programming languages with static scope, alpha-conversion can be used to make name resolution simpler by ensuring that no variable name masks a name in a containing scope (see alpha renaming to make name resolution trivial).

Substitution, written ${\displaystyle E[V:=R]}$, is the process of replacing all free occurrences of the variable ${\displaystyle V}$ in the expression ${\displaystyle E}$ with expression ${\displaystyle R}$. Substitution on terms of the lambda calculus is defined by recursion on the structure of terms, as follows (note: x and y are only variables while M and N are any λ expression).

${\displaystyle {\begin{aligned}x[x:=N]&\equiv N\\y[x:=N]&\equiv y{\text{, if }}x\neq y\end{aligned}}}$

${\displaystyle {\begin{aligned}(M_{1}\ M_{2})[x:=N]&\equiv (M_{1}[x:=N])\ (M_{2}[x:=N])\\(\lambda x.M)[x:=N]&\equiv \lambda x.M\\(\lambda y.M)[x:=N]&\equiv \lambda y.(M[x:=N]){\text{, if }}x\neq y{\text{, provided }}y\notin FV(N)\end{aligned}}}$

To substitute into a lambda abstraction, it is sometimes necessary to α-convert the expression. For example, it is not correct for ${\displaystyle (\lambda x.y)[y:=x]}$ to result in ${\displaystyle (\lambda x.x)}$, because the substituted ${\displaystyle x}$ was supposed to be free but ended up being bound. The correct substitution in this case is ${\displaystyle (\lambda z.x)}$, up to α-equivalence. Notice that substitution is defined uniquely up to α-equivalence.

β-reduction captures the idea of function application. β-reduction is defined in terms of substitution: the β-reduction of ${\displaystyle ((\lambda V.E)\ E')}$ is ${\displaystyle E[V:=E']}$.

For example, assuming some encoding of ${\displaystyle 2,7,\times }$, we have the following β-reduction: ${\displaystyle ((\lambda n.\ n\times 2)\ 7)\rightarrow 7\times 2}$.

η-reduction expresses the idea of extensionality, which in this context is that two functions are the same if and only if they give the same result for all arguments. η-reduction converts between ${\displaystyle \lambda x.(fx)}$ and ${\displaystyle f}$ whenever ${\displaystyle x}$ does not appear free in ${\displaystyle f}$.

The purpose of β-reduction is to calculate a value. A value in lambda calculus is a function. So β-reduction continues until the expression looks like a function abstraction.

A lambda expression that cannot be reduced further, by either β-redex, or η-redex is in normal form. Note that alpha-conversion may convert functions. All normal forms that can be converted into each other by α-conversion are defined to be equal. See the main article on Beta normal form for details.

The execution of a lambda expression proceeds using the following reductions and transformations,

1. α-conversion - ${\displaystyle \operatorname {alpha-conv} (a)\to \operatorname {canonym} [A,P]=\operatorname {canonym} [a[A],P]}$
2. β-reduction - ${\displaystyle \operatorname {beta-redex} [\lambda p.b\ v]=b[p:=v]}$
3. η-reduction - ${\displaystyle x\not \in \operatorname {FV} (f)\to \operatorname {eta-redex} [\lambda x.(f\ x)]=f}$

where,

• canonym is a renaming of a lambda expression to give the expression standard names, based on the position of the name in the expression.
• Substitution Operator, ${\displaystyle b[p:=v]}$ is the substitution of the name ${\displaystyle p}$ by the lambda expression ${\displaystyle v}$ in lambda expression ${\displaystyle b}$.
• Free Variable Set ${\displaystyle \operatorname {FV} (f)}$ is the set of variables that do not belong to a lambda abstraction in ${\displaystyle f}$.

Execution is performing β-reductions and η-reductions on subexpressions in the canonym of a lambda expression until the result is a lambda function (abstraction) in the normal form.

All α-conversions of a λ-expression are considered to be equivalent.

Canonym is a function that takes a lambda expression and renames all names canonically, based on their positions in the expression. This might be implemented as,

${\displaystyle {\begin{aligned}\operatorname {canonym} [L,Q]&=\operatorname {canonym} [L,O,Q]\\\operatorname {canonym} [\lambda p.b,M,Q]&=\lambda \operatorname {name} (Q).\operatorname {canonym} [b,M[p:=Q],Q+N]\\\operatorname {canonym} [X\ Y,x,Q]&=\operatorname {canonym} [X,x,Q+F]\ \operatorname {canonym} [Y,x,E+S]\\\operatorname {canonym} [x,M,Q]&=\operatorname {name} (M[x])\end{aligned}}}$

Where, N is the string "N", F is the string "F", S is the string "S", + is concatenation, and "name" converts a string into a name

Map from one value to another if the value is in the map. O is the empty map.

1. ${\displaystyle O[x]=x}$
2. ${\displaystyle M[x:=y][x]=y}$
3. ${\displaystyle x\neq z\to M[x:=y][z]=M[z]}$

If L is a lambda expression, x is a name, and y is a lambda expression; ${\displaystyle L[x:=y]}$ means substitute x by y in L. The rules are,

1. ${\displaystyle (\lambda p.b)[x:=y]=\lambda p.b[x:=y]}$
2. ${\displaystyle (X\,Y)[x:=y]=X[x:=y]\,Y[x:=y]}$
3. ${\displaystyle z=x\to (z)[x:=y]=y}$
4. ${\displaystyle z\neq x\to (z)[x:=y]=z}$

Note that rule 1 must be modified if it is to be used on non canonically renamed lambda expressions. See Changes to the substitution operator.

The set of free variables of a lambda expression, M, is denoted as FV(M). This is the set of variable names that have instances not bound (used) in a lambda abstraction, within the lambda expression. They are the variable names that may be bound to formal parameter variables from outside the lambda expression.

The set of bound variables of a lambda expression, M, is denoted as BV(M). This is the set of variable names that have instances bound (used) in a lambda abstraction, within the lambda expression.

The rules for the two sets are given below.[5]

${\displaystyle \mathrm {FV} (M)}$ - Free Variable Set	Comment	${\displaystyle \mathrm {BV} (M)}$ - Bound Variable Set	Comment
${\displaystyle \mathrm {FV} (x)=\{x\}}$	where x is a variable	${\displaystyle \mathrm {BV} (x)=\emptyset }$	where x is a variable
${\displaystyle \mathrm {FV} (\lambda x.M)=\mathrm {FV} (M)\setminus \{x\}}$	Free variables of M excluding x	${\displaystyle \mathrm {BV} (\lambda x.M)=\mathrm {BV} (M)\cup \{x\}}$	Bound variables of M plus x.
${\displaystyle \mathrm {FV} (M\ N)=\mathrm {FV} (M)\cup \mathrm {FV} (N)}$	Combine the free variables from the function and the parameter	${\displaystyle \mathrm {BV} (M\ N)=\mathrm {BV} (M)\cup \mathrm {BV} (N)}$	Combine the bound variables from the function and the parameter

Usage;

• The Free Variable Set, FV is used above in the definition of the η-reduction.
• The Bound Variable Set, BV, is used in the rule for β-redex of non canonical lambda expression.

This mathematical definition is structured so that it represents the result, and not the way it gets calculated. However the result may be different between lazy and eager evaluation. This difference is described in the evaluation formulas.

The definitions given here assume that the first definition that matches the lambda expression will be used. This convention is used to make the definition more readable. Otherwise some if conditions would be required to make the definition precise.

Running or evaluating a lambda expression L is,

${\displaystyle \operatorname {eval} [\operatorname {canonym} [L],Q]}$

where Q is a name prefix possibly an empty string and eval is defined by,

${\displaystyle {\begin{aligned}\operatorname {eval} [x\ y]&=\operatorname {eval} [\operatorname {apply} [\operatorname {eval} [x]\ \operatorname {strategy} [y]]]\\\operatorname {apply} [(\lambda x.y)\ z]&=\operatorname {canonym} [\operatorname {beta-redex} [(\lambda x.y)\ z],x]\\\operatorname {apply} [x]&=x{\text{ if x does match the above.}}\\\operatorname {eval} [\lambda x.(f\ x)]&=\operatorname {eval} [\operatorname {eta-redex} [\lambda x.(f\ x)]]\\\operatorname {eval} [L]&=L\\\operatorname {lazy} [X]&=X\\\operatorname {eager} [X]&=\operatorname {eval} [X]\end{aligned}}}$

Then the evaluation strategy may be chosen as either,

${\displaystyle {\begin{aligned}\operatorname {strategy} &=\operatorname {lazy} \\\operatorname {strategy} &=\operatorname {eager} \end{aligned}}}$

The result may be different depending on the strategy used. Eager evaluation will apply all reductions possible, leaving the result in normal form, while lazy evaluation will omit some reductions in parameters, leaving the result in "weak head normal form".

All reductions that can be applied have been applied. This is the result obtained from applying eager evaluation.

${\displaystyle {\begin{aligned}\operatorname {normal} [(\lambda x.y)\ z]&=\operatorname {false} \\\operatorname {normal} [\lambda x.(f\ x)]&=\operatorname {false} \\\operatorname {normal} [x\ y]&=\operatorname {normal} [x]\land \operatorname {normal} [y]\end{aligned}}}$

In all other cases,

${\displaystyle \operatorname {normal} [x]=\operatorname {true} }$

Reductions to the function (the head) have been applied, but not all reductions to the parameter have been applied. This is the result obtained from applying lazy evaluation.

${\displaystyle {\begin{aligned}\operatorname {whnf} [(\lambda x.y)\ z]&=\operatorname {false} \\\operatorname {whnf} [\lambda x.(f\ x)]&=\operatorname {false} \\\operatorname {whnf} [x\ y]&=\operatorname {whnf} [x]\end{aligned}}}$

In all other cases,

${\displaystyle \operatorname {whnf} [x]=\operatorname {true} }$

The lambda abstraction operator, λ, takes a formal parameter variable and a body expression. When evaluated the formal parameter variable is identified with the value of the actual parameter.

Variables in a lambda expression may either be "bound" or "free". Bound variables are variable names that are already attached to formal parameter variables in the expression.

The formal parameter variable is said to bind the variable name wherever it occurs free in the body. Variable (names) that have already been matched to formal parameter variable are said to be bound. All other variables in the expression are called free.

For example, in the following expression y is a bound variable and x is free: ${\displaystyle \lambda y.x\ x\ y}$. Also note that a variable is bound by its "nearest" lambda abstraction. In the following example the single occurrence of x in the expression is bound by the second lambda: ${\displaystyle \lambda x.y\ (\lambda x.z\ x)}$

In the definition of the Substitution Operator the rule,

• ${\displaystyle (\lambda p.b)[x:=y]=\lambda p.b[x:=y]}$

must be replaced with,

1. ${\displaystyle (\lambda x.b)[x:=y]=\lambda x.b}$
2. ${\displaystyle z\neq x\ \to (\lambda z.b)[x:=y]=\lambda z.b[x:=y]}$

This is to stop bound variables with the same name being substituted. This would not have occurred in a canonically renamed lambda expression.

For example the previous rules would have wrongly translated,

${\displaystyle (\lambda x.x\ z)[x:=y]=(\lambda x.y\ z)}$

The new rules block this substitution so that it remains as,

${\displaystyle (\lambda x.x\ z)[x:=y]=(\lambda x.x\ z)}$

The meaning of lambda expressions is defined by how expressions can be transformed or reduced.[6]

There are three kinds of transformation:

• α-conversion: changing bound variables (alpha);
• β-reduction: applying functions to their arguments (beta), calling functions;
• η-reduction: which captures a notion of extensionality (eta).

We also speak of the resulting equivalences: two expressions are β-equivalent, if they can be β-converted into the same expression, and α/η-equivalence are defined similarly.

The term redex, short for reducible expression, refers to subterms that can be reduced by one of the reduction rules.

Alpha-conversion, sometimes known as alpha-renaming,[7] allows bound variable names to be changed. For example, alpha-conversion of ${\displaystyle \lambda x.x}$ might give ${\displaystyle \lambda y.y}$. Terms that differ only by alpha-conversion are called α-equivalent.

In an α-conversion, names may be substituted for new names if the new name is not free in the body, as this would lead to the capture of free variables.

${\displaystyle (y\not \in FV(b)\land a(\lambda x.b)=\lambda y.b[x:=y])\to \operatorname {alpha-con} (a)}$

Note that the substitution will not recurse into the body of lambda expressions with formal parameter ${\displaystyle x}$ because of the change to the substitution operator described above.

See example;

α-conversion	λ-expression	Canonically named	Comment
	${\displaystyle \lambda z.\lambda y.(z\ y)}$	${\displaystyle \lambda \operatorname {P} .\lambda \operatorname {PN} .(\operatorname {P} \operatorname {PN} )}$	Original expressions.
correctly rename y to k, (because k is not used in the body)	${\displaystyle \lambda z.\lambda k.(z\ k)}$	${\displaystyle \lambda \operatorname {P} .\lambda \operatorname {PN} .(\operatorname {P} \operatorname {PN} )}$	No change to canonical renamed expression.
naively rename y to z, (wrong because z free in ${\displaystyle \lambda y.(z\ y)}$)	${\displaystyle \lambda z.\lambda z.(z\ z)}$	${\displaystyle \lambda \operatorname {P} .\lambda \operatorname {PN} .({\color {Red}\operatorname {PN} }\operatorname {PN} )}$	${\displaystyle z}$ is captured.

β-reduction captures the idea of function application (also called a function call), and implements the substitution of the actual parameter expression for the formal parameter variable. β-reduction is defined in terms of substitution.

If no variable names are free in the actual parameter and bound in the body, β-reduction may be performed on the lambda abstraction without canonical renaming.

${\displaystyle (\forall z:z\not \in FV(y)\lor z\not \in BV(b))\to \operatorname {beta-redex} [\lambda x.b\ y]=b[x:=y]}$

Alpha renaming may be used on ${\displaystyle b}$ to rename names that are free in ${\displaystyle y}$ but bound in ${\displaystyle b}$, to meet the pre-condition for this transformation.

See example;

β-reduction	λ-expression	Canonically named	Comment
	${\displaystyle (\lambda x.\lambda y.(\lambda z.(\lambda x.z\ x)(\lambda y.z\ y))(x\ y))}$	${\displaystyle (\lambda \operatorname {P} .\lambda \operatorname {PN} .(\lambda \operatorname {PNF} .(\lambda \operatorname {PNFNF} .\operatorname {PNF} \operatorname {PNFNF} )(\lambda \operatorname {PNFNS} .\operatorname {PNF} \operatorname {PNFNS} ))(\operatorname {P} \operatorname {PN} ))}$	Original expressions.
Naive beta 1,	${\displaystyle (\lambda x.\lambda y.((\lambda x.(x\ y)x)(\lambda y.(x\ y)y)))}$	Canonical ${\displaystyle (\lambda \operatorname {P} .\lambda \operatorname {PN} .((\lambda \operatorname {PNF} .({\color {Blue}\operatorname {P} }\operatorname {PN} )\operatorname {PNF} )(\lambda \operatorname {PNS} .(\operatorname {P} {\color {Blue}\operatorname {PN} })\operatorname {PNS} )))}$ Natural ${\displaystyle (\lambda \operatorname {P} .\lambda \operatorname {PN} .((\lambda \operatorname {PNF} .({\color {Red}\operatorname {PNF} }\operatorname {PN} )\operatorname {PNF} )(\lambda \operatorname {PNS} .(\operatorname {P} {\color {Red}\operatorname {PNS} )}\operatorname {PNS} )))}$	x (P) and y (PN) have been captured in the substitution.
Alpha rename inner, x → a, y → b	${\displaystyle (\lambda x.\lambda y.(\lambda z.(\lambda x.z\ a)(\lambda b.z\ b))(x\ y))}$	${\displaystyle (\lambda \operatorname {P} .\lambda \operatorname {PN} .(\lambda \operatorname {PNF} .(\lambda \operatorname {PNFNF} .\operatorname {PNF} \operatorname {PNFNF} )(\lambda \operatorname {PNFNS} .\operatorname {PNF} \operatorname {PNFNS} ))(\operatorname {P} \operatorname {PN} ))}$
Beta 2,	${\displaystyle (\lambda x.\lambda y.((\lambda a.(x\ y)a)(\lambda b.(x\ y)b)))}$	Canonical ${\displaystyle (\lambda \operatorname {P} .\lambda \operatorname {PN} .((\lambda \operatorname {PNF} .(\operatorname {P} \operatorname {PN} )\operatorname {PNF} )(\lambda \operatorname {PNS} .(\operatorname {P} \operatorname {PN} )\operatorname {PNS} )))}$ Natural ${\displaystyle (\lambda \operatorname {P} .\lambda \operatorname {PN} .((\lambda \operatorname {PNF} .(\operatorname {P} \operatorname {PN} )\operatorname {PNF} )(\lambda \operatorname {PNS} .(\operatorname {P} \operatorname {PN} )\operatorname {PNS} )))}$	x and y not captured.

${\displaystyle {\begin{array}{r}((\lambda x.z\ x)(\lambda y.z\ y))[z:=(x\ y)]\\((\lambda a.z\ a)(\lambda b.z\ b))[z:=(x\ y)]\end{array}}}$

In this example,

1. In the β-redex,
   1. The free variables are, ${\displaystyle \operatorname {FV} (x\ y)=\{x,y\}}$
   2. The bound variables are, ${\displaystyle \operatorname {BV} ((\lambda x.z\ x)(\lambda y.z\ y))=\{x,y\}}$
2. The naive β-redex changed the meaning of the expression because x and y from the actual parameter became captured when the expressions were substituted in the inner abstractions.
3. The alpha renaming removed the problem by changing the names of x and y in the inner abstraction so that they are distinct from the names of x and y in the actual parameter.
   1. The free variables are, ${\displaystyle \operatorname {FV} (x\ y)=\{x,y\}}$
   2. The bound variables are, ${\displaystyle \operatorname {BV} ((\lambda a.z\ a)(\lambda b.z\ b))=\{a,b\}}$
4. The β-redex then proceeded with the intended meaning.

η-reduction expresses the idea of extensionality, which in this context is that two functions are the same if and only if they give the same result for all arguments.

η-reduction may be used without change on lambda expressions that are not canonically renamed.

${\displaystyle x\not \in \mathrm {FV} (f)\to {\text{η-redex}}[\lambda x.(fx)]=f}$

The problem with using an η-redex when f has free variables is shown in this example,

Reduction	Lambda expression	β-reduction
	${\displaystyle (\lambda x.(\lambda y.y\,x)\,x)\,a}$	${\displaystyle \lambda a.a\,a}$
Naive η-reduction	${\displaystyle (\lambda y.y\,x)\,a}$	${\displaystyle \lambda a.a\,x}$

This improper use of η-reduction changes the meaning by leaving x in ${\displaystyle \lambda y.y\,x}$ unsubstituted.