Y Combinator explained

I have spent some time to look into the Y Combinator, a function for defining recursive functions without using conventional recursion support.

The Y Combinator is quite legendary in functional programming, and appears in "The Little Schemer", by Daniel P. Friedman and Matthias Felleisen. The idea is to show how recursion can be expressed in a language that does not support recursion (but has support for higher-order functions). As implementation language I will use JavaScript, and I will also show how Y can be expressed in Smalltalk and in Erlang.

A good article on Y written by James Coglan can be found here: http://blog.jcoglan.com/2008/01/10/deriving-the-y-combinator/. Like James Coglan, I write this blog article to better understand Y, and I use a somewhat different approach to explain it. A tool you can use to interactively experiment with the functions below, is this live browser-based JavaScript editor: http://droidscript.se/jsedit.html

Typically a recursive function is said to "call itself", like this recursive definition of the factorial function in JavaScript:

function factorial(n) {
    if (n == 0) { return 1; }
    else { return n * factorial(n - 1); }
}

The trick to understand recursion, and the Y Combinator, is that a recursive function actually does not "call itself", it calls an instance of a function that has the same function body, but with its own values for the actual parameters. Thus, recursion is not iterative, but consists of a chain of function calls lined up waiting for each other to return (unless you have optimised tail recursion, but that is another story). When the recursion has reached the end and returns, the function calls that wait return one by one, each using their local variable values to compute their result in the call chain.

If I could draw a diagram of this (not easily done with primitive blog tools!), it would become more clear than using plain words. But we can picture the call chain like this:

factorial(3)

is the same as:

3 * (2 * (1 * (1)))

This is what we get if we substitute the calls with the actual variable values in each function instance. The innermost 1 is the number returned by the factorial function when the value of n is zero.

The point of Y Combinator is to show that recursion can be expressed without referring to the name of the recursive function. Of little practical relevance, but an interesting exploration of recursive functional structures.

Lets start by this recursive JavaScript function:

function repeat() {
    if (confirm("Continue?")) { repeat(); }
}

How can this be written without referring to the name of the function? To do this, we will use an anonymous function that takes another anonymous function as a parameter.

Anonymous functions are functions that do not have a name, here is a quick example before we continue.

This:

function twice(n) { return n * 2; }
alert(twice(22));

Can be written as:

fun = function(n) { return n * 2 };
alert(fun(22));

Or, if we substitute the variable fun with the expression it refers to:

result = (function(n) { return n * 2 }) (22);
alert(result);

Now back to the version of repeat written with anonymous functions:

(function(fun) { fun(fun); }) 
(function(fun) { 
    if (confirm("Continue?")) { fun(fun); });

What happens here is that the function (function(fun) { fun(fun); }) gets called and "kick-starts" the recursion. This is an anonymous function that takes another function as a parameter. It then calls that function with the very same function as the argument. The actual function being called is the other anonymous function, which is a variation of our continue function. Inside that function, the function is again called, with the very same function as its argument! This means that we will get an endless chain of function calls until the user chooses not to continue, in which case the recursive function application is not called, and the call stack unwinds and the function call chain terminates.

Another way to write the same thing:

repeat = (function(fun) { 
    if (confirm("Continue?")) { fun(fun); });
repeat(repeat);

Here we use a variable to refer to the anonymous function, and apply it to itself. Note that this is not cheating, it is not a named recursive function call, and we could just as well have replaced the occurrences of repeat in the call on the second line with the function expression it refers to.

This "trick" of calling a function with another function as a parameter (which happens to be the same function), is at the heart of the Y Combinator.

Before showing Y, we will use one more intermediate step. The above example does not take a parameter, and does not return anything useful. To recursively compute something, say the factorial of a number, we need to be able to supply parameters to and return values from the recursive function applications.

Here is factorial written as a "kick-started" anonymous recursive function; then we call the function using the variable factorial, which refers to the expression that starts the computation:

factorial = (function(fun) { return fun(fun); })
    (function(fun) {
        return function(n) {
            return n == 0 ? 1 : n * fun(fun)(n - 1); } } );
alter(factorial(9));

Tadam! Here we have proper recursion without using named functions. But what does the variable factorial in the above piece of code refer to? It refers to an instance of the anonymous function that starts on line 3, with the local variable fun referring to the anonymous function that starts on line 2. The function returned on line 3 is an example of a closure; a function instance that has some of its local variables initialised, but has not yet started to execute. On line 5, that function gets called with the argument value 9. And on line 4 the same process continues and drives the recursion.

It is still a bit cumbersome and non-general to have to apply fun to itself inside factorial. It would be nicer to have something that looks like a proper recursive function call, and this is what Y accomplishes.

Finally, here is the definition of Y Combinator, using a style similar to the one we have used above:

Y = function(fun) {
    return (function(recurse) { return recurse(recurse); })
       (function(recurse) { return function(x) { 
           return fun(recurse(recurse))(x); }; });
};

Y neatly packages the recursive function application into one single closure; the function that is returned on line 3 above. The difference from the previous example is that we have separated the function fun that does the specific computation (factorial in our example below) from the function that does the recursive application (recurse). It should also be noted that this definition of Y is limited to recursive functions that take one argument.

Y is used with functions that have this form:

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

And here is how to call it:

alert(Y(factorial)(9));

Y can (as far as I know) be written in any language that supports higher-order functions and closures. Here is a version in Smalltalk that uses block closures:

y := [:fun | [:recurse | recurse value: recurse] value:
    [:recurse | [:x | (fun value: 
        (recurse value: recurse)) value: x]]].

Example on use (produces a pretty big number):

factorial := [:recurse | [:n | n = 0 
    ifTrue: [1] 
    ifFalse: [n * (recurse value: n - 1)]]].
   
(y value: factorial) value: 5000.

Erlang is a cool functional language, and here goes two variations of Y:

Y = fun(Function) -> 
    (fun(Recurse) -> Recurse(Recurse) end)
    (fun(Recurse) -> fun(X) -> 
        (Function(Recurse(Recurse)))(X) end end) end.

Somewhat simplified with a variable that refers to the recursive function:

Y = fun(Function) -> 
    Go = fun(Recurse) -> fun(X) -> 
        (Function(Recurse(Recurse)))(X) end end,
    Go(Go) end.

And how to use (Erlang too can handle big numbers):

Factorial = fun(Recurse) -> 
    fun(0) -> 1; 
       (N) -> N * Recurse(N - 1) end end.

(Y(Factorial))(5000).

A good way to understand how the above code examples work is to draw diagrams on paper of how the anonymous functions are instantiated and called.

Y Combinator is also the name of a start-up venture firm funded by Paul Graham.