From 69fc902f8f5fd8f36db0991f6ba4faeabb3090fa Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sat, 20 May 2017 16:27:42 +0200 Subject: 03 --- evaluator/evaluator.go | 325 ++++++++++++++++++++++++++++++++++++++++ evaluator/evaluator_test.go | 351 ++++++++++++++++++++++++++++++++++++++++++++ object/environment.go | 30 ++++ object/object.go | 85 +++++++++++ repl/repl.go | 10 +- 5 files changed, 799 insertions(+), 2 deletions(-) create mode 100644 evaluator/evaluator.go create mode 100644 evaluator/evaluator_test.go create mode 100644 object/environment.go create mode 100644 object/object.go diff --git a/evaluator/evaluator.go b/evaluator/evaluator.go new file mode 100644 index 0000000..c8fa09a --- /dev/null +++ b/evaluator/evaluator.go @@ -0,0 +1,325 @@ +package evaluator + +import ( + "fmt" + "monkey/ast" + "monkey/object" +) + +var ( + NULL = &object.Null{} + TRUE = &object.Boolean{Value: true} + FALSE = &object.Boolean{Value: false} +) + +func Eval(node ast.Node, env *object.Environment) object.Object { + switch node := node.(type) { + + // Statements + case *ast.Program: + return evalProgram(node, env) + + case *ast.BlockStatement: + return evalBlockStatement(node, env) + + case *ast.ExpressionStatement: + return Eval(node.Expression, env) + + case *ast.ReturnStatement: + val := Eval(node.ReturnValue, env) + if isError(val) { + return val + } + return &object.ReturnValue{Value: val} + + case *ast.LetStatement: + val := Eval(node.Value, env) + if isError(val) { + return val + } + env.Set(node.Name.Value, val) + + // Expressions + case *ast.IntegerLiteral: + return &object.Integer{Value: node.Value} + + case *ast.Boolean: + return nativeBoolToBooleanObject(node.Value) + + case *ast.PrefixExpression: + right := Eval(node.Right, env) + if isError(right) { + return right + } + return evalPrefixExpression(node.Operator, right) + + case *ast.InfixExpression: + left := Eval(node.Left, env) + if isError(left) { + return left + } + + right := Eval(node.Right, env) + if isError(right) { + return right + } + + return evalInfixExpression(node.Operator, left, right) + + case *ast.IfExpression: + return evalIfExpression(node, env) + + case *ast.Identifier: + return evalIdentifier(node, env) + + case *ast.FunctionLiteral: + params := node.Parameters + body := node.Body + return &object.Function{Parameters: params, Env: env, Body: body} + + case *ast.CallExpression: + function := Eval(node.Function, env) + if isError(function) { + return function + } + + args := evalExpressions(node.Arguments, env) + if len(args) == 1 && isError(args[0]) { + return args[0] + } + + return applyFunction(function, args) + } + + return nil +} + +func evalProgram(program *ast.Program, env *object.Environment) object.Object { + var result object.Object + + for _, statement := range program.Statements { + result = Eval(statement, env) + + switch result := result.(type) { + case *object.ReturnValue: + return result.Value + case *object.Error: + return result + } + } + + return result +} + +func evalBlockStatement( + block *ast.BlockStatement, + env *object.Environment, +) object.Object { + var result object.Object + + for _, statement := range block.Statements { + result = Eval(statement, env) + + if result != nil { + rt := result.Type() + if rt == object.RETURN_VALUE_OBJ || rt == object.ERROR_OBJ { + return result + } + } + } + + return result +} + +func nativeBoolToBooleanObject(input bool) *object.Boolean { + if input { + return TRUE + } + return FALSE +} + +func evalPrefixExpression(operator string, right object.Object) object.Object { + switch operator { + case "!": + return evalBangOperatorExpression(right) + case "-": + return evalMinusPrefixOperatorExpression(right) + default: + return newError("unknown operator: %s%s", operator, right.Type()) + } +} + +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) + case operator == "==": + return nativeBoolToBooleanObject(left == right) + case operator == "!=": + return nativeBoolToBooleanObject(left != right) + case left.Type() != right.Type(): + return newError("type mismatch: %s %s %s", + left.Type(), operator, right.Type()) + default: + return newError("unknown operator: %s %s %s", + left.Type(), 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 + } +} + +func evalMinusPrefixOperatorExpression(right object.Object) object.Object { + if right.Type() != object.INTEGER_OBJ { + return newError("unknown operator: -%s", right.Type()) + } + + value := right.(*object.Integer).Value + return &object.Integer{Value: -value} +} + +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} + case "<": + return nativeBoolToBooleanObject(leftVal < rightVal) + case ">": + return nativeBoolToBooleanObject(leftVal > rightVal) + case "==": + return nativeBoolToBooleanObject(leftVal == rightVal) + case "!=": + return nativeBoolToBooleanObject(leftVal != rightVal) + default: + return newError("unknown operator: %s %s %s", + left.Type(), operator, right.Type()) + } +} + +func evalIfExpression( + ie *ast.IfExpression, + env *object.Environment, +) object.Object { + condition := Eval(ie.Condition, env) + if isError(condition) { + return condition + } + + if isTruthy(condition) { + return Eval(ie.Consequence, env) + } else if ie.Alternative != nil { + return Eval(ie.Alternative, env) + } else { + return NULL + } +} + +func evalIdentifier( + node *ast.Identifier, + env *object.Environment, +) object.Object { + val, ok := env.Get(node.Value) + if !ok { + return newError("identifier not found: " + node.Value) + } + + return val +} + +func isTruthy(obj object.Object) bool { + switch obj { + case NULL: + return false + case TRUE: + return true + case FALSE: + return false + default: + return true + } +} + +func newError(format string, a ...interface{}) *object.Error { + return &object.Error{Message: fmt.Sprintf(format, a...)} +} + +func isError(obj object.Object) bool { + if obj != nil { + return obj.Type() == object.ERROR_OBJ + } + return false +} + +func evalExpressions( + exps []ast.Expression, + env *object.Environment, +) []object.Object { + var result []object.Object + + for _, e := range exps { + evaluated := Eval(e, env) + if isError(evaluated) { + return []object.Object{evaluated} + } + result = append(result, evaluated) + } + + return result +} + +func applyFunction(fn object.Object, args []object.Object) object.Object { + function, ok := fn.(*object.Function) + if !ok { + return newError("not a function: %s", fn.Type()) + } + + extendedEnv := extendFunctionEnv(function, args) + evaluated := Eval(function.Body, extendedEnv) + return unwrapReturnValue(evaluated) +} + +func extendFunctionEnv( + fn *object.Function, + args []object.Object, +) *object.Environment { + env := object.NewEnclosedEnvironment(fn.Env) + + for paramIdx, param := range fn.Parameters { + env.Set(param.Value, args[paramIdx]) + } + + return env +} + +func unwrapReturnValue(obj object.Object) object.Object { + if returnValue, ok := obj.(*object.ReturnValue); ok { + return returnValue.Value + } + + return obj +} diff --git a/evaluator/evaluator_test.go b/evaluator/evaluator_test.go new file mode 100644 index 0000000..e8c77fa --- /dev/null +++ b/evaluator/evaluator_test.go @@ -0,0 +1,351 @@ +package evaluator + +import ( + "monkey/lexer" + "monkey/object" + "monkey/parser" + "testing" +) + +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}, + } + + for _, tt := range tests { + evaluated := testEval(tt.input) + testIntegerObject(t, evaluated, tt.expected) + } +} + +func TestEvalBooleanExpression(t *testing.T) { + tests := []struct { + input string + expected bool + }{ + {"true", true}, + {"false", false}, + {"1 < 2", true}, + {"1 > 2", false}, + {"1 < 1", false}, + {"1 > 1", false}, + {"1 == 1", true}, + {"1 != 1", false}, + {"1 == 2", false}, + {"1 != 2", true}, + {"true == true", true}, + {"false == false", true}, + {"true == false", false}, + {"true != false", true}, + {"false != true", true}, + {"(1 < 2) == true", true}, + {"(1 < 2) == false", false}, + {"(1 > 2) == true", false}, + {"(1 > 2) == false", true}, + } + + for _, tt := range tests { + evaluated := testEval(tt.input) + testBooleanObject(t, evaluated, tt.expected) + } +} + +func TestBangOperator(t *testing.T) { + tests := []struct { + input string + expected bool + }{ + {"!true", false}, + {"!false", true}, + {"!5", false}, + {"!!true", true}, + {"!!false", false}, + {"!!5", true}, + } + + for _, tt := range tests { + evaluated := testEval(tt.input) + testBooleanObject(t, evaluated, tt.expected) + } +} + +func TestIfElseExpressions(t *testing.T) { + tests := []struct { + input string + expected interface{} + }{ + {"if (true) { 10 }", 10}, + {"if (false) { 10 }", nil}, + {"if (1) { 10 }", 10}, + {"if (1 < 2) { 10 }", 10}, + {"if (1 > 2) { 10 }", nil}, + {"if (1 > 2) { 10 } else { 20 }", 20}, + {"if (1 < 2) { 10 } else { 20 }", 10}, + } + + for _, tt := range tests { + evaluated := testEval(tt.input) + integer, ok := tt.expected.(int) + if ok { + testIntegerObject(t, evaluated, int64(integer)) + } else { + testNullObject(t, evaluated) + } + } +} + +func TestReturnStatements(t *testing.T) { + tests := []struct { + input string + expected int64 + }{ + {"return 10;", 10}, + {"return 10; 9;", 10}, + {"return 2 * 5; 9;", 10}, + {"9; return 2 * 5; 9;", 10}, + {"if (10 > 1) { return 10; }", 10}, + { + ` +if (10 > 1) { + if (10 > 1) { + return 10; + } + + return 1; +} +`, + 10, + }, + { + ` +let f = fn(x) { + return x; + x + 10; +}; +f(10);`, + 10, + }, + { + ` +let f = fn(x) { + let result = x + 10; + return result; + return 10; +}; +f(10);`, + 20, + }, + } + + for _, tt := range tests { + evaluated := testEval(tt.input) + testIntegerObject(t, evaluated, tt.expected) + } +} + +func TestErrorHandling(t *testing.T) { + tests := []struct { + input string + expectedMessage string + }{ + { + "5 + true;", + "type mismatch: INTEGER + BOOLEAN", + }, + { + "5 + true; 5;", + "type mismatch: INTEGER + BOOLEAN", + }, + { + "-true", + "unknown operator: -BOOLEAN", + }, + { + "true + false;", + "unknown operator: BOOLEAN + BOOLEAN", + }, + { + "true + false + true + false;", + "unknown operator: BOOLEAN + BOOLEAN", + }, + { + "5; true + false; 5", + "unknown operator: BOOLEAN + BOOLEAN", + }, + { + "if (10 > 1) { true + false; }", + "unknown operator: BOOLEAN + BOOLEAN", + }, + { + ` +if (10 > 1) { + if (10 > 1) { + return true + false; + } + + return 1; +} +`, + "unknown operator: BOOLEAN + BOOLEAN", + }, + { + "foobar", + "identifier not found: foobar", + }, + } + + for _, tt := range tests { + evaluated := testEval(tt.input) + + errObj, ok := evaluated.(*object.Error) + if !ok { + t.Errorf("no error object returned. got=%T(%+v)", + evaluated, evaluated) + continue + } + + if errObj.Message != tt.expectedMessage { + t.Errorf("wrong error message. expected=%q, got=%q", + tt.expectedMessage, errObj.Message) + } + } +} + +func TestLetStatements(t *testing.T) { + tests := []struct { + input string + expected int64 + }{ + {"let a = 5; a;", 5}, + {"let a = 5 * 5; a;", 25}, + {"let a = 5; let b = a; b;", 5}, + {"let a = 5; let b = a; let c = a + b + 5; c;", 15}, + } + + for _, tt := range tests { + testIntegerObject(t, testEval(tt.input), tt.expected) + } +} + +func TestFunctionObject(t *testing.T) { + input := "fn(x) { x + 2; };" + + evaluated := testEval(input) + fn, ok := evaluated.(*object.Function) + if !ok { + t.Fatalf("object is not Function. got=%T (%+v)", evaluated, evaluated) + } + + if len(fn.Parameters) != 1 { + t.Fatalf("function has wrong parameters. Parameters=%+v", + fn.Parameters) + } + + if fn.Parameters[0].String() != "x" { + t.Fatalf("parameter is not 'x'. got=%q", fn.Parameters[0]) + } + + expectedBody := "(x + 2)" + + if fn.Body.String() != expectedBody { + t.Fatalf("body is not %q. got=%q", expectedBody, fn.Body.String()) + } +} + +func TestFunctionApplication(t *testing.T) { + tests := []struct { + input string + expected int64 + }{ + {"let identity = fn(x) { x; }; identity(5);", 5}, + {"let identity = fn(x) { return x; }; identity(5);", 5}, + {"let double = fn(x) { x * 2; }; double(5);", 10}, + {"let add = fn(x, y) { x + y; }; add(5, 5);", 10}, + {"let add = fn(x, y) { x + y; }; add(5 + 5, add(5, 5));", 20}, + {"fn(x) { x; }(5)", 5}, + } + + for _, tt := range tests { + testIntegerObject(t, testEval(tt.input), tt.expected) + } +} + +func TestEnclosingEnvironments(t *testing.T) { + input := ` +let first = 10; +let second = 10; +let third = 10; + +let ourFunction = fn(first) { + let second = 20; + + first + second + third; +}; + +ourFunction(20) + first + second;` + + testIntegerObject(t, testEval(input), 70) +} + +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("object 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 +} + +func testBooleanObject(t *testing.T, obj object.Object, expected bool) bool { + result, ok := obj.(*object.Boolean) + if !ok { + t.Errorf("object is not Boolean. got=%T (%+v)", obj, obj) + return false + } + if result.Value != expected { + t.Errorf("object has wrong value. got=%t, want=%t", + result.Value, expected) + return false + } + return true +} + +func testNullObject(t *testing.T, obj object.Object) bool { + if obj != NULL { + t.Errorf("object is not NULL. got=%T (%+v)", obj, obj) + return false + } + return true +} diff --git a/object/environment.go b/object/environment.go new file mode 100644 index 0000000..6f31070 --- /dev/null +++ b/object/environment.go @@ -0,0 +1,30 @@ +package object + +func NewEnclosedEnvironment(outer *Environment) *Environment { + env := NewEnvironment() + env.outer = outer + return env +} + +func NewEnvironment() *Environment { + s := make(map[string]Object) + return &Environment{store: s, outer: nil} +} + +type Environment struct { + store map[string]Object + outer *Environment +} + +func (e *Environment) Get(name string) (Object, bool) { + obj, ok := e.store[name] + if !ok && e.outer != nil { + obj, ok = e.outer.Get(name) + } + return obj, ok +} + +func (e *Environment) Set(name string, val Object) Object { + e.store[name] = val + return val +} diff --git a/object/object.go b/object/object.go new file mode 100644 index 0000000..cdde084 --- /dev/null +++ b/object/object.go @@ -0,0 +1,85 @@ +package object + +import ( + "bytes" + "fmt" + "monkey/ast" + "strings" +) + +type ObjectType string + +const ( + NULL_OBJ = "NULL" + ERROR_OBJ = "ERROR" + + INTEGER_OBJ = "INTEGER" + BOOLEAN_OBJ = "BOOLEAN" + + RETURN_VALUE_OBJ = "RETURN_VALUE" + + FUNCTION_OBJ = "FUNCTION" +) + +type Object interface { + Type() ObjectType + Inspect() string +} + +type Integer struct { + Value int64 +} + +func (i *Integer) Type() ObjectType { return INTEGER_OBJ } +func (i *Integer) Inspect() string { return fmt.Sprintf("%d", i.Value) } + +type Boolean struct { + Value bool +} + +func (b *Boolean) Type() ObjectType { return BOOLEAN_OBJ } +func (b *Boolean) Inspect() string { return fmt.Sprintf("%t", b.Value) } + +type Null struct{} + +func (n *Null) Type() ObjectType { return NULL_OBJ } +func (n *Null) Inspect() string { return "null" } + +type ReturnValue struct { + Value Object +} + +func (rv *ReturnValue) Type() ObjectType { return RETURN_VALUE_OBJ } +func (rv *ReturnValue) Inspect() string { return rv.Value.Inspect() } + +type Error struct { + Message string +} + +func (e *Error) Type() ObjectType { return ERROR_OBJ } +func (e *Error) Inspect() string { return "ERROR: " + e.Message } + +type Function struct { + Parameters []*ast.Identifier + Body *ast.BlockStatement + Env *Environment +} + +func (f *Function) Type() ObjectType { return FUNCTION_OBJ } +func (f *Function) Inspect() string { + var out bytes.Buffer + + params := []string{} + for _, p := range f.Parameters { + params = append(params, p.String()) + } + + out.WriteString("fn") + out.WriteString("(") + out.WriteString(strings.Join(params, ", ")) + out.WriteString(") {\n") + out.WriteString(f.Body.String()) + out.WriteString("\n}") + + return out.String() +} diff --git a/repl/repl.go b/repl/repl.go index 7fa3e42..7097e68 100644 --- a/repl/repl.go +++ b/repl/repl.go @@ -4,7 +4,9 @@ import ( "bufio" "fmt" "io" + "monkey/evaluator" "monkey/lexer" + "monkey/object" "monkey/parser" ) @@ -12,6 +14,7 @@ const PROMPT = ">> " func Start(in io.Reader, out io.Writer) { scanner := bufio.NewScanner(in) + env := object.NewEnvironment() for { fmt.Printf(PROMPT) @@ -30,8 +33,11 @@ func Start(in io.Reader, out io.Writer) { continue } - io.WriteString(out, program.String()) - io.WriteString(out, "\n") + evaluated := evaluator.Eval(program, env) + if evaluated != nil { + io.WriteString(out, evaluated.Inspect()) + io.WriteString(out, "\n") + } } } -- cgit v1.2.3