One of the most profound ideas in lambda calculus, is the Y-operator.

I’ve learned the Y-operator at least three times, and every time, I found

it extremely hard to understand. This blog is therefore an example of a

quixotic undertaking: I want to see whether it is possible for me to

explain the Y-operator so that you, gentle reader, can understand it

with minimal background. In this case, “minimal background” means

at least a few years of college level mathematics.

## Background: Why Y?

The Y-operator is part of lambda calculus, a field of logic that

appeals to people who just couldn’t get enough of solving equations in

high-school mathematics. Lambda calculus is named after the “lambda”

operator, which stands for an “anonymous function”. It can be used to

syntactically (that is, mechanically) transform expressions. A short

example: “`(lambda (x) (* x x))`” is a method that takes one

argument (called `x`) and returns the square of the argument.

Here is how you use it:

1 2 3 4 5 |
((lambda (x) (* x x)) 8) ;; apply the abovementioned function to 8 => (* 8 8) ;; MECHANICALLY substiture 8 for x => 64 ;; Whee! |

The Y-operator is used to create *recursive* functions

using lambdas. That is, functions that call themselves. That is

its *purpose*. Y is defined as follows:

1 |
(Y F) = (F (Y F)) |

For this to work, F better be a function. Read it as follows:

“Y of a function F equals F applied to Y of F”.

## An example: Factorial

As I said: This allows us to define recursive stuff using just

lambdas. To demonstrate, I will need a volunteer recursive function.

You over there: Factorial! could you step over here, please?

The factorial function is defined thus: The factorial of a number

n is the *product* of all natural numbers up to n. A way of

writing this in a fairly conventional syntax is:

`fact(n) = (n == 1) ? 1 : (n * fact(n - 1))`. Now, lets

do it *without function definitions*. Lets say we want to

find the factorial of 8. In lambda calculus we can write:

1 2 3 4 |
((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) 8) |

Holy lambda, Batman! That didn’t help much, did it? Well: here’s

the good thing: *You don’t have to understand it*. Using

what we learned about lambda, we can just blindly calculate it.

Lets see how it works.

## Doing the math

Calculating the factorial for 8 will be a really long

exercise, so let’s settle for 2 instead. Here we go:

1 2 3 4 |
((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) 2) |

Substitute the definition of `(Y F) = (F (Y F))`:

1 2 3 4 5 6 7 |
(((lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x)))))) (Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x)))))))) 2) |

Whoa, those parenteses are dizzying. Well, we can substitute for the

f in the first lambda:

1 2 3 4 5 6 7 8 9 |
((lambda (x) (if (= x 1) 1 (* x ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) (-1 x))))) 2) |

Keep substituting for the outer lambda at all times. This time x = 2 (only for the outer lambda)

1 2 3 4 5 6 |
(if (= 2 1) 1 (* 2 ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) (-1 2)))) |

We now know the answer to the `if` (and I’ll expand `(-1 2)` => `1` as well):

1 2 3 4 |
(* 2 ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) 1)) |

We need to do another of those crazy Y expansions. It is not hard, just exchange the f

(I’ll skip one step this time):

1 2 3 4 5 6 7 8 |
(* 2 ((lambda (x) (if (= x 1) 1 (* x ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) (-1 x))))) 1)) |

Substitute the 1 for x in the outermost lambda:

1 2 3 4 5 6 |
(* 2 (if (= 1 1) 1 (* 1 ((Y (lambda (f) (lambda (x) (if (= x 1) 1 (* x (f (-1 x))))))) (-1 x))))) |

If we had started with a larger number, we would’ve gotten a string of

`(* 4 (* 3 (* 2....` built up from these transformations. But we’re

almost done: The `if` is true this time, so we can substitute:

1 |
(* 2 1) |

The whole Y and lambda mess just evaporated. w00t! And the answer is

of course `2` which is correct.

## What happened?

What the magic `(Y F) = (F (Y F))` does is to let us embed a

function within itself an inifinitely number of times. So, for factorial:

1 |
(Y fact) = (fact (fact (fact (fact (fact (Y fact)))))) |

In this case `fact` is defined as (pay attention now): A function that

takes a function as an argument and returns another function. The returned

function takes a natural number as an argument, and if the number is one, it

returns it, otherwise: *it calls the function that was given as argument to the
first function*. Y keeps injecting fact into itself, so it can always go

deeper in the recursive call. But as soon as the number reaches 1,

*we don’t*

have to go any further, and the “final” (Y fact) collapses into

have to go any further

nothingness.

Y generates as many function applications as we need, so it will let us

create recursiveness, without naming a single function. (Y F) is then

the value of F when F is applied to itself an infinitely number of times.

This is called *the fixed point for the function F*.

## Conclusion: Why Y?

The Y operator lets us use purely *syntactic* (mechanical) steps

to evaluate recursive functions. It gives the mathematical construct of

lambda calculus as much computing power as a programming language, without

needing to define names for functions. It is a mathematical marvel.

Can it be used for anything? I don’t really think so. But just as

Y expands a lambda expression, it can expand your mind. I hope that

you feel a little smarter going away from this blog than entering it.

You can read more about the Y-operator at wikipedia.

Of course.

And if you want to go for the whole nine yards, check out the Structure and Interpretation of Computer Programs online video

lectures! 20 hours of Lisp!

## Postscript

Did you manage to read through the whole article? Did you understand it?

Let me know what you think: Write a comment, or send me an

email.

Copyright © 2006 Johannes Brodwall. All Rights Reserved.