この記事はLispアドベントカレンダー2021の５日目の記事です。
後でいろいろ実験するベースになりそうな、できるだけ変に目立った特徴が無いLisp処理系が欲しい、という動機で作りました。
実装について下記の選択をしています。
- できるだけ上から下まで把握しておきたいのでGCは自作。フラグメンテーションに悩まされない、かつ何回も作ったことがあるのでCheneyのコピーGC
- VMベースのLispはいくつか書いたことがあるので、Cなどで書いたことがなかった普通のインタプリタ。インタプリタの方がどれぐらい簡単なのか知りたい
- 末尾呼び出し最適化
- 64bitリトルエンディアン環境固定。データ型は62bit整数・nil・ペア（リスト）・シンボル・配列・バイト配列・文字列
- evalの前にコード変換用のフックを作って、マクロ展開器はLisp自身で書く
簡単なプロトタイプベースのオブジェクトシステムやシングルスレッドなのでchromeからアクセスすると応答しなくなるHTTPサーバーなどある程度遊べるぐらいには作っています。
感想とメモ
同じようなものを作ってみたい人、特に初めて(Lisp)処理系を書いてみたい人の参考になればと思います。
GCでよく起きたバグ
Copying GCやMark Compactionなどオブジェクトのアドレスが移動するGCの場合、ほとんどのやっかいなバグは、保護し忘れたオブジェクトが誤って回収されることで起きました。Lesxeの場合保護用スタックを使っていますが、大抵の場合はpushし忘れです。
そういったバグは、回収されてしまったオブジェクトへGCのちょっと後にアクセスすることで起きます。そのため、原因となる場所の特定が面倒です。
デバッグの際は下記を参考にしてみて下さい。
- できるだけ小さい関数に小分けして一度に扱う保護すべきオブジェクト数を減らす。長いところは怪しい
- アドレスを他の変数に代入して、片方だけ保護し忘れてないか？そういうところは怪しい
- Lisp（ターゲット言語）ではなくC（ホスト言語）のevalなどから場所を絞り込んだ方が早いかも
VM(+コンパイラ)とインタプリタどっちが楽か
予想通りインタプリタの方が楽でした。ただ、コアの部分(VM/インタプリタ）はあまり変わりません。ASTの操作vsバイトコードの操作など、どちらかというとVMの方が楽な場面も多いです。
しかし、VM(+コンパイラ)の場合、どれもセルフホスティングにしましたが、コンパイラ自体を改良するときに現在のコンパイラが壊れないように気をつけないといけないのが面倒になってしまいました。結局全て放置しています。
VMを採用する場合、ある程度はVMのホスト言語でコンパイラを書いてしまったほうが楽かもしれません。
VMはSECDマシンをアセンブリとCで、3impのスタックVMをCで書いたことがありますが、初めてのVMならSECDを先に作ってみるのがオススメです。後者を理解しやすくなりました。
今後
下記をやれたらやるか〜と考えています。
- tgcを参考にConservative GCを書いてみる
- インタプリタから「徐々に」VMへ切り替えていけるか試してみる
- アセンブリで書き直してみる
- Scheme(Gauche)で書いたシンセ・音楽生成スクリプトをLesxeで書き直して処理系高速化・ライブラリ充実の動機を作る