9.3 memoizationの追加

Next: 10 構造体とsetf Up: 9 遅延評価(lazy evaluation) Previous: 9.2 遅延評価の一般化

9.3 memoizationの追加

これまでの定義では，必要になったらば計算するという遅延評価はできていたのですが，必要になることが何度もあった場合には，そのつど計算することになっていた．つまり，


> (setq a (stream-cons (expt 2 2)
         (stream-cons (expt 2 3) 'empty-stream)))
(4 (LAMBDA NIL (STREAM-CONS (EXPT 2 3) 'EMPTY-STREAM))) 
> (stream-rest a)
(8 (LAMBDA NIL 'EMPTY-STREAM)) 
> (stream-rest a)
(8 (LAMBDA NIL 'EMPTY-STREAM)) 
> (stream-rest a)
(8 (LAMBDA NIL 'EMPTY-STREAM)) 
> a
(4 (LAMBDA NIL (STREAM-CONS (EXPT 2 3) 'EMPTY-STREAM)))

のように，毎回8を計算していた．そこで，最初の節のmemo関数のように一度計算したらば覚えてしまうという方法を考える．


(defmacro encapsulate (form)
  `(let ((switch nil) (result nil))
     #'(lambda ()
         (if switch
             result
           (setf switch t result ,form)))))

というように，encapsulateを定義すると，クロージャの中に計算をしたかどうかのスイッチと計算結果が保存される．このクロージャが評価される(expose)たびにスイッチが判定されることになる．

generated through LaTeX2HTML. M.Inaba 平成18年5月7日