SICP 問題 4.29

メモ化しないとはるかに遅くなるプログラムの例として
再帰でフィボナッチ数列の第n項を求める手続きを定義する．

(define (fib n)
  (let iter ((a 0) (b 1) (count n))
    (if (= count 0)
        a
        (iter b (+ a b) (- count 1)))))

;; メモ化するforce-it
(define (force-it obj)
  (cond ((thunk? obj)
         (let ((result (actual-value (thunk-exp obj)
                                     (thunk-env obj))))
           (set-car! obj 'evaluated-thunk)
           (set-car! (cdr obj) result) ;;expをその値で置き換える
           (set-cdr! (cdr obj) '())    ;;必要のなくなったenvを忘れる
           result))
        ((evaluated-thunk? obj) (thunk-value obj))
        (else obj)))

;; メモ化しないforce-it
(define (force-it obj)
  (if (thunk? obj)
      (actual-value (thunk-exp obj) (thunk-env obj))
      obj))

;; driver-loopにtimeマクロを仕込む
(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
    (let ((output (time (actual-value input the-global-environment)))) ;;ここにtimeマクロ
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))

メモ化する場合

;;; M-Eval input:
(fib 30)
;(time (actual-value input the-global-environment))
; real   0.001
; user   0.000
; sys    0.000

;;; M-Eval value:
832040

メモ化しない場合

;;; M-Eval input:
(fib 30)
;(time (actual-value input the-global-environment))
; real   6.559
; user   6.540
; sys    0.000

;;; M-Eval value:
832040

　

(define (square x)
  (* x x))

(define (id x)
  (set! count (+ count 1))
  x)

メモ化する場合

;;; M-Eval input:
(square (id 10))

;;; M-Eval value:
100

;;; M-Eval input:
count

;;; M-Eval value:
1

メモ化しない場合

;;; M-Eval input:
(square (id 10))

;;; M-Eval value:
100

;;; M-Eval input:
count

;;; M-Eval value:
2

メモ化すると(* x x)を評価する時に初めのxは(thunk (id 10))となっているのでこれをforce-itしてcountを+1して10を返し，
xの束縛を(evaluated-thunk 10)に変える．
次のxをforce-itするとそのまま10が返る．