Gosh JS is such a horrible programming language. An identifier can, depending on context, refer to different objects *in the same scope* without being reassigned between references. But I still use JS anyway because I’m too lazy to learn GUI programming for anything else, and the HTML+CSS+JS combo is actually pretty useful because it’s so heavily riced. (Have I mentioned how cool CSS transitions look? Of course I have, and I’ll mention it again: they’re *cool*.) Anyway. I’ve actually written on memoising JS functions before on the old blog, but let’s pretend that never happened, shall we?

So you have a memoisation function that takes a function, and returns a memoised version of that function. This is rather straightforward, though it didn’t immediately occur to me to use JSON.stringify or [].slice because I learnt JS in a time where neither JSON nor Function.prototype.apply existed.

function memoise(f) { var l = {}; return function () { var argstr = JSON.stringify([].slice.apply(arguments)); // f could possibly return undefined so don't just do (l[argstr] !== undefined) and instead check for membership if (!(argstr in l)) l[argstr] = f.apply(this,arguments); return l[argstr]; }; }

Because we like clichéd examples, suppose we want a function to calculate the th Fibonacci number for nonnegative using recursion to implement the recurrence relation and bootstrapping from .

function F(n) { if (n < 2) return n; else return F(n-1) + F(n-2); }

This gives a nonmemoised Fibonacci calculator, which takes time to calculate . (I’m ignoring the fact that it’s not really valid to use big-o notation here because the integers with representable predecessors only go up to 2^{53}, so just leads to the function never halting.) This is terrible, because in the process of calculating the value of is needed, which is also used later in the computation, but the calculation has to be redone because the value is not cached.

F = memoise(F);

It’s memoised, right? Of course it is. So now the first invocation of `F(`

will still take an exponential amount of time, but all subsequent calls will be fast. Yay!`n`)

… Not. This is still terrible, because calling `F`

from outside the original `F`

gives you the “memoised” version, but, for reasons I’m not too sure of, calling `F`

from within the original `F`

gives the original `F`

instead of the memoised one. (I have two hypotheses for the reason, and I’m fairly sure at least one of them is right, but I don’t know which. One is that as the function was defined with a name, the name can only ever refer to itself or a variable within the function. The other is that there’s a distinction between `F`

the variable (which is the memoised function) and `F`

the function (which is the nonmemoised function) and since `F`

is referred to using function call syntax, the function version is used. I’m already confusing myself here, but tl;dr it doesn’t work as expected.) The following is *not* a fix, and exhibits the same behaviour.

var F1 = memoise(function F1 (n) {if (n < 2) return n; else return F1(n-1) + F1(n-2);});

The reason is that this uses a function expression (as opposed to a function statement, as used for `F`

), so the identifier can only refer to the function itself unless it’s shadowed by a variable with the same identifier within the function. On the other hand, the following does work.

var F2 = memoise(function (n) {if (n < 2) return n; else return F2(n-1) + F2(n-2);});

This gives a Fibonacci calculator, and the reason this works is that `F2`

can only possibly refer to the memoised function so there’s nowhere for things to go wrong.

`F2`

has time complexity, but also space complexity because all previous values are cached. (Again, calling attention to the fact that big-o notation is invalid because while real integers use space, JS numerical types have only a finite range and thus can fit in constant space.) In fact, a solution is to just not use recursion at all. Memoisation then becomes optional when you just want one specific Fibonacci number, though the usual benefits of memoisation for nonrecursive functions (more commonly just known as “caching”) apply if you need to call the function multiple times. In practice, you also have to make sure that accessing the cache is not any slower than just recomputing the value.

function F3(n) { if (n < 2) return n; var a = 0, b = 1, c; while (n --> 1) { c = a + b; a = b; b = c; } return b; }

Still time, but only constant space complexity. Can we do better? Of course we can. The powers of have the Fibonacci numbers as entries, so performing exponentiation by repeated squaring gives time, and something similar is used in GMP. This is the best that can be achieved with only integer arithmetic; allowing floating-point arithmetic lets you use Binet’s formula, for a constant-time constant-space algorithm, though you’ll run into accuracy/precision issues.

Anyhow, the above memoisation function is incapable of taking an arbitrary recursive function and making it auto-cache, unless the standard trick of passing the function as one of its own arguments is used. Except that no one does this in JS so `memoise`

can never provide a direct drop-in replacement, in which case you might as well just hard-code the caching in each function.

Python’s `functools.lru_cache`

decorator is a nice example of a memoiser, and it’s somewhat unfortunate that it’s impossible to have this same niceness in JS.