JavaScript applicative Y combinator

Recently I have been working with JavaScript.
Although JavaScript interpreter does not have to be tail call optimized, and I believe most of them are not, JavaScript have closures and functions are first class objects. Hence it is possible to write in JavaScript applicative Y combinator.

In this short text I will start with a simple recursive factorial function written in JavaScript and by modifying it again and again I will transform the code into two methods Y and F such that Y handles the recursion and F handle the factorial logic.
It is worth to mention that once one have those methods, they can be used without naming (anonymously).

Starting with:


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

The first change is to create a factorial factory and use it instead the direct call.


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

Now instead of factorial(6) we call f()(6).

Next we change the factory method r to receive one argument, this argument will be always a factorial factory itself.


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

Now the call has changed to something like f(f)(6).
When substituting r’s body with r in the call above we have:

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

The next transformation is reverse eta conversion (η-conversion)
 f(f)(n) => function(a){ return  f(f)a}(n), this delays the computation of f(f(n)  and prevent infinite  loop because of the evaluation order in applicative order.


    function(f) {
        return function(n) {
            if (n === 0) {
                return 1;
            } else {
                return n * ((function(a) {
                    return f(f)(a);
                })(n - 1));
            }
        };
    }
    (function(f) {
        return function(n) {
            if (n === 0) {
                return 1;
            } else {
                return n * ((function(a) {
                    return f(f)(a);
                })(n - 1));
            }
        };
    })(6);

Now (function(a) {

                    return f(f)(a);

                })

can be extracted out we will do that by wrapping everything in a new function call with param r and passing it the expression  (function(a) {

                    return f(f)(a);

                })

To the function

    function(f) {

        return function(r) {

            return function(n) {

                if (n === 0) {

                    return 1;

                } else {

                    return n * r(n - 1);

                }

            };

        }(function(a) {

            return f(f)(a);

        });

    }

    (function(f) {

        return (function(r) {

            return function(n) {

                if (n === 0) {

                    return 1;

                } else {

                    return n * r(n - 1);

                }

            };

        })(function(a) {

            return f(f)(a);

        });

    })

Now we do the same with the pink expression and have:

function(m) {

        return function(f) {

            return m(function(a) {

                return f(f)(a);

            });

        }(function(f) {

            return m(function(a) {

                return f(f)(a);

            });

        })(function(r) {

            return function(n) {

                if (n === 0) {

                    return 1;

                } else {

                    return n * r(n - 1);

                }

            };

        });

Hence we have 2 functions

var y = function(m) {

        return function(f) {

            return m(function(a) {

                return f(f)(a);

            });

        }(function(f) {

            return m(function(a) {

                return f(f)(a);

            });

        });

and:

var fact = function(r) {

            return function(n) {

                if (n === 0) {

                    return 1;

                } else {

                    return n * r(n - 1);

                }

            };

        }

and 

y(fact)(6) => 720