# Deriving The Y Combinator

Posted on:October 23, 2020

To this day I remain in awe of a book that contains both a whole page dedicated to peanut butter jelly stains and a derivation of the Y combinator.

For my own understanding, I decided to “re-derive” the Y combinator by writing it in another language. It’ll be in JavaScript because of its natural syntax for lambda expressions.

The big idea behind the Y combinator, as stated in the book, starts off as a sort of musing — if we cannot give names to functions, how can we write recursive functions?

To expand on that a bit, recursive functions usually refer to themselves by name (or to the name of another function, in the case of mutual recursion), like this:

``````const recursiveLength = arr => {
if (arr.length === 0) return 0;
return 1 + recursiveLength(arr.slice(1));
};``````

However, in some fantasy world (i.e. the world of lambda calculus), there is no such concept of a function referring to itself (The Little Schemer says to pretend that `define` doesn’t exist), so let’s see how we can achieve recursion by reimplementing `recursiveLength`.

First off, let’s define some primitive functions:

``````const eternity = () => eternity();
const car = l => l;
const cdr = l => l.slice(1);
const isNull = l => l.length === 0;
const add1 = x => x + 1;``````

You might recognize the definition of `eternity` from a previous post on intuiting the Halting problem.

Now, let’s imagine a silly function, whose only use is to calculate the length of empty arrays.

``````const length0 = l => {
if (isNull(l)) return 0;
return 1 + eternity(cdr(l));
};

console.log(length0([])); // 0``````

`length0` only returns a legitimate value (of 0) for empty arrays. For any other array, `length0` can be thought of as returning an indeterminate value (i.e. does not terminate).

Using `length0`, how can we build `length1` without recursion? We can substitute `eternity(cdr(l))` with another copy of `length0`, nesting it like so,

``````const length1 = l => {
if (isNull(l)) return 0;
(m => {
if (isNull(m)) return 0;
})(cdr(l))
);
};

console.log(length1(["a"])); // 1``````

Now, using a sleight of hand, we can “pull” `eternity` out from `length0`, supplying it as an argument to a now higher-order function:

``````const length0EternityOut = length =>
(l => {
if (isNull(l)) return 0;
})(eternity);``````

The same trick applied to `length1`:

``````const length1EternityOut = (length => l => {
if (isNull(l)) return 0;
})(length1 =>
(m => {
if (isNull(m)) return 0;
})(eternity)
);``````

If we want to write `length2`, or `lengthN`, we need to figure out a way to avoid duplicating the function body. If you notice, `length1EternityOut` has a shape of `f(f(enternity))`, where `f` is the function `length => l => ...`, so we can pull that out:

``````const length1Deduplicate = (f => f(f(eternity)))(length => l => {
if (isNull(l)) return 0;
});``````

Again, if you can see, we apply the function `length => l...` to `f => f(f(eternity))` and it gives us back the same thing as `length1EternityOut`. It then becomes much easier to write `length2`. We simply nest it in another call to `f`:

``````const length2Deduplicate = (f => f(f(f(eternity))))(length => l => {
if (isNull(l)) return 0;
});``````

Now we’re getting somewhere. The `eternity` is a bit of a red herring — it can be safely removed at this point:

``````const length1NoEternity = (f => f(f(f)))(length => l => {
if (isNull(l)) return 0;
});``````

We’re still having to nest calls of `f` for each increasing `lengthX` — how do we avoid that? I must admit I was completely stumped at this point. In what I can only call a stroke of genius by whoever thought of this, we can move the “recursive” call inside the function instead, yielding this:

``````const lengthItself = (f => f(f))(length => l => {
if (isNull(l)) return 0;
});``````

So we can finally have a “non-recursive” function that can compute lengths of arbitrary arrays.

``console.log(lengthItself(["a", "b", "c"]));``

At this point, you might want to stop and ruminate about how this works before continuing. Convince yourself that whatever we have so far works.

Now for the finishing touch: how can we completely abstract the length function out? The `length(length)` part can be pulled out yet again:

``````const lengthRefactored = (g => (f => f(f))(f => g(x => f(f)(x))))(
length => l => {
if (isNull(l)) return 0;
}
);``````

And that’s it! Whatever you see in the front part is the Y combinator, stated on its own here:

``const y = g => (f => f(f))(f => g(x => f(f)(x)));``

When applied to a lambda, it recursively produces another copy of itself with the new argument, until the function no longer needs it (which in this case is represented by the base case `if (isNull)...`). This is also the reason it is called a fixed-point combinator. A fixed point of a function is a point of the function’s domain whose value remains the same after the function is applied to it. For example, for the function `f(x) = x * x`, a fixed point would be 1, since `f(1) = 1`.

In using the term fixed-point to refer to the Y combinator, what we’re really trying to say is the Y combinator behaves like this:

``y(g) === g(y(g));``

To me it’s a miracle that evaluating `y(g)` somehow gives itself back (and nested in an additional `g`, which is what gives it the recursion). Try evaluating it yourself by hand!

Here are a few more example applications of the Y combinator:

``````const length = y(length => l => {
if (isNull(l)) return 0;
});

console.log(length(["a", "b", "c"])); // 3

const fact = y(fact => x => {
if (x <= 2) return x;
return x * fact(x - 1);
});

console.log(fact(5)); // 120``````

It can also work with multiple arguments if the function is curried (or tupled):

``````const exists = y(exists => item => arr => {
if (isNull(arr)) return false;
if (item === car(arr)) return true;
return exists(item)(cdr(arr));
});

console.log(exists("a")(["b", "c"])); // false
console.log(exists("a")(["b", "a"])); // true``````