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))

課題 8-3.

発展課題 8-3.

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

亀山幸義, 海野広志