「Go言語でつくるインタプリタ」のつづき ~再代入可能な変数を実装してみる~

Go言語でつくるインタプリタという本を読みました。この本を読み進めながらコードを書いていくと、数値、加減乗除、文字列、配列、ハッシュ、if文、関数呼び出し等々、を実現するインタプリタがあっという間に実装できます。今年発売されたGo言語関連の書籍の中でも1、2を争う名著ではないでしょうか。
とはいえ、個人的には物足りないなと思う点もあり、その中の一つが再代入できる変数が存在しないことでした。

let x = 0;
x = 1; // error!!

ということで、自分で実装してみることにしました。
以下の説明は、 Go言語でつくるインタプリタを読んでない方にとってはピンと来ないかもしれませんが、あしからず。

仕様

varをつけて変数を定義すると、再代入可能な変数を定義できます。
また、代入式は式として評価され、代入された値が返ります。

var x = 1;
x = 2; // 再代入できる
var y = x = 3;  // 代入式(x = 3)は3を返すので、y = 3となる

字句解析

新たに追加するvarを特別なTokenとして読み込むようにする必要があるので、varをキーワードに追加します。

token.go

var keywords = map[string]TokenType{
    ...
    "var":    VAR,
}

構文解析

varによる変数定義文を表現するVarStatementをastのnodeとして新たに追加します。

ast.go

type VarStatement struct {
	Token token.Token
	Name  *Identifier // 左辺の変数(識別子)
	Value Expression  // 右辺の式
}

そして、以下のように構文解析を行います。

parser.go

// `var`のTokenを読み込むと呼ばれる関数
func (p *Parser) parseVarStatement() *ast.VarStatement {
	stmt := &ast.VarStatement{Token: p.curToken}
	
	// `var`の次は`Identfier`
	if !p.expectPeek(token.IDENT) {
		return nil
	}

	stmt.Name = &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}

	// `Identfier`の次は`=`(ASSIGN)
	if !p.expectPeek(token.ASSIGN) {
		return nil
	}

	p.nextToken()

	// 右辺の式を解析する
	stmt.Value = p.parseExpression(LOWEST)

	if p.peekTokenIs(token.SEMICOLON) {
		p.nextToken()
	}

	return stmt
}

また、代入式はAssignExpressionというastのnodeを定義します。

ast.go

type AssignExpression struct {
	Token token.Token
	Name  *Identifier
	Value Expression
}

代入式の構文解析を行う関数は、Pratt構文解析におけるInfixのパターンとして登録します。

parse.go

func New(l *lexer.Lexer) *Parser {
	p := &Parser{l: l, errors: []string{},}

	...	

	// Infixとして、代入式の構文解析を行う関数(parseAssignExpression)を登録する
	p.registerInfix(token.ASSIGN, p.parseAssignExpression)

	return p
}

// `=`を読み込むと呼ばれる代入式の構文解析を行う関数。引数として、左辺のnodeが渡される。
func (p *Parser) parseAssignExpression(left ast.Expression) ast.Expression {
	// 左辺はIdentifierであること
	ident, ok := left.(*ast.Identifier)
	if !ok {
		return nil
	}

	assign := &ast.AssignExpression{Token: p.curToken, Name: ident}

	p.nextToken()

	// 右辺の式を解析する
	assign.Value = p.parseExpression(LOWEST)

	return assign
}

評価

変数の構造体に、「再代入可能か」を示すIsMutableというフィールドを追加します。

environment.go

type Value struct {
	Obj Object
	IsMutable bool
}

そして、再代入不可なLetStatementの場合はIsMutable=falseに、再代入可能なVarStatementの場合はIsMutable=trueとして、変数をセットします。
代入式AssignExpressionは、左辺の変数がIsMutable=trueであることを確認してから、右辺の値を変数に代入します。

evaluator.go

func Eval(node ast.Node, env *object.Environment) object.Object {
	switch node := node.(type) {
	...
	case *ast.LetStatement: // 再代入不可のLetStatement
		// 右辺を評価
		val := Eval(node.Value, env)
		if isError(val) {
			return val
		}
		env.Set(node.Name.Value, val, false) // isMutable = false として変数を登録
	case *ast.VarStatement: // 再代入可のVarStatement
		// 右辺を評価
		val := Eval(node.Value, env)
		if isError(val) {
			return val
		}
		env.Set(node.Name.Value, val, true) // isMutable = true として変数を登録
	case *ast.AssignExpression: // 代入式
		identVal, ok := env.Get(node.Name.Value)
		if !ok {
			// 未定義の変数には代入できない
			return newError("identifier not found: " + node.Name.Value)
		}

		if !identVal.IsMutable {
			// 再代入不可の変数には代入できない
			return newError("can't assign value to immutable identifier: " + node.Name.Value)
		}

		// 右辺を評価
		val := Eval(node.Value, env)
		if isError(val) {
			return val
		}
		env.Set(node.Name.Value, val, true) // isMutable = true として登録する
		return val  // 代入した値を返す
	}
	...
	}
	return nil
}

これで、実装完了です！

REPLで試してみる

>> var i = 0; i = 1;
1
>> var x = 1; var y = 2; var z = x = y = 3;   
>> x
3
>> y
3
>> z
3
>> j = 0
ERROR: identifier not found: j
>> let k = 0
>> k = 1
ERROR: can't assign value to immutable identifier: k

ちゃんと動いてそうですね

まとめ

「インタプリタを作る」というと、かなりハードルの高いものだと思っていましたが、このように簡単なものであれば、案外あっさりと実装することができました。この記事では、一部のコードしか記載しなかったので、全体の差分が見たい方は こちらのPRをご覧ください。

参考