関数定義をトップレベルでしか書けない言語とは異なり,閉じた正規形のコード中には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型の関数定義のリストである.

このフラット表現と講義テキストの言語の違いは以下のとおりである.

  1. 式がに分類されている.
  2. 言語のプログラムはであったが,フラット表現には式がない.
  3. 変数参照式がVarFunに分類されている.
  4. 組(TupleExpProjExp)がある.
  5. loop式,recur式がある.

1.は,前の章までのフェーズで正規形を用いているため生じている違いであり,仮想機械コードへの変換にはあまり影響しない.

2.の違いにより,フラット表現にはメイン式が存在しないが,代わりに,_toplevelという特別な名前の関数をプログラムのメイン関数として扱うことに決めている.たとえば,式1+2というだけの簡単なプログラムは:

let rec _toplevel () = 1 + 2

のようなフラット表現になるものとする.一般的には,正規形コードのトップレベルに出現する式のうち,let rec式以外が同じ順番に並んだ関数本体式を持つような_toplevel関数を定義すると良い.

3.の変数参照式の分類は,講義テキストでは言語から言語へ変換する際に行われている処理である(paramlocallabimmの分類).この資料のコンパイラの内部設計では仮想機械コードへの変換が2つの変換処理に分かれているため,まず先に,labimmFun)とそれ以外(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.mlflatten関数を完成させることにより,正規形コードを平滑化しなさい.

平滑化(と変数参照の分類)を実装するのは,前の章までのフェーズと比較しそれほど難しくないはずだが,以下に少しだけヒントを書いておく.

まず,平滑化では,変換後の関数定義の並び順を気にしなくても良いため,正規形への変換で行なったlet式を持ち上げる操作と比べて,もっと簡単である.変換後の関数定義を貯めておくdecl list型のリストを1つ用意し,入力(正規形コード)を適当な順番で巡回しつつ,見つかったlet rec式を片っ端からdeclにして放り込んでゆけばよい.

次に,参照の分類については,id型の名前をflat.ml(* <= 3 *)行目で定義されているvalue型の値に束縛する環境を用いるのが簡単である.具体的には,入力を巡回中,let式による束縛を見つければVarオブジェクトを生成して環境に追加し,let rec式による束縛を見つければFunオブジェクトを生成して環境に追加すると良い.

なお,これら二つの処理を別々のパスで行っていけないわけではないが,入力を巡回しながらこれら二つの処理を同時に行うのは簡単である.