Building an Interpreter in Go: Implementing the Evaluator with Closure

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.

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; // 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!

Chapter 3: Adding an Evaluator to MonkeyLang