Writing A Compiler In Go を読んだ感想
- はじめに
- Chapter 1: Compilers & Virtual Machines
- Chapter 2: Hello Bytecode!
- Chapter 3: Compiling Expressions
- Chapter 4: Conditionals
- Chapter 5: Keeping Track of Names
- Chapter 6: String, Array and Hash
- Chapter 7: Functions
- Chapter 8: Built-in Functions
- Chapter 9: Closures
- Chapter 10: Taking Time
はじめに
Writing A Compiler In Go を読みました。
Rust による実装例です。
他の方の書評としては
- https://cipepser.hatenablog.com/entry/go-compiler
- https://junchang1031.hatenablog.com/entry/2018/12/23/081222
などがあります。
Writing A Compiler In Go は Writing An Interpreter In Go (以降ではインタプリタ本と呼びます) の続編です。インタプリタ本のマクロ以外を把握していることが必要とされます。Go の知識に関してはインタプリタ本に出てきた範囲を押さえておけば十分です。
本文を読むだけにするか、読みつつ手を動かしてソースコードを書くかで読了時間がけっこう変わります。テストコードとその説明が豊富なので読んで理解するだけでも楽しめると思います。Chapter 7, Chapter 9 などは stack の状態変化を図に描きながら進めると読みやすいです。
Writing An Interpreter In Go は和訳『Go言語でつくるインタプリタ』が出ているので、いつか『Go言語でつくるコンパイラ』も出版されるといいなと思っています。
ここでは、各チャプターの感想を記録しておきます。
Chapter 1: Compilers & Virtual Machines
コンパイラと VM の説明。そういうチャプターなので仕方ないけどソースコードがほとんど出てこないのでつらい。
なんとなく聞いたことのあった「VM」をちょっと知れたのはよかった。virtual machine (VM) は real machine の CPU で言うところの fetch-decode-execute cycle (instruction cycle) をソフトウェア的に実装したもの、という説明だった。JavaScript による、足し算引き算のみをサポートする VM の実装例 (擬似コード?) があったのでイメージしやすかった。
コンパイラは、AST を受け取って VM の入力となる bytecode (bytecode instruction) を吐く。この bytecode はソース言語 Monkey Language に存在しない機能はサポートしなくてよい。たとえば、Monkey Language には for 文や浮動小数点数がないのでこれらは考えなくてよい、ということだと思う。一般のプログラミング言語 (→ AST) → bytecode のような変換をするわけではないため。
他にも、本書ではなぜ (レジスタマシン型ではなくて) スタックマシン型の VM をつくるの？ → 実装がラクというのが理由のひとつ。などが書いてあって、大事なチャプターではあると思う。
Chapter 2: Hello Bytecode!
一気に REPL 完成まで持っていく。
登場する Opcode が OpConstant, OpAdd のふたつだけなので operand width をよく分かってなくても大丈夫かも。本を読み進めれば分かってくる気がする。
ユニットテスト用の helper 関数とかを実装することもあり行数はけっこうかさむ。Go でやるなら外部 package を使って assert.Equal とかしたほうがいいと思う。
Chapter 3: Compiling Expressions
四則演算、大小比較などを追加する。このチャプターから、チャプターごとに PR を分けていた。
おもしろポイントとしては、Opcode の種類数節約のために OpGreaterThan だけ用意して OpLessThan は無いという点。(Monkey Language) → (bytecode での表現) の形で書くとイメージは↓の感じ。
a > b→[OpGreaterThan, a, b]a < b→[OpGreaterThan, b, a]
Chapter 4: Conditionals
if 式を追加する。
if 式では if 節と else 節の片方だけを通るようにする必要がある。それはそうですが……。
たとえば、下のようなコードが無限時間かかると困る。
if (true) { // do nothing } else { sleep(9999999); }
したがって instruction を前からひとつずつ見ていくだけではダメで、以下のようにジャンプを使うとうまくいく。
Chapter 5: Keeping Track of Names
変数の binding (let x = ...) を追加する。
compiler では hash map で変数を管理するが VM ではパフォーマンスのために配列へのインデックスアクセスで変数を参照する。コンパイル時 hash map に追加した変数の順番を覚えておく感じ。
Chapter 6: String, Array and Hash
String, Array, HashMap を追加する。
そんなに難しいところはない。
Opcode OpArray は array の要素数を表すオペランドをひとつ持つ。VM ではその数だけ stack から pop して array object をつくる。pop した順番そのままだと逆順なので reverse しておく。
hash map について、デバッグしやすくするために hash 化前のキーも持つほうがよかった。
Chapter 7: Functions
関数を追加する。
いちばん難しいチャプターだと思う。実際 70 ページもある。
local bindings を実現するにはいくつか方法があると言うが、本書では VM の stack に穴を開けてそこを利用する。よくあるやり方らしい。
関数を実行する際には vm.sp より上の領域を使う。
ローカル変数の参照は「その変数が関数内で何番目に現れたか」をコンパイル時に計算しておけば stack から読み出せる。
関数から抜ける (return する) ときは図の Local 2, Local 1, Function を順に pop して掃除するイメージ。実際は vm.sp を減らすだけ。
他には arguments の扱いも学ぶ。引数がふたつある関数呼び出しでは Arg 1, Arg 2 がそれぞれ上図の Local 1, Local 2 に対応する。これらの引数以外にもローカル変数があれば Local 3, Local 4, ... のようになる。
Chapter 8: Built-in Functions
ビルトイン関数を追加する。
前のチャプターを済ませていれば、とくに詰まるところはないと思う。
Chapter 9: Closures
closure を追加する。
chapter 7 で関数は完成したかと思いきや、実は次のような使い方はできなかった。(めちゃくちゃ紛らわしい挙動だけど chapter 7 時点では addTwo(3) が 6 を返す)
let newAdder = fn(a) { let adder = fn(b) { a + b }; return adder; }; let addTwo = newAdder(2); addTwo(3); // => 5
この問題は、adder の定義時に a が 2 であったことを adder に覚えさせて解決できる。
より一般には、関数と自由変数 (= その関数に現れる、parameter でもローカル変数でもない変数すべて) を組にして扱うことで解決できる。
Chapter 10: Taking Time
fib(35) を求めるコードの実行時間を interpreter と VM とで比較する。
3 倍速くなるらしい。自分は interpreter を実装していないので比較できてない。
ところで、自分で実装した VM で fib(35) を計算すると、本書の実装によるものより 2 倍遅かった。ヘルプ。
