Lisp処理系の実装 考察
こちらで開発を行っているLispの処理系ですが、目標だったaobenchの動作まで行えるようになりました。上の画像はaobenchを実行することで作成される画像になります。*1
文法
100個程度の関数・マクロを提供しています。これらの関数についてはCで実装を行っています。
Common Lispと同様の記述が行えるように頑張ったのですが、Common Lispの仕様を完全に再現する事は難しく、省略している部分がいくつかあります。
- 逆クォート
- キーワード引数
- 多くの組み込み関数・マクロ
型・データ構造
整数・浮動小数点・リスト・文字列・配列をサポートしています。
データについては、Lispの特徴的なデータ構造であるコンスセルを用いて表現しているのですが、整数と浮動小数点についてはUnboxingされた状態で値を保持しています。
メモリ管理
mark and sweep GCを用いた動的メモリ管理を行っています。プログラム中のBoxingされているオブジェクトの基底型としてcons_tを用意し、型毎の初期化関数をnewメソッドとして提供しています。コンスセルのnewはnew_cons_cell関数を用いて行い、メモリが足りなくなった場合は内部でGCが走ります。
cons_t *new_string(const char *str) { cons_t *cons = new_cons_cell(); cons->type = STRING; cons->api = &cons_string_api; cons->str = str; return cons; }
パフォーマンス
下記のような処理速度になりました。大体clispと同程度のパフォーマンスを得られているようです。*2
| 処理系 | fibonacci | aobench |
|---|---|---|
| clisp | 0.86 | 14.67 |
| 自作処理系 | 1.22 | 12.56 |
関数呼び出しの際のオーバーヘッドがかなり大きく、パフォーマンスが伸び悩んだ原因となっていると思われます。
関数を返す関数を定義する事が出来るプログラミング言語では、クロージャーと呼ばれる関数を定義する事が出来ます。クロージャーは自身が定義された箇所から参照する事の出来る変数に触る事が出来るため、関数内で定義されたローカル変数の生存期間が、関数の呼び出しから終了までの期間と一致しない場合があります。
;関数fは、ローカル変数xの値をインクリメントする関数を返す (defun f () (let ((x 0)) (lambda () (setq x (+ x 1))))) (setq g (f)) ;関数fの呼び出しは終了しているが、ローカル変数xは生存している (funcall g) ;1 (funcall g) ;2
クロージャーから参照される可能性の無いローカル変数は生存期間が関数のスコープと同一なため、これらの変数についてはコールスタックをもちいてやりとりする事で高速な実行を行う事が出来るのですが、私の処理系ではローカル変数がクロージャーから参照されるかどうかの判定を行っていません。
クロージャーの定義・呼び出しの際に行う処理をクロージャーでない関数の際にも行ってしまっているので、余計な処理を行っている分パフォーマンスが低下しています。
Common Lispの挙動を出来る範囲で再現し、いくつかのベンチマークを動作させる事が出来ました。満足しきれていない部分もあるのですが、今回の処理系の実装を通してLispに対する理解もかなり進んだため、それなりに満足しています。
