2005年06月20日

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

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

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

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

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

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

式やプログラムを表す型

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

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

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

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

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

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

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

変換の実装

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

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

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自身は自由変数を使わないが、gfを値として返すためにクロージャになる。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)

この記事へのトラックバック
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス:

ホームページアドレス:

コメント: [必須入力]

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。