Elisp Memoize

Memoization is something I think should be packaged as a standard function for just about every language. That's not generally the case, but luckily this is easy to fix in Lisps. I needed memoization recently for an Elisp project I'm working on. I could have hand-written one but a generic memoization function would have worked just fine. Since I didn't find any generic Elisp memoization on-line I wrote my own.

Download: memoize.el

Just put it in your path and (require 'memoize) it. Here's the core function.

;; ID: 83bae208-da65-3e26-2ecb-4941fb310848
(defun memoize-wrap (func)
  "Return the memoized version of FUNC."
  (lexical-let ((table (make-hash-table :test 'equal)))
    (lambda (&rest args)
      (let ((value (gethash args table)))
        (if value
            value
          (puthash args (apply func args) table))))))

The hash table is stored inside the fake closure provided by lexical-let. In a previous version of this function, I stored it in an uninterned symbol, which is what is going on behind the scenes of lexical-let.

Note that in the full code it keeps the original function documentation intact. I want the memoization wrapper to be an unobtrusive as possible.

Here's a demo of it in action. This whiten function is computationally expensive: it performs key whitening. It repeats a hash function thousands of times to produce an expensive value. This isn't something you generally want to memoize, but stick with me.

(defun whiten (key)
  "Perform key whitening with the md5 hash function."
  (dotimes (i 100000 key)
    (setq key (md5 key))))

(whiten "password")   ; takes a couple of seconds

On my laptop that takes a couple of seconds to run. Increase that counter if it's quick on your computer. My memoize package provides a memoize function which will create a new function that wraps the original, then installs the new function in place of the old one if we give it the function symbol.

(memoize 'whiten)

The first time you run it after memoization it will be slow, but after that the memoization kicks in for a quick return.

There are two Elisp specific issues at hand. First is that memoizing an interactive function will produce a non-interactive function. It would be easy to fix this problem when it comes to non-byte-compiled functions, but recovering the interactive definition from a byte-compiled function is more complex than I care to deal with. Besides, interactive functions are always used for their side effects so there's no reason to memoize them.

Second is a limitation of Elisp hash tables. There's no way to distinguish a nil value and no value. The hash table returns nil for both. This means you cannot memoize nil returns. But a computationally expensive function shouldn't be returning nil anyway.

Update: As of August 2012, me and several other people have gotten good mileage out of this function! It's an essential part of my Emacs dotfiles.

• emacs
• elisp