新しいプログラミング言語を学ぶとき、簡単なLisp処理系を作るという話
私は新たにプログラミング言語を学ぶとき、しばしば簡単なLisp処理系を作ってみます。いくつかの言語で取り組んでいるうちに、このLisp処理系群に小さな共通基盤も出来上がったりしているので、これを紹介しつつ、Lisp処理系の実装がプログラミング言語の学習にどう丁度いいのかを紹介します。
Rosetta Lisp
自作のLisp処理系群を、ロゼッタ・ストーンから名を借りてRosetta Lispと呼んでいます。Rosetta Lispは以下のような特徴を持ちます。
一定の共通した言語仕様・VMの仕様に基づいて動作する
Rosetta Lispは (Rosetta Lispに準拠するLisp処理系群は)、いずれも共通した命令セットのVM上でLispプログラムを実行するように実装されています。
Lispの簡単な実装では、よくインタプリタ形式が採用されます。kanaka/malやrui314/minilispはいずれもインタプリタ形式で動作します。インタプリタ形式から離れると実装が困難になるのではないかと思われがちですが、必ずしもそうではありません。Rosetta LispではSECDマシンを参考にした、命令セットの命令数がわずか11個の、単純で抽象的なVM上でプログラムを実行します。SECDマシンの詳細は日本語でもいくつか解説が見られるので割愛しますが、このVMの特徴として一つ挙げられることに、それが 移植性やパフォーマンスといった現実の課題を考慮して設計されたものではない ということがあります。小さく理解しやすく、「簡単なLisp処理系」のVMのデザインにはちょうどいい存在でした。
具体的には、Rosetta LispのLisp処理系群は、いずれもRoseta Lispの命令セットに対応するVMとコンパイラを実装します。ここで、Rosetta Lispはtestsuites/以下にVMとコンパイラが正しく実装できているかについてのテストケースを提供しているので、 1. parser (パーサのテスト), 2. compiler (S式→VMコードのコンパイラのテスト), 3. vm (VMのテスト) を順にパスさせるように逐次的にLisp処理系を実装していくことができます。 また、オマケとしてインタプリタ形式では困難であろう call/cc が実装できます。
共通のブートストラップコードで動作する
Rosetta Lispはブートストラップコードとしてboot.lispを提供しています。各Lisp処理系は、始めにこのコードが実行されるようにします。
boot.lispは最低限のシンタックスとビルトイン関数だけがあれば動作するように実装されており、boot.lispには quasiquote や let といったかなり基本的な構文などもマクロとして定義されています。このような構文もブートストラップコードから得られるようにすることで、ホスト言語 (各Lisp処理系を実装している言語) 上で実装しなければならないものをより少なくすることができます。[1] またboot.lispの実行自体、ある程度のコードを実行しての動作テストにもなります。
Lisp処理系が提供しなければならない機能は、ビルトイン関数の一覧にまとめられています。各Lisp処理系は、上述のVM、コンパイラに加え、これらビルトイン関数を提供することで、examples/以下のコードなどを動かせるようになります。
Rosetta LispによるRosetta Lisp実装: wonderlisp
これは半分余興ですが、boot.lispによってある程度の言語機能が揃ったところで、もう少し大きなプログラムを動かして動作確認したいということで、Rosetta Lisp自身によるLisp処理系の実装…wonderlispがあります。wonderlispもRosetta Lispに準拠するLisp処理系なので、Rosetta Lispのテストを実行することができます。この実行の過程で、I/Oも含めてLisp処理系が正しく動作することを一通り確認できます。
Rosetta Lispに準拠する過程で試せる言語機能
ここまでRosetta Lispはできるだけ少ない手間で実装を加えられるようにしていることを紹介してきました。一方で、Rosetta Lispの実装は 頻出の言語機能と標準ライブラリを試せるような課題 にもなっています。そのため、この実装は新しいプログラミング言語を試すのに丁度いいものとなっています。
S式のパース処理: 文字列と文字列の操作
Rosetta Lispのシンタックスはそれほど複雑ではありませんが、再帰的なS式の構造をパースするため正規表現では完結しません。文字と文字列の扱いがここである程度試せます。手書きの再帰下降型パーサを書いても良いですし、言語によってはパーサコンビネータライブラリを試すのにも丁度いい課題となっています。
ASTと命令列: 再帰的なデータ構造の表現
パース後のS式データやコンパイル後の命令データは、代数的データ型で表現しやすい典型的な構造となっています。データ型の定義方法や、データの構築・分解、データに関連する関数・メソッドを含めたモジュールの構成方法などがここで一通り学べます。言語によってはクラスと継承を用いるかもしれません。また、言語によってはパターンマッチングの拡張が可能かもしれません。
VMの実行: 可変状態の扱い
SECDマシンはごく単純なスタックで動作するので様々なデータ構造を試せるというわけではありませんが、VMの動作は可変状態をある程度扱います。変数束縛やレキシカルスコープを実現する環境(Env)の実装では HashMap などのキーバリュー型の構造を用います。
ビルトイン関数の実装: エラーハンドリングやマクロ、I/Oなど
ビルトイン関数はそれぞれ引数に取る値が限られており (例えば + なら数値など)、またビルトイン関数はそこそこ数があるので、入力の値をパターンマッチして特定のケースだけ受け付ける、というような処理をマクロ等で共通化できるか考えられます。受け付けない入力が与えれたときのエラーをVMに伝播して、VMの実行エラーとするエラーハンドリングの流れも考慮することになります。また、標準入出力や read-byte write-line といったビルトイン関数が要求されるので、その言語でのI/Oの基本的な扱いにも触れることになります。
まとめ
もちろん目的によって/目的によらず試しておきたい機能はまだまだある (ネットワーク通信や並行処理、ファイル処理、JSONの操作、テスト、パフォーマンス、...) 他、ガベージコレクションを持たない言語には比較的向かない課題ではありますが、プログラミング言語の書き心地を試すのにLisp処理系の実装はなかなか丁度いいというお話でした。
おまけ: 言語別の実装の感想など
これまでRosetta Lispの実装を以下の言語で行ってきました。それぞれの雑感です。
毎年一つ二つはプログラミング言語を新たに試し、Rosetta Lispシリーズに加えるようにしています。
-
ただし、マクロはパフォーマンスをあまり考慮していないVM上で動作するので、必然的にオーバーヘッドも大きくなります ↩︎
Discussion