"Writing An Interpreter In Go"をC++&PEGで実装して

2020/4/19
遅ればせながら、良書と評判の「Go言語で作るインタープリタ」を買った。この本では学習にちょうどよいサイズのMonkeyという小さなインタープリタ言語を作成する。といっても高階関数も定義でき、なかなか洒落たコードもかける。

さらっと全体を眺めてみると、平易なコードとわかりやすい説明でしたためられている。無味乾燥な教科書調ではなく、筆者が直接語りかけてくれているような親しみやすさも感じる。それなりに深い内容を扱っているにも関わらず、すんなりと読み進めていける。

といっても自分でも手を動かさない限り、この本の真価は実感できないだろう。それで実際にMonkeyインタープリタを実装してみることにした。

Goで書かれたコードを書き写すだけでは、単に手を動かしているに過ぎない。それで使い慣れているC++で実装することにする。本書の字句解析・構文解析器の章は本当に素晴らしいのだが、ここは楽をしてcpp-peglibを使ってAST生成までを任せる。またREPLの実装にもcpp-linenoiseを使用。

基本的に書かれている通りの順序で進め、「テストコードを移植し、機能を実装し、テストが通るのを確認し、次のセクションに進む」をひたすら繰り返す。

セクションを終えるごとに「テストが通るのを見る快さ」を感じ、また言語が成長するにつれMonleyの表現力が増していくのを見れるので、最後まで楽しくやり遂げることができた。

この本ではとりわけTDDを推奨している。徐々に増えていくテストケースが大きなセーフネットへとなって行き、安心してコードを書き進めるための心の拠り所となった。ポカミスを犯してもリグレッションにすぐに気づくため、相当の時間の節約につながったと感じる。

GoのコードをC++に書き換える「移植」という作業は、目に入るコードを忠実に書き写すいわゆる「写経」と異なり、思考力をフル稼働させることを強制される。まずGoのコードが何をしているのかをきちんと把握し、言語間の差異を意識しつつC++に変換していかなければならない。

構文（変数定義、条件判断、関数定義・呼び出し、構造体の定義）や型（真偽、整数）、データ構造（配列、辞書）、基本的なライブラリ（IO、文字列操作）といった基本的な点についてはどちらも似たようなもの。しかしGoとC++で、類似のコンセプトを異なる仕方で実現している部分もあった。例えば、

• 戻り値：複数戻り値 vs 単一戻り値（タプルを使用できるが…）
• 遠い関数呼び出し元への通知：戻り値をひたすら伝播 vs 例外送出で一気に通知
• メモリ管理：ガーベッジコレクション vs std::shared_ptrによるリファレンスカウンティング
• 差分機能の実装：interface vs 仮想関数

このように、必ずしも単純な置き換え作業とはならない箇所が出てくる。まずはGoのコードを理解し、できる限りC++でも同様のスタイルで書けるように努力する。両言語の差異が大きい場合は、C++の特性を反映したコードに変換していく。

C++でどう書くのが最善かを考える際、言語に対する曖昧な理解では正しい判断を下せない。それはGoとC++のそれぞれの言語仕様をより明確に比較・理解する良い機会ともなった。またそれぞれの言語設計者の思想の違いを感じ取れるのも、コード移植のメリットかもしれない。

それなりのページ数のある本ではあるが、一度「テストコードを移植し、機能を実装し、テストが通るのを確認し、次のセクションに進む」のイテレーションに慣れると、後はそのリズムの繰り返しで、無理なく本の最後のHashとputsの実装までたどり着けた。

実際に手を動かすことによって、「Go言語で作るインタープリタ」は本当に良く書かれた本だと感じることができた。小さな部品を少しずつ組み上げていく過程は、小さい頃にプラモデルを作っていた時の経験と似ていて、本当に楽しい時間だった。(https://github.com/yhirose/monkey-cpp)

2021/10/2
いまだパンデミックが続いて家の中に閉じこもる時間が多い中、続編の「Writing A Compiler In Go」にチャレンジした。前編で実装したMonkeyインタープリタを、言語仕様はそのままにバイトコードVMコンパイラとして実装するという本。Monkey言語のパフォーマンスがどう向上するのかを見るのが興味深いところ。

前編で実装したパーサーやASTはほぼそのまま使い、EnvironmentとEvaluatorの代わりにVMとCompilerを実装して動かす。この本もテストを書いてから実装・確認という同じスタイルで、機能を少しずつ追加しながらコンパイラを作り上げていく。今回の作業では、本のセクションごとに進捗をGitに記録して後で振り返ることができるようにした。(https://github.com/yhirose/monkey-cpp)

コンパイラの実装の要はインストラクションデータと実行時のスタック動作を理解することだった。数値の四則演算などの単純な処理は意外と簡単。しかし条件ジャンブ・関数呼び出し・配列のアクセスなどの実装は、まずインストラクションポインタ・スタックポインタ・スタックフレームの動きをよく理解することが必要で、そうして初めてC++に移植することができた。

最大の難関は、最後のクロージャの実装。スコープ内の自由変数をどう認識するか、また実際の値をどのように上位のフレームから見つけて現在のスタックに持ってくるかなど、自分にとってマジックの様に感じられていたものを一つ一つ紐解きながら理解できたのはとても新鮮な経験だった。

前著の「Go言語で作るインタープリタ」を楽しんだ人は、間違いなくこの本も楽しめると思う。

今年の7月、「Crafting Interpreters」が遂に出版された。🎉 Web版は今でも無料で読めるようにしてくれている。この本ではLoxという言語をJavaでインタープリタとして、またCでバイトコードVMとして実装する模様。Cでどうクロージャ付VMを実装するのかにとても興味があるので、こちらもトライしてみたい。