Another stop on the long road to JavaScript understanding from a C# developers perspective.

This time we really look at what it means to say that functions are not only objects, but *first-class objects* in JavaScript.

Over this series I've constantly declared functions using function expressions instead of function statements. For example, I've used:

var isFiniteNumber = function(value) { return ((typeof value === "number") && isFinite(value)); };

instead of this:

function isFiniteNumber(value) { return ((typeof value === "number") && isFinite(value)); };

There is no real difference between the two (if you like, the second declaration is compiled as the first), but the reason for doing so is that I wanted to emphasize that a function is merely another kind of object. The second declaration, as a *function declaration*, looks like a C# method and in reading it you might fall into the trap and just treat it like a method, somehow fixed and immutable and locked to a class. Functions in JavaScript are *not* like that.

Let's investigate "functions as objects" using a recursive function. Here's a factorial function written recursively, rather than, say, iteratively.

var factorial = function(value) { if (value <= 1) { return 1; } return value * factorial(value - 1); }; console.log(factorial(5));

Looks simple enough (and do note that I've removed a bit of parameter error checking for simplicity): if the value is 0 or 1, return 1, otherwise return the value times the factorial of the value minus 1.

But note one thing in particular: the function refers to itself. Well, duh, of course it does, that's what recursion means. But, remember, functions are objects, so I can do this:

var factorial = function(value) { if (value <= 1) { return 1; } return value * factorial(value - 1); }; var anotherFactorial = factorial; console.log(anotherFactorial(5));

Think about what this code is now doing. Executing `anotherFactorial`

is going to call `factorial`

; however it is not recursive in and of itself. It'll still work though, so let's really gum up the works:

var factorial = function(value) { if (value <= 1) { return 1; } return value * factorial(value - 1); }; var anotherFactorial = factorial; factorial = undefined; console.log(anotherFactorial(5));

Crash: `factorial`

is not a function. Note that `anotherFactorial`

still is a function: it's the original code for `factorial`

. It's just that `factorial`

no longer exists.

This, to put it mildly, is annoying: since any named function object can be thought of as transient, we can't really reference the function name in the body of the function. If you like, the function code is an anonymous object that we can assign to whatever variable we like. How can we write a recursive anonymous function? It needs to refer to itself after all, and since it's *anonymous,* that's a little difficult. Let's see how we can.

The best idea is to pass in the recursive anonymous function as a parameter, for then we can name it. The idea we're going to explore is to create a function that can make a factorial function.

var makeFactorial = function(recurse) { return function(value) { if (value <= 1) { return 1; } return value * recurse(value - 1); }; };

OK, take this slowly. We're defining a function called `makeFactorial`

. It takes a recursive function called `recurse`

as a parameter and it returns another function. This other function takes a single parameter called `value`

and that returns the factorial of `value`

, providing `recurse`

works properly. You'd call it like this

var factorial = makeFactorial(someFunction); var result = factorial(5);

Or, in one line:

var result = makeFactorial(someFunction)(5);

In other words, execute `makeFactorial`

on `someFunction`

to return another function, which is immediately executed with parameter 5. But what is `someFunction`

? Well, it's certainly the factorial function in some sense and the only way we know how to get that with this code is to use `makeFactorial`

.

Somehow.

The problem is that `makeFactorial`

is a function accepting another function, not a function accepting a single numeric value. So the only way we could write this would be:

var makeFactorial = function(recurse) { return function(value) { if (value <= 1) { return 1; } var factorial = recurse(recurse); return value * factorial(value - 1); }; }; var factorial = makeFactorial(makeFactorial); var result = factorial(5); // result === 120

Wow, this is getting tautological, and definitely recursive. What does `makeFactorial`

do now? It still takes a function and returns another, that much is clear. The returned function, when executed, will call the original passed in function, passing in itself. That returns a function which we then execute and bingo it produces the factorial result via a recursive call.

It's instructive to pause here in our discussion and work out what happens when this code is executed. First of all the outer `factorial`

variable is set to the result of calling `makeFactorial`

on itself. So, if you like, the outer `factorial`

will be set to:

var outerFactorial = function(value) { if (value <= 1) { return 1; } var factorial = makeFactorial(makeFactorial); return value * factorial(value - 1); };

We then call it passing in 5. The first thing that happens is that we check the value to be less than or equal to 1 (it isn't) and then we set the inner factorial variable to:

var factorial2 = function(value) { if (value <= 1) { return 1; } var factorial = makeFactorial(makeFactorial); return value * factorial(value - 1); };

This is the second factorial function we've created, so for clarity I've labeled it with a 2. Still in the outer factorial function, we now call that inner factorial function, `factorial2`

, passing in 4. The first thing `factorial2`

does is to check the value passed in to be 1 or less, and then to call `makeFactorial`

on itself (the third time):

var factorial3 = function(value) { if (value <= 1) { return 1; } var factorial = makeFactorial(makeFactorial); return value * factorial(value - 1); };

and then it calls this third factorial function.

This recursion continues until we get to the fifth level. This time the factorial function is not created, since we can return 1. We then unwind the stack, passing return values back and doing all the multiplications until we reach the outer function again, to give the result 120. (Notice in all of this, how much we owe to function closures.)

Seems pretty good, apart from one fact: we make a reference to `makeFactorial`

as a parameter the first time it's called. So we're still self-referencing. All right, let's remove it.

var factorial = function(maker) { return function(value) { if (value <= 1) { return 1; } var factorial = maker(maker); return value * factorial(value - 1); }; }(function(maker) { return function(value) { if (value <= 1) { return 1; } var factorial = maker(maker); return value * factorial(value - 1); }; }); var result = factorial(5); // result === 120

OK, before you freak out, all I've done is to replace `makeFactorial(makeFactorial)`

with the actual code for `makeFactorial`

, and if you look closely, you can see the call parentheses surrounding the second function declaration. Although it's a ruddy mess, it still works. (I also took the opportunity to rename the passed-in recursive function `maker`

, since it's a function that makes another.)

But, note there's no longer a `makeFactorial`

anywhere. We've created an anonymous function that's recursive; albeit at the expense of some pretty horrible duplicated code. Let's clean it up.

First is to clean up the bit that does the factorial calculation (it'll be easier to understand what's going on if the body of the returned factorial function is one line):

var factorial = function(maker) { return function(value) { return (value <= 1) ? 1 : value * maker(maker)(value - 1); }; }(function(maker) { return function(value) { return (value <= 1) ? 1 : value * maker(maker)(value - 1); }; }); var result = factorial(5); // result === 120

Now we should extract this duplicate code somehow, without naming things again.

First a lemma, as we say in mathematics. Using an anonymous function, we can write

f(value);

(that is, calling `f`

with a parameter `value`

) like this:

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

We're declaring an anonymous function that takes a single parameter. The function returns the value of `f`

applied to that parameter. So, overall, it's equivalent, although not something I recommend you do in normal JavaScript programming.

Back to the problem. We'd like to extract this function somehow:

var F = function(value) { return (value <= 1) ? 1 : value * maker(maker)(value - 1); };

But we're left with this awful `maker(maker)`

thing. We can use our lemma to convert it:

var F = function(value) { return (value <= 1) ? 1 : value * (function(x){return maker(maker)(x);})(value - 1); };

Applying the lemma yet again, this time making the internal anonymous function (`(function(x){return maker(maker)(x);})`

) a parameter, we get:

var F = function(mm) { return function(value) { return (value <= 1) ? 1 : value * mm(value - 1); }; }(function(x){return maker(maker)(x);});

That is, `F`

is set to the result of calling an anonymous function taking a single parameter, and the result of that function looks pretty much like a factorial function.

Nearly there! My next step is going to remove the parameter of this expression and create a function I'm going to call `genFactorial`

, because it's going to generate the actual recursive factorial function in a moment:

var genFactorial = function(mm) { return function(value) { return (value <= 1) ? 1 : value * mm(value - 1); }; };

I can now do some substituting into my "cleaned-up" function declaration above:

var factorial = function(maker) { return genFactorial(function(x){return maker(maker)(x);}); }(function(maker) { return genFactorial(function(x){return maker(maker)(x);}); }); var result = factorial(5); // result === 120

Nice, it still works. The next step is to generalize this a little bit. I'm going to declare a new function that can take the `genFactorial`

function as a parameter and produce the factorial function as we just wrote it:

var Y = function(generator) { return function(maker) { return generator(function(x){return maker(maker)(x);}); }(function(maker) { return generator(function(x){return maker(maker)(x);}); }); };

And then we can easily create the factorial function as follows:

var factorial = Y(genFactorial); var result = factorial(5); // result === 120

That's it. We can delete `genFactorial`

with impunity after creating `factorial`

if we so wish, and `factorial`

will continue to work because the current value of `genFactorial`

will have been saved due to the closure inside the function `Y`

. We have created a recursive function for calculating factorials without self-referencing the function name.

Along the way we created this rather bizarre function called `Y`

that can convert any specially-written generator function to produce a recursive function. This `Y`

function that we derived from first principles is better known as the *Y combinator*, and is well-known in functional programming circles (as well as being a Venture Capital investor and owner of Hacker News). I call it bizarre because just by looking at the finished result, it's hard to understand how it actually works; you have to go through the derivation as we did to get a better comprehension. The Y combinator was originally derived by American mathematician Haskell Curry (after whom we have the functional language called Haskell and the process known as *currying*) using lambda calculus.

As a further example of the usefulness of the Y combinator, here's the generator function for a Fibonacci number (we assume `fib(0) === 1`

, and `fib(1) === 1`

, and `fib(n) = fib(n-2) + fib(n-1)`

):

var genFibonacci = function(mm) { return function(value) { if (value === 0) return 1; if (value === 1) return 1; return mm(value - 2) + mm(value - 1); }; }; var fib = Y(genFibonacci); var result = fib(7); // result === 21

Notice that none of this exploration into lambda calculus would have worked if JavaScript did not support functions as first-class objects (that is, functions can be passed as parameters to other functions, and functions can be returned from functions).

Next time in our journey, we'll look at something a little simpler.

Now playing:

Terry, Blair and Anouchka - **Ultra Modern Nursery Rhymes**

(from *Ultra Modern Nursery Rhymes*)

## 2 Responses

## Dew Drop - Weekend Edition - April 11-12, 2009 | Alvin Ashcraft's Morning Dew said...

Pingback from Dew Drop - Weekend Edition - April 11-12, 2009 | Alvin Ashcraft's Morning Dew

## Anthony Mills said...

It's hard to believe I read through that and you didn't mention arguments.callee at all! Sure, the Y combinator is neat, but I think arguments.callee is more useful. And easier to understand.

## Leave a Response