「速攻MinCamlコンパイラ概説」とMinCamlのソースコードを読んだ結果の整理がてら纏めておく。
ビルドと実行
Makefileではいくつかの変数を定義してOCamlMakefileをインクルードしている。このOCamlMakefileはOCamlによるソフトウェアの定型的なビルド手順を記述したMakefileである。FreeBSDなどのbsd.*.mkに相当する(ユーザであればportsが一番お馴染みであろう)。
OCamlMakefileが提供するターゲットとして、make byte-codeとすればコンパイルしたモジュールをバイトコードとして持つ実行ファイル、make native-codeではネイティブコードの実行ファイル、make topとすればモジュールを組み込んだ対話環境を生成する。
実行例: ./min-caml.opt test/fibとするとtest/fib.mlをコンパイルしたtest/fib.sが出来る。出力されるのはSPARCのアセンブリソースである。
メインルーチン
filesにはコマンドラインで与えられたソースファイルのリストが入る。そのファイル名それぞれについて関数fileを呼ぶ。fileでは、入力と出力をオープンして関数lexbufを呼ぶ。
lexbuf
入力を読み込み、コンパイルの各フェーズを順に実行する。MinCamlではコンパイルをデータ変換の連続したプロセスと捉える。一つ一つのフェーズがデータ変換であり、あるフェーズの出力は次のフェーズの入力となる。
全体の流れは次のようなもの。
| 字句解析 | Lexer.token |
バイト列を、トークンという単位に分割する |
| ↓ | トークン列 (呼び出し毎に新しいトークンを一つ返す関数) | |
| 構文解析 | Parser.exp |
構文木を構築する |
| ↓ | 構文木 (Syntax.t) |
|
| 型推論 | Typing.f |
構文木に現れる関数や変数の型を決定する |
| ↓ | 構文木 (Syntax.t) [型変数を型オブジェクトで置換] |
|
| K正規化 | KNormal.f |
複雑な式を単純な式に分解、全ての式の値に変数を割り当てる |
| ↓ | 中間コード (KNormal.t) |
|
| α変換 | Alpha.f |
変数名をコンパイル単位中で一意になるように付け替える |
| ↓ | 中間コード (KNormal.t) |
|
| 最適化 | Main.iter |
|
| ↓ | 中間コード (KNormal.t) |
|
| クロージャ変換 | Closure.f |
ネストした関数定義を関数とクロージャに分解する |
| ↓ | 中間コード (Closure.t)と関数(Closure.fundef)のリスト |
|
| 仮想マシンコード生成 | Virtual.f |
式を仮想マシンコードに変換する |
| ↓ | 仮想マシンコードのプログラム (SparcAsm.prog) 。浮動小数定数リスト、仮想マシンコードにした関数のリストとメインの式から成る。仮想マシンコードの型はSparcAsm.t。 |
|
| SPARCの13ibt即値最適化 | Simm13.f |
SPARCで即値オペランドにできる13bit以下の整数を即値オペランド化 (SPARCでは、それ以外の定数は演算の前に一旦レジスタにセットする必要がある) |
| ↓ | 仮想マシンコードのプログラム (SparcAsm.prog) |
|
| レジスタ割り当て | RegAlloc.f |
仮想マシンコードの変数(無限の仮想レジスタ)を、有限の実際のレジスタに置き換える |
| ↓ | 仮想マシンコードのプログラム (SparcAsm.prog) [命令オペランドの変数をレジスタに置き換え] |
|
| アセンブリ生成 | Emit.f |
最終的なアセンブリソースを出力する |
最適化は次の処理を最大1000回繰り返す。
| β簡約 | Beta.f |
値をコピーするだけの変数定義を削除し、元の変数を使うようにする |
| ↓ | 中間コード (KNormal.t) |
|
| ネストしたletの簡約 | Alloc.f |
変数の初期値を計算する式の中のletを外へ移す |
| ↓ | 中間コード (KNormal.t) |
|
| インライン展開 | Inline.f |
小さな関数の適用をその関数の式で置き換える |
| ↓ | 中間コード (KNormal.t) |
|
| 定数畳み込み | ConstFold.f |
定数同士の演算をその計算結果で置き換える |
| ↓ | 中間コード (KNormal.t) |
|
| 不要定義削除 | Elim.f |
使われない変数や関数を削除する |
| ↓ | 中間コード (KNormal.t) |
|
MinCaml言語の仕様
「概説」中の「MinCamlの構文と型」で述べられている通りだが、コンパイラを読むにあたっては特に次の点に留意。
- プログラムはただ一つの式から成る。test/ディレクトリにあるサンプルをいくつか見ればわかる通りである。教育目的と割り切った仕様である。構文解析の関数名が
Parser.expなのもこれに因る。 - GCは無い。これも割り切っている。
- 変数の値は変更されない。これはMinCamlに限らずOCamlやML等もそうである。配列や参照(MinCamlには参照はないが)も、その中身は書き換わるがそれらを指す変数は変更されることはない。
letでは変数のみ定義。let recでは関数のみ定義。無名関数はない。
OCamlメモ
MinCamlのソースコード中では「超入門」にないライブラリや構文も使われているので、重要そうなものを挙げる。私はOCamlについて「超入門」以上の知識はないので間違いもあり得る。訂正乞う。
List.iter: ('a -> unit) -> 'a list -> unit- リストの要素それぞれに与えられた関数を適用する。
もう少し馴染みのある書き方にすると、
List.iter func list(listは型'aのリスト。funcは引数を一つ受け取ってunitを返す関数) となる。早い話がSchemeのfor-each。 ignore: 'a -> unit- 引数が何であろうと
unitを返す。関数の戻り値を無視する意志を明示するために用いる。 M.empty(MinCamlのコードで定義しているものだが)- 空のマップ型オブジェクトを返す。OCamlには
Mapという型があり、モジュールMではそのキーの型をId.tに指定したものを定義していると思えばよい。C++でtemplate <typename Value> class M : public std::map<Id.t, Value> { };とするのと同じようなものだろう。
