Skip to content
August 6, 2011 / codehost

Fixed Point Combinators in Javascript

I write a lot of Javascript code where I currently work. It’s not for web pages though, but fully fledged clients and servers, using the node.js framework.
That’s how I discovered that Javascript is not a kiddie language at all. Sure, it focuses on simplicity and has syntax similar to Java, but it’s a high-level language with many interesting features.

Functions

Functions in Javascript are “First Class Citizens”. You can pass along functions like variables to call later. They can be anonymous, just like in functional languages, defined and called on the fly. Even closures are built into Javascript.

What I found rather funny was that, as a matter of fact, functions are objects. It gets even better – there are no classes in Javascript. An object can be declared many other ways, one of them as a function – where the properties and methods are variables declared during execution and stay in memory as a closure. Calling the constructor is just calling the function. Sure, there is a new operator, but it’s syntactic sugar.

Fun with functions

I was wondering what fun things can be done in this surprisingly non-trivial language. I thought of messing around with anonymous recursive functions, because I remembered how they were written in Lambda Calculus.

I’ll run along with the Nth Fibonacci Number function. This is how it looks in standard coding style:

function fibo(n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return fibo(n - 1) * fibo(n - 2);
    }
}

Like I said, functions can be assigned to variables, so our function can look like this:

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

Let’s write a function that takes another function as a parameter and calls it. It should be able to take any number of arguments. For this, the arguments object comes in handy. It’s created for every function and acts like an array with all the arguments plus some useful properties, like callee – which is the reference to itself, kind of like this (which also exists in Javascript). Every function has a call method and can be used for calling it. The first argument is the computational context (can also be the instance of an object) and the second argument – an array of parameters to be called with.

function run(f) {
    var args = [];
    for (var i = 1; i < arguments.length; i++)
        args.push(arguments[i]);
    return f.call(this, args);
}

… and run our fibo like this:

var result = run(fibo, 5);

The last thing to try is calling run with an anonymous function. There is no reference to it, so we will use arguments.callee.

var result = run(function(n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return arguments.callee(n - 1) * arguments.callee(n - 2);
    }
}, 5);

It works nicely using node.js, but unfortunately the strict mode of the ES5 standard doesn’t give you access to arguments.callee.

Lambda Calculus

The above examples are not what I had in mind for this article though. I thought of making use of the wonderfully confusing concept of fixed point combinators from the Lambda Calculus. In this theoretical language (in my case polluted with Scheme functions and pseudocode syntax), our fibo routine is written like this:

f \equiv \lambda n. (if\ (n=0\ or\ n=1)\ 1\ (+\ (f\ (-\ n\ 1))\ (f\ (-\ n\ 2))))

… where f is our Fibonacci function. Again, f is a convenience name for it – there is another way to describe recurrence.

Fixed point combinators

Theory
Let F be a functional and f a function. If

(F\ f) = f

then f is called a fixed point of F.
A recursive function is the smallest fixed point of a functional. There exist functionals that take another functional and compute its smallest fixed point. Let’s say one of them is Fix , so that:

(Fix\ F) = (F\ (Fix\ F))

This is the same as saying that (Fix\ F) is our little f . This works for languages with parameters passed by name. Since Javascript passes by value, a small modification in the above equation is needed:

(Fix\ F) = \lambda x.((F\ (Fix\ F))\ x)

Here is the proof that they are equivalent:

\begin{array}{rcl}((Fix\ F)\ a) & = & \lambda x.(((F\ (Fix\ F))\ x)\ a)  \\ & = & ((F\ (Fix\ F))\ a)  \\ \Rightarrow (Fix\ F) & = & (F\ (Fix\ F))  \end{array}

Defining our Fibonacci functional
Now that we have some idea what to do, our F will be:

F \equiv \lambda g. \lambda n. (if\ (n=0\ or\ n=1)\ 1\ (+\ (g\ (-\ n\ 1))\ (g\ (-\ n\ 2))))

Fix will then take care of computing our fibo:

fibo \equiv (Fix\ F) = (F\ (Fix\ F))

Proof
Let’s see what the last equation actually computes.
Case 1: n = 0 or n = 1

\begin{array}{rcl}(fibo\ 0) & = & ((Fix\ F)\ 0) \\  & = & ((F\ (Fix\ F))\ 0) \\  & = & (\lambda n. (if\ (n=0\ or\ n=1)\ 1\ (+\ ((Fix\ F)\ (-\ n\ 1))\ ((Fix\ F)\ (-\ n\ 2))))\ 0) \\  & = & if\ (n=0\ or\ n=1)\ 1\ ... \\  & = & 1  \end{array}

Case 2: n > 1

\begin{array}{rcl}(fibo\ n) & = & ((Fix\ F)\ n) \\  & = & ((F\ (Fix\ F))\ n) \\  & = & (\lambda n. (if\ (n=0\ or\ n=1)\ 1\ (+\ ((Fix\ F)\ (-\ n\ 1))\ ((Fix\ F)\ (-\ n\ 2))))\ n) \\  & = & (+\ ((Fix\ F)\ (-\ n\ 1))\ ((Fix\ F)\ (-\ n\ 2)))) \\  & = & (fibo\ (n - 1)) + (fibo\ (n - 2))  \end{array}

Long story short, this is how recursive functions can be anonymous.

A particular fixed point combinator
There are many fixed point combinators out there. One that suits our needs and is implementable in Javascript is this one:

Fix \equiv \lambda F. (\lambda g.\lambda x.((F\ (g\ g))\ x)\ \lambda g.\lambda x.((F\ (g\ g))\ x))

Javascript implementation

Fix
This is the code for the Fix function. There is no Javascript magic here, only the instruction to instruction translation from Lambda Calculus:

var Fix = function (F) {
    return (function (g) {
        return function (x) {
            return F(g(g))(x);
        };
    })(function (g) {
        return function (x) {
            return F(g(g))(x);
        };
    });
}

Fibonacci functional
The functional F is written in a similar manner, and is pretty much the fibo function from the beginning of the post:

var F = function(f) {
    return function (n) {
        if (n == 0 || n == 1) {
            return 1;
        } else {
            return f(n - 1) + f(n - 2);
        }
    };
}

Fibonacci number
And to compute the actual function, here is the code, followed by a test call:

var fibo = Fix(F);

for (var i = 0; i <= 15; i++) {
    console.log(fibo(i));
}

Conclusion

Obviously all this wasn’t so that we could write neat code using F and fibo as placeholders. We went to great lengths so that by combining run and Fix we could produce:

console.log(run(Fix(function(f) {
    return function (n) {
        if (n == 0 || n == 1) {
            return 1;
        } else {
            return f(n - 1) + f(n - 2);
        }
    };
}), 10));

Well, that would be it. I would really like to step through this code and trace each line, but the debuggers I used were quite cryptic and not much fun. I wonder if this guy could give me a hint since, well, he’s Chuck Norris.

About these ads

2 Comments

Leave a Comment
  1. Martín Ciparelli / Aug 9 2011 06:24

    Ive found it very interesting, and Im currently wondering for a Newton-Raphson implementation to find a fixed point… probably starting to work in one soon.

    • codehost / Aug 9 2011 11:10

      I’m glad you like it :).
      Good luck with your implementation.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: