Golang でプログラミング言語を作る__Part23
前回は配列の実装を行いました。
今回はHashタイプ(Go言語でいうmap)を、言語に取り入れていきます。
Hashタイプのイメージとしては、次のようになります。
{hash literal: a value , ...}key-valueのペアが、コンマによって分けられるリストを表します。
では、実際にコードを書いていきます。今回も、以前行った流れ同様に、実装してきます。
まずが、TokenにHashタイプを表すタイプを設定します。token/token.goファイルのconst内に COLON = ":" を追加します。
また、lexer_test.goファイルのテストケースに {"foo": "bar"} を加えて、テストをfailさせます。
上のテストは、下のコードをlexer.goファイルの NextToken() 内に追加するとpassすることが確認できます。
tok = newToken(token.COLON, l.ch)以上が、HashタイプをlexerでToken化する処理になります。
次はparsing(解析)処理ですね。ここでは、ASTノードを設定する際に、Go言語のmap関数を使用します。それによって、key-valueのペア設定が簡潔になります。
ast/ast.go
type HashLiteral struct {
Token token.Token // the '{' token
Pairs map[Expression]Expression
}func (hl *HashLiteral) expressionNode() {}
func (hl *HashLiteral) TokenLiteral() string { return hl.Token.Literal }
func (hl *HashLiteral) String() string {
var out bytes.Bufferpairs := []string{}
for key, value := range hl.Pairs {
pairs = append(pairs, key.String()+":"+value.String())
} out.WriteString("{")
out.WriteString(strings.Join(pairs, ", "))
out.WriteString("}")return out.String()
}
このHashタイプに対して、今回は以下3つのテストを実施します。
一つ目はkeyが文字列であるHashタイプのケースを入力値とした時に、 ast.HashLiteral がparserから返ってくるかのテストです。
parser/parser_test.go
func TestParsingHashLiteralsStringKeys(t *testing.T) {
input := `{"one": 1, "two": 2, "three": 3}`l := lexer.New(input)
p := New(l)
program := p.ParseProgram()
checkParserErrors(t, p)stmt := program.Statements[0].(*ast.ExpressionStatement)
hash, ok := stmt.Expression.(*ast.HashLiteral)
if !ok {
t.Fatalf("exp is not ast.HashLiteral. got=%T", stmt.Expression)
}expected := map[string]int64{
"one": 1,
"two": 2,
"three": 3,
}if len(hash.Pairs) != len(expected) {
t.Errorf("hash.Pairs has wrong length. got=%d", len(hash.Pairs))
}for key, value := range hash.Pairs {
literal, ok := key.(*ast.StringLiteral)
if !ok {
t.Errorf("key is not ast.StringLiteral. got=%T", key)
continue
}expectedValue := expected[literal.String()]
testIntegerLiteral(t, value, expectedValue)
}
}
このテスト内でも、期待される値をmapでつくり、実際に返ってくるリストと比較しながらテストされています。
この2つめのテストには input := "{}" を入れて、3つめのテストには、 input := `{"one": 0 + 1, "two": 10 — 8, "three": 15 / 5}` で行います。
上記3つのテストがfailするのを確認したら、上のテストがpasするような、parser処理を加えていきます。
まず、parserの初期化関数、 New() 内に、token.LBRACEタイプとHashタイプ用の解析関数を結べつけます。
parser/parser.go
p.registerPrefix(token.LBRACE, p.parseHashLiteral)解析関数(parserHashLiteral)の処理は、次のようになります。
func (p *Parser) parseHashLiteral() ast.Expression {
hash := &ast.HashLiteral{Token: p.curToken}
hash.Pairs = make(map[ast.Expression]ast.Expression)for !p.peekTokenIs(token.RBRACE) {
p.nextToken()
key := p.parseExpression(LOWEST) if !p.expectPeek(token.COLON) {
return nil
}
p.nextToken()
value := p.parseExpression(LOWEST) hash.Pairs[key] = value
if !p.peekTokenIs(token.RBRACE) && !p.expectPeek(token.COMMA) {
return nil
}
}
if !p.expectPeek(token.RBRACE) {
return nil
}
return hash
}
ここまでの処理を終えて、 go test ./parser のテストがpassすることを確認したら、解析処理は完了です。
次は、Hashタイプの評価に移ります。
evaluatorの実装の前に、Hashを包むオブジェクトを設定する必要がありました。しかし、Hashの仕様上、少し複雑になります。
ですので、まずはHashを包むオブジェクトがどのような機能を持ってほしいかを、次のテストケースを持って確認します。
object/object_test.go
func TestStringHashKey(t *testing.T) {
hello1 := &String{Value: "Hello World"}
hello2 := &String{Value: "Hello World"}
diff1 := &String{Value: "My name is johnny"}
diff2 := &String{Value: "My name is johnny"}if hello1.HashKey() != hello2.HashKey() {
t.Errorf("strings with same content have different hash keys")
}if diff1.HashKey() != diff2.HashKey() {
t.Errorf("strings with same content have different hash keys")
}if hello1.HashKey() == diff1.HashKey() {
t.Errorf("strings with different content have same hash keys")
}
}
上のケースは、Hashタイプのkeyが文字列である場合のテストになります。実際には、keyは他2つの値、論理値と数値タイプを認めていますので、残りの2つも同様のobject testを書きます。
このテストをfailさせたら、次の HashKey タイプを作成します。
type HashKey struct {
Type ObjectType
Value uint64
}type Hashable interface {
HashKey() HashKey
}
このHash keyを扱うオブジェクトを、各値(boolean, string, integer)に備え付け(embedding)します。
func (i *Integer) HashKey() HashKey {
return HashKey{Type: i.Type(), Value: uint64(i.Value)}
}func (b *Boolean) HashKey() HashKey {
var value uint64if b.Value {
value = 1
} else {
value = 0
}return HashKey{Type: b.Type(), Value: value}
}func (s *String) HashKey() HashKey {
h := fnv.New64a()
h.Write([]byte(s.Value))return HashKey{Type: s.Type(), Value: h.Sum64()}
}
これによって、各値タイプのオブジェクトから、Hashのkeyを操作することができます。処理はシンプルに、HashKeyオブジェクトをそれぞれの値をもって、返される処理になります。
以上の処理を書いた後に、 go test ./object を走らせpassすることを確認します。
そしたら、 Hash本体の(今まではHashのkeyの取扱い)オブジェクトを、次のように設定します。
type HashPair struct {
Key Object
Value Object
}type Hash struct {
Pairs map[HashKey]HashPair
}
Hashタイプの解釈には、上記のKEYとVALUEとが、それぞれのペアを区別して、保存していく必要があります。
func (h *Hash) Inspect() string {
var out bytes.Bufferpairs := []string{}
for _, pair := range h.Pairs {
pairs = append(pairs, fmt.Sprintf("%s: %s",
pair.Key.Inspect(), pair.Value.Inspect()))
}out.WriteString("{")
out.WriteString(strings.Join(pairs, ", "))
out.WriteString("}")return out.String()
}
これで、オブジェクトの設定は終了です。
次はいよいよ、Hashタイプの解釈(evaluation)に移っていきます。
テストケースは次の入力値をもたせ、
input := `let two = "two";
{
"one": 10 - 9,
two: 1 + 1,
"thr" + "ee": 6 / 2,
4: 4,
true: 5,
false: 6
}`期待されるkey-valueのペアは、次のようになります。
expected := map[object.HashKey]int64{
(&object.String{Value: "one"}).HashKey(): 1,
(&object.String{Value: "two"}).HashKey(): 2,
(&object.String{Value: "three"}).HashKey(): 3,
(&object.Integer{Value: 4}).HashKey(): 4,
TRUE.HashKey(): 5,
FALSE.HashKey(): 6,
}keyには、オブジェクトで設定した全ての値タイプが、この入力値に使わえれています。このテストをfailさせたら、次はevaluatorを作っていきます。
evaluator/evaluator.go
case *ast.HashLiteral:
return evalHashLiteral(node, env)上の処理をtop-levelの解釈関数、Evalに加えます。
更に、 Hashタイプの解釈関数は次のようになります。
func evalHashLiteral(
node *ast.HashLiteral,
env *object.Environment,
) object.Object {
pairs := make(map[object.HashKey]object.HashPair)for keyNode, valueNode := range node.Pairs {
key := Eval(keyNode, env)
if isError(key) {
return key
} hashKey, ok := key.(object.Hashable)
if !ok {
return newError("unusable as hash key: %s", key.Type())
} value := Eval(valueNode, env)
if isError(value) {
return value
} hashed := hashKey.HashKey()
pairs[hashed] = object.HashPair{Key: key, Value: value}
}return &object.Hash{Pairs: pairs}
}
処理の流れは、次のようになります
- map型のリストを作ります。これは
object.HashPairを表します。 - 次はループ処理です。ペアがある限りループは行われます。
- まず、keyが
Eval関数で評価されます - このkeyが正しくない場合はerrorをだします。
- 次にこのkeyが
object.Hashableであるかどうかテストします。つまりは使用可能なタイプ、数値、論理値、また文字列タイプでなければエラーをだします。 - つぎはkey-valueの、valueを評価します
- 最後に、keyとvalueとを、それぞれを
object.Haspairに渡してインスタンス化します。ここで、一組のペアが作成されます - ループ処理が終わり、7のpairのリストが全てが出揃った時
&object.Hash(Hashを扱うオブジェクトの参照アドレス)に渡します。
以上のevaluation処理を書き終えて、テストを走らせた時にpassすることを確認したら、Hashタイプの実装は終了です。
更に、HashタイプのIndexを有効にさせる処理を追加します。が、これは配列時に行った処理と同様のものになります。
evaluator.goファイル内の、 evalIndexExpression で、Hashタイプ用の分岐処理を加えます。
以上がHash機能の実装になります。
