In my last post I talked about memoization i.e. caching the results of a function. Memoization is a fairly common technique for optimization. It is common enough to warrant writing a macro that makes it easy to define memoized functions. When demonstrating memoization, I had a memoized Fibonacci function that looked like this:¹

(let ((table (make-hash-table)))
  (defun fib (n)
    (or (gethash n table)
        (setf (gethash n table)
              (if (<= 0 n 1)
                  n
                  (+ (fib (- n 1))
                     (fib (- n 2))))))))

There are a couple problems with the above code. One problem is the boilerplate. If you wanted ten different memoized functions, you would have to copy lines 1, 3, and 4 for every single memoized function. Some people like to call programmers who do this needless duplication, human compilers, since they are writing code that the compiler should be writing for them.

Another issue with the above code is the lack of abstraction. If you wanted to change the caching mechanism to say, only cache the last hundred values, you would have to change the definition of every single function! Ideally you would only need to modify the code in one place in order to change how the caching is implemented.

Defmemo is one way to solve both of these problems. Here is what the above code would look like if it were were to use defmemo:

(defmemo fib (n)
  (if (<= 0 n 1)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

Defmemo solves both of the problems extremely well. It removes all of the differences between the memoized version on the regular version except for having to use defmemo instead of defun. Defmemo also solves the abstraction problem by moving all of the code relevant to memoization into the body of defmemo. If you want to change how memoization works, all you have to do is change the code for defmemo.

Now for the implementation of defmemo. The implementation is made up of two separate parts. First, a higher order function, memo, which takes a function as an argument, and returns a memoized version of that function. The second part is the actual macro, defmemo. Instead of just defining the function like defun, defmemo first builds a lambda expression for the body. Then it generates code that calls memo on that lambda function. Finally defmemo uses the result of memo as the implementation of the function being defined.²

Here is the code for memo:³⁴

(defun memo (f)
  (let ((cache (make-hash-table :test #'equalp)))
    (lambda (&rest args)
      (or (gethash args cache)
          (setf (gethash args cache)
                (apply f args))))))

Memo works by returning a function that has an internal hash-table. When that function is called, it first checks its hash-table to see if it has been called with the same arguments before. If so, it returns the value it had calculated the first time it was called.⁵ If it hasn’t been called with the same arguments before, the function will instead call the function that was passed in to memo, and then store the result of that inside the table. This way, if the memoized function is called with the same arguments a second time, it can just look up the result in the table.

Next, for defmemo itself, we need to generate code that takes the body as a lambda expression, passes that lambda function through memo, and uses that as the implementation of the function. One way to set the implementation of a function to be a lambda function is to use setf with symbol-function.⁶ For example, here is how you could set the implementation of square to be a lambda function that squares its argument:

(setf (symbol-function 'square) (lambda (x) (* x x)))

(square 5) => 25

Based on the paragraph above, here is the code for defmemo:

(defmacro defmemo (name args &body body)
 `(setf (symbol-function ',name) 
        (memo (lambda ,args ,@body))))

Now instead of defining a function with defun, we can define it with defmemo and it will automatically be memoized! Defmemo is a great example of how you can define your own ways to define functions. Many libraries provide similar features in which you use the same syntax as defun, only with a bit of magic thrown in.

1. Alternatively you could use or=, but in order to keep the code in this post pure Common Lisp, I am leaving it out.
2. If you are experienced with Python, you should be able to see what we are doing. The function memo is effectively a decorator and defmemo is just a way of applying it.
3. You could also use or= so you don't have to call gethash multiple times.
4. There is a problem with the code below, when the result being stored is nil. The code determines if it has been called before by checking if the value in the hash-table is non-nil. Instead it should do this check by looking at the second value returned by gethash.
5. The logic for this is expressed concisely in the code through or. Or evaluates its first argument. If it is non-nil it returns it. Otherwise it continues with the remaining arguments.
6. Another way is to use setf with fdefinition which not only works on symbols, but setf functions as well.