Ericpony's Blog: Deriving the Y Combinator in Javascript

Wednesday, February 5, 2014

Deriving the Y Combinator in Javascript

A fixpoint combinator is a higher-order function that computes a fixed point of other functions. Fix-point computation is essential in the theory of programming languages, because it allows the implementation of recursion in the form of rewrite rules, without explicit support from the language's runtime engine. Fixpoint combinators are also used to show that typed lambda calculus is Turing complete, which is an important result in the theory of computation that provides a theoretical foundation for functional programming.

The Y combinator is one of the many fixpoint combinators in lambda calculus. These fixpoint combinators implement recursion without requiring a function to call itself. The requirement, though, is that the language supports anonymous and call-by-name functions. If you want to use this in a strict call-by-value language, you will need in addition the related Z combinator; otherwise the Y combinator derived here will lead to an infinite call stack.

Three derivations of fixpoint combinators are introduced in this post:

Derivation based on the Fixpoint Theorem

Let $D$ be a chain-complete partially ordered set (abbr. ccpo) and $FIX$ be a fixpoint operator for Scott continuous function on $D$. Hence, if $g:D\rightarrow D$ is Scott continuous then $FIX(g)$ is the least upper bound of chain $\{g^n(\perp):n\ge0\}$. The fact that operator $FIX$ is well-defined follows from the Kleene Fixpoint Theorem, see here or [2] for more details. It turns out that the property $g(FIX(g))=FIX(g)$ of a fixpoint suffices to characterize the computation of $FIX$:

function FIX(g) = { return function(x){ g(FIX(g))(x); } }

This function effectively finds a fixpoint of functional $g$ if there exists one. Note the return value is eta-abstracted so as to avoid infinite recursion due to strict evaluation. By exploiting a construct called the U combinator, we can eliminate explicit recursion from the definition of $FIX$ (see here for a step-by-step example of recursion elimination using the U combinator) and obtain

function FIX(g) { 
    return (function(h) { return h(h,g); })
    (function (h,g) { 
        return function(x) { return g(h(h,g))(x); }
    }) 
}

Now fix a function $f$ on non-negative integers. Let $f_m$ be a partial function such that $f_m(n)=f(n)$ for $0\le n \le m$ and $f_m(n)=\perp$ otherwise. Suppose that $g$ is a functional such that $g(f_m)=f_{m+1}$ for all $m\ge0$. Since $g$ is Scott continuous on chain $\{f_m:m\ge0\}$, it follows from the Fixpoint Theorem that $FIX(g)$ exists and $FIX(g)=\bigsqcup \{f_m\}=f$. For example, if $f$ is the factorial function and $g$ is

function g(f) { return function(n) { return n<=1 ? 1 : n*f(n-1); } }

then $FIX(g)(n)=f(n)=n!$ for $n=0,1,2,...$.

An ad hoc derivation of the Y combinator

In the following, I shall start from an ordinary recursive factorial function, apply transformations over the initial function, eliminate the recursive structure step by step, and derive the Y combinator in the end. A recursive factorial function is

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

Now consider a function, denoted by makeFact, that takes a factorial function as parameter and generates another factorial function that "unwind" the computation of factorial for one step:

function makeFact (fact) {
    return function(n) {
        if(n<2) return 1; else return fact(n-1)*n;
    }
}

Here we have makeFact(fact)(n) = fact(n). It seems that we cannot use makeFact to generate factorial without already having a factorial function at hand. However, it turns out that makeFact does not really need a factorial function. Given that makeFact takes a factorial function and returns a factorial function, the following function will take makeFact as input and generates a factorial function:

function createFact (makeFact) {
    var fact = function(n) { return makeFact(fact)(n); }
    return fact;
}

Instead of using a factorial function, createFact uses a function that generates a factorial function to generate another factorial function, ie., createFact(makeFact)(n) = fact(n). Thus it avoids the need of a predefined factorial function. However, the definition of variable fact (in the function body of makeFact) is recursive, since it needs to call itself to compute the return value. Such a reference can be avoided if we define another function that makes the reference for it:

function createFact (makeFact) {
    var genFact = function() {
        var fact = function(n) { return genFact()(n); };
        return makeFact(fact);
    };
    return genFact();
}

Now, the definition of fact is not recursive, but we have a new function genFact that refers to itself. This reference can be made via a parameter, rather than calling the function directly:

function createFact (makeFact) {
    var genFact = function(genFactRef) {
        var fact = function(n) { return genFactRef(genFactRef)(n); };
        return makeFact(fact);
    };
    return genFact(genFact);
}

Now, all the functions (ie. genFact and fact) declared in the function body of createFact are non-recursive. We proceed to show that the declarations can be further eliminated and the result is a version of the famous Y combinator. First, we avoid declaring fact by making it an anonymous function:

function createFact (makeFact) {
    var genFact = function(genFactRef) {
        return makeFact(function(n) { return genFactRef(genFactRef)(n) });
    };
    return genFact(genFact);
}

Also, we use an anonymous helper function function(f){ return f(f) } to return genFact(genFact), avoiding the need of declaring genFact:

function createFact (makeFact) {
    return function(f){ return f(f); }(function(genFactRef){
        return makeFact(function(n){ return genFactRef(genFactRef)(n) });
    });
}

Now we reach a function which has no declarations, only parameters. By renaming the parameters to general names, we call this function the Y combinator (for single-parameter functions):

function Y (rec) {
    return function(f){ return f(f) }(function(f) {
        return rec(function(x) { return f(f)(x) });
    });
} // In untyped lambda calculus: Y = λf.(λx.x x) (λx.f (x x))

Take a close look at the definition of Y. It uses only three kinds of expression: anonymous functions, variable reference and function application. It also makes no explicit reference to an outside variable or to itself. The Y combinator allows a concise transformation from a recursive function to a non-recursive function. For example, we can use the Y combinator function to define non-recursive factorial function and a Fibonacci function. To compute factorial,

Y(function(f) { return function(n) { return n<2 ? 1 : n*f(n-1); }})

To compute Fibonacci number,

Y(function(f) { return function(n) { return n<=2 ? 1 : f(n-1)*f(n-2); }})

Finally, if you need a Y combinator for functions that takes more than one argument, you can use Javascript's built-in argument object to obtain all the arguments indefinitely:

function Y(rec) {
    return function(f) { return f(f) }(function(f) {
        return rec(function() { 
            return f(f).apply(null, arguments) 
        });
    });
}

An ad hoc derivation of the U combinator

The Y combinator it not the only way to eliminate recursive calls from a program. The U combinator also does the job, and it is much simpler than the Y combinator. The derivation of the U combinator is also more intuitive and straightforward, at least for those who are comfortable with currying. The ease of derivation, however, comes at the cost that the input function of the U combinator has to make self-application explicit, which may make the user program (which is the factorial function here) look more artificial.

First note that a reference to function itself can be provided to the function as a parameter, avoiding the self reference:

function fact0(f,n) { 
    return n<2 ? 1 : n*f(f,n-1);
}

Hence we have fact0(fact0, n) = fact(n). If we define a function U as

function U(f,n) { return f(f,n); }

then U(fact0, n) yields fact(n). Here we reach a function with two inputs, but we are looking for a combinator that should take only one input. Can we work around this problem? Well a smart guy by the name of Haskell Curry has a neat trick: if you have good higher-order functions then you only need functions of one variable. The proof is that you can get from functions of two (or more in the general case) variables to one variable with a purely mechanical text transformation called currying. For example, by currying f(x,y) we can obtain a function g such that g(x)(y) = f(x,y):

var f = function(x,y) { ... } // original
var g = function(x) { return function(y) { return f(x,y) } } // curried

Now we just apply this transformation in the right places to get our final version of the U combinator.

function fact0(f,n) { // fact0(fact,n) = fact(n)
    return n<2 ? 1 : n*f(n-1);
}
function fact0(f) { // curried, now fact0(fact0)(n) = fact(n)
    return function(n) { return n<2 ? 1 : n*f(f)(n-1); } 
}
function U(f,n) { // U(fact0,n) = fact(n)
    return f(f)(n);
}
function U(f) { // curried, reaching the famous U combinator λf.(f f)
    return function(n) { return f(f)(n); }
}
function U(f) { // allowing an arbitrary number of parameters
    return function() {
        return f(f).apply(null, arguments); 
    }
}

One can check that U(fact0)(n)=fact(n), where U(fact0) can be expanded to

U(function(f) { return function(n) { return n<2 ? 1 : n*f(f)(n-1); }})

References

1. Many faces of the fixed-point combinator: This web page also describes in detail the fix-point combinators for mutual recursion, called poly-variadic fixpoint combinators. It derives the simplest combinator I've seen so far.
2. Semantics with Applications: An Appetizer, Section 5.2.
3. Fixed-point combinators in JavaScript: Memoizing recursive functions
4. Also check Y combinators on Rosetta Code, and many other fixed-point combinators on Wiki.

Ericpony's Blog