関数定義をトップレベルでしか書けない言語とは異なり,閉じた正規形のコード中にはlet rec
式の入れ子構造が残っている.しかし,クロージャ変換によってすべての関数定義の本体式は自由変数への参照を含まないようになっているため,この入れ子構造はもはや本質的ではない.このことを,前章までの復習を兼ね,let rec
式の入れ子構造の残る簡単な例を使って確認してみよう.
$ ./minimlc -v
# let make_adder = fun a ->
fun x -> x + a in
let adder = make_adder 3 in
adder 4;;
(* [Normal form] *)
let rec _f1 a =
let rec _f2 x = x + a in
_f2 in
let make_adder = _f1 in ...
(* [Closure] *)
let rec _b__f1 (_f1, a) =
let rec _b__f2 (_f2, x) =
let a = _f2.1 in
x + a in
let _f2 = (_b__f2, a) in
_f2 in
let _f1 = (_b__f1) in
let make_adder = _f1 in ...
関数_b__f2
を定義するlet rec
式が,関数_b__f1
を定義するlet rec
式の本体式中に含まれていることが見てとれる.しかしながら,_b__f2
の関数本体式は,クロージャ変換の結果,外側の変数を参照することはない.そのため,上記のクロージャ変換後コードは:
let rec _b__f2 (_f2, x) =
let a = _f2.1 in
x + a in
let rec _b__f1 (_f1, a) =
let _f2 = (_b__f2, a) in
_f2 in
...
のように,_b__f2
の定義をそのままの形で_b__f1
の外側(トップレベル)に移動してもまったく問題ない.
上の例のようにlet rec
式を移動し,すべての関数が言語と同じようにトップレベルでのみ定義されるように変換することを,関数定義の平滑化 (flattening)と呼ぶことにする.平滑化後の中間表現(以降,フラット表現と呼ぶことにする)を以下に示す.
flat.ml
(冒頭部分)
open Pretty
module S = Syntax
module C = Closure
exception Error of string
let err s = raise (Error s)
type id = S.id
type binOp = S.binOp
(* ==== 値 ==== *)
type value = (* <= 3 *)
Var of id
| Fun of id (* NEW *)
| IntV of int
(* ==== 式 ==== *)
type cexp =
ValExp of value
| BinOp of binOp * value * value
| AppExp of value * value list
| IfExp of value * exp * exp
| TupleExp of value list
| ProjExp of value * int
and exp =
CompExp of cexp
| LetExp of id * cexp * exp
| LoopExp of id * cexp * exp
| RecurExp of value
(* ==== 関数宣言 ==== *)
type decl = RecDecl of id * id list * exp (* NEW *) (* <= 2 *)
(* ==== プログラム ==== *)
type prog = decl list (* NEW *) (* <= 1 *)
プログラム全体は,(* <= 1 *)
行目で定義されているprog
型の値として表現され,その実体は(* <= 2 *)
行目で定義されているdecl
型の関数定義のリストである.
このフラット表現と講義テキストの言語の違いは以下のとおりである.
- 式がとに分類されている.
- 言語のプログラムはであったが,フラット表現には式がない.
- 変数参照式が
Var
とFun
に分類されている. - 組(
TupleExp
,ProjExp
)がある. loop
式,recur
式がある.
1.は,前の章までのフェーズで正規形を用いているため生じている違いであり,仮想機械コードへの変換にはあまり影響しない.
2.の違いにより,フラット表現にはメイン式が存在しないが,代わりに,_toplevel
という特別な名前の関数をプログラムのメイン関数として扱うことに決めている.たとえば,式1+2
というだけの簡単なプログラムは:
let rec _toplevel () = 1 + 2
のようなフラット表現になるものとする.一般的には,正規形コードのトップレベルに出現する式のうち,let rec
式以外が同じ順番に並んだ関数本体式を持つような_toplevel
関数を定義すると良い.
3.の変数参照式の分類は,講義テキストでは言語から言語へ変換する際に行われている処理である(param,local,labimmの分類).この資料のコンパイラの内部設計では仮想機械コードへの変換が2つの変換処理に分かれているため,まず先に,labimm(Fun
)とそれ以外(Var
)の間の分類だけを1つ目の平滑化で行うことにしている.
4.は,この実験の仮想機械コードにも同等の機能が追加されているだけである.
5.は,これらの式をどのような仮想機械コードへ変換すれば良いか次節で説明する.
これらの違いがある一方で,言語と同様,フラット表現ではトップレベルの関数定義の並び順を気にする必要はない.たとえば,先程のフラット表現は:
let rec _b__f1 (_f1, a) =
let _f2 = (_b__f2, a) in
_f2 in
let rec _b__f2 (_f2, x) =
let a = _f2.1 in
x + a in
...
の順番で関数定義が並んでいてもかまわない.並び順を気にしなくて良い理由は,この先どのようなアセンブリコードに変換されるかを理解すると分かる.
- 課題7(必須) 平滑化
flat.ml
のflatten
関数を完成させることにより,正規形コードを平滑化しなさい.
平滑化(と変数参照の分類)を実装するのは,前の章までのフェーズと比較しそれほど難しくないはずだが,以下に少しだけヒントを書いておく.
まず,平滑化では,変換後の関数定義の並び順を気にしなくても良いため,正規形への変換で行なったlet
式を持ち上げる操作と比べて,もっと簡単である.変換後の関数定義を貯めておくdecl list
型のリストを1つ用意し,入力(正規形コード)を適当な順番で巡回しつつ,見つかったlet rec
式を片っ端からdecl
にして放り込んでゆけばよい.
次に,参照の分類については,id
型の名前をflat.ml
の(* <= 3 *)
行目で定義されているvalue
型の値に束縛する環境を用いるのが簡単である.具体的には,入力を巡回中,let
式による束縛を見つければVar
オブジェクトを生成して環境に追加し,let rec
式による束縛を見つければFun
オブジェクトを生成して環境に追加すると良い.
なお,これら二つの処理を別々のパスで行っていけないわけではないが,入力を巡回しながらこれら二つの処理を同時に行うのは簡単である.