Functional JavaScript – Memoization, Part II

Introduction

In Part 1 of this series we looked at a simple function generator for memoizing functions. Recall memoized functions are functions that cache their results; once the value is determined for a particular input the value is placed into a cache and subsequent calls to the function using the same input return the previously cached value — thus eliding the function call. Using a fibonacci sequence generator we examined how memoized functions can greatly improve program performance.

Memoizing Recursive Functions

Let’s take another look at the Fibonacci function presented in the previous post:

// retrieve nth fibonacci number from sequence (0-relative)
// recursive solution for fibonacci calculation is not efficient
function fibonacci(idx) {
   if (idx == 0) return 0;
   if (idx == 1) return 1;
   return fibonacci(idx-2) + fibonacci(idx-1);
}

What’s the problem here? Let’s suppose we’ve generated a memoized version of this fibonacci function, called mfibonacci, and we call mfibonacci(10). What’s happening? At a high level we’re going to return

fibonacci(8) + fibonacci(9)

Do you see the problem? We’re not calling memoized versions of our fibonacci function in our recursive generation! In calculating mfibonacci(10) we’ve calculated fibonacci(9), fibonacci(8), fibonacci(7), fibonacci(6), fibonacci(5), fibonacci(4), fibonacci(3), fibonacci(2) and none of these values have been cached. If after calling mfibonacci(10) we were to subsequently call mfibonacci(9), we’d have to start all over again. The fact we’ve already calculated fibonacci(9) while computing mfibonacci(10) has been lost.

This particular implementation of fibonacci compounds the problem:

fibonacci(n) = fibonacci(n-2) + fibonacci(n-1)

When calling mfibonacci(10) both fibonacci(8) and fibonacci(9) are called. We’d like the result of fibonacci(8) to be cached and available when calling fibonacci(9). This implementation of fibonacci was deliberately chosen for this pathological case.

How do we memoize recursive functions?

Re-Thinking Memoize

We need to backtrack a little bit. Previously we used the following function generator for memoizing functions:

// Return a memoizing version of a function f                                                                
function memoize(f) {
   if (f instanceof Function) {
      // only memoize functions of arity 1, otherwise return function                                 
      if (f.length == 0 || f.length > 1) return f;

      var fn = function(x) {
         if (fn.memoizer.values[x] == null) {
            fn.memoizer.values[x] = f.call(f,x);
         }
         return fn.memoizer.values[x];
      };

      fn.memoizer = { values : [] };
      return fn;
   } else {
      return f; // garbage in, garbage out I always say!                                               
   }
}

While this function generator works, it’s less than ideal. To see what’s wrong consider the following contrived scenario:

   memoize(fibonacci)(10);
   memoize(fibonacci)(10);

Here the function generator memoize is creating a new and separate memoized version of fibonacci — each having their own cache! That’s not what we want. Instead we’d like the function’s memoization to be a property of the function itself. This way everyone getting the memoized form of a function are getting the same implementation, and more importantly, the same cached set of values.

It’s extremely useful to make a function’s memoized form a property of the function itself. In JavaScript functions are first-order objects: they can be assigned to variables, stored in properties, passed as function arguments and so forth. There are many ways you can get a reference to a function and it would be convenient to get the memoized form of the function in a uniform way.

How do we do that?

Function Prototype

The solution is to place the memoizer function and the property to the memoized form of the function in the function prototype. Recall that in JavaScript whatever functions and properties exist in the object’s prototype also exist in all instances of the object. You may also recall that in JavaScript all functions are objects — all being instances of the base Function object. Whatever methods and properties we add to Function.prototype will therefore exist for all functions.

We don’t typically think of functions as being objects having methods and properties, but in JavaScript that’s exactly what they are. Now let’s look at how we can add a memoizer and memoized form property to a Function.prototype:

// Return a memoizing version of function                                                                
Function.prototype.memoize = function() {
    // only memoize functions of arity 1, otherwise return function                                      
    if (this.length == 0 || this.length > 1) return this;

    var _this = this,
    _caller = this.caller;

    if (this.memoizer == null) {
        this.memoizer = {
            fn : function(x) {
                if (_this.memoizer.values[x] == null) {
                    _this.memoizer.values[x] = _this.call(_caller, x);
                }
                return _this.memoizer.values[x];
            },

            values: []
        }
    }

    return this.memoizer.fn.wrap(this);
}

As before we only memoize functions whose arity is 1. this refers to the function object being memoized. We’re adding a new memoizer property to the function. The memoizer property is an object having 2 properties:

  1. fn  The memoized form of this function
  2. values  The value cache for the memoized form of this function

The key difference now is memoize is a property of the function instance. Meaning regardless of how many times we call memoize we’re retrieving the same memoized form for the function.

Once we’ve gotten over the fact that functions are objects and may therefore have their own properties and methods, we need to be careful to delegate those properties in the memoized form of the function. That’s what wrap does:

// Wrap an object, pulling wrapped object properties up to wrapper                                       
// so as to make them accessible                                                                         
Object.prototype.wrap = function(o) {
    for (var p in o) {
        if (o.hasOwnProperty(p)) {
            this[p] = o[p];
        }
    }
    return this;
}

We won’t discuss the wrap function any further at this time. We’ll see the importance of wrap in future posts.

Memoizing Fibonacci

Let’s put this all together and generate a fully memoized form of fibonacci:

// retrieve nth fibonacci number from sequence (0-relative)                                              
// memoized solution for fibonacci calculation is very efficient                                         
function fibonacci(idx) {

    if (fibonacci.memoizer == null || !fibonacci.memoizer._fibonacci) {
        var innerFibonacci = function(idx) {
            if (idx == 0) return 0;
            if (idx == 1) return 1;
            return innerFibonacci(idx-2) + innerFibonacci(idx-1);
        }.memoize();
        fibonacci.memoizer = innerFibonacci.memoizer;
        fibonacci.memoizer._fibonacci = true;
    }

    return fibonacci.memoizer.fn(idx);
}

The innerFibonacci is key to the implementation. It’s a function object assigned to a memoized form of an anonymous function implementation of the fibonacci function. The innerFibonacci references within the anonymous function definition refer to this outer innerFibonacci variable being defined. Thus the recursive form is fully memoized.

The second key to this implementation is aliasing the innerFibonacci memoizer with the fibonacci memoizer. It’s our Function.prototype version of memoize that allows us to do this: it created the memoizer property on the function that we can now refer to. When we retrieve the Fibonacci memoizer we’ll actually be retrieving the innerFibonacci memoizer — which is exactly what we want.

Finally, notice how we nonchalantly call the memoize method on the anonymous fibonacci function we’ve created at runtime. Now you should begin to understand that in JavaScript functions are objects and as such may have properties and methods and that these properties and methods not only apply to named functions but anonymous functions as well.

What’s Next

We’ve seen how to create fully memoized forms of recursive functions. In so doing we’ve created a single value cache for a function’s memoized form. Both are vast improvements to where we were at the end of the previous post when we first considered memoization.

We’re still not done with memoization however. We’ve not looked at any aspect of cache management. Currently our memoization cache will grow without bounds. We may need to limit both the size constraints and time constraints of the cache. We may only wish to cache so many values based off frequency of use. We may be dealing with a function that returns different values over time even when provided with the same inputs, meaning we may need to empty the cache when some time limit has been exceeded.

In future posts we’ll look at ways of enhancing our memoize implementation to provide these capabilities. See you then!

More to Explore

Functional JavaScript — Memoization, Part I
Functional JavaScript — Tail Call Optimization and Trampolines
Functional JavaScript — Currying

About these ads

About taylodl

I'm an enterprise architect/developer who enjoys programming, math, music, physics, martial arts and beer
This entry was posted in JavaScript and tagged . Bookmark the permalink.

One Response to Functional JavaScript – Memoization, Part II

  1. Pingback: Memoized Fibonacci Sequence in LISP | mtaylorprogramming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s