Java では通常、JVM (Java Virtual Macihne) と呼ばれる抽象化された(実在しない)機械の上で動く機械語がターゲット言語である。 この場合、実在のハードウェアでそのまま実行できないので、 JVM を動かすためのインタープリタを用意する。 Intelだろうと他のCPUだろうと、 このインタープリタさえ用意すれば、 (Javaコンパイラ自身は作り変えることなく)、 どのようなマシンでも動かすことができる。
実は OCaml も、普通にコンパイルすると、 本当の機械語 (Intel x86 の機械語など)のプログラムへ変換されるのではなく、 OCaml 用の仮想機械の機械語に変換される。 その仮想機械のインタープリタが、 コンパイルされた(仮想的な)機械語のプログラムを実行している。 (もっとも、OCaml でも Java でも、 本当の機械語に変換するコンパイラも存在しており、native compiler と呼ぶ。 通常は、native compiler でコンパイルしたプログラムの方が、 仮想機械のプログラムよりも高速に動作する。 その2つの実行速度の差は、大きいこともあるし、 ほとんどないこともある(プログラムの性質による)。
ごちゃごちゃ書いてきたが、今回の実験でのコンパイルは、 最適化を(ほとんど)やらないので、 ターゲット言語は、本当の機械語ではなく、 もう少し抽象的なレベルの仮想的な機械でよい。 このような機械を、仮想機械(virtual machine) と言う。 (なお、抽象機械(abstract machine)という言葉もあり、 プログラム言語の理論では「抽象機械」の方をよく使う。 両者は似ているが、若干異なる言葉であり、ここでは「仮想機械」という。) 仮想機械の侯補も非常に多数のものがあるが (JVM のほか、LLVM など) ここでは、コンパイル方式を理解するという目的のため、 以下の教科書の ASEC機械を採用する。
Dowek & Levy, "Introduction to the Theory of Programming Languages" Undergraduate Topics in Computer Science, Springer, 2011.筑波大学ネットワークからは、 この本の第4章(Compilation)の電子版を入手することができる。
ASEC機械というのは変な名前であり、実は上記の教科書でもそのような 名前は使っていないのだが、この機械がもつ要素が、 以下の4つであることから、名前をつけた。
なぜ、スタックのほかに環境というデータを持つかといえば、 スタックの一番上にあるスタックフレームには、頻繁にアクセスするからである。 インタープリタでは、lookup操作(変数名からその値を取り出す操作)は、 実行時間のかかる操作であったが、 ここでは、環境としてスタックから切り離することにより、 高速にアクセスできるようにする。
インタープリタにおける環境は、[("x",35);("y",true)] のように、 変数名とその値の対のリストとして表現していた。 一方、仮想機械では、これを [35; true]のように表現する。(ただし、もちろん、 こんなリストはOCamlでは直接表現できないので、 実装の上では、タグをつけて、 [AM_IntVal(35); AM_BoolBal(true)]というようにするのだが、 ここでは説明を簡単にするため、タグをはずして記述する。)
ポイントは、仮想機械での環境には、変数名がない、という点である。 なぜ変数名がなくてよいかといえば、今回のコンパイラでは、 「変数xが、環境の中で、何番目に格納された変数であるか」 をあらかじめ計算しておき、 その数(インデックス)を機械語のコードに埋めこんでおくという方式を取っているからである。 従って、「変数x の変数名が "x"であった」という情報は機械語では不要になり、 かわりに、「環境の 3番目の変数の値を取ってくる」といった命令を持つ。
実例を見よう。let x = 1 in let y = 2 in x + 5 というミニOCamlプログラムをコンパイルして、仮想機械で動かしているとする。 このx+5を実行しているときの(インタープリタでの)環境は、[("y",2); ("x", 35)] である。 コンパイラでは、「x+5を実行しているときに y は環境中の0番目の要素であり、 x は1番目の要素である」という情報を覚えておく、対応する機械語に埋めこむ。 これにより (x+5) を計算する命令例は、 [Ldi(5); Push; Search(2); Add]といった形になる。 この Search(1) が、「環境の中の2番目の要素の値を取り出す」という命令である。 (1番目が0であるので、2番目が1となる。) この操作が、「環境の中の"x" に対応する値を取り出す」より高速に実装できそうだ、というのは、 容易に想像がつくだろう。つまり、コンパイラが頑張って計算することにより、 仮想機械の実行速度を上げているのである。
このための変換は、コンパイラの一部として学生が実装するので、 次の節で、もう少し丁寧な解説をつける。
type am_value = | AM_IntVal of int (* 仮想機械の値に対するタグにはAM_ をつける *) | AM_BoolVal of bool | AM_Closure of code * am_env (* 再帰関数に対応するクロージャ *) | AM_Env of am_env (* 「環境」を1つの値とする *) and am_env = am_value list (* 環境は、1つのスタックフレームに相当する。 *)
type instr = | I_Ldi of int (* I_Ldi(n) は、整数nを Accumulator に置く (loadする) *) | I_Ldb of bool (* I_Ldb(b) は、真理値bを Accumulator に置く (loadする) *) | I_Push (* Accumulatorにある値をスタックに積む *) | I_Extend (* Accumulatorにある値を環境に積む (環境を拡張する) *) | I_Search of int (* I_Search(i) は、環境の i 番目の値を取っきて Accumulatorに置く *) | I_Pushenv (* 現在の環境を、スタックに積む *) | I_Popenv (* スタックのトップにある環境を、現在の環境とする *) | I_Mkclos of code (* I_Mkclos(c) は、関数本体のコードが c で、 * その環境が、現在の環境であるような関数 * クロージャを生成し、それをAccumulatorに置く。 * なお、関数の引数は、変数名を除去してい * るので、このクロージャに含まれず、0番目 * の引数として指定される。 * なお、この関数クロージャは、再帰関数で * あるとして処理される。 *) | I_Apply (* Accumulatorに関数ある値が関数クロージャ * であるとき、その関数を、スタックトップ * にある値に関数適用した計算を行なう。 *) | I_Test of code * code (* I_Test(c1,c2)は、Accumulatorにある値が * true ならば、コードc1 を実行し、false * ならばコード c2 を実行する。 *) | I_Add (* Accumulatorにある値にスタックトップの値 * を加えて結果をAccumulator にいれる *) | I_Eq (* Accumulatorにある値とスタックトップの値 * が同じ整数であるかどうかをテストして結 * 果をAccumulator にいれる *) and code = instr list (* コードは、命令の列である *)コードの簡単な例: ((1+2)+3)+4 に対応する命令列
[I_Ldi 4; I_Push, I_Ldi 3; I_Push; I_Ldi 2; I_Push; I_Ldi 1; I_Add; I_Add; I_Add]もっと複雑なコード例は、後述の課題にあらわれる。
この表の読み方: 「-」の記号ではじまる各行が1つの遷移を表す． たとえば，1行目は，ASEC機械が(a,s,e,((Mkclos i), c)) という状態にあるとき， 次の状態は，(<i,e>,s,e,c) であることを示す． ((Mkclos i), c) というのは，この実験テキストの表記では， I_Mkclos(i)::c という命令列のことであり， 要するに，「命令列の先頭が I_Mkclos(i) である場合」を意味する． これは，クロージャを生成してAccumulator に置く命令であるので， 次の状態では，<i,e> というクロージャ (実験テキストの表記では AM_Closure(i,e)となる)が Accumulator に置かれている． また，このとき，スタックと環境は変化しないので，s,e がそれぞれそのまま置かれている． さらに，コード(命令列)は，先頭のMkclos(i) が消費され， 残りのコードc だけとなっている． 他の命令の意味も同様に解釈してほしい． ただし，本実験では，ミニOCaml言語にあわせて， 上記テキストのASEC機械を若干変更している．
ASEC機械は、上記の遷移を繰返してコード(命令列)を消費していき， コードが空になったら Accumulator にある値を最終結果として返す。 ただし、その時、スタックが空にもどっていなかったり、環境が空でなければ、 何らかのエラーなので(ミニOCamlのプログラムを正しくコンパイルしたコード であれば、そのようなことは起きないはずなので)、エラーとする。
また、関数 am_eval は、Accumulator の値が 0, スタックが空スタック、 環境が空環境である状態から始めて、コードを実行したときに得られる最終結果を返す関数である。
亀山幸義