The Mysterious Y-Combinator

y-combinator.md

The Mysterious Y-Combinator

You may have heard the term before—you may even know what it is already. If you want a really technical description of the Y-combinator, look no further than Wikipedia (though we can certainly do better). However, this will leave most of us laymen more confused than we were going in. So what is the Y-combinator, really?

Getting right to it, written in ES6 this would look like the following (courtesy Brendan Eich):

let Y = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))

Yikes. What is this I don't even.

Let's explain it with code.

The Y-combinator has 2 main parts. A function that takes an identical function as its argument, which you can see here on line 2. Although they are the same, all the work happens on the right side.

let Y = f => {
  return (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))
  // --------------------------^
}

So, to use the most popular example, we'll create the non-recursive version of a factorial function with the following code.

let Yfact = Y(g => n => n <= 1 ? n : n * g(n - 1))

As you can see, Yfact doesn't use recursion here, because it's not calling itself. Let's look at a typical recursive factorial function, for reference:

let fact = n => n <= 1 ? n : n * fact(n - 1)

You'll note that the key difference is that Yfact is constructed from the Y function, which sets up Yfact to take a callback g that it will call instead of calling itself as you would in a typical recursive function.

In Yfact, we passed a functional into Y that wraps the actual factorial algorithm.

let Y = Yfact => {
  return (x => Yfact(v => x(x)(v)))(x => Yfact(v => x(x)(v)))
}

Here I have replaced the f param with Yfact to highlight what's happening within the Y function. The first thing that happens is the left (or "outer") function is called with the function from the right (or "inner") side. This wraps the Yfact function with a reference to the "inner" function.

let Yfact = Y(inner => n => n <= 1 ? n : n * inner(n - 1))

console.log(Yfact)
// n => n <= 1 ? n : n * inner(n - 1)

Now when Yfact is called, the final outer reference is called to set things into motion. From here, everything else happens from the inner function. Essentially, every time inner gets called by Yfact, it calls Yfact again which decides if it should call inner again.

Here is the basic order of operations:

1. Y is called with a function that takes a callback
2. Y initializes a construct that creates a circular callback reference wrapped around the original function it took and returns the fixed point for that
3. When the Y-combined function (Yfact) is called, it takes a value and does an operation, if it needs to repeat the operation with a new value, it calls the callback, otherwise it returns a value.
4. Once the first value is returned, the stack frames cascade backward, combining together all the values to get the final value, just like in recursion.

So what's the point of all this then?

The Y-combinator allows languages that don't have a concept of named functions (or those that have a concept of anonymous functions, like JavaScript) to create recursive functions in the absence of named functions. Typically for recursion to work, a function has to be able to call itself—something that's not possible in languages where naming functions isn't a concept. By creating this sort of circular callback logic, the Y-combinator works around the problem. The function never calls itself, instead it calls the callback it was given which then calls it again, emulating the act of recursion.

This was an early, very rough draft. Refer to The Mysterious Y-combinator for the published article.