MinCaml読解ノート: 仮想マシンコード生成

このフェーズではSPARCアセンブリに準じた仮想マシンコードを生成する。

「概説」によると、仮想である所以は次の2点。

• 変数(レジスタ)が無限にある
• ブランチやジャンプの代わりにif-then-elseや関数呼び出しがある

つまり、これまで変数であったものが「無限にある仮想レジスタ」という位置付けに横滑りする。 条件分岐で枝分かれする中間コードの構造は変更しない。

MinCamlのコードの規約

SPARCプロセッサの概要は既に説明したが、これからマシンコードに落とし込む上で必要となるレジスタの使い方などを整理しておく。

クロージャやタプルはヒープ上に取る。ヒープは拡大する一方で、ガベージコレクションはしない。クロージャの実体は [関数のポインタ, 自由変数1, 自由変数2, ..., 自由変数n] というレコード。浮動小数点数が入る場合、その要素がダブルワード境界になるようパディングする。タプルも同様のレコード。

MinCamlでは、次のような決まりでレジスタを使う。

スタックポインタ (reg_sp)

%i0 [Cと違う。Cは%o6がスタックポインタ]

リターンアドレス (reg_ra)

%o7 [C等と同じ]

ヒープポインタ (reg_hp)

%i1

引数

残りの汎用レジスタ全て (regs = %i2〜%i7, %l0〜%l7, %o0〜%o5)

浮動小数点数の引数

浮動小数点レジスタ全て (fregs = %f0,%f2,...,%f30)

戻り値

%i2または%f0 (汎用レジスタの最初のレジスタ)

クロージャを指すレジスタ (reg_cl)

%o5

クロージャを呼ぶときは、まずreg_clにクロージャのアドレスをセットし、その先頭にある関数へのポインタをレジスタにロードして呼び出す。

関数内では変数は全て仮想レジスタと考えるので、クロージャの自由変数は関数先頭で全部レジスタにロードしてしまう。以後はレジスタ渡しされた引数やローカル変数と区別されなくなる。

仮想マシンコードの表現

仮想マシンコードのデータ型はsparcAsm.mlで定義される。このうち、命令列のデータ型がSparcAsm.t、個々の命令がSparcAsm.expである。

type t =
  | Ans of exp
  | Let of (Id.t * Type.t) * exp * t
  | Forget of Id.t * t

Forgetは今は措くとして、命令列がLetのリストであることがより明確となった。次図のように、命令列は一連のLetと末尾のAnsによるリストとなる(ただしexpには条件分岐があり得る)。

Let-Let-//-Ans
|   |      |
exp exp    exp

SparcAsm.expにはSPARC概要で述べた命令が並べられ、それに条件分岐や関数呼び出しに対応する仮想命令が加わっている。これらの構成子は入力オペランドとなるレジスタと即値をとる。出力レジスタは命令を指すLetノードの方で決まる。

and exp =
  | ...
  | Mov of Id.t
  | Neg of Id.t
  | Add of Id.t * id_or_imm
  | Sub of Id.t * id_or_imm
  | Ld of Id.t * id_or_imm
  | St of Id.t * Id.t * id_or_imm
  | ...
  | IfEq of Id.t * id_or_imm * t * t
  | IfLE of Id.t * id_or_imm * t * t
  | ...
  | CallCls of Id.t * Id.t list * Id.t list
  | CallDir of Id.l * Id.t list * Id.t list

実装

virtual.mlで定義される関数はclassify, separate, expand, g, h, f の6つ。 中間コードから仮想マシンコードへの変換の中心はVirtual.gである。 Virtual.hは関数の本体のコード生成、Viruatl.fはプログラムを構成する各関数の本体とメインの式それぞれについて変換を呼び出す。

virtual.mlで定義されるグローバル変数dataは浮動小数点数のテーブルである。 SPARCでは浮動小数点数は即値に出来ないため、定数のテーブルを作っておいてロードする。そのためにプログラム中に出現する浮動小数点数を記録する。

大きい関数を見る前に、まずは小さいものから片付けておく。 classifyは(変数名, 型)のリストxtsについてのfold_leftで、 ただし要素の型によって違う関数を適用する(Unitの場合は何もしない)。 separateとexpandはこれを用いる。

separateは変数を整数と浮動小数点数に仕分けし、 整数型の変数のリスト, 浮動小数点数のリストの2つのリストを返す。

expandはレコード中の変数のオフセットを計算しながら処理を進めるclassifyと言える。関数にはリストの要素のほか、計算中のオフセットも渡される。オフセットの計算では浮動小数点数のダブルワード境界のアラインメントを考慮する。

Virtual.g

整数の即値や算術演算のようなものはそのまま対応する命令一つに変換する。

例:

  | Closure.Add(x, y) -> Ans(Add(x, V(y)))

浮動小数点数の場合、既に述べたように即値として扱えない。そこでラベルを生成して値と共にテーブルdataに登録し、まずはこれも新しく生成した変数(レジスタ)xにアドレスを代入、そのレジスタの指すアドレスから値をロードするという2命令に変換する。

条件分岐はClosure.tと同じ構造の仮想命令なのでそのまま。

関数やクロージャの呼び出しも仮想命令なのでほとんどそのままである。

Let((x,t),e1,e2)はe1を変換したコードの後ろにe2を変換したコードを繋げる。 e1の末尾のAnsは変数xのLetに置き換えられる。

変数の参照はmov命令になる。

Closure.MakeClsの変換

クロージャの生成(Closure.MakeCls)は、トップレベル関数と束縛する自由変数を順にレコードにストアする処理である。

ここでの核心はoffsetとstore_fvの計算である。expandはオフセットを計算しながらリスト中の変数の型に応じて与えられた関数を呼ぶから、store_fvにはストア命令のリストが返される。

このストア命令のリストが実は自由変数の並びと逆になっているところがミソである。パディングが絡むオフセット計算はレコードの並び通りの順で行う必要がある。しかし実際に動くとき、ストア命令の実行は並び順の通りでなくても構わない。この着想のお蔭でこの処理が以前の版に比べ簡単になっている。

実はこれと同じ処理はもう一つある。タプルの生成がそれで、どちらも一連の変数をレコードにストアする処理である。

Virtual.h

関数の式を仮想マシンコードに変換する。関数は最初に自由変数を全てレジスタにロードする処理を入れる。これは丁度Closure.MakeClsを変換したときの逆の処理であるが、やっていることはストア命令がロード命令になっただけでほとんど同じである。

クロージャの生成にタプル生成という同種の処理があったように、こちらも同じ構造の処理がある。Closure.LetTupleの変換がそれである。

MinCaml読解ノート: SPARC概要

次のフェーズで生成する仮想マシンコードは実際のターゲットであるSPARCの命令に近いものになる。そこで、先にSPARCアーキテクチャの概要、特にMinCamlに必要な部分を中心に整理する(全部を説明するのは大変なので)。

SPARCの概要

• RISCアーキテクチャであり、メモリのロード・ストアと演算命令が分離している。
• 命令はどれも1ワード(32bit)の固定長である。
• レジスタウィンドウという独特の仕組みを持つ(MinCamlでは使っていない)。

SPARCの大きな特徴の一つはレジスタウィンドウであるが、MinCamlでは利用しない(そのほかにもSPARCでのC関数呼び出し規約は全く無視している)。

SPARCのレジスタ

SPARCのレジスタのうち、特に関係するのは次のものである。

汎用32bitレジスタ

多数あるが、一度に見えるのは32個 (r0〜r31)

プロセッサステータスレジスタ (PSR)

フラグ、モード(カーネル/ユーザモード)、CPU優先レベルなど

プログラムカウンタ (PC)

実行している命令のアドレス

ネクストプログラムカウンタ (nPC)

次に実行する命令のアドレス (プリフェッチに使われる)

演算結果の一部を入れるレジスタ (Y)

主に整数演算で使われる(乗算の上位ワード等)

32個の汎用レジスタにはレジスタウィンドウでの役割から、g0〜g7, i0〜i7, l0〜l7, o0〜o7という別名がついている。但しMinCamlではレジスタウィンドウという仕組みを使わないので、汎用レジスタについては単に同じようなレジスタが32個あると考えて差し支えない。

SPARCの浮動小数点ユニット(FPU)には32個の作業レジスタ(f0〜f31)がある。但しMinCamlで使う倍精度浮動小数点数を表すには2つのレジスタが必要なので、一度に表現できる倍精度浮動小数点数は16個である。

特定の用途に使われる汎用レジスタ

汎用レジスタのうち、いくつかのものは特定の用途に使われることが決まっている。 関数呼び出しの際、o7はリターンアドレス、o6はスタックポインタを入れるのに使われる。

またg0は特殊なレジスタで、常に値は0である。g0への値のセットは効果がない。

命令セット

SPARCの次の6種類に大別される。

• ロード・ストア
• 算術・論理演算命令
• 制御転送命令: call、ジャンプ、トラップ(システムコール発行)
• 制御レジスタ操作 (カーネルのみ)
• 浮動小数点命令
• その他

SPARCの命令はレジスタとレジスタ(または即値)間の演算が基本である。メモリ上のデータを処理するには、一旦レジスタにロードし、処理結果を再びメモリにストアする。

命令は1ワード(32ビット)の固定長。命令の多くは13ビット符号つきの即値を持てる。

算術・論理演算は3オペランド形式で、第1・第2オペランド間を演算した結果が第3オペランドのレジスタにセットされる。

オペランドの種類

reg	レジスタ
freg	浮動小数点レジスタ
simm13	13ビット符号つき即値
reg_or_imm	レジスタまたは13ビット即値
address	アドレス。 reg, simm13, reg+/-simm13, reg1+reg2の4通りが可能。

MinCamlで利用する命令一覧

ld	[address], reg	ワードをレジスタにロード
st	reg, [address]	ワードをメモリに書き込む
ldd	[address], freg	ダブルワードを浮動小数点レジスタにロード
std	freg, [address]	ダブルワードをメモリに書き込む
nop		何もしない
set	value, reg	ワードの即値をレジスタに代入 (※合成命令)
mov	reg1, reg2	レジスタ間でデータをコピー
neg	reg1, reg2	符号を反転させる
add	reg1, reg_or_imm, reg2	足し算
sub	reg1, reg_or_imm, reg2	引き算
sll	reg1, reg_or_imm, reg2	論理左シフト
fmovs	freg1, freg2	浮動小数点レジスタ間でデータをコピー
fnegs	freg1, freg2	浮動小数の符号を反転させる
faddd	reg1, reg_or_imm, reg2	倍精度浮動小数の足し算
fsubd	reg1, reg_or_imm, reg2	倍精度浮動小数の引き算
fmuld	reg1, reg_or_imm, reg2	倍精度浮動小数の乗算
fdivd	reg1, reg_or_imm, reg2	倍精度浮動小数の除算
cmp	reg, reg_or_imm	比較
fcmpd	freg1, freg2	倍精度浮動小数の比較
jmp	address	ジャンプ
be	label	条件分岐
bne	label	〃
ble	label	〃
bg	label	〃
bge	label	〃
bl	label	〃
fbe	label	浮動小数点ユニットのフラグによる条件分岐
fbne	label	〃
fble	label	〃
fbg	label	〃
fbge	label	〃
fbl	label	〃
call	label	サブルーチン呼び出し
retl		サブルーチンからの復帰

ロード・ストア命令では、アドレスはロード・ストアするデータのアラインメント境界に合わせる必要がある。

制御転送命令(ジャンプ、条件分岐、サブルーチンコール、サブルーチンからの復帰など)では、その命令の次の命令を実行してから実際の制御が移る。 これはパイプラインで仕掛かり中の処理を無駄にしないため。 ジャンプ先はワード境界に合っていなければならない。

set命令は値によって一つまたは複数の命令に翻訳される。SPARCではワード即値をレジスタに代入する命令はない(SPARCの命令は1ワードの固定長だから、ワード即値はとれない)。その代わりレジスタの上位22ビットに即値を与えるsethiという命令があり、これと論理和orを組み合わせてレジスタへのワード即値の代入を行う。

レジスタウィンドウ

既に記したようにMinCamlでは使用しないが紹介しておく。

SPARCの汎用レジスタは多数ある(プロセッサによって異なる)が、ある時点ではそのうちの32個だけが見えるようになっている。

関数呼び出しの際にウィンドウが「スライド」し、一部のレジスタが見えなくなり、代わりに新しいレジスタが使えるようになる。この仕組みをレジスタウィンドウと呼ぶ。

このときレジスタウィンドウは一部がオーバーラップして、いくつかのレジスタは呼び出し元でも呼び出し先でもアクセスできる。関数呼び出しではそのレジスタを利用して引数を渡す。

この仕組みを反映し、汎用レジスタの32個は次のように4種類に分けられそれぞれ別名がついている。

• グローバル(8) (どの関数からも見える) : g0〜g7 (r0〜r7)
• 出力 (8) (関数を呼び出すときに引数を入れる): o0〜o7 (r8〜r15)
• ローカル (8) (関数内の計算のみに利用): l0〜07 (r16〜r23)
• 入力 (8) (自分に渡された引数が入っている): i0〜i7 (r24〜r31)

グローバルの8個を除く24個がウィンドウとなる。関数呼び出しでは16個分スライドさせるので、8個がオーバーラップする。この8個は呼び出し元から見るとo0〜o7、呼び出し先の関数ではi0〜i7になる。

関数呼び出しのネストが深くなりレジスタが不足すると、割込みが発生してカーネルに制御が移り、スタック上に書き出してレジスタを空ける。

資料

SPARC V8、V9のアーキテクチャマニュアルはweb上で公開されている。大学等のwebで解説ページを見付けることもできる。

• SPARC仕様、技術書 (sparc.org)
• SPARCアセンブラの基礎 (東工大の千葉先生による)

MinCaml読解ノート: クロージャ変換

関数を、環境をとるクロージャとトップレベル関数とに仕分ける。 これまでで一番大きそうなフェーズである。

MinCamlにおけるクロージャの表現

このフェーズでは、これまで式中にあった関数定義を全て分離してトップレベルに持って来る。

関数が自由変数を参照しない場合は環境を無視してそのままトップレベルに持ってこれる。 一方、自由変数にアクセスする場合は、トップレベルに持ってきた関数だけでは意味がなく、関数と環境のセットで表すクロージャとして扱わなければならない。

MLでは変数の値は変更されない点をうまく利用し、MinCamlでは環境フレームを持たずにクロージャごとに自由変数のコピーを持たせることで実現する。 つまりクロージャは、静的なコードであるトップレベル関数と、自由変数の束縛のリストとして表現される。 トップレベル関数本体をf、その中で使われる自由変数をv₁, ..., v_nとすると クロージャの実体は{f, v₁, ..., v_n}というレコードとなる。

式やプログラムを表す型

プログラムの表現もここで変わる。

これまでは一つの式をもってプログラムとしていたが、全ての関数をトップレベルに移動し、複数のトップレベル関数のリスト+メインの式という形に分解される。 それを表すのが型Closure.progである。

式(中間コード)を表す型はKNormal.tに替えてClosure.tを使用する。

その大きな違いはLetRecが消えてクロージャ作成を示すMakeClsが登場し、関数適用がトップレベル関数の適用AppDirとクロージャの適用AppClsに細分化される点である。

また、一部でId.tに替えてId.lを使用する。これはトップレベル関数や外部の変数・関数のラベルとして最終的には定数になる性質のものである。一方Id.tのまま残ったものは全て一時的な変数となる。

KNormal.ExtFunAppはAppDirに吸収される。 外部関数もプログラム内で定義した関数も同じId.lとして扱うためである。

関数を表す型はClosure.fundefである。これの要素formal_fvがクロージャが持たされる自由変数のリストである。

変換の実装

クロージャ変換のエントリポイントであるClosure.fは、モジュール内変数toplevelを空のリストで初期化してClosure.gを呼ぶ。このリストはトップレベル関数を記録するのに使われる。

Closure.gが本体である。ほとんどのパターンではそのままKNormal.tからClosure.tへ写すだけの単純さだが、LetRecとAppの場合は案の定大仕事となる。

let rec g env known = function
  | ...

まずは簡単な関数適用の方から見てゆく。knownは自由変数を使わない関数の集合である。 そのような関数ならAppDirに、そうでなければAppClsに置き換える。また関数を示す変数をラベルに変換する。

  | KNormal.App(x, ys) when S.mem x known ->
      Format.eprintf "directly applying %s@." x;
      AppDir(Id.L(x), ys)
  | KNormal.App(f, xs) -> AppCls(f, xs)

LetRecの場合がややこしい。 let recで定義する関数本体を変換し、クロージャであればMakeClsにしなければならない。

最初に定義する関数が自由変数を持つかどうかを調べて関数かクロージャかを決め、然る後に関数本体と式e2を変換すればよさそうに思えるが、そうはなっていない。何故だろうか?

関数本体を変換する際には、そこで定義する関数の呼び出し(再帰呼び出し)があった場合にAppDirを使うかAppClsを使うかを決定しなければならない。この判断は、関数が自由変数を使うかどうかで決まる。自由変数のない関数の呼び出しはAppDirで問題ない。

LetRecの場所にMakeClsを入れてクロージャを生成するかどうかは、それに加えて式e2の中で関数が変数として参照されるかにも左右される。 一旦変数となると、それを適用する側はクロージャと関数の区別がつかないため、扱いをクロージャとしての扱いに統一せざるを得ない。そこで自由変数のないものでも、自由変数が0個のクロージャとする。このことはClosure.tにも表れていて、ラベルだけでは値として扱うことはできず、値となり得るのはUnit, Int, Float, Tuple, それにMakeClsで変数に代入されるクロージャだけとなっている。トップレベル関数を受渡しするには自由変数0個のクロージャとして扱うよりないわけである。

自由変数を調べるには、Closure.fvという関数を用いる。既に類似の目的のKNormal.fvがあるが、ここでそれでは不足である。その理由はラベルと変数を区別して扱わなければならないことによる。関数適用に現れるトップレベル関数のラベルは変数ではない。一方、単独で参照された場合(Var(x))は変数でありクロージャである。

このような理由から、判定するにはまず関数本体をClosure.tに変換する必要があるという、卵が先か鶏が先かにも似た問題が発生する。 そこで、まずとにかく一回変換して自由変数があるか調べ、その結果に基づいて(必要があれば)変換をやり直すという手順を踏むわけである。

猶、自由変数を持たない関数でもクロージャを生成する必要のある例がtest/cls-bug.mlにある。

let rec f x = x + 123 in
let rec g y = f in
print_int ((g 456) 789)

このプログラムではf自身は自由変数を使わないが、gがfを値として返すためにクロージャになる。gを呼び出す側ではクロージャと関数の区別がつかないので、戻り値は全てクロージャとして扱うためである。

クロージャ生成にどのような情報が持たせられるかは、MakeClsに与えられるパラメータzsを計算する式をみればわかる。またzsからztsが計算され、クロージャを生成するかどうかによらずトップレベル関数をリストtoplevelに追加する。

let zs = S.elements (S.diff (fv e1') (S.add x (S.of_list (List.map fst yts)))) in (* 自由変数のリスト *)
let zts = List.map (fun z -> (z, M.find z env')) zs in
toplevel := { name = (Id.L(x), t); args = yts; formal_fv = zts; body = e1' } :: !toplevel; (* トップレベル関数を追加 *)
let e2' = g env' known' e2 in
if S.mem x (fv e2') then (* xが変数としてe2'に出現するか *)
  MakeCls((x, t), { entry = Id.L(x); actual_fv = zs }, e2')
else
  e2'

toplevelに追加されるトップレベル関数にはformal_fvとして自由変数のリストが入る。クロージャによって渡される「隠れ引数」である。一方、MakeClsに渡す情報のactual_fvはそれらの自由変数のクロージャ生成時における束縛である。

あとは、外部変数・外部関数も見ておこう。変数名をラベルに変換している。関数名は"min_caml_"というプレフィクスが付けられている。

  | KNormal.ExtArray(x) -> ExtArray(Id.L(x))
  | KNormal.ExtFunApp(x, ys) -> AppDir(Id.L("min_caml_" ^ x), ys)

MinCaml読解ノート: 不要定義削除

このフェーズでは使われない変数や関数の定義を削除する。

let x = e1 in e2 という定義を削除するには2つの条件を調べればよい。

• 使われていないか? ……e2にxが出現していなければ使われていない。
• 副作用がないか? ……e1に副作用がなければ削除できる。配列の破壊的変更があれば明らかに副作用がある。他の関数を呼んでいる場合その先はわからないので副作用がないとは言い切れない。

両方の条件を満たせば、Letを取り払ってe2に置換できる。

まずここで使われるKNormal.fvから見てゆく。この関数は式を再帰的に調べて、式に出現する自由変数の集合を返す。つまり式の内部で束縛した変数は含まない(調べる式はα変換済なので束縛変数を含もうが含むまいが影響はないのだが)。

変数の集合はS.tで表す。これは標準ライブラリのSetを要素にId.tをとるよう特殊化したものである。

Elim.fではこの関数を使って、変数が使われるかどうかを調べることになる。

次に副作用をチェックするElim.effectをみる。変数の値を計算する式e1を取り、その中に破壊的変更や関数呼び出しがあれば真を返す。非常に簡単である。

let rec effect = function
  | Let(_, e1, e2) | IfEq(_, _, e1, e2) | IfLE(_, _, e1, e2) -> effect e1 || effect e2
  | LetRec(_, e) | LetTuple(_, _, e) -> effect e
  | App _ | Put _ | ExtFunApp _ -> true
  | _ -> false

内部関数の呼び出しの方は、もう少し頑張ればその先で本当に副作用があるかどうかを調べられる筈である。副作用のある関数の集合を記録し、LetRecで関数を定義する際に副作用があるものは追加すればよい。

不要定義削除の本体はElim.fである。

letの場合、式e1, e2を処理した後、e1に副作用がなく、e2で変数が使われなかった場合はめでたくLetを削除できる。

  | Let((x, t), e1, e2) ->
      let e1' = f e1 in
      let e2' = f e2 in
      let live = fv e2' in
      if effect e1' || S.mem x live then Let((x, t), e1', e2') else
      (Format.eprintf "eliminating variable %s@." x;
       e2')

let recの場合、定義した関数が式e2の中で使われていなければLetRecを削除する。変数と違って値を計算する式はないので副作用は関係せず、使われていなければ削除できる。

OCamlメモ

S.empty

空の集合(S.t)を返す。S.tはs.mlで定義される型で、標準ライブラリのSetをId.tを要素に特殊化したものである。

S.add item set

setにitemを加えた新しい集合を返す。

S.remove item set

setからitemを除いた新しい集合を返す。

S.union set1 set2

和集合を作る。

S.singleton item

要素を一つだけ含む集合を作る。

S.mem item set

集合に要素に含まれていれば真を返す。

MinCaml読解ノート: 定数畳み込み

定数畳み込みは次のような結果がわかっている式をコンパイル時に計算した値に置き換えてしまう処理である。

let x = 1 in
let y = 2 in
x + y

MinCamlでは、演算のオペランドの両方の値が定数である場合にその計算結果で置き換えることだけを実装している。だから

let x = 3 in
let y = 7 in
let x + a + y

のような場合を10+aにはできない。

まず、小さな関数から見ていく。

memi, memf, memtは変数xと環境envを受け取り、xが登録されていて値が即値のInt/Float/タプルであれば真、それ以外の場合は偽を返す。

findi, findf, findt はxの値が即値のInt/Float/タプルであれば値を返す。xが見付からないか型が合わない場合はエラーとする。

次に定数畳み込みの本体ConstFold.gである。

ソースコードと順番が前後するが、letではまず代入する式を定数畳み込みし、変数とその式を環境に追加する。

変数の評価はそのまま即値に置き換える。ただしIntの場合のみで、FloatやTupleの場合はコメントアウトされている。これらは整数と異なり最終的にメモリ上に置かれるデータとなるため重複を嫌ったものであろうか。代償として畳み込みの効率は少し落ち、(let x=1.0 in x) +. (let y=2.0 in y)のような式を一回では3.0と計算できず、最適化フェーズを2回通る必要がある。重複した浮動小数点数は後の仮想マシンコード生成にて省かれるので、ここでFloatの処理を避ける必要はないように思えるのだが。

整数の演算、浮動小数の演算は、全ての項が定数なら計算した即値で置換。

比較による条件分岐では、比較が即値同士なら真偽が確定するので生きる方の式だけを残す。

LetTupleではタプルの中身がわかっている場合はタプルを分解し、要素の数だけLetを並べた形に変換する。同時にletの場合と同様変数と式を環境に追加する。

例えば、t=(a,b,c)とわかっているとき let (x,y,z)=t in e は let x=a in let y=b in let z=c in e となる。

MinCaml読解ノート: インライン展開

小さい関数の関数適用をその本体で置き換える。 「概説」の説明の通りで、難しい点は特にない。

変数thresholdはインライン展開するかどうかを決める関数の大きさの閾値で、-inlineオプションによりセットされる。

関数sizeは式の大きさを計算する関数で、単にKNormal.tのノードの数を数え上げて決めている。

関数gがインライン展開の本体である。インライン展開する関数の表(最初は空)と式を受け取りインライン展開した式を返す。 関数定義のKNormal.LetRecと関数適用のKNormal.Appに対する処理が要。

KNormal.LetRecでは関数本体の大きさをsize関数で計算し、threshold以下であれば関数を表に登録する。

KNormal.Appは適用する関数が表に登録されているものなら、展開する関数本体の式で置き換える。 このとき、「仮引数を引数で置換」「本体の式を複製することになるため、α変換で変数名を一意なものに付け替え」をAlpha.gを使って一度に行う。Alpha.gは変換する変数名の表の初期値を外部から与えられるのでこのような流用が利く。

OCamlメモ

List.fold_left 関数 初期値 リスト

初期値をX、リストの要素をx₁...x_n、関数を中置演算子*で表すとして、
(((X * x₁) * x₂) * ... * x_n)
を計算する。 fold_leftという名前はこの計算が左結合であることによる。 これを右結合にしたfold_rightというのもあり、向きの違いを反映して型が少し異なる。

# List.fold_left (fun x y -> x@[y*2]) [0] [1;2;3];;
- : int list = [0; 2; 4; 6]
# List.fold_right (fun x y -> (x*2)::y) [1;2;3] [0];;
- : int list = [2; 4; 6; 0]

List.fold_left2 関数 初期値 リスト1 リスト2

List.fold_leftに与える引数がx_iではなくリスト1の要素x_iとリスト2の要素y_iの2つになったもの。上に倣って書き表すと
(((X * (x₁,y₁)) * (x₂,y₂)) * ... * (x_n,y_n))
のような感じになる(実際にタプルを構成するわけではないが)。

# List.fold_left2 (fun x y z -> x@[(y,z)]) [(0,0)] [1;2;3] [4;5;6];;
- : (int * int) list = [(0, 0); (1, 4); (2, 5); (3, 6)]

MinCaml読解ノート: ネストしたletの簡約

K正規化で述べたように、ここまでの中間コードはネストしたletのリストになっている。 このネストを開いて平たい一列のリストに直す。

そのために、letが入れ子になっている箇所で図のような繋ぎ替えを行う。

このための処理が見慣れないと少しややこしい。 Assoc.fの中で内部定義された関数insertは、入れ子になったリストを末尾の手前までそのまま複製しながら進む。末尾の非letの要素eに代わり、eを持ち元のリストの続きに接続するLet(xt, e, f e2)を入れる。

let rec f = function
  | [...]
  | Let(xt, e1, e2) ->
      let rec insert = function
	| Let(yt, e3, e4) -> Let(yt, e3, insert e4)
	| LetRec(fundefs, e) -> LetRec(fundefs, insert e)
	| LetTuple(yts, z, e) -> LetTuple(yts, z, insert e)
	| e -> Let(xt, e, f e2) in
      insert (f e1)

※この処理では非末尾の条件分岐はletの要素になるため厳密には完全にネストがなくなるわけではない。またこの後のインライン展開で再びネストが発生するので、以後もネストしたリストとして扱うことに変わりはない。

MinCaml読解ノート: β簡約

MinCamlでβ簡約と呼んでいるのは、変数の定義が単に別の変数のコピーであるような変数を元の変数で置き換えることである。 つまり let y = x in ... のような変数yを使う箇所を全て元の変数xで置き換える。

変数を別の変数に置き換えるという処理はα変換と似通っており、コードもほとんど同じである。 違いはletのときに変数の値を与える式が変数(KNormal.Var)である場合に限り変換を登録する点等である。

let rec g env = function
  | Add(x, y) -> Add(find x env, find y env)
  | Sub(x, y) -> Sub(find x env, find y env)
  | [...]
  | Let((x, t), e1, e2) ->
      (match g env e1 with
      | Var(y) ->
	  Format.eprintf "beta-reducing %s = %s@." x y;
	  g (M.add x y env) e2
      | e1' ->
	  let e2' = g env e2 in
	  Let((x, t), e1', e2'))
  | [...]

MinCaml読解ノート: α変換

プログラム中の束縛変数の名前を付け替えて一意な名前にする。

Alpha.findが付け替えた変数名の変換を行う関数である。envに登録されていなければ外部変数として変換せずにそのまま返す。

let find x env = try M.find x env with Not_found -> x

本体はAlpha.gで、この関数は環境(付け替え前と後の変数名の対応表)と式を受け取る。基本的には変数名をfind x envで置き換えるだけである。

letでは新しい変数名を生成して置き換え、元の変数名との対応を環境に追加して残りの式を変換する。let recの場合も同様である。let recではそれぞれの関数の引数名も変換し、関数の式をα変換するときに引数の変換も加えた環境を渡す。

let rec g env = function
  | Add(x, y) -> Add(find x env, find y env)
  | Sub(x, y) -> Sub(find x env, find y env)
  | [...]
  | IfEq(x, y, e1, e2) -> IfEq(find x env, find y env, g env e1, g env e2)
  | IfLE(x, y, e1, e2) -> IfLE(find x env, find y env, g env e1, g env e2)
  | Let((x, t), e1, e2) ->
      let x' = Id.genid x in
      Let((x', t), g env e1, g (M.add x x' env) e2)
  | [...]

MinCaml読解ノート: K正規化

K正規化の意味

K正規化は、複雑な計算の途中結果全てを変数として定義する。 これによって複雑な式が一連の単純な式に分解され、プログラムは順序づけられた単純な計算の繰り返しに姿を変える。

K正規化後の型であるKNormal.tにもそれが表れている。

type t =
  | Add of Id.t * Id.t
  | Sub of Id.t * Id.t
  | ...
  | IfEq of Id.t * Id.t * t * t
  | IfLE of Id.t * Id.t * t * t
  | Let of (Id.t * Type.t) * t * t
  | LetRec of fundef * t
  | LetTuple of (Id.t * Type.t) list * Id.t * t

全ての演算や関数適用は、式KNormal.tではなく変数Id.tをオペランドにとるようになり、KNormal.tをとるのはlet類と条件分岐のみである。 つまり、KNormal.tによる表現はletをノードとするリストとなる。

「速攻MinCamlコンパイラ概説」にある例では、a+b+c-dは次のようになる。

let tmp1=a+b in
let tmp2=tmp1+c in
tmp2-d

※正確には、MinCamlのK正規化の実装では a+b+c-dは

let tmp2 =
  let tmp1 = a+b in
  tmp1+c in
tmp2-d

に変換される。これは次のように図示できる。青い破線と数字は実行順を示す。

データ構造としては完全な一次元ではないが、これは入れ子になったリストと見ることが出来る。計算とその順序の点では先の表現と等価である。 簡単な変形を施すと先の表現のような入れ子のないリストに出来、後のネストしたletの簡約フェーズではそれを行う。

K正規化の実装

kNormal.mlで定義される関数はfv, insert_let, g, f。このうちfvは当面使われない。fはgを呼ぶだけのもので、K正規化の本体はKNormal.gである。

KNormal.gは型環境と式(Syntax.t)を取り、K正規化した式(KNormal.t)と型を返す。 最も基本的な単項演算の場合はこのようになる。

  | Syntax.Neg(e) ->
      insert_let (g env e)
	(fun x -> Neg(x), Type.Int)

insert_letはオペランドの式で変数を定義するLetノードを作り、演算ノードをそれに繋げる。ただし演算ノードはオペランドの変数名が不明では作れないので、insert_letに渡すのは演算ノードではなくそれを作るクロージャである。

insert_letでは受け取った式を調べ、単なる変数の場合はその変数をそのまま演算に渡し、letを作らない。この節約をしないと項の数だけ無駄にletが増える。

二項演算子はオペランドが2つあるのでinsert_letを重ねる。Letノードが2つ続き、その次にAddノードが来る形になる。

  | Syntax.Add(e1, e2) ->
      insert_let (g env e1)
	(fun x -> insert_let (g env e2)
	    (fun y -> Add(x, y), Type.Int))

この変換の結果は次のようになる。

Let [x] ---- Let [y] ---- Add(x,y)
|            |
(g env e1)   (g env e2)

その他、関数適用等の場合もこれと同様に出てくる式の数だけletを並べ最後にApp等のノードが来る形になる。

「ついで」の変換

「概説」にある通り、ブール値は整数の1と0に置換される。

KNormal.tでは比較・論理演算とif文を条件分岐 IfEqとIfLE による表現に置き換える。

直接KNormal.IfEq、KNormal.IfLE に変換できるのは、Syntax.If(Syntax.Eq(e1,e2), e3, e4)のようにif文の中に比較がある場合である

それ以外のif文の扱いが面白い。Syntax.tによる別の表現に言い換えた上で、もう一度KNormal.gにかけるのである。つまりLispでいうマクロのようにして実現している。

例えば、条件式が比較ではないif文Syntax.If(e1,e2,e3)は、Syntax.If(Syntax.Eq(e1, Syntax.Bool(false)), e3, e2)に言い換える。 また、単独で出現する比較は、その比較を行ってtrueまたはfalseを返すif文に態々変換されるという具合である。

OCamlメモ

fst: 'a * 'b -> 'a

二つの要素の組をとり、最初の要素を返す。早い話がLispのcar。 案の如くcdrに相当する二つ目の要素を返すものもあり、そちらはsndという。

MinCaml読解ノート: 型推論

型推論は変数や関数の型を推定する作業であり、既に述べたように構文木の中のType.Varの値を決めていく。

型推論の中核はTyping.gとTyping.unifyである。 Typing.gは型環境env (変数の名前→変数の型の写像)と式eを受け取り、式eの型を返す。

Typing.unifyは二つの型を受け取り、それらを一致させる。つまり一方が未定の型変数であれば型が決定する。双方が既知の型であれば一致しない場合にはエラーとなる。

この二つが互いを呼んで再帰的に式や式の内部の変数の型を推論する。

コードにはあまり直接表れないが型推論には自然ある程度の方向がある。特定の型を対象とする演算子からオペランドの型が決まり、変数定義では値から変数の型が決まる。関数本体の式や引数から関数の型が決まり、戻り値の型が決まるという具合である。

Typing.g

定数項であれば型はわかっているのでそれを返す。

not, -, +, *, /, -., +., *., /. では演算子から型が決定できるので、オペランドの型を推論して、その型とunifyする。

==, <= では直ちにオペランドの型はわからないが両辺の型は同じ筈なので、それぞれの推論した型同士をunifyする。式の型としてはType.Boolを返す。 それ以上は両辺の型をチェックしないので、例えばtrue < falseのような式をこの時点でエラーにすることはできない。

if式では、条件の式をType.Boolとunify。then式とelse式をそれぞれ型推論してunifyする。またその型をif式の型として返す。

letでは、=の右辺つまり値の式を型推論したものと型変数をunifyする。これで型変数の中身が決まる筈である(別の型変数を指すだけかも知れないが)。その後、変数名と型変数の組を型環境に追加して、inの後に続く式を型推論する。

let recの場合、まず関数名と関数の型変数を環境に追加する。inに続く式はこの環境を使って推論する。関数本体の式はこれに引数とその型を追加した環境を使って型推論する。

let recの型推論で関数の型変数がどのようになるかの例を挙げる。

let f x = x + 3 in f 4

この式をTyping.gにかけて型推論すると、構文木とその中の型変数は次のようになる。

Syntax.LetRec
 ([{Syntax.name =
     ("f",
      Type.Var
       {contents =
         Some (Type.Fun ([Type.Var {contents = Some Type.Int}], Type.Int))});
    Syntax.args = [("x", Type.Var {contents = Some Type.Int})];
    Syntax.body = Syntax.Add (Syntax.Var "x", Syntax.Int 3)}],
 Syntax.App (Syntax.Var "f", [Syntax.Int 4]))

ついでにletの場合も見てみよう。

let x = 1 in x + 2

この式は次のようになる。

Syntax.Let (("x", Type.Var {contents = Some Type.Int}), Syntax.Int 1,
 Syntax.Add (Syntax.Var "x", Syntax.Int 2))

変数の型推論では、束縛変数であればenvに含まれる筈であるので対応する型変数を返す。envに見付からない場合は外部変数の表であるextenvを捜す。それで見付からない場合は未定義となるが、MinCamlでは宣言のない外部変数を許しており、新しく型変数を与えてextenvに追加する。

関数適用の型推論。関数定義のみでは必ずしもその戻り値は決まらない為、実際に適用して初めて決まる。そこで、その適用における関数の型を表現した値(戻り値の型は未定なので新しい型変数を使う)と、g env eが返す関数の型変数をunifyする。

ここでMinCamlの弱点の一つに遭遇する。関数の型を示す型変数がそのまま使われているため、一度適用でunifyされてしまうと関数の型が固定されてしまい、別の型で呼べなくなる。つまりMinCamlでは関数に多相性がない。例えば次の式は型推論の段階でエラーになってしまう。

let rec f x y = if x < y then 1 else -1 in
print_int (f 3 4) ; print_int (f 2.0 1.0)

回避するには次のように型毎に別々の関数を定義する必要がある。

let rec fi x y = if x < y then 1 else -1 in
let rec ff x y = if x < y then 1 else -1 in
print_int (fi 3 4) ; print_int (ff 2.0 1.0)

型推論がありながらこれでは少し寂しい。言語としてバランスに欠ける。

Typing.unify

2つの型を突き合わせて両者が一致するか調べ、また一致するように型変数を決定する。 つまり片方が未定の型変数であればもう一方の式を代入する。ここが型変数の代入が行われる唯一の箇所である。

このとき、代入する式の中にその型変数が出現していないか調べて循環の発生を防ぐ(と「概説」にはある。だが実際に型が循環するような式はあり得るだろうか?)。

また、両者が既知の型で一致しない場合は例外を発生させる。

Typing.f

Typing.fは型推論のメインルーチンであり、受け取った構文木をTyping.gに渡して型推論する。 その結果とType.Unitをunifyしているのは単なるお節介。様々な式を通して実験するには、このunifyする部分の代わりにコメントアウトされている警告を出力するだけの式を生かすとよい。

Typing.deref_typは型変数をその中身で置き換える関数である。型変数が別の型変数を指している場合はさらにその中身を採る。外部から呼ばれるときに受け取る引数はType.Varであるが、その中身について再帰的に処理するためType.tの全ての型を扱う。

Typing.deref_termは構文木中の型変数を全てその中身で置き換える。

こうして最終的には型変数は実際の型で置き換えられる。

OCamlメモ

例外

例外の宣言: exception 名前 [of 型]

例外の送出: raise 例外

例外の捕捉:

try 式 with 
  パターン -> 式
| パターン -> 式

failwith 文字列

例外Failureを発生させる。

Format.eprintf

エラー出力する関数。

M.add key value map

mapにkeyとvalueの組を追加する。

M.add_list (key,value)のリスト map

mapに一連の組を追加する。

List.map func list

listの各要素にfuncを適用した結果のリストを返す。

List.iter2 func list1 list2

2つのリストから引数を一つずつとり2引数の関数funcを適用することを繰り返す。

List.exists elem list

リスト中に要素があるか調べる。

MinCaml読解ノート: 構文解析

MinCamlとは関係ないが、祝、サッカー日本代表ワールドカップ予選突破。素晴らしい。

構文解析ではトークン列を受け取って構文木を構築する。 ソースコードとしてはparser.mlyに文法を記述。ocamlyaccというツールを使い構文解析器を生成する。

parser.mlyからアクションを省略してMinCamlの文法を拡張BNFのように書くと次のようになり、非常に短い。

「速攻MinCamlコンパイラ概説」で説明されているが、simple_expとexpの違いは括弧で囲まなくても関数の引数になれるか否か。この区別が必要なのは、MLでは単にスペースで区切って並べるだけで関数適用になるためである。

simple_exp:
| ( exp )
| ()				/* Unit */
| true
| false
| integer
| float
| identifier
| simple_exp .( exp )		/* 配列の参照 */

exp: /* 一般の式 */
| simple_exp
| not exp
| - exp
| exp + exp
| exp - exp
| exp = exp
| exp <> exp
| exp < exp
| exp > exp
| exp <= exp
| exp >= exp
| if exp then exp else exp
| -. exp
| exp +. exp
| exp -. exp
| exp *. exp
| exp /. exp
| let identifier = exp in exp
| let rec fundef in exp
| let ( identifier { , identifier }+ ) = exp in exp
| exp simple_exp +		/* 関数適用 */
| exp { , exp }*		/* タプル */
| simple_exp . ( exp ) <- exp	/* 配列への代入 */
| exp ; exp			/* 順序評価 */
| Array.create simple_exp simple_exp	/* 配列の作成 */

fundef:
| identifier { identifier }+ = exp	/* 関数名 引数リスト 本体 */

integer:
|  -?[0-9]+
float:
|  -?[0-9]+{.[0-9]*}?{[eE][+-]?[0-9]+}?
identifier:
| _
| [a-z][a-zA-Z0-9_]*			/* 但し予約語を除く */

整数の乗算と除算がないことに気付く。

それはさておき、この構文解析器で生成する構文木のデータ型はSyntax.tである。

type t =
  | Unit
  | Bool of bool		← 定数値
  | Int of int
  | Float of float
  | Not of t			← 単項演算子。型がtというのはオペランドが式。
  | Add of t * t		← 二項演算子
  | [...]
  | Eq of t * t
  | LE of t * t
  | If of t * t * t		← 条件、THEN式、ELSE式
  | Let of (Id.t * Type.t) * t * t	← 変数(名前(Id.t)、型(Type.t))、値、式
  | Var of Id.t			← 変数の参照
  | LetRec of fundef * t	← 関数定義、メインの式
  | App of t * t list		← 関数、引数リスト(t list)
  | Tuple of t list
  | [...]
and fundef = { name : Id.t * Type.t; args : (Id.t * Type.t) list
↑ 構文木で関数を表すデータ型。name: 名前と型。args: 引数(名前と型)リスト

先に見た文法と異なり、Syntax.tには比較演算子はEqとLEしかない。残りの<>, <, >, >=は、これら2つとNotの組み合わせで表現される。

MinCamlでの型を表すデータ型はType.t。基本のデータ型はUnit, Bool, Int, Floatのみで、これに関数Fun、タプルTuple、配列Array、それに変数や関数の型を表すための型変数Varが加わる。

変数や関数の型は構文解析の時点では定まらず、次の型推論のフェーズで決定される。そのためType.VarはType.tのオプション型への参照を取る構成子とされ、書き換えが可能である。構文解析中はaddtypを通して作成され、初めはNoneで初期化され型が未定であることを示す。型推論の段階で型が決定すればこれが書き換えられる。最終的には以後の扱いを簡単にするために、型変数を型そのもので置き換えることになる。

猶parser.mly中に出てくるVarはSyntax.Var(変数の参照を示す)のことであって、Type.Varではない。

構文解析器のアクションではSyntax.tの構文ノードを作るだけである。

スタート規則がexpであるから、このコンパイラは式を一つだけしか読まない。だから変数や関数を定義してそれらを使ったプログラムを書くためには、letやlet recを延々と入れ子にし一つの式として構成することになる(test/にあるサンプルを参照)。

OCamlメモ

オプション型: 'a option

型'aの何れかの値、または無効値(None)になるような型。任意の型について自動で定義される。他の言語で、値が無効であることを示すためにnullやnilを使うのに似ている。有効な値で構成するにはSomeというデータ構成子を使う。
オプション型の定義は書くとすれば次のようになる。

type 'a option = None | Some of 'a

レコード型

複数のフィールドを持つ。早い話が構造体である。type 型名 = { 名前1 : 型; 名前2 : 型; ... }という形で宣言する。プログラム中で値を作るには{ 名前1=値; 名前2=値; ... }と書く。パターンマッチでは { 名前1 = 変数; 名前2 = 変数; ... } -> 式のように書くことができる。

MinCaml読解ノート: 字句解析

字句解析器は、lexer.mllというファイルに記述してocamllexというツールで生成する。このツールは名前の通りlexのOCaml版である。

lexer.mllでは、tokenとcommentの2つのスキャナが定義されている。

MinCamlの文法は素直な文脈自由文法で、tokenスキャナでは予約語を認識して対応するトークンを返す。

例外はコメントの処理で、(*という文字列が来るとスキャナをcommentスキャナに切り替えて読み飛ばす(アクション部で更にスキャナを呼ぶというのは今読んだ文字列を読み飛ばすことを意味する)。commentスキャナでも(*を認識していて、これが来るとcommentスキャナを二度呼ぶ。これはMinCamlではコメントのネストを許しているためで、一回目でネストしたコメントを読み飛ばし、次に現在のコメントの残りを読む。

トークンは構文解析器を記述するparser.mly中の%token命令で定義される。構文解析器を生成するocamlyaccというツールにより、それらをデータ構成子とする型Parser.tokenが定義される。

parser.mlyでのトークンの定義:

%token <bool> BOOL
%token <int> INT
%token <float> FLOAT
%token NOT
%token MINUS
%token PLUS
...

ocamlyaccにより生成されるparser.mliでのデータ型Parser.token:

type token =
  | BOOL of (bool)
  | INT of (int)
  | FLOAT of (float)
  | NOT
  | MINUS
  | PLUS
 ...

スキャナでは予約語以外の単語がくるとトークンIDENTを返す。このトークンの値となるId.tは文字列のみから成るデータ型で、以後変数や関数の名前に用いられる。

パターンマッチのダミーを示す'_'に対してはその都度新しく名前を生成する。

識別子等のアクション部で使われるLexing.lexeme lexbufという式はパターンにマッチした文字列を参照する。

OCamlメモ

open Module

他のモジュールで定義した識別子を、モジュール名のプレフィクスなしで使えるようにする。JavaのimportやC++のusing namespaceに似ている。

int_of_string: string -> int

文字列を整数として解釈する。

float_of_string: string -> float

文字列を浮動小数として解釈する。

MinCaml読解ノート: ビルドと全体の流れ

「速攻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> { };

とするのと同じようなものだろう。

MinCaml

MinCamlコンパイラを読み終えた。

このコンパイラはOCamlで書かれたMinCamlというML系のサブセットの言語のコンパイラで、SPARCアセンブリを生成する。 「速攻MinCamlコンパイラ概説」というパート毎にソースコードと短い解説が合わせて読めるwebページが作られており、これを案内として読んでいった。

MinCamlコンパイラはコンパイルという仕事を変換の連続と定義している。コンパイラの構成はパートごとに綺麗に分かれていて、それぞれのパートも小さい。 MinCamlの言語としての仕様は教育目的に非常に割り切った仕様であり、これはコンパイラのソースコードを簡潔で理解しやすい大きさに保つ為と思われる。同時に、読む側から見ると色々と手を出してみたくなる点が多いのが心憎い(表面的な仕様拡充以外にも手を出せる余地は最適化やレジスタ割り付けなど色々ある)。OSにおけるMinixのような位置付けのコンパイラ版と言えるかも知れない。

読んでみると、各パートが小さいので十分わかりやすい。しかし後のパートにいくと多少ややこしいものもあったように思う。特にレジスタ割り当ては私には厄介だった。