This post makes use of places. If you are unfamiliar with places, see my post Getting Places.

There are many cases where caching the results of a function (also called memoization), make a function much more efficient. For example a function that calculates the Fibonacci numbers:

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

If you try running fib on different values, you will notice that around 35 or so, it starts to take quite a long time to run. The problem is that fib calculates the smaller Fibonacci numbers many more times than it needs to. When calculating the 35th Fibonacci number, the second Fibonacci number is calculated a total of 5702887 times.¹

This is where memoization comes in. If the above function were memoized, it would only need to calculate each Fibonacci number once. Then, whenever fib is asked to calculate a number it has already calculated, it can just look up the result in the table. Here is what the above code would look like if it were to take advantage of memoization:

(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))))))))

With the memoized version, you will hit a stack overflow before you find a value that takes more than a moment to calculate. The problem with the above implementation is that it has some duplicate code. There are two calls made to gethash. The first call checks to see if the value has already been calculated. If not, fib calculates the value manually, and then uses the second call to store it into the table. The fact that the gethash call is repeated may not seem like a problem, but when the expression for the place is more complicated, it can become a much bigger deal.

Or= is a macro that fixes this problem. It does so by first checking whether its first argument, which should be a place, has a non-nil value.² If it does, or= will just return that value. Otherwise it evaluates its remaining arguments until one of them evaluates to a non-nil value. Or= will then write the value of that expression into the place designated by the first argument. Here is the above code rewritten to use or=.

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

The implementation of or= looks very similar to the incf template³ that is used when writing a macro that works with places. Here is the implementation of or=:

(defmacro or= (place &rest args)
  (multiple-value-bind 
        (temps exprs stores store-expr access-expr) 
      (get-setf-expansion place)
    `(let* (,@(mapcar #'list temps exprs)
            (,(car stores) (or ,access-expr ,@args)))
       ,store-expr)))

This time, the value being stored to the place is the or of the place and whatever other arguments are passed in. Since or evaluates its arguments lazily, we get the desired behavior of or= evaluate the expression (and store the result) only if the place doesn’t have a value already. One problem with or= is that it determines if a value has already been stored in the place by testing if the value is non-nil. This can lead to a problem if the value stored in the place is actually nil! As an exercise, try writing a version of or= that takes advantage of the multiple values returned by gethash in order to properly handle nil.

In my next post, I am going to continue with the memoization example and demonstrate how to write a macro defmemo, which makes it easy to define memoized functions.

1. It will be calculated F(n-1) times. 5702887 is just the 34th Fibonacci number.
2. Effectively determining whether the value has already been calculated.
3. That sounds like a macro.