SICP 問題 5.33
以下の2つの翻訳結果を比較してその相違を説明する.
(compile '(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) 'val 'next) (compile '(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) 'val 'next)
一つ目を出力して整形したのが以下になる.
((env) (val) ((assign val (op make-compiled-procedure) (label entry1) (reg env)) (goto (label after-lambda2)) entry1 (assign env (op compiled-procedure-env) (reg proc)) (assign env (op extend-environment) (const (n)) (reg argl) (reg env)) (save continue) (save env) (assign proc (op lookup-ariable-value) (const =) (reg env)) (assign val (const 1)) (assign argl (op list) (reg val)) (assign val (op lookup-ariable-value) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch6)) compiled-branch7 (assign continue (label after-call8)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch6 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call8 (restore env) (restore continue) (test (op false?) (reg val)) (branch (label false-branch4)) true-branch3 (assign val (const 1)) (goto (reg continue)) false-branch4 (assign proc (op lookup-ariable-value) (const *) (reg env)) (save continue) (save proc) (assign val (op lookup-ariable-value) (const n) (reg env)) (assign argl (op list) (reg val)) (save argl) (assign proc (op lookup-ariable-value) (const factorial) (reg env)) (save proc) (assign proc (op lookup-ariable-value) (const -) (reg env)) (assign val (const 1)) (assign argl (op list) (reg val)) (assign val (op lookup-ariable-value) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch9)) compiled-branch10 (assign continue (label after-call11)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch9 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call11 (assign argl (op list) (reg val)) (restore proc) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch12)) compiled-branch13 (assign continue (label after-call14)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch12 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call14 (restore argl) (assign argl (op cons) (reg val) (reg argl)) (restore proc) (restore continue) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch15)) compiled-branch16 (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch15 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) (goto (reg continue)) after-call17 after-if5 after-lambda2 (perform (op define-variable!) (const factorial) (reg val) (reg env)) (assign val (const ok)) ))
これを5.33a.scmとして保存し,二つ目を5.33b.scmとして保存し,diffを取った.
--- 5.33a.scm 2016-02-06 19:25:30.000000000 +0900 +++ 5.33b.scm 2016-02-06 19:26:35.000000000 +0900 @@ -32,9 +32,7 @@ (assign proc (op lookup-ariable-value) (const *) (reg env)) (save continue) (save proc) - (assign val (op lookup-ariable-value) (const n) (reg env)) - (assign argl (op list) (reg val)) - (save argl) + (save env) (assign proc (op lookup-ariable-value) (const factorial) (reg env)) (save proc) (assign proc (op lookup-ariable-value) (const -) (reg env)) @@ -62,7 +60,9 @@ primitive-branch12 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call14 - (restore argl) + (assign argl (op list) (reg val)) + (restore env) + (assign val (op lookup-ariable-value) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (restore proc) (restore continue)
construct-arglistでoperandをまずreverseしているので,
書かれた引数とは逆順に処理していくことになる.
一箇所目のdiffはfalse-branch4の中,二箇所目はprimitive-brach12にある.
5.33aはfalse-branchでまずnの値を求める.
そして値をリスト化し,arglに代入してsaveする.
primitive-branchでvalの値は(factorial (- n 1))を翻訳したものになっている.
そこでarglをrestoreして,valとconsしてarglを完成させている.
一方5.33bはまずenvを保存するところから始まる.
(factorial (- n 1))を評価するときに環境が変更されたら困るからだ.
そしてprimitive-branchに来たところで5.33aと同じく,valの値は(factorial (- n 1))になっている.
5.33bはvalをリスト化してarglに保存する.
そして環境を(factorial (- n 1))を評価する前の状態に戻し,nを評価する.
評価した値とarglをconsしてarglは完成する.
一箇所目は5.33aも5.33bも一回saveし,二箇所目で一回restoreする.
5.33bは一箇所目で二回assignし,5.33aは二箇所目で二回assignする.
save箇所が同じでassignする場所が違うだけなので,効率はかわらない.