SICP 読み (326) 5.5 翻訳系

問題 5.34

問題文には_本質的な相違を示し、結果のコードを説明せよ_とある。本質的かどうかは分からんが相違点を挙げるとしたら以下か。

• 繰り返し版では手続きの中身は define と application となっている。application な式は末尾な式として翻訳。又、内部の define の中身も if 一発になっていて、これも末尾な式として取り扱われる。再帰版の手続きの中身は define 一発でその中身も if 一発。else 側の式は * な演算が末尾な式になっている。

うーん。微妙。
あと、これは本質的な相違ではないんですが、再帰版における env の save/restore if の条件式の評価部分の一回のみとなっている。preserving は再帰呼び出しにおいて env の退避や復帰が不要というのが分かっている、という事なのかなぁ。ちなみに繰り返し版においては、引数が application な並びになっているので env の退避と復帰が行なわれているのは直前エントリだかで書いた。しかも繰り返し版では元に戻らなくて良いので env の退避や復帰が不要 (本当かなぁ)。
あ、(* (factorial (- n 1) n)) になってるとゆー事はこの時点での n の評価は済んでるのか。前の問題のように (* n (factorial (- n 1))) ってなっていると env の退避と復帰が必要になってくるのか。自分で問題解いてて今更気づくなよ、という話もありますが、エントリを確認してみます。

確認

(323)によると env の退避と復帰は必要みたい。良かった。結果を説明、については以下に scheme なコメント付きのリストを、という事で勘弁してもらって次の問題に移りたい。

((env continue) (val)
;; define なので entry1 と env で make-compiled-procedure して jmp
 ((assign val (op make-compiled-procedure) (label entry1) (reg env))
 (goto (label after-lambda2))
 entry1
;; env を define 時の状態に復帰させて引数と値のセットで拡張
 (assign env (op compiled-procedure-env) (reg proc))
 (assign env (op extend-environment) (const (n)) (reg argl) (reg env))
;; define なので entry3 と env で make-compiled-procedure して jmp
 (assign val (op make-compiled-procedure) (label entry3) (reg env))
 (goto (label after-lambda4))
 entry3
;; env を define 時の状態に復帰させて引数と値のセットで拡張
 (assign env (op compiled-procedure-env) (reg proc))
 (assign env (op extend-environment) (const (product counter)) (reg argl) (reg env))
;; (> counter n) の評価 continue と env は save/restore
 (save continue)
 (save env)
 (assign proc (op lookup-variable-value) (const >) (reg env))
 (assign val (op lookup-variable-value) (const n) (reg env))
 (assign argl (op list) (reg val))
 (assign val (op lookup-variable-value) (const counter) (reg env))
 (assign argl (op cons) (reg val) (reg argl))
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch8))
 compiled-branch9
 (assign continue (label after-call10))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch8
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 after-call10
 (restore env)
 (restore continue)
;; 条件式の戻りの評価
 (test (op false?) (reg val))
 (branch (label false-branch6))
 true-branch5
;; 真の場合は product を戻す (末尾式)
 (assign val (op lookup-variable-value) (const product) (reg env))
 (goto (reg continue))
 false-branch6
;; 偽の場合は iter を呼び出す
 (assign proc (op lookup-variable-value) (const iter) (reg env))
;; 引数の評価において手続き呼び出しがあるため continue と proc を save
 (save continue)
 (save proc)
;; 引数の並びがどちらも手続きになっているので末端側の手続き評価時に
;; env は save される
 (save env)
;; 末端側の引数の評価 (戻ってこなければならない)
 (assign proc (op lookup-variable-value) (const +) (reg env))
 (assign val (const 1))
 (assign argl (op list) (reg val))
 (assign val (op lookup-variable-value) (const counter) (reg env))
 (assign argl (op cons) (reg val) (reg argl))
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch14))
 compiled-branch15
 (assign continue (label after-call16))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch14
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 after-call16
;; 戻ってきたら argl にセットして env を restore
 (assign argl (op list) (reg val))
 (restore env)
;; 再度手続き評価なので argl は save
 (save argl)
;; 先頭側の引数の評価 (これも戻ってこなければならない)
 (assign proc (op lookup-variable-value) (const *) (reg env))
 (assign val (op lookup-variable-value) (const product) (reg env))
 (assign argl (op list) (reg val))
 (assign val (op lookup-variable-value) (const counter) (reg env))
 (assign argl (op cons) (reg val) (reg argl))
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch11))
 compiled-branch12
 (assign continue (label after-call13))
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch11
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 after-call13
;; 戻ってきたら argl を restore して結果を格納
 (restore argl)
 (assign argl (op cons) (reg val) (reg argl))
;; iter 呼び出し準備 (proc と continue の restore)
 (restore proc)
 (restore continue)
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch17))
 compiled-branch18
;; 戻らない
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch17
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 (goto (reg continue))
 after-call19
 after-if7
 after-lambda4
;; entry3 な手続きを iter にセットして OK 戻す (OK はスルー)
 (perform (op define-variable!) (const iter) (reg val) (reg env))
 (assign val (const ok))
;; iter の呼び出し準備
 (assign proc (op lookup-variable-value) (const iter) (reg env))
 (assign val (const 1))
 (assign argl (op list) (reg val))
 (assign val (const 1))
 (assign argl (op cons) (reg val) (reg argl))
 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch20))
 compiled-branch21
;; 戻ってこない
 (assign val (op compiled-procedure-entry) (reg proc))
 (goto (reg val))
 primitive-branch20
 (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
 (goto (reg continue))
 after-call22
 after-lambda2
;; entry1 な手続きを factorial にセットして OK 戻して return
 (perform (op define-variable!) (const factorial) (reg val) (reg env))
 (assign val (const ok))
 (goto (reg continue))))

次もなかなかに面白そげ。