Matematika

A Tutorial Introduction to the Lambda Calculus
Ra_ul Rojas_
FU Berlin, WS-97/98
Abstract
This paper is a short and painless introduction to the _ calculus. Originally developed in order to study some mathematical properties of ectively computable functions, this formalism has provided a strong theoretical foundation for the family of functional programming languages. We show how to perform some arithmetical computations using the _ calculus and how to de_ne recursive functions, even though functions in _ calculus are not given names and thus cannot refer explicitly to themselves.

1 De_nition
The _ calculus can be called the smallest universal programming language of the world. The _ calculus consists of a single transformation rule (variable substitution) and a single function de_nition scheme. It was introduced in the 1930s by Alonzo Church as a way of formalizing the concept of e_ective computability. The _ calculus is universal in the sense that any computable function can be expressed and evaluated using this formalism. It is thus equivalent to Turing machines. However, the _ calculus emphasizes the use of transformation rules and does not care about the actual machine implementing them. It is an approach more related to software than to hardware.The central concept in _ calculus is the \expression". A \name", also called a \variable", is an identi_er which, for our purposes, can be any of the letters a; b; c; : : :
An expression is de_ned recursively as follows:
:= j j
:= _ .
:=
An expression can be surrounded with parenthesis for clarity, that is, if E is an expression, (E) is the same expression. The only keywords used in the language are _and the dot. In order to avoid cluttering expressions with parenthesis, we adopt the convention that function application associates from the left, that is, the expression E1E2E3 : : :En
_Send corrections or suggestions to rojas@inf.fu-berlin.de

is evaluated applying the expressions as follows:
(: : : ((E1E2)E3) : : :En)
As can be seen from the de_nition of _ expressions given above, a single identi_er
is a _ expression. An example of a function is the following:
_x:x
This expression de_nes the identity function. The name after the _ is the identi_er of the argument of this function. The expression after the point (in this case a single x) is called the \body" of the de_nition.
Functions can be applied to expressions. An example of an application is
(_x:x)y This is the identity function applied to y. Parenthesis are used for clarity in order to avoid ambiguity. Function applications are evaluated by substituting the value of the argument x (in this case y) in the body of the function de_nition, i.e.
(_x:x)y = [y=x]x = y
In this transformation the notation [y=x] is used to indicate that all occurrences of x are substituted by y in the expression to the right.
The names of the arguments in function de_nitions do not carry any meaning by themselves. They are just \place holders", that is, they are used to indicate how to rearrange the arguments of the function when it is evaluated. Therefore (_z:z) _ (_y:y) _ (_t:t) _ (_u:u)
and so forth. We use the symbol \_" to indicate that when A _ B, A is just a
synonym of B.

1.1 Free and bound variables
In _ calculus all names are local to de_nitions. In the function _x:x we say that x is \bound" since its occurrence in the body of the de_nition is preceded by _x. A name not preceded by a _ is called a \free variable". In the expression (_x:xy) the variable x is bound and y is free. In the expression (_x:x)(_y:yx) the x in the body of the _rst expression from the left is bound to the _rst _. The y in the body of the second expression is bound to the second _ and the x is free. It is very important to notice that the x in the second expression is totally independent
of the x in the _rst expression. Formally we say that a variable is free in an expression if one of the
following three cases holds:
_ is free in .
_ is free in _ : if the identi_er 6=
and is free in .
_ is free in E1E2 if is free in E1 or if it is free in E2.
A variable is bound if one of two cases holds:
_ is bound in _ : if the identi_er =
or if is bound in .
_ is bound in E1E2 if is bound in E1 or if it is bound in E2.
It should be emphasized that the same identi_er can occur free and bound in the
same expression. In the expression
(_x:xy)(_y:y)
the _rst y is free in the parenthesized subexpression to the left. It is bound in the
subexpression to the right. It occurs therefore free as well as bound in the whole expression.

1.2 Substitutions
The more confusing part of standard _ calculus, when _rst approaching it, is the fact that we do not give names to functions. Any time we want to apply a function, we write the whole function de_nition and then procede to evaluate it. To simplify the notation, however, we will use capital letters, digits and other symbols as synonyms for some function de_nitions. The identity function, for example, can be denoted with
I which is a synonym for (_x:x).
The identity function applied to itself is the application
II _ (_x:x)(_x:x)
In this expression the _rst x in the body of the _rst expression in parenthesis is independent of the x in the body of the second expression. We can in fact rewrite the above expression as
II _ (_x:x)(_z:z)
The identity function applied to itself
II _ (_x:x)(_z:z)
yields therefore
[_z:z=x]x = _z:z _ I
that is, the identity function again.
We should be careful when performing substitutions to avoid mixing up free occurrences of an identi_er with bound ones. In the expression
(_x:(_y:xy))y
The function to the left contains a bound y, whereas the y at the right is free. An incorrect substitution would mix the two identi_ers in the erroneous result (_y:yy)
Simply by renaming the bound y to t we obtain
(_x:(_t:xt))y = (_t:yt)
which is a completely di_erent result but nevertheless the correct one.
Therefore, if the function _x: is applied to E, we substitute all free occurrences
of x in with E. If the substitution would bring a free variable of E in
an expression where this variable occurs bound, we rename the bound variable before
performing the substitution. For example, in the expression
(_x:(_y:(x(_x:xy))))y
we associate the argument x with y. In the body
(_y:(x(_x:xy)))
only the _rst x is free and can be substituted. Before substituting though, we have to rename the variable y to avoid mixing its bound with is free occurrence:
[y=x](_t:(x(_x:xt))) = (_t:(y(_x:xt)))
In normal order reduction we try to reduce always the left most expression of a
series of applications. We continue until no further reductions are possible.
2 Arithmetic
We expect from a programming language that it should be capable of doing arithmetical
calculations. Numbers can be represented in lambda calculus starting from zero and writing \suc(zero)" to represent 1, \suc(suc(zero))" to represent 2, and so on. In the lambda calculus we can only de_ne new functions. Numbers will be de_ned as functions using the following approach: zero can be de_ned as _s:(_z:z)
This is a function of two arguments s and z. We will abbreviate such expressions with more than one argument as
_sz:z It is understood here that s is the _rst argument to be substituted during the evaluation and z the second. Using this notation, the _rst natural numbers can be de_ned as
1 _ _sz:s(z)
2 _ _sz:s(s(z))
3 _ _sz:s(s(s(z))) and so on.
Our _rst interesting function is the successor function. This can be de_ned as S _ _wyx:y(wyx)
The successor function applied to our representation for zero yields
S0 _ (_wyx:y(wyx))(_sz:z)
In the body of the _rst expression we substitute all occurrences of w with (_sz:z) and this yields
_yx:y((_sz:z)yx) = _yx:y((_z:z)x) = _yx:y(x) _ 1
That is, we obtain the representation of the number 1 (remember that variable names are \dummies").
Successor applied to 1 yields:
S1 _ (_wyx:y(wyx))(_sz:s(z)) = _yx:y((_sz:s(z))yx) = _yx:y(y(x)) _ 2
Notice that the only purpose of applying the number (_sz:s(z)) to the arguments y and x is to \rename" the variables used in the de_nition of our number.
2.1 Addition
Addition can be obtained immediately by noting that the body sz of our de_nition of the number 1, for example, can be interpreted as the application of the function s
on z. If we want to add say 2 and 3, we just apply the successor function two times to 3.
Let us try the following in order to compute 2+3:
2S3 _ (_sz:s(sz))(_wyx:y(wyx))(_uv:u(u(uv)))
The _rst expression on the right side is a 2, the second is the successor function, the
third is a 3 (we have renamed the variables for clarity). The expression above reduces
to (_wyx:y((wy)x))((_wyx:y((wy)x))(_uv:u(u(uv)))) _ SS3

The reader can verify that SS3 reduces to S4 = 5.
2.2 Multiplication
The multiplication of two numbers x and y can be computed using the following
function:
(_xyz:x(yz))
The product of 2 by 2 is then:
(_xyz:x(yz))22
which reduces to
(_z:2(2z))
The reader can verify that by further reducing this expression, we can obtain the
expected result 4.
5
3 Conditionals
We introduce the following two functions which we call the values \true"
T _ _xy:x
and \false"
F _ _xy:y
The _rst function takes two arguments and returns the _rst one, the second function
returns the second of two arguments.
3.1 Logical operations
It is now possible to de_ne logical operations using this representation of the truth
values.
The AND function of two arguments can be de_ned as
^ _ _xy:xy(_uv:v) _ _xy:xyF
The OR function of two arguments can be de_ned as
_ _ _xy:x(_uv:u)y _ _xy:xTy
Negation of one argument can be de_ned as
: _ _x:x(_uv:v)(_ab:a) _ _x:xFT
The negation function applied to \true" is
:T _ _x:x(_uv:v)(_ab:a)(_cd:c)
which reduces to
TFT _ (_cd:c)(_uv:v)(_ab:a) = (_uv:v) _ F
that is, the truth value \false".
3.2 A conditional test
It is very convenient in a programming language to have a function which is true if
a number is zero and false otherwise. The following function Z complies with this
requirement
Z _ _x:xF:F
To understand how this function works, note that
0fa _ (_sz:z)fa = a
that is, the function f applied zero times to the argument a yields a. On the other
hand, F applied to any argument yields the identity function
Fa _ (_xy:y)a = _y:y _ I
6
We can now test if the function Z works correctly. The function applied to zero yields
Z0 _ (_x:xF:F)0 = 0F:F = :F = T
because F applied 0 times to : yields :. The function Z applied to any other number
N yields
ZN _ (_x:xF:F)N = NF:F
The function F is then applied N times to :. But F applied to anything is the identity, so that the above expression reduces for any number N greater than zero to
IF = F
3.3 The predecessor function
We can now de_ne the predecessor function combining some of the functions introduced above. When looking for the predecessor of n, the general strategy will be to create a pair (n; n 􀀀 1) and then pick the second element of the pair as the result.
A pair (a; b) can be represented in _-calculus using the function
(_z:zab)
We can extract the _rst element of the pair from the expression applying this function
to T (_z:zab)T = Tab = a
and the second applying the function to F
(_z:zab)F = Fab = b
The following function generates from the pair (n; n􀀀1) (which is the argument p in
the function) the pair (n + 1; n 􀀀 1):
_ _ (_pz:z(S(pT))(pT))
The subexpression pT extracts the _rst element from the pair p. A new pair is formed using this element, which is incremented for the _rst position of the new pair and just copied for the second position of the new pair. The predecessor of a number n is obtained by applying n times the function _ to the pair (_:z00) and then selecting the second member of the new pair:
P _ (_n:n_(_z:z00)F
Notice that using this approach the predecessor of zero is zero. This property is useful
for the de_nition of other functions.
3.4 Equality and inequalities
With the predecessor function as the building block, we can now de_ne a function which tests if a number x is greater than or equal to a number y:
G _ (_xy:Z(xPy))
7
If the predecessor function applied x times to y yields zero, then it is true that x _ y.
If x _ y and y _ x, then x = y. This leads to the following de_nition of the
function E which tests if two numbers are equal:
E _ (_xy: ^ (Z(xPy))(Z(yPx)))
In a similar manner we can de_ne functions to test whether x > y, x < y or x 6= y.
4 Recursion
Recursive functions can be de_ned in the _ calculus using a function which calls a function y and then regenerates itself. This can be better understood by considering
the following function Y:
Y _ (_y:(_x:y(xx))(_x:y(xx)))
This function applied to a function R yields:
YR = (_x:R(xx))(_x:R(xx))
which further reduced yields:
R((_x:R(xx))(_x:R(xx))))
but this means that YR = R(YR), that is, the function R is evaluated using the recursive call YR as the _rst argument.
Assume, for example, that we want to de_ne a function which adds up the _rst n
natural numbers. We can use a recursive de_nition, since Pn
i=0 i = n +Pn􀀀1
i=0 i. Let
us use the following de_nition for R:
R _ (_rn:Zn0(nS(r(Pn))))
This de_nition tells us that the number n is tested: if it is zero the result of the sum is zero. If n is not zero, then the successor function is applied n times to the recursive call (the argument r) of the function applied to the predecessor of n.
How do we know that r in the expression above is the recursive call to R, since functions in _ calculus do not have names? We do not know and that is precisely
why we have to use the recursion operator Y. Assume for example that we want to add the numbers from 0 to 3. The necessary operations are performed by the call: YR3 = R(YR)3 = Z30(3S(YR(P3)))
Since 3 is not equal to zero, the evaluation reduces to
3S(YR2) that is, the sum of the numbers from 0 to 3 is equal to 3 plus the sum of the numbers from 0 to 2. Successive recursive evaluations of YR will lead to the correct _nal result. Notice that in the function de_ned above the recursion will be broken when the argument becomes 0. The _nal result will be
3S2S1S0
that is, the number 6.
8
5 Projects for the reader
1. De_ne the functions \less than" and \greater than" of two numerical arguments.
2. De_ne the positive and negative integers using pairs of natural numbers.
3. De_ne addition and subtraction of integers.
4. De_ne the division of positive integers recursively.
5. De_ne the function n! = n _ (n 􀀀 1) _ _ _ 1 recursively.
6. De_ne the rational numbers as pairs of integers.
7. De_ne functions for the addition, subtraction, multiplication and division of
rationals.
8. De_ne a data structure to represent a list of numbers.
9. De_ne a function which extracts the _rst element from a list.
10. De_ne a recursive function which counts the number of elements in a list.
11. Can you simulate a Turing machine using _ calculus?
References

[1] P. M, Kogge, The Architecture of Symbolic Computers, McGraw-Hill, New York,
1991, chapter 4.

[2] G. Michaelson, An Introduction to Functional Programming through Lambda Calculus,
Addison-Wesley, Wokingham, 1988.

[3] G. Revesz, Lambda-Calculus Combinators and Functional Programming, Cambridge
University Press, Cambridge, 1988, chapters 1{3.