Introduction
After implementing a lexer to tokenize our code and a parser to create an Abstract Syntax Tree (AST), the next crucial step in building MonkeyLang is adding an evaluator. The evaluator traverses our AST and executes the code, bringing our language to life.
Series Navigation
Building an Interpreter in Go:
Chapter 3: Adding an Evaluator (Current)
Core Concepts
The evaluator's primary responsibility is to:
Walk through the AST
Evaluate expressions and statements
Maintain program state
Handle runtime operations
Sequence Diagram for Evaluator
Implementation Details
Object System
First, we need to define our object system to represent values during evaluation:
type ObjectType string
const (
INTEGER_OBJ = "INTEGER"
BOOLEAN_OBJ = "BOOLEAN"
NULL_OBJ = "NULL"
RETURN_VALUE_OBJ = "RETURN_VALUE"
FUNCTION_OBJ = "FUNCTION"
)
type Object interface {
Type() ObjectType
Inspect() string
}
type Integer struct {
Value int64
}
type Boolean struct {
Value bool
}
type Null struct{}
The Evaluator
Our evaluator's core function processes nodes recursively:
func Eval(node ast.Node, env *Environment) Object {
switch node := node.(type) {
case *ast.Program:
return evalProgram(node, env)
case *ast.ExpressionStatement:
return Eval(node.Expression, env)
case *ast.IntegerLiteral:
return &Integer{Value: node.Value}
case *ast.Boolean:
return nativeBoolToBooleanObject(node.Value)
case *ast.PrefixExpression:
right := Eval(node.Right, env)
return evalPrefixExpression(node.Operator, right)
case *ast.InfixExpression:
left := Eval(node.Left, env)
right := Eval(node.Right, env)
return evalInfixExpression(node.Operator, left, right)
}
return NULL
}
Handling Operations
Prefix Operations
func evalPrefixExpression(operator string, right Object) Object {
switch operator {
case "!":
return evalBangOperatorExpression(right)
case "-":
return evalMinusPrefixOperatorExpression(right)
default:
return newError("unknown operator: %s%s", operator, right.Type())
}
}
Infix Operations
func evalInfixExpression(operator string, left, right Object) Object {
switch {
case left.Type() == INTEGER_OBJ && right.Type() == INTEGER_OBJ:
return evalIntegerInfixExpression(operator, left, right)
case operator == "==":
return nativeBoolToBooleanObject(left == right)
case operator == "!=":
return nativeBoolToBooleanObject(left != right)
default:
return newError("unknown operator: %s %s %s",
left.Type(), operator, right.Type())
}
}
Environment and Scope
To handle variables and functions, we need an environment:
type Environment struct {
store map[string]Object
outer *Environment
}
func NewEnvironment() *Environment {
s := make(map[string]Object)
return &Environment{store: s, outer: nil}
}
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
}
Features Implemented
1. Integer Operations
let x = 5;
let y = 10;
let result = x + y; // Evaluates to 15
2. Boolean Operations
let isTrue = true;
let isFalse = !isTrue; // Evaluates to false
3. Conditionals
if (x > 5) {
return true;
} else {
return false;
}
4. Functions
let add = fn(a, b) {
return a + b;
};
let result = add(5, 10); // Evaluates to 15
5. Closures
let newAdder = fn(x) {
fn(y) { x + y };
};
let addTwo = newAdder(2);
addTwo(5); // Returns 7
The closure implementation relies on our environment chain:
type Function struct {
Parameters []*ast.Identifier
Body *ast.BlockStatement
Env *Environment // Captures the enclosing scope
}
func evalFunctionCall(fn Object, args []Object) Object {
function, ok := fn.(*Function)
if !ok {
return newError("not a function: %s", fn.Type())
}
extendedEnv := extendFunctionEnv(function, args)
evaluated := Eval(function.Body, extendedEnv)
return unwrapReturnValue(evaluated)
}
This enables functions to capture and maintain access to their creation environment, supporting functional programming patterns.
Key Learnings: Environments and Closures
Environment Extension
As displayed in the diagram above, for evaluating function calls we extend the environment to create a new scope:
func extendFunctionEnv(fn *Function, args []Object) *Environment {
env := NewEnvironment()
env.outer = fn.Env // Link to outer scope
// Bind parameters to arguments
for paramIdx, param := range fn.Parameters {
env.Set(param.Value, args[paramIdx])
}
return env
}
This is crucial because:
It creates isolated scopes for each function call
Maintains access to outer scope variables
Prevents name collisions between different function calls
Enables proper variable shadowing
Closure Implementation
The magic of closures happens through environment chains:
let multiply = fn(x) {
fn(y) { x * y }; // x is captured from outer scope
};
let multiplyByTwo = multiply(2);
multiplyByTwo(5); // Returns 10
When multiply(2)
is called:
New environment created with
x = 2
Inner function created, storing reference to this environment
When inner function called later, it still has access to
x
// Each function stores its creation environment
type Function struct {
Parameters []*ast.Identifier
Body *ast.BlockStatement
Env *Environment // Captures scope where function was created
}
This environment chaining enables:
Factory functions
Private state
Partial application
Memoization patterns
Next Steps
Add support for strings and string operations
Implement arrays and array methods
Add built-in functions
Optimize evaluation performance
Conclusion
With the evaluator in place, MonkeyLang can now execute basic programs. The combination of lexer, parser, and evaluator creates a complete interpretation pipeline, turning source code into executed results.
The evaluator's design prioritizes clarity and extensibility, making it easy to add new features and optimizations as the language grows.
Continue Learning
If you're just joining this series, start with:
Stay tuned for the next and final Chapter 4 where we'll explore Strings, Arrays and Hashes next!