Y combinator in small steps

The Y combinator is an interesting construct, allowing recursion without referring the function being recursed. In other words, call a function recursively, without naming it. We will go through one approach of deriving it.

This approach mostly follows WhyOfY by Richard P GabrielA somewhat similar approach is followed by James Coglan's blog post.. And watch an interesting talk on it, by Jim Weirich.. We will derive it in JavaScript, in steps. Each step is complete. Click on the 'Edit in JSFiddle' to explore the steps.

Premise & setup

Lets pick a simple example, so we can concentrate on exploring recursion. Given a number, n, return the sum of numbers from 1 to n. To start with, below is a recursive solution for the problem. Individual steps are hosted in JSFiddle, for you to play around.

var sum = function (n) {
    return n === 1 ? 1 : n + sum(n - 1);
};
console.assert(sum(5) === 15, sum(5));

try in fiddle

The process

We have to remove the reference to sum, inside the function, which fortunately leads to the Y combinator. One approach to calling a function, without using its name, is to pass the function as parameter.

var s1 = function (f, n) {
    return n === 1 ? 1 : n + f(f, n - 1);
}
console.assert(s1(s1, 5) === 15);

try in fiddle

We have just moved the function name (reference) from inside the function, to the function call. As a next step, we could pass the function as a curried param.

This helps later, in abstracting the passing of function as parameter, out of the logic for the problem.

var s2 = function (h) {
    return function (n) { // inner function
        return n === 1 ? 1 : n + h(h)(n - 1);
    };
};
console.assert(s2(s2)(5) === 15);

try in fiddle

The double call inside the inner function, is quite irrelevant to the problem of calculating sum. The logic of sum shouldn't know that h(h) gives the next function call. The recursive function should just receive a function, to continue the recursion with. We could abstract that in another function. Ex:

// replace
return function (n) {
    return n === 1 ? 1 : n + h(h)(n-1);
};

// with
return (function(f) {
    return function (n) {
        return n === 1 ? 1 : n + f(n-1);
    };
})(function (n) {
    return h(h)(n);
});

Why not pass h(h) as parameter? Why do we have to wrap it in a function?

Here is the complete version.

var s3 = function (h) {
    return (function (f) { // sum function
        return function (n) {
            return n === 1 ? 1 : n + f(n - 1);
        };
    })(function (n) {
        return h(h)(n);
    });
}
console.assert(s3(s3)(5) === 15, s3(s3)(5));

try in fiddle

In the current version, the function dealing with the sum logic, doesn't have any dependency on context, or specific knowledge about how to get the next function. Lets name it as sum (for the time being). Ex.

var sum = function(f) {
    return function (n) {
        return n === 1 ? 1 : n + f(n-1);
    };
};

This is just so we can see the real changes in code. Here is the recursion with sum.

var sum = function (f) {
    return function (n) {
        return n === 1 ? 1 : n + f(n - 1);
    };
};

var s4 = function (h) {
    return sum(function (n) {
        return h(h)(n);
    });
};
console.assert(s4(s4)(5) === 15);

try in fiddle

To evaluate the recursion, we had to call s4 with itself, ex s4(s4). To not use a name, we would have to abstract it in a function. We can define a function which s4 as parameter, and call it with itself as parameter.

var s5 = (function (f) {
    return f(f);
})(s4);
console.assert(s5(5) === 15);

Expanding the definition of s4 gives.

var sum = function (f) {
    return function (n) {
        return n === 1 ? 1 : n + f(n - 1);
    };
};

var s5 = (function (g) {
    return g(g);
})(function (h) {
    return sum(function (n) {
        return h(h)(n);
    });
});
console.assert(s5(5) === 15);

try in fiddle

We are almost done. Now, we just need to pass the actual function (ex sum in our case) as a parameter. Here is the Y combinator.

var Y = function (fn) {
    return (function (g) {
        return g(g);
    })(function (h) {
        return fn(function (n) {
            return h(h)(n);
        });
    });
};
var sum = function (f) {
    return function (n) {
        return n === 1 ? 1 : n + f(n - 1);
    };
};
console.assert(Y(sum)(5) === 15);

try in fiddle

Or in its inlined form:

((function (fn) {
    return (function (g) {
        return g(g);
    })(function (h) {
        return fn(function (n) {
            return h(h)(n);
        });
    });
})(function (f) {
    return function (n) {
        return n === 1 ? 1 : n + f(n - 1);
    };
}))(5); // => 15

try in fiddle

Explorations

If you would like to think more about this, here are a few thoughts to explore.

1. We have only explored function with single argument. How could we make this work with multiple arguments.

2. Could we come up with a combinator, which doesn't take curried version of sum. Ex a combinator which takes sum defined as function sum(f, n) { return n + f(n-1); } as argument.