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

SICP scheme

ちょっと確認できてる点だけ控えておく。

問題 5.26

現時点では末尾再帰な ev-sequence のはずなので手続きを評価器に吸わせてみた。

;;; EC-Eval input:
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

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

;;; 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:

push 回数が 35 回づつ増加しているのが分かる。最大深さは変わらず。この回数の根拠は面倒臭いけど確認すべきかな。

検討

(factorial 1) を評価器に読み込ませてみる。ってその前に define も見てみた方が良いか。

  • eval-dispatch で definition 認定
    • unev に definition-variable (factorial) を格納して save
    • exp に definition-value (lambda 式) をセット
    • env (the-global-environment) を save
    • continue (最初なので print-result が格納) を save
    • continue に ev-definition-1 をセットして eval-dispatch に jmp
  • eval-dispatch では lambda 認定
    • unev に lambda-parameter をセット
    • exp に lambda-body をセット
    • val に make-procedure した値をセット
    • continue (ev-definition-1) に jmp
    • continue、env、unev の順で restore
    • define-variable! で factorial を va lに束縛
    • val に OK セットして continue (print-result) に jmp

確かに 3 回 push して最大深さは 3 ですな。で、(factorial 1) の評価行きます。(ってやり始めて気が付いたんですが、push の回数 64 回だったなぁ。やれやれだ)

  • eval-dispach で application 認定
    • continue (最初なので print-result が格納) を save
    • env (factorial を手続きに束縛している the-global-environment が格納) を save
    • unev に operands を格納して save
    • exp に operator、cont に ev-appl-did-operator をセット
  • eval-dispatch で variable 認定 (ev-variable に jmp)
    • val に lookup した式をセット
    • continue (ev-appl-did-operator) に jmp
    • unev、env の順で restore (cont は最後限定じゃないとマズい)
    • algl に空リスト、proc に val をセット
    • 引数ナシだったら jmp しますが、引数は一つある
    • proc を save
    • argl も save
    • exp に unev (引数リスト) の最初の要素をセット
    • unev に残りがないので ev-appl-last-arg に jmp
    • continue に ev-appl-accum-last-arg をセット
    • この時点で stack には argl, proc, continue が格納されている
  • exp は 1 なので eval-dispatch で self-evaluating 認定
    • val に 1 セットして continue (ev-appl-accum-last-arg) に jmp
    • argl を restore
    • argl に val を追加
    • proc を restore して apply-dispatch に jmp
    • proc の中身は compound 認定なので compound-apply に jmp
    • uenv に procedure-parameter をセット
    • env に procedure-environment (これは define した時点の環境) をセット
    • env 拡張 uenv と argl を使って n に 1 を束縛
    • uenv に procedure-body をセット
    • ev-sequence に jmp
    • この時点の stack は continue (最初のヤツ) のみな模様
    • exp に取り出される最初の式は define な式
    • uenv と env が save
    • continue に ev-sequence-continue がセットされて eval-dispatch に jmp
  • eval-dispatch では definition 認定

ってちょい中断。define な式を eval する直前の env を push しといて、eval から戻った時点で env を pop しとりますが、iter が手続きに束縛された環境はチャラになってしまうのかなぁ。そうではないハズなんですが、そうではない根拠が見つからぬ。
あ、そーか。compound-apply する時に手続き作った時の環境を使うんだ。すげー (ここに至る迄にちょっとした時間が経過しております)。って違うか。駄目だ。頭がテンパッてる状態なんで、ちょっと頭を冷やしまーす。

駄目だ

頭は未だ冷えません。とりあえずスルーで問題はヤッツケて、なんとかしてデバッガを作って確認してみる事に。
ってーか、誰かタスケテ下さひ状態だよ。ワケワカんねぇ。(とほほほほ
週末はネットに繋げない可能性が高いんで製造という観点においては逆に都合が良い。