Getting the Y-combinator in 7 easy steps

The Y-combinator is a method for implementing the recursion mechanism in a programming language that does not support it initially (in fact, it is used more to implement brain programming). However, the language is required to support anonymous functions.



I chose JavaScript to get the Y-combinator, starting with the definition of the recursive factorial function, using incremental transformations over the original function.

Step 1

At the initial stage, we use the built-in JavaScript recursion mechanism.

var fact = function (n) { if (n < 2) return 1; return n * fact(n - 1); }; 

Step 2

To be the simplest thing to get basic recursion? We could define a function that takes itself as arguments and calls this argument with the same argument. Of course, this is an endless loop, and this will cause a stack overflow.

 (function (f) { f(f); })(function (f) { f(f); }); 

Let's use the pattern above for our factorial function. There is however a slight difference. The factorial function takes an argument that is not yet known, so we want to return a function that takes this argument. This function can be used to calculate factorials. Also, this is what makes our implementation not the result of an infinite loop.

 var fact = (function (f) { return function (n) { // termination condition if (n < 2) return 1; // because f returns a function, we have a double function call. return n * f(f)(n - 1); }; })(function (f) { return function (n) { // termination condition if (n < 2) return 1; // because f returns a function, we have a double function call. return n * f(f)(n - 1); }; }); 

Step 3

At the moment we have some ugly duplication. Let's hide it in some helper function recur

 var recur = function (f) { return f(f); }; var fact = recur(function (f) { return function (n) { if (n < 2) return 1; // because f returns a function, we have a double function call. return n * f(f)(n - 1); }; }); 

')

Step 4

The problem with the version above is double function call. We want to eliminate it, so to implement factorial similarly with the recursive version. How can we do this?



We can use a helper function that takes a numeric argument and performs a double call. The trick is to leave this helper function in some environment where f is visible, so that g can call f.

 var recur = function (f) { return f(f); }; var fact = recur(function (f) { var g = function (n) { return f(f)(n); }; return function (n) { if (n < 2) return 1; // no more double call, g is a function which takes a numeric arg return n * g(n - 1); }; }); 

Step 5

The work above is good, but the definition contains so much random code. We can hide it away inside another auxiliary function, leaving almost only the definition of factorial.

 var recur = function (f) { return f(f); }; var wrap = function (h) { return recur(function (f) { var g = function (n) { return f(f)(n); }; return h(g); }); }; var fact = wrap(function (g) { return function (n) { if (n < 2) return 1; return n * g(n - 1); }; }); 

Step 6

Let's embed the definition of g inside wrap since we only call it once.

 var recur = function (f) { return f(f); }; var wrap = function (h) { return recur(function (f) { return h(function (n) { return f(f)(n); }); }); }; var fact = wrap(function (g) { return function (n) { if (n < 2) return 1; return n * g(n - 1); }; }); 

Step 7

Now, if we also embed the definition of the recur function inside the wrap we will end up with the well-known Y-combinator.

 var Y = function (h) { return (function (f) { return f(f); })(function (f) { return h(function (n) { return f(f)(n); }); }); }; var fact = Y(function (g) { return function (n) { if (n < 2) return 1; return n * g(n - 1); }; }); 

the end

I hope you enjoyed it.