Y Combinator

Every now and again you hear developers at some programming event talking about this fabled myth of a function, the understanding of which will transcend you to a new plane of programming. Well, challenge accepted. Spoiler, I am still among us mortals.

Thinking About the Problem

The first place you go: wiki. If you are anything like me, lambda calculus hurts your head and only paints a fuzzy picture. Heavy math aside, what problem does it solve? It lets us have recursion of anonymous functions.

Factorial function to the rescue

function factorial(num) {   
  return num === 0 ? 1 : num * factorial(num -1);  
}

To define recursion you must first define recursion.

But seriously, in order to be able to make this function anonymous, we need to get rid of our dependency on "factorial" I agree, crazy. But lets give it a try. Some closure? Maybe we can wrap it in a function? We no longer call the function by its name, does that help? Maybe if we can somehow call the wrapper function with the result of itself.

function(factorial) {
  return function(num) {   
    return num === 0 ? 1 : num * factorial(num -1);  
  };
}

And queue the entrance of the Y Combinator!

function Y(bindFn) {   
  return function () {  
    return bindFn(Y(bindFn)).apply(null, arguments);  
  };  
}

Untwisting the Pretzel

Right, that's what I thought, that a bit crazy. The factorial wrapper gets passed into it self, is that even possible? Seems so, here is a trace: (jsbin)

There is a beauty to this almost mechanical algorithm, reminiscent of the sewing machine or the RNA copy mechanism.

  • Wrap the anonymous function.
  • Send in the wrapped anonymous function into the Y combinator function.
  • Unpack the anonymous function and execute it, by passing the Y combinator result of the wrapped function into the wrapped function.

Related Books