Javscript closure questions

Question

While I was reading the book Javascript: The Good Parts. I can not understand the piece of code bellow:

We can generalize this by making a function that helps us make memoized functions. The memoizer function will take an initial memo array and the fundamental function. It returns a shell function that manages the memo store and that calls the fundamental function as needed. We pass the shell function and the function's parameters to the fundamental function:

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;
};

We can now define fibonacci with the memoizer, providing the initial memo array and fundamental function:

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

My question is what is the test function? When does it get defined and invoked? It seems very confusing to me. Also I think this statement: memo[n] = result; is useless. Please correct if I am wrong.

Answer 1

The statement memo[n] = result; stores the newly-calculated number in the memoization array or cache. The test function is an argument to the function to be memoized and is defined and passed by the memoizer. When called, it checks whether the value to be calculated has already been cached. If so, it returns it from the cache. Otherwise it recalculates it again.

After all the above code is executed, we get something like this in memory (but with the memo array and orig_fibonacci encapsulated):

var memo = [0, 1];

function fibonacci(n) {
  var result = memo[n];
  if (typeof result != 'number') {
    result = orig_fibonacci(n);
    memo[n] = result;
  }
  return result;
}

function orig_fibonacci(n) {
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Answer 2

This was a fun code snippet to read :)

You probably know that memoization is storing the result of a function, so that next time the function is called, it doesn't have to compute the answer, it can just look it up.

So we need to store answers for the fibonacci function that takes an int and returns an int.

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

Calls memoizer with an initial memo array, mapping fib(0)->0 and fib(1)->1.

The rest defines an unnamed function that takes a function and a number. 'test' is a bad name for it, it should be "recursive_fibonacci_helper" :)

This unnamed function becomes the "fundamental" parameter. The memoizer function returns a function (shell) that takes an int argument. This eventually becomes the fibonacci function.

So when someone says "fibonacci(5)". They're really calling "shell(5)". The important part about closures is that "fundamental" and "memo" are already bound.

So what does 'shell' do?

It looks up in the memo table to see if it has already computed an answer for this input. If it sees an answer (== 'number') then it returns it. Otherwise it calculates it and stores it in the memo table. memo[n] = result is actually storing the computed result in the memoization table.