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

SICP scheme

どうもこつこつヤるのは性に合わん。ってか、全部を地道にハンドアセンブルって面倒くっさい。なんとかして

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))
(factorial 1)

の評価をざくっとヤッツける手法がないものか。
# ハンドアセンブル、ではないような気もする (駄目

とりあえず

検討してみる事に。上記の factorial 手続きは定義済みが前提で (factorial 1) が前提として、この式が apply されるまでに都合 5 回 save されるはず。この手続き呼び出しのパターンは

  • 引数が一つ
  • それ以外

あるいは引数が save を伴なうものかそうでないかによっても save な回数は変わる。例えば引数二つで両方変数だったら 4 + 3 + 1 で 8 回だし、変数な引数が三つだったら、4 + 3 + 3 + 1 で 11 回か。
これが本当かどうか、そして引数が変数なケースはこの後出てくるので略。apply においては primitive なソレであれば save は無し。compound なものについては ev-sequence に jmp してから、になるはず。しかも ev-sequence も末尾再帰な考慮が入ってるので評価する式が一つだけ、とか一番最後の手続きは、という形で微妙な計算式になるものと思われます。
factorial が束縛されている手続きは iter の define と iter の呼び出しになってて、define な処理における save の回数は 3 回。define を評価する前に 2 回 save が発生。次の iter の呼び出し関連の評価では save は行なわれずに、continue を restore して stack が空になった挙句にいきなり eval に jmp。
で、(iter 1 1) を評価して apply に渡るまでに上述の通りだと 4 + 3 + 1 で 8 回になる、と書いた。本当かどうか確認してみる。うん。多分大丈夫。apply はスルーで compound な手続きなので ev-sequence がナニ。
iter の中の手続きは if 式一発になってるので、ev-sequence において save はされない形になる。てコトは ev-sequence では評価する要素の数から 1 引いた値に 2 を掛けた数の save が少なくとも発生するのか。eval する式がどうか、にはよりますが。
次の eval-if では基本的に条件式を評価する時に 3 回の save が行なわれる。あとは条件式の評価だったりその結果だったり then ブロック、else ブロックの評価によって save が何回か、は変化するか。
factorial (ってか iter) の場合には条件式が primitive な引数二つ (しかも save されない) という事で条件式の評価における save の回数は 3 + 4 + 3 + 1 で 11 回とゆー事になるのでしょうか。
ここまでの save 回数が 5 + 5 + 8 + 11 で 29 回。ここから先は

(iter (* counter product) (+ counter 1))

の評価になります。この手続きは factorial においては最低でも一度は実行されますが、それ以降は factorial に渡される n の値によってその回数が違ってくる、と。値から判断するに、この先の save 回数は 35 で、n の値が 1 増える毎に save の回数が 35 回づつ増えていくのもこっから先の save 回数が根拠になっているはず。

ちょい休憩

で、再開。
上記の手続き呼び出しは 4 + 3 + 1 な形ですが、これに加えてそれぞれの引数な手続きを評価していく時の save が 4 + 3 + 1 を 2 回分、という事に (日本語微妙
引数は primitive な手続きなので iter が apply に渡る迄の save の回数は 24 回になるのかなぁ。あとは if の評価にかかる save の回数 11 を加えて 35 ってコトで良いのだろうか。なんとなく easy に過ぎないか、と自分でも思うんですが OK ってコトにしておきます。

整理してみる

  • save されないもの

基本的に self-eval、variable、quoted、lambda なソレは save は行なわれない

  • application

演算子の評価で 4 回。被演算子の評価で (+ (* 3 (- 被演算子の数 1)) 1) 回の save が行なわれる。ただし、引数が手続きだった場合は同じ計算を行なった結果を加える必要がある模様

  • if

条件式の評価前に 3 回 save される。加えて条件式の評価における考慮が必要

  • apply

apply では save は行なわれないが、compound な手続きの場合に以降の ev-sequence にて save される場合もある

  • sequence

二つ以上の式の並びが評価される場合には (* 2 (- リストの数 1)) 回の save が行なわれる。式が一つだけだった場合には save は行なわれない

  • define と assignment

3 回 save されて変数の評価を行なう。通常変数は手続きではあり得ないので 3 回と見てて OK なのかどうか。