自由帳

@_nibral の技術ブログ

Writing An Interpreter In Go その8

その7はこちら

3.10: 関数の定義と呼び出し

3.9: Implement function call · nibral/monkey_interpreter@f09f2fd · GitHub

(コミットメッセージの章番号を間違えてた)

関数を定義する fn 構文と、定義した関数を呼び出す処理を実装する。本に従ってコードを書いていくと、構造体の定義、関数の処理と引数の取り出し、関数の評価という順で一つずつ進んでいく

ここでのポイントは2つ。

1つ目は関数実行時に Environment(変数空間) を入れ子構造にすること。下の例のように定義した関数の外側と内側で同じ変数名が使われる可能性があるので、関数呼び出しを評価する時にはプログラム全体の Environment (outer) とは別に関数内部でのみ使用する Environment (inner) も使う必要がある。

引数の値はinner側に追加する、innerに指定された識別子がなければouterを見に行く、という動作にすることでブロックスコープが実現できる。書いて動かしてみるとシンプルかつスマートな感じがした。

let i = 5;
let printNum = fn(i) {
  puts(i);
};

printNum(10);
puts(i);

2つ目は ReturnValue を返さないようにすること。式を評価した結果として ReturnValue を返すとそこでプログラムが終了するようになっているので、関数内部でreturn文が使われたときはReturnValueの値を取り出して(unwrapして)評価値とする必要がある。

let fooFunc = fn() {
  return 5;
}
fooFunc();  // ReturnValueをunwrapしないとここで終了してしまう
return 10;

3.11: メモリ解放の話

Q. 明示的なメモリ解放をしていないので、関数の再帰呼び出しが深くなると
  その分メモリを消費したままになりますがどうしたらいいですか
A. golangのガベージコレクション (GC) がよしなにしてくれるのでそれでよしとしましょう

ということでコードの追加はなし。

ともあれ、これでEvaluatorも完成。関数という一見複雑そうな機能を付けたわりに、追加したコードの量はそこまで多くなかったように感じる。

本の目次を見ると、残る4章では新しいデータ型として文字列・配列・ハッシュを追加するらしい。このシリーズもあと3回くらいで終わるか?

Writing An Interpreter In Go その7

その6はこちら

前回までの内容でREPLが電卓として使えるようになったので、if文とreturn文、それに変数の宣言と利用を追加して電卓からプログラミング言語にレベルアップさせる。

3.6: if文の評価

3.6: Evaluate if statements · nibral/monkey_interpreter@9645d49 · GitHub

ASTに Condition, Consequence, Alternative が格納されているので、Conditionの式を評価してどちらを実行するか決定する。

if <Condition> {
  <Consequence>
} else {
  <Alternative>
}

Parserにbooleanを追加したときと同様に、式がNULLまたはFALSEの時に偽、それ以外はすべて真として評価する。つまり数値の5は真。

>> if (5) { return true; } else { return false; }
true

ここの挙動は言語仕様の問題で、

  • 0を偽、それ以外を1として扱う(C言語
  • 型エラーにする(golang

などの選択肢がある。個人的には型エラーにするのが親切でいいかなと思う。

3.7: return文の評価

3.7: Evaluate return statements · nibral/monkey_interpreter@2f9e42d · GitHub

Monkeyでは最後に評価した値が戻り値になるが、return文が出現したときはそこで処理を打ち切って以降の文を実行しないようにする。

単にreturnが出た時に打ち切るだけだとブロックが入れ子になった時に正しく動作しない(下の例で1を返してしまう)ので、return文による戻り値であることを示す ReturnValue というオブジェクトを追加して処理を打ち切ったことをブロックの外側にも伝搬させる必要がある。

if (10 > 1) {
  if (10 > 1) {
    return 10;
  }

  return 1;
}

3.8: エラー処理を追加

3.8: Implement error handling · nibral/monkey_interpreter@f9ce1dc · GitHub

入力したコードに問題があって評価できないときに、単にnilを返すのではなく適切なエラーメッセージを返すようにした。「そんな演算子は知らん」とか「整数と真偽値を足してるぞ」とか。

return文の時と同様にエラーが発生したらそれ以降の処理はすべて打ち切る必要があるので、Errorというオブジェクトを追加した。2項演算子を評価する場合は右辺と左辺がそれぞれエラーになっていないかチェックする必要があるので、修正箇所は多め。

3.9: 変数の宣言と利用

3.9: Implement variable · nibral/monkey_interpreter@0548f28 · GitHub

値に識別子を付けてあとで使う、つまり変数の仕組みを追加する。

仕組みとしては非常に簡単で、文字列をキーとするオブジェクトのmapを持っておく。letで識別子が定義されたらmapに追加、別の場所で識別子が現れたらmapから取得。識別子がmapに存在しなければエラーにすればよい。

もちろんこのmapはプログラムの実行中ずっと同じものを保持していなければならないので、Environment という構造体を追加してRPELまたはテストコードから渡すようにする。

Evaluator 側でEnvironmentのインスタンスを作らずに、呼び出し側から渡してもらうあたりは DI (Dependency-Injection) っぽいと思ってるけどこの理解であってるのかな?

ここまで来るとREPLがかなりプログラミング言語っぽくなってくる。一丁前にエラーも出してくるが、自分のtypoを自分が作ったEvaluatorが見つけていると思うと「よしよしちゃんと動いとるな」という感じでニヤニヤしてしまった。

> go run .\main.go
Hello nibral! This is the Monkey programming language!
Feel free to type commands
>> let apple = 120;
>> let quantity = 3;
>> apple * quontity;
ERROR: identifier not found: quontity
>> apple * quantity;
360
>>

Writing An Interpreter In Go その6

その5はこちら

Parserが構築した抽象構文木 (AST) を評価し、入力したソースコードの意味を取り出すEvaluatorの作成に入る。

3.4: オブジェクト表現を実装

3.4: Implement object representation · nibral/monkey_interpreter@ac2828d · GitHub

Evaluatorで評価した値を扱うためにObjectというインターフェースを定義する。実際の評価結果はIntegerだったりBooleanだったりNullだったりするが、これらを表す構造体に全てObjectインターフェースを実装することになる。

全てはObject、と言われるとC#っぽいなと思ったり。

3.5: Integerの評価

3.5: Evaluate integer · nibral/monkey_interpreter@e018d49 · GitHub

プログラムを1行ずつ取り出してASTを再帰的に辿っていき、一番末端の IntergerLiteral (Parserの表現) から object.Integer (Evaluatorの表現) を生成して評価値とする。あるブロックに含まれるプログラムが複数行ある場合、最後に評価した値が戻り値として扱われる。

対話コンソールにも改良を行い、単にASTを出力していたところを評価結果の出力に変更。

3.5: Booleanと前置演算子の評価

3.5: Evaluate boolean and prefix expressions · nibral/monkey_interpreter@fa18985 · GitHub

IntegerLiteral と同様に Boolean と PrefixExpression の評価を追加。真偽を反転する ! 演算子を扱うにあたって true/false以外の値(例えば整数の5)に対する挙動をどうするか決める必要があるが、Monkeyではtrueとして扱うことになっている。つまり、!5 は false として評価される。

また、Evaluator内部ではTrue,False,Nullを示すオブジェクトを区別する必要がないので、あらかじめオブジェクトを生成しておいて使いまわす。

3.5: 2項演算子の評価

3.5: Evaluate infix expressions · nibral/monkey_interpreter@d341f9e · GitHub

+,-,*,/,<,>,==,! の評価。

いまのところ評価できるのは整数と真偽値だけなので、演算子の両辺が整数なら整数用の評価処理、真偽値なら ==/!= の評価を行う。真偽値の評価はオブジェクトを共有していることが前提なので、整数のcaseより後に書く必要がある。

// case文をこの順番で書かないと正しく評価されない
switch {
case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
    return evalIntegerInfixExpression(operator, left, right)
case operator == "==":
    return nativeBoolToBooleanObject(left == right)
case operator == "!=":
    return nativeBoolToBooleanObject(left != right)
default:
    return NULL
}

この時点で対話コンソールが電卓として使えるようになった。

> go run .\main.go
Hello nibral! This is the Monkey programming language!
Feel free to type commands
>> 2 + (3 * 4)
14
>> (1+2*3)==7
true
>>

Writing An Interpreter In Go その5 (Parser完成)

その4はこちら

引き続き各種トークンの処理を追加し、Parserを完成させる。

この辺から一部のテストコードが省略されるようになってきて、実装してテストが通った後に著者のコードと比べて答え合わせをする作業が増えた。

2.8: boolean

2.8: Add boolean · nibral/monkey_interpreter@9b60d31 · GitHub

true/false の値を持つ構造体を作って、token.TRUE/FALSE が来たらASTに追加する。

このコミットではテストの方が変更が多い。まず、前置演算子と2項演算子のテストで値が整数であること前提としていたのでbooleanも使えるように型をinterface{}に変更。ついでにリテラル (整数, 識別子, boolean) と2項演算子のASTが期待した値になっているかテストする処理を作って共通で使えるようにした。

2.8: 式のグループ化

2.8: Add grouped expressions · nibral/monkey_interpreter@e80c585 · GitHub

式の一部を括弧でくくって先に計算させるために、先に括弧の中身だけでASTを作る。一瞬で終わった。

2.8: if-else

2.8: Add if-else · nibral/monkey_interpreter@d9c439f · GitHub

ついに制御構文を処理するところまできた。if文は

if <条件式> {
  <処理ブロック>
} else {
  <処理ブロック>
}

という形式なので、ASTで使う構造体には条件式 (condition)・真の時の処理ブロック (consequence)・偽の時の処理ブロック (alternative)を持たせる。処理ブロックは1文とは限らないので、BlockStatement として複数の文が扱えるようにしておく。

type IfExpression struct {
    Token       token.Token
    Condition   Expression
    Consequence *BlockStatement
    Alternative *BlockStatement
}

構造体を定義したら、あとはifの構文に従ってフィールドを設定する parseIfExpression() を書く。順番にトークンを読んでいって、もしあるべき場所にあるべき括弧がなかったらその時点で nil を返してしまうので比較的読みやすいと感じた。

2.8: 関数定義

続いて関数の定義。Monkeyでは fn という語を使う。

fn (<パラメータ1>, <パラメータ2>, ...) {
  <処理ブロック>
}

↓

type FunctionLiteral struct {
    Token      token.Token
    Parameters []*Identifier
    Body       *BlockStatement
}

if文と同様、構文に従ってトークンを読み進める。fnの後ろには小括弧があって、その中身はパラメータなのでカンマごとに識別子として追加、続く中括弧の中身はすべてBlockStatement。もしこの形から外れたらその時点で return nil

2.8: 関数呼び出し

2.8: Add call expressions · nibral/monkey_interpreter@05202be · GitHub

Monkeyでの構文は <式>(<パラメータ1>, <パラメータ2>, ...) になる。上で定義した FunctionLiteral も式として扱えるので

fn (x, y) { x + y; }(2, 3);
callsFunction(2, 3, fn(x, y) { x + y; });

という書き方も許容されるが、自分で書くなら関数の部分をいったん変数に入れたいなぁという感じ。

識別子に続く ( を登録するだけだとダメで、関数呼び出しが最優先で処理される (=ASTの葉側になる) ように優先度を設定するところがポイント。

2.8: let と return に値をセット

2.8: Set values to let statement and return statement · nibral/monkey_interpreter@dd38cef · GitHub

コミットメッセージが雑すぎたかなという気がしている。2.4と2.5で後回しにした値の取り出し処理を追加した。

let と return の構造体に値がセットされるようになったので、いままで名前しか見ていなかったところを期待した値になっているかどうかのテストに置き換える。

2.9: RPPLの実装

2.9: Implement Read-Parse-Print-Loop (RPPL) · nibral/monkey_interpreter@ea32869 · GitHub

LetStatementのString()で値を出すのを忘れてたので追加して go run。よく考えたら1.5で作ったのもRead-Lexer-Print-Loopだし、REPLへの道のりはまだ長い。

monkey_interpreter> go run main.go
Hello AQUAMARINE\athlex! This is the Monkey programming language!
Feel free to type commands
>> let x = 1 + 2 * 3;
let x = (1 + (2 * 3))
>> fn (x, y, z) { return x + y + z; }
fn(x, y, z) return ((x + y) + z)
>> 

Parserの実装はいったんここまで。

ちなみに、本ではエラーが起きた時に猿のAAを表示する機能を付けているが、イラつくだけだと思ったので省略した。

↓こんな感じ

>> let x 12 * 3
            __,__
   .--.  .-"     "-.  .--.
  / .. \/  .-. .-.  \/ .. \
 | |  '|  /   Y   \  |'  | |
 | \   \  \ 0 | 0 /  /   / |
  \ '- ,\.-"""""""-./, -' /
   ''-' /_   ^ ^   _\ '-''
       |  \._   _./  |
       \   \ '~' /   /
        '._ '-=-' _.'
           '-----'
Woops! We ran into some monkey business here!
 parser errors:
        expected next token to be =, got INT instead

Writing An Interpreter In Go その4

その3はこちら

Parserへ識別子と演算子をASTに追加する処理をつけていく。

演算子には「左から右へ」「掛け算は足し算より先に」という優先順位があるが、C言語コンパイラにチャレンジしたときは生成規則からパーサを書こうとして左再帰で詰んだり、スタックマシンで計算させてみたら右から処理されてしまったりとつらい記憶しかない。個人的にここは鬼門だと思っている。

2.6: 識別子

2.6: Add parser of identifier · nibral/monkey_interpreter@763c848 · GitHub

パース処理をトークンの種類をキーとするMapに登録しておいて、let / return 以外のトークンが来たらトークンに合わせた処理を呼び出す仕組み。このコミットでは識別子 (token.IDENT) のみ登録した。

イベントハンドラを登録するのに似ていて、パース対象のトークンが増えたらその分登録すればよいのでスマートっぽい。

あと、デバッグ・テストでParserがトークン列をどのように解釈したかを確認するために、各パース処理に String() を生やした。演算子ごとにカッコでくくるようにして、

1 + 2 * 3 → (1 + (2 * 3))

という感じで出力させる。ただ、GoLandだとテストでもデバッガが使えるので、ASTの中身を見るだけならこっちの方が早い気もする。

f:id:nibral:20190112222935p:plain

演算子の優先順位を示す定数を追加したがこの時点では使用していない。

2.6: 整数

2.6: Add parser of integer literal · nibral/monkey_interpreter@d6f0f9c · GitHub

AST上で整数を表す構造体を定義して、トークンの文字列を64ビット整数に変換する処理を書いて、token.INT の処理として登録して終わり。

一応整数に変換できなかった時のエラー処理も書いてあるが、Lexerの実装上文字列には0-9の数値のみ含まれるはずなので発動するのは64ビット整数の範囲外だったときだけ?

2.6: 前置演算子

2.6: Add parser of prefix operators · nibral/monkey_interpreter@f494a20 · GitHub

! と - の処理。前置演算子を表す構造体に Right というフィールドがあり、再帰的に式を処理するようになって「あー木構造っぽいなー」という感じが出てくる。

演算子が正しく処理されたか・ぶら下がっている数値は正しいかの両方を確認するので、実装したコードよりもテストの方が倍くらい長い。テスト駆動っぽいといえばその通りだけど、テストを書くのが面倒でついコピペしてしまう。

実装が何もない状態だとIDEの補完が効かなくてテスト書きづらいし、実装のガワだけ作ることにするといつのまにか中身まで作っててテストが後になる。この辺の解決策というか、テスト駆動するにはどこまで設計すべきなのかが知りたい。

2.6: 2項演算子

2.6: Add parser of infix operators with precedence · nibral/monkey_interpreter@b0ae349 · GitHub

==, !=, <, >, +, -, /, * の処理を一気に追加。といってもASTの構造は全部同じなのでParserに登録するところ以外は共通で使える。シュッと実装してテスト走らせるとテストが通った。

何が起きているのかさっぱりわからないが優先順位は守られている。どういうこっちゃと思って本を見ると

We are now officially able to parse infix operator expressions correctly!

Wait, what? What the hell did just happen? How does this work?

ということで、先に動くものを作ってから解説するスタイルだった。

2.7章の解説では、本では "1 + 2 + 3;" という文を例として ((1 + 2) + 3) というASTができる流れを追いかける。一番のポイントは parser/parser.go の parseExpression() にあるこの処理。

for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
    infix := p.infixParseFns[p.peekToken.Type]
    if infix == nil {
        return leftExp
    }

    p.nextToken()

    leftExp = infix(leftExp)
}

for のループ条件に演算子の優先順位が入っているのと、infix() の中から parseExpression() を再帰的に呼ぶときに演算子に合わせた優先順位を渡すことで木構造が左に深くなるか右に深くなるかが制御されるようになっている。

実は一回読んだだけだとよくわからなくて、ステップ実行したり紙に書いてみたりして何となく理解したつもり。これだけ読んでも意味不明だと思うので、ちゃんと知りたい人は本を買ってください。内容的にはここまでで半分くらい。

interpreterbook.com

www.oreilly.co.jp

Writing An Interpreter In Go その3

その2はこちら

Lexerが完成してソースコードトークン列に分解できるようになったので、抽象構文木 (Abstract Syntax Tree, AST) を組み立てるParseの実装に入る。

バッカス・ナウア記法 (BNF) などで書かれた構文規則からParserを自動生成するParser Generatorというものもある (e.g. yacc, bison) が、この本ではGeneratorは使わずに自力でParserを作る。完成するParserは発明者の名前をとってPratt parserと呼ばれており、JSLintでも使われているらしい。

2.4: let のParserを実装

Implement parser of 'let' statement · nibral/monkey_interpreter@53cff67 · GitHub

Lexerのときと同じように、今読んでいるトークンの位置と次のトークンの位置を一つずつ進めていく。

ここでは変数を定義する "let x = 5;" のようなコード、トークンで言うと LET IDENT ASSIGN で始まって SEMICOLON で終わる部分を取り出してASTに追加する。この時点では名前を取り出しているだけなので、= と ; の間に何が入っていてもすべて読み飛ばす。

2.4: Parserにエラー処理を追加

Add error handling to parser · nibral/monkey_interpreter@fc9056d · GitHub

文法的におかしいトークンが出現したときにエラーを出すようになった。上で実装した let の場合、let の次に識別子がなかったり ("let = 10;") 、= がなかったり ("let x 5;") というエラーを検出できる。

「〇〇というトークンが来るはずだけど××が来た」という具体的なエラーメッセージが出るので、この時点でそこらのコンパイラより親切なのでは?という気持ちになる。

2.5: return のParserを追加

2.5: Add parser of 'return' statement · nibral/monkey_interpreter@64b4e6f · GitHub

文法上 "return <式>;" という形なので、return が出たら ; まで読み飛ばしてASTに追加する。let と同様返却する値の解析は後回しにしているので、return から ; までの間に何が書かれていてもエラーにならない。

あと、写経をミスってParser内部でしか使わない関数がpublicになっていたのでprivateにした。

Writing An Interpreter In Go その2 (Lexer完成)

その1はこちら

1.4: '==' と '!=' の追加

1.4: Add '==' and '!=' · nibral/monkey_interpreter@0b77bb3 · GitHub

lexer/lexer.go

演算子 == と != を追加した。2文字の演算子として処理させるのではなく、=/! の後に = が続くかどうか判定する処理を入れて =, ! の処理と共存させている。golangのswitch-caseは文字列を条件に設定できるので case "==": でもいいような気がするがいったん本の通りに進めることにした。

lexer/lexer_test.go

テストケースを追加。テーブルがかなり長くなってきた。

token/token.go

識別子を追加。

1.5: REPLの実装

1.5: Implement REPL · nibral/monkey_interpreter@efce289 · GitHub

Read Eval Print LoopでREPL。Pythonを起動したときに「>>>」というプロンプトが出てきて対話的にコードを実行できるみたいなやつ。この本独自の用語かと思ったら一般的なワードだった。

ja.wikipedia.org

main.go

mainパッケージが登場、ようやくビルドして実行できるようになる。

処理としてはWelcomeメッセージを表示してreplの処理を起動するだけ。err != nilが出てくるとgolangを感じる。GoLandで書いてたらuserという変数名がインポートしたパッケージ名と競合してるという警告が出たので、replUserにリネームした。

repl/repl.go

Enterを押すたびにユーザの入力を受け取ってLexerにかけ、トークンの一覧を表示する。exitコマンドの類はつけていないので、終了するときはCtrl+Cで抜ける。

Lexerのテストで字句解析に問題がないことがわかっていても、自分で打った文がちゃんとトークンの一覧に変換されると達成感があった。

monkey_interpreter> go run .\main.go
Hello nibral! This is the Monkey programming language!
Feel free to type commands
>> let a = 1 + 2;
{Type:LET Literal:let}
{Type:IDENT Literal:a}
{Type:= Literal:=}
{Type:INT Literal:1}
{Type:+ Literal:+}
{Type:INT Literal:2}
{Type:; Literal:;}
>> :
{Type:ILLEGAL Literal::}
>>