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.
Just put it in your path
(require 'memoize) it. Here's the core
;; 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
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
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.
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.blog comments powered by Disqus