automatic memoization macro

defmemo.lisp

(defun fib (x)
  (if (< x 2) x (+ (fib (- x 2))
                   (fib (- x 1)))))


(time (fib 10))
=> 1x10^4 cycles

(time (fib 20))
=> 1x10^6 cycles

(time (fib 40))
=> 1x10^9 cycles


(defmacro aif (test consequent &optional alternative)
  `(let ((it ,test))
     (if it ,consequent ,alternative)))

(defmacro defmemo (name args &body body)
  `(let ((cache (make-hash-table :test #'equal)))
     (defun ,name ,args
       (aif (gethash (list ,@args) cache)
            it
            (setf (gethash (list ,@args) cache)
                  `(progn ,@body))))))


(defmemo memo-fib (x)
  (if (< x 2) x (+ (memo-fib (- x 2))
                   (memo-fib (- x 1)))))

(time (memo-fib 10))
=> 1x10^4 cycles

(time (memo-fib 20))
=> 3x10^4 cycles

(time (memo-fib 40))
=> 5x10^4 cycles

O(n^2) ->  O(n)