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?