それでは,MiniMLコンパイラにおける効率良いクロージャの表現方法を見てみよう.まずは,簡単な例:
fun x -> fun y -> x + y
からはじめる.実際には,このフェーズの入力中にfun
式は存在せず,すべての関数はlet rec
式で定義されているため:
let rec _f0 x =
let rec _f1 y = x + y in
_f1 in
_f0
について考えることになる.
まず,外側の関数_f0
の本体式は自由変数を一つも含んでおらず,その評価には引数x
の値だけが分かれば良い.x
の値は_f0
を適用する関数適用式を評価する際の実引数によって決まるため,結局,関数定義の時点において生成するクロージャには,関数本体式だけを含めておけば十分と言える.
ここで,「関数本体式を含む」の実現方法がインタプリタとコンパイラでは大きく異なることに注意しなければいけない.インタプリタは,その名のとおりプログラム実行時に式(抽象構文木)を解釈実行する言語処理系であり,「関数本体式を含む」とは単純に抽象構文木を含むことを意味していた(詳しくは講義テキスト3.4節).
一方,コンパイラでは,式の評価のためプログラム実行時にメモリ中に存在するオブジェクトは,ハードウェアが直接実行する機械語命令列である.
ハードウェアの講義で学んでいるはずだが(詳しくはコード生成でも説明するが),機械語(あるいはアセンブリ言語)における関数は,関数呼出し命令のジャンプ先として指定するメモリアドレスから始まる機械語命令列に過ぎず,その先頭アドレスさえ知っていればどこからでも呼び出すことができる.
したがって,コンパイラにおける「関数本体式を含む」は,関数本体を実行する機械語命令列の先頭アドレスを含むことを意味する.
ただし,この章で扱うクロージャ変換は,いきなり機械語(アセンブリ)コードへ変換するわけではないため,「関数本体を実行する機械語命令列の先頭アドレス」に相当する概念を,変換先の中間表現である閉じた正規形に含める必要がある.ここでは,そのための専用の構文を追加する代わりに,単に関数名がその先頭アドレスを参照する式であるということにする.たとえば:
let rec f x = x + 1 in f
をクロージャ変換前の正規形コードとして読むと,変数参照式f
の評価結果である関数値がまさしくクロージャであるが,この同じコードをクロージャ変換後の閉じた正規形コードとして読むと,変数参照式f
の評価結果は,関数f
の本体を実行する機械語命令列の先頭アドレスを意味する.
以降では,C言語の用語を借り,関数本体を実行する機械語命令列の先頭アドレスを関数ポインタ (function pointer)と呼ぶことにする.
話を元に戻そう.先程の例における外側の関数_f0
を定義する時点において,クロージャに含める必要のある情報は関数ポインタだけであるから,次のような閉じた正規形コードへ変換することになる.
let rec _b__f0 x = 〚let rec _f1 y = x + y in _f1〛 in let _f0 = (_b__f0) in _f0
ただし,コード中の〚〛はクロージャ変換を表し,その内側に書かれているのは変換前の正規形コードである.フレッシュな関数名_b__f0
への参照が関数ポインタを表しており,ここで生成しているクロージャ_f0
は,その関数ポインタだけを含む1つ組となっている.
それでは次に,内側の関数_f1
のクロージャ表現について考えてみる.外側の関数_f0
とは異なり,こちらは本体式中に自由変数x
を含んでいる.このx
は外側の関数_f0
(変換後のコードでは関数_b__f0
)のパラメータであるから,変換後のコードにおいても全く同じ変数参照式x
を使って値を取得し,その値をクロージャに含めておけば良さそうである.そのような方針に従い,上のコードのクロージャ変換をさらに進めてみると:
let rec _b__f0 x = let rec _b__f1 y = 〚x + y〛 in let _f1 = (_b__f1, x) in _f1 in let _f0 = (_b__f0) in _f0
となる.
関数本体を定義しているlet rec
式の直後で生成している2つ組の第2要素に,その時点で変数参照式x
を評価して得られる値を入れることにより,クロージャ表現(つまり2つ組)の中に関数定義時点で自由変数x
が束縛されている値を閉じこめている.
最後に,一番内側に残っている変換〚x + y
〛について考える.変数参照式y
は関数_b__f1
のパラメータy
のスコープ中にあるため,変換後もそのままの式y
で大丈夫である.一方,変数参照式x
は,クロージャ表現である2つ組_f1
(_b__f0
が返す値)の第2要素を参照したいはずだが,上の変換後コードでは関数_b__f1
の本体中からその組を参照することはできない.関数_b__f1
の本体中からクロージャ_f1
に閉じこめられた自由変数の値を参照するためには,クロージャを呼び出す際,そのクロージャ自身を追加の引数として渡してやる必要がある.したがって,先程のコードは,追加の引数としてクロージャを受け取る以下のようなコードとする必要がある.
let rec _b__f0 (_f0, x) =
let rec _b__f1 (_f1, y) =
let x = _f1.1 in
x + y in
let _f1 = (_b__f1, x) in
_f1 in
let _f0 = (_b__f0) in
_f0
各関数定義の1番目のパラメータ_f0
,_f1
がその関数自身のクロージャである.当然のことながら,関数を呼び出す側では追加の実引数として適切なクロージャを渡すようにする必要がある.最終的に,関数適用も含めた次の式:
(fun x -> fun y -> x + y) 1 2
をクロージャ変換した結果の閉じた正規形コードは以下のようになる.
let rec _b__f0 (_f0, x) =
let rec _b__f1 (_f1, y) =
let x = _f1.1 in
x + y in
let _f1 = (_b__f1, x) in
_f1 in
let _f0 = (_b__f0) in
let _r__f0 = _f0.0 in
let _v0 = _r__f0 (_f0, 1) in
let _r__v0 = _v0.0 in
_r__v0 (_v0, 2)
関数適用では,必ずクロージャ_f0
,_v0
の第1要素から取り出した関数ポインタ_r__f0
,_r__v0
を使って呼び出していることに注意して欲しい.上のような簡単なコードであれば,_r__f0
への参照を_b__f0
への参照に置き換えても同じであるが(実際,コンパイラ内部で少しコードを解析すれば,そうしても良いことは簡単に分かるが),_r__v0
の方はそれが_b__f1
と同じ関数ポインタを含んでいることは簡単には分からない.また,_r__v0
を参照している一番下の行の関数適用式は_b__f1
を宣言しているlet rec
式のスコープに含まれていないため,単純に_b__f1
への参照に置き換えることはできない.
ここまでの単純な例では,関数本体中の自由変数は高々1つだけであったが,複数の自由変数を含む場合にはもう少し注意が必要である.たとえば:
let a = 1 in
let b = 2 in
let c = 3 in
let rec g = fun x -> a * x + c in
g 4
のようなプログラムのクロージャ変換を考えてみる.let rec
式を評価する時点で環境 (environment)には変数a
,b
,c
の束縛情報が含まれているが,関数g
の本体から参照されているのはa
とc
だけである.クロージャにはこれら2つの(let rec
式評価時点における)値だけを含めれば良いため,上のコードを変換すると以下のようになる:
let a = 1 in
let b = 2 in
let c = 3 in
let rec _b_g (g, x) =
let a = g.1 in
let c = g.2 in
a * x + c in
let g = (_b_g, a, c) in
let _r_g = g.0 in
_r_g (g, 4)
ここで,クロージャ表現である3つ組g
中のa
とc
の並び順は,それらの変数がlet
式で束縛されている順番と一致している必要はない.let rec
式の変換によって生み出される,関数本体を定義するlet rec
式(の中のコード)と,クロージャ(組)を生成する式の間で一貫している限り,組の中の自由変数の並び順は自由に決めてよい.たとえば,逆順に並べた:
let a = 1 in
let b = 2 in
let c = 3 in
let rec _b_g (g, x) =
let a = g.2 in
let c = g.1 in
a * x + c in
let g = (_b_g, c, a) in
let _r_g = g.0 in
_r_g (g, 4)
のようなコードでも,まったく同じ計算を行う関数を定義できていることは明らかである.
以上のようなクロージャ表現を追加の引数として受け取る方法を用いると,再帰関数も自動的に実現できていることは注目に値する.たとえば,(無限ループしてしまう)次の単純な再帰関数:
let rec h = fun x -> h (x+1) in
h 0
のクロージャ変換後コードは:
let rec _b_h (h, x) =
let _r_h = h.0 in
_r_h (h, x + 1) in
let h = (_b_h) in
let _r_h = h.0 in
_r_h (h, 0)
であるが,関数本体中で_b_h
を直接(つまり再帰的に)呼び出すことはない.つまり,let rec
式を正しく扱うために,講義テキスト3.5節のMLインタプリタのような特別な方法は必要ない.クロージャ変換後の閉じた正規形におけるlet rec
式の持つ意味に,キーワードrec
が本来意味していた「再帰」の
ニュアンスはもはや含まれておらず,let rec
式は関数を定義するだけの通常のlet
式に過ぎない.
コンパイラでクロージャを実現するための変換方法の説明は以上である.最後に,コンパイラでこのような表現を採用している理由を正しく理解できるよう,講義テキスト3.4,3.5節のインタプリタにおけるクロージャ表現との違いを簡単にまとめておく.先程の例に出てきた関数g
の各クロージャ表現を以下の図に示す.
インタプリタのクロージャ表現では,自由変数の束縛情報として,関数を定義する時点での(連想リストとして実現されている)環境全体を含めている.一方,コンパイラのクロージャ表現は以下の特徴を持つ.
- 関数本体式中に実際に出現する自由変数に関する束縛情報だけを含む.
- それぞれの束縛情報は名前と値の組ではなく値だけである.
- 実行時に名前をキーに線形探索するのではなく,コンパイル時に決まるインデックスを使って(定数時間で)直接参照する.
- 再帰を実現するために循環参照をつくる必要がない.
これらの特徴により,コンパイラのクロージャ表現の方が実行時間,消費メモリ量の両方において効率が良いと言える.
- 課題6(必須) クロージャ変換
closure.ml
のconvert
関数を完成させることにより,クロージャ変換を実装しなさい.