(defun memo (fn) (let (alist) #'(lambda (x) (let ((result (assoc x alist))) (cond ((null result) (setq result (funcall fn x)) (setq alist (cons (cons x result) alist)) result) (t (cdr result)))))))このmemo関数にfibを渡して記憶型のfibを定義することができる.
> (setq fib-memo (memo #'fib)) ... > (funcall fib-memo 4) 0: (FIB 3) 1: (FIB 2) 2: (FIB 1) 2: returned 1 2: (FIB 0) 2: returned 1 1: returned 2 1: (FIB 1) 1: returned 1 0: returned 3 0: (FIB 2) 1: (FIB 1) 1: returned 1 1: (FIB 0) 1: returned 1 0: returned 2 5このfib-memoを実行してもfib自体が変更されていないために, トップレベルの実行結果のみしか蓄積されない. そこでfib-memoをfib本体として定義してしまえば良い.
> (setf (symbol-function 'fib) fib-memo) #<Function FIB @ #x900a76> > (fib 5) 0: (FIB 5) 1: (FIB 4) 1: returned 5 1: (FIB 3) 1: returned 3 0: returned 8 8 > (fib 6) 0: (FIB 6) 1: (FIB 5) 1: returned 8 1: (FIB 4) 1: returned 5 0: returned 13 13このようにfibが下請けの計算をいちいちせずに関数を用意している ことがわかる.