Memoizing recursive JavaScript functions (without mentioning fixed-point combinators or lambda calculus)

This is me attempting to decode this.

The problem

Let's say you've got a function of one argument. Basic Fibonacci sequence. Recursive, calls itself. Returns an integer.

var fibo = function(n) {
  return n == 0 ? 0 :
         n == 1 ? 1 :
         fibo(n-1) + fibo(n-2);
};

alert("fibo(32) = " + fibo(32)); // Takes a little while

Is there a way to create a new function which is identical but automatically caches answers before it returns them? Let's say, for simplicity of implementation, that the argument can always be used as the index in an object, which means that a simple object cache can be used to cache the results from the function.

Then there sure is. For example, we could manually create a wrapper function fibo_caching:

var fibo = function(n) {
  return n == 0 ? 0 :
         n == 1 ? 1 :
         fibo(n-1) + fibo(n-2);
};

var fibo_caching = function(n, cache) {
  if(!cache[n]) {
    cache[n] = fibo(n);
  }
  return cache[n];
};

var cache = {};
alert("fibo_caching(32, cache) = " + fibo_caching(32, cache)); // Takes a little while
alert("fibo_caching(32, cache) = " + fibo_caching(32, cache)); // Runs instantly on the second call

In fact, creating a caching version of any function f can be done programmatically:

var fibo = function(n) {
  return n == 0 ? 0 :
         n == 1 ? 1 :
         fibo(n-1) + fibo(n-2);
};

var cachify = function(f, cache) {
  return function(n) {
    if(!cache[n]) {
      cache[n] = f(n);
    }
    return cache[n];
  };
};

var cache = {};
var fibo_caching = cachify(fibo, cache);

alert("fibo_caching(32) = " + fibo_caching(32)); // Takes a little while
alert("fibo_caching(32) = " + fibo_caching(32)); // Runs instantly on the second call

Notice how both implementations of fibo_caching seen so far take just as long as fibo to compute the 32nd Fibonacci number straight off. This is because they both drop through to fibo, which in and of itself does NOT populate cache while calculating, nor does it examine cache for quick answers.

The problem is recursion. fibo calls itself internally. It's perfectly straightforward to manually rewrite fibo into a function which is itself recursive and caches results, like so:

var fibo_caching = function(n, cache) {
  if(!cache[n]) {
    cache[n] = n == 0 ? 0 :
               n == 1 ? 1 :
               fibo_caching(n-1, cache) + fibo_caching(n-2, cache);
  }
  return cache[n];
};

var cache = {};
alert("fibo_caching(70, cache) = " + fibo_caching(70, cache)); // Very fast even on the first call
alert("fibo_caching(70, cache) = " + fibo_caching(70, cache)); // Instantaneous on the second call

However, there is no way to rewrite fibo into fibo_caching programmatically. There is no way to automatically replace instances of "fibo(...)" inside the body of fibo with instances of "fibo_caching(...)". At least, not without resorting to ugly string replacement nonsense.

The solution

The solution is this. Step 1: make a slight modification to our basic Fibonacci function, so that's it's no longer explicitly recursive:

var fibo_useless = function(g, n) {
  return n == 0 ? 0 :
         n == 1 ? 1 :
         g(n-1) + g(n-2);
};

var fibo = function(n) {
  var g = fibo;
  return fibo_useless(g, n);
}

alert("fibo(32) = " + fibo(32)); // Still slow

Make sure it's clear to you what is going on here. Our new base function fibo_useless, on its own, is useless. It cannot actually generate Fibonacci numbers without being supplied with the correct value of g every time. But fibo can "enable" fibo_useless by always providing the correct g to pass into it. The value of g is always fibo itself.

This "enablement" can be accomplished programmatically for any suitably prepared function f:

var fibo_useless = function(g, n) {
  return n == 0 ? 0 :
         n == 1 ? 1 :
         g(n-1) + g(n-2);
};

var enable = function(f) {
  return function(n) {
    var g = enable(f);
    return f(g, n);
  };
};

var fibo = enable(fibo_useless);

alert("fibo(32) = " + fibo(32)); // Still exactly equally slow

Step 2: make some slight tweaks to enable, effortlessly turning it into cachify:

var fibo_useless = function(g, n) {
  return n == 0 ? 0 :
         n == 1 ? 1 :
         g(n-1) + g(n-2);
};

var cachify = function(f, cache) {
  return function(n) {
    if(!cache[n]) {
      var g = cachify(f, cache);
      cache[n] = f(g, n);
    }
    return cache[n];
  };
};

var cache = {};
var fibo_caching = cachify(fibo_useless, cache);

alert("fibo_caching(70) = " + fibo_caching(70)); // Very fast on the first call
alert("fibo_caching(70) = " + fibo_caching(70)); // Instantaneous on the second call

Anyway, I believe the above is equivalent to the final example given in the original article, and about four times more readable. For example, I un-inlined quite a lot of functions, un-curried fibo_useless, and replaced the equivalent of

var g = function(arg) {
  return cachify(f, cache)(arg);
};

with

var g = cachify(f, cache);

which is - correct me if I'm wrong - the same thing. Fixed-point combinators (oops!) are complicated enough without code obfuscation.

The same caveats about cachify only supporting single-argument functions and indexable arguments still apply.

Please let me know if the Y combinator was used anywhere in the above.

Update

I guess the main reason for using

var g = function(arg) {
  return cachify(f, cache)(arg);
};

over

var g = cachify(f, cache);

is lazy evaluation. In the first case, the call cachify(f, cache) doesn't get evaluated until the first time that g itself is called. g is called almost immediately almost every time in this example, though.

Oh, and there is just one more thing

This whole song and dance is pointless if you don't mind simply replacing the original, unmodified fibo function with its memoized equivalent:

// No special preparation needed whatosever
var fibo = function(n) {
  return n == 0 ? 0 :
         n == 1 ? 1 :
         fibo(n-1) + fibo(n-2);
};

var cachify = function(f, cache) {
  return function(n) {
    if(!cache[n]) {
      cache[n] = f(n);
    }
    return cache[n];
  };
};

var cache = {};
fibo = cachify(fibo, cache);

alert("fibo(70) = " + fibo(70)); // Super fast on the first call
alert("fibo(70) = " + fibo(70)); // Instantaneous on the second call

So yeah, who needs advanced lambda calculus and fixed-point combinators when the above (1) works perfectly and (2) is transparently simple in its operation? In fact, what use is the Y-combinator at all? Any?

Back to Code
Back to Things Of Interest

Facebook Twitter Reddit Email Hacker News StumbleUpon

Discussion (15)

2011-09-07 22:42:53 by hpc:

> var fibo_useless = function(g, n) {
> return n == 0 ? 0 :
> n == 1 ? 1 :
> g(n-1) + g(n-2);
> };
>
> var fibo = function(n) {
> var g = fibo;
> return fibo_useless(g, n);
> }

The way you wrote fibo is one way of using Y. In Haskell, the analogous code for the above would be

> fib = fix \fib n -> if n < 2 then n else fib (n - 1) + fib (n - 2)

Your last example, in broken side-effectful Haskell, would be

> cachify f cache n =
> fix \rec -> do
> unless (n `elem` cache) $ do
> cache n $= f rec n
> return $ cache n

2011-09-07 22:44:01 by hpc:

Apparently I can't indent my code? You can see the indentation if you view source.

2011-09-07 22:47:56 by hpc:

So sorry, I just keep forgetting things...

The trick to the above code is that in "fix \f -> ...", f = "fix \f -> ...".

In code like "f = blahblah f blah", you can trivially rewrite it as "f = fix \f -> blahblah f blah". With that in mind, fixed-point code is a lot easier to read.

2011-09-08 01:29:18 by Artanis:

There is a way to rewrite fibo() programmatically into the caching function. In fact, you were halfway there with cachify() and fibo_caching().

1. Write your fibonacci function as normal, referencing itself for recursion (the first implementation is perfect).
2. Write a function that takes a function, and returns a function that caches the results of the first function.
3. Call the caching function with the fibonacci function as it's argument, and (this is important) assign the new function to the fibonacci variable.

Now, references to the fibonacci function (even from inside the fibonacci function) call the caching function, and if you write the caching function correctly, this is effectively transparent.

For example, https://gist.github.com/1202231

Now, you'll probably tell me I missed the point entirely. I don't particularly care, since I got to port one of my favorite Python decorators to JavaScript, which was quite fun.

2011-09-08 19:11:45 by Jason:

I'm the jpadvo from HN who asked for a clearer explanation of that article. You knocked this one out of the park -- thank you for helping me understand. :)

All the best!

- Jason

2011-09-09 14:06:50 by Sam:

Thanks for that, Artanis. You've shown that the emperor has no clothes. Fixed point combinators are evidently wholly unnecessary for this purpose, and memoization is trivially simple to automate!

2011-09-09 22:30:04 by AWood:

A fixed point combinator is only useful when you're in a language that doesn't have variable assignment, so you can't use the magic of variables.
The lambda calculus is a good example (the only things you can name there are arguments).

Useful in proofs, and it looks elegant, but not so practical (unless you happen to love using a language like unlambda for instance).

2011-09-10 08:49:32 by Artanis:

As for a practical example, there's a question on that over at Stack Overflow (http://stackoverflow.com/questions/869497/y-combinator-practical-example). The accepted answer asserts that there are practical applications, but holds that they are difficult to find, and for example/proof links a to paper on the subject.

Which is incomprehensible to me, so you'll have to look at that yourself.

2011-10-06 01:11:25 by Broney:

I was once asked during an interview to write code for the Fibonacci function.

I wrote
var fibo = function(n) {
return floor(pow(sqrt((1+sqrt(5))/2),n)/sqrt(5) + 0.5);
};

They just kind of looked at me dumbfounded.

2011-10-15 20:24:35 by Artanis:

If it's any comfort, I'd have hired you on the spot.

2011-10-19 07:45:25 by William:

Broney: While that's clever mathematically, it only works up to 70 or so before you run into floating-point precision problems.

2011-12-11 00:14:19 by theractwentyfive:

I wrote a post about this, also taking fibonacci as an example:
http://fallen.nfshost.com/Therac25/?p=394

2011-12-11 00:29:52 by zorg:

As Awood noted, nobody pretends that the Y combinator is essential to memoize recursive functions, since most languages have mutable variables.
It is a beautiful artefact of CS theory worth studying for folks suitably inclined.

2012-01-27 09:45:41 by David:

The trick here is that you’re using side-effects. It’s not possible to use your approach if the original function and the caching version don’t share the same scope.

2012-07-23 23:41:30 by RangerMauve:

Hey, why not just store the cache within the fibo function?
All functions in Javascript are also objects and you can add parameters to them as you would to any other object.

function fibo(n){
if(!fibo["cache"])
fibo["cache"] = [];
if(fibo.cache[n])return fibo.cache(n);
ans = (n == 0 ? 0 : n == 1 ? 1 : fibo(n-1) + fibo(n-2));
fibo.cache[n]= ans;
return ans;
}

This way the whole function is fully contained.