(compile
'(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
'val
'next)
define式の値をvalレジスタに置くよう指定した. defineの実行後,
翻訳したコードが何をするかには関心がないので, 接続記述としてのnextの選択は任意である.
compileは式が定義であると知り, compile-definitionを呼び出して(valに標的して)代入する値を計算するコードと, それに続く定義を組み込むコードと, それに続くdefineの値(記号okである.)を標的レジスタに置くコードと, 最後に接続のコードに翻訳する. envは定義を組み込むのに必要なので値の計算の前後で保存する. 接続がnextなので今の場合接続コードはない. 従って翻訳したコードの骨組みは
⟨値を計算するコードで修正されるならenvを退避⟩
⟨標的val, 接続nextで定義する値の翻訳⟩
⟨上で退避したならenvを回復⟩
(perform (op define-variable!)
(const factorial)
(reg val)
(reg env))
(assign val (const ok))
である.
変数factorialに対し値を作るべく翻訳する式はlambda式で, その値は階乗を計算する手続きである. compileはこれを扱うのに, compile-lambdaを呼び出す. それは手続き本体を翻訳し, それに新しい入り口としてラベルをつけ, 新しい入り口にある手続き本体を実行時の環境と組み合せ, 結果をvalに代入する命令を生成する. 命令列はこの場所に挿入した翻訳した手続きコードを飛び越す. 手続きのコード自身は手続きの定義の環境を, 仮パラメタnを手続き引数に束縛するフレームで拡張することで始る. 次に実際の手続き本体が来る. 変数の値に対するこのコードは, envレジスタを修正しないので, 上に示した選択的なsaveとrestoreは生成しない. (entry2の手続きコードはここでは実行しないので, envの使用は無関係である.) 従って翻訳したコードの骨組みは次のようになる.
(assign val (op make-compiled-procedure)
(label entry2)
(reg env))
(goto (label after-lambda1))
entry2
(assign env (op compiled-procedure-env) (reg proc))
(assign env (op extend-environment)
(const (n))
(reg argl)
(reg env))
⟨手続き本体の翻訳⟩
after-lambda1
(perform (op define-variable!)
(const factorial)
(reg val)
(reg env))
(assign val (const ok))
手続き本体は(compile-lambda-bodyで)標的valと接続 returnを持つ列として常に翻訳する. 今の場合は単一のif式である:
(if (= n 1)
1
(* (factorial (- n 1)) n))
compile-ifは, 最初に(valに標的した)述語を計算し, 次に結果を調べて述語が偽なら真の枝を飛び越すコードを生成する. envとcontinueはif式の残りで必要とするかも知れないので, 述語コードの前後で保存する.
if式は手続き本体の作る列の最後の式(でまた唯一の式)なので, その標的はval,
接続はreturnであり, 真と偽の枝は共に標的valと接続
returnを持って翻訳する. (つまりどちらかの枝で計算する条件式の値が手続きの値である.)
⟨述語で修正され枝で使われるならcontinue, envを退避⟩ ⟨標的val, 接続nextで述語を翻訳⟩ ⟨上で退避したのならcontinue, envを回復⟩ (test (op false?) (reg val)) (branch (label false-branch4)) true-branch5 ⟨標的val, 接続returnで真の枝の翻訳⟩ false-branch4 ⟨標的val, 接続returnで偽の枝の翻訳⟩ after-if3
述語(= n 1)は手続き呼出しである. これは演算子(記号=)を探索し, その値をprocに置く. 次に引数1とn の値をarglに組み立てる. 次にprocが基本手続きか合成手続きかをテストし, それに従い基本手続きの枝か合成手続きの枝かに振り分ける. 両方の枝はafter-callラベルから合流する. 演算子と被演算子の評価の前後でレジスタを保存する要求は, 今の場合これらの評価は問題のレジスタを修正しないので, レジスタの退避には至らない.
(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
定数1である真の枝は(標的val, 接続returnで)
(assign val (const 1)) (goto (reg continue))に翻訳する. 偽の枝のコードは, 手続きを記号*の値で引数はnと別の手続き呼出し(factorialの呼出し)の結果である別の手続き呼出しである. これらの呼出しのそれぞれでprocとarglと自分の基本手続きの枝と合成手続きの枝を設定する. 図5.17はfactorial手続きの定義の全翻訳を示す. 上に示した述語の前後のcontinueとenvのsaveとrestoreは, これらのレジスタは述語の手続き呼出しで修正され, 枝の手続き呼出しとreturn接続で必要とするので, 実際は生成される.
;; 手続きを構成し手続き本体のコードを飛び越す
(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 argl) (reg env))
;; 手続き本体の開始
(save continue)
(save env)
;; (= n 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 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
;; (* (factorial (- n 1)) n)を計算し返す
(assign proc (op lookup-variable-value) (const *) (reg env))
(save continue)
(save proc) ; *手続きを退避
(assign val (op lookup-variable-value) (const n) (reg env))
(assign argl (op list) (reg val))
(save argl) ; *の部分引数リストを退避
;; *のもう一つの引数(factorial (- n 1))の計算
(assign proc
(op lookup-variable-value) (const factorial) (reg env))
(save proc) ; factorial手続きを退避
;; factorialの引数(- n 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 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) ; factorialを回復
;; factorialを作用させる
(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 (- n 1))の結果がある
(restore argl) ; *の部分引数リストを回復
(assign argl (op cons) (reg val) (reg argl))
(restore proc) ; *を回復
(restore continue)
;; *を作用させ値を返す
(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
;; 手続きを変数factorialに代入
(perform
(op define-variable!) (const factorial) (reg val) (reg env))
(assign val (const ok))
図5.17 factorial手続きの定義の翻訳
(define (factorial-alt n)
(if (= n 1)
1
(* n (factorial-alt (- n 1)))))
この手続きを翻訳し, 結果のコードをfactorialで出来たのと比べよ. 見つけた相違を説明せよ. どちらのプログラムがもう一方より効率的に実行するか.
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
を翻訳せよ. factorialの反復的なものと再帰的なもののコードの間の, 一方のプロセスにスタックを積み上げさせ, 他方には固定スタックスペースで走らせる本質的な相違を示し, 結果のコードを説明せよ.
(assign val (op make-compiled-procedure) (label entry16)
(reg env))
(goto (label after-lambda15))
entry16
(assign env (op compiled-procedure-env) (reg proc))
(assign env
(op extend-environment) (const (x)) (reg argl) (reg env))
(assign proc (op lookup-variable-value) (const +) (reg env))
(save continue)
(save proc)
(save env)
(assign proc (op lookup-variable-value) (const g) (reg env))
(save proc)
(assign proc (op lookup-variable-value) (const +) (reg env))
(assign val (const 2))
(assign argl (op list) (reg val))
(assign val (op lookup-variable-value) (const x) (reg env))
(assign argl (op cons) (reg val) (reg argl))
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-branch19))
compiled-branch18
(assign continue (label after-call17))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
primitive-branch19
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call17
(assign argl (op list) (reg val))
(restore proc)
(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
(assign argl (op list) (reg val))
(restore env)
(assign val (op lookup-variable-value) (const x) (reg env))
(assign argl (op cons) (reg val) (reg argl))
(restore proc)
(restore continue)
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-branch25))
compiled-branch24
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
primitive-branch25
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))
(goto (reg continue))
after-call23
after-lambda15
(perform (op define-variable!) (const f) (reg val) (reg env))
(assign val (const ok))
図5.18 翻訳出力の例 問題5.35参照(assign val (op lookup-variable-value) (const a) (reg env)) (assign val (op +) (reg val) (const 1))のように何か単純なものに翻訳されよう.43 この問題では翻訳系を拡張し, 選ばれた基本手続きにオープンコードを支援させる. これらの基本手続きの呼出しでは, 一般的な手続き作用のコードの代りに, 特別目的のコードを生成する. このために計算機を特別な引数レジスタarg1とarg2で拡張する. 計算機の基本算術演算は入力をarg1とarg2からとる. 結果はval, arg1またはarg2に置く.
翻訳系は原始プログラムの中で, オープンコード基本手続きの作用が認識出来なければならない.
compile手続きの中の振分けを拡張し, 現状で認識している
予約語(特殊形式)に追加して, これらの基本手続き名が認識出来るようにする.44
各特殊形式に対して翻訳系はコード生成器を持つ. この問題はオープンコード基本手続きに対し, 一組のコード生成器を構成する.
a. オープンコード基本手続きは特殊形式と違って, 引数をすべて評価する.
オープンコードのコード生成器のすべてが使うコード生成器spread-argumentsのコードを書け.
spread-argumentsは被演算子のリストをとり, 連続した引数レジスタを標的として被演算子を翻訳する. 被演算子にはオープンコード基本手続きの呼出しがあるかも知れないので, 被演算子の評価中は引数レジスタは保存しなければならないことに注意しよう.
b. 基本手続き=, *, -および+のそれぞれに対し, 演算子を持つ組合せと標的と接続記述をとり, 引数をレジスタに展開するコードを作り, 与えられた標的と与えられた接続を持つ演算を実行するコード生成器を書け. 二つの被演算子の式を扱うだけでよい. compileがこれらのコード生成器にも振り分けるようにせよ.
c. 新しい翻訳系をfactorialの例で試せ. 結果のコードをオープンコードなしに生成した結果と比べよ.
d. コード生成器を+と*について拡張し, 任意個の被演算子の式が扱えるようにせよ. 二つを超える被演算子の式は, それぞれが二つの入力を持つ演算の列へ翻訳しなければならない.
43
ここでは同じ記号+を原始言語手続きと機械演算の両方を表すのに使った. 一般に原始言語の基本演算と計算機の基本演算の間には1対1対応はない.
44
基本手続きを予約語にするのは, 利用者がこれらの名前を別の手続きに束縛しなおすことが出来ないので, 一般にはよくない考えである. 更に予約語を使用中の翻訳系に追加すると, これらの名前の手続きを定義する現行のプログラムは働かなくなる. この問題を避ける方法については問題5.44参照