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

Tuyoshi Akiyama
Aug 22, 2017 · 13 min read

前回までは、evaluation(ASTの意味付け)を行う際の基礎となる、オブジェクトそれぞれを値ごとにつくりました。

parserから渡されるASTを、一度、各値のオブジェクトに入れてからevaluatingを行っていくことが今回の内容になります。

まずは、数値型と論理型の評価から行っていきます。

解析する関数は、イメージとして、下の Eval() 関数で行います。

func Eval(node ast.Node) object.Object

parserからの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.Object
for _, 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).Value
switch 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処理によって、ソースコードがかなり扱いやすくなっているのが正しいですね。

)
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