プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート

SICP 5.5 Compilation

LISP Scheme

ノート

前節のインタープリタのプログラムは機械語のプログラムと捉えることができる。
ソースプログラムと機械語とを橋渡しする方法には二つある。
一つはインタープリタ。インタープリタの基本的な命令は機械語のサブルーチンとして実現されていて、ソースプログラムはデータとして存在している。データであるソースプログラムを解釈しながら適切な機械語のサブルーチンを呼び出してプログラムを実行してゆく。
もう一つはコンパイラ。コンパイラはソースプログラムを機械語のプログラムに翻訳する。
コンパイルすると実行の効率は良いが、インタープリタの方は対話的な開発やデバッグ等に優れた環境を提供できる。
近年ではこれら二つの方式が混在する環境が求められている。

An overview of the compiler

後々のインタープリタとコンパイルされたプログラムの混在を考慮して、コンパイラもインタープリタと同じレジスタの使い方をするようなプログラムを生成させる。4.1.7 Separating Syntactic Analysis from Executionで行ったのと同様に、プログラムの解釈と実行を分離する。4.1.7の時はlambda式のリストを生成していた。
レジスタの対比についてはインタープリタよりもコンパイラの方が最適化出来る。インタープリタでは、入れ子の式を評価するのに使用中の全てのレジスタを対比する必要があったが、コンパイラではその間に使用されるレジスタが分かるので、必要最小限のレジスタ退避で済む。
変数の検索も実行時に行わずに済む。

5.5.1 Structure of the Compiler

最上位の手続きcompileは4.1.1節のeval、4.1.7節のanalyze、5.4.1節のeval-dispatchと同じ役割。

Targets and linkages

手続きcompileの引数はプログラムとしての式expの他にtargetとlinkage。
targetは式を評価した結果を保存するレジスタ。linkageはコンパイルしたコードが実行を終えた後の続きを示す。

Instruction sequences and stack usage

単純に二つの命令列を連結するのがappend-instruction-sequences。
preservingは二つ目の命令列が必要とするレジスタを一つ目の命令列が変更してしまう場合に、一つ目の命令列の前後にsaveとrestoreを挿入してから二つの命令列を連結する。レジスタのハンドリングはこのpreservingに任せる。
ただ、preservingだけで命令を連結してゆくと、一度レジスタ使用を走査した命令列を何度も走査する事になり非効率なので、命令列には入力として初期化される必要があるレジスタ、命令列で変更されるレジスタの情報が添付される。

Exercise 5.31

preservingの内容というよりは、ev-applicationエントリポイントに相当する命令がどう生成されるのかに依存するので、ここでは予測に過ぎないが、ポイントは評価は左から行うものの右側から評価に何が必要かを考える。

  • (f 'x 'y)　：オペランドは全て定数なのでenvは使用しないし、fが保存されているprocや、引数を保存するarglを別用途で書き換える事もないので、レジスタの退避は一切必要なし。
  • ((f) 'x 'y)　：オペランドの評価にはenv、procは必要ないし、arglも別の用途で使われる事もないので(f)の評価時にレジスタの退避は一切必要なし。
  • (f (g 'x) y)　：最後のyを評価するのにenvが必要だし、procには既にfが入っているので(g 'x)評価時にenvとprocは退避が必要。arglは(g 'x)評価前に初期化されているなら退避が必要。
  • (f (g 'x) 'y)　：前問に比べて最後のyの評価にenvは必要ないので(g 'x)評価時にはprocのみを退避すれば良い。arglについては前問と同様。
Exercise 5.32

a) オペレータがシンボルの場合、すなわち変数の場合は結局以下の部分に飛んで戻って来る。

     ev-variable
     (assign val (op lookup-variable-value) (reg exp) (reg env))
     (test (op bound?) (reg val))
     (branch (label bound-variable))
     (goto (label unbound-variable))
     bound-variable
     (assign val (op bound-value) (reg val))
     (goto (reg continue))

val以外には書き換えない。expにオペレータ部を入れてこれが変数だった場合には、ev-variableに飛んで戻って来れば良い。

     ev-application
     (save continue)
     (assign unev (op operands) (reg exp))
     (save unev)
     (assign continue (label ev-appl-did-operator))
     (assign exp (op operator) (reg exp))
     (test (op variable?) (reg exp))
     (branch (label ev-variable))
     (save env)
     (save unev)
     (assign continue (label ev-appl-operator-evaluated))
     (goto (label eval-dispatch))     
     ev-appl-operator-evaluated
     (restore unev)
     (restore env)
     ev-appl-did-operator
    …

実行してみる

;;; EC-Eval input:
(define (double x) (* x 2))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(double 3)

;;; EC-Eval value:
6

;;; EC-Eval input:

トレースを出してみると：

…
ev-application
(save continue)
(assign unev (op operands) (reg exp))
(assign continue (label ev-appl-did-operator))
(assign exp (op operator) (reg exp))
(test (op variable?) (reg exp))
(branch (label ev-variable))
ev-variable
(assign val (op lookup-variable-value) (reg exp) (reg env))
(test (op bound?) (reg val))
(branch (label bound-variable))
bound-variable
(assign val (op bound-value) (reg val))
(goto (reg continue))
ev-appl-did-operator
(assign argl (op empty-arglist))
(assign proc (reg val))
…

b) インタープリタをどこまで最適化しても、eval-dispatchでの全ての条件判断、今回追加した様なvariable?の様な条件判断（つまりソースコードを解釈する部分）が残っている限りコンパイラの速度に追い付く事はない。