Sunday, November 05, 2006

Memoization: Lisp vs. Ruby

All implementations of memoization below use lexical closures.

Lisp

Common Lisp

Based on Paul Graham's code for memoize (search for memoize) from the book On Lisp, here is a version that also handles functions that return multiple values:
(defun memoize (fn)
(let ((cache (make-hash-table :test #'equal)))
#'(lambda (&rest args)
(multiple-value-bind (val win) (gethash args cache)
(if win
(values-list val)
(let ((val (setf (gethash args cache)
(multiple-value-list (apply fn args)))))
(values-list val)))))))
This works by keeping all the values returned by the function call in a list created using multiple-value-list, inside the cache hash table. The conversion from the stored list to multiple values is done by values-list.

Arc - a new dialect of Lisp

Memoization in Arc by Paul Graham:
(def memo (f)
(let cache (table)
(fn args
(or (cache args)
(= (cache args) (apply f args))))))
As you can see, it is significantly shorter than the Common Lisp one.
Please note, however, that in this case, function calls returning nil are not retrievable from cache, since (cache args) would appear to fail. There is a workaround, involving the use of the *fail* variable: Arc search functions return the value of *fail* upon failure. However, the author assumes that the case of a function call that is computationally intensive only to return nil in the end is so rare that this implementation deliberatly ignores this case and evaluates the function call normally. Thinking about programs that deal with automated theorem proving, program verification or other scientific apps, this assumption may or may not hold a lot of liquid for your purposes. I, for one, would be content with an increase of 1 or 2 in the line count of memoize's definition so that I can forget about this quirk in the implementation that restricts the return value of functions and have it cache everything properly, thereby getting a clean abstraction, just like in the Ruby code below.
But, as always, YMMV.

Ruby

And now for something completely similar, in Ruby-speak:
def memoize(fn)
cache = {}
lambda {|*args|
return cache[args] if cache.has_key?(args)
cache[args] = fn.call(*args)
}
end
It is worth noting that in Ruby, there is no difference between multiple values and Arrays, so no conversion between the two is necessary for storing and retrieving them. This is one reason for which the Ruby version is surprisingly shorter.
Please note that there is an even more elegant (while very similar) implementation of memoize that can optionally cache on disk too, by Daniel J. Berger.