Writing An Interpreter In Go その9（終）

その8はこちら

この本に取り組み始めて1か月が経ってしまいそうだったので、日曜丸1日を使って残りを全部終わらせることにした。

4章では文字列型、配列、ハッシュの構文と、それに付随する組み込み関数をいくつか追加する。インタプリタの仕組みはすでに完成しているので、それぞれの構文について

構文に必要な記号の処理をLexerに追加
構文を表す構造体を定義し、AST上で表現できるようにParserを変更
文法的な意味を評価する処理をEvaluatorに追加

という作業を行うことになる。

4.2: 文字列型

4.2: Parse and evaluate strings · nibral/monkey_interpreter@aeaa9b1 · GitHub

Monkeyにおける文字列は、"foobar" のように対象をダブルクオーテーションで挟む形で表記する。

上で示した流れに沿って、

Lexerに「 " が出現したら次の " までを文字列トークンとする」処理を追加
Parserに文字列を表す構造体を追加
Evaluatorでは構造体の持つ文字列をそのまま評価値とする

の順に改良すると文字列が扱えるようになる。

4.2: Concat strings · nibral/monkey_interpreter@782322f · GitHub

あわせて+演算子を使った文字列の連結も追加する。これは簡単で、演算子の両辺が文字列の場合は連結した文字列を評価値とすればよい。

>> "hello" + " world"
hello world
>> let greet = fn(first, last) { "Hello, " + first + " " + last + "!" }
>> greet("John", "Doe")
Hello, John Doe!
>>

4.3: 組み込み関数 (len)

4.3: Add built-in function (len) · nibral/monkey_interpreter@0a22d78 · GitHub

文字列の長さを返す組み込み関数 len() を追加する。

長さを求める処理はgolangに同名の関数があるのでそのまま使うことにして、"len"というキーワードが出たら識別子ではなく組み込み関数の呼び出しとして評価するようにEvaluatorの処理を変更。

>> len("Hello World!")
12
>> len("")
0

4.4: 配列

4.4: Implement array · nibral/monkey_interpreter@92fcd31 · GitHub

Monkey以外の多くの言語と同じように、配列は大括弧とカンマを使って [var1, var2, var3] と表現する。

Lexerで [ と ] を処理できるようにするとParserで配列宣言の始まりと終わりが認識できるようになるので、あとはカンマ区切りの式を順番に評価していく。この動きは関数の機能を付けた時に引数の処理ですでに実装したものがあるので、宣言の終わりを意味する文字を指定できるように改良して流用できる。

配列の仕組みそのものはgolangの配列をそのまま使っているので目新しいことはなく、なんか消化試合っぽいなぁと思ったり。

4.4: Add built-in functions for array · nibral/monkey_interpreter@2630420 · GitHub

組み込み関数も改良。len()で配列の長さを取得できるようにしたのと、first/last/rest という配列特有の処理を行う関数を追加した。

この辺の関数と高階関数をうまいこと組み合わせるとmapとかreduceも実現できるらしい。すごい。

>> let a = [1, 2, 3, 4];
>> let double = fn(x) { x * 2 };
>> map(a, double);
[2, 4, 6, 8]

4.5: ハッシュ

4.5: Implement hash · nibral/monkey_interpreter@166b489 · GitHub

最後に追加するのはハッシュ。言語によってはマップとか辞書とか呼ばれるが、要はkey-valueの形で値を保持する仕組みのこと。

ここで面白かったのは key の扱い。いまのつくりでは各行に現れた文字列を別々のオブジェクトとして扱うので、keyとなるオブジェクトをそのまま使ってしまうと同じ文字列なのにHashから値が取り出せなくなってしまう。

文章だとわかりにくいので本文のコードを抜粋。Javaの文字列を .equals じゃなくて == で比較してアレ？ってなるのと同じ。たぶん。

name1 := &object.String{Value: "name"}
monkey := &object.String{Value: "Monkey"}

pairs := map[object.Object]object.Object{}
pairs[name1] = monkey
fmt.Printf("pairs[name1]=%+v\n", pairs[name1])       // => pairs[name1]=&{Value:Monkey}

name2 := &object.String{Value: "name"}
fmt.Printf("pairs[name2]=%+v\n", pairs[name2])       // => pairs[name2]=<nil>
fmt.Printf("(name1 == name2)=%t\n", name1 == name2)  // => (name1 == name2)=false

この問題を解決するために、MonkeyではHashKeyという整数値を使う。booleanなら0/1、intならその値、文字列ならFNV-1というアルゴリズムで求めたハッシュ値をkeyにすることで、同じ値を示す別々のオブジェクトを通してHashの値を取り出せるようになった。

FNV-1って初めて聞いたけど、SHA-1やMD5と比べると軽くて速いらしい。（その代わり暗号化には使えない？）

qiita.com