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

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

私に教えられることなら

VMとGCとClosure Conversion(途中まで)

やったことの記録・感想です。

モチベーション

Squeak SmalltalkVMは、Smalltalkのサブセット「Slang」で書かれていて、Cに変換されて生成されます。

Slangはかなり機能が制限されてはいますが、サブセットなのでSqueak Smalltalk上で直接動かすことができます。(Squeak) Smalltalkの強力なデバッガを使うことができるので、そのままCで書くよりも大変楽、と聞いています。

その話を知ってから、同じようにLispでもサブセットでVMを記述してみたいと思い続けています。

VMを記述するためのサブセットに必要な特徴は、GCを書く部分だけはGCを利用してはいけない、ということです。(GC中にGCが発生すると……?)

The 90 minute Scheme to C compilerというスライド([日本語での説明])(http://www.slideshare.net/ryos36/90-scheme-to-c)を読んでいると、CPS変換は置いといて、Closure Conversionだけを使えばとりあえずlambdaをある程度便利に使ってGC不使用のCに変換できるのでは……?と思ったので途中まで書いてみました。

結論から言いますが、読み間違えていました。"One heap section (and currently no GC!)“というのは、GC不要という意味ではなく、ただサンプルコードで実装してないだけで、GCは必要です。例えばグローバル変数fooに対して、nがlexical scopeに入ってる状態で(set! foo (lambda (x) (+ n x))とやるとき、Closure部分のメモリをどうにかしてアロケートする必要があります。

というわけでC出力の手前ですがやめることにしました。まあ結構楽しかったし、後で使いそうなので良いかな……

Lambda Liftingなら不要かもしれませんが、Internal Defineぐらいにしか使えないので、単純にGC記述部でのlambdaを諦めたほうが良さそうです。

Closure Conversionについて

最初、どう書いていいのかわからなくて結構苦労しました。

まずlambda/apply/def/symbol/valueだけのシンプルな文法のみを対象にして、さらに Closure Conversion→トップレベルへのLambdaの持ち上げ と分けて書きました。Schemeみたいに動的型付けの言語なら、中間表現(の型)が増える事を気にしなくていいので、何度もフェーズを分けて処理し、後にアルゴリズムを統合するという戦略でも良いと思います。

こういった式の変換については、ML系のレコードやClojureのマップのような、Immutableな名前で引けるデータ構造があると楽です。引数を増やすことで対応するとかなり厳しいコードになります……。

コード

(途中まで中途半端に自作方言への移植を目指したので、変なコードになっています)

github.com

広告を非表示にする