読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

3imp 4.4-4.5メモ

3imp 4.1-4.4メモ - レガシーコード生産ガイドでDisplayClosureまで流し読みして、なんとなくわかったので4章を最初から実装していました。

コード置き場

毎日20〜30分ずつやってたら1ヶ月近く経っちゃった。まあいいや。

3impに関する日本語の記事はそこそこ多くて、大部分は箇条書きのメモや小さな気付きだったりするんですが、それらが生む差異のおかげでかなり楽に理解することができました。

というわけで僕も僕の言葉で理解した事を簡単にまとめておきます。これから学習する人の理解の足しにしてください。

4.4 DISPLAY

lambda式の中に、引数の中に居ないのに、突如現る変数がおるとします。

(lambda [f y]
  (f
    x ; ←こやつ
    y))

こういうやつを自由変数と呼び、集めていきます。

なんでかというと、上のlambdaが、次のように別のlambdaの中で生成されて渡されていくとき

(lambda [x]
  (lambda [f y] (f x y)))  

引数fとyは評価時に渡されるんだけど、xが渡されたlambdaからはもう出ちゃってるので、評価時にxがおらんヤンケ!となります。

なのでまだxが生きてるlambdaの中にいるとき、そこで生成されるときに自由変数x(の値)を自分の中に取り込んでおきます。

3impの場合は[lambdaのコード, x]みたいな配列として実装します。先頭がコードで残りは自由変数(の値)。

Display Closureは必要な変数(の値)を、全て配列にコピーして持っています。変数参照はO(1)で済みます。速い!

3章の実装だとribリンクをたどっていくので、変数参照の度にO(n)の時間がかかります。

定義時に現れた全ての変数(の値)を持っておくと無駄なので、自分の中に自由変数として現れるものだけを集めて、コピーする、ということです。

4.5 BOX

しかし変数の値をコピーして持っておくと、困ったことがおきます。変数の値を書き換えたいときです。

(lambda [x]
  (cons
    (lambda [] x)            ; LAM1
    (lambda [v] (set! x v))) ; LAM2

こういう風に、自由変数xの値を取り出すLAM1、書き換えるLAM2を生成して使うとします。

困ったことに、LAM1もLAM2も、それぞれxの値をコピーして自分の中に持っています。LAM2は自分の中のxだけでなく、LAM1の中のxも書き換えないと反映されません。

一つの自由変数を変更する度に、それを参照している全てのClosureを更新するのはとても遅くなります。

対策として、BOXを導入します。BOXとは、箱のようなものです。(これお決まりのセリフね)

set!で書き換えられる可能性のある変数は、間接参照にします。

ヒープ上のどこかに、xの値を保存しておく場所(BOX)を確保します。そしてLAM1,LAM2は、xの値の代わりに、その場所(BOX)の情報を持っておきます。

xの値を書き換えるときは、BOXの内容を書き換えます。そして、xの値を参照するときは、BOXに保存されている情報を読み取ります。

4章の実装では、継続はスタックを全てコピーします。よって、自由変数に限らず、全てのset!される引数で同じ問題が起きます。BOXを作らずに継続内で変数の値を書き換えるとどうなるか想像してみてください。

というわけで全てのset!される変数を集めて、生成時はboxで包み、参照時はboxを開き、set!時は内容を書き換えるようにします。これらの情報は全てコンパイル時にわかります。(Schemeコンパイラに優しいと言われる理由がなんとなくわかりました)

ちなみに継続が存在しない言語では自由変数のみをboxingすればよく、そもそも参照を書き換えない言語ではboxingは不要みたいです。プログラマが明示的にboxingする言語もあります。

今後

4.6の末尾呼び出し最適化の前に、コンパイル結果とスタックをもうちょっと見やすくして、頭でVMの動きを追いたい。あとコード整理しましょう。

広告を非表示にする