On my last post I presented a solution to write the recursive factorial function with anonymous recursive function, but there is a better and more general way to write recursive functions, it is called fix-point combinator and one well-known (and perhaps the simplest) fixed-point combinator in the untyped lambda-calculus is called the Y combinator. It was discovered by Haskell B. Curry, and is defined as:

Translating lambda-calculus to JavaScript is not a easy task because they do not operate in the same way. JavaScript is a practical programming language and lambda-calculus is a theoretical language that is much more close to a simple mechanical operation.

Example:

function add (a, b) { return a + b;}

In lambda-calculus this should be written in JavaScript as:

function add (a) { return function (b) { return (a+b) } }

And execution is like this:

add (1) (2);

Everything in lambda-calculus is mostly functions, and all function are lazy evaluated, this is important when we want to translate lambda-calculus to JavaScript because JavaScript evaluates most of expression early.

# Fixpoint Y-Combinator in JavaScript

This is one of does examples that are much more simple in lambda-calculus that are in JavaScript or maybe I am just misunderstanding the Y fix-point combinator…

Anyway this is what I got:

function Y (f) {return function (x) { return function () { return f ( function () {return x (x);} ) ( function (x) { return function () { return f ( function (x) {return x(x);} ); } } ); } } }

You can see that all functions return a function as result but this is mostly because we don’t want the function to be executed right away, we want to return a function as result and then apply it if necessary, otherwise we will make a infinity function call that would result in stack overflow.

# Writing Factorial with Fixpoint Y-Combinator in JavaScript

The factorial function,

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

Now I need to change the function to work with the Y combinator, something like this:

function fact (self) { return function () { // I think this dummy function is unnecessary // but this is executed with no argument at // initialization and I don't know why... return function (n) { if (n === 0) { return 1; } else if (n > 0) { return (self () (self) (n-1)) * n; } } }; }

Once again I return functions to avoid early execution. The function self is not really the function itself but the function constructed with the Y combinator.

The recursive function is initialized like this:

var factorial = Y (fact) (Y (fact)) (); console.log (factorial (0)); // print 1 console.log (factorial (4)); // print 24

# Putting it all together!

Next code is kind of messy thats why I am wondering if this is the correct way to do it, but it works…

console.log ( function ( Y ) { return function (fact) { return function (factorial) { return "factorial (0) = " + factorial(0) + "n" + "factorial (1) = " + factorial(1) + "n" + "factorial (2) = " + factorial(2) + "n" + "factorial (3) = " + factorial(3) + "n" + "factorial (4) = " + factorial(4) + "n" + "factorial (5) = " + factorial(5) + "n" ; } ( Y (fact) (Y(fact)) () ) } ( function (self) { return function () { return function (n) { if (n === 0) { return 1; } else if (n > 0) { return (self () (self) (n-1)) * n; } } }; } ); } ( function (f) { return function (x) { return function () { return f ( function () {return x (x);} ) ( function (x) { return function () { return f ( function (x) {return x (x);} ); } } ); } } }) );

The output would be

factorial (0) = 1 factorial (1) = 1 factorial (2) = 2 factorial (3) = 6 factorial (4) = 24 factorial (5) = 120

# Other way

When I was playing with fix-points I made a code prototype that actually works, but is much more simple than the code above so something must be wrong,

anyway the code is very simple,

function ( fixpoint ) { return function ( factorial ) { // execute factorial return factorial (4); // return 24 } ( fixpoint (function (fact) { return function (n) { if (n === 0) { return 1; } else if (n > 0) { return fact (fact) (n-1) * n; } } }) ); } ( function fixpoint (f) { return function (x) { return x (x); } ( function (x) { return f (x); } ) } }; )