y-combinator.js

/**
 * DERIVING THE Y COMBINATOR IN 7 EASY STEPS
 *
 * Ionut G. Stan  |  ionut.g.stan@gmail.com  |  http://igstan.ro  |  http://twitter.com/igstan
 *
 *
 * The Y combinator is a method of implementing recursion in a programming
 * language that does not support it natively (actually, it's used more for
 * exercising programming brains). The requirement is the language to support
 * anonymous functions.
 *
 * I chose JavaScript for deriving the Y combinator, starting from the definition
 * of a recursive factorial function, using a step-by-step transformation over
 * the initial function.
 */



/* STEP 1
 *
 * The initial implementation, using JavaScript's built-in recursion mechanism.
 */
var fact = function (n) {
    if (n < 2) return 1;
    return n * fact(n - 1);
};



/* STEP 2
 *
 * What would be the simplest thing to do to obtain basic recursivity? We could
 * just define a function which receives itself as an argument and calls that
 * argument with the same argument. That's an infinite loop of course:
 *
 *     (function (f) {
 *         f(f);
 *     })(function (f) {
 *         f(f);
 *     });
 *
 * Let's use the above pattern for our factorial function. There is however a
 * small difference. The factorial function receives an argument which we don't
 * know yet, so what we want is to return a function which takes that argument.
 * That function can then be used to compute factorial numbers. Also, this is
 * what makes our implementation to not result into an infinite loop.
 */
var fact = (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);
    };
})(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 3
 *
 * At this point we have some ugly duplication in there. Let's hide it away into
 * a helper function called "dupe"
 */
var dupe = function (f) {
    return f(f);
};

var fact = dupe(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 above version is that double function call. We want to
 * eliminate it so that the implementation of this factorial is similar with
 * the recursive version. How can we do that?
 *
 * We can use a helper function that takes a numeric argument and performs the
 * double call. The trick is though to keep this helper function in the same
 * environment where "f" is visible, so that "g" can actually call "f".
 */
var dupe = function (f) {
    return f(f);
};

var fact = dupe(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 above works nice, but the definition contains so much clutter code. We
 * could hide it away in yet another helper function, keeping almost just the
 * definition of factorial.
 */
var dupe = function (f) {
    return f(f);
};

var ext = function (h) {
    return dupe(function (f) {
        var g = function (n) {
            return f(f)(n);
        };

        return h(g);
    });
};

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



/* STEP 6
 *
 * Let's inline the definition of "g" inside "ext" because we only call it once
 */
var dupe = function (f) {
    return f(f);
};

var ext = function (h) {
    return dupe(function (f) {
        return h(function (n) {
            return f(f)(n);
        });
    });
};

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



/* STEP 7
 *
 * Now, if we also inline the definition of the "dupe" function inside "ext" we
 * end up with the famous 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!
 */