OCaml では(Javaと同様に)、普通に ocamlc というコマンドでコンパイルすると、Intel CPU の機械語な ど のプログラムへ変換されるのではなく、OCaml 用の抽象機械の機械語に変換される。これでも十分な実行性能のことが多いが、更に高速化するために、特定のCPUの機械語をターゲット言語とするコンパイラ(native compiler)もある。
今回の実験では、個々のCPUの命令の学習はやらず、抽象的なレベルの (仮想的な)機械を想定してその機械語をターゲット言語とする。このような機械を、抽象機械 (abstract machine) と言う。(なお、仮想機械 (virtual machine) という言葉もあり、プログラム言語理論では「抽象機械」を使い、実装では「仮想機械」をよく使う。) 抽象機械にもいろいろあるが、本実験では、OCaml の前身の言語で使われてきたカテゴリカル抽象機械 (CAM) とZINC抽象機械 (ZAM) を採用する。 CAM は関数型プログラム言語のコンパイラのターゲットとして基本的なものであり、ZAM は、CAMを改良して、より効率的に実行できるようにしたものである。
本実験では、まず、CAMを学習し、ミニOCamlプログラムから CAM へのコンパイラを作成する。その後、ZAM の学習と ZAM へのコンパイラを作成する。(CAMは必須課題、ZAMは発展課題とする。)
CAMは以下の3つの要素を持つ。
インタープリタにおける環境は、[("x",35);("y",true)] のように、変数名とその値の対のリストとして表現していた。一方、抽象機械では、これを [35; true]のように表現する。(ただし、このようなリストはOCamlでは型エラーとなり表現できないので、実装上は、タグをつけて、[CAM_IntVal(35); CAM_BoolVal(true)]というようにするのだが、ここでは説明を簡単にするため、タグをはずして説明する。)
抽象機械での環境には、変数名がない。なぜ変数名がなくてよいかといえば、今回のコンパイラでは、「変数xが、環境の中で、何番目に格納された変数であるか」をコンパイル時に計算しておき、その順番(インデックス)を機械語のコードに埋めこんでおくという方式を取っているからである。従って、「変数 x の変数名が "x"であった」という情報は機械語では不要になり、かわりに、「環境の N番目の変数の値を取ってくる」といった命令となる持つ。 これは、ラムダ計算における de Bruijn index (ド・ブラウン・インデクッス)と同じ概念である。
実例を見よう。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 (* CAM_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のコード(命令列) c の実行は、以下のように定義される。 (1) CAMの初期状態は、(c,[],[])である。ただし、[]は空の環境あるいは空のスタックを表す。 (2) CAMの各状態において、上記の遷移を繰返す。 (コードを消費していく)。 (3) コードが空になったら、その時点の スタックトップにある値を最終結果として返す。 ただし、その時、スタックの要素が2つ以上(最終結果以外の値がスタックにある)あったり、 環境が空でなければ、エラーとする。
[CAM_Ldi 3; CAM_Ldi 5; CAM_Add]コード例2 (let x=3 in let y=5 in x = 5 -> false):
[CAM_Ldi 3; CAM_Let; CAM_Ldi 5; CAM_Let; CAM_Access 1; CAM_Ldi 5; CAM_Eq; CAM_EndLet; CAM_EndLet]コード例3 (TAの須永君作成、1から10までの総和):
[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]
亀山幸義