Memoisation in Emacs Lisp

Memoisation in lisp has a nice implementation; see for example section 9.1 in Norvig's Paradigms of Artificial Intelligence Programming. The idea is of course the same: maintain some data structure such as a hash-table for caching along-side your function, then for each invocation check if an entry already exists in the cache and if so return it, else calculate the result as normal then cache it using the argument(s) as a key before returning. This is particularly useful for functions with a recursive definition, and indeed the poster child is again the fibonacci function, which has a natural definition but horrid run-time:

What makes the lisp implementation particularly attractive is the ability to manipulate the symbol so that you don't need to write your function in any special way, and the memoisation can be added on transparently. For some reason however I haven't found a general implementation of this for emacs lisp (read: googling "elisp memoisation" didn't return much, even after changing it to "memoization" -- surprisingly it didn't prompt me for that spelling change either). Inspired by this comment by Randall Schwartz I decided to try using advice instead of a straight-up port of the symbol-function manipulation that Norvig uses.

The basic idea is we want add some "around" advice, like so:

(Note that you don't return a value, but manipulate "ad-return-value" if you want to set the return value yourself).

The hash table will be stored as a property on the function's symbol, and the advice name is also trivially generated:

Now the original advice can be written generically as a macro:

We can also write a couple of utilities to reset the cache or remove the memoisation entirely:

(Trap for beginners, or at least the sleepy: note that you need to call ad-update to make the changes to advice actually take effect!)

This will only work for functions of one argument.  You can use it like so:

Mark Hepburn 29 May 2010
blog comments powered by Disqus