問題3-27 (3.3.3 Representing Tables)

いわゆるメモ化．
フィボナッチ数列の計算でメモ化使うと，時間計算量がでできるという話．
プログラムは以下の通りで，計算結果をテーブルに蓄積しておいて，

• もし既に計算済みの計算結果がテーブルにあれば，それを即座に答えとして返す
• 計算済みの計算結果がテーブルになければ，計算してその結果をテーブルに蓄積する

という形になっている．

(define memo-fib
  (memoize (lambda (n)
	     (cond ((= n 0) 0)
		   ((= n 1) 1)
		   (else (+ (memo-fib (- n 1))
			    (memo-fib (- n 2))))))))

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
	(or previously-computed-result
	    (let ((result (f x)))
	      (insert! x result table)
	      result))))))

environment diagram を書けというのはあまりにもメンドい，かつ煩雑になるので省略する．
なぜになるかは，はそれぞれ一度計算すれば，以後逐一計算する必要がなくなるため．
ホントは厳密に証明すべきなんだけど，いまじかんない．