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:

- Encode
*loop*(the function that just calls itself) with*rec*. I.e.,loop = rec (?)

- 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:

The variable names of a function can be changed without changing the function itself. E.g., the following functions are*Alpha (α)- conversion*is the act of changing the variable name(s) of a function.**α-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.

E.g.,*Beta (β)- reduction*is the act of applying a function to an input.(λ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?

- It takes in an input n.
- When n is 0, f equals 1.
- 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:

- 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. - 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. - 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!

## Leave a Reply