The λ calculus (lambda calculus) is a formal mathematical system
devised by Alonzo Church to investigate
functions, function application and recursion.
It has influenced many programming languages but
none more so than the functional programming languages.
Lisp
The λ calculus (lambda calculus) is a formal mathematical system
devised by Alonzo Church to investigate
functions, function application and recursion.
It has influenced many programming languages but
none more so than the functional programming languages.
Lisp was the first of these although only the "pure" Lisp sublanguage
can be called a true functional language.
Haskell, Miranda and ML are more recent examples.
The syntax of the λ calculus is short and simple. There are clauses for variable identifiers, function abstraction, function application and subexpressions. This simplicity provides great power, an example of `less is more'.
A function abstraction is an expression for a function.
The identifier is the name of the parameter; it is said to be bound.
An unbound identifier is free.
The function itself has no name.
Application is left associative:
It is convenient, but not essential, to add an option for constants.
The clause for constants can be omitted because constants can be defined with what is left but this is inconvenient and does not aid our purpose. (But see [ints], [bool] and [list] if interested.) The constants certainly include true, false, integers, some functions such as plus, minus, and a conditional function (if). Just what the set of constants contains is not crucial; it is a parameter of the λ calculus rather than a central part of it, and the set can be varied from application to application.
The previous grammar forces the use of prefix notation. It costs nothing to extend the grammar to include prefix and infix operators. The gain is purely in convenience not in power or difficulty of implementation.
This section considers list processing applications which require a list constructor, often called cons, and written as an infix operator `::'. The constant `nil' represents the empty list. Unary operators `hd' (head) and `tl' (tail) dismantle a list and `null' tests for the empty list. Conventionally a list is terminated by nil, but this is not essential.
Note that the conditional expression evaluates either its true or its false branch but not both, thus the expression below evaluates to 1 and is not in error. A strict function evaluates all of its arguments; the conditional is therefore a non-strict function.
The process of evaluating a λ expression is called reduction. Each operator must have an evaluation rule but the interesting case is the application of functions.
The actual parameter f is substituted for the formal parameter x throughout the function body, e[f/x]. This is called beta-reduction. A precise definition of substitution is given shortly.
The actual parameter 7 is substituted for n. The modified body is then evaluated.
The choice of a variable name is not important. A name can be changed provided this is done "systematically". This is called alpha-conversion.
Renaming can be used to prevent name clashes, e.g.,
We can now define substitution properly in terms of the original simple grammar. The most difficult case involves substitution in functions. There could be a name clash and the rule for functions effectively defines the scope rule of λ calculus in avoiding this problem. It is essentially the same as the scope rule in Pascal or other block-structured programming languages - this is where those programming languages got the idea.
There may be a choice of two or more applications in an expression. The strategy for determining which application to carry out next is called an evaluation rule. A familiar evaluation rule is variously known as strict evaluation or call by value. It requires the evaluation of an actual parameter before it is passed to, or substituted in, a function. It corresponds to passing parameters by value in a programming language such as Pascal. A second rule is known as normal-order evaluation or as call by name. It specifies that the left-most, outer-most application of an expression be carried out at each step. An actual parameter is not evaluated before being passed to a function. This corresponds to passing parameters by name, as in Algol-60.
In the example, normal-order evaluation terminates but strict evaluation does not.
The Church-Rosser theorem states firstly that if any evaluation rule terminates when applied to a particular expression then normal-order evaluation also terminates. Secondly, if any two evaluation rules terminate then they give the same result, up to alpha-conversion. Thus, normal-ord