Memoization: general purpose function from On Lisp

[Edward Kenworthy]

Hi All

Dice of Doom uses hand-crafted memoisation to improve performance.

Thought others might be interested in this general purpose memoization function which returns a closure that you use in place of the original function.

(defun memoize (fn) ;; the value returned from this function is the memoized version (a closure) of the given function fn.

(let ((cache (make-hash-table :test #’equal))) ;; First it create the cache (which will be wrapped as the closure that gets returned)

#’(lambda (&rest args) ;; define the memoized function (note we just treat the arguments to the function as a lump

(multiple-value-bind (val win) (gethash args cache) ;; gethash returns multiple values: val is the value found and win is true if the key was found

;; can't rely on val being nul to indicate the key not being found as nul is a valid value

(if win ;; if the key is found in the cache...

val ;; ...return the cached value...

(setf (gethash args cache) ;; ...otherwise invoke the original function, store the returned value in the cache and return the value.

(apply fn args)))))))

It's a general purpose function than will wrap any given function with memoization and return the wrapped function. No need explicitly save the original function as it gets wrapped in a closure- and the hash is performed on the whole set of args- so no need to hold multiple dimensions of hash.

This is why Lisp is so cool- and of course only works for functions with no side-effects ;)

This comes from Paul Graham's OnLisp- inadequate commentary by me.

Enjoy

[Conrad]

Thanks Edward- The reason I didn't use a function like this in the
book is because there's some subtleties in how keys are compared in
the hash that makes the general function not usable when infinite,
lazy data structures are involved. That's why I had to write custom
memoization functions in DOD, I believe (I think I discuss this
somewhat in the relevant chapter.)

[Edward Kenworthy]

Hi Conrad

I haven't read that far yet- I'd just assumed you'd kept it simple as you'd just introduced memoization.

As part of my own learning process I've been extreme-re-writing DoD as Draughts ( Checkers ) and went looking for a more general memoization method. I expected a macro but was surprised to find this function.

Edward