2006/10/19 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井英二郎 コンパイラ演習 第 3 回 2006/10/19 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井英二郎

今日の内容 クロージャ変換 ネストした関数定義を平らにする ⇒ K 正規形をさらに RISC アセンブリに近づける(cf. A 正規化： ネストした変数定義を平らにする)

クロージャ変換 （基本）

Motivating Example let rec f a = let rec g b = a + b in g 3 これをどうアセンブリに落とすか？ let rec f a = let rec g b = a + b in g 3 val f : int -> int = <fun> # f 4;; - : int = 7

関数の表現 Ｃの世界 アセンブリの世界 関数 ラベル （アドレス） 関数呼び出し ラベルへのジャンプ ＭＬの世界 アセンブリの世界 関数 ？

C コンパイラの仕事 アドレス空間 static int a = 6; 対応 0xefffbac4 6

C コンパイラの仕事 int foo(int a) { return a + 1; } アドレス空間 0x08048328 fooの呼び出し pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax incl %eax leave ret fooの呼び出し ラベルfooへのジャンプ

ML でも同様にできるか？ let rec foo a = a + 1 アドレス空間 0x08048328 fooの呼び出し pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax incl %eax leave ret fooの呼び出し ラベルfooへのジャンプ

ML でも同様にできるか？ let rec f a = let rec g b = a + b in g 3 アドレス空間 f: 捨てる？ Ｃ言語的な単なる 関数ポインタではない！ g: aとbを足す命令列？ bは引数にもらったが aはどこにある？

問題の所在 関数定義内に自由変数が存在しうる let rec f a = let rec g b = a + b in g 3

解決策 自由変数を持つ関数を許さない C, C++ などのほとんどの処理系 レイトレだけなら何とかなる 関数のアドレスと一緒に、 自由変数の値も保存しておく Scheme, ML, Java (inner class) 等の処理系

ネスト関数に対する態度 (1) コンパイラはネスト関数定義を許さない プログラマはネスト関数定義がなくなるようにソースを書き換える

ネスト関数に対する態度 (2) C extension in GCC 関数定義内で関数を定義可能 できるだけ内側のスコープから変数を参照 内側関数のアドレスを変数に格納し、それを後で呼び出すことも可能 ただし外側関数のreturn後に内側関数を呼び出すと、何が起こるかわからない

ネスト関数に対する態度（３） ML ネスト関数定義や自由変数を持つ関数が なくなるような変換をコンパイラがする ネスト関数定義や自由変数を持つ関数が なくなるような変換をコンパイラがする プログラマは自由変数を持つ関数を利用できる さらに、自由変数を持つ関数を first-classとして、スコープ制限なしに利用できる 例：リストに格納して 外側関数への return 後に呼び出す

クロージャ変換 let rec g a b = a + b let rec f a = g a 3 大域変数でない自由変数を関数定義からなくす ネストした関数定義群 →独立したトップレベルの関数定義群 引数を増やすなどの単純なプログラム変換で実現可能 おおざっぱなアイデア： let rec g a b = a + b let rec f a = g a 3

基本アイデア ＭＬの世界 アセンブリの世界 関数 クロージャ: 関数ラベル（アドレス）と 自由変数群を含むレコード 関数呼び出し クロージャから自由変数群 を取り出して関数ラベル （アドレス）へジャンプ

クロージャからaを取り出して、引数bと足した結果を返す クロージャによる関数の表現 アドレス空間 let rec g b = a + b gのラベル （アドレス） g 3 28 （aの値） g: pushl … movl %eax, … … ret クロージャからaを取り出して、引数bと足した結果を返す

クロージャ変換後のコード 関数を作るとき： クロージャを作って、自由変数の値をしまっておく 関数を呼び出すとき： 自由変数の値を取り出して、引数に追加して渡す 呼び出される関数： 自由変数の値を、追加の引数として受け取る

対応関係 ＭＬの世界 アセンブリの世界 変換前のｇ ？？？ クロージャ（メモリ上に 作られたデータ構造）の アドレス 変換後のｇ gのコードが書かれている メモリのアドレス 変換後のL(g) クロージャ変換によって、MLの世界のデータを アセンブリの世界のデータにダイレクト対応させられる！

クロージャ変換 （発展）

クロージャ変換 (基本) の問題点 自由変数のない関数でも クロージャ作成 クロージャからの変数の取り出し のオーバーヘッドがかかる

「賢い」クロージャ変換 不要なクロージャを作らないですます やり方： （やや賢い） 「自由変数がない」とわかる関数は、クロージャではなくラベルを通じて呼び出す （もっと賢い） その結果いらなくなったクロージャは作らない MinCaml にも実装されている

「賢い」クロージャ変換の手順 (1) MinCaml では closure.ml 「自由変数がないとわかる関数の集合」 を管理 「自由変数がないとわかる関数の集合」 を管理 変数 known が保持 関数 fv により自由変数を計算 その情報に応じて、関数の呼び出し方を 切り替える AppCls か AppDir か

「賢い」クロージャ変換の手順 (2) 関数の引数は、 従来からあった引数 (args) 関数本体の自由変数 (formal_fv) の二集合の和となる 不要なクロージャ作成コードを削る let の本体に出現しない関数のクロージャは作らない (MakeCls を出力しない)

共通課題 ML 演習や Scheme 演習などで、 自分が今までに書いたプログラムを探してみて、自由変数を持つ関数の例を挙げよ。 その例を、自由変数がなくなる (クロージャがいらない) ように書き直せ。 もしそういう例がなかったら… 逆に「自由変数を持つ関数を使えば 簡単だったのに」というプログラムを探し、 そのように書き直してください

共通課題 次ページのプログラムを 「賢く」クロージャ変換したとする。 下線を引いた各関数について、 以下のものを答えよ 次ページのプログラムを 「賢く」クロージャ変換したとする。 下線を引いた各関数について、 以下のものを答えよ クロージャが作られるかどうか 作られる場合、クロージャの中に含まれる ラベルおよび変数 （関数fのラベルは Lf などと表記すること） 余裕のある人は、クロージャ変換後の （抽象）プログラムを書いてみてください

共通課題 let z = 4 in let rec f x = x – z in f 8 let rec g x = x – 2 in g 6 let rec f x = x – 1 in f let rec g h = h 3 in g let i x = x in let z = 4 in let rec f x = x - 5 in if z < 6 then (i, f 7) else (f, 8) let rec fact x = if x = 1 then 1 else x * fact (x – 1) in fact x

課題の提出先と締め切り 提出先: compiler-enshu@yl.is.s.u-tokyo.ac.jp 締め切り: 2 週間後 (11/2) の午後 1 時 Subject: Report 3 <学籍番号> <アカウント> 本文にも氏名と学籍番号を明記のこと