情報科学実験II資料 (5)
Closure変換

田浦

5/11/98

Closure変換の目的と概要

Min-Scheme の関数定義を, 対応するCPSの関数定義に変換した後, 我々に残された仕事は, CPS関数を機械語の列に変換することである.

CPS命令Iの中で, 変数vが使われた時(つまりprimitiveのargumentか APPの中に現れた時), この変数vの出現は次の3通りに分類できる.

束縛された出現
vが, Iを含む最内側の(FIXSまたはFIXHに よる)関数定義のparameterであるか, またはそのbody内(のprimitiveまたは fix)で定義されている.(注)
内部自由な出現
vは, 束縛された出現ではないが, Iを含むCPS式 のどこかで束縛されている
外部自由な出現
束縛された出現でも内部自由な出現でもないもの

内部自由な出現と外部自由な出現を総称して自由な出現という.

あるCPS関数定義や, CPS式に対して, その中で(内部/外部)自由な出現をして いる変数の集合を, そのCPS関数またはCPS式の(内部/外部)自由変数と いう. 外部自由変数を単に外部変数と呼ぶこともある. また, 内部自 由変数と外部変数を総称して単に自由変数であると呼ぶ.

例えば以下のMin-Scheme programを考える.

(define (f x)
  (+ x (g x)))
これは次のようなCPS関数へと変換される.
[f (k x)
   (FIXS ([c (r) 
             (+ [x r] [t] (APPB k (t)))])
     (APPF g (c x)))]
ここで, CPS関数c(つまり呼びだし(g x)のcontinuation)の中で, また, fにおいては, となる.

CPS命令Iで変数vが使われる(つまり, primitiveの引数の位置に来るか, APPの関数または引数の位置に来る)時, vが上記のどの型の出現であるかに 応じて, その参照の仕方には差がある. より詳しくは後で述べるが, 束縛され た出現の場合, 値は定義された時点から使用の時点までずっとregister上に存 在するし, 内部自由な出現の場合, 値はそれを含む最内側のCPS関数が定義さ れた時点でrecordに格納され, 使用時にそこから取り出される. 最後に, 外部 自由な出現の場合には, 値は常にある決まった番地におかれており, そこから 取り出される.

このように変数の参照も一概には取り扱えず, 実は結構複雑である. CPS変換 後, いきなり機械語生成をはじめるのはあまりりこうではなく, 内部自 由変数, 外部変数への参照を明示的にするためのphaseを機械語生成の 前処理としてかませるのがすっきりとしたやり方である. このphaseを closure変換と呼ぶ.

用語の確認

FIXにおいて作られる, コード番地および自由変数を格納したrecordをそのFIX のclosure recordと呼ぶ. また, 特にFIXSにおいて作られるclosure recordをcontinuation recordと呼ぶこともある.

Closure変換は実際には, 一つまたは複数のCPS関数定義を受けとって, それを やはりCPS関数定義に変換する. 雰囲気を知るために先に例を見せると, 上の 例は結果的に以下のように変換される.

(f: (f k x) 
    (fixs [(c: (c r) 
            (rref [c 2] [x]
              [(+ [x r] [t]
                 [(rref [c 1] [k]
                    [(rref [k 0] [k'] 
                       [(APPB k' [k t])])])])]))]
      (stack [k (label c:) k x] [c]  ; allocate {(label c:), k, x} on k
         [(rref [(label g) 0] [g] 
            [(rref [g 0] [g'] 
               [(APPF g' (g c x))])])])))
注目すべき点は, このようにした場合, f:c:は表面上束縛変数のみを含ん でいるように見えることに注意せよ. むしろ以下のようにflatに並べた方が, この変換の持つ意味がわかりやすいかも知れない(各々が独立した関数として 「読める」ことを確認せよ).
(c: (c r) 
    (rref [c 2] [x]
       [(+ [x r] [t]
          [(rref [c 1] [k]
             [(rref [k 0] [k'] 
                [(APPB k' (k t))])])])]))

(f: (f k x) 
    (stack [k (label c:) k x] [c] 
       [(rref [(label g) 0] [g] 
          [(rref [g 0] [g'] 
             [(APPF g' (g c x))])])]))
このようにclosure変換は, 内部にnestした関数定義を含むCPSの関数定義(群) を, 自由変数を含まないCPSの関数定義(群)に変換する. また, 自由変数がど こから取り出され, そのためのメモリがどのように割り当てられるかも明示的 になっている. Closure変換された後もCPS形式だが, 特に区別したい時は, CLO形式と呼ぶ.

自由変数, Closure RecordのFormat

自由変数や, closure recordのformatについては今までに何度か述べてきたが, ここで今一度はっきりさせておく.

自由変数

まずはじめにあるCPS命令, CPS関数, およびCPS関数 群に対する, 自由変数を定義しておく.

eqnarray183

tex2html_wrap_inline514 が定義される関数で, 右辺は集合である. tex2html_wrap_inline516tex2html_wrap_inline518 において定義される関数の名前を並べたも のである. tex2html_wrap_inline520 はCPS operandのlistから変数だけを重複なく取り 出す関数である. また,

eqnarray197

である. このようにして求まる自由変数の集合は, 内部自由変数と, 外部変数 の和であることに注意せよ.

自由変数は構文的には使用される変数の中で束縛されていないもの, というだ けのことであるが, より実行モデルに密着した意味としては, 「その式を実行 するに当たって仮定されている変数束縛の集合」という意味を持つ. すなわち, その式を実行するのに当たって, 保存しておかなくてはならない変数の集合を 表す.

Closure Record Format

FIX式を実行するたびに一つclosure recordが作られる. つまりそのFIXで定義 されるいくつかの関数定義に対して, recordを一つ生成する.

単純には, あるFIXで定義される関数定義の列 tex2html_wrap_inline518 に対するclosure record formatは,

eqnarray204

である. tex2html_wrap_inline544 は, tex2html_wrap_inline518 で定義される関数のコード番地を順に並 べたlistである. tex2html_wrap_inline518 で関数 tex2html_wrap_inline550 が定義されるとすると,

tex2html_wrap_inline552

@はlistのappendを表す(順序も重要). また, DはそのFIX の外側で定義される変数の集合で, tex2html_wrap_inline556 によって, 内部自由変数だけを格 納するようにしている. 「単純には」と述べたのは, 後に見るようにFIXSにお いては, 前に割り当てられたrecordの一部を再利用する, ということをするの で, その他の制約が加わるからである. 具体的にどうするのかは後に述べる.

言葉でいうならば, あるFIXに対するclosure record formatとは,

そこで定義される関数群の自由変数のうち, そこで定義される関数群自身を取 り除き, さらに外部変数を取り除いたものを作り, その先頭に定義される関数 のコード番地を並べたもの
ということになる. そこで定義される関数群自身を取り除くのは, それらは closure recordに格納しなくても, そのclosure自身をずらす(offsetする)こ とによって得られるからであり, また, 外部変数を取り除くのはそれらはいつ でも決まった番地に格納されているからである.

例:

最初に単純な例として,
[f (k x)
   (FIXS ([c (r) 
             (+ [x r] [t] (APPB k (t)))])
     (APPF g (c x)))]
をcompile中だったとして, その中のFIXSを見る. すると,

eqnarray220

ということになる. ここで(label c:)cのコード番地である. fの方は,

eqnarray232

明らかにtoplevelで定義された関数には, 自由変数は存在せず, したがっ てclosure record formatは, コード番地ただ1語から成る.

一つのFIXに複数の関数定義がなされる場合を見る.

(define (ten-is-odd?)
  (fix ((odd? (y) (if (= y 0) #f (even? (- y 1))))
        (even? (y) (if (= y 0) #t (odd? (- y 1)))))
    (odd? 10)))
これは次のようなCPS関数定義に変換されるだろう.
[ten-is-odd? (k)
  (FIXH ([odd? (c y) (= [y 0] [] 
                        [(APP c (#f))
                         (- [y 1] [t] [(APPF even? (c t))])])]
         [even? (c y) (= [y 0] []
                         [(APP c (#t))
                          (- [y 1] [t] [(APPF odd? (c t))])])])
    (APP odd? (k 10)))]
このFIXHにおいて作られるclosure record formatは,

eqnarray241

となる. 特に, odd?, even?はお互いのbody部で自由であるにもかかわ らずclosure recordに格納されていないことに注意せよ. それらは一つの closure recordを共有し, 一方のclosure recordをoffset(ずらす)すること によってもう片方のclosureが得られる.

Closure Recordの割り当て

heapおよびstack命令

heap命令はconsセルの割り当てなど, 他の目的にも使われる命令で,

(heap [ tex2html_wrap_inline564 ] [h] [C])
によって, tex2html_wrap_inline570 をこの順に並べたrecordを作り, そのポイ ンタをhにbindし, Cを実行する.

stack命令は, heap命令と似ているが, 第1引数として, 割り当て るべき場所を指定する. つまり,

(stack [b tex2html_wrap_inline564 ] [s] [C])
によって, tex2html_wrap_inline570 をこの順に並べたrecordを, bで指される レコードの(stackが下に伸びると仮定して)下に割り当てる.

roffs命令

関数群 tex2html_wrap_inline588 を定義するFIXにおいて, tex2html_wrap_inline590 の正体はそこで 生成されるclosure recordへのpointerとなる. tex2html_wrap_inline590 は, heapまたは stack命令を使って割り当てられる. では残りの tex2html_wrap_inline594 以降はどうなるの かというと, 前述したように, それぞれに別々なrecordを割り当てるのでは なく, tex2html_wrap_inline590 を適切にoffsetしたもの(ずらしたもの)になる. tex2html_wrap_inline594tex2html_wrap_inline590 を1 word分, tex2html_wrap_inline602tex2html_wrap_inline590 を2 word分. . .ずらしたものになる. 先 のclosure record formatと照らしあわせて, 常にclosure 0 word目を読み出すと対応する関数のコード番地が得られることに注意せよ. 例えば, tex2html_wrap_inline594 の0 word目を良み出すと tex2html_wrap_inline594 のコード番地が得られる. これに よってclosureを呼び出す側はそれが実際にrecordの途中を指していようとい まいとに関わらず0 word目を読みだして得られたコード番地にjumpすることに よりその関数を実行することができる.

Recordのoffsetを実現する命令として, CPSのprimitiveにroffs を追加する.

(roffs [r o] [s] [...])
のように用い, roだけoffsetさせたrecordをsに束縛する. Closure変 換後FIX式のbody部は, 先頭にrecordの割当が, 引続きいくつかのoffsetが並 び, その後にもともとの本体が実行されるように変換される.

このように, FIX時においては,

のである.(注)

変数の参照方法

各種変数の参照方法をまとめておく. 以下で, CPS命令I中に現れる変数の出現 vをを考えているとする. fを, Iを含む最内側のCPS関数, tex2html_wrap_inline646fと同じFIXで同時に定義される関数の集合とする. また, そのFIXのclosure formatをF, Iの外側かつfの内側で束縛されている変数をBで与える.

displaymath624

は, vIにおいて束縛された出現であれば, そのままIを返すが, そう でない場合は, vを適切にとりだし(束縛し)た上でIを実行するCPS命令を 返す.

補助関数として, リストとその中のある2要素を与えられて, その2要素のリス ト中における相対位置を返す関数relposを用いる. たとえば,

relpos a b (a b c) = 0 - 1 = -1, relpos c a (a b c) = 2 - 0 = 2
である.

displaymath626

合計4通りの場合分けがされていて, それぞれで 行なわれていることを言葉で説明すると以下のようになる.

たとえば,

[f (k x)
   (FIXS ([c (r) 
             (+ [x r] [t] (APPB k (t)))])
     (APPF g (c x)))]
c内の最後のCPS命令において, kの出現は自由な出現であり, tex2html_wrap_inline748 に渡すべきパラメータは, であり, この時適用されるのは上の場合わけの第3の場合であって,
	relpos k (label c:) ((label c:) k x) = 1
より, 求めるものは,
	(rref [c 1] [k] [(APP k (t))])
である.

次の例として,

[ten-is-odd? (k)
  (FIXH ([odd? (c y) (= [y 0] [] 
                        [(APP c (#f))
                         (- [y 1] [t] [(APPF even? (c t))])])]
         [even? (c y) (= [y 0] []
                         [(APP c (#t))
                          (- [y 1] [t] [(APPF odd? (c t))])])])
    (APP odd? (k 10)))]
odd?の中の最後の命令(APPF even? (c t))における even?の参照を解決することを考えよう. つまり, である. 適用すべきは第2の場合で,
relpos (label even?:) (label odd?:) ((label odd?:) (label even?:)) = 1
より, 求めるべきものは,
(roffs [odd? 1] [even?] [(APPF even? (c t))])
である.

後のために, tex2html_wrap_inline774 と同じ目的で, 複数の変数を入力とする,関数 tex2html_wrap_inline776 を定義しておく. tex2html_wrap_inline776 は, 与えられた変数のリ スト中の各変数を順に束縛してから, 与えられた命令を実行する.

eqnarray324

FIXのためのメモリ管理

さて, closure recordを割り当てるにはメモリ管理が必要である. もっとも単 純には, (完全な処理系にはもともと必須である)garbage-collected heapを仮 定して, 常にそこから割り当ててしまうというものである.(注)

ここでは, GCなしでも, Min-SchemeFixのfixや明示的なheap割り当て(consな ど)を行なわない限り, プログラムが動き続けることができるよう, FIXSに関 してはGCなしで明示的に領域を再利用しながら実行する方式を考える. 実際に はstackを使ってメモリを管理し, もういらないはずのところを書き潰しなが ら実行する.(注) FIXHについてはheapに割り当てる(そしてGCが実装されることを期待する). (注)

したがってここで問題にするのは, FIXSの方だけで, そのために全体が以下の ような不変条件を保ちながら動作する. 今stackは下に伸びると仮定する.

  1. FIXHによって定義された関数(f (k …) B) が呼ばれた時, kより下は使用可能.
  2. FIXSによって定義された関数(k (...) B) が呼ばれた時, kより下は使用可能.
  3. FIXS式(FIXS [(k (...) ...)] B)の本体(B) を実行する時, kより下は利用可能.

これにともなって, 具体的な動作としては以下のような動作をする.

  1. FIXHによって定義された関数(f (k …) B) において, Bで最初に実行されるFIXSに対しては, kの下にrecordを allocateする.
  2. FIXSによって定義された関数(k (...) B) において, Bで最初に実行されるFIXSに対しては, kの下にrecordを allocateする.
  3. FIXSの本体, つまり, (FIXS [(k (...) ...)] B)B内で最初に実行されるFIXSに対しては, kの下にrecordを allocateする.
Closure変換アルゴリズムはこのstack管理を実現するために上の, kやその formatを引数として受けとらなくてはならない(以下のtおよびT).

具体的な動作としては以下のような動作をする.

Closure変換アルゴリズムのインタフェース

Closure変換アルゴリズムは以下のような呼び出し形式をしている.

displaymath864

ここで,

tex2html_wrap_inline896 は再帰的に式をたどっていく. その際に, B, Dを自明なやり方で 拡張していく.

t, Tについて説明する. これはCを実行する時点でのstackのtopを覚えて おくためのもので, tがtopに割り当てられているCPS関数名, Tがその closure formatである. Tは新たなclosureをstack上に作る時に, 同じ変数 を何度もstoreしないようにするために覚えておく.

課題

上のinterfaceにしたがって、Closure変換アルゴリズム (CPSの関数を、変数への参照を明示的に行なうCLO形式の関数に変換 するプログラム)を完成させよ.

締切り: 11月18日(水)


...fix)で定義されている.
vが, Iを含む再内側のFIXによって定義される関数の名前そのものである場合, そ れを束縛されていると定義するかどうかは微妙であるが, ここでは便宜上束縛 されていないと定義する.
...のである.
Min-Scheme においては, FIXはすなわちFIXSのことであ り, そこではCPS変換の結果から常に定義される関数は一つと決まっているの で, offset命令は必要ない.
...常にそこから割り当ててしまうというものである.
実際に SML/NJはこの方法で実装されている.
...ら実行する.
したがって間違って使っているはずのところを書き潰 すコードを生成してしまうと, プログラムが何でもありの挙動を示します.
...FIXHについてはheapに割り当てる(そしてGCが実装されることを期待する).
レイトレプログラムはGCがなくても動く.
 

 

〔トップページへ〕 〔「コンパイラ演習レジュメ」のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 11 May, 1999