SICP 読み (296) 5.4 積極制御評価器

SICP scheme

問題 5.27

机上で push 回数を考えようとしてみたんですが、バスの中で直前エントリな材料が見えないので断念。この下書き書きながら直前エントリな纏めを見ながら計算してみたら一応合ってる模様。
まず、5.26 な factorial のスタックのソレが以下。

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

(total-pushes = 64 maximum-depth = 10)
;;; EC-Eval value:
1

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

(total-pushes = 99 maximum-depth = 10)
;;; EC-Eval value:
2

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

(total-pushes = 134 maximum-depth = 10)
;;; EC-Eval value:
6

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

(total-pushes = 169 maximum-depth = 10)
;;; EC-Eval value:
24

;;; EC-Eval input:

最大深さは変わらず。push 回数は 35 づつ増分。以下が 5.27 の実行結果。

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

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

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

(total-pushes = 48 maximum-depth = 13)
;;; EC-Eval value:
2

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

(total-pushes = 80 maximum-depth = 18)
;;; EC-Eval value:
6

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

(total-pushes = 112 maximum-depth = 23)
;;; EC-Eval value:
24

;;; EC-Eval input:

最大深さが 5 づつ増分。push 回数は 32 づつ増分。あと、机上な計算ですが (factorial 1) の場合は

  • 引数一つの application は 4 + 1 の push
  • if の条件式の評価前で 3 回 push
  • 二つ引数がある application な条件式の評価で 4 + 3 + 1

の合計が 16 となる。あるいは (factorial 2) の場合は、上記に加えて else なブロックの手続きの push 回数として

  • 引数二つの application として 4 + 3 + 1 の push
  • factorial の引数の手続きが引数二つで 4 + 3 + 1 の push
  • factorial の評価で 5 + 3 + 8 の push

の合計が 32 になります。これが増分。お蔭様で随分計算が楽です。

n を使った式

  • 反復的階乗
    • 深さは 10
    • push 回数は 64 + (n - 1) * 35
  • 再帰的階乗
    • 深さは 8 + (n - 1) * 5
    • push 回数は 16 + (n - 1) * 32