Lambda Calculus Part 3: Evaluation
So you’ve made it far enough in λ calculus that you now understand the three types of expressions. The next obvious step is how to actually do stuff with the expressions. This is where the two rules of evaluation come in. (There is a third rule, but it is of less importance in a quick intro like this one.)
The first rule is called α conversion. An α conversion replaces one name with another to ensure you don’t have naming collisions. This may seem relatively trivial - since the meaning of an expression isn’t changed - but it will become very important once we introduce recursion.
The second rule is called β reduction. A β reduction is how you apply a function in λ calculus: the replacement of a bound variable with an argument in a function body.
As Mark Chu-Carrol describes it: “If you have a function application, you can apply it by replacing the function with the body of the λ and then taking the argument expression and replacing all uses of the parameter in the λ with the argument expression.” (Good Math, p. 225)
This may seem like quite a mouthful, but β reduction has a deep significance: with it, the λ calculus can perform any computation that can by carried out by a machine.
Let’s look at an example of β reduction that harks back to part 1:
The first step in the β reduction is to apply the first parameter, which reduces to:
Which in turn reduces to:
Which is, of course:
A name clash (sometimes also referred to as “the name capture problem”) arises when a β reduction places an expression with a free variable in the scope of a bound variable with the same name as the free variable. So, α conversion is the process which removes the name clash.
Let’s look at a λ expression where α reduction will resolve a name clash:
The first occurrence of y in the expression above is bound, while the second - the one on the far right - is free. If we were to replace
y blindly, we would get the incorrect reduction
(λy. y + y). Applying α conversion we arrive at the following steps:
1 2 3 ((λx.(λy. x + y)) y) ((λx.(λz. x + z)) y) (λz. y + z)
This all may seem a bit abstract for now, so we’ll look at the two different evaluation strategies of λ expressions in the next part. In the final parts, we’ll show how λ calculus is Turing complete by constructing numbers and flow of control.