Zenn
🤖

「Writing A Compiler In Go」が面白い

に公開
Go
compiler
tech

数年前に読んだ書籍「Writing A Compiler In Go」がとても勉強になったので、どういう内容かを解説します。

Writing A Compiler In Go
https://compilerbook.com/

「Writing A Compiler In Go」とは

今回紹介するのは「Writing A Compiler In Go」になりますが、その前作にあたる「Writing An Interpreter In Go」の日本語訳が「Go言語でつくるインタプリタ」としてオライリーから出版されているため、ご存じの方も多いかと思います。
私は数年前に「Go言語でつくるインタプリタ」を読んでいて、続編の日本語訳が出るのを待っていましたが、なかなか発売されなかったので英語版を購入しました。

「Writing A Compiler In Go」を簡単に説明すると、「写経しながら軽量な自作コンパイラを作ってみよう」という本です。
前作「Writing An Interpreter In Go」で実装したインタプリタを改修し、Virtual Machine（VM）上で動作するようにします。

コンパイラを作ると聞くと非常に難しい印象を持ちがちですが、この本は小さなテストを書き、それに対応する小さな実装を積み重ねながら進むので、気がつけばVMとそのVM用のバイトコードを生成するコンパイラが完成している、という感じで、思ったよりスムーズに最後までたどり着けます。

前作「Writing An Interpreter In Go」でやったこと

まずは前作「Writing An Interpreter In Go」でやったことを振り返ります。
前作では「Monkey言語」というJavaScript風のオリジナル言語を定義し、そのインタプリタを実装しました。

Monkey言語は以下のようなコードです。

// Monkey言語の例
let people = [{"name": "Anna", "age": 24}, {"name": "Bob", "age": 99}];

let getName = fn(person) { person["name"]; };

getName(people[0]); // => "Anna"
getName(people[1]); // => "Bob"

入力されたMonkey言語のコードに対して、字句解析、抽象構文木解析、評価を順に実行し、結果を得ます。

下図のように、最初は文字列として扱われていたプログラムが順に処理されていき、「10 + 2;」の結果として12を得ています。

ここまでが前作「Writing An Interpreter In Go」でやったことの大まかな流れです。

次に字句解析と抽象構文木解析についても軽く復習します。

字句解析（Lexer）

字句解析では文字を1文字ずつ読み進め、意味のある単位で区切っていきます。
例えば「let number = 2;」なら「l」「e」「t」…という感じで1文字ずつ読み進め、行頭から「let」という字句を見つけることで、これは「let」トークンだ、と識別します。

構文木解析（Parser）

字句解析した結果をもとに構文解析を行い、意味のあるツリー状のデータ構造を生成します。
本書では既存のパーサージェネレータは使わず、自前でPratt構文解析器を実装しています。

評価（Eval）

Tree-Walkingインタプリタを実装します。
この方式では、抽象構文木を辿りながら順に評価します。
構文解析でツリー状になっているため、あとは評価を進めるだけで意外にシンプルです。

「Writing A Compiler In Go」で何をやるか

ここまでが前作での内容でした。

今回「Writing A Compiler In Go」では、インタプリタの評価部分を以下のように書き換えます（赤色部分）。

Tree-WalkingインタプリタではASTを辿り評価していましたが、今回はコンパイラがASTをたどりバイトコード（中間表現）を生成し、そのバイトコードをVMが順に評価します。実装方式は変わりますが、得られる結果は書き換え前と同じです。
※今回実装するVMはインタプリタの一種です。なおJITコンパイラは実装しません。

では、なぜ既に実装ずみのインタプリタをわざわざコンパイラとVMで実装し直すのか、その理由について本書籍では「modular」と「performance」をあげていますが、主な魅力は「performance」と説明しています。仮想マシンを構築することで、より少ない命令で表現できるようになり、結果としてコード密度が高まり、実行速度が向上するということだそうです。
実際、本書の最後のフィボナッチ数列のベンチマークでは約3倍の高速化を確認できます。

なお、今回オリジナルのMonkey言語をVM方式に書き換えるわけですが、実在する多くのプログラミング言語もライフタイムの中で実行方式をVM方式に書き換えるているらしく、Rubyもその一つとして説明されています。

Rubyがまさにこの例だ。バージョン1.8以下ではTree-WalkingインタプリタでASTを辿りながら実行していたが、1.9からは仮想マシンアーキテクチャに移行した。

— 「Go言語で作るインタプリタ」3章 評価

それでは、既に作成済みのインタプリタをどのように書き換えるか簡単に説明してみようと思います。

スタックマシンとバイトコードとデコード

今回実装するVMはスタックマシンです。
スタックは後入れ先出し（Last In First Out）のデータ構造で、これを使って演算します。
例えば1 + 2を実行する場合は

  1. 1 をスタックにプッシュ
  2. 2 をスタックにプッシュ
  3. 2つポップして加算したものをプッシュする

と順に行うことで、スタックのトップに加算の結果が残り、結果が 3 だということが分かります。

これを実行するバイトコードは以下のように定義されたりします（これは説明用に単純化した架空のバイトコードで、書籍の中で実際に使われるものではありません）。

PUSH 1
PUSH 2
ADD

ただし、実際にはこれらは文字列ではなく、次のようなバイナリで表現されたバイトコードとしてVMに渡されます。

00000001 00000001
00000001 00000010
00000010

これは下図のようにオペコードとオペランドをバイナリで表現したものです。
（ちなみにオペコードの長さが1バイトなので「バイトコード」と呼ばれるそうです）

このように「00000001 00000001 00000001 00000010 00000010」という数値の羅列がVMに渡され、VMはこの数値（バイトコード）を受け取り、「デコード」と「実行」を繰り返して処理します。

具体的にはバイトコードは以下のように評価されます。

例えばPUSH命令は1つの引数（オペランド）を持つため、PUSHの隣のバイトも読み取り、それが引数であると認識しスタックに値をプッシュします。

その後、次のオペコードに処理を進めていきます。

このようにVMはバイトコードを読み取って何をすべきか判断し、順次処理を行います。これが大まかな仕組みです。

コンパイラとVM

ここまで概念的な説明をしましたが、今回作成するコンパイラとVMの具体的な動きの一例を説明します。ここでは定数領域とグローバル変数領域について説明します。

例えば、

let three = 1 + 2;

をコンパイルすると、定数領域に「1」と「2」が登録され、以下の命令が生成されます。

# 定数の0番目をスタックにロード
OpConstant 0

# 定数の1番目をスタックにロード
OpConstant 1

# スタック上の2つを加算し結果を積む
OpAdd

# グローバル変数に格納（let文）
OpSetGlobal 0

# スタックのトップをポップ（let文終了）
OpPop

VM実行前はコンパイラが生成した定数だけが存在します。

OpConstant命令が実行されると、指定された定数（ここでは0番目、1番目）をスタックにプッシュします。

OpAdd命令でスタック上の2つをポップし加算し、その結果をプッシュします。

OpSetGlobalでスタックトップの値をグローバル領域に格納します。格納先のインデックスはオペランドで指定されます。

OpPopでスタックから1つ値を取り除きます。

終わりに

「Writing A Compiler In Go」はこのようなコンパイラを実装していく書籍となります。

当記事には書きませんでしたが、条件分岐や関数呼び出し、コールフレーム、クロージャなど、面白い内容がまだまだ有りますので、ご興味のある方はぜひ読んでみると楽しいと思います。
それと、「Writing A Compiler In Go」は洋書ですが、公式サイトから購入するとHTML版もダウンロードできるので、DeepLなどの翻訳ツールを使えば読みやすいと思います。

以上です。

Discussion