Page 2 of 3
So far we have a simple grammar that generates lots of strings of characters, but they don't have any meaning. At this point it is tempting to introduce meanings for what we are doing - but we don't have to. We can regard the whole thing as playing with symbols.
If this sounds like an empty thing to do, you need to remember that this is exactly what a Turing machine, or any computer, does. The symbols don't have any intrinsic meaning. When you write a program to compute the digits of Pi, say, you may think that you are doing something real, but the digits are just symbols and you add the extra interpretation that they are numbers in a place value system.
There are a number of additional rules added to the bare syntax of the lambda expression that can be used to reduce one expression to another. The most important to understand is probably beta reduction.
To the grammar above we can add another rule called beta reduction.
If you have a lambda expression of the form:
then you can reduce it to a new lambda expression by replacing every occurrence of x in t by s and erasing the λx. You can think of this as a simple string operation if you like. For example:
(λx. x z) (a b)
is of the form given with t=x z and s=a b.
By our new rule we can replace the x in x z with s, i.e. a b. The resulting new reduced expression is:
a b z
You can think of this as a function application. The function is
(λx. x z)
and λx can be thought of as defining the function's parameter as being x and the expression following the dot is the function's body.
Hence when you write:
(λx.x z) (a b)
the function is evaluated by having the parameter x set to (a b) in the function body.
The only thing odd about this is that we don't usually write the parameter values after the function in this way. This, however, fits in with Reverse Polish Notation used in most functional languages.
A very common example is the identity function:
which, if you think about its form, simply substitutes the expression you apply it to for x which gives you the original expression again.
For example given:
(λx. x)(a b)
then reduction means substitute (a b) for x in the function body which gives:
More than one parameter
You can have functions with more than one parameter by using more than one lambda. For example:
(λz. (λx. x z)) (a b) (c d)
which means set z to the first expression (a b) and then set x to the second expression giving:
(c d) (a b)
It is usual to abbreviate such multiple parameter functions by just writing a single lambda for all the parameters. For example:
(λz. (λx. x z) = λz x. x z
which means z and x are the parameters for the function body x z.
More than one function
Notice that you can have multiple function applications in a single expression. For example:
which is just two applications of the identify function reduces to:
(λy.y)(a b) after first reduction
(a b) after second reduction
You can repeatedly reduce a lambda expression until there are no more lambdas, or until there are no more arguments to supply values to the lambdas.
Notice that it makes it easier to think about reduction to liken it to function evaluation, but you don't have to. You can simply see it as a game with symbols.
If you think of a Turing machine then what is initially written on the tape is a set of symbols that is converted to a final output as the machine runs. This is computation.
In the case of lambda expressions you start with an initial expression and apply functions to it using beta reduction which produces a new string of symbols. This too is computation.