From e5ed6e13a4adbbe61317194af36c33c82b33c90f Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sun, 25 Mar 2018 01:50:10 +0100 Subject: lost chapter --- evaluator/evaluator.go | 3 + evaluator/macro_expansion.go | 123 ++++++++++++++++++++++++++++++++++++++ evaluator/macro_expansion_test.go | 123 ++++++++++++++++++++++++++++++++++++++ evaluator/quote_unquote.go | 68 +++++++++++++++++++++ evaluator/quote_unquote_test.go | 117 ++++++++++++++++++++++++++++++++++++ 5 files changed, 434 insertions(+) create mode 100644 evaluator/macro_expansion.go create mode 100644 evaluator/macro_expansion_test.go create mode 100644 evaluator/quote_unquote.go create mode 100644 evaluator/quote_unquote_test.go (limited to 'evaluator') diff --git a/evaluator/evaluator.go b/evaluator/evaluator.go index a6b21cc..6ea4b01 100644 --- a/evaluator/evaluator.go +++ b/evaluator/evaluator.go @@ -82,6 +82,9 @@ func Eval(node ast.Node, env *object.Environment) object.Object { return &object.Function{Parameters: params, Env: env, Body: body} case *ast.CallExpression: + if node.Function.TokenLiteral() == "quote" { + return quote(node.Arguments[0], env) + } function := Eval(node.Function, env) if isError(function) { return function diff --git a/evaluator/macro_expansion.go b/evaluator/macro_expansion.go new file mode 100644 index 0000000..1fdac0a --- /dev/null +++ b/evaluator/macro_expansion.go @@ -0,0 +1,123 @@ +package evaluator + +import ( + "monkey/ast" + "monkey/object" +) + +func DefineMacros(program *ast.Program, env *object.Environment) { + definitions := []int{} + + for i, statement := range program.Statements { + if isMacroDefinition(statement) { + addMacro(statement, env) + definitions = append(definitions, i) + } + } + + for i := len(definitions) - 1; i >= 0; i = i - 1 { + definitionIndex := definitions[i] + program.Statements = append( + program.Statements[:definitionIndex], + program.Statements[definitionIndex+1:]..., + ) + } +} + +func isMacroDefinition(node ast.Statement) bool { + letStatement, ok := node.(*ast.LetStatement) + if !ok { + return false + } + + _, ok = letStatement.Value.(*ast.MacroLiteral) + if !ok { + return false + } + + return true +} + +func addMacro(stmt ast.Statement, env *object.Environment) { + letStatement, _ := stmt.(*ast.LetStatement) + macroLiteral, _ := letStatement.Value.(*ast.MacroLiteral) + + macro := &object.Macro{ + Parameters: macroLiteral.Parameters, + Env: env, + Body: macroLiteral.Body, + } + + env.Set(letStatement.Name.Value, macro) +} + +func ExpandMacros(program ast.Node, env *object.Environment) ast.Node { + return ast.Modify(program, func(node ast.Node) ast.Node { + callExpression, ok := node.(*ast.CallExpression) + if !ok { + return node + } + + macro, ok := isMacroCall(callExpression, env) + if !ok { + return node + } + + args := quoteArgs(callExpression) + evalEnv := extendMacroEnv(macro, args) + + evaluated := Eval(macro.Body, evalEnv) + + quote, ok := evaluated.(*object.Quote) + if !ok { + panic("we only support returning AST-nodes from macros") + } + + return quote.Node + }) +} + +func isMacroCall( + exp *ast.CallExpression, + env *object.Environment, +) (*object.Macro, bool) { + identifier, ok := exp.Function.(*ast.Identifier) + if !ok { + return nil, false + } + + obj, ok := env.Get(identifier.Value) + if !ok { + return nil, false + } + + macro, ok := obj.(*object.Macro) + if !ok { + return nil, false + } + + return macro, true +} + +func quoteArgs(exp *ast.CallExpression) []*object.Quote { + args := []*object.Quote{} + + for _, a := range exp.Arguments { + args = append(args, &object.Quote{Node: a}) + } + + return args +} + +func extendMacroEnv( + macro *object.Macro, + args []*object.Quote, +) *object.Environment { + extended := object.NewEnclosedEnvironment(macro.Env) + + for paramIdx, param := range macro.Parameters { + extended.Set(param.Value, args[paramIdx]) + } + + return extended +} diff --git a/evaluator/macro_expansion_test.go b/evaluator/macro_expansion_test.go new file mode 100644 index 0000000..4a67f35 --- /dev/null +++ b/evaluator/macro_expansion_test.go @@ -0,0 +1,123 @@ +package evaluator + +import ( + "monkey/ast" + "monkey/lexer" + "monkey/object" + "monkey/parser" + "testing" +) + +func TestDefineMacros(t *testing.T) { + input := ` +let number = 1; +let function = fn(x, y) { x + y }; +let mymacro = macro(x, y) { x + y; }; +` + + env := object.NewEnvironment() + program := testParseProgram(input) + + DefineMacros(program, env) + + if len(program.Statements) != 2 { + t.Fatalf("Wrong number of statements. got=%d", + len(program.Statements)) + } + + _, ok := env.Get("number") + if ok { + t.Fatalf("number should not be defined") + } + _, ok = env.Get("function") + if ok { + t.Fatalf("function should not be defined") + } + + obj, ok := env.Get("mymacro") + if !ok { + t.Fatalf("macro not in environment.") + } + + macro, ok := obj.(*object.Macro) + if !ok { + t.Fatalf("object is not Macro. got=%T (%+v)", obj, obj) + } + + if len(macro.Parameters) != 2 { + t.Fatalf("Wrong number of macro parameters. got=%d", + len(macro.Parameters)) + } + + if macro.Parameters[0].String() != "x" { + t.Fatalf("parameter is not 'x'. got=%q", macro.Parameters[0]) + } + if macro.Parameters[1].String() != "y" { + t.Fatalf("parameter is not 'y'. got=%q", macro.Parameters[1]) + } + + expectedBody := "(x + y)" + + if macro.Body.String() != expectedBody { + t.Fatalf("body is not %q. got=%q", expectedBody, macro.Body.String()) + } +} + +func testParseProgram(input string) *ast.Program { + l := lexer.New(input) + p := parser.New(l) + return p.ParseProgram() +} + +func TestExpandMacros(t *testing.T) { + tests := []struct { + input string + expected string + }{ + { + ` + let infixExpression = macro() { quote(1 + 2); }; + + infixExpression(); + `, + `(1 + 2)`, + }, + { + ` + let reverse = macro(a, b) { quote(unquote(b) - unquote(a)); }; + + reverse(2 + 2, 10 - 5); + `, + `(10 - 5) - (2 + 2)`, + }, + { + ` + let unless = macro(condition, consequence, alternative) { + quote(if (!(unquote(condition))) { + unquote(consequence); + } else { + unquote(alternative); + }); + }; + + unless(10 > 5, puts("not greater"), puts("greater")); + `, + + `if (!(10 > 5)) { puts("not greater") } else { puts("greater") }`, + }, + } + + for _, tt := range tests { + expected := testParseProgram(tt.expected) + program := testParseProgram(tt.input) + + env := object.NewEnvironment() + DefineMacros(program, env) + expanded := ExpandMacros(program, env) + + if expanded.String() != expected.String() { + t.Errorf("not equal. want=%q, got=%q", + expected.String(), expanded.String()) + } + } +} diff --git a/evaluator/quote_unquote.go b/evaluator/quote_unquote.go new file mode 100644 index 0000000..d3521f9 --- /dev/null +++ b/evaluator/quote_unquote.go @@ -0,0 +1,68 @@ +package evaluator + +import ( + "fmt" + "monkey/ast" + "monkey/object" + "monkey/token" +) + +func quote(node ast.Node, env *object.Environment) object.Object { + node = evalUnquoteCalls(node, env) + return &object.Quote{Node: node} +} + +func evalUnquoteCalls(quoted ast.Node, env *object.Environment) ast.Node { + return ast.Modify(quoted, func(node ast.Node) ast.Node { + if !isUnquoteCall(node) { + return node + } + + call, ok := node.(*ast.CallExpression) + if !ok { + return node + } + + if len(call.Arguments) != 1 { + return node + } + + unquoted := Eval(call.Arguments[0], env) + return convertObjectToASTNode(unquoted) + }) +} + +func isUnquoteCall(node ast.Node) bool { + callExpression, ok := node.(*ast.CallExpression) + if !ok { + return false + } + + return callExpression.Function.TokenLiteral() == "unquote" +} + +func convertObjectToASTNode(obj object.Object) ast.Node { + switch obj := obj.(type) { + case *object.Integer: + t := token.Token{ + Type: token.INT, + Literal: fmt.Sprintf("%d", obj.Value), + } + return &ast.IntegerLiteral{Token: t, Value: obj.Value} + + case *object.Boolean: + var t token.Token + if obj.Value { + t = token.Token{Type: token.TRUE, Literal: "true"} + } else { + t = token.Token{Type: token.FALSE, Literal: "false"} + } + return &ast.Boolean{Token: t, Value: obj.Value} + + case *object.Quote: + return obj.Node + + default: + return nil + } +} diff --git a/evaluator/quote_unquote_test.go b/evaluator/quote_unquote_test.go new file mode 100644 index 0000000..2859540 --- /dev/null +++ b/evaluator/quote_unquote_test.go @@ -0,0 +1,117 @@ +package evaluator + +import ( + "monkey/object" + "testing" +) + +func TestQuote(t *testing.T) { + tests := []struct { + input string + expected string + }{ + { + `quote(5)`, + `5`, + }, + { + `quote(5 + 8)`, + `(5 + 8)`, + }, + { + `quote(foobar)`, + `foobar`, + }, + { + `quote(foobar + barfoo)`, + `(foobar + barfoo)`, + }, + } + + for _, tt := range tests { + evaluated := testEval(tt.input) + quote, ok := evaluated.(*object.Quote) + if !ok { + t.Fatalf("expected *object.Quote. got=%T (%+v)", + evaluated, evaluated) + } + + if quote.Node == nil { + t.Fatalf("quote.Node is nil") + } + + if quote.Node.String() != tt.expected { + t.Errorf("not equal. got=%q, want=%q", + quote.Node.String(), tt.expected) + } + } +} + +func TestQuoteUnquote(t *testing.T) { + tests := []struct { + input string + expected string + }{ + { + `quote(unquote(4))`, + `4`, + }, + { + `quote(unquote(4 + 4))`, + `8`, + }, + { + `quote(8 + unquote(4 + 4))`, + `(8 + 8)`, + }, + { + `quote(unquote(4 + 4) + 8)`, + `(8 + 8)`, + }, + { + `let foobar = 8; + quote(foobar)`, + `foobar`, + }, + { + `let foobar = 8; + quote(unquote(foobar))`, + `8`, + }, + { + `quote(unquote(true))`, + `true`, + }, + { + `quote(unquote(true == false))`, + `false`, + }, + { + `quote(unquote(quote(4 + 4)))`, + `(4 + 4)`, + }, + { + `let quotedInfixExpression = quote(4 + 4); + quote(unquote(4 + 4) + unquote(quotedInfixExpression))`, + `(8 + (4 + 4))`, + }, + } + + for _, tt := range tests { + evaluated := testEval(tt.input) + quote, ok := evaluated.(*object.Quote) + if !ok { + t.Fatalf("expected *object.Quote. got=%T (%+v)", + evaluated, evaluated) + } + + if quote.Node == nil { + t.Fatalf("quote.Node is nil") + } + + if quote.Node.String() != tt.expected { + t.Errorf("not equal. got=%q, want=%q", + quote.Node.String(), tt.expected) + } + } +} -- cgit v1.2.3