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:
- It's didactical, showing what could be done with a closure (which had been explained just before) and providing an example of
symbol-function
. - This technique is applicable even in situations, where you cannot or may not change the source code of
neighbors
. - I am missing something.
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 functionold-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:
Where ˋmemoizeˋ would be something like this
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/sharplispers/cormanlisp/blob/master/examples/memoize.lisp
https://github.com/AccelerationNet/function-cache
Using my
memoize
from above:The first call with arg
10
runs three seconds:The second call with arg
10
runs faster:The first call with arg
2
runs three seconds:The second call with arg
2
runs faster:The third call with arg
10
runs fast: