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)
Loading links to posts on similar topics...
2 Responses
#1 Dew Drop - Weekend Edition - April 11-12, 2009 | Alvin Ashcraft's Morning Dew said...
11-Apr-09 7:44 PMPingback from Dew Drop - Weekend Edition - April 11-12, 2009 | Alvin Ashcraft's Morning Dew
#2 Anthony Mills said...
22-Oct-10 12:09 PMIt'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
Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.
_emphasis_**strong**[text](url)`IEnumerable`* an item1. an item> Now is the time...Preview of response