Writing an Interpreter in Go

March 20, 2024 · 12 min read

統計解析のためにRのコードを書く機会があったのだけど、これまで「お行儀のいい」言語に慣れていた身からすると、 dplyrで活用されているメタプログラミングのようなもの（いわゆるnon-standard evaluationと呼ばれている奴ら）の識別子とデータがコード上で厳密に区別されずにごちゃ混ぜになっている「柔らかさ」には強い違和感を覚えた。

どうなっているのか訳が分からないと感じたが、一方でこれも結局のところコンピューターで動いているわけだから、この振る舞いにも厳密なセマンティクスが存在していることには違いない。 Rの文法は一見すると、常識的な手続き型言語のような見た目をしているが、その内部はSchemeのようなLisp系言語に近いようである。また別のところでRのメタプログラミングやtidyverseの非正格評価についても整理したいと思っているが、そんな不思議言語に触れ（ざるを得なかっ）たことをきっかけに、言語処理系の中身への興味が再燃した。

パーサーの書き方や、クロージャーがどう実装されるのかとか、そういうことを理解するには作ってみるのが一番手っ取り早いだろうということで、 Writing an Interpreter in Goという本を読んでみた。僕の理解度には適切なレベルで、とても面白く読み進めることができた。

せっかくなので、この本の内容について、自分の理解を整理するためにも、感想をまとめておくことにする。

この本では、一般的なインタプリタ言語の構成に倣って、

Lexer: プログラムの文字列をトークン列に変換する
Parser: トークン列を抽象構文木(AST)に変換する
Evaluator: ASTを評価する

の3要素を順番に作っていき、最終的にMonkey languageのインタプリタが完成する。

なお、評価器については、ASTの各ノードを再帰的に評価するシンプルなtree-traversing interpreterになっているが、同じ言語でのスタック型仮想マシンを使ったバイトコード実行系の実装が同じ作者による続編「Writing a Compiler in Go」で紹介されている。

自作のMonkey languageは、中置記法の算術演算子、変数束縛、関数定義、条件分岐、再帰、クロージャー、配列、ハッシュマップ、文字列をサポートする言語で、例えば、以下のようなコードが書ける。

let fib = fn(x) {
  if (x == 0) {
    0
  } elseif (x == 1) {
    1
  } else {
    fib(x - 1) + fib(x - 2)
  }
};

print(fib(10))

let adder = fn(x) {
  fn(y) { x + y }
};

let addTwo = adder(2);
print(addTwo(3));

Parser

基本的にASTの各ノードに対応する関数を作り、それらを組み合わせるトップダウンの再帰下降パーサーを実装していく。

EBNFのようなフォーマルな形式で文法が定義されているわけではなく、 ifが文でなく式になっていて、セミコロンがどこで必要かなどが、本文の記載や公式の実装では曖昧に感じられて少し気になった。

let sign = if a < 0 { -1 } else { 1 }; // ここではセミコロンが必要

if err != nil {
  print("ERROR")
}  # ここでセミコロンは不要にするのが自然

この本では、通常の再帰下降パーサーに、式のパースのためPratt parserを組み合わせている。 Pratt parserは優先順位つきの演算子を含む式をパースするための手法で、 prefix opsとinfix/postfix opsのそれぞれについて、演算子ごとに関数を定義し、それを呼んでいくような構造で実装する。確かに式のパースが見通しよくすっきりと書ける。

例えば、C言語の文法のEBNF定義を見ると、

...
<conditional-expression> ::= <logical-or-expression>
                           | <logical-or-expression> ? <expression> : <conditional-expression>

<logical-or-expression> ::= <logical-and-expression>
                          | <logical-or-expression> || <logical-and-expression>

<logical-and-expression> ::= <inclusive-or-expression>
                           | <logical-and-expression> && <inclusive-or-expression>

<inclusive-or-expression> ::= <exclusive-or-expression>
                            | <inclusive-or-expression> | <exclusive-or-expression>

<exclusive-or-expression> ::= <and-expression>
                            | <exclusive-or-expression> ^ <and-expression>

<and-expression> ::= <equality-expression>
                   | <and-expression> & <equality-expression>
...

のような感じで、優先順位を考慮して式の文法要素を逐一定義しており、これを再帰下降パーサーで愚直に実装すると、式のパースのために関数のネストがかなり深くなることがわかる。 Pratt parserを使えば、このような文法を自然にパースすることができる。

Haskellの結合性定義(fixity declaration)のように動的に演算子を定義したり、優先順位や結合性（右結合、左結合）を変えたりできるような柔軟な文法を持つ言語の場合には、 Pratt parserのような手法が特に有効になるだろう。

Evaluator

単にASTのノードを再帰的に評価していくだけだろうと思っていたけれど、 return文やエラーをきちんと伝播させるための処理、何をtruthy/falsy valueとするかについての考察、環境の扱いなど、意外と細かいところでnon-trivialなことがたくさんあって、勉強になった。

Closure

lexical scopeとかclosureとか、なんとなくいろいろな場面で聞いたことがあるけれど、これまでイマイチどういったものか理解できていなかったが、今回実装してみたことで理解は深まった気がする。

Closureとは、関数が定義された時点での外側の環境を保持しておき、関数が実行されるときにその環境をも参照することで、 lexical scopeを実現する仕組みのことである。

変数の参照の際は、最も内側のスコープから順に外側のスコープを探索していくが、代入の際は、代入しようとする名前の変数が外側のスコープに存在する場合、その変数を更新するか、最も内側のスコープに新たな変数を定義して外側の変数を遮蔽するか、どちらの振る舞いも考えられる。

JavaScriptのように、変数の宣言と代入が区別されている言語では、宣言の際には最も内側のスコープに新たな変数を定義し、代入の際には、参照と同じく外側のスコープを探索して変数を更新する。

Pythonの場合は、変数の宣言と代入が区別されていないため、代入文では最も内側のスコープに変数を定義・更新するのがデフォルトの振る舞いで、外側のスコープも探索して変数を更新するためには、その変数についてnonlocal宣言を行う必要がある。

function createCounter() {
  let count = 0;
  return function() {
    count += 1;
    return count;
  }
}

def create_counter():
    count = 0
    def counter():
        nonlocal count
        count += 1
        return count
    return counter

Go言語について

GCによりメモリ管理が自動化されているので、低レベルなことを意識せずに実装できるのは楽。もちろん、メモリ管理など低レイヤな部分が言語処理系で最も本質的ではあるとは思うが、言語処理系作成入門という意味では、そこの難しさを言語のランタイムが隠蔽してくれるのはとてもありがたい。

C/C++と違ってスタックに確保された変数のアドレスを渡しても何も問題ないというのが、奇妙な感覚ではある。基本的にはシンプルな言語なのだけど、使い慣れていないこともあって、いくつか罠にハマることもあった。例えば、

nil interfaceについて：interfaceは型情報とデータのペアで、データがnilでも型情報があるため、nilとして扱われない
スライスのappend()は直感的でない。(buf, len, cap)の三つ組みからなる構造体だということを意識しないと、挙動が理解できない

だいたいはスクリプト言語のようなノリで気楽にかけるのだけど、一部は低レイヤな内部表現も意識しないと挙動が理解できないところがあって、慣れは必要だと感じた。

Parser​

Evaluator​

Closure​

Go言語について​

Parser

Evaluator

Closure

Go言語について