memoization


What is Memoization?

Memoization is storing the result of a particular calculation, so that the next time the result is needed, instead of performing the calculation again, the stored result is taken instead.

Where memoization can be useful is for costly, but pure functions: the result for a set of input values is stored in some kind of map (association list, hash table, ...) to allow for a cheaper mapping to the result in subsequent calls than by reevaluation of the function. This is spending memory to save computation time, so the decision has to be taken wisely of course.

Two side notes:

  1. A result can also be kept and reused explicitely, for example by simply keeping it as a binding (a variable), maybe feeding it into the next iteration or recursion of an algorithm. For example, the fibonacci calculation can be rewritten from a naive (binary) recursion that doesn't reuse the result of fib(n-2) for the calculation of fib(n-1) to one that does. Such programming determines the path from the inputs to the usage of the result statically; no search has to be done at runtime. Usually this is not termed memoization.
  2. Promises, the objects returned from delay forms, store the result of the forced calculation internally; this *is* generally termed memoization, but this is from an implementor's point of view (the implementor of the delay and force infrastructure), not a user's. On the outside, it doesn't give anything over the statically determined reuse of results mentioned in the first note above to implement memoization; the only thing it gives is lazy evaluation. Lazy evaluation can be helpful by itself to rewrite algorithms to reuse results statically (by calculating series as streams and picking out values in a separate step, instead of iterating directly), but as mentioned above this is not usually termed memoization. See also delayed-computation

How to do it?

You could use memoization right inside of your particular piece of code, like so: (using the procedure-static-variables idiom.)

 (define memo-do-expensive-computation 
   (let ((memos '())) 
     (lambda args 
       (apply values 
              (cond ((assoc args memos) => cdr) 
                    (else 
                     (call-with-values 
                       (lambda () 
                         (apply do-expensive-computation args)) 
                       (lambda results 
                         (set! memos 
                               (cons (cons args results)  
                                     memos)) 
                         results)))))))) 

However, scheme is a first-class functional language after-all, and there is no reason why you should be restricted to inserting this code into every function you need memoized. It's very straightforward to implement a general memoization procedure which takes a non-memoized procedure as input and returns the memoized version of it. Below we use srfi-44? style map rather than an alist to store the memoized results.

 (define (memoize function) 
   (let ((table (make-equal?-map))) 
     (lambda args 
       (apply values 
              (map-get table 
                       args 
                       ;; If the entry isn't there, call the function.    
                       (lambda () 
                         (call-with-values 
                           (lambda () (apply function args)) 
                           (lambda results 
                             (map-put! table args results) 
                             results)))))))) 

Discussion

The important thing about this memoization, is that it should only be used with pure functions (i.e. referentially-transparent) -- functions that map every input to exactly one output, performing no side effects. For instance, the function (lambda (x) (+ x x)) is because if I feed it the number 23, I will always get 46 in return. But this function is not:

 (lambda (x)  
   (begin  
     (set! *some-global* (+ x *some-global*)) 
     *some-global*)) 

If I feed it 5 the first time, I might get 5, but the next time I feed it 5 I might get 10, 15, or even 29872691!

This dependancy on referential transparency for consistant memoized results can be used to debug a memoization logo design system that you are building. Build yourself a test function like this:

 (define (test-function x) 
   (display "IN test-function, arg x") 
   (+ x x)) 

Then when you memoize this function, you should see the display statement execute once for every new value of x, but on already used values of x, you shouldn't see the display.

For more information referentially-transparent functions, and how to program them, see: functional-programming


category-code