# Deriving The Y Combinator

October 23, 2020

To this day I remain in awe of a book that con­tains both a whole page ded­i­cat­ed to peanut butter jelly stains and a deriva­tion of the Y com­bi­na­tor.

For my own under­stand­ing, I decid­ed to “re-derive” the Y com­bi­na­tor by writ­ing it in anoth­er lan­guage. It’ll be in JavaScript because of its nat­ur­al syntax for lambda expres­sions.

The big idea behind the Y com­bi­na­tor, as stated in the book, starts off as a sort of musing — if we cannot give names to func­tions, how can we write recur­sive func­tions?

To expand on that a bit, recur­sive func­tions usu­al­ly refer to them­selves by name (or to the name of anoth­er func­tion, in the case of mutual recur­sion), like this:

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

How­ev­er, in some fan­ta­sy world (i.e. the world of lambda cal­cu­lus), there is no such con­cept of a func­tion refer­ring to itself (The Little Schemer says to pre­tend that `define` does­n’t exist), so let’s see how we can achieve recur­sion by reim­ple­ment­ing `recursiveLength`.

First off, let’s define some prim­i­tive func­tions:

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

You might rec­og­nize the def­i­n­i­tion of `eternity` from a pre­vi­ous post on intu­it­ing the Halt­ing prob­lem.

Now, let’s imag­ine a silly func­tion, whose only use is to cal­cu­late 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 legit­i­mate value (of 0) for empty arrays. For any other array, `length0` can be thought of as return­ing an inde­ter­mi­nate value (i.e. does not ter­mi­nate).

Using `length0`, how can we build `length1` with­out recur­sion? We can sub­sti­tute `eternity(cdr(l))` with anoth­er copy of `length0`, nest­ing 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`, sup­ply­ing it as an argu­ment to a now higher-order func­tion:

``````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 dupli­cat­ing the func­tion body. If you notice, `length1EternityOut` has a shape of `f(f(enternity))`, where `f` is the func­tion `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 func­tion `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 anoth­er call to `f`:

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

Now we’re get­ting some­where. The `eternity` is a bit of a red her­ring — 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 increas­ing `lengthX` — how do we avoid that? I must admit I was com­plete­ly stumped at this point. In what I can only call a stroke of genius by who­ev­er thought of this, we can move the “recur­sive” call inside the func­tion instead, yield­ing this:

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

So we can final­ly have a “non-recur­sive” func­tion that can com­pute lengths of arbi­trary arrays.

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

At this point, you might want to stop and rumi­nate about how this works before con­tin­u­ing. Con­vince your­self that what­ev­er we have so far works.

Now for the fin­ish­ing touch: how can we com­plete­ly abstract the length func­tion 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! What­ev­er you see in the front part is the Y com­bi­na­tor, stated on its own here:

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

When applied to a lambda, it recur­sive­ly pro­duces anoth­er copy of itself with the new argu­ment, until the func­tion no longer needs it (which in this case is rep­re­sent­ed by the base case `if (isNull)...`). This is also the reason it is called a fixed-point com­bi­na­tor. A fixed point of a func­tion is a point of the func­tion’s domain whose value remains the same after the func­tion is applied to it. For exam­ple, for the func­tion `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 com­bi­na­tor, what we’re really trying to say is the Y com­bi­na­tor behaves like this:

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

To me it’s a mir­a­cle that eval­u­at­ing `y(g)` some­how gives itself back (and nested in an addi­tion­al `g`, which is what gives it the recur­sion). Try eval­u­at­ing it your­self by hand!

Here are a few more exam­ple appli­ca­tions of the Y com­bi­na­tor:

``````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 mul­ti­ple argu­ments if the func­tion is cur­ried (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``````