Imagine you have a recursive pure (side-effect free) function. As the function calls itself with smaller and smaller input arguments as we move down on the recursion tree, there is a big possibility that we calculate and re-calculate the function with the same input over and over again which is wasteful in terms of time, energy and memory.
One good option is to store the results of our calculations in a cache, and then recall them as we traverse the recursion tree. This is done in two different ways:
In dynamic-programming we build our computations ground-up, that is, we start with the base cases and work our way up gradually increasing the input and storing the results of our calculations in a cache. Then we call our recursive function.
In memoization we work our way down. Given an input we check the cache if our function is called with that input. If that is the case we return the cached result. Otherwise we go on making our recursive calculation.
I am a great fan of the second approach. In the past, as you might recall, I employed it successfully in calculating several difficult functions. And, as it happens, it is not that difficult to implement.
I will define a macro mem-defun which you can use to
replace a function definition with a memoized version of the same
function. On the syntactic level, there is no difference. Just replace
defun with mem-defun and it is done.
(defmacro mem-defun (name args body)
(let ((hash-name (gensym)))
`(let ((,hash-name (make-hash-table :test 'equal)))
(defun ,name ,args
(or (gethash (list ,@args) ,hash-name)
(setf (gethash (list ,@args) ,hash-name)
,body))))))
MEM-DEFUNIn the definition I employed a nice trick I learned from someone else a long long time ago, but I fortunately I forgot when and where, about encapsulating a state within a function:
(let ((n 0))
(defun counter () (incf n)))
COUNTERNow, if you call counter back to back, it will do the
right increment. Plus, the variable n is completely
encapsulated within counter.
(counter)
1
(counter)
2It is not very functional of me, but, hey it gets the job done. Neat, isn’t it?
I will use the following function which calculates the number of unordered \(k\)-partitions of an integer \(n\):
(defun par (n k)
(cond ((< n k) 0)
((= n k) 1)
((= k 1) 1)
((= k 2) (if (evenp n) (/ n 2) (/ (1- n) 2)))
(t (+ (par (1- n) (1- k)) (par (- n k) k)))))
PAR
(time (par 125 25))
Evaluation took:
4.039 seconds of real time
4.036252 seconds of total run time (3.980249 user, 0.056003 system)
[ Run times consist of 0.024 seconds GC time, and 4.013 seconds non-GC time. ]
99.93% CPU
14,104,722,285 processor cycles
1,604,091,864 bytes consed
139620591
(mem-defun par (n k)
(cond ((< n k) 0)
((= n k) 1)
((= k 1) 1)
((= k 2) (if (evenp n) (/ n 2) (/ (1- n) 2)))
(t (+ (par (1- n) (1- k)) (par (- n k) k)))))
PAR
(time (par 125 25))
Evaluation took:
0.000 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
100.00% CPU
1,186,483 processor cycles
170,440 bytes consed
139620591Reiner Joswig pointed out that, if a return value for our function to be memoized is `NIL`, the macro I wrote above will fail, and the function will be recomputed. So, if your function has a possibility of returning a NIL, use the version below:
(defmacro mem-defun (name args body)
(let ((hash-name (gensym)))
`(let ((,hash-name (make-hash-table :test 'equal)))
(defun ,name ,args
(multiple-value-bind (val found-p)
(gethash (list ,@args) ,hash-name)
(if found-p
val
(setf (gethash (list ,@args) ,hash-name)
,body)))))))He also pointed me to Norvig’s PAIP, specifically his version a macro doing the same thing and much more [here]. I knew the code, and there are few things I didn’t like about the way he designed the memoization macro. But Norvig’s code is very well-structured and fun to read. I definitely recommend to go through it and the PAIP book for one’s edification.