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月6日