Code for this Chapter

In this chapter we will discuss memoization, a programming technique for cacheing the results of previous computations so that they can be quickly retrieved without repeated effort.  Memoization is fundamental to the implementation of lazy data structures, either "by hand" or using the implementation provided by the SML/NJ compiler.

We begin with a discussion of memoization to increase the efficiency of computing a recursively-defined function whose pattern of recursion involves a substantial amount of redundant computation.  The problem is to compute the number of ways to parenthesize an expression consisting of a sequence of n multiplications as a function of n.   For example, the expression

2*3*4*5

can be parenthesized in 5 ways:

((2*3)*4)*5, (2*(3*4))*5, (2*3)*(4*5), 2*(3*(4*5)), 2*((3*4)*5).

A simple recurrence expresses the number of ways of parenthesizing a sequence of n multiplications:

fun sum f 0 = 0
  | sum f n = (f n) + sum (f (n-1))

fun p 1 = 1
  | p n = sum (fn k => (p k) * (p (n-k)) (n-1)

where sum f n computes the sum of values of a function f (k) with k running from 1 to n.  This program is extremely inefficient because of the redundancy in the pattern of the recursive calls.

What can we do about this problem?  One solution is to be clever and solve the recurrence.  As it happens this recurrence has a closed-form solution (the Catalan numbers).  But in many cases there is no known closed form, and something else must be done to cut down the overhead.  In this case a simple cacheing technique proves effective.  The idea is to maintain a table of values of the function that is filled in whenever the function is applied.  If the function is called on an argument n, the table is consulted to see whether the value has already been computed; if so, it is simply returned.  If not, we compute the value and store it in the table for future use.  This ensures that no redundant computations are performed.  We will maintain the table as an array so that its entries can be accessed in constant time.   The penalty is that the array has a fixed size, so we can only record the values of the function at some pre-determined set of arguments.  Once we exceed the bounds of the table, we must compute the value the "hard way".  An alternative is to use a dictionary (e.g., a balanced binary search tree) which has no a priori size limitation, but which takes logarithmic time to perform a lookup.  For simplicity we'll use a solution based on arrays.

Here's the code to implement a memoized version of the parenthesization function:

local

  val limit = 100
  val memopad = Array.array (100, NONE)

in

  fun p' 1 = 1
    | p' n = sum (fn k => (p k) * (p (n-k))) (n-1)

  and p n =
      if n < limit then
         case Array.sub of
              SOME r => r
            | NONE =>
              let
                  val r = p' n
              in
                  Array.update (memopad, n, SOME r);
                  r
              end
      else
         p' n

end

The main idea is to modify the original definition so that the recursive calls consult and update the memopad.  The "exported" version of the function is the one that refers to the memo pad.  Notice that the definitions of p and p' are mutually recursive!

Lazy evaluation is a combination of delayed evaluation and memoization.  Delayed evaluation is implemented using thunks, functions of type unit -> 'a.   To delay the evaluation of an expression exp of type 'a, simply write fn () => exp.  This is a value of type unit -> 'a; the expression exp is effectively "frozen" until the function is applied.  To "thaw" the expression, simply apply the thunk to the null tuple, ().  Here's a simple example:

val thunk = fn () => print "hello\n"             (* nothing printed *)
val _ = thunk ()                                 (* prints hello *)

While this example is especially simple-minded, remarkable effects can be achieved by combining delayed evaluation with memoization.  To do so, we will consider the following signature of suspensions:

signature SUSP = sig
  type 'a susp
  val force : 'a susp -> 'a
  val delay : (unit -> 'a) -> 'a susp
end

The function delay takes a suspended computation (in the form of a thunk) and yields a suspension.  It's job is to "memoize" the suspension so that the suspended computation is evaluated at most once --- once the result is computed, the value is stored in a reference cell so that subsequent forces are fast.  The implementation is slick.  Here's the code to do it:

structure Susp :> SUSP = struct
  type 'a susp = unit -> 'a
  fun force t = t ()
  fun delay (t : 'a susp) =
      let
          exception Impossible
          val memo : 'a susp ref = ref (fn () => raise Impossible)
          fun t' () =
              let val r = t () in memo := (fn () => r); r end
      in
          memo := t';
          fn () => (!memo)()
      end
end

It's worth discussing this code in detail because it is rather tricky.   Suspensions are just thunks; force simply applies the suspension to the null tuple to force its evaluation.  What about delay?  When applied, delay allocates a reference cell containing a thunk that, if forced, raises an internal exception.  This can never happen for reasons that will become apparent in a moment; it is merely a placeholder with which we initialize the reference cell.   We then define another thunk t' that, when forced, does three things:

  1. It forces the thunk t to obtain its value r.
  2. It replaces the contents of the memopad with the constant function that immediately returns r.
  3. It returns r as result.

We then assign t' to the memo pad (hence obliterating the placeholder), and return a thunk dt that, when forced, simply forces the contents of the memo pad.  Whenever dt is forced, it immediately forces the contents of the memo pad.  However, the contents of the memo pad changes as a result of forcing it so that subsequent forces exhibit different behavior.  Specifically, the first time dt is forced, it forces the thunk t', which then forces t its value r, "zaps" the memo pad, and returns r.  The second time dt is forced, it forces the contents of the memo pad, as before, but this time the it contains the constant function that immediately returns r.  Altogether we have ensured that t is forced at most once by using a form of "self-modifying" code.

Here's an example to illustrate the effect of delaying a thunk:

val t = Susp.delay (fn () => print "hello\n")
val _ = Susp.force t                             (* prints hello *)
val _ = Susp.force t                             (* silent *)

Notice that "hello" is printed once, not twice!  The reason is that the suspended computation is evaluated at most once, so the message is printed at most once on the screen.

The constructs for manipulating lazy data structures provided by the SML/NJ compiler may be explained in terms of suspensions.  For the sake of specificity we'll consider the implementation of streams, but the same ideas apply to any lazy datatype.

The type declaration

datatype lazy 'a stream = Cons of 'a * 'a stream

expands into the following pair of type declarations

datatype 'a stream_ = Cons_ of 'a * 'a stream
withtype 'a stream = 'a stream_ Susp.susp

The first defines the type of stream values, the result of forcing a stream computation, the second defines the type of stream computations, which are suspensions yielding stream values.  Thus streams are represented by suspended (unevaluated, memoized) computations of stream values, which are formed by applying the constructor Cons_ to a value and another stream.

The value constructor Cons, when used to build a stream, automatically suspends computation.  This is achieved by regarding Cons e as shorthand for Cons_ (Susp.susp (fn () => e).  When used in a pattern, the value constructor Cons induces a use of force.   For example, the binding

val Cons (h, t) = e

becomes

val Cons_ (h, t) = Susp.force e

which forces the right-hand side before performing pattern matching.

A similar transformation applies to non-lazy function definitions --- the argument is forced before pattern matching commences.  Thus the "eager" tail function

fun stl (Cons (_, t)) = t

expands into

fun stl_ (Cons_ (_, t)) = t
and stl s = stl_ (Susp.force s)

which forces the argument as soon as it is applied.

On the other hand, lazy function definitions defer pattern matching until the result is forced.  Thus the lazy tail function

fun lstl (Cons (_, t)) = t

expands into

fun lstl_ (Cons_ (_, t)) = t
and lstl s = Susp.delay (fn () => lstl_ (Susp.force s))

which a suspension that, when forced, performs the pattern match.

Finally, the recursive stream definition

val rec lazy ones = Cons (1, ones)

expands into the following recursive function definition:

val rec ones = Susp.delay (fn () => Cons (1, ones))

Unfortunately this is not quite legal in SML since the right-hand side involves an application of a a function to another function.  This can either be provided by extending SML to admit such definitions, or by extending the Susp package to include an operation for building recursive suspensions such as this one.  Since it is an interesting exercise in itself, we'll explore the latter alternative.

We seek to add a function to the Susp package with signature

val loopback : ('a susp -> 'a susp) -> 'a susp

that, when applied to a function f mapping suspensions to suspensions, yields a suspension s whose behavior is the same as f(s), the application of f to the resulting suspension.  In the above example the function in question is

fun ones_loop s = Susp.delay (fn () => Cons (1, s))

We use loopback to define ones as follows:

val ones = Susp.loopback ones_loop

The idea is that ones should be equivalent to Susp.delay (fn () => Cons (1, ones)), as in the original definition and which is the result of evaluating Susp.loopback ones_loop, assuming Susp.loopback is implemented properly.

How is loopback implemented?  We use a technique known as backpatching.   Here's the code

fun loopback f =
    let
        exception Circular
        val r = ref (fn () => raise Circular)
        val t = fn () => (!r)()
    in
        r := f t ; t
    end

First we allocate a reference cell which is initialized to a placeholder that, if forced, raises the exception Circular.  Then we define a thunk that, when forced, forces the contents of this reference cell.  This will be the return value of loopback.  But before returning, we assign to the reference cell the result of applying the given function to the result thunk.  This "ties the knot" to ensure that the output is "looped back" to the input.   Observe that if the loop function touches its input suspension before yielding an output suspension, the exception Circular will be raised.

Code for this Chapter