Golang でプログラミング言語を作る__Part23

Tuyoshi Akiyama
Aug 24, 2017 · 13 min read

前回は配列の実装を行いました。

今回は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.Buffer
pairs := []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 uint64
if 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.Buffer
pairs := []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}
}

処理の流れは、次のようになります

  1. map型のリストを作ります。これは object.HashPair を表します。
  2. 次はループ処理です。ペアがある限りループは行われます。
  3. まず、keyが Eval 関数で評価されます
  4. このkeyが正しくない場合はerrorをだします。
  5. 次にこのkeyが object.Hashable であるかどうかテストします。つまりは使用可能なタイプ、数値、論理値、また文字列タイプでなければエラーをだします。
  6. つぎはkey-valueの、valueを評価します
  7. 最後に、keyとvalueとを、それぞれを object.Haspair に渡してインスタンス化します。ここで、一組のペアが作成されます
  8. ループ処理が終わり、7のpairのリストが全てが出揃った時 &object.Hash (Hashを扱うオブジェクトの参照アドレス)に渡します。

以上のevaluation処理を書き終えて、テストを走らせた時にpassすることを確認したら、Hashタイプの実装は終了です。

更に、HashタイプのIndexを有効にさせる処理を追加します。が、これは配列時に行った処理と同様のものになります。

evaluator.goファイル内の、 evalIndexExpression で、Hashタイプ用の分岐処理を加えます。

以上がHash機能の実装になります。

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade