JavaScriptは通常のブラウザで動作するので面倒なプログラミング環境のインストールとか必要なく動かすことができ、またnode.jsなどをインストールしてコマンドラインでも動かすことができる。なのでJavaScriptで動くコードを書くことは価値があるだろう。

てなわけで、LispコードをJavaScriptに変換するトランスレータを作り始めた。

方針

継続とか末尾呼び出し最適化を諦めればVM方式じゃなくて直接動作するJavaScriptに変換できるのではないかと思った。さらにいろいろ、RnRSだかCommon Lispの仕様とかに従わずに正確数やら文字型やらを実装しないでJavaScriptのデータ型をそのまま使う形にすればJavaScriptと同等な速度で動くプログラムに直接変換できるのではないか、などと考えた。

最適化に関しては、あまり頑張らなくてもJavaScript処理系がやってくれるのではないかなーと勝手に期待。

セルフホスティングコンパイラまでの道のり

まず最初はGaucheで動く、S式からJavaScriptのコードを表す文字列に変換する簡単なプログラムから作っていった。リテラルのコンパイルから始めて関数呼び出し、ラムダ関数、スペシャルフォームをコンパイルできるように拡張していった。

ある段階になると、コンパイラ自体をセルフホスティングしてJavaScript上で動くコンパイラを生成できるようにすることを考える。セルフホスティングするにはコンパイラが使う機能すべてをコンパイルできるようにする必要がある。足りない機能を実装して、また過剰な機能を使わないで単純な実装に置き換えたりした。

マクロの実装

Lisp言語の特徴として、コンパイルがホスト言語上でのコンパイル処理だけにとどまらず、ターゲット環境での実行を必要とする、ということがある。なぜかというと、マクロによるS式の変換を行うには実行環境が必要になるからだ。

セルフホスティングが完了してない段階ではJavaScriptでコンパイラが動く環境がないのでGaucheで動くコンパイラを使うのだけど、その段階ではマクロを実行できない。というのもマクロの定義に対してコンパイラが生成したJavaScriptコードはホスト言語であるGaucheでは動かせないからだ。

それを避けるためにスペシャルフォーム以外の文法(letとかcondとか)をすべて実装するのは大変だし、逆にそれらを使わずに基本的な文法だけでコンパイラを書くのも辛い。

そこでちょっとインチキだけどマクロの変換はGauche上でevalしてしまうことで実現しておく。その際にはホスト言語であるGaucheと実装中の言語の動作を同じにしておく必要がある。

はしごを外す

セルフホスティングが実現できたならば、ようやくホスト言語からおさらばできる環境が整う。Lisp(Scheme)で書いているコンパイラをコンパイルしてJavaScriptで動くプログラムができあがる。コンパイラを変更・拡張するにはLispで書いてるソースコードを変更してJavaScriptで動くコンパイラを使ってJavaScriptのコードを生成すればよい。新たなブートストラップ問題のできあがり!

ここまでのコード

シンプルなセルフホスティングコンパイラができたので、現段階で公開しておきます:

lisp2js v0.1