Java では通常、JVM (Java Virtual Machine) と呼ばれる抽象化された (実在しない) 機械の上で動く機械語がターゲット言語である。この場合、実在のハードウェアでそのまま実行できないので、JVM を動かすためのインタープリタを用意する。Intelだろうと他のCPUだろうと、このインタープリタさえ用意すれば、(Javaコンパイラ自身は作り変えることなく)、どのようなマシンでも動かすことができる。
実は OCaml も、普通にコンパイルすると、本当の機械語 (Intel x86 の機械語など) のプログラムへ変換されるのではなく、OCaml 用の抽象機械の機械語に変換される。その抽象機械のインタープリタが、コンパイルされた (抽象的な) 機械語のプログラムを実行している。(もっとも、OCaml でも Java でも、本当の機械語に変換するコンパイラも存在しており、native compiler と呼ぶ。通常は、native compiler でコンパイルしたプログラムの方が、抽象機械のプログラムよりも高速に動作する。その2つの実行速度の差は、大きいこともあるし、ほとんどないこともある (プログラムの性質による))。
ごちゃごちゃ書いてきたが、今回の実験でのコンパイルは、最適化を (ほとんど) やらないので、ターゲット言語は、本当の機械語ではなく、もう少し抽象的なレベルの仮想的な機械でよい。このような機械を、抽象機械 (abstract machine) と言う。(なお、仮想機械 (virtual machine) という言葉もあり、プログラム言語の理論では「抽象機械」を、実装では「仮想機械」をよく使う。両者は似ているが、若干異なる言葉であり、ここでは「抽象機械」を使うことにする。) 抽象機械の侯補も非常に多数のものがあるが (JVM のほか、LLVM など) 本実験では、コンパイル方式を理解するという目的のため、OCaml の前身の言語で使われてきたカテゴリカル抽象機械 (CAM) とZINC抽象機械 (ZAM) を採用する。
ZAM は関数プログラムをより効率的に実行できるように CAM を改良したものであり、CAM と比べると複雑なので、まずは、本節で CAM を、次節でミニOCamlプログラムから CAM へのコンパイラを作成する。その後、ZAM と ZAM へのコンパイラを作成する。ただし、本実験では、CAM へのコンパイラ作成までを必須課題とし、ZAM と ZAM コンパイラ作成については発展課題とする。
CAMは以下の3つの要素を持つ。
なぜ、スタックのほかに環境というデータを持つかといえば、スタックの一番上にあるスタックフレームには、頻繁にアクセスするからである。インタープリタでは、lookup操作 (変数名からその値を取り出す操作) は、実行時間のかかる操作であったが、ここでは、環境としてスタックから切り離することにより、高速にアクセスできるようにする。
インタープリタにおける環境は、[("x",35);("y",true)] のように、変数名とその値の対のリストとして表現していた。一方、抽象機械では、これを [35; true]のように表現する。(ただし、もちろん、こんなリストはOCamlでは直接表現できないので、実装の上では、タグをつけて、[CAM_IntVal(35); CAM_BoolVal(true)]というようにするのだが、ここでは説明を簡単にするため、タグをはずして記述する。)
ポイントは、抽象機械での環境には、変数名がない、という点である。なぜ変数名がなくてよいかといえば、今回のコンパイラでは、「変数xが、環境の中で、何番目に格納された変数であるか」をあらかじめ計算しておき、その数(インデックス)を機械語のコードに埋めこんでおくという方式を取っているからである。従って、「変数x の変数名が "x"であった」という情報は機械語では不要になり、かわりに、「環境の 3番目の変数の値を取ってくる」といった命令を持つ。
実例を見よう。let x = 1 in let y = 2 in x + 5 というミニOCamlプログラムをコンパイルして、抽象機械で動かしているとする。この x+5 を実行しているときの(インタープリタでの)環境は、[("y",2); ("x", 1)] である。コンパイラでは、「x+5 を実行しているときに y は環境中の1番目の要素であり、x は2番目の要素である」という情報を覚えておき、対応する機械語に埋めこむ。これにより (x+5) を計算する命令例は、[Ldi(5); Access(1); Add]といった形になる。この Access(1) が、「環境の中の2番目の要素の値を取り出す」という命令である。(1番目が0であるので、2番目が1となる。) この操作が、「環境の中の"x" に対応する値を取り出す」より高速に実装できそうだ、というのは、容易に想像がつくだろう。つまり、コンパイラが頑張って計算することにより、抽象機械の実行速度を上げているのである。
このための変換は、コンパイラの一部として学生が実装するので、次の節で、もう少し丁寧な解説をつける。
type cam_value = | CAM_IntVal of int (* CAM の値に対するタグにはCAM_ をつける *) | CAM_BoolVal of bool | CAM_ClosVal of cam_code * cam_env (* 再帰関数に対応するクロージャ *) and cam_stack = cam_value list (* スタック *) and cam_env = cam_value list (* 環境は、1つのスタックフレームに相当する。 *)
type cam_instr = | CAM_Ldi of int (* CAM_Ldi(n) は、整数 n をスタックに積む (loadする) *) | CAM_Ldb of bool (* CAM_Ldb(b) は、真理値 b をスタックに積む (loadする) *) | CAM_Access of int (* CAM_Access(i) は、環境の i+1 番目の値をスタックに積む *) | CAM_Closure of cam_code (* CAM_Closure(c) は、関数本体のコードが c で、 * その環境が、現在の環境であるような関数 * クロージャを生成し、それをスタックに積む。 * 前項で説明したように変数は名前の代わりに * 環境のインデックスで参照されるので、 * このクロージャにも関数引数は含まれない。 * なお、この関数クロージャは、再帰関数で * あるとして処理される。 *) | CAM_Apply (* スタックトップの値が関数クロージャならば、 * その関数を、スタックの上から2番めにある値に * 関数適用した計算を行なう。 *) | CAM_Return (* 関数の呼び出し元に戻る *) | CAM_Let (* スタックトップの値を環境の先頭に移す (環境を拡張する) *) | CAM_EndLet (* 環境の先頭の値を取り除く *) | CAM_Test of cam_code * cam_code (* I_Test(c1,c2)は、スタックトップの値が * true ならば、コードc1 を実行し、false * ならばコード c2 を実行する。 *) | CAM_Add (* スタックトップの値とスタックの上から2番めの値を * 取り出し、その和をスタックに積む *) | CAM_Eq (* スタックトップの値とスタックの上から2番めの値を * 取り出し、それらが同じ整数であるかどうかテストし、 * その結果の真理値をスタックに積む *) and cam_code = cam_instr list (* コードは、命令の列である *)コードの簡単な例: ((1+2)+3)+4 に対応する命令列
[CAM_Ldi(4); CAM_Ldi(3); CAM_Ldi(2); CAM_Ldi(1); CAM_Add; CAM_Add; CAM_Add]
遷移前の状態 | 遷移後の状態 | ||||
---|---|---|---|---|---|
コード | 環境 | スタック | コード | 環境 | スタック |
Ldi(n) :: c | env | s | c | env | n :: s |
Ldb(b) :: c | env | s | c | env | b :: s |
Access(i) :: c | env | s | c | env | env(i) :: s |
Closure(c') :: c | env | s | c | env | <c', env> :: s |
Apply :: c | env | <c', env'> :: v :: s | c' | v :: <c', env'> :: env' | <c, env> :: s |
Return :: c | env | v :: <c', env'> :: s | c' | env' | v :: s |
Let :: c | env | v :: s | c | v :: env | s |
EndLet :: c | v :: env | s | c | env | s |
Test(c1, c2) :: c | env | true :: s | c1; c | env | s |
Test(c1, c2) :: c | env | false :: s | c2; c | env | s |
Add :: c | env | n1 :: n2 :: s | c | env | (n1 + n2) :: s |
Eq :: c | env | n1 :: n2 :: s | c | env | (n1 = n2) :: s |
この表の読み方: 各行が1つの遷移を表す。たとえば、Closure命令の遷移規則は、CAM が (Closure(c') :: c, env, s) という状態にあるとき、次の状態は、(c, env, <c', env> :: s) であることを示す。Closure(c') :: c は先頭が Closure(c') である命令列を意味する。これは、クロージャを生成してスタックに積む命令であるので、次の状態では、<c', env> というクロージャ (実験テキストの表記では CAM_Closure(c', env) となる) がスタックに積まれている。また、このとき、環境は変化しないので、env がそのまま置かれている。さらに、コード (命令列) は、先頭の Closure(c') が消費され、残りのコード c だけとなっている。他の命令の意味も同様に解釈してほしい。Access命令の遷移規則で env(i) は環境 env の i+1 番目の値を表す。
この表のApply命令の状態遷移では、関数呼び出しから戻ってきた後に実行すべき残りのコード c とそのために必要な現在の環境 env をまとめたクロージャ <c, env> を作ってスタックに退避していることに注目してほしい。逆に、Return命令の状態遷移では、スタックトップに戻り値 v が、上から2番目に呼び出し元に戻った後に実行すべきコード c' とその環境 env' をまとめたクロージャ <c', env'> が積まれていることを確認してから、環境 env' のもとでコード c' の実行を行っている。
また、Test命令の遷移規則において、遷移後のコード c1; c のセミコロン(;) はコードの連接を表している。OCamlではリストの連接にセミコロンではなくアットマーク(@) を使うので注意すること。
CAMは、上記の遷移を繰返してコード (命令列) を消費していき、コードが空になったらスタックトップにある値を最終結果として返す。ただし、その時、スタックの要素が2つ以上あったり、環境が空でなければ、何らかのエラーなので (ミニOCamlのプログラムを正しくコンパイルしたコードであれば、そのようなことは起きないはずなので)、エラーとする。
[CAM_Closure [CAM_Ldi 1; CAM_Access 0; CAM_Eq; CAM_Test ([CAM_Ldi 1], [CAM_Ldi (-1); CAM_Access 0; CAM_Add; CAM_Access 1; CAM_Apply; CAM_Access 0; CAM_Add]); CAM_Return]; CAM_Let; CAM_Ldi 10; CAM_Access 0; CAM_Apply; CAM_EndLet]
亀山幸義, 海野広志