Deriving The Y Combinator

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[0];
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;
  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, supplying it as an argument to a now higher-order function:

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

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

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

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

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

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;
  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 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