Memoization with a closure example from Land of Lisp

Question

On page 329 of Land of Lisp, Conrad Barski explains the technique of memoization with the following example code

(let ((old-neighbors (symbol-function 'neighbors))
      (previous (make-hash-table)))
  (defun neighbors (pos)
    (or (gethash pos previous)
        (setf (gethash pos previous) (funcall old-neighbors pos)))))

The idea is nice: when I call the neighbors function, I save the result into a hash table, so that the next time calling neighbors with the same value of pos, I can just look-up the result without having to compute it again.

So I was wondering, whether it would not be easier to rename the function neighbors to old-neighbors by editing and recompiling its source code (given on page 314 of the book). Then the memoization example could be simplified to

(let ((previous (make-hash-table)))
  (defun neighbors (pos)
    (or (gethash pos previous)
        (setf (gethash pos previous) (funcall old-neighbors pos)))))

or, by turning previous into a global variable *previous-neighbors* beforehand, even into

(defun neighbors (pos)
  (or (gethash pos *previous-neighbors*)
      (setf (gethash pos *previous-neighbors*) (funcall old-neighbors pos))))

thus rendering the closure unnecessary.

So my question is: what is the reason for doing it this way?

Reasons I could imagine:

1. It's didactical, showing what could be done with a closure (which had been explained just before) and providing an example of symbol-function.
2. This technique is applicable even in situations, where you cannot or may not change the source code of neighbors.
3. I am missing something.

Torino

Answer 1

You have made some good observations.

Generally the style to use closures like that is more likely to be found in Scheme code - where Scheme developers often use functions to return functions.

Generally as you have detected it makes little sense to have a memoize function foo calling an function old-foo. Using global variables reduces encapsulation (-> information hiding), but increases the ability to debug a program, since one can more easily inspect the memoized values.

A similar, but potentially more useful, pattern would be this:

(defun foo (bar)
  <does some expensive computation>)

(memoize 'foo)

Where ˋmemoizeˋ would be something like this

(defun memoize (symbol)
  (let ((original-function (symbol-function symbol))
        (values            (make-hash-table)))
    (setf (symbol-function symbol)
          (lambda (arg &rest args)
            (or (gethash arg values)
                (setf (gethash arg values)
                      (apply original-function arg args)))))))

The advantage is that you don't need to write the memoizing code for each function. You only need one function memoize. In this case the closure also makes sense - though you could also have a global table storing memoize tables.

Note the limitations of above: the comparison uses EQL and only the first argument of the function to memoize.

There are also more extensive tools to provide similar functionality.

See for example:

• https://github.com/fare/fare-memoization

• https://github.com/sharplispers/cormanlisp/blob/master/examples/memoize.lisp

• https://github.com/AccelerationNet/function-cache

Using my memoize from above:

CL-USER 22 > (defun foo (n)
               (sleep 3)
               (expt 2 n))
FOO

CL-USER 23 > (memoize 'foo)
#<Closure 1 subfunction of MEMOIZE 40600008EC>

The first call with arg 10 runs three seconds:

CL-USER 24 > (foo 10)
1024

The second call with arg 10 runs faster:

CL-USER 25 > (foo 10)
1024

The first call with arg 2 runs three seconds:

CL-USER 26 > (foo 2)
4

The second call with arg 2 runs faster:

CL-USER 27 > (foo 2)
4

The third call with arg 10 runs fast:

CL-USER 28 > (foo 10)
1024

Rexrexana

Reading a bit further, I came across an idea similar to the approach you suggest in Paul Graham's On Lisp, Figure 5.2. But I find your version easier to use, because one needs to call (memoize 'foo) (foo 10) whereas the other one would be called with something like (setq fast-foo (memoize 'foo)) (funcall fast-foo 10) Are there any further differences apart from this and using equal instead of eql for comparisons? – Rancid