サンダーボルト

相手モンスターを全て破壊する。

「Go言語で作るインタプリタ」を完走した

プログラミング基礎 Go

この記事は何か？

www.oreilly.co.jp

の本編（第1章〜第4章）を読みながら実装して、実際にインタプリタを作ることができたので、本の内容や感想をまとめる。

リポジトリ

本に沿って実装してみたインタプリタを試せるリポジトリは以下です。 github.com

$ git clone https://github.com/nakir323/monkey
$ cd monkey
$ go run main.go
Hello YourName! This is the Monkey programming language!
Feel free to type in commands
>> let addFunc = fn(a, b){return a + b;}
>> addFunc(3, 4)
7

こんな感じで遊べると思います。

筆者の属性

  • 非情報系学部（理系）卒
  • プログラミング（Webエンジニア）歴8年
  • 経験した言語はJava, JavaScript, TypeScript, Dart, Go
  • Go歴は半年

なぜやろうと思ったか

  • プログラミング言語を比較するための観点が自分には不足していると思っていて、その観点が増えそうな気がしたから
  • そもそもプログラミング言語がどのように動いているかに興味があったから
  • アセンブリやメモリの使い方について詳しくなれそうだと思ったから
  • Go言語自体の勉強になりそうだと思ったから
  • 言語作ったことあるよって言ってみたかったから😅

とりあえず低レイヤーなことに興味があったのでした。 また、以前ある言語について「どうですか？」と聞かれたときに文法についてくらいしかまともに答えることができず、言語を評価する観点が少ないなぁと痛感したのでその強化もできるかな？と思いやってみました。 先に言っておくと、3つ目の

アセンブリやメモリの使い方について詳しくなれそうだと思ったから

この需要はこの本では全く満たせませんでした。その他の4つは満たせたと思います。

所要時間

2020/1/23に買って、2020/2/27に実装完了したので、だいたい1ヶ月くらい。 毎日1時間くらいやったかな？サボった日もあるのでよくわかりませんがだいたい30~40時間くらいな気がします。

内容について

章ごとのまとめ

1章：字句解析

この章では字句解析を扱う。字句解析というのは、12+345という文字列（プログラム）があったときに、

'12'　'+'　'345'

という3つのトークンに分けること。 fn(a,b){return a + b}だったら

'fn'　'('　'a'　','　'b'　')'　'{'　'return'　'a'　'+'　'b'　'}'

に分ける。つまり、文字列を前から読んで、これは識別子なのか？演算子なのか？キーワード(returnやfn)なのか？というのを判断していくことになる。 ここでは単に文節に分けていくような作業をするだけなので、文法的に誤っているかどうかのチェックはしない。

本に沿って実装すればこの字句解析ロジックはlexer.goというファイルに書くのだが、終始lexer_test.goを変更しながらテスト駆動で開発をしていく。進捗が少しずつ出るしどんどんできることが増えるようになるのが味わえて非常に楽しい。

1章の最後にはREPL環境を作る。つまり、lexer_test.goで動作確認をするだけでなく、実際にmain.goを実装してそれを実行することで対話型で字句解析器の動作を確認することができるようになる。イメージとしてはこんな感じ。実行後、let result = x + y;と入力してEnterを押したときの出力例。

$ go run main.go
>> let result = x + y;
{Type:let Literal:let}
{Type:IDENT Literal:result}
{Type:= Literal:=}
{Type:IDENT Literal:x}
{Type:+ Literal:+}
{Type:IDENT Literal:y}
{Type:; Literal:;}

2章：構文解析

2章では1章で作ることができたトークン列からAST(抽象構文木)を作成する。といっても非常に簡単で、トークン列になったものを文法に合わせて構造として保持するだけ。 例えばlet result = x + y;が先のトークン列になった後、構文解析をすると以下のような構造体になる

type LetStatement struct {
  Name Identifier // resultを表す
  Value Expression // x + yを表す
}

つまり、文法が決まるところと言っていい場所である。let x = +といった記述は1章ではエラーを吐かないが2章でエラーを吐くことになる。 2章ではreturn文とlet文の2つの文と、式を構文解析する。return文は上のlet文と同じくらいシンプル。問題は式の構文解析で、例えば add(a + b + c * d / f + g)を解析するとadd((((a + b) + ((c * d) / f)) + g))となる。つまり、3章で行う評価のために、評価順をここで決める。

=,+,-,!,*,/,<,>,==,!=といった基本的な演算子は全て網羅されている。

再帰を使ってガリガリ解析していく、結構骨の折れる章なのだ😅

3章：評価

ASTができたらそのオブジェクト(struct)を使って実際に評価を行う。最初はここで、アセンブリとかの話が出てくるのかな〜なんて思ってたんだけど全く出てこなかった。 単純に解析した構文をGoで実行して、Goに評価させるだけだった😅

まぁでも最初はそれくらいでもいいか（続編のGoで作るコンパイラにその辺載ってるらしいし）と思って読み進めた。 実際に一番動き出すのが味わえるのがここなので、ここまで来ればあとはすいすい進むと思う。

最初は数値と+や-を評価できるようになって、すぐに電卓として使える言語ができあがる。その後はifやreturn、関数を評価し一通り動く言語が出来上がる。

4章：インタプリタの拡張

ここまでで、一通り言語としては動くが、いくつか基本的な言語としての機能が足りていないので、monkey言語に機能追加をするのが4章の内容となっている。 これが非常に良い構成になっていると感じていて、ここで再度1~3章の字句解析、構文解析、評価を総復習する。そして、文字列、配列、Map、組み込み関数を実装する。

全体的な内容

文体がかなりフランクなのが特徴😅
おかたい感じの文体ではないし、話しかけてくれているような感じなので、ハンズオンの講座に参加している感覚。monkeyのソースは全て手で書いたけど、1つ1つ順を追って丁寧に教えてくれるし全然苦しくなかった。自分の場合は電子版を買ったのだが、途中からテストコードはコピペで済ますようになった。

本のレビューや書評では2章が難しいと書いてあったので結構ビビっていたけど、挫折するほどではなかった。でもたしかにかなり複雑で、めちゃくちゃprintを仕込んでデバッグしてなんとか雰囲気掴んだ、という感じ😅再帰が苦手な人だと厳しいかもしれない。でもまぁ構文解析ロジックを完全に理解するための本ではないのでもし理解できなくてもそこまで深刻に考えなくてもよいし、できないからといってやめちゃったら勿体ないです。本質はそこじゃない。

自分はコンピュータサイエンスを学生時代に学んだわけではないので、結構この本を買う前はビビっていたのですが、思っていたほど全然難しくなかったです。自分でも理解できたし、多少の言語機能を拡張するとしたらどの辺をいじれば良いのかイメージは湧いているので個人的には名著だなぁと感じています！

学んだこと

本を読んでもちろんインタプリタってどういう原理で動いているかは分かるのですが、それに付随して学んだことをいくつか。

文と式

今まで何回かググったことがあったけどたまにごっちゃになったりする言葉。今回これでもかという程これらを意識して実装したのでもう染み付いた😅普段の仕事ではif文を使うが、monkeyではif式なので、そういったところも理解を深めるのに役立った。

クロージャの仕組み

何回か勉強したけどこれも作ってみてよくわかりました。Wikipediaのクロージャの説明は

引数以外の変数を実行時の環境ではなく、自身が定義された環境（静的スコープ）において解決することを特徴とする。

まぁそうなんだろうだけど、うーん😅という感じ。monkeyを作るときは評価の章にて関数オブジェクトを以下のように定義しました。

type Function struct {
    Parameters []*ast.Identifier // 関数の引数
    Body       *ast.BlockStatement // 関数の中身
    Env        *Environment // その関数から参照できる変数をまとめたMap
}

このようにEnvという環境情報を関数オブジェクトの中に保持しています。これこそクロージャを実現するためのもので、実装してみてなるほど、と腹落ちしました。

コンパイラも人間が作っているという事実

普通エラーが起きたりしたらどのファイルの何行目かって出ると思うんですが、monkey言語では表示されません。当たり前ですが、人がきちんと実装しているからそういった表示が出るんだよなぁと😅
単なるブラックボックスとして言語を見るのではなく、内部がどうなっているか少しイメージがつくようになったのは、結構大きいと思っています。

例えば、「○○言語って実行速度が速いらしいよ」という話を聞いたときに、今までなら「ふ〜ん、そうなんや😅」くらいで終わっていたものが、解析が速いの？評価が速いの？どういう評価方式なの？どういう工夫をしているの？と疑問が無限に湧いてくるようになったし、興味が湧くようになりました。

言語の観点

👆に似ている話かもしれません、。
今回はとりあえずシンプルな作りで言語を実装したけど、この本によれば、例えば評価のタイミングでAST を書き換える小さな最適化を行ったり(例えば使われてい ない変数束縛を削除する)、再帰や繰り返しを実行するのにより適した他の中間表現(IR; intermediate representation)に変換したりすることもあるらしい。

評価するのもGoに任せるパターンもあれば機械語に翻訳してしまう手もある。これから言語を見るときの観点（と興味）は間違いなく増えたと思う。

怯まない心

字句解析、構文解析、AST、パーサー。このあたりの言葉を聞いても怯まなくなりました✌

Goの文法について

ポインタレシーバや==による比較について、実装している中で不明点が出てきたので勉強しました。

ポインタレシーバ：The Go Playground
==による比較：The Go Playground

まとめ

買う前はめっちゃビビってたけど買ってよかった！

言語がそもそもどう動いているのか気になる、言語を評価する観点を増やしたい、って人にはおすすめです。ただ、読むだけだとそこまで理解できないと思うので、買うならきちんと実装するのが良いです。 難易度としては、とりあえずGoが書ける人なら完走は意外と易しいと思ってます。

続編に「Go言語で作るコンパイラ」という本があるのですが、英語版しかないのでかなりビビっています😅

compilerbook.com

でもいつかやってみたいです。

とりあえずインタプリタ本を完走できてよかった。お疲れ様でした🙇