「Go言語でつくるインタプリタ」を読んでインタプリタの身近さをを確認した

「Go言語でつくるインタプリタ」は、そこらへんのネットに転がっている超軽量なRubyで作ったLispインタプリタほど小さくなく、重厚な理論に関する論文や書籍のような難しすぎるものでもなく、インタプリタがどのように動作するのか理解するために十分で適量のコードと解説が書かれた本だ。
この本を読み終わった頃には、コンピュータがプログラミング言語を解析して評価するための基礎知識が得られるだろう。

Go言語でつくるインタプリタ

インタプリタ

インタプリタとは、テキストを受け取って、解析し、評価し、結果を出し、これを繰り返す。

インタプリタの実装についてだが、本当に簡単なインタプリタなら30分〜1時間程度で作れるものもある。(BrainfuckやLispなどが簡単な部類だ) もちろん上等なものを求めればキリがなくJITインタプリタなるものもあったり、何年かかるか分かったものではない。

この本のインタプリタは1日1時間ずつやれば1ヶ月くらいでできる程度のちょうど良いものだ。 コード自体も難解で困り果てるようなものは存在せず、多少頭をひねるところがあるといった程度だ。

この本の流れとしては、字句解析、構文解析、抽象構文木、内部オブジェクトシステム、評価、データ構造や組み込み関数の拡張、マクロシステムの追加、といった順番でインタプリタが出来上がっていく。 使用言語はGo言語で、全てのコードはTDD(テスト駆動開発)で進められる。

完成するインタプリタで使えるコード例を示す。 ここには変数、関数、高階関数、クロージャー、if式、マクロ定義、マクロ呼び出し、などなど様々な要素が含まれているが、これでもまだまだ一部だ

字句解析

字句解析というのは非常に単純明快だ。

1文字ずつ読んでいき、このインタプリタ言語(以下monkey)で決めた字句の識別子(トークン)を設定していくだけだ。 monkeyでは空白に大した意味を持たせないので、字句解析時に空白は全てスキップする。

let five = 5;

例えばこのプログラムを字句解析すると、

token.LET, token.IDENT, token.ASSIGN, token.INT, token.SEMICOLON

という風にトークンを設定していく。 あとはこれらのトークンを増やしていき、言語仕様で許される限りのトークンを用意していけば良い。

構文解析

構文解析とは字句解析で設定したトークンらに構文としての意味を持たせていくものである。 monkeyでは抽象構文木(AST)を用いて構文を表現する。

let文(let ident = 1 + 1)のASTイメージはこんな感じだ。

let文が存在するだけのプログラムのASTだ。 Programというのが原点になっていて、その下にlet文のノードがあり、letが持つ名前と値それぞれから変数ノードと式ノードが連なっている。

monkeyのシステム内で、ASTのノードはあるインターフェースを満たす構造体で表現されている。 プログラムで表現される文や式には全て構造が決まっている。 その構造をASTのノードという形にひたすら変えていく作業だ。

評価

monkeyコードの全容はすでにASTに収められている。 あとはこれらに意味付けをし、命を吹き込んでいくことでmonkeyは本当の意味で動き出す。

ASTを使って評価をしていくわけだが、この評価の仕方によって性能や移植性、実装難度が大きく変わってくる。 今回はASTのノードを巡ってそのまま評価するtree-walking型インタプリタと呼ばれる方式で評価する。 実際に世間でよく使われている言語ではここで最適化やバイトコードへの変換など様々なことが行われたりする。

ここでは値や式をオブジェクトとして扱っていく。 Evalと呼ばれる巨大な評価器を拡張し、ノードを順番に巡り式を評価し、そのまた中にある式を評価し、値を評価していく。

本当に素晴らしいのは、この章では特に難しいことなどしていないのに気がついたらmonkeyに命が吹き込まれ動き出していることだ。 今まで字句解析し、構文解析をへて真心込めて作られたASTは評価され、実際に式が計算されたり、let文に値が代入されたり、return文が動作したり、エラーがあれば排出する。

しかもなんとGC(ガーベジコレクション)までも動いている！まさかと思うなら実際に読んでみればわかる。動いているんだ。

データ構造拡張

ここまでのmonkeyには数値、真偽値といった単純なデータ構造しかなかった。 この章では文字列、組み込み関数、配列、ハッシュ、という言語を彩る追加のデータ型や関数を追加する。

データ構造を追加していくために、一番最初からコードを追加していく必要がある。 字句解析からもう一度見ていく必要があるんだ。 だけどそれは知識の定着にも繋がるので、もう一度しっかり理解しながら進めていこう。

まず字句解析に""や[]や{}などの字句を追加する。 構文解析ではこれらが文字列として、配列としてハッシュとしてオブジェクトシステムに当てはめられる。 評価器では新しいデータ構造用にEvalを拡張する。

組み込み関数やハッシュでは新しい試みが多く見られるが、今までに組み上げてきた部分の多くを使い回せるのでそれほど大きな手間はかからない。 あっという間に追加のデータ構造は完成するだろう。

マクロシステム

この章では今までのデータ構造や関数とは一風変わったマクロと呼ばれる、自分自身を書き換えるための仕組みを実装していく。 自分自身を書き換えるというと、ブラックジャ●クのように自分で自分の手術をするようなイメージだ。(危険もあるという意味でも)

マクロは自分自身を書き換えるといったが実際にどこでどう行われるのかを簡単にまとめよう。 構文解析が終わったあと、評価される前にASTを書き換えてしまうのだ。 書き換えるためにASTが生成されていないといけないし、評価されてしまってはもう手遅れなので評価される前でないとダメだ。

実際に実装するマクロシステムはquote, unquote, macro の3つだ。 それぞれ、評価させない、quoteの中でもここだけ評価させる、macro定義でプログラムの指定位置を置き換える、といった役割を持っている。

これらを実装するには通常のEval実装にマクロシステムを割り込ませ、本来評価するはずだった場所を評価させないように隠蔽したり、はたまた隠蔽した場所を再度Evalの実装とは別の場所で下準備をしたあと何食わぬ顔でEvalを再度実行したりする。 マクロシステムで通常のEval実装に割り込む部分は目から鱗が落ちるような単純だが強力なノードの書き換えを行う。 ASTの書き換えという部分が増えたが、結局やるべきことはだいたい同じなので今までのコードとだいたい同じものを少し追加するだけだ。

まとめ

ここまでで本の範囲で見ることができるmonkeyの全てだ。 冒頭で見せたサンプルコードも問題なく実行できるだろう。

だがmonkeyはまだまだ未熟なインタプリタなので、多くの部分を拡張したり最適化できるだろう。 変数名などに許される名前の設計を変えたり、あらたなデータ構造を追加したり、ユーザーに優しいエラー発生システムの追加、評価方法の変更、組み込み関数や組み込みライブラリの追加、......数えればキリがないほどの拡張ができるし、すぐに取りかかれるさほど難しくない拡張もある。

この本で学べることは簡単すぎず、難しすぎない丁度良いボリュームのインタプリタの作り方を学べる。 もちろんGoコードの勉強にもなるかもしれないが、一番の目玉としては字句解析や構文解析、評価器、マクロシステムなどがどのような仕組みや考え方で実装されているのかを学べることだろう。 この本を学んだことで今までより難しい理論に関する書籍のようなものもつまみ食いしていけるかもしれない。

そしてなにより、インタプリタは楽しいってことだ！！

Go言語でつくるインタプリタ