At the end of The Little Schemer, the authors lead you step-by-step through the process of deriving the Y Combinator. They do this repeatedly abstracting a length function–and then magically, the Y Combinator appears. It is a pretty neat trick, and certainly mind-bending on your first read through the book.
Since Javascript has first-class functions, we can derive the Y Combinator in Javascript as well. I will take a different approach than The Little Schemer. This approach owes a lot to a couple of blog posts I read on the subject1.
Since this is a post about recursive functions, then we can use that old chesnut, factorial. Here is a possible implementation of factorial in Javascript:
function basicFactorial(n) {
return n === 0 ? 1 : n * basicFactorial(n-1);
}
Let’s start by making a non-recursive basicFactorial, which we’ll call nonRecursive:
function nonRecursive(f) {
return function(n) {
return n === 0 ? 1 : n * f(n-1);
}
}
All we’ve done here is replace the recursive call of basicFactorial. Instead, we pass in a function that will get called. We can pass any function that returns something that supports the * operator:
nonRecursive(function(x) { return 0; })(100); // => 0
nonRecursive(function(x) { return 1; })(100); // => 100
nonRecursive(function(x) { return 10; })(100); // => 1000
// ... etc.
But it starts to get a little interesting when we pass basicFactorial in there. Then we get back … basicFactorial!
nonRecursive(basicFactorial)(4) === basicFactorial(4);
nonRecursive(basicFactorial)(10) === basicFactorial(10);
nonRecursive(basicFactorial)(17) === basicFactorial(17);
// ... etc.
In other words, basicFactorial is a fixed point of the function nonRecursive.
This is pointless in this case, since we have defined basicFactorial already. But suppose we had not defined basicFactorial. Wouldn’t it be nice if there was a function that we could pass nonRecursive to that would return the fixed point of it, i.e. the factorial function?
That is what the Y Combinator does. Pass nonRecursive to Y, and out comes the factorial function:
Y(nonRecursive)(100); // 9.33262154439441e+157
Note that:
Y(nonRecursive)(100) === nonRecursive(basicFactorial)(100);
Or in other words:
Y(nonRecursive)(100) === nonRecursive(Y(nonRecursive))(100);
So if we have Y, we do not need to define basicFactorial at all, we let Y derive it from the non-recursive function nonRecursive. Now let’s look at it from the other direction, and build up to Y. Here again, is the functional nonRecursive that we want to calculate the fixed point of:
function nonRecursive(f) {
return function(n) {
return n === 0 ? 1 : n * f(n-1);
}
}
As noted above, pass basicFactorial in, and nonRecursive returns basicFactorial. Notice that we have pretty much defined factorial in the body of nonRecursive: return n === 0 ? 1 : n * f(n-1);–why not use that? So here’s our next try: Apply nonRecursive to itself. This requires a small change to the body of nonRecursive, to self-apply the passed-in function to get the body out and apply it to the inner argument.
function nonRecursive(f) {
return function(n) {
return n === 0 ? 1 : n * f(f)(n-1);
};
}
nonRecursive(nonRecursive)(5); // => 120
Now we want to isolate the fixed point function. Let’s wrap that in a function g:
function nonRecursive(f) {
return function(x) {
var g = function(q) {
return function(n) {
return n === 0 ? 1 : n * q(n-1);
};
};
return g(f(f))(x);
};
}
Since inner function g does not depend on anything in closure, we can pull it out:
function g(f) {
return function(n) {
return n === 0 ? 1 : n * f(n-1);
};
}
The pulled-out function may look familiar–it’s nonRecursive again. Here’s what’s left over after g (a.k.a. nonRecursive) is pulled out; let’s call it almostY:
function almostY(f) {
return function(x) {
return g(f(f))(x);
};
}
almostY(almostY)(5); // => 120
We’ve pulled g out of almostY, but almostY still depends on g. The final step is to wrap almostY in a function that takes the functional g as an argument. Then almostY will have no dependencies.
So, let’s wrap it in a function that takes our non-recursive factorial functional and returns the fixed point of it. And since this is the last step, let’s call that function Y:
function Y(f) {
var p = function(h) {
return function(x) {
return f(h(h))(x);
};
};
return p(p);
}
Y(g)(6); // => 720
Holy crap! It works! But it’s not just for factorial–Y will provide a fixed point for any unary function, e.g.
function nonRecursiveFibonacci(f) {
return function(n) {
return n < 2 ? n : f(n-1) + f(n-2);
};
}
Y(nonRecursiveFibonacci)(10); // => 55
As presented, this version of Y can only handle unary functions, and it will blow up the stack for relatively low values of n. It is straightforward to extend Y to handle functions of any arity, and to memoize it.