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

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

#### Fixed point combinators

**Theory**

Let be a functional and a function. If

then is called a *fixed point* of .

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 , so that:

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

Here is the proof that they are equivalent:

**Defining our Fibonacci functional**

Now that we have some idea what to do, our will be:

will then take care of computing our `fibo`

:

**Proof**

Let’s see what the last equation actually computes.

Case 1: or

Case 2:

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:

#### 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.

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.

I’m glad you like it.

Good luck with your implementation.