Golang でプログラミング言語を作る__Part13
前回までは、evaluation(ASTの意味付け)を行う際の基礎となる、オブジェクトそれぞれを値ごとにつくりました。
parserから渡されるASTを、一度、各値のオブジェクトに入れてからevaluatingを行っていくことが今回の内容になります。
まずは、数値型と論理型の評価から行っていきます。
解析する関数は、イメージとして、下の Eval() 関数で行います。
func Eval(node ast.Node) object.ObjectparserからのASTノードを取って、objectに変換していますね。
まずは、数値(Integer Literal)タイプから始めます。今回もTDDの手法で実装していきます。テスト→実装の順番ですね。
evaluator/evaluator_test.go
func TestEvalIntegerExpression(t *testing.T) {
tests := []struct {
input string
expected int64
}{
{"5", 5},
{"10", 10},
}for _, tt := range tests {
evaluated := testEval(tt.input)
testIntegerObject(t, evaluated, tt.expected)
}
}func testEval(input string) object.Object {
l := lexer.New(input)
p := parser.New(l)
program := p.ParseProgram()
env := object.NewEnvironment()return Eval(program, env)
}func testIntegerObject(t *testing.T, obj object.Object, expected int64) bool {
result, ok := obj.(*object.Integer)
if !ok {
t.Errorf("obj is not Integer, Got=%T (%+v)", obj, obj)
return false
}if result.Value != expected {
t.Errorf("object has wrong value, Got=%d, want=%d", result.Value, expected)
return false
}
return true
}
実際に上のテストを走らせて、 TestIntegerExpression が呼ばれます。
入力値(ソースコード)は Eval 関数に送られ、evaluation処理がされた値と、期待される値とが等しいかを testIntegerObject でテストしています。
上のEval 関数を次のようになります。
func Eval(node ast.Node) object.Object {
switch node := node.(type) {
case *ast.IntegerLiteral:
return &object.Integer{Value: node.Value}
return nil }ASTの構造タイプから、そのタイプのオブジェクトを返す関数になっています。
上のテストをfailさせたら、評価(evaluate)の実装です。
evaluator/evaluator.go
func Eval(node ast.Node, env *object.Environment) object.Object {
switch node := node.(type) {
// its for Statements
case *ast.Program:
return evalStatements(node.Statements)// its for Expression, after here, it should be evaluated to each node type
case *ast.ExpressionStatement:
return Eval(node.Expression, env)
case *ast.IntegerLiteral:
return &object.Integer{Value: node.Value}
return nil
}
このEval関数がparserからASTノードを渡される、top-levelの評価関数になります。
ast.Integer タイプが渡された時は、 &object.Integer が返されます。
ast.Program が渡された時は、下の evalStatement 関数に渡されます。
func evalStatements(stmts []ast.Statement) object.Object {
var result object.Objectfor _, statement := range stmts {
result = Eval(statement)if returnValue, ok := result.(*object.ReturnValue); ok {
return returnValue.Value
}
}
return return
}
このテストがpassすることを確認したら、このevaluation機能をREPLに反映させます。
repl/repl.go
func Start(in io.Reader, out io.Writer) {
scanner := bufio.NewScanner(in)
env := object.NewEnvironment()for {
// [...]
line := scanner.Text()
l := lexer.New(line)
p := parser.New(l)// [...]
evaluated := evaluator.Eval(program)
if evaluated != nil {
io.WriteString(out, evaluated.Inspect())
io.WriteString(out, "\n")
}
}
}
処理内容はシンプルで、ASTノードに変換したソースコード(program)を Eval 関数に渡したものになります。
ここで、 go run main.go で、数値が正常に評価されているか確認できれば、evaluationの反映は完了です。
次は、論理値とNULLになります。
まず、テストにBooleanをソースに含むテストと、返ってくる値がobject.Booleanタイプであるかのテストを、数値型同様に書きます。
そしてテストのfailを確認したら、evaluatorの実装になります。
evaluator/evaluator.go
var (
NULL = &object.Null{}
TRUE = &object.Boolean{Value: true}
FALSE = &object.Boolean{Value: false}
)まず、論理値もNULLタイプも、渡される値は決まっていますので、参照渡しされたobjectタイプを返すようにします。つまり、毎度新しいインスタンスを作成するのは、効率的では無い為です。
この後、 Eval 関数にASTが論理値である時の分岐と、その分岐先の処理内容を書いてテストをpassさせます。
ここまで、数値、論理値とNULLの評価を実装しました。次は、prefix値タイプとinfix値タイプに対応した処理をつくります。
まずは、prefixについてですが、処理はシンプルですね。というのも、今回はprefixタイプは (! or -)の二種類だけだからです。
まずはテストケースの作成です。
func TestBangOperator(t *testing.T) {
tests := []struct {
input string
expected bool
}{
{"!true", false},
{"!false", true},
{"!5", false},
{"!!true", true},
}for _, tt := range tests {
evaluated := testEval(tt.input)
testBooleanObject(t, evaluated, tt.expected)
}
}
ここでのtrueは、nullでもfalseでも無い値をtrueとしている事が分かります。
evaluatorには Eval 関数にASTがprefixタイプである時の分岐を書き、分岐先の関数は次のような処理になります。
func evalPrefixExpression(operator string, right object.Object) object.Object {
switch operator {
case "!":
return evalBangOperatorExpression(right)
default:
return newError("unknown operator: %s%s", operator, right.Type())
}
}func evalBangOperatorExpression(right object.Object) object.Object {
switch right {
case TRUE:
return FALSE
case FALSE:
return TRUE
case NULL:
return TRUE
default:
return FALSE
}
}
上の evalPrefixExpression 内の分岐には、後ほど-(マイナス)用の分岐処理を加えます。
ここで!(Bangの)evaluatorの実装が終わりましたので、テストを走らせpassすることを確認します。
-(マイナス用の)テストですが、数値の際に書いた TestIntegerExpression にマイナスを持つ数値(Integer Literal)を加えて、!(Bang)同様にevaluatorの実装を行います。
次は、infix値タイプを扱っていきます。
infixタイプには、結果として数値が返されるものと、論理値が返されるものがあり、それぞれを別でテストする必要があります。
evaluator/evaluator_test.go
func TestEvalIntegerExpression(t *testing.T) {
tests := []struct {
input string
expected int64
}{
{"5", 5},
{"10", 10},
{"-5", -5},
{"-10", -10},
{"5 + 5 + 5 + 5 - 10", 10},
{"2 * 2 * 2 * 2 * 2", 32},
{"-50 + 100 + -50", 0},
{"5 * 2 + 10", 20},
{"5 + 2 * 10", 25},
{"20 + 2 * -10", 0},
{"50 / 2 * 2 + 10", 60},
{"2 * (5 + 10)", 30},
{"3 * 3 * 3 + 10", 37},
{"3 * (3 * 3) + 10", 37},
{"(5 + 10 * 2 + 15 / 3) * 2 + -10", 50},
}// [...]
上のテストケースは、infixタイプの数値を返すケースになります。
このテストを走らせfailすることを確認したら、次はevaluatorの実装に移ります。
func evalInfixExpression(operator string, left, right object.Object) object.Object {
switch {
case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
return evalIntegerInfixExpression(operator, left, right)
}
}ここで、infixノードのleft/right両サイドが数値である場合は、 evalIntegerInfixExpression 関数に処理が移ります。
今回はここでの処理は(数値 operator 数値)でしたが、違うタイプ同士のinfixの場合どの処理を行うかを、この関数内で拡張してくことが出来ますね。
evalIntegerInfixExpression 関数は次のように、計算処理を担います。
func evalIntegerInfixExpression(operator string, left, right object.Object) object.Object {
leftVal := left.(*object.Integer).Value
rightVal := right.(*object.Integer).Valueswitch operator {
case "+":
return &object.Integer{Value: leftVal + rightVal}
case "-":
return &object.Integer{Value: leftVal - rightVal}
case "*":
return &object.Integer{Value: leftVal * rightVal}
case "/":
return &object.Integer{Value: leftVal / rightVal}
// from later this implementaition, it will be writtern some operators for boolean case
}
}
上の処理を書き終え、このテストがpassすることを確認したらもう一つのinfix(論理値を返り値に持つ)を同様に実装していきます。
実装のポイントとしては、常に論理値にはpointer(参照渡し)の比較、つまりTRUE/FALSEだけを使っていきます。つまりオブジェクトで包まれた値を比較する、インスタンス同士の比較ではなく、値そのもの(trueとfalseだけ)を比較する必要があります。
ここまで、infixタイプのevaluatorを実装しました。
次は、if文の解釈(evaluation)を作っていきます。
感想
ここまでを終えたら、 go run main.go を走らせ、実際にいままでのevaluatorが機能してきるのか確認できます。
実際に、ちょっとずつコードが動いてくのが面白いですね。
なによりも、今までのparsing(解析処理)の部分がかなり濃厚な内容だっただけに、今のevaluatorが楽に感じます。
と言うよりは、parsing処理によって、ソースコードがかなり扱いやすくなっているのが正しいですね。
