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 1: Introduction to Lexer
Chapter 2: Parser Implementation
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;
2. Boolean Operations
let isTrue = true;
let isFalse = !isTrue;
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);
5. Closures
let newAdder = fn(x) {
fn(y) { x + y };
};
let addTwo = newAdder(2);
addTwo(5);
The closure implementation relies on our environment chain:
type Function struct {
Parameters []*ast.Identifier
Body *ast.BlockStatement
Env *Environment
}
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
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 };
};
let multiplyByTwo = multiply(2);
multiplyByTwo(5);
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
type Function struct {
Parameters []*ast.Identifier
Body *ast.BlockStatement
Env *Environment
}
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!
