仮想マシン化 - w

今朝、通勤途中、おもむろに、ILogScriptをバイトコードコンパイラ+仮想マシンな構造にしようとか、思った。これの動機は、速度とか、スタック管理だとか、そういうのもあるんだけど、一番大きな理由は、「インタプリタとしてはそこそこ動くようになってしまって、あとは少々の機能追加とデバッグぐらいしかやることが無くて面白くなくなってきたから。」とか、そんな感じ。
しかし、普通の言語と違って、ILogScriptの場合は、中間コードにバイトコードではなく、構文木を用いているのには、それなりの理由がある。それは、前にちょろっと書いたように、パーサを書き換えたりして、作った構文木をインタプリタに実行させたり、コンパイラに流して、アセンブリに変換したりするような無茶苦茶なことを実現可能にできるかもしれない、というような理由だ。Lispの場合は、「値」と「プログラム」が、同一のものとして扱える面白さがあるけど、ILogScriptの場合は、それをさらに超えて、「値」と「プログラム」と「出力したいもの」が同一に扱える、とか、そういう話だ。

すなわち、プログラム自身の構文木が操作できることによって、色々と面白いことができそうだ、という話。けど、こいつは、そんなに単純な話ではない。

ちょっと話はそれるのだけど、ILogScriptは、ブロックとローカル変数検索の効率が非常に悪い。ブロックに入るたびにハッシュテーブルは作られるし、変数は宣言されるたびにハッシュテーブルにノードが作られる。例えば、

for ( var i=0; i<1000; i++ ) {
	var j = x+y;
	var k = i;
}

こーいう場合は、1000回ハッシュテーブルが作られて、しかも、ループ一回ごとに変数jとkのノードが作られる。たったこれだけで、ゴミが3000個も作られてしまうのだ。なんということか。
こうなった背景には、ブロックスコープもオブジェクトも関数スコープも全部ハッシュテーブルにすれば、オブジェクトのメソッドのクロージャも全部まるごとハッシュテーブルのチェインにしてしまうことができるとかで楽だなー、と思った、とか、そういうのがあるのだ。
まあ、そうなった背景はどうでもいいとしても、常にメモリアロケーションを気にしながらコードを書いている人からすれば、これを理解しながらプログラムを書くのは結構辛いものがある、というか、実際、僕は、無意識のうちになるべくブロックを作らないようにしながらコードを書きたくなったりしてたのである。

しかし、それはいくらなんでも、問題ありすぎだ。レキシカルなブロックを気軽に作れないのはさすがに許されるものではない。そこで、この部分の最適化を考えるわけだ。おそらく、それは、変数がクロージャの中で使われるかどうかを判定して、スタックに積むか、ヒープから拾ってくるか、を決めておく、というものだろう。こうすれば、いくつかのローカル変数はヒープを使わなくなるだろうし、ブロックの名前空間も中身が全部スタックに積んであって、ブロックを抜けたあとにそのスコープの変数を再利用しないことがわかっていれば、ブロックのスコープをわざわざハッシュテーブルにする必要は無くなるだろう。

で、ここでスクリプト自身のプログラムの構文木を弄れるのは問題である、とかの話に戻ってくるのである。例えば、上のループの場合だと、var j = x+y; という文が、「グローバルスコープのhogeという変数に、今の環境で作った関数を代入する」みたいな意味に変更することも不可能ではなくなってくる。実際、今のILogScriptはパーサさえ対応すればそれが実現可能、というところまできているのだ。そうなると、どの変数がローカル変数として使われるか、という判定をするためには、恐しく複雑な解析を行わなくてはいけなくなってくる。

さすがに、それは現実的ではない。で、ここで、「レキシカルなブロックを気軽に作れる」か「構文木操作によって強力なマクロが書けるか」のトレードオフになってくるのである。これは、どっちを取るべきか。僕が色々書いた直感で言うならば、「ブロックを気軽に作れる」を選択するべきであると思う。まさか、「ブロックが作れるのよりもマクロが書けるほうが重要だ」と、言う人はいないだろう。で、そこで、マクロを書けないようにするとなると、わざわざ中間コードを構文木で持つ必要も無くなるわけで、「それじゃあいっそのこと仮想マシン化しちゃえ」と、いう話になるのである。

と、いうのは全部、建前で、実際のところは、Pythonが仮想マシンであることを知って、TJSも意外なことに仮想マシンで動いてるらしいことを知って、で、さらにyarv作ってるのを見ながら、「楽しそうだなぁ…」と、思って、なんか、こう「バイトコードとそれの仮想マシンの実装ってやってみたいなぁ…」と、いう気持ちになったから、というのが実際の理由であって、超個人的都合。

でも、そうすると、今のインタプリタの実装は殆んど捨てちゃうことになるんだよなぁ…、と思って、どうするべきかを考えたところ、次の三択。

今のままでいく
マクロ機能を取り除いて、変数スコープの解析だけやる。中間表現は今のままにしとく
今のは捨てて、仮想マシンを作る

で、気持ちとしては、「仮想マシン作りたいなぁ…」ってところなので、3番目なのだが、でも、「それで、速くなるのか？実際に仮想マシンにして速くなるかどうかなんてベンチマーク取ってみんとわからんのではないか」とか思って、「そこまでやるんだったら、もうちょっと踏み込んだ解析して、最適化入れたほうがいいんじゃないか」と、なって、「でも、GCCにも最適化モジュール載ってるのに、さらにILogScriptにそれよりショボい最適化モジュール載せるのは車輪＋メモリ領域の無駄遣いなんじゃねーか」と、想像、で、「でもなぁ…GCCの最適化モジュールはRTLにしか適用できないしなぁ…RTL表現はターゲットマシンに依存してるしなぁ…」と、思って、ここでビビっときたTree-SSAだ。Tree-SSAは以前調べた感じだと、RTLには依存しない。これを使えば、中間表現の最適化をGCCに任せられるんじゃないか。

で、簡単に調べてみたところ、そんなに間違ってはなかったようだ。それなりにうまくいきそうな気配はする。まだ、なんとも言えない部分のほうが多いけど。

とりあえず、決まった。流れは「ソース→GIMPLE→SSAなプログラム→仮想マシンコード」だ。SSAなプログラムでは、CFG（Call Flow Graph:プログラムの流れの経路を示すグラフ）も作られてるようなので、気合いを出せば、仮想マシンコードに落とすときにそれなりの最適化を入れられるかもしれない。もし、Tree-SSAの都合でこのような話が実現不可能だったとしても、Tree-SSAモジュールの使い方の勉強にはなるので、損はしないだろう。

あと、ここまでやってしまうんだったら、いっそ、今の実装のILogScriptでILogScriptコンパイラを書いちゃう、とかも考えたけど、GCCのバックエンド部分とのリンクはちょい時間がかかるので、スクリプトであることの利点が無くなってしまうと思う。まあ、そこまでやったら、もはやスクリプトではないかもしれんが。

と、いうような妄想をしてた。ネタ的には面白いと思うんだけど。やるとしたら、GCC4.0への移植、Tree-SSAの理解、仮想マシン、バイトコードの設計、効率のいいクロージャの実装のしかた、あたりを勉強したうえに、さらに実装しないと話にならないので、ちょっと量が多過ぎるような。要検討。