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;
  return add1(
    (m => {
      if (isNull(m)) return 0;
      return add1(eternity(cdr(m)));
    })(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;
    return add1(length(cdr(l)));
  })(eternity);

The same trick applied to length1:

const length1EternityOut = (length => l => {
  if (isNull(l)) return 0;
  return add1(length(cdr(l)));
})(length1 =>
  (m => {
    if (isNull(m)) return 0;
    return add1(length1(cdr(m)));
  })(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;
    return add1(length(cdr(l)));
  }
);

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;
    return add1(length(cdr(l)));
  }
);

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;
  return add1(length(cdr(l)));
});

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;
  return add1(length(length)(cdr(l)));
});

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;
    return add1(length(cdr(l)));
  }
);

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;
  return add1(length(cdr(l)));
});

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