Functional JavaScript – Memoization, Part I

Introduction

I recently attended Neal Ford’s functional thinking presentation at COJUG. Neal aims to introduce functional programming concepts to traditional developers. Neal covered a lot of ground but for now I want to focus on one aspect of his presentation: memoization.

Memoization

A key concept of functional programming is a function’s result is solely determined by its inputs. A function called with the same inputs produces the same result every time. The result is not determined by some transient state not captured by the inputs.

Since the same inputs are always mapped to the same result then we can cache the result in a key/value map and return the result from the cache, if present, instead of calling the function. In the case of a cache miss we would call the function with the inputs and insert the result into the cache. Such function result caching is called memoization. Memoization is a useful technique for functions that are called repeatedly with the same set of inputs but whose result is relatively expensive to produce.

Higher-Order Functions

Functions are first-class objects in functional languages. This means functions can be assigned to variables, passed as inputs to other functions and so on. The ability to provide a function as an input to another function allows us to create higher-order functions. When we say ‘provide a function as an input’ we’re talking the function itself, not the result of the function applied to some set of inputs. You simply can’t do such things in non-functional languages.

We can do some pretty amazing things by combining the ability to provide a function implementation as the input to another function with the ability to generate functions at runtime as needed, via function generators. One of those things is creating a higher-order memoization function generator. We can create a memoized version of a function as needed at runtime and then use the memoized version wherever we would have used the non-memoized version. They’re interchangeable.

Function Generator for Creating Memoized Functions

Creating a memoization function generator in JavaScript is simple:

// 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!                                               
   }
}

Analysis

Lines 7-12 is the heart of the implementation. This is the function being generated and returned. This generated function contains a memoizer property containing the cached function results. When this generated function is called it first checks its cache to retrieve the value. In the case of a cache miss it simply calls through to the function f supplied to the function generator and caches the result. In both cases the cached result is returned.

The rest of the implementation is housekeeping. In line 3 we check to ensure f is a function and if not we return f, whatever it was, in line 17. Line 5 checks the number of inputs, or arity, of f. To simplify things we only memoize functions whose arity is 1 (unary functions). There’s an elegant solution for memoizing functions of higher arity that I’ll be demonstrating in a future post.

f is returned in the case where f isn’t a unary function. This is fine since memoize(f) and f are interchangeable functions producing indistinguishable results. The only downside is the caller may believe it’s using a memoized version of the function when it isn’t. The caller can determine whether the function it’s calling is a memoized function by checking for the existence of the function’s memoizer property.

Fibonacci

To demonstrate the powers of memoization we need a function to memoize. This example utilizes a fully-recursive fibonacci sequence generator. The parameter is the 0th—based index of the fibonacci sequence whose corresponding value is to be returned. This is an extremely inefficient implementation thus illustrating the potential computational time savings of memoization.

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

Memoizing Fibonacci

Creating a memoized version of this fibonacci function is simple:

var fn=memoize(fibonacci);

The function fn is the memoized version of the fibonacci function. fn may be invoked in lieu of the fibonacci function like so:

fn(35);

yielding the result 9227465 in 273ms of execution time. Once we’ve retrieved the value once for 35, subsequent invocations for 35 yield the result in 1ms, according to the Google Chrome profiler; which has a minimum resolution of 1ms—so the actual time may be less!

What About Memory Utilization?

Memoization illustrates the classic execution time vs. execution space trade-off. More memory is consumed by caching the results but there’s the potential to save a lot of execution time. If you need to clear the function result cache to free up some memory then simply do the following:

fn.memoizer.values.length=0;

and the cached values will be released.

Insufficient Memoization

The recursive definition of fibonacci may have caused you to wonder whether the intermediate results are cached. They are not. So when computing

fn(35);

we’ve also computed:

fn(34), fn(33), fn(32)…fn(2), fn(1), fn(0)

though none of these interim results are cached. In future posts we’ll consider ways to cache these interim results.

What’s Next

In future posts I’m going to further expand upon the ideas presented here addressing both the memoization of the interim results of recursive functions and memoizing non-unary functions. We’ll even be looking at ways to make the memoization generator function a property of all functions. See you then!

More to Explore

Functional JavaScript — Memoization, Part II
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 I

  1. Pingback: Functional JavaScript – Currying | @taylodl's getting IT done

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