Explanation on "JavaScript - the Good Parts" example (section 4.15)?

Question

Beginner in JS :) needs an explanation of code piece from Crockford's book, section 4.15:

var memoizer = function (memo, fundamental) {
    var shell = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fundamental(shell, n);
            memo[n] = result;
        }
        return result;
    };
    return shell;
};

var fibonacci = memoizer([0, 1], function (shell, n) {
    return shell(n - 1) + shell(n - 2);
});

Question: How do we calculate fibonacci(15), and if it is simple fibonacci(15) call, then how it works in detail?

Thanks for help.

Answer 1

Here's a console.log() annotated version which attempts to show how the stack returns and assigns the result of (n-1)+(n-2) to the memo array for each respective recursive call. Also remember that the stack returns in reverse order. So in the logged output you'll see the last call returned first:

var memoizer = function (memo, fundamental) {
    var shell = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fundamental(shell, n);
            console.log("Hence 'shell(n-1)+shell(n-2)' results in the assignment memo["+n+"]="+result);
            memo[n] = result;
        }
        return result;
    };
    return shell;
};
var fibonacci = memoizer([0, 1], function (shell, n) {
    console.log("shell is called, and 'n' is equal to --> " + n + "\n" + "At this point shell(n-1)="+shell(n-1)+" AND shell(n-2)="+shell(n-2));
    return shell(n - 1) + shell(n - 2);    
});

Answer 2

It looks like you're confused about WHY the invocation fibonacci(15) works. Let's simplify the code (forget about memoization for a second).

var m = function () {
    var s = function (n) {
        console.log(n);
    };
    return s;
}; 
var f = m();

Basically we are setting f to the return value of function m(). In this case, that return value is a function. See, we could simplify it further as:

var f = function (n) { console.log(n); };

In other words, we are setting f to be a function that takes in one parameter. We are doing the same thing in the fibinacci example. That is why the invocation fibonacci(15) works.

Answer 3

As the comments to your question suggest, you should walk through the code in a debugger to get a good understanding of what's going if you can't follow the explanation in the book. But I'll give you a brief overview of what's happening:

What's being demonstrated is 'memoisation' which is a common optimisation technique used in functional programming. A function is said to be pure if the result depends only on the arguments passed into it. So, if a function is pure you can cache the result based on the arguments - this technique is called memoisation. You would do this if a function is expensive to calculate and is called multiple times.

The classical example used to demonstrate this (as here) is generating Fibonacci numbers. I'm not going to go through how those are worked out, but basically as you go to higher and higher numbers you repeat yourself more and more as each number is calculated from the preceeding two numbers. By memoising each intermediate result you only have to calculate them once hence making the algorithm much faster (much, much faster as you go higher up the sequence).

As far as this code is concerned the memoizer takes two parameters - 'memo' which is the cache. In this case it's going in with the first two values already filled in the '[0,1]' - these are the first two Fibonacci numbers.

The second parameter is the function to which the memoisation will be applied. In this case a recursive Fibonacci function:

function (shell, n) { return shell(n - 1) + shell(n - 2); }

i.e. the result is the sum of the previous two numbers in the sequence.

The memoizer first of checks to see if it already has a cached result. If it does it returns that immediately. If not it calculates the result and stores it in the cache. Without doing this it'd be repeating itself again and again and rapidly gets impossibly slow once to get to the higher numbers in the sequence.