8-3. ミニOCamlから CAM へのコンパイル

本節では、ミニOCamlのプログラムから CAM の命令列へのコンパイルについて解説する。まず、コンパイルに用いる以下の補助関数を実装する。関数 position は、変数名 x と、変数名のリスト venv が与えられたとき、x が venv の何番目の要素であるかを計算する関数である。ここで、1 番目に現れるとき 0 を返し、一般に venv の N 番目の要素であったとき、N-1 を返すものとする。x が venv に現れない時はエラーとし、x が venv に 2 回以上出現するときは、最初の出現についての値を返す。

たとえば (position "a" ["b"; "a"; "c"; "a"]) は、1を返す。

position の具体的な実装は以下の通りである。

  let rec position (x : string) (venv : string list) : int =
    match venv with
      | [] -> failwith "no matching variable in environment"
      | y::venv2 -> if x=y then 0 else (position x venv2) + 1

いよいよコンパイラの本体である。コンパイルを行う関数 C は以下のように定義される。(ここでは、数学の記法で関数が定義されているが、それをOCamlの記法に書きなおすのは難しくないはずである。)

  C(x, venv) = Access(position x venv)
  C(fun x -> e, venv) = Closure(C(e, x :: _ :: venv); Return)
  C(e1 e2, venv) = C(e2, venv); C(e1, venv); Apply
  C(let x = e1 in e2, venv) = C(e1, venv); Let; C(e2, x :: venv); EndLet
  C(let rec f x = e1 in e2, venv) = Closure(C(e1, x :: f :: venv); Return); Let; C(e2, f :: venv); EndLet
  C(n, venv) = Ldi(n)
  C(b, venv) = Ldb(b)
  C(e1 + e2, venv) = C(e2, venv); C(e1, venv); Add
  C(e1 = e2, venv) = C(e2, venv); C(e1, venv); Eq
  C(if e1 then e2 else e3, venv) = C(e1, venv); Test(C(e2, venv), C(e3, venv))

全体として、C(e, venv) の形に対する定義である。ここで、e は式 (実装上は、exp 型のデータとして表されるもの) である。また、venv は変数名のリストである。C(e, venv) の定義の右辺は、CAM の命令列（実装上は、cam_code 型のデータとして表わされるもの）である。結局、e というミニOCamlプログラムを、CAM の命令列にどう変換 (コンパイル) するかを定義したものである。(venv の初期値は空リストであり、定義の途中で補助的に使う。)
最初は、venv を無視して、C(e) の定義だと思って読んでみよう。venv を無視しても、変数の取扱いを除いてはだいたいは理解できるのではないだろうか。
たとえば、7行目の C(e1+e2, venv) は、 (1) e2 の計算に対応する命令列、 (2) e1 の計算に対応する命令列、 (3) スタックトップと上から 2 番めの値を足す Add命令、の3つから構成されている。
3行目は e1 e2 という形の式、つまり、関数適用の形の式をどう変換するかである。 (1) まず引数 e2 の計算に対応する命令例 C(e2, venv) 、 (2) 次に関数部分 e1 の計算に対応する命令列 C(e1, venv)、 (3) 最後に、スタックトップにある値 (関数部分 e1 の計算結果)を、スタックの上から2番めにある値 (引数 e2 の計算結果) に適用する Apply命令、という3つの部分から構成されている。
次に、venv の役割を考える。これは、具体例で考えるとよい。たとえば、let x=1 in let y=2 in x+y という式を変換してみると、 (計算を始めるとき、venv は空リスト[ ]とする)
```
  C(let x=1 in let y=2 in x+y, [ ])
= C(1, [ ]); Let; C(let y=2 in x+y, [x]); EndLet
= Ldi(1); Let; C(2, [x]); Let; C(x+y, [y; x]); EndLet; EndLet
```
となる。ここで、x+y という式の変換のときの venv が [y; x] になっていることに注目してほしい。これは、x+y という式を変換するとき、束縛変数 (実行時の環境に格納される変数たち) は、y と x であること、また、y が 1 番目で、x が 2 番目であることを表している。そこで、x+y の中の x を変換するときは、Access(1) に変換され、y を変換するときは、Access(0) となる。(1 番目が 0, 2 番目が 1 である。) よって、
```
  C(let x=1 in let y=2 in x+y, [ ])
= Ldi(1); Let; Ldi(2); Let; Access(0); Access(1); Add; EndLet; EndLet
```
となる。このように、変数が (実行時の) 環境の中の何番目に格納されているかを調べる目的のため、C(e, venv) の venv を使ったのである。
let 式以外でも、fun と let rec において、変数が束縛されるので、venv の部分が増加している。
fun の場合は、変数列 venv の途中に _ (underscore) という謎の変数名が出てきている。これは、「決して使われることのない変数名」を意味する。こんなことをする理由は以下の通り。CAMでは、「再帰しない関数のクロージャ」というデータ構造は持たず、「再帰関数のクロージャ」1つで両方を兼用している。そこで、再帰しない無名関数の場合も、「再帰関数の名前」に相当する部分に、何か変数名を置く必要がある。これは、実際には fun で構成される無名関数なので、この「変数名」は決して使われることはないので、ダミーの _ という変数名としている。なお、このダミーの変数をいれないと、計算が狂ってしまうので必ずいれること。
venvの初期値は [] (空の環境)である。すなわち、式 e をコンパイルするためには、 C(e, []) の計算を行なう。
上記の変換を実装するためには、上の変換関数の数学的な表記を、OCamlのプログラムとして表現しなければいけない。命令列は、命令のリストという形で実現する。また、本実験では、個々のCAM 命令名の頭に CAM_ をつけた。たとえば、let x=1 in let y=2 in x+y という式をコンパイルすると、
```
 CAM_Ldi(1); CAM_Let; CAM_Ldi(2); CAM_Let; CAM_Access(0); CAM_Access(1); CAM_Add; CAM_EndLet; CAM_EndLet
```
となる。

課題 8-3.

上記の説明を参考にして、ミニOCaml言語から CAMの機械語へのコンパイラを実装しなさい。
コンパイラが正しく変換できていることを示す例を与えて実行しなさい。
また、変換されたコードを、CAMの実装にかけて実行し、正しい答えが返ってくるかを試しなさい。

発展課題 8-3.

上記コンパイラは、「ミニOCaml言語からCAMへの変換」はきちんとやってくれるが、素朴なものであるので、「インタープリタより高速に実行されるコードへの変換」については、不満足なものである。そこで、様々な工夫について考察し、実装に取り組んでもらいたい。

定数の伝搬: let x = 10 in x+x+x といった式を let x = 10 in 10+10+10 といった式に変換するものである。なお、同じようでも、xの値が定数でないときは変換しない。たとえば、 let x = (f 10) in x+x+x といった式を let x = 10 in (f 10)+(f 10)+(f 10) といった式には変換しない。これは、以下の理由による。 (1)　そもそも (f 10) の計算に時間がかかるようなら、上記の変換は実行速度を低下させる、 (2) 将来、ミニOCaml に、副作用(print式など)を加えたら、この変換がプログラムの意味を変えてしまう危険がある。
関数のインライン化 (inlining): インライン化とは、let f x = e1 in e2 の形で、e2 の中で (f e3) の形で呼び出されているとき、この式を e1[e3/x] という式に置き換えることである。ただし、e3 は定数や関数など、いわゆる「値」を表す式とする。(e3 が「計算」を表す式であるときは、上記の定数伝搬のときに書いたことと同じ事情により、インライン化をしない。)
ここで e1[e3/x] は、式e1の中の x (の自由な出現) に、式 e3 を代入して得られる式のことであり、以下の例を参照されたい。
```
インライン化前
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y -> (f y) * y in
    g 10
gのインライン化後
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y -> (f y) * y in
    (f 10) * 10
fのインライン化後
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y -> (f y) * y in
    (10 + y) * 10
```
なお、f を先にインライン化するときには、注意しなければならい。つまり、単純に、
```
fのインライン化後(誤り)
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y -> (x + y) * y in
    g 10
```
とやってしまうと誤りになるからで、この場合は、y の変数名を変更して、
```
fのインライン化後
  let y = ... in 
  let f = fun x -> x + y in
  let g = fun y1 -> (y1 + y) * y1 in
    g 10
```
としなければならない。
インライン化のもう 1 つの注意として、(当然だが) 再帰関数は、インライン化しても消えないので、単純にやると無限にインライン化してしまうことになる、ということがある。(従って、通常、再帰関数はインライン化しない。)
その他の効率化: コンパイラでおこなわれる効率化には様々なものがあるので、コンパイラの教科書を参考にしたり自分で試行錯誤したり、各自、工夫してもらいたい。

トップ, 前へ次へ.

亀山幸義