Writing A Compiler In Goを読んだ

Writing A Compiler In Goを読みました。

本書は、Writing An Interpreter In Go（邦訳：Go言語でつくるインタプリタ）の続編で、前作で開発したプログラミング言語MonkeyのコンパイラとVirtual Machine(以下、VM)を実装する内容となっています。

本書を読む前に、2018年後半にGo言語でつくるインタプリタを読み始めました。 Lexer、Parserを実装し、抽象構文木ASTを構築して、evalする流れを、自分の手でなぞり、ちゃんと動いたときには「Monkeyちゃん」と呼び出すほどに愛着が湧いていました。

これまで「すごそうだけどよくわからない」「いつか挑戦してみたい」と思っていた言語実装を一から自分の手でできたことに感動を覚え、「Lexerは他にも使えそうだな」と、12月にはGo2 Advent Calendar 2018 - Qiitaにて以下のようにProtocol Buffersのデコーダを書いていました。

cipepser.hatenablog.com

そんな折、続編である本書Writing A Compiler In Goの存在を知りました。 Turing Complete FMがとても好きなpodcastなのですが、2018年のセキュリティ・キャンプのCコンパイラを自作してみよう！でも多数の方がコンパイラを実装していて、本当にみんなすごいなぁと憧れを抱いていました。本書は、C言語ではないですが、コンパイラを実装できたことはとても嬉しかったです。

また、本書は現時点で邦訳が出ていません。個人的に初めて洋書を一冊完走することができた本にもなりました。初めての洋書でしたが、思いの外すらすらと読み進めることができました。理由としては以下がよかったです。

一文一文が短いので、どこを読んでいるのか迷子にならない
シンプルな言い回しなので、文意がわかる
わからなくてもコードを見れば何を言っているのかわかる
やたら文章のテンションが高く、勢いがある
「このテストは失敗して当然なんだ」のような応援が心強い

ちなみに、読むのにどれくらい時間が掛かるのか計測したところ26時間11分でした。実装中にtypoでハマったりしたので参考ですが。

f:id:cipepser:20190120123326p:plain

また、インタプリタと合わせて書いたコードの量は9289行でした。本書そのものがコメント（ドキュメント？）みたいなもので、コード中にはコメントがないので、処理そのものの行数だと考えると、気づけば結構書いたんだなぁと感慨深くもあります。

各章の所感

概要とメモベースで各章の所感を書きます。

第1章 Compilers & Virtual Machines

コンパイラ、VMとは何なのか、本書で実装するものが何なのかの説明。コードがなく（例示のみあり）、ひたすら説明。

初めての洋書だったこともあり、本章が一番つらかったかもしれない。

第2章 Hello Bytecode!

バイトコードとは何か。どうやって表現し、実装するかの概要説明。

スタックを実装して、OpCodeをVMに解釈させて実行させるまでを行う。 JVMなど聞いたことはあったVMやバイトコード、OpCodeがどういうものなのか、自分の手で実装することで掴めたのは大きかった。

第3章 Compiling Expressions

式をコンパイルする章。

まず中置式として四則演算のOpCodeから始まり、Booleanや比較演算子、前置式などを実装する。同じことを繰り返しやっていくので、よくわからなくても進めていくうちに前のほうもわかるようになる。繰り返し大事。

True/False/Nullをグローバルオブジェクトとして実装すると比較が楽（こうしないとrefrect.DeeqEqualを使うことになる）のも、勉強になった。

第4章 Conditionals

条件式をバイトコードで表現する。

条件が真のときとそうでないときで、スタックの飛ぶ先をJUMP命令として実装する。これがあのJUMP命令か！と謎の感動があった。

第5章 Keeping Track of Names

Identifier、もとい名前がついた変数や関数をバイトコードでどうやって表現するか

変数名を数字で置き換えることは知っていたが、実際に実装したことあるかないかは違うと思う。この章時点ではグローバル変数のみ実装。7章でScopeが実装される。

第6章 String, Array and Hash

章題の通り、String、Array、Hashを実装する。

同じような内容の繰り返しなので、復習を兼ねてサクサク進む。IndexをArrayとHashで同一の実装にできるのが気持ちいい。

第7章 Functions

おそらく本書の山場。関数や関数呼び出しを実装する。

個人的にはこの章が一番おもしろかったけど、同時に一番頭を使った。テストを一行一行追いかけて、スタック上がどうなっているか考えると理解できると思う。一番エッジケースを考慮しないといけないものこの章だったと思う。

関数内でローカル変数を実装するため、Scopeを定義する。関数の引数もローカル変数と同じように実装できるのがよい。 VMのほうではScopeと同様の概念をFrameと呼んでいた。

第8章 Built-in Functions

前作で登場した組み込み関数を実装する。

7章のScopeを組み込み関数用に特別に用意する。特に詰まることもなく進んだ。

第9章 Closures

クロージャを実装する。

7章でScopeの実装をしていたので、その延長ではあるものの自由変数の実装は興味深かかった。グローバル変数ではなく自由変数を扱うために、前章までで関数をOpConstantでスタックに積んでいたが、 OpClosureを使って、関数と一緒に自由変数もスタックに積む。これでうまく動くのかと懐疑的な気持ちだったが、テストが通る。すごい。

第10章 Taking Time

9章まででは関数を再帰で書けないので軽く修正を加える。

最後に、前作のevaluator v.s. vm (with compile)でベンチマーク。フィボナッチ数列の計算ベースで3倍程度速くなった。

Goコンパイラ本読了。
Goインタプリタ本で作ったevaluatorからコンパイルすることでフィボナッチ数列の計算ベースで3倍速くなった。 pic.twitter.com/J4PzdMg0Ju
— さいぺ (@cipepser) 2019年1月19日

最後に

思いは、本記事の序盤で語ってしまったので、多くは語りませんが、同じよう気持ちを持っている人には強く勧めます。もちろん最適化や実装方法にも別の方式があるなど、本書の範囲外となっていることも多数あります。（本書でも最適化よりわかりやすさ、学習を優先すると述べられている）しかし、入門書としてとても素晴らしい本だと思います。

なお、LexerやParserは、前作から引き続き利用するので、Go言語でつくるインタプリタから読むべきです。前作から合わせるとクロージャや第一級オブジェクト、リテラルなどイマイチ掴めていなかった概念を、実装することで理解を深めることができました。

あとTDD（Table Driven Tests）を実践できるのも、Goのプラクティスを知る上で役立つと思います。ただ、テストパターンはTypoで詰まると結構ハマる（1つのTypoで2時間くらい溶かしたりした）ので、コピペがおすすめです。（たぶんめんどくさくなるのもある）

本書は、Writing A Compiler In Go | Thorsten Ballで買えますが、eBookで買うとePub (iBook), Mobi (Kindle), PDF and HTMLで読めるのもよかったです。