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:
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
