User:Thepigdog/Lambda Calculus - standard definition

The standard definition of Lambda Calculus uses some definitions which I would prefer to consider as theorems, which can be proved based on the Canonical naming definition.

The canonical naming definition deals with the problem of variable identity by constructing a unique name for each variable based on the position of the lambda abstraction for the variable name in the expression.

This definition introduces the rules used in the standard definition and relates explains them in terms of the canonical renaming definition.

Free and bound variables

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: $\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: $\lambda x.y\ (\lambda x.z\ x)$

Changes to the substitution operator

In the definition of the Substitution Operator the rule,

$(\lambda p.b)[x:=y]=\lambda p.b[x:=y]$

must be replaced with,

$(\lambda x.b)[x:=y]=\lambda x.b$
$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,

(\lambda x.x\ z)[x:=y]=(\lambda x.y\ z)

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

(\lambda x.x\ z)[x:=y]=(\lambda x.x\ z)

Transformation

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

There are three kinds of transformation:

α-conversion: changing bound variables (alpha);
β-reduction: applying functions to their arguments (beta), calling functions;
η-conversion: 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

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

In an alpha 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.

(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 $x$ because of the change to the substitution operator described above.

See example;

Alpha conversion	Lambda Expression	Canonically named	Comment
	$\lambda z.\lambda y.(z\ y)$	$\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)	$\lambda z.\lambda k.(z\ k)$	$\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 $\lambda y.(z\ y)$ )	$\lambda z.\lambda z.(z\ z)$	$\lambda \operatorname {P} .\lambda \operatorname {PN} .({\color {Red}\operatorname {PN} }\operatorname {PN} )$	$z$ is captured.

Beta reduction (capture avoiding)

Beta-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. Beta-reduction is defined in terms of substitution.

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

(\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 $b$ to rename names that are free in $y$ but bound in $b$ , to meet the pre-condition for this transformation.

See example;

Beta Reduction

Lambda Expression

Canonically named

Comment

(\lambda x.\lambda y.(\lambda z.(\lambda x.z\ x)(\lambda y.z\ y))(x\ y))

(\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,

(\lambda x.\lambda y.((\lambda x.(x\ y)x)(\lambda y.(x\ y)y)))

Canonical	$(\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	$(\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

(\lambda x.\lambda y.(\lambda z.(\lambda x.z\ a)(\lambda b.z\ b))(x\ y))

(\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,

(\lambda x.\lambda y.((\lambda a.(x\ y)a)(\lambda b.(x\ y)b)))

Canonical	$(\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	$(\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.

$((\lambda x.z\ x)(\lambda y.z\ y))[z:=(x\ y)]$
$((\lambda a.z\ a)(\lambda b.z\ b))[z:=(x\ y)]$

In this example,

In the beta-redex,
1. The free variables are, $FV(x\ y)=\{x,y\}$
2. The bound variables are, $BV((\lambda x.z\ x)(\lambda y.z\ y))=\{x,y\}$
The naive beta-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.
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, $\operatorname {FV} (x\ y)=\{x,y\}$
2. The bound variables are, $\operatorname {BV} ((\lambda a.z\ a)(\lambda b.z\ b))=\{a,b\}$
The beta-redex then proceeded with the intended meaning.

Eta reduction

Eta-conversion 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.

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

x\not \in \operatorname {FV} (f)\to \operatorname {eta-redex} [\lambda x.(fx)]=f

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

Reduction	Lambda expression	Beta-reduction
	$(\lambda x.(\lambda y.y\ x)\ x)\ a$	$\lambda a.a\ a$
Naive eta-reduction	$(\lambda y.y\ x)\ a$	$\lambda a.a\ x$

This improper use of eta-reduction changes the meaning by leaving $x$ in $\lambda y.y\ x$ unsubstituted.

Normalization

The purpose of beta-reduction is to calculate a value. A value in Lambda Calculus is a function. So beta-reduction continues until the expression looks like a function abstraction.

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

Normal Form Type	Definition.
Normal Form	No beta or eta reductions are possible.
Head Normal Form	In the form of a lambda abstraction whose body is not reducible.
Weak Head Normal Form	In the form of a lambda abstraction.

Links

Lambda Calculus

References

^ de Queiroz, Ruy J.G.B. "A Proof-Theoretic Account of Programming and the Role of Reduction Rules." Dialectica 42(4), pages 265-282, 1988.
^ Turbak, Franklyn; Gifford, David (2008), Design concepts in programming languages, MIT press, p. 251, ISBN 978-0-262-20175-9

[1] Queiroz, Ruy J.G.B. "A Proof-Theoretic Account of Programming and the Role of Reduction Rules." Dialectica 42(4), pages 265-282, 1988.

[2] Turbak, Franklyn; Gifford, David (2008), Design concepts in programming languages, MIT press, p. 251, ISBN 978-0-262-20175-9

[1]

[2]