Scheme - 積極制御評価器(木構造再帰的手続き(Fibonacci数とスタック演算(最大の深さ、プッシュの総数)))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• MIT/GNU Scheme (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の5(レジスタ計算機での計算)、5.4(積極制御評価器)、5.4.4(評価の実行)、評価器の性能監視、問題 5.29.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 5.29.

コード(BBEdit)

sample.scm

(load "./eval.scm")
(load "./register.scm")
(load "./eceval.scm")
(start eceval)

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Saturday October 26, 2013 at 11:02:50 PM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> (load "./sample.scm")

;Loading "./sample.scm"...
;  Loading "eval.scm"... done
;  Loading "register.scm"... done
;  Loading "eceval.scm"... done


;;; EC-Eval input:
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok

;;; EC-Eval input:
(fib 0)

(total-pushes = 16 maximum-depth = 8)
;;; EC-Eval value:
0

;;; EC-Eval input:
(fib 1)

(total-pushes = 16 maximum-depth = 8)
;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 2)

(total-pushes = 72 maximum-depth = 13)
;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 3)

(total-pushes = 128 maximum-depth = 18)
;;; EC-Eval value:
2

;;; EC-Eval input:
(fib 4)

(total-pushes = 240 maximum-depth = 23)
;;; EC-Eval value:
3

;;; EC-Eval input:
(fib 5)

(total-pushes = 408 maximum-depth = 28)
;;; EC-Eval value:
5

;;; EC-Eval input:
(fib 6)

(total-pushes = 688 maximum-depth = 33)
;;; EC-Eval value:
8

;;; EC-Eval input:
(fib 7)

(total-pushes = 1136 maximum-depth = 38)
;;; EC-Eval value:
13

;;; EC-Eval input:
(fib 8)

(total-pushes = 1864 maximum-depth = 43)
;;; EC-Eval value:
21

;;; EC-Eval input:
(fib 9)

(total-pushes = 3040 maximum-depth = 48)
;;; EC-Eval value:
34

;;; EC-Eval input:
(fib 10)

(total-pushes = 4944 maximum-depth = 53)
;;; EC-Eval value:
55

;;; EC-Eval input:
End of input stream reached.
Moriturus te saluto.
$

a.

n ≥ 2なるFib(n)を計算するのに必要なスタックの最大の深さの式。

3 + 5n

b.

n ≥ 2なるFib(n)を計算するのに使うプッシュの総数の式(S(n))を求める。

S(n)をS(n - 1)、S(n - 2)、定数kで表してみる。

n = 2のとき。

S(2) = S(1) + S(0) + k
72 = 16 + 16 + k
k = 40

n = 3のとき。

S(3) = S(2) + S(1) + k
128 = 72 + 16 + k
k = 40

n = 4のとき。

S(4) = S(3) + S(2) + k
240 = 128 + 72 + k
k = 40

以上から、n ≥ 2のとき。

S(n) = S(n - 1) + S(n - 2) + 40

S(n)をFib(n + 1)で表してみる。

n = 2のとき。

S(2) = a Fib(2 + 1) + b
72 = a * 2 + b

n = 3のとき。

S(3) = a Fib(3 + 1) + b
128 = a * 3 + b

a, bを求める。

a = 56
b = -40

よって、

S(n) = 56 * Fib(n + 1) - 40

(フィボナッチ数列はnに指数的に成長するので、n ≥ 2なるFib(n)を計算するのに使うプッシュの総数も指数的に成長する。)