Memoizing Fibonacci in Common Lisp

memo-fib.lisp

; the hashtable is found on the binding stack

(defmacro memo (v e &aux (§v (gensym "V")))
  `(locally (declare (special *mem*))
     (let ((*mem* (or (and (boundp '*mem*) *mem*)
                      (make-hash-table)))
           (,§v ,v))
       (declare (special *mem*))
       (or (gethash ,§v *mem*)
           (setf (gethash ,§v *mem*) ,e)))))

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


; slightly improved 

(defmacro memo (sym v e
                &aux
                (§v (gensym "V"))
                (§f (gensym "F"))
                (§mem (gensym (format nil "MEM-~a" (symbol-name sym)))))
  `(locally (declare (special ,§mem))
     (let ((,§v ,v))
       (flet ((,§f () ,e))
         (cond ((and (boundp ',§mem) (gethash ,§v ,§mem)))
               ((boundp ',§mem)
                (setf (gethash ,§v ,§mem) (,§f)))
               (t (let ((,§mem (make-hash-table)))
                    (declare (special ,§mem))
                    (setf (gethash ,§v ,§mem) (,§f)))))))))



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