8-2. カテゴリカル抽象機械

コンパイラ作成にあたって、最初に決めるべきは、どのような言語のプログラムに変換するかである。この「行き先の言語」をターゲット言語と言う。

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つの要素を持つ。

実行時のある瞬間のCAMの状態を図で表現する。(図は、TAの宮部君作成)
この図は、スタックには、空リストや true などの値が積まれ、現在の環境は [4; true; 2; 1; <closure>; false; ...] であり、実行すべきコードが [Ldi 3; Add; Ldi 2; Add; Ldi 4; ...]である状態を示している。なお、<closure> というのは関数クロージャのことであり、実際には複雑な構造であるが、図示の都合上、単に<closure>と書いた。

CAM の「環境」: 変数名の消去

インタープリタとコンパイラの両方で「環境」がある。両者は、概念的には同じものだが、一点だけ違いがあるので説明する。

インタープリタにおける環境は、[("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" に対応する値を取り出す」より高速に実装できそうだ、というのは、容易に想像がつくだろう。つまり、コンパイラが頑張って計算することにより、抽象機械の実行速度を上げているのである。

このための変換は、コンパイラの一部として学生が実装するので、次の節で、もう少し丁寧な解説をつける。

CAM の「値」

インタープリタでは、実行時の値 (value) は、整数値、真理値、クロージャ、再帰クロージャの4種類であった。 この抽象機械でも、ほぼそれと同様であるが、「再帰関数に対応するクロージャ」さえあれば、「再帰関数でないクロージャ」は不要なので、そちらに統合する。
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つのスタックフレームに相当する。 *)

CAM の命令

命令は、実際の機械語に似せて設計しているが、一部、抽象度の高い (高級言語に近い) 命令もある。
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]

CAM の実行

コードが与えられたとき、CAM をどのように実行するか (機械の実行を「遷移(transition)」と呼ぶこともある) を見てみよう。

遷移の表
遷移前の状態 遷移後の状態
コード 環境 スタック コード 環境 スタック
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' の実行を行っている。

CAMは、上記の遷移を繰返してコード (命令列) を消費していき、コードが空になったらスタックトップにある値を最終結果として返す。ただし、その時、スタックの要素が2つ以上あったり、環境が空でなければ、何らかのエラーなので (ミニOCamlのプログラムを正しくコンパイルしたコードであれば、そのようなことは起きないはずなので)、エラーとする。

課題 8-2.


トップ, 前へ, 次へ.

亀山幸義, 海野広志