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
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.
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