Scheme - 翻訳系の概観\(再帰的プロセス, 反復的プロセスとスタックスペース(階乗計算))

計算機プログラムの構造と解釈
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.34.を解いてみる。

その他参考書籍

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

問題 5.34.

反復的プロセスの再帰的手続き階乗計算の翻訳。

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

entry2 ;; factorialの呼び出し
  (assign env (op compiled-procedure-env) (reg proc))
  (assign env (op extend-environment) (const (n)) (reg env))
  
  ;; 手続き本体の開始
  (save continue)
  (save env)
  
  ;; 並びの翻訳
  ;; 並びの1つ目(define (iter…)…)
  (assign val (op make-compiled-procedure (label entry4) (reg env))
  (goto (label after-lambda3))
  
entry4 ;; iterの呼び出し
  (assign env (op compiled-procedure-env) (reg proc))
  (assign env (op extend-environment) (const (product counter)) (reg env))
  ;; 手続き本体の開始
  (save continue)
  (save env)
  
  ;; (> counter n)の計算
  (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-branch22))
compiled-branch21
  (assign continue (label after-call20))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch22
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call20 ;; valには(> counter n)の結果がある
  (restore env)
  (restore continue)
  (test (op false?) (reg val))
  (branch (label false-branch9))
true-branch10
  (assign val (reg product))
  (goto (reg continue))
false-branch9
;; (iter (* counter product) (+ counter 1))を計算して返す
  (assign proc (op lookup-variable-value) (const iter) (reg env))
  (save continue)
  (save proc) ;; iter手続きを退避
  
  (save env)
  ;; (+ counter 1) を計算して返す
  (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) (op val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch13))
compiled-branch12
  (assign continue (label after-call11))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch13
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call11 ;; valには(+ conter 1)の結果がある
  (assign argl (op list) (reg val))
  (restore env)
  (save argl)
  ;; (* counter product)を計算して返す
  (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-branch16))
compiled-branch15
  (assign continue (label after-call14))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch16
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call14 ;; valには(* counter product)の結果がある
  (restore argl)
  (assign argl (op cons) (reg val) (reg argl))
  (restore proc) ;; iter手続きを回復
  (restore continue)
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch19))
compiled-branch18
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch19
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
  (goto (reg continue))
after-call17
after-if8
after-lambda3
  (perform (op define-variable)
           (const iter)
           (reg val)
           (reg env))
  (assign val (const ok))

  ;; 並びの2つ目(iter 1 1)
  ;; (iter 1 1)を計算して返す
  (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-branch8))
compiled-branch6
  
primitive-branch7
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call5 ;; valには(iter 1 1)の結果がある
after-lambda1
  (perform (op define-variable!)
           (const factorial)
           (reg val)
           (reg env))
  (assign val (const ok))

再帰的プロセスの場合、本書のp.356のfalse-branch4の(save argl)でスタックが積み上がっていく。(entry2に戻る前までに退避されたarglは回復されない。)一方、上記の翻訳反復的プロセスの場合は、after-call11の(save argl)で退避されたarglは次のiterの呼び出し(entry4)に行く前に、after-call14の(restore argl)で回復されるので、再帰的プロセスのようにスタックがどんどん積み上がっていくことはなく、固定スタックスペースで走らせることが出来る。