Scheme - 翻訳系の概観(翻訳したコードの例(2通りの階乗手続き))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• MIT/GNU Scheme (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の5(レジスタ計算機での計算)、5.5(翻訳系)、翻訳系の概観、5.5.5(翻訳したコードの例)、問題 5.33-b.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 5.33.

翻訳。

  (assign val (op make-compiled-procedure) (label entry2) (reg env))
  (goto (label after-lambda1))

entry2 ;; factorial-altの呼び出し
  (assign env (op compiled-procedure-env) (reg proc))
  (assign env (op extend-environment) (const (n)) (reg argl) (reg env))
  ;; 手続き本体の開始
  (save continue)
  (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 n) (reg env))
  (assign argl) (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch17))
compiled-branch16
  (assign continue (label after-call15))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch17
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call15 ;; valには(= n 1)の結果がある
  (restore env)
  (restore continue)
  (test (op false?) (reg val))
  (branch (label false-branch4))
true-branch5 ;; 1を返す
  (assign val (const 1))
  (goto (reg continue))

false-branch4
;; (* n (factorial-alt (- n 1)))を計算して返す
  (assign proc (op lookup-variable-value) (const *) (reg env))
  (save continue)
  (save proc) ;; 手続きを退避
  (save env) ;; factorial-altでは必要
  ;; (factorial-alt (- n 1))の計算
  (assign proc (op lookup-variable-value) (const factorial-alt) (reg env))
  (save proc)
  ;; (- n 1)の計算
  (assign proc (op lookup-variable-value) (const -) (reg env))
  (assign val (const 1))
  (assign argl (op list) (reg val))
  ;; (save argl) factorial-altでは不必要
  (assign val (op lookup-variable-value) (const n) (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure? (reg proc)))
  (branch (label primitive-branch8))
compiled-branch7
  (assign continue (label after-call6))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch8
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call6 ;; valには(- n 1)の結果がある
  (assign argl (op list) (reg val))
  (restore proc)
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch11))
compiled-branch10
  (assign continue (label after-call9))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch11
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call9 ;; valには(factorial-alt (- n 1))の結果がある
  ;; (restore argl) factorial-altでは不必要
  (assign argl (op list) (reg val))
  (restore env) ;; factorial-altでは必要
  (assign val (op lookup-variable-value) (const n) (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (restore proc) ;; *を回復
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch14))
compiled-branch13
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch14
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
  (goto (reg continue))
after-call12
after-if3
after-lambda1
  (perform (op define-variable!)
           (const factorial-alt)
           (reg val)
           (reg env))
  (assign val (const ok))

条件式ifのfalse部分について、factorial階乗手続きは、nを計算し、部分引数リストを退避し、(factorial (- n 1))を計算し、部分引数リストを回復して結果を求める。

一方、factorial-alt階乗手続きは、環境を退避し、(factorial (- n 1))を計算して、環境を回復して結果を求める。

部分引数リストを退避回復するか、環境を退避回復するかという相違はあるけど、どちらのプログラムの実行も効率性に大きな差はない。