After successfully building a lexer and parser that convert source code into an abstract syntax tree (AST), the next critical step is to evaluate expressions. This phase brings the AST to life by computing actual values from syntactic structures.

The Role of the Visitor Pattern

To evaluate different node types—such as binary operations, literals, groupings, and unary expressions—we adopt the Visitor pattern. This design cleanly separates the data structure (the AST nodes) from the operations performed on them (like evaluation).

public abstract class Expr
{
    public abstract T Accept<T>(IVisitor<T> visitor);
}

public interface IVisitor<T>
{
    T VisitBinary(Binary expr);
    T VisitGrouping(Grouping expr);
    T VisitLiteral(Literal expr);
    T VisitUnary(Unary expr);
}

public class Binary : Expr
{
    public Expr Left { get; }
    public Token Operator { get; }
    public Expr Right { get; }

    public override T Accept<T>(IVisitor<T> visitor) =>
        visitor.VisitBinary(this);
}

The interpreter implements this visitor interface to define how each expression type should be evaluated.

Runtime Error Handling

Unlike parse errors, runtime errors occur during evaluation—for example, applying arithmetic to non-numeric values. We define a dedicated exception:

public class RuntimeError : Exception
{
    public Token Token { get; }

    public RuntimeError(Token token, string message) : base(message)
    {
        Token = token;
    }
}

Error reporting includes line numbers for better diagnostics:

public static void ReportRuntimeError(RuntimeError error)
{
    Console.Error.WriteLine($"{error.Message} [line {error.Token.Line}]");
    HadRuntimeError = true;
}

Interpreter Implementation

The interpreter traverses the AST recursively using the visitor pattern.

Literal Values

public object VisitLiteral(Literal expr) => expr.Value;

Grouping Expressions

public object VisitGrouping(Grouping expr) => Evaluate(expr.Inner);

private object Evaluate(Expr expr) => expr.Accept(this);

Unary Operations

public object VisitUnary(Unary expr)
{
    var operand = Evaluate(expr.Operand);
    switch (expr.Operator.Type)
    {
        case TokenType.BANG:
            return !IsTruthy(operand);
        case TokenType.MINUS:
            EnsureNumber(expr.Operator, operand);
            return -(double)operand;
        default:
            throw new UnreachableException();
    }
}

Binary Operations

Binary expressions handle multiple operators with type-aware logic:

public object VisitBinary(Binary expr)
{
    var left = Evaluate(expr.Left);
    var right = Evaluate(expr.Right);

    return expr.Operator.Type switch
    {
        TokenType.PLUS => Add(left, right),
        TokenType.MINUS => Subtract(expr.Operator, left, right),
        TokenType.STAR => Multiply(expr.Operator, left, right),
        TokenType.SLASH => Divide(expr.Operator, left, right),
        TokenType.GREATER => CompareNumbers(expr.Operator, left, right, (a, b) => a > b),
        TokenType.GREATER_EQUAL => CompareNumbers(expr.Operator, left, right, (a, b) => a >= b),
        TokenType.LESS => CompareNumbers(expr.Operator, left, right, (a, b) => a < b),
        TokenType.LESS_EQUAL => CompareNumbers(expr.Operator, left, right, (a, b) => a <= b),
        TokenType.BANG_EQUAL => !AreEqual(left, right),
        TokenType.EQUAL_EQUAL => AreEqual(left, right),
        _ => throw new UnreachableException()
    };
}

String concatenation and numeric addition are both supported for +:

private object Add(object left, object right)
{
    if (left is double l && right is double r) return l + r;
    if (left is string || right is string)
        return ToLoxString(left) + ToLoxString(right);
    throw new RuntimeError(expr.Operator, "Operands must be numbers or strings.");
}

Type Utilities

Key helper methods manage dynamic typing in a statically typed language:

private void EnsureNumber(Token op, object value)
{
    if (value is not double)
        throw new RuntimeError(op, "Operand must be a number.");
}

private void EnsureNumbers(Token op, object left, object right)
{
    if (left is not double || right is not double)
        throw new RuntimeError(op, "Operands must be numbers.");
}

private bool IsTruthy(object value) =>
    value != null && (value is not bool b || b);

private bool AreEqual(object a, object b) =>
    a == null ? b == null : a.Equals(b);

private string ToLoxString(object value)
{
    if (value == null) return "nil";
    if (value is double d)
        return d % 1 == 0 ? ((int)d).ToString() : d.ToString();
    return value.ToString();
}

Putting It All Together

A test harness validates correctness across various expressions:

var cases = new[]
{
    "1 + 2 * 3",          // → 7
    "(1 + 2) * 3",        // → 9
    "-42",                // → -42
    "!false",             // → true
    "\"hi\" + \" there\"",// → hi there
    "nil == nil"          // → true
};

foreach (var src in cases)
{
    var tokens = new Scanner(src).ScanTokens();
    var ast = new Parser(tokens).Parse();
    var result = new Evaluator().Evaluate(ast);
    Console.WriteLine($"{src} → {ToLoxString(result)}");
}

This completes the expression evaluation pipeline. The interpreter now correctly handles arithmetic, comparisons, logical operations, and type coercion according to Lox semantics.