MinCaml解説

「美しい日本のMLコンパイ
ラ」
を読む～MinCaml解説
福盛秀雄
http://fukumori.org
Ver.2005.08.11
1
MinCamlとは
OCamlのサブセット
あるもの：
•型推論
•基本型: int、float
•派生型: tuple, array
•高階関数
ないもの：
•パターンマッチング
•多相性（ポリモルフィズム）
•ガーベッジコレクション
•レコード型
2
コンパイラを構成する
ファイルとモジュール
＜ファイル名＞.mlで暗黙のモジュールが構成される
syntax.ml → Syntaxモジュール
typing.ml → Typingモジュール
kNormal.ml → KNormalモジュール
などなど
＜ファイル名＞.mliはインタフェース宣言
同名のモジュールの外部仕様を定義する
typing.mli → Typingモジュールの外部インタフェース
3
.mli(インタフェース)を押さえる
<モジュール名>.fが
各モジュールの主力関数
typing.mli
3: val f : Syntax.t -> Syntax.t
kNormal.mli
28: val f : Syntax.t -> t
alpha.mli
1: val f : KNormal.t -> KNormal.t
などなど
4
モジュール間のデータの流れ
main.ml
.mliファイルに記述されている内容と
Mainモジュールの処理をつき合わせてみると…
13: Emit.f outchan
モジュール間で
SparcAsm.prog
14: (RegAlloc.f
データを変形させながら
15:
(Simm13.f
SparcAsm.prog
流していく姿が見える
16:
(Virtual.f
Closure.prog
17:
(Closure.f
KNormal.t
18:
(iter !limit
KNormal.t
19:
(Alpha.f
KNormal.t
20:
(KNormal.f
Syntax.t
iterの内容は
21:
(Typing.f Syntax.t
22: 次のページで
(Parser.exp Lexer.token l)))))))))
5
モジュール間のデータの流れ(2)
関数“iter”の内容はこんなカンジ：
main.ml
(Closure.fへ)
KNormal.t
モジュール間で
データを変形させながら
流していく姿が見える
6: ... Elim.f (ConstFold.f (Inline.f (Assoc.f (Beta.f e))))
KNormal.t
KNormal.t KNormal.t KNormal.t
KNormal.t
(Alpha.fから)
流れているデータの内容はどうなっているのだろう?
6
データ型定義を押さえる
<モジュール名>.tがデータ型
序盤～中盤の処理で重要なのは以下の3つ：
Syntax.t
構文木を表現するデータ型
KNormal.t
K正規系（中間表現）を表すデータ型
Type.t
型表現を表すデータ型
7
構文木(Syntax.t)
syntax.ml
1: type t = (* MinCamlの構文を表現するデータ型 *)
2: | Unit
3: | Bool of bool
再帰データ型でツリーを構成
4: | Int of int
8: | Add of t * t
19:
20:
21:
22:
| If of t * t * t
| Let of (Id.t * Type.t) * t * t
| Var of Id.t
| LetRec of fundef list * t (* mutual recursion *)
29: and fundef = { name : Id.t * Type.t;
args : (Id.t * Type.t) list; body : t }
8
構文木の例
let rec sum x =
if x <= 0 then 0 else
sum (x - 1) + x in
print_int (sum 10000)
9
K正規形(KNormal.t)
Syntax.tと見た目はほとんど同じだが…
kNormal.ml(i)
Boolは消滅―Intに変換されている
1: type t =
2: | Unit
tからId.tへ―非再帰型データ化
3: | Int of int
6: | Add of Id.t * Id.t
13:
14:
15:
16:
17:
| IfEq of Id.t * Id.t * t * t
| IfLE of Id.t * Id.t * t * t
| Let of (Id.t * Type.t) * t * t
| Var of Id.t
| LetRec of fundef list * t
Ifは2種類の表現を使用
条件判断部を非再帰化
他は（おおむね）変更なし
25: and fundef = { name : Id.t * Type.t;
args : (Id.t * Type.t) list; body : t }
10
K正規形の例
let rec sum x =
if x <= 0 then 0 else
sum (x - 1) + x in
print_int (sum 10000)
11
型表現(Type.t)
Syntax.t, KNormal.tの中で使われる
type.ml
1: type t = (* MinCamlの型を表現するデータ型 *)
2: | Unit
「引数のリスト」と
3: | Bool
「返り値」の組
4: | Int
5: | Float
6: | Fun of t list * t (* arguments are uncurried *)
7: | Tuple of t list
ある変数の「型」
8: | Array of t
型の確定前は“ref None”
9: | Var of t option ref
確定後は“ref Some t”となる
10:
11: let gentyp () = Var(ref None) (* 新しい型変数を作る *)
12
重要な変数とイディオム
environmentの略
“env”
Id.t(変数名/関数名)をキーとするMap
値は「型」（Typing,KNormal)だったり
「変数名/関数名の別名」（Alpha, Beta,他)だったり
M.emptyを初期値とし、再帰処理のときに
これを引数にして引き回す
13
重要な変数とイディオム(2)
M.add x t env
xという変数/関数名に対応する型
（あるいは別名）tをenvに追加した、
新たなenvを返す
例）
M.add “a” Type.Int env
旧env
“f” -> Type.Float
新env
追加
“a” -> Type.Int
“f” -> Type.Float
14
重要な変数とイディオム(3)
“member”
M.mem x env
xに対応する型/別名がenvに存在するか
M.find x env
xに対応する型/別名を返す
例）
env
M.find “a” env
“a” -> Type.Int
“f” -> Type.Float
Type.Int
15
型推論
Typingモジュールで実行
Syntax.t->Syntax.tの変換
main.ml
20: (KNormal.f Syntax.t
21:
(Typing.f Syntax.t
22:
(Parser.exp Lexer.token l)))
16
Typingモジュール
Typingモジュールで定義される関数：
val deref_typ : Type.t -> Type.t
val deref_id_typ : 'a * Type.t -> 'a * Type.t
val deref_term : Syntax.t -> Syntax.t
val occur : Type.t option ref -> Type.t -> bool
val unify : Type.t -> Type.t -> unit
val g : Type.t M.t -> Syntax.t -> Type.t
val f : Syntax.t -> Syntax.t
(基本的に) 参照関係は下から上へ
= 下の関数が上の関数を呼び出す
17
Typing.f
eはプログラム全体を指すSyntax.t型データ
typing.ml
プログラム全体の
型推論はここで実施
164: let f e =
165: extenv := M.empty;
171: (try unify Type.Unit (g M.empty e)
172: with Unify _ -> failwith ”...");
173: extenv := M.map deref_typ !extenv;
174: deref_term e
型推論の結果を
整理する
18
Typing.g
typing.ml
88: let rec g env e = (* 型推論ルーチン *)
89: try
Syntax.tから
90: match e with
Type.tへの変換
91: | Unit -> Type.Unit
92: | Bool(_) -> Type.Bool
101:
102:
103:
104:
| Add(e1, e2) | Sub(e1, e2) ->
unify Type.Int (g env e1);
unify Type.Int (g env e2);
Type.Int
e1,e2の型推論結果が
Intであることを期待
Add/Subの結果はInt
19
Typing.g (2)
“let x = e1 in e2”の型推論：
typing.ml
121:
122:
123:
| Let((x, t), e1, e2) -> (* letの型推論 *)
unify t (g env e1);
e1の型推論結果と
g (M.add x t env) e2
tを一致させる
変数xを型tとして追加し、
e2の型推論に進む
20
Typing.unify
型変数間のチェック、代入を行う関数
typing.ml
二つの変数に対する
パターンマッチ
t1とt2の型が既に判明しており、
66: let rec unify t1 t2 =
かつ両者が同一の場合は何もしない
67: match t1, t2 with
68: | Type.Unit, Type.Unit | Type.Bool, Type.Bool
| Type.Int, Type.Int | Type.Float, Type.Float -> ()
86: | _, _ -> raise (Unify(t1, t2))
他のパターンについてのチェック
および（必要ならば）型の確定
match文内のパターン(68-85行)で拾えなかった場合の処理：
t1とt2間に型の不整合ありとみなし、例外を投げる
21
Typing.unify
片方が未確定の型を持つ変数であった場合
typing.ml
66: let rec unify t1 t2 =
67: match t1, t2 with
t1が型未確定のケース
80: | Type.Var({ contents = None } as r1), _ ->
81:
if occur r1 t2 then raise (Unify(t1, t2));
82:
r1 := Some(t2)
r1と同じ型変数がt2内に
例) let a = 1
左辺“a”の型は
Type.Var(ref None)から
Type.Var(ref Some(Type.Int))に変化
出現していないかチェック
（無限長の型が発生することを防止）
t1の型をt2に確定
22
Typing.fの実行結果
MinCamlプログラム
“let a = 1 in let b = 2 in a + b”を例に
Parser.expからTyping.fに入る構文木
Syntax.Let (("a", Type.Var {contents = None}), Syntax.Int 1,
Syntax.Let (("b", Type.Var {contents = None}), Syntax.Int 2,
Syntax.Add (Syntax.Var "a", Syntax.Var "b")))
Typing.fの“unify”まで実行した構文木
Syntax.Let (("a", Type.Var {contents = Some Type.Int}), Syntax.Int 1,
Syntax.Let (("b", Type.Var {contents = Some Type.Int}), Syntax.Int 2,
Syntax.Add (Syntax.Var "a", Syntax.Var "b")))
23
Typing.fの実行結果(2)
Typing.fの“unify”まで実行した構文木
Syntax.Let (("a", Type.Var {contents = Some Type.Int}), Syntax.Int 1,
Syntax.Let (("b", Type.Var {contents = Some Type.Int}), Syntax.Int 2,
Syntax.Add (Syntax.Var "a", Syntax.Var "b")))
Typing.fの“deref_term”まで実行した構文木
Syntax.Let (("a", Type.Int), Syntax.Int 1,
Syntax.Let (("b", Type.Int), Syntax.Int 2,
Syntax.Add (Syntax.Var "a", Syntax.Var "b")))
24
K正規化
KNormalモジュールで実行
Syntax.t->KNormal.tの変換
main.ml
19: (Alpha.f
20:
(KNormal.f
21:
(Typing.f
KNormal.t
Syntax.t
25
Syntax.tからKNormal.tへ
“a+b+c-d”を例に：
実行前(Syntax.t)
実行後(KNormal.t)
KNormal.f
「演算のネスト」を「Letのネスト」へ
26
実はこのままでは読みにくいので…
後ほどAssocモジュールにてletの簡約を行う
Assoc.f
（図は説明のためのイメージ）
実際は変数名などの付け替えがあるため、少し異なる
27
KNormal.f
fstは2要素のタプルの1番目の要素を返す関数
例） fst (1,2) = 1
kNormal.ml
195: let f e = fst (g M.empty e)
KNormal.gはK簡約形のツリーと型の組
すなわち(KNormal.t, Type.t)を返す関数
（型はKNormal.insert_letで使用するために必要）
28
KNormal.g
kNormal.ml
58: let rec g env = function (* K正規化ルーチン本体 *)
59: | Syntax.Unit -> Unit, Type.Unit
60: | Syntax.Bool(b) -> Int(if b then 1 else 0), Type.Int
63: | Syntax.Not(e) ->
g env (Syntax.If(e, Syntax.Bool(false),
Syntax.Bool(true)))
Syntax.NotからSyntax.Ifへ
変換して再びgに廻す
BoolからInt (0 or 1)
への変換
29
KNormal.g(2)
67: | Syntax.Add(e1, e2) -> (* 足し算のK正規化 *)
68:
insert_let (g env e1)
69:
(fun x -> insert_let (g env e2)
70:
(fun y -> Add(x, y), Type.Int))
例） (a+b) + (c+d)
KNormal.g
30

Download Report