Writing an interpreter in Goを読んだ感想
この記事はもともとはてなブログにあった内容を引っ越ししてきたものです
冬休み(2019年の)に入ってからWriting an interpreter in Goという本をやっていて、一通りやり終えたので感想をまとめる
ざっくりまとめから
・全体的にわかりやすく、コードも公開されているのでほぼ躓かずに完動までいける
・goの標準moduleだけで実装できるので、基本文法がわかっていれば最後までいけると感じた。関連モジュールのバージョンや依存に振り回されるストレスがなかった
・TDDの雰囲気がわかる(ただ似たような記述が多い部分もあって都度写経してると結構大変ではあった)
・interpreterにおけるlexer、parser、evaluaterそれぞれがどういう役割を持っているかがわかった
モチベーション
goの学習がしたかったのと、以前以下の記事に挑戦して途中でやめてしまったので、言語処理系に再挑戦したい気持ちがあった(コンパイラ作成にもいずれ再挑戦したいと思う)
半分以上は好奇心からで、インタプリタやコンパイラの動く仕組みに興味があったのと、ちょうど冬休みもあったのでいつもと趣向の違う事でもガッツリやってみるかーということで手を伸ばした感じ
最近の業務はwebアプリ開発なので、ast周りの知見が得られればbabel周りで良いことあるかも? という皮算用も少しあった
この本にはGo言語で作るインタプリタというO'Reillyの日本語版が存在するが、英語版のほうがkindleが存在していてほぼ半額だったのと、英語の技術書を一冊読み切るという体験が得たかったので英語版にした。日本語版とは読み比べていないが、O'Reilly版には加筆があったりするかもしれない
各章の感想
内容は1~4章に分かれている
1章ではlexerの実装を行う
lexerは字句解析器(Lexical Analyzer)の略で、inputとして渡された文字列を解釈し、tokenという後にparserで扱う構造体を生成する
といっても内容的には=が出てきたらequalトークン、!だったらbangトークンみたいな感じで結構シンプル
2章でparserを実装する
多分parserの実装が最も難易度が高いと感じた。再帰下降構文解析(Recursive Descent Parsing)という手法でlexerの生成したtoken一覧から抽象構文木(Abstruct syntax tree)を生成するところまでがparserの責務
再帰下降構文解析は各構文の定義を元に再帰的に解析を行う方法と理解している(構文の定義についてはBNFや、EBNFといった内容を参照)
例えばletの変数定義は let a = 10 のようになるが、これはletの次のtokenはident(変数名)であり、その次のtokenは=であり、その次は何かしらのexpressionである。というような形で let <ident> = <expression> のように定義され、parserはこの定義に従って構文を解釈していく
構文の定義には再帰的なものも発生するが、それが関数の再帰で綺麗に実装されているのが印象的だった
3章でevaluatorという実行系(?)の実装を行い、parserの作ったastをもとに変数・関数の定義や演算が行えるようになる
ここまでやるとinterpreterとしてはある意味完成していて、簡単な演算や関数の呼び出しができて面白い
evaluator上での変数定義はグローバルなmapを使って保持する(envという変数で持ち回る)が、このenvはouterという変数でenvを持つ再帰構造になっており、関数呼び出し時にenvの子供を作ってそれを使うという点と、関数内でそのスコープにない変数を参照したとき、一つ親のenvを参照しにいくよう実装されている点が面白かった
これはPythonで関数内でスコープ外の変数を参照したときと同じ挙動で馴染みがあったためで、今まで挙動だけ知っていたものが内側から理解できた実感があった
4章では作ったinterpreter拡張していく
stringやarray、hashmapにbuiltin関数といった他の言語でもよく見る型などの実装を行う
ここまでやっていると追加はどうやるのかぼんやりとでもアタリが付くようになってきていて進める前に一度考えて答え合わせしていくのが楽しかった
自分の理解度を試す為に、本を読み終えた後にfloat対応をやってみた(テスト込み)
実装に際してはlexerで数字を解釈しているreadNumber関数で"."を解釈するようにするだけで、ほかはintの実装をちょっといじるだけで実装できた(本の中で作るMonkeyという言語はドットを演算子として定義していないので楽だったのかもしれない)。
総じてとても良い勉強になった、まとまった休暇がある時は仕事とはあまり関係ないけれど興味がある分野に頭を突っ込むのも悪くないなと感じた(結果的に仕事が始まってからは3週間以上がこのブログを書くまでに掛かっているのだけれど…)
リポジトリは以下
この記事が気に入ったらサポートをしてみませんか？