In this post I'll derive the Y-combinator and explain all the steps taken. The key to understanding the Y-combinator is knowing precisely what it does. I am sure many people never understand Y-combinator because of this very reason, or because the introduction is too lengthy to comprehend. Therefore I'll give the shortest possible explanation of Y-combinator before I derive it so that you know what the end result should be.

The Y-combinator allows an anonymous function to call itself, that is, **it allows anonymous function recursion**. Since anonymous functions don't have names, they can't refer to themselves easily. The Y-combinator is a clever construct helps them to refer to themselves. That's it. That's all the Y-combinator does. Remember that.

I'll use the Scheme programming language to derive the Y-combinator. My derivation is based on the one in "The Little Schemer" book. I took the examples from the book, filled in the missing steps and explained the steps in more details.

Here it is.

Suppose we want to write the `length`

function, which, given a list, returns the number of elements in it. It's really easy if we can give the function a name:

```
(define length
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list)))))))
```

But now suppose that we can't give names - we can only use anonymous functions:

```
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (??? (cdr list)))))))
```

Suddenly there is no way this anonymous function can refer to itself. What do we put in ** ???**? We can't refer to the name

`length`

anymore because it's an anonymous function, which doesn't have any name. One thing we can try is to put the function itself in the place of **:**

`???`

```
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (
(lambda (list) ; the
(cond ;
((null? list) 0) ; function
(else ;
(add1 (??? (cdr list)))))) ; itself
(cdr list))))))
```

This is not much better, we are still left with ** ???**. But there is a bright side to it, this function can determine lengths of lists with one element and no elements. Let's try inserting the same anonymous function in place of

**again:**

`???`

```
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (??? (cdr list))))))
(cdr list))))))
(cdr list))))))
```

Now this function can determine lengths of lists with 0, 1 and 2 elements. If we continue this way, we can construct the `length`

function for lists with a certain number of elements. But this is not what we want, we the real `length`

function that works for lists with any number of elements.

As we all know, repeating code is not a good thing. Let's try to factor out the repetitions and rewrite the original anonymous function slightly. Instead of leaving `???`

in the code, let's pass it to an anonymous function via an argument called `length`

.

```
((lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list)))))))
???)
```

Notice that this code invokes the first `lambda (length)`

function and passes it `???`

as the `length`

argument. This function in turn returns the original anonymous function:

```
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (??? (cdr list))))))
```

Now let's try constructing the previous two length functions that work for lists with a maximum of one and two elements. First the function for lists with a maximum of one element:

```
((lambda (f)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (f (cdr list)))))))
((lambda (g)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (g (cdr list)))))))
???))
```

Here `???`

first gets passed to `lambda (g)`

, which returns the original anonymous function, which then gets passed to `lambda (f)`

, which in turn returns the function that works for lists with one element:

```
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (??? (cdr list))))))
(cdr list))))))
```

Similarly, the following code returns a function that works for lists with a maximum of two elements:

```
((lambda (f)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (f (cdr list)))))))
((lambda (g)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (g (cdr list)))))))
((lambda (h)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (h (cdr list)))))))
???)))
```

Since the argument names `f`

, `g`

,`h`

in `(lambda (f) ...)`

, `(lambda (g) ...)`

, `(lambda (h) ...)`

are independent, we can rename all of them to `length`

, to make it look more similar to the `length`

function:

```
((lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list)))))))
((lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list)))))))
((lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list)))))))
???)))
```

We are still repeating code. The obvious thing we can do about it is create an anonymous function called `mk-length`

(make length) that creates this code for us:

```
((lambda (mk-length)
(mk-length ???))
(lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list))))))))
```

This is pretty tricky. Observe how `(lambda (mk-length) ...)`

gets the `(lambda (length) ...)`

function passed as the `mk-length`

argument, which in turn accepts `???`

as an argument and returns our original anonymous function:

```
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (??? (cdr list))))))
```

Now let's try constructing length functions for lists of length one and two. For the list of length one, we just need to apply `mk-length`

on itself:

((lambda (mk-length) (<span style="color:green">mk-length</span></code> (<span style="color:blue">mk-length</span> ???))) (lambda (length) (lambda (list) (cond ((null? list) 0) (else (add1 (length (cdr list))))))))

Let's go through this code. First `(lambda (length) ...)`

gets passed to the `lambda (mk-length)`

function as the `mk-length`

argument. Then it applies the result of `(mk-length ???)`

(which is the original anonymous function) to the `mk-length`

. This produces our well known function that works on lists with one or none elements:

```
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (??? (cdr list))))))
(cdr list))))))
```

Similarly, by adding another call to `mk-length`

, we get the function that works for lists with two or less elements:

```
((lambda (mk-length)
(mk-length
(mk-length
(mk-length ???)))
(lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list))))))))
```

Now, since we don't know what `???`

is, let's just call it `mk-length`

and see what happens:

```
((lambda (mk-length)
(mk-length mk-length))
(lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list))))))))
```

Nothing bad actually happens, we still get the same original anonymous function, except in place of `???`

we have the function:

```
(lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list)))))))
```

Notice also that argument names `mk-length`

and `length`

in `lambda (mk-length)`

and `lambda (length)`

are independent. Therefore we can rename `length`

to `mk-length`

to remind that the first argument to `mk-length`

is `mk-length`

:

((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) (lambda (list) (cond ((null? list) 0) (else (add1 (<span style="color:green">mk-length</span> (cdr list))))))))

And now comes the key trick. We replace `mk-length`

with a self-application `(mk-length mk-length)`

:

```
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 ((mk-length mk-length) (cdr list))))))))
```

If you try this code out, you'll see that it returns the length of a list for any list. Here is an example of applying it to a list of 10 elements:

```
(((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 ((mk-length mk-length) (cdr list))))))))
'(a b c d e f g h i j))
```

The function works because it keeps adding recursive uses by passing `mk-length`

to itself, just as it is about to expire. This is not yet the Y-combinator, but we have successfully managed to recursively call an anonymous function. Now we need to massage the code a bit to separate the anonymous function from the self-applicative code.

The first step is to move the self-applicative code out as much as possible:

((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) <strong>((lambda (length) (lambda (list) (cond ((null? list) 0) (else (add1 (length (cdr list)))))))</strong> (lambda (x) ((mk-length mk-length) x)))))

Now the code in bold looks very much like the `length`

function we need! Let's move it outside as well:

((lambda (le) ((lambda (mk-length) (mk-length mk-length)) (lambda (mk-length) (le (lambda (x) ((mk-length mk-length) x)))))) <strong>(lambda (length) (lambda (list) (cond ((null? list) 0) (else (add1 (length (cdr list))))))))</strong>

There we have it! The anonymous `length`

function has been separated from the self-applicative call. The code in **bold** is the `length`

function, and the code not-in-bold is the Y-combinator!

Now let's rename `mk-length`

to `f`

and join the lines to make it more compact:

```
((lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x))))))
(lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list))))))))
```

And we are done. We can now write down the definition of Y-combinator:

```
(define Y
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))
```

And we can apply it to our anonymous `length`

function:

```
((Y (lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list))))))))
'(a b c d e f g h i j))
; ==> 10
```

This is one of many derivations of the applicative-order Y-combinator. See the publication "The Why of Y" for another derivation.