Go言語でつくるインタプリタを読んだ
こちらの本を読んだので感想をば www.oreilly.co.jp
※Scalaに移植しました github.com
結論
本の簡単な説明
Go言語を使って簡単な仮想言語のインタプリタを作っていこうぜ!という本です。
本の構成はこのようになっています。
- 字句解析器の実装(Lexer)
- 構文解析器の実装(Parser)
- 評価器の実装(Evaluator)
ソースを読んでからその内容が実行されるまでのステップを一つずつ実装していくようになっていて、この手の内容では一般的な構成なのかなと思います。
低レイヤを知りたい人のためのCコンパイラ作成入門にも書かれていますが、この構成だと最後の最後までプログラムを実行できないので道中つまらないのでは?と思うかもしれません。
しかしこの本では序盤でREPLを実装し、例えば入力した文字の字句解析結果をコンソールで確認したり、都度のステップで動かして遊べるようになっていますので、あまり心配する必要はないと思います。
その他の特徴としては、TDD(テスト駆動開発)で進めていくのでテストをたくさん書きます。
わりとテストコードの量が多くて正直面倒なんですが、のちのち拡張するときにこれが効いてきます(後述)。
最終的にインタプリタが完成すると、こんなプログラムを実行できるようになります!
# 変数束縛 let age = 1; let name = "Monkey"; let result = 10 * (20 / 2); # 配列 let myArray = [1, 2, 3, 4, 5]; # ハッシュ let thorsten = {"name": "Thorsten", "age": 28}; # 関数 let add = fn(a, b) { return a + b; }; add(1, 2); # 再帰 let fibonacci = fn(x) { if (x == 0) { 0 } else { if (x == 1) { 1 } else { fibonacci(x - 1) + fibonacci(x - 2); } } }; # 高階関数 let twice = fn(f, x) { return f(f(x)); }; let addTwo = fn(x) { return x + 2; }; twice(addTwo, 2); // => 6
抜粋:: Thorsten Ball “Go言語でつくるインタプリタ”
よかったところ
翻訳が素晴らしい
これは本当によかった。
翻訳ものにありがちなぎこちなさが皆無で、下手な和書より全然読みやすいです。
すべての訳書がこのレベルだと非常にありがたいですね...。
文体がフランクで読みやすい
これは好みが分かれそうですが、例えば「〇〇の実装はこんな感じだ。 簡単そうだろう? 実際そうなんだ。」みたいな感じで全体的にそういうノリで書いてあります。
原著がそんな感じで、それを丁寧に再現しているのかなーと思います。
"読みやすい"というよりは"親しみやすい"、かも。
ターゲットにうまくマッチしている印象。
難しい理論が出てこない
私は情報工学を学んだこともなければ、(忘れてしまったので)中学の数学さえ怪しい人間ですが、順を追って進めていけばまったく問題なく理解できました。
何も知らない人向けに書いてあるようで、初見でハア?となりそうな用語や理論は一切出てきません。
その代わりに、
- 今からどんな機能を追加するのか
- そのためには何をしなくてはいけないのか、その理由
が丁寧に書いてあります。
あと、ここはちょっと大変かも、とかここは実はめっちゃ簡単やで!みたいなのがちょこちょこ書いてあるのもやさしい世界。
Goを選択した筆者の選球眼
私はほとんどGoを触ったことがありませんが*1、JavaなりJavaScriptなり何かしらの言語をやっていればなんとなく読めると思います。
唯一、型アサーションだけは調べるまで確信が持てませんでしたがその程度です。
そういった意味で、少なくとも技術書で使われる言語としてGoは良い選択肢だと思います。
テーブルドリブンテストも便利!
作ったインタプリタが拡張しやすい
前述の通りテストがきっちり書かれているので、拡張の過程でぶっ壊してもすぐわかります。
テスト自体の拡張も容易で、TableDrivenTestsで書いてある既存のテストにパターンを追加するか、真似て新しいテストを書いていくだけです。
(テストが多いぶんScalaに移植するとき心が折れそうになりましたけどねハハハ)
テストの例(OCamlのようなlet文のパースをテストするケース)
こんな感じでinputとexpectedを定義して、このパターンを使って実装を検証していきます。
tests := []struct { input string expectedIdentifier string expectedValue interface{} }{ {"let x = 5;", "x", 5}, {"let y = true;", "y", true}, {"let foobar = y;", "foobar", "y"}, }
おもちゃではなく、わりとちゃんとした言語ができる
冒頭のコード例を見ていただければわかるかと思いますが、文字列をprintできまーすとか、四則演算ができまーすみたいな単機能の言語ではなく、いちおう最低限の機能が実装されています。
最終的にここまでできるのならばやる気も出るというものです。
これはこの本を執筆した動機の一つのようで、導入の部分でも下記のように書かれています。
(引用して気づきましたが脱字ありますね)
私が欲しかったのは、900ページにも及ぶコンパイラについて書籍と、50行のRubyコードでLispインタプリタを実装する方法に関するブログ記事との間にあるようなものだ。
抜粋:: Thorsten Ball “Go言語でつくるインタプリタ”
ちなみに、インタプリタが完成すると組み込み関数を使ってMonkey上でmapやreduceを実装できるようにもなります。
本の構成がイテレーティブ
イテレーティブって言いたかっただけです。
TDDなのでまあそうなのかなと思いますが、どの章も以下のような流れになっていて、一定のリズムで読み進める&手を動かしていくことができます。
- 今から実装する機能の概要説明(識別子って何?とか)
- テスト書く -> 失敗
- 実装の説明&実装
- テスト成功
これ、読み進めていくうちに流れが体に刻みこれていくのがわかります。
プログラミング言語って、結局式と文の集合でできてるだけじゃん!
というのがわかって非常におもしろかった。
式と文についてもちゃんと説明してくれます。
一見難しそうな機能でも、実はこれただの式だからさ!前の章で作った機能を使って簡単に処理できるんだ!みたいなアハ体験?の連続で、いやー本当にうまくできてますね...という感じ。
最後がいい
普通、最初は四則演算とかHello Worldの実現から始めるような気がしますが、なんとこの本は一番最後の"グランドフィナーレ"という章でやっとHello World(というか文字列の出力)を実装します。
3章では、Monkeyプログラミング言語に生を与えた。呼吸を始めたんだ。
そして、私たちの最後の変更で、声を与えた。そう、Monkeyはついに、本物のプログラミング言語になった。抜粋:: Thorsten Ball “Go言語でつくるインタプリタ”
>> puts("Hello World!") Hello World!
Go言語でつくるインタプリタ 〜完〜
良質な物語か何かかな???
わるかったところ
ほとんどなかったのと面倒なので略(省エネ)
唯一、クロージャの実装で出てくるEnvironmentについては図が欲しかったかも。
どうやって進めたか
まず、コードの写経は一切やらずに全てコピペしました。
これは私の特性で、写経しても何も身につかないからです。
(できたものを拡張したりいじくりまわすときに初めて頭に入ってくるタイプの人間なのです...)
もちろん文章とコードを読んで理解しなが進めていきますが、あとでガチャガチャやるときに頭に定着させればいーやーという感じで進めました。
この前提で普通に頭から読み進めていきましたが、この本のキモであるPratt構文解析の部分はちょっと複雑だったので、そこだけ謎DSLをテキストに書きながら理解していきました。
晒すのが恥ずかしいですが、こんな感じです
(他人が見ても意味不明だと思いますが)
parseExpressionStatement<1, +> ★parseExpression<1, +>(LOWEST) 1を消化 for(LOWEST<SUM) -> peekFn(+) next(+) parseInfixExpression<+, 2>(left(1)) next(2) ★parseExpression<2, *>(SUM) 2を消化 for(SUM<PRODUCT) -> peekFn(*) next(*) parseInfixExpression<*, 3>(left(2)) next(3) ★parseExpression<3, ;>(PRODUCT) 3を消化 !for(!; or PRODUCT<LOWEST) RETURN 3 <3, ;> expression.Right=3 RETURN expression #expression(left:2, op:*, right: 3) <3, ;> RETURN expression #expression(left:2, op:*, right: 3) <3, ;> RETURN expression #expression(left:1, right(expression(left:2, op:*, right: 3))) <3, ;> !for(!;) RETURN expression #expression(left:1, right(expression(left:2, op:*, right: 3))) expression(left:1, right(expression(left:2, op:*, right: 3)))
ここが難しいのはもちろん筆者も理解していて、いい感じにログを出せるようになるコードが掲載されています。
ただ、それだと情報が足りなかったので自作した次第です。
エディタはVisual Studio Codeを使いましたが、まったく問題なく快適に進められました。
(まあほとんどコピペするだけなんですが)
最後に
冒頭にも書きましたが、プログラミング言語を作ってみたいけどスキルや前提知識に不安が...という人にはうってつけだと思います。
この後は、機能を追加するなりコンパイラを作るなり無限に広げていけるはず。
続編としてGoでコンパイラを作る本(未翻訳)が出ているので、いずれそちらも読んでみたいですね。
また、言語自作に限らずとも、この本で得た知識は例えば何らかの独自形式設定ファイルを解析するとかそういうシーンでも役に立つと思います。
(私、仕事では基幹系システムの受託開発をやっているのですが、たまにそういう"案件"があるんですよね...。たいてい地獄を見るけどね★)
ちなみに現在はScala移植版をベースに自作言語をシコシコ作っています。
まだほとんどMonkeyのままですが、色々いじっていきたい所存です。