Encoding Recursion with the Y Combinator

In this post I’ll go through some exercises and encode some recursive functions with the Y combinator.

Encoding with rec

Continuing on from my last post, Professor Hutton gave us two exercises in the Y combinator video:

1. Encode loop (the function that just calls itself) with rec.  I.e.,

   loop = rec (?)

2. Encode the factorial function with rec.  I.e.,

   fac = rec (λf.λn.?)

Alpha-Conversion and Beta-Reduction

As we move towards more complicated functions, it is helpful to get familiar with some terminologies of concepts that we went over in my earlier posts:

1. Alpha (α)- conversion is the act of changing the variable name(s) of a function.  The variable names of a function can be changed without changing the function itself.  E.g., the following functions are α-equivalent, although they have different variable names:
   

   λx.x      (apply α-conversion to variable x)
   λy.y
   

   α-conversion is useful because it helps distinguish which function/variable you are working with, especially when there are multiple functions at once.

2. Beta (β)- reduction is the act of applying a function to an input.  E.g.,

   (λb.b FALSE TRUE) FALSE = FALSE FALSE TRUE      (β-reduction of b with input FALSE)
   

   Using this terminology clarifies what I’m doing in each step.  This is especially important when the corresponding functions and inputs are more complicated.

Encoding loop with rec

Because loop has to equal itself, but rec f = f (rec f), I have to find an f such that when it is passed to a function it’s still itself.  The identity function (λx.x) does exactly that!  Let’s verify that it works:

loop 
= rec (λx.x) 
= λf.(λx.f (x x)) (λx.f (x x)) (λx.x)      (rec is encoded as the Y combinator in lambda calculus.)
= (λx.(λx.x) (x x)) (λx.(λx.x) (x x))      (β-reduction of f with the input (λx.x))
= (λx.(λy.y) (x x)) (λx.(λy.y) (x x))      (apply α-conversion to variable x of (λx.x))
= (λy.y) ((λx.(λy.y) (x x))(λx.(λy.y) (x x)))      (β-reduction of x with the input (λx.(λy.y) (x x)))

You can see that I can keep going and the expression will not get smaller!  That’s when I learnt that the order of reduction matters!  You should β-reduce the function (the left item) as much as possible first, before applying the input (the right item) to it.  Let’s try again:

loop 
= λf.(λx.f (x x)) (λx.f (x x)) (λy.y)     
= (λx.(λy.y) (x x))(λx.(λy.y) (x x))      (β-reduction of f with the input (λy.y))
= (λx.(x x))(λx.(x x))      (β-reduction of (λy.y) with input (x x) in each item)
= (λx.x x)(λx.x x)

Refer back to my last post, this is exactly how loop can be encoded in lambda calculus!

Encoding the Factorial Function

The factorial function fac can be defined as a recursive function in the usual manner:

fac n = 0 when n == 1, else n * fac (n-1)

With the Y combinator, we don’t need to call fac recursively ourselves.  Instead, we can use the Y combinator, giving it f, which has the properties of the factorial function.  What are these properties?

1. It takes in an input n.
2. When n is 0, f equals 1.
3. When n is not 0, f equals n*f(n-1).

From 1, we know the beginning of what we should input to the Y combinator is:

λf.λn

Because we need to input f and also n.  Then, we define the output

if n == 0 then 1 else n*f (n-1)

That’s right, we just write out the function!  I have to confess that I did not realize that I can just write out the function itself like this in lambda calculus.  This is different from what I’ve seen so far, but it’s great that it’s so straight forward!  Therefore, we have:

fac = rec (λf.λn.(if n == 0 then 1 else n*f (n-1))

For simplicity I define:

F = (λf.λn.(if n == 0 then 1 else n*f (n-1))

A few notes before we demonstrate the function:

1. We know the Y combinator results in Y g = g (Y g), we will just apply this result rather than substituting the definition of Y.  Each time we recurse, we apply this result.
2. We evaluate the expression by substituting in the definition of F in the outer most layer only, so that we can β-reduce each layer in sequence.
3. Function application is left-associative.  That is Y F n = (Y F) n.

Let’s find the factorial of 2 as an example:

fac 2
= Y F 2      
= (Y F) 2      (Left-associative property of function application)      
= F (Y F) 2      (The Y combinator in action) 
= λf.λn.(if n == 0 then 1 else n*f (n-1)) (Y F) 2      (substitute in the definition of F in the outer most layer)      
= λn.(if n == 0 then 1 else n*(Y F) (n-1)) 2      (β-reduction of f with the input (Y F))
= (if 2 == 0 then 1 else 2*(Y F) (2-1))      (β-reduction of n with the input 2)
= 2* (Y F) (1)      (evaluate, 2≠0)
= 2* F (Y F) (1)      (The Y combinator in action)
= 2* λf.λn.(if n == 0 then 1 else n*f (n-1)) (Y F) (1)      (substitute in the definition of F in the outer most layer)
= 2* λn.(if n == 0 then 1 else n* (Y F) (n-1)) (1)      (β-reduction of f with the input (Y F))
= 2*(if 1 == 0 then 1 else 1* (Y F) (1-1))       (β-reduction of n with the input 1)
= 2*1* (Y F) (0)      (evaluate, 1≠0)
= 2*1* F (Y F) (0)      (The Y combinator in action)
= 2*1*λf.λn.(if n == 0 then 1 else n*f (n-1)) (Y F) (0) (substitute in the definition of F in the outer most layer)
= 2*1*λn.(if n == 0 then 1 else n* (Y F) (n-1)) (0)      (β-reduction of f with the input (Y F))
= 2*1*(if 0 == 0 then 1 else 1* (Y F) (0-1))      (β-reduction of n with the input 0)
= 2*1*1      (evaluate, 0 == 0)

There!  As desired, fac 2 = 2 *1!  The definition above defines the factorial function!