書籍『Go言語でつくるインタプリタ』を写経してみた

今さらながら『Go言語でつくるインタプリタ』のとおりにMonkey言語を作ってみました。個人的に名著だと思います。

実際に買ったのはKindleの日本語版です。

英語版はこちら。

公式サイト↓には既に続編の「Writing A Compiler in Go」もありますので、こちらもそのうちやってみたいです（やってます）。

• サイト: Writing An Interpreter In Go | Thorsten Ball
• サイト: Writing A Compiler In Go | Thorsten Ball

同書の特徴

同書の大きな特徴は「読みながら実際に作ってみる」ことを主眼においていることです。

それなりの規模のプログラミング言語を作ろうとすると、昔は（今でも）yaccやlexといったツールを使うことがよくあったようです（なおRubyの場合はbison（yaccの実装のひとつ）以外は基本的にC言語で手作り、標準ライブラリの一部はRubyで実装しているようです）。

今ならPEG記法↓で書けるパーサージェネレーターのようなお便利なツールもいろいろありますし、もっと洗練された言語構築法がきっとあるのでしょう。マシンもランタイムも高速になってきたので、JVMやらJavaScript上で動作する言語やらきりがありません。

参考: Parsing Expression Grammar - Wikipedia

しかし同書は学習が目的なので、あえてそうした言語構築の支援ツールを使わず、token/lexer/parser/AST/evaluatorを手作りしています。お便利ツールを使うと、lexerやparserの生のしくみに触れにくくなるという説明で、納得です。

Go言語を使ったのは環境づくりなどがいろいろ手っ取り早いからだろうと想像しています。

プログラミング言語をゼロから実用に近いレベルまでひととおり作り上げる体験はそうそうできるものではありませんが、同書は説明も実に丁寧で、理論も邪魔にならない程度に解説してくれているので、書かれているとおりに進めれば本当に作れてしまいます。正直、めちゃくちゃ楽しい体験でした。

いい時代になったものですね😂。

Monkey言語の特徴

MonkeyはVMを使わない素朴なインタプリタ言語で、現代的な機能はひととおり盛り込みつつも、あまり独自色を出さないようにしているところに好感が持てました。逆に考えれば、Monkeyの機能は今どきのインタプリタ系言語なら持っているのが普通ということでしょう。
クラスを使わないあたりがGo言語を思わせます。

// 同書サンプルより
let add = fn(a, b) { a + b };
let sub = fn(a, b) { a - b };
let applyFunc = fn(a, b, func) { func(a, b) };
applyFunc(2, 2, add);
applyFunc(10, 2, sub);

• {}によるブロック構文
• 1つの文は;で終わる
• 代入はlet
• 関数はファーストクラス扱いで、代入可能
• クロージャも使える
• 文字列、数値、配列、ハッシュが使える
• REPLがほぼ最初から使える

それでいて、以下のあたりにほんのりとRubyの匂いも感じられました。きっと著者はRubyも好きなのだろうと勝手に推測しています。

• 動的型付け
• ハッシュ{}のキーにはstringやint以外にtrue/falseも使える
• 出力はputs()

Monkey言語の構造

Monkey言語には以下の要素があります。

• メインとREPL
• token（キーワードや記号を定義）
• AST（抽象構文木と基本メソッド）
• object（evaluatorで使うオブジェクト）
• environment（実行コンテキストを保持する）
• lexer（コードをtokenに分割する）
• parser（lexerの出力を解析してASTを出力する）
• evaluator（ASTを評価してobjectに変換し、objectを動かす）
• 標準関数（サンプル）

Monkey言語の処理は以下のような流れで進みます。

• REPL開始
  • 入力をlexerに渡す
  • lexerはtokenを参照しながら入力をtokenに分割する
  • parserはtokenを受け取り、tokenをASTとして組み立てる
  • evaluatorはASTを受け取り、ASTノードからobjectとenvironmentを生成して、コードを評価（実行）する
• REPLは評価結果を受け取って出力する

Monkey言語を作ってみて

写経ではGo 1.14.3とVSCodeを用いました。

同書でのMonkey言語の構築は、基本的にテストドリブンで進められますが、説明上の理由であえてテストドリブンにしていない部分も少しあります。

集中的にやれば1日8時間として3日もあれば完走できます。わかりませんが、大学で言うと1〜2年生に相当するレベルなのでしょうか。なお、自分は巻末付録の「マクロ」の部分はやりませんでした。

同書を買うと、4つの章ごとのコードサンプルも利用できます↓。

2章ぐらいまではテストコードも無心に手入力しましたが、途中からはコードサンプルのテストコードをほぼそのまま流用したので、写経がとてもはかどりました。

特に楽しいのはクロージャを実装するあたりで、著者も興奮を隠しきれない様子でした。以前の自分もクロージャは一種の副作用か何かだと思い込んでいたのですが、明示的な実装が必要なんですね。

プログラミング言語を手作りする体験をしてみたいという奇特な方には、またとない良書だと思います。

同書では、Goのインターフェイス、埋め込み、関数リテラルのmap登録による標準関数定義など、Goの機能がふんだんかつ適切に使われているので、Goそのものをもっと学びたい人にもよい教材になると思いました。

// 同書よりast.go: 以下のようにASTのNodeをインターフェイスと埋め込みで定義している
type Node interface {
    TokenLiteral() string
    String() string
}

type Statement interface {
    Node
    statementNode()
}

type Expression interface {
    Node
    expressionNode()
}

type Program struct {
    Statements []Statement
}
...

// 同書よりbuiltin.go: 組み込み関数をmapの値として定義
var builtins = map[string]*object.Builtin{
    "len": &object.Builtin{
        Fn: func(args ...object.Object) object.Object {
            if len(args) != 1 {
                return newError("wrong number of arguments. expected: 1, got: %d", len(args))
            }

            switch arg := args[0].(type) {
            case *object.Array:
                return &object.Integer{Value: int64(len(arg.Elements))}
            case *object.String:
                return &object.Integer{Value: int64(len(arg.Value))}
            default:
                return newError("unsupported argument type to 'len()'. got: %s", args[0].Type())
            }
        },
    },
...    

ついでながら、Goで構造体をレシーバーにする場合、ほぼいつもポインタレシーバーが使われる理由が以前からよくわからなかったのですが、以下の記事でとてもよくわかりました。ありがとうございます。

参考: Go 言語の値レシーバとポインタレシーバ | Step by Step

同書のコードどおりでなかった部分

細かいですが、同書執筆時にはなかったGoモジュールに乗っかって作業したので、import文ではサンプルコードのようなmonkey/tokenではなく、ダミーのGitHubリポジトリの形でgithub.com/hachi8833/monkey/tokenのように書きました。これでよかったのかな...？

package ast

import (
    "bytes"
    "strings"

    "github.com/hachi8833/monkey/token"
)
...

また、自分が作ったMonkey言語は本と完全に同じではなく、メッセージや定数名は若干自分好みに変えてあります。というのも、同書が書かれた頃よりgofmtのルールが厳しくなったらしく、Go 1.14.3で同書のとおりに書くとgofmtによる怒られがいくつか発生したためです。

• 以下のように定数で_を使うと怒られるので_なしに書き換えた

// 同書より: parse.go
var precedences = map[token.TokenType]int{
    ...
    token.NOT_EQ:   EQUALS, // NOTEQに変えた
    ...
}

// 同書より: object.go
const (
    NULL_OBJ  = "NULL"  // NullObj = "NullObj"に変えた
...    

• tokenパッケージのTokenType型↓は参照がtoken.TokenTypeとなって冗長だから変えろと怒られたので、Typeとした。

// 同書より: token.go
package token

type TokenType string           // Typeに変えた

Gobyのしくみもちょっと見えてきた

例のGoby言語↓は、同書に強く影響されています。

• リポジトリ: goby-lang/goby: Goby - Yet another programming language written in Go

実際、写経しながらtoken/lexer/parser/ASTあたりの構成や命名が同書と実に似通っていることを実感できました。その代わり、同書ではやっていないRubyのYARV的なVMを実装している点が異なります。各所で言われているように、同書でも「インタプリタでもVMを使う方が速い」と力説されていました。

Gobyの場合、先のMonkey言語からobjectとevaluatorを取り払い、それに代わってbytecodeジェネレーターとVMが入った形になっています。

おまけ

作成したMonkey言語は自分のGitHubリポジトリにアップしましたが、著作権的な部分が気になったので念のためprivateにしました。ちょっと草が青々としてきましたね。

関連記事

Goby: Rubyライクな言語（2）Goby言語の全貌を一発で理解できる解説スライドを公開しました！