In mathematical logic, the lambda calculus (also written as λ-calculus) is a formal system for expressing computation based on function abstraction and application using variable binding and substitution. Untyped lambda calculus, the topic of this article, is a universal machine, i.e. a model of computation that can be used to simulate any Turing machine (and vice versa). It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. In 1936, Church found a formulation which was logically consistent, and documented it in 1940.
Definition
The lambda calculus consists of a language of lambda terms, which are defined by a formal syntax, and a set of transformation rules for manipulating those terms. In BNF, the syntax is e ::= x ∣ λ x . e ∣ e e , {\displaystyle e::=x\mid \lambda x{\text{.}}e\mid e\,e,} where variables x , y , z {\displaystyle x,y,z} range over an infinite set of names. Terms M , N , t , s , e , f {\displaystyle M,N,t,s,e,f} range over all lambda terms. This corresponds to the following inductive definition:
A variable x {\displaystyle x} is a valid lambda term. An abstraction is a lambda term ( λ x . t ) {\displaystyle (\lambda x{\text{.}}t)} where t {\displaystyle t} is a lambda term, referred to as the abstraction's body, and x {\displaystyle x} is the abstraction's parameter variable, An application is a lambda term ( t s ) {\displaystyle (t\,s)} where t {\displaystyle t} and s {\displaystyle s} are lambda terms. A lambda term is syntactically valid if it can be obtained by repeated application of these three rules. For convenience, parentheses can often be omitted when writing a lambda term—see Lambda calculus definition § Notation for details. Within lambda terms, any occurrence of a variable that is not a parameter of some enclosing λ {\displaystyle \lambda } is said to be free. Any free occurrence of x {\displaystyle x} in a term M {\displaystyle M} is bound in λ x . M {\displaystyle \lambda x{\text{.}}M} . Any free occurrence of any other variable within M {\displaystyle M} remains free in λ x . M {\displaystyle \lambda x{\text{.}}M} . For example, in the term x y {\displaystyle x\,y} , both x {\displaystyle x} and y {\displaystyle y} occur free. In ( λ x . x y ) {\displaystyle (\lambda x{\text{.}}x\,y)} , y {\displaystyle y} is free, but x {\displaystyle x} in the body (i.e. after the dot) is not free, and is said to be bound (to the parameter). While y {\displaystyle y} is free in ( λ x . x y ) {\displaystyle (\lambda x{\text{.}}x\,y)} , it is bound in ( λ y . λ x . x y ) {\displaystyle (\lambda y{\text{.}}\lambda x{\text{.}}x\,y)} . There are two occurrences of x {\displaystyle x} in ( λ y . ( λ x . x y ) x ) {\displaystyle (\lambda y{\text{.}}(\lambda x{\text{.}}x\,y)\,x)} – one is bound, and the other is free.
FV ( M ) {\displaystyle \operatorname {FV} (M)} is the set of free variables of M {\displaystyle M} , i.e. such variables that occur free in M {\displaystyle M} at least once. It can be defined inductively as follows:
FV ( x ) = { x } {\displaystyle \operatorname {FV} (x)=\{x\}}
FV ( M 1 M 2 ) = FV ( M 1 ) ∪ FV ( M 2 ) {\displaystyle \operatorname {FV} (M_{1}M_{2})=\operatorname {FV} (M_{1})\cup \operatorname {FV} (M_{2})}
FV ( λ x . M ) = FV ( M ) ∖ { x } {\displaystyle \operatorname {FV} (\lambda x{\text{.}}M)=\operatorname {FV} (M)\backslash \{x\}}
… excerpt ends here. Continue reading the full article.
