メモ化再帰: symbol-function を使う方法

Elispで再帰的関数をメモ化する方法の続き。

Y Combinator による方法のほかにも、symbol-function を使って関数定義を書き換える方法がある。

symbol-functionを使ったメモ化再帰の例（Elisp）

(defun memo (fn name key test)
  "Return a memo-function of fn."
  (lexical-let ((_fn fn) (_key key) (table (make-hash-table :test test)))
    #'(lambda (&rest args)
        (let ((k (funcall _key args)))
          (if (gethash k table)
              (gethash k table)
            (setf (gethash k table) (apply _fn args)))))))
=> memo

(defun* memoize (fn-name &key (key #'first) (test #'eql))
  "Replace fn-name's global definition with a memoized version."
  (setf (symbol-function fn-name)
        (memo (symbol-function fn-name) fn-name key test)))
=> memoize

;;; フィボナッチ数列で試す
(defun fib (n)
  (if (<= n 1) 1
    (+ (fib (- n 1)) (fib (- n 2)))))
=> fib

;;; 実行時間をはかる関数
(defun profile (func &rest args)
  (let ((start (current-time)))
    (apply func args)
    (time-to-seconds (time-subtract (current-time) start))))
-> profile

;;; メモ化なしの場合の実行時間
(profile 'fib 25)
=> 0.124392

;;; fibをメモ化する
(memoize 'fib)
=> (lambda (&rest --cl-rest--) (apply (lambda (G90287 G90288 G90289 &rest args) (let ... ...)) (quote --table--) (quote --_key--) (quote --_fn--) --cl-rest--))

;;; メモ化した場合の実行時間
(profile 'fib 25)
=> 0.000166

ちなみにこの方法は、"Paradigms of Artificial Intelligence Programming" というCommon Lispの本に載っていた（9.1 Caching Results of Previous Computations: Memoization）。そのプログラムを、 defun*, lexical-let等を利用してEmacs Lisp 用に調整しただけ。

参考

• Paradigms of Artificial Intelligence Programming