[ 目次, 前節, 次節, 索引 ]

   手続きcompileは翻訳系のトップレベルの振分け処理である. これは4.1.1節のeval手続き, 4.1.7節のanalyze 手続き, 5.4.1節の積極制御評価器のeval-dispatch入り口に対応する. 翻訳系は, 解釈系と同じで, 4.1.2節で定義した式構文手続きを使う.35 compileは翻訳すべき式の構文型について場合分けを実行する. 式の各型につき特別の コード生成器(code generator)へ振り分ける.

(define (compile exp target linkage)
  (cond ((self-evaluating? exp)
         (compile-self-evaluating exp target linkage))
        ((quoted? exp) (compile-quoted exp target linkage))
        ((variable? exp)
         (compile-variable exp target linkage))
        ((assignment? exp)
         (compile-assignment exp target linkage))
        ((definition? exp)
         (compile-definition exp target linkage))
        ((if? exp) (compile-if exp target linkage))
        ((lambda? exp) (compile-lambda exp target linkage))
        ((begin? exp)
         (compile-sequence (begin-actions exp)
                           target
                           linkage))
        ((cond? exp) (compile (cond->if exp) target linkage))
        ((application? exp)
         (compile-application exp target linkage))
        (else
         (error "Unknown expression type -- COMPILE" exp))))

標的と接続

例えば(自己評価の)式5を, 標的valレジスタ, 接続nextで翻訳すると, 命令

(assign val (const 5))

(assign val (const 5))
(goto (reg continue))

命令列とスタックの使用

   命令列を組み合せる最も単純な方法は append-instruction-sequences という手続きである. これは逐次に実行すべき任意個数の命令列をとり, それらを連結して組み合せた列を返す. つまり⟨seq₁⟩と⟨seq₂⟩が命令列なら

(append-instruction-sequences ⟨seq1⟩ ⟨seq2⟩)

⟨seq1⟩
⟨seq2⟩

   レジスタを退避しなければならない時は, 翻訳系のコード生成器は preservingを使う. これは命令列の組合せとしては遥かに微妙な方法である. preservingは三つの引数: レジスタの集合と逐次に実行すべき二つの命令列をとる. これはレジスタ集合の内容で, 第二の列の実行に必要なものがあれば, 第一の列の実行中, それを退避するよう列を連結する. つまり第一の列がレジスタを修正し, 第二の列が実際にレジスタの元々の内容を必要とするなら, preserving は第一の列の回りをそのレジスタのsaveと restoreでくるんでから, 列を連結する. そうでなければpreserving は単に連結した命令列を返す. それで例として

(preserving (list ⟨reg1⟩ ⟨reg2⟩) ⟨seq1⟩ ⟨seq2⟩)

   命令列の組合せにpreservingを使うと, 翻訳系は不必要なスタック演算を避ける. これはまたsaveとrestore 命令を生成するかどうかの細部を, preserving手続きの中に隔離し, それを個々のコード生成器を書く時に生じる関心から分離する. 実際saveとrestore命令がコード生成器で陽に作られることはない.

   原則として命令列を命令のリストとして表現出来る. そうすると append-instruction-sequencesは通常のリストのappendを実行して命令列を組み合せることが出来る. しかしpreservingは, 列がレジスタをどう使うか決めるため, 命令列を解析しなければならず, 複雑な演算になろう. preservingは複雑と同時に, その命令列引数がpreservingを呼び出して構成されていれば, その時その一部は既に解析されたにも拘らず, 引数のそれぞれをまた解析しなければならないので, 非効率である. そういう繰返しの解析を避けるため, 各命令列にレジスタの使い方に関する情報を対応づける. 基本命令列を構成する時, これに情報を積極的に用意し, 命令列を組み合せる手続きは, 合成列に対する, レジスタの使い方の情報を, 要素列に対応づけられた情報から導き出す.

   命令列は次の情報を含む.

• 列の命令を実行する前に初期化しなければならないレジスタの集合(これらのレジスタを列で必要(needed)という)

• 列の命令が値を修正するレジスタの集合 および

• 列の実際の命令(文(statements)ともいう)

命令列をこの三つの部分のリストとして表現する. そこで命令列の構成子は

(define (make-instruction-sequence needs modifies statements)
  (list needs modifies statements))

   例えば現在の環境で変数xの値を探索し, 結果をvalに代入して戻る二命令列は, レジスタenvとcontinueが初期化されることを要求し, レジスタvalを修正する. 従ってこの列は

(make-instruction-sequence '(env continue) '(val)
 '((assign val
           (op lookup-variable-value) (const x) (reg env))
   (goto (reg continue))))

   時には文の一つもない命令列を構成する必要がある:

(define (empty-instruction-sequence)
  (make-instruction-sequence '() '() '()))

   命令列を組み合せる手続きは5.5.4節にある.

問題 5.31

手続き作用の評価では, 積極制御評価器は常に演算子の評価の前後でenvレジスタを退避回復し, (最後のものを除いて)各被演算子の前後でenvを退避回復し, 各被演算子の前後でarglを退避回復し, 被演算子列の評価の前後でprocを退避回復する. 次の組合せのそれぞれで, これらのsaveとrestoreのどれが余分であり, 翻訳系のpreserving 機構で除けるかを示せ.

(f 'x 'y)

((f) 'x 'y)

(f (g 'x) y)

(f (g 'x) 'y)

35 しかしわれわれの翻訳系はSchemeプログラムであり, 式を操作するのに使う構文手続きは, 超循環評価器で使った実際のScheme手続きであることに注意しよう. 対照的に積極制御評価器では, 等価な構文演算はレジスタ計算機の演算として使用可能と仮定した. (もちろんSchemeでレジスタ計算機をシミュレートした時, 実際のScheme手続きをレジスタ計算機シミュレーションで使った.)

[ 目次, 前節, 次節, 索引 ]