aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2017-05-20 16:27:42 +0200
committerDimitri Sokolyuk <demon@dim13.org>2017-05-20 16:27:42 +0200
commit69fc902f8f5fd8f36db0991f6ba4faeabb3090fa (patch)
tree36b77847cb8548047f3c8bc7a9d40ae017b86658
parentce78935009d931faf2db7e882929a7a4c95ce3e0 (diff)
03
-rw-r--r--evaluator/evaluator.go325
-rw-r--r--evaluator/evaluator_test.go351
-rw-r--r--object/environment.go30
-rw-r--r--object/object.go85
-rw-r--r--repl/repl.go10
5 files changed, 799 insertions, 2 deletions
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")
+ }
}
}