EECS 762

Programming Language Foundation I


Y-Combibator example

Note that I need to do one more proofread before I’m 100% confident in this example.

Yesterday in class we went through a derivation of factorial using the y-combinator to construct a recursive function. We made it through one step, but I thought it would be a good idea to provide a step-by-step example of how it worked.

First, we’re going to be disciplined in how we apply $\beta$-reduction. The rule says that we apply the lambda when its argument is a value. Not all the argument, but when its specific argument is a lambda.

Second, \(g\) is not a variable. It is a value that may be expanded at any time. You’re welcome to do this from the beginning if you want, but it’s not much fun.

Third, applications are left associative. This means that \(A\; B\; C\; D\) fully parenthesized is \((((A\; B)\; C)\; D)\). The left-most application is reduced first

Finally, the body of a lambda extends as far right as possible. Specifically, \(\lambda x . A B\) is \((\lambda x . A B)\) note \((\lambda x . A) B\).

Let’s initially remember the form of the Y-Combinator:

Now the function we’ll pass into \(fix\) as its function argument:

So, factorial becomes:

and $fact 3$ becomes:

Parenthesis are added for clarity. Let’s first replace \(fix\) by it’s value defined above. This is not a reduction, but simply replacing a symbol by its value:

Now we have a lambda applied to ((g)). The lambda’s parameter is \(f\) and it’s body goes as far to the right as possible. That would be the parenthesis right before \(g\) making \(g\) the argument to the outermost lambda. \(g\) is itself a lambda, a value by definition. So, we can replace \(f\) with \(g\) in the body of the lambda:

Note that we’re not expanding \(g\) yet. Look at the form of the result. There are three values here - the Y-combinator with \(g\)$ replacing the variable \(f\) twice and the parameter 3. Remember that application is left associative, so we’ll take care of the Y-Combinator reduction first before worrying about 3:

Look at what’s happened. \(g\) is now out front, so the factorial body is going to be invoked at least once. Let’s expand the first \(g\) in place:

\(f\) is now replaced with the Y-Combinator instantiated with \(g\). This is as it should be because that’s the call we want to make recursively - the Y-Combinator instantiated with \(g\) is exactly \(fact\).

Beta reduction on the outermost lambda replaced \(f\):

Now we have a lambda whose body extends to 3 allowing us to reduce the outermost lambda by replacing \(n\) with 3:

Pretty cool. When \(n\) is replaced by 3, the \(if\) falls away leaving 3 multiplied by the recursive call to \(fact\). Look what also happened. \(n-1\) in the recursive call becomes \(3-1\) or 2. Exactly what we need it to be. We’re left with 3 times

Finally, we see what the \(y\) added to Omega to get Y does. It pulls the value 2 into place for the recursive call. The outermost \(y\) is replaced giving us the following form:

If you look carefully, this is exactly \(3*(fact\; 2)\). Just what we want.

Will the recursion terminate? After two more reductions, the input parameter to \(fact\) will zero; Something like this:

If we go through the previous steps again with 0 as \(n\) we will end up with:

Now the \(n\) is replaced by 0 and \(0=0\) is true. Thus resuilting in 1 with no additional work. The result becomes:

and \(f\) turns of th recursion just like we wanted it to.

It’s a lot of work to get 6, but it provides a way of performing recursion without a global namespace. Pretty neat.