# Javascript Y Combinator

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:

Let’s start by making a non-recursive `basicFactorial`, which we’ll call `nonRecursive`:

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:

But it starts to get a little interesting when we pass `basicFactorial` in there. Then we get back … `basicFactorial`!

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:

Note that:

Or in other words:

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:

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.

Now we want to isolate the fixed point function. Let’s wrap that in a function `g`:

Since inner function `g` does not depend on anything in closure, we can pull it out:

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`:

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`:

Holy crap! It works! But it’s not just for factorial–`Y` will provide a fixed point for any unary function, e.g.

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.

1. I found these articles helpful: Fixed-point combinators in JavaScript: Memoizing recursive functions and Deriving the Y combinator.
05 September 2013