読者です 読者をやめる 読者になる 読者になる

(wat-aro)

無職から有職者にランクアップしました

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する場所が違うだけなので,効率はかわらない.