System Design (LLD)Interpreter Pattern

Interpreter Pattern (Overview)

LevelAdvanced

Duration90 mins

TopicInterpreter Pattern

2 / 4

Solution: Grammar Representation as Classes

From Grammar to Object Hierarchy

The Interpreter Pattern's genius lies in a simple observation: if grammar rules are recursive and hierarchical, then the code that represents them should be recursive and hierarchical too. By modeling each grammar rule as a class in an object-oriented hierarchy, we create a structure where expressions can be composed, extended, and evaluated through polymorphism.

This approach transforms the interpretation problem from procedural string manipulation into an elegant class design exercise. Each expression type knows how to interpret itself, and complex expressions are built by composing simpler ones—exactly mirroring how grammars define complex expressions through composition of simpler rules.

What You Will Learn

By the end of this page, you will understand the complete structure of the Interpreter Pattern: the abstract Expression interface, concrete Terminal and Non-terminal expression classes, and the Context object that provides runtime data. You'll see how this design enables polymorphic evaluation and maintains a clear grammar-to-code mapping. We'll implement a full working example that brings these concepts to life.

The Interpreter Pattern Structure

The Interpreter Pattern consists of four key participants that work together to define and evaluate a language. Understanding each participant's role is essential to implementing the pattern correctly.

The four participants:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
┌─────────────────────────────────────────────────────────────────────────────┐
│                        INTERPRETER PATTERN STRUCTURE                         │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  ┌─────────────────────┐           ┌──────────────────────────────────────┐ │
│  │       Client        │           │            Context                   │ │
│  ├─────────────────────┤           ├──────────────────────────────────────┤ │
│  │ Builds or receives  │           │ • Contains global information         │ │
│  │ the AST, invokes    │◀─────────▶│ • Variable bindings                   │ │
│  │ interpret() on root │           │ • External data for interpretation    │ │
│  └─────────────────────┘           └──────────────────────────────────────┘ │
│              │                                                              │
│              ▼                                                              │
│  ┌─────────────────────────────────────────────────────────────────────┐   │
│  │                    AbstractExpression                                │   │
│  │                         <<interface>>                                │   │
│  ├─────────────────────────────────────────────────────────────────────┤   │
│  │ + interpret(context: Context): any                                   │   │
│  └─────────────────────────────────────────────────────────────────────┘   │
│                            ▲                                               │
│              ┌─────────────┼─────────────┐                                 │
│              │                           │                                 │
│  ┌───────────────────────┐    ┌───────────────────────────────────────┐   │
│  │  TerminalExpression   │    │     NonTerminalExpression              │   │
│  ├───────────────────────┤    ├───────────────────────────────────────┤   │
│  │ Represents atoms      │    │ Represents composite expressions       │   │
│  │ (literals, variables) │    │ (operations combining sub-expressions) │   │
│  │                       │    │                                        │   │
│  │ Examples:             │    │ Examples:                              │   │
│  │ • NumberLiteral       │    │ • AddExpression(left, right)           │   │
│  │ • BooleanLiteral      │    │ • AndExpression(left, right)           │   │
│  │ • VariableReference   │    │ • NotExpression(operand)               │   │
│  │ • StringLiteral       │    │ • IfExpression(cond, then, else)       │   │
│  └───────────────────────┘    └───────────────────────────────────────┘   │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

Interpreter Pattern Participants

•AbstractExpression — The interface or abstract class that declares the interpret(context) method. All concrete expression classes implement this interface, enabling polymorphic interpretation. This corresponds to the abstract syntax of the grammar.
•TerminalExpression — Implements interpretation for terminal symbols (leaf nodes in the grammar). Terminal expressions don't reference other expressions; they represent atomic values like numbers, strings, booleans, or variable references. In grammar terms, these are the symbols that don't appear on the left side of any production.
•NonTerminalExpression — Implements interpretation for non-terminal symbols (composite nodes). These expressions contain references to other expressions, enabling the recursive composition that mirrors the grammar's recursive rules. Binary operators, unary operators, and control structures are typically non-terminal expressions.
•Context — Contains the global information needed during interpretation. This typically includes variable bindings (mapping variable names to values), function definitions, and any external data required for evaluation. The context is passed through the interpretation tree.

Mapping Grammar Rules to Classes

The most powerful aspect of the Interpreter Pattern is the direct correspondence between grammar rules and class definitions. This mapping is systematic and predictable—once you understand it, you can translate any grammar into a class hierarchy.

The mapping rules:

Grammar to Class Transformation Rules
Grammar Element	Class Representation	Example
Terminal symbol (literal)	Terminal Expression class with value	`42` → `NumberLiteral(42)`
Terminal symbol (variable)	Terminal Expression with name lookup	`age` → `VariableRef('age')`
Binary operator rule	NonTerminal with left & right expressions	`A + B` → `AddExpr(A, B)`
Unary operator rule	NonTerminal with single expression	`NOT A` → `NotExpr(A)`
Alternative (A \| B)	Multiple concrete classes for same interface	`expr: add \| sub` → `AddExpr`, `SubExpr`
Sequence (A B C)	Class with ordered references	`if cond then expr` → `IfExpr(cond, expr)`
Repetition (A*)	Class with list of expressions	`block: stmt*` → `Block(stmts[])`

Let's see this mapping in action:

Starting from our validation rule grammar from the previous page, here's how each production maps to a class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
GRAMMAR                                    CLASS HIERARCHY
═══════════════════════════════════════════════════════════════════════════
 
expression ::= orExpression           →   Expression (interface)
                                          ├── OrExpression
                                          ├── AndExpression  
                                          ├── NotExpression
                                          ├── ComparisonExpression
                                          ├── LiteralExpression
                                          └── VariableExpression
 
orExpression ::=                      →   class OrExpression implements Expression {
    andExpression ("OR" andExpression)*       left: Expression;
                                              right: Expression;
                                          }
 
andExpression ::=                     →   class AndExpression implements Expression {
    primary ("AND" primary)*                  left: Expression;
                                              right: Expression;
                                          }
 
primary ::=                           →   (Handled by multiple classes)
    comparison                            • ComparisonExpression
  | "(" expression ")"                    • (just wraps inner expression)
  | "NOT" primary                         • NotExpression
 
comparison ::=                        →   class ComparisonExpression implements Expression {
    identifier operator value                 field: string;
                                              operator: ComparisonOp;
                                              value: Expression;
                                          }
 
value ::=                             →   Terminal expression classes:
    number                                • NumberLiteral
  | string                                • StringLiteral  
  | "true" | "false"                      • BooleanLiteral
  | identifier                            • VariableExpression

The One-to-One Principle

Each distinct construct in your grammar should have exactly one class to represent it. This one-to-one mapping is what makes the Interpreter Pattern maintainable—when you need to add or modify grammar rules, you know exactly where to look and what to change. The grammar serves as a blueprint for your class hierarchy.

Complete Implementation: Boolean Expression Language

Let's build a complete, working Interpreter Pattern implementation for a boolean expression language. This example is substantial enough to demonstrate all the pattern's features while remaining comprehensible.

The language grammar:

expression  ::= orExpr
orExpr      ::= andExpr ('OR' andExpr)*
andExpr     ::= primary ('AND' primary)*
primary     ::= 'NOT' primary | comparison | '(' expression ')' | literal
comparison  ::= identifier ('<'|'>'|'<='|'>='|'=='|'!=') value
literal     ::= 'true' | 'false'
value       ::= number | string | identifier

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Context holds the variable bindings for expression evaluation.
 * During interpretation, variable names are looked up in this context.
 */
interface EvaluationContext {
    /**
     * Look up a variable's value by name.
     * Throws if the variable is not defined.
     */
    get(variableName: string): any;
    
    /**
     * Check if a variable is defined in the context.
     */
    has(variableName: string): boolean;
}
 
/**
 * Simple implementation of EvaluationContext using a record.
 */
class SimpleContext implements EvaluationContext {
    constructor(private variables: Record<string, any>) {}
    
    get(variableName: string): any {
        if (!this.has(variableName)) {
            throw new Error(`Undefined variable: ${variableName}`);
        }
        return this.variables[variableName];
    }
    
    has(variableName: string): boolean {
        return variableName in this.variables;
    }
}
 
/**
 * The abstract Expression interface - all expression types implement this.
 * This is the key interface of the Interpreter Pattern.
 */
interface Expression {
    /**
     * Interpret this expression in the given context.
     * Returns the result of evaluation.
     */
    interpret(context: EvaluationContext): any;
    
    /**
     * Return a string representation for debugging.
     */
    toString(): string;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// ═══════════════════════════════════════════════════════════════════════
// TERMINAL EXPRESSIONS: Expressions that don't contain sub-expressions
// ═══════════════════════════════════════════════════════════════════════
 
/**
 * Represents a numeric literal like 42 or 3.14
 */
class NumberLiteral implements Expression {
    constructor(private value: number) {}
    
    interpret(context: EvaluationContext): number {
        // Literals evaluate to themselves - no context needed
        return this.value;
    }
    
    toString(): string {
        return String(this.value);
    }
}
 
/**
 * Represents a string literal like "hello" or "premium"
 */
class StringLiteral implements Expression {
    constructor(private value: string) {}
    
    interpret(context: EvaluationContext): string {
        return this.value;
    }
    
    toString(): string {
        return `"${this.value}"`;
    }
}
 
/**
 * Represents boolean literals: true or false
 */
class BooleanLiteral implements Expression {
    constructor(private value: boolean) {}
    
    interpret(context: EvaluationContext): boolean {
        return this.value;
    }
    
    toString(): string {
        return String(this.value);
    }
}
 
/**
 * Represents a variable reference like "age" or "user.name".
 * The actual value is looked up in the context during interpretation.
 */
class VariableExpression implements Expression {
    constructor(private variableName: string) {}
    
    interpret(context: EvaluationContext): any {
        // This is where the Context participant becomes essential
        return context.get(this.variableName);
    }
    
    toString(): string {
        return this.variableName;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// ═══════════════════════════════════════════════════════════════════════
// NON-TERMINAL EXPRESSIONS: Expressions composed of sub-expressions
// ═══════════════════════════════════════════════════════════════════════
 
/**
 * Represents a logical AND: (left AND right)
 * 
 * This is a binary non-terminal expression - it contains two sub-expressions.
 * The recursive nature of interpretation happens here: we interpret the
 * children before computing our result.
 */
class AndExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): boolean {
        // Short-circuit evaluation: if left is false, don't evaluate right
        const leftResult = this.left.interpret(context);
        if (!leftResult) {
            return false;
        }
        return Boolean(this.right.interpret(context));
    }
    
    toString(): string {
        return `(${this.left.toString()} AND ${this.right.toString()})`;
    }
}
 
/**
 * Represents a logical OR: (left OR right)
 */
class OrExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): boolean {
        // Short-circuit evaluation: if left is true, don't evaluate right
        const leftResult = this.left.interpret(context);
        if (leftResult) {
            return true;
        }
        return Boolean(this.right.interpret(context));
    }
    
    toString(): string {
        return `(${this.left.toString()} OR ${this.right.toString()})`;
    }
}
 
/**
 * Represents a logical NOT: NOT(operand)
 * 
 * This is a unary non-terminal expression - it contains one sub-expression.
 */
class NotExpression implements Expression {
    constructor(private operand: Expression) {}
    
    interpret(context: EvaluationContext): boolean {
        return !this.operand.interpret(context);
    }
    
    toString(): string {
        return `NOT(${this.operand.toString()})`;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * Supported comparison operators
 */
type ComparisonOperator = '==' | '!=' | '<' | '>' | '<=' | '>=';
 
/**
 * Represents a comparison: left op right
 * 
 * Examples:
 *   age >= 18
 *   country == "US"
 *   score < threshold
 */
class ComparisonExpression implements Expression {
    constructor(
        private left: Expression,
        private operator: ComparisonOperator,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): boolean {
        const leftValue = this.left.interpret(context);
        const rightValue = this.right.interpret(context);
        
        switch (this.operator) {
            case '==':
                return leftValue === rightValue;
            case '!=':
                return leftValue !== rightValue;
            case '<':
                return leftValue < rightValue;
            case '>':
                return leftValue > rightValue;
            case '<=':
                return leftValue <= rightValue;
            case '>=':
                return leftValue >= rightValue;
            default:
                // TypeScript exhaustiveness check
                const _exhaustive: never = this.operator;
                throw new Error(`Unknown operator: ${this.operator}`);
        }
    }
    
    toString(): string {
        return `(${this.left.toString()} ${this.operator} ${this.right.toString()})`;
    }
}
 
// ═══════════════════════════════════════════════════════════════════════
// ADDITIONAL OPERATORS: Extending the language is straightforward
// ═══════════════════════════════════════════════════════════════════════
 
/**
 * Represents an IMPLIES operator: (condition IMPLIES consequence)
 * 
 * This is logically equivalent to: NOT(condition) OR consequence
 * "If condition is true, then consequence must be true"
 */
class ImpliesExpression implements Expression {
    constructor(
        private condition: Expression,
        private consequence: Expression
    ) {}
    
    interpret(context: EvaluationContext): boolean {
        const conditionResult = this.condition.interpret(context);
        if (!conditionResult) {
            // If condition is false, implication is true (vacuously)
            return true;
        }
        // If condition is true, consequence must be true
        return Boolean(this.consequence.interpret(context));
    }
    
    toString(): string {
        return `(${this.condition.toString()} IMPLIES ${this.consequence.toString()})`;
    }
}

Using the Interpreter: AST Construction and Evaluation

With our expression classes defined, we can now construct and evaluate expression trees. In practice, these trees would be built by a parser; here we'll construct them manually to focus on the interpretation aspect.

Example: Building and evaluating expressions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// ═══════════════════════════════════════════════════════════════════════
// EXAMPLE: Form Validation Rule Evaluation
// ═══════════════════════════════════════════════════════════════════════
 
// Rule: (age >= 18) AND ((country == "US") OR (verified == true))
// 
// This rule requires:
// - User must be at least 18 years old, AND
// - Either be from the US, OR be verified
 
// Step 1: Build the expression tree (normally done by a parser)
const validationRule: Expression = new AndExpression(
    // Left side: age >= 18
    new ComparisonExpression(
        new VariableExpression('age'),
        '>=',
        new NumberLiteral(18)
    ),
    // Right side: (country == "US") OR (verified == true)
    new OrExpression(
        new ComparisonExpression(
            new VariableExpression('country'),
            '==',
            new StringLiteral('US')
        ),
        new ComparisonExpression(
            new VariableExpression('verified'),
            '==',
            new BooleanLiteral(true)
        )
    )
);
 
// Step 2: Create context with form data
const formData = new SimpleContext({
    age: 25,
    country: 'UK',
    verified: true
});
 
// Step 3: Evaluate the rule
const isValid = validationRule.interpret(formData);
console.log(`Validation result: ${isValid}`);  // true (age >= 18 AND verified)
console.log(`Rule: ${validationRule.toString()}`);
// Output: ((age >= 18) AND ((country == "US") OR (verified == true)))
 
// ═══════════════════════════════════════════════════════════════════════
// EXAMPLE: Different contexts, same expression
// ═══════════════════════════════════════════════════════════════════════
 
// The same expression can be evaluated with different contexts
const testCases = [
    { age: 25, country: 'US', verified: false },  // true: age OK, country is US
    { age: 25, country: 'UK', verified: true },   // true: age OK, verified
    { age: 16, country: 'US', verified: true },   // false: age too low
    { age: 30, country: 'UK', verified: false },  // false: not US, not verified
];
 
testCases.forEach((data, index) => {
    const context = new SimpleContext(data);
    const result = validationRule.interpret(context);
    console.log(`Test ${index + 1}: ${JSON.stringify(data)} => ${result}`);
});
 
// Output:
// Test 1: {"age":25,"country":"US","verified":false} => true
// Test 2: {"age":25,"country":"UK","verified":true} => true
// Test 3: {"age":16,"country":"US","verified":true} => false
// Test 4: {"age":30,"country":"UK","verified":false} => false

The Power of Separation

Notice how cleanly the expression tree separates from the data. The same rule can be evaluated against any context without modification. This is fundamental to the pattern's utility: rules are defined once, stored, and evaluated repeatedly against different data. This enables:

• Storing rules in a database • User-defined rules (when combined with a parser) • Rule sharing across different parts of an application • Easy testing with mock contexts

Extending the Pattern: Adding New Expression Types

One of the Interpreter Pattern's primary benefits is extensibility. Adding new expression types requires only adding new classes—existing code remains unchanged. This aligns with the Open/Closed Principle: open for extension, closed for modification.

Example: Adding arithmetic expressions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// ═══════════════════════════════════════════════════════════════════════
// EXTENSION: Adding arithmetic operations to our language
// No changes to existing code required!
// ═══════════════════════════════════════════════════════════════════════
 
/**
 * Represents addition: left + right
 */
class AddExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): number {
        const leftValue = Number(this.left.interpret(context));
        const rightValue = Number(this.right.interpret(context));
        return leftValue + rightValue;
    }
    
    toString(): string {
        return `(${this.left.toString()} + ${this.right.toString()})`;
    }
}
 
/**
 * Represents subtraction: left - right
 */
class SubtractExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): number {
        const leftValue = Number(this.left.interpret(context));
        const rightValue = Number(this.right.interpret(context));
        return leftValue - rightValue;
    }
    
    toString(): string {
        return `(${this.left.toString()} - ${this.right.toString()})`;
    }
}
 
/**
 * Represents multiplication: left * right
 */
class MultiplyExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): number {
        const leftValue = Number(this.left.interpret(context));
        const rightValue = Number(this.right.interpret(context));
        return leftValue * rightValue;
    }
    
    toString(): string {
        return `(${this.left.toString()} * ${this.right.toString()})`;
    }
}
 
/**
 * Represents function calls like MAX(a, b) or SUM(items)
 */
class FunctionCallExpression implements Expression {
    constructor(
        private functionName: string,
        private args: Expression[]
    ) {}
    
    interpret(context: EvaluationContext): any {
        const argValues = this.args.map(arg => arg.interpret(context));
        
        switch (this.functionName.toUpperCase()) {
            case 'SUM':
                return argValues.reduce((sum, val) => sum + Number(val), 0);
            case 'MAX':
                return Math.max(...argValues.map(Number));
            case 'MIN':
                return Math.min(...argValues.map(Number));
            case 'AVG':
                const nums = argValues.map(Number);
                return nums.reduce((a, b) => a + b, 0) / nums.length;
            case 'LEN':
            case 'COUNT':
                return argValues.length;
            default:
                throw new Error(`Unknown function: ${this.functionName}`);
        }
    }
    
    toString(): string {
        const argsStr = this.args.map(a => a.toString()).join(', ');
        return `${this.functionName}(${argsStr})`;
    }
}
 
// ═══════════════════════════════════════════════════════════════════════
// USING THE EXTENDED LANGUAGE
// ═══════════════════════════════════════════════════════════════════════
 
// Rule: total <= creditLimit * 1.1 (allow 10% grace on credit limit)
const creditCheckRule = new ComparisonExpression(
    new VariableExpression('total'),
    '<=',
    new MultiplyExpression(
        new VariableExpression('creditLimit'),
        new NumberLiteral(1.1)
    )
);
 
// Rule: averageOrderValue > 100
const premiumCustomerRule = new ComparisonExpression(
    new FunctionCallExpression('AVG', [
        new VariableExpression('order1'),
        new VariableExpression('order2'),
        new VariableExpression('order3')
    ]),
    '>',
    new NumberLiteral(100)
);
 
const customerData = new SimpleContext({
    total: 1050,
    creditLimit: 1000,
    order1: 150,
    order2: 80,
    order3: 200
});
 
console.log(creditCheckRule.interpret(customerData));    // true (1050 <= 1100)
console.log(premiumCustomerRule.interpret(customerData)); // true (avg 143.33 > 100)

Extension Without Modification

We added arithmetic operations, comparison expressions, and function calls without changing any existing expression classes. This is the Open/Closed Principle in action. Each new capability is a new class that implements the Expression interface; the existing interpreter infrastructure handles it automatically.

The Context's Role: Beyond Simple Variables

The Context participant deserves special attention. While our simple example used a flat variable lookup, production interpreters often need richer context capabilities.

What a robust context might provide:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/**
 * A production-grade evaluation context with advanced features.
 */
interface EnhancedContext {
    // Variable access (potentially nested: "user.address.city")
    get(path: string): any;
    has(path: string): boolean;
    
    // Scoping for local variables
    pushScope(): void;
    popScope(): void;
    defineLocal(name: string, value: any): void;
    
    // Function registry
    getFunction(name: string): ((...args: any[]) => any) | undefined;
    registerFunction(name: string, fn: (...args: any[]) => any): void;
    
    // Type information (for type checking)
    getType(path: string): string | undefined;
    
    // Execution metadata
    incrementEvalCount(): void;
    getEvalCount(): number;
    setMaxEvalCount(limit: number): void;
}
 
/**
 * Implementation of enhanced context
 */
class RichContext implements EnhancedContext {
    private scopes: Map<string, any>[] = [new Map()];
    private functions: Map<string, (...args: any[]) => any> = new Map();
    private evalCount = 0;
    private maxEvalCount = 10000;  // Prevent infinite loops
    
    constructor(rootData: Record<string, any>) {
        // Initialize root scope with data
        for (const [key, value] of Object.entries(rootData)) {
            this.scopes[0].set(key, value);
        }
        
        // Built-in functions
        this.registerBuiltins();
    }
    
    private registerBuiltins(): void {
        this.functions.set('NOW', () => new Date());
        this.functions.set('TODAY', () => {
            const d = new Date();
            return new Date(d.getFullYear(), d.getMonth(), d.getDate());
        });
        this.functions.set('UPPER', (s: string) => String(s).toUpperCase());
        this.functions.set('LOWER', (s: string) => String(s).toLowerCase());
        this.functions.set('TRIM', (s: string) => String(s).trim());
        this.functions.set('ABS', (n: number) => Math.abs(n));
        this.functions.set('ROUND', (n: number, decimals = 0) => 
            Math.round(n * 10**decimals) / 10**decimals
        );
    }
    
    get(path: string): any {
        this.incrementEvalCount();
        
        // Handle dot notation: "user.address.city"
        const parts = path.split('.');
        
        // Find variable in scopes (inner to outer)
        let value: any = undefined;
        for (let i = this.scopes.length - 1; i >= 0; i--) {
            if (this.scopes[i].has(parts[0])) {
                value = this.scopes[i].get(parts[0]);
                break;
            }
        }
        
        if (value === undefined) {
            throw new Error(`Undefined variable: ${parts[0]}`);
        }
        
        // Navigate nested path
        for (let i = 1; i < parts.length; i++) {
            if (value === null || value === undefined) {
                throw new Error(`Cannot access '${parts[i]}' of ${value} in path '${path}'`);
            }
            value = value[parts[i]];
        }
        
        return value;
    }
    
    has(path: string): boolean {
        try {
            this.get(path);
            return true;
        } catch {
            return false;
        }
    }
    
    pushScope(): void {
        this.scopes.push(new Map());
    }
    
    popScope(): void {
        if (this.scopes.length > 1) {
            this.scopes.pop();
        }
    }
    
    defineLocal(name: string, value: any): void {
        this.scopes[this.scopes.length - 1].set(name, value);
    }
    
    getFunction(name: string): ((...args: any[]) => any) | undefined {
        return this.functions.get(name.toUpperCase());
    }
    
    registerFunction(name: string, fn: (...args: any[]) => any): void {
        this.functions.set(name.toUpperCase(), fn);
    }
    
    getType(path: string): string | undefined {
        try {
            const value = this.get(path);
            return typeof value;
        } catch {
            return undefined;
        }
    }
    
    incrementEvalCount(): void {
        this.evalCount++;
        if (this.evalCount > this.maxEvalCount) {
            throw new Error(`Evaluation limit exceeded (${this.maxEvalCount}). Possible infinite loop.`);
        }
    }
    
    getEvalCount(): number {
        return this.evalCount;
    }
    
    setMaxEvalCount(limit: number): void {
        this.maxEvalCount = limit;
    }
}

Context Responsibilities in Production Systems

•Nested path resolution — Supporting paths like user.profile.settings.theme for accessing nested data structures.
•Scoping — When expressions define local variables (in loops, comprehensions), the context manages scope chains.
•Function registry — Custom functions that expressions can call are registered in the context.
•Evaluation limits — Protecting against infinite loops or excessive computation through evaluation counting.
•Type information — For type-checked languages, the context provides type information for semantic analysis.
•External services — The context might provide access to external APIs, databases, or services that expressions need.

Composite Structure and Recursive Evaluation

The Interpreter Pattern is closely related to the Composite Pattern—in fact, it can be viewed as a specialized application of Composite. This connection is worth understanding because it reveals the deep structural elegance of the pattern.

The Composite connection:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
┌─────────────────────────────────────────────────────────────────────────────┐
│               INTERPRETER PATTERN AS COMPOSITE STRUCTURE                     │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  COMPOSITE PATTERN       INTERPRETER PATTERN                                │
│  ═══════════════════     ═══════════════════                                │
│                                                                             │
│  Component               Expression (interface)                             │
│    └─ operation()          └─ interpret(context)                            │
│                                                                             │
│  Leaf                    TerminalExpression                                 │
│    └─ no children          └─ Literal, Variable                             │
│    └─ direct operation     └─ returns value directly                        │
│                                                                             │
│  Composite               NonTerminalExpression                              │
│    └─ has children         └─ And, Or, Comparison, etc.                     │
│    └─ delegates to         └─ interprets children, combines results         │
│       children                                                              │
│                                                                             │
│  RECURSIVE STRUCTURE:                                                       │
│                                                                             │
│                         [AndExpression]                                     │
│                         interpret() {                                       │
│                           left.interpret() &&                               │
│                           right.interpret()                                 │
│                         }                                                   │
│                              │                                              │
│               ╭──────────────┴──────────────╮                               │
│               │                             │                               │
│      [ComparisonExpr]               [OrExpression]                          │
│      interpret() {                  interpret() {                           │
│        left.interpret()               left.interpret() ||                   │
│        op                             right.interpret()                     │
│        right.interpret()            }                                       │
│      }                                   │                                  │
│               │                    ╭─────┴─────╮                            │
│         ╭─────┴──────╮             │           │                            │
│         │            │        [Compare]   [Compare]                         │
│    [Variable]  [Literal]                                                    │
│    interpret() interpret()     ...and so on recursively...                  │
│    = context   = value                                                      │
│      .get()                                                                 │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

How recursive evaluation works:

Base case (Terminal expressions): When interpret() is called on a terminal expression (literal or variable), it returns a value directly—no recursion.
Recursive case (Non-terminal expressions): When interpret() is called on a non-terminal expression, it first calls interpret() on its children, then combines the results.
Tree traversal: Evaluation naturally performs a post-order traversal of the AST—children are fully evaluated before their parent combines the results.
Stack management: The call stack implicitly manages the recursion; each level of the tree corresponds to a stack frame.

Stack Overflow Risk

Deeply nested expressions can cause stack overflow due to deep recursion. For languages that allow very deep nesting (100+ levels), consider:

• Trampolining — Converting recursion to iteration using thunks • Explicit stack — Managing your own stack data structure instead of using the call stack • Continuation-passing style — Transforming recursive calls into continuations

For typical DSLs with reasonable nesting depth (< 50 levels), the standard recursive approach is fine.

Summary: Grammar as Class Hierarchy

We've explored the complete solution architecture of the Interpreter Pattern. Let's consolidate the key insights:

Key Takeaways: The Interpreter Pattern Solution

•Grammar maps to class hierarchy — Each grammar production becomes a class; the grammar structure becomes the inheritance/composition structure.
•Four key participants — AbstractExpression defines the interface; TerminalExpression handles atoms; NonTerminalExpression handles composites; Context provides runtime data.
•Polymorphic interpretation — Each expression type knows how to interpret itself, eliminating type-checking switches in the evaluator.
•Recursive composition — Non-terminal expressions contain other expressions, enabling arbitrary nesting and complexity.
•Extension is additive — New expression types are new classes implementing the interface; existing code remains unchanged.
•Context decouples data from rules — The same expression tree can be evaluated against different contexts, enabling rule reuse.
•Composite Pattern relationship — The Interpreter Pattern is structurally a Composite with specialized semantics for language interpretation.

What's next:

Now that we understand how the Interpreter Pattern structures language evaluation, we need to understand when to use it. The pattern has significant trade-offs—it's powerful but carries costs. The next page will provide clear guidance on when the Interpreter Pattern is appropriate and when alternatives are better choices.

Page Complete

You now understand the Interpreter Pattern's solution architecture: representing grammar rules as a class hierarchy where each expression type implements a common interface and knows how to interpret itself. You've seen complete, working implementations and understand how the pattern enables extensible, maintainable language interpretation. Next, we'll explore the critical question of when to use this pattern.

2 / 4

Loading learning content...

System Design (LLD)Interpreter Pattern

Interpreter Pattern (Overview)

LevelAdvanced

Duration90 mins

TopicInterpreter Pattern

2 / 4

Solution: Grammar Representation as Classes

From Grammar to Object Hierarchy

What You Will Learn

The Interpreter Pattern Structure

The four participants:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
┌─────────────────────────────────────────────────────────────────────────────┐
│                        INTERPRETER PATTERN STRUCTURE                         │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  ┌─────────────────────┐           ┌──────────────────────────────────────┐ │
│  │       Client        │           │            Context                   │ │
│  ├─────────────────────┤           ├──────────────────────────────────────┤ │
│  │ Builds or receives  │           │ • Contains global information         │ │
│  │ the AST, invokes    │◀─────────▶│ • Variable bindings                   │ │
│  │ interpret() on root │           │ • External data for interpretation    │ │
│  └─────────────────────┘           └──────────────────────────────────────┘ │
│              │                                                              │
│              ▼                                                              │
│  ┌─────────────────────────────────────────────────────────────────────┐   │
│  │                    AbstractExpression                                │   │
│  │                         <<interface>>                                │   │
│  ├─────────────────────────────────────────────────────────────────────┤   │
│  │ + interpret(context: Context): any                                   │   │
│  └─────────────────────────────────────────────────────────────────────┘   │
│                            ▲                                               │
│              ┌─────────────┼─────────────┐                                 │
│              │                           │                                 │
│  ┌───────────────────────┐    ┌───────────────────────────────────────┐   │
│  │  TerminalExpression   │    │     NonTerminalExpression              │   │
│  ├───────────────────────┤    ├───────────────────────────────────────┤   │
│  │ Represents atoms      │    │ Represents composite expressions       │   │
│  │ (literals, variables) │    │ (operations combining sub-expressions) │   │
│  │                       │    │                                        │   │
│  │ Examples:             │    │ Examples:                              │   │
│  │ • NumberLiteral       │    │ • AddExpression(left, right)           │   │
│  │ • BooleanLiteral      │    │ • AndExpression(left, right)           │   │
│  │ • VariableReference   │    │ • NotExpression(operand)               │   │
│  │ • StringLiteral       │    │ • IfExpression(cond, then, else)       │   │
│  └───────────────────────┘    └───────────────────────────────────────┘   │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

Interpreter Pattern Participants

•AbstractExpression — The interface or abstract class that declares the interpret(context) method. All concrete expression classes implement this interface, enabling polymorphic interpretation. This corresponds to the abstract syntax of the grammar.
•TerminalExpression — Implements interpretation for terminal symbols (leaf nodes in the grammar). Terminal expressions don't reference other expressions; they represent atomic values like numbers, strings, booleans, or variable references. In grammar terms, these are the symbols that don't appear on the left side of any production.
•NonTerminalExpression — Implements interpretation for non-terminal symbols (composite nodes). These expressions contain references to other expressions, enabling the recursive composition that mirrors the grammar's recursive rules. Binary operators, unary operators, and control structures are typically non-terminal expressions.
•Context — Contains the global information needed during interpretation. This typically includes variable bindings (mapping variable names to values), function definitions, and any external data required for evaluation. The context is passed through the interpretation tree.

Mapping Grammar Rules to Classes

The mapping rules:

Grammar to Class Transformation Rules
Grammar Element	Class Representation	Example
Terminal symbol (literal)	Terminal Expression class with value	`42` → `NumberLiteral(42)`
Terminal symbol (variable)	Terminal Expression with name lookup	`age` → `VariableRef('age')`
Binary operator rule	NonTerminal with left & right expressions	`A + B` → `AddExpr(A, B)`
Unary operator rule	NonTerminal with single expression	`NOT A` → `NotExpr(A)`
Alternative (A \| B)	Multiple concrete classes for same interface	`expr: add \| sub` → `AddExpr`, `SubExpr`
Sequence (A B C)	Class with ordered references	`if cond then expr` → `IfExpr(cond, expr)`
Repetition (A*)	Class with list of expressions	`block: stmt*` → `Block(stmts[])`

Let's see this mapping in action:

Starting from our validation rule grammar from the previous page, here's how each production maps to a class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
GRAMMAR                                    CLASS HIERARCHY
═══════════════════════════════════════════════════════════════════════════
 
expression ::= orExpression           →   Expression (interface)
                                          ├── OrExpression
                                          ├── AndExpression  
                                          ├── NotExpression
                                          ├── ComparisonExpression
                                          ├── LiteralExpression
                                          └── VariableExpression
 
orExpression ::=                      →   class OrExpression implements Expression {
    andExpression ("OR" andExpression)*       left: Expression;
                                              right: Expression;
                                          }
 
andExpression ::=                     →   class AndExpression implements Expression {
    primary ("AND" primary)*                  left: Expression;
                                              right: Expression;
                                          }
 
primary ::=                           →   (Handled by multiple classes)
    comparison                            • ComparisonExpression
  | "(" expression ")"                    • (just wraps inner expression)
  | "NOT" primary                         • NotExpression
 
comparison ::=                        →   class ComparisonExpression implements Expression {
    identifier operator value                 field: string;
                                              operator: ComparisonOp;
                                              value: Expression;
                                          }
 
value ::=                             →   Terminal expression classes:
    number                                • NumberLiteral
  | string                                • StringLiteral  
  | "true" | "false"                      • BooleanLiteral
  | identifier                            • VariableExpression

The One-to-One Principle

Complete Implementation: Boolean Expression Language

The language grammar:

expression  ::= orExpr
orExpr      ::= andExpr ('OR' andExpr)*
andExpr     ::= primary ('AND' primary)*
primary     ::= 'NOT' primary | comparison | '(' expression ')' | literal
comparison  ::= identifier ('<'|'>'|'<='|'>='|'=='|'!=') value
literal     ::= 'true' | 'false'
value       ::= number | string | identifier

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Context holds the variable bindings for expression evaluation.
 * During interpretation, variable names are looked up in this context.
 */
interface EvaluationContext {
    /**
     * Look up a variable's value by name.
     * Throws if the variable is not defined.
     */
    get(variableName: string): any;
    
    /**
     * Check if a variable is defined in the context.
     */
    has(variableName: string): boolean;
}
 
/**
 * Simple implementation of EvaluationContext using a record.
 */
class SimpleContext implements EvaluationContext {
    constructor(private variables: Record<string, any>) {}
    
    get(variableName: string): any {
        if (!this.has(variableName)) {
            throw new Error(`Undefined variable: ${variableName}`);
        }
        return this.variables[variableName];
    }
    
    has(variableName: string): boolean {
        return variableName in this.variables;
    }
}
 
/**
 * The abstract Expression interface - all expression types implement this.
 * This is the key interface of the Interpreter Pattern.
 */
interface Expression {
    /**
     * Interpret this expression in the given context.
     * Returns the result of evaluation.
     */
    interpret(context: EvaluationContext): any;
    
    /**
     * Return a string representation for debugging.
     */
    toString(): string;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// ═══════════════════════════════════════════════════════════════════════
// TERMINAL EXPRESSIONS: Expressions that don't contain sub-expressions
// ═══════════════════════════════════════════════════════════════════════
 
/**
 * Represents a numeric literal like 42 or 3.14
 */
class NumberLiteral implements Expression {
    constructor(private value: number) {}
    
    interpret(context: EvaluationContext): number {
        // Literals evaluate to themselves - no context needed
        return this.value;
    }
    
    toString(): string {
        return String(this.value);
    }
}
 
/**
 * Represents a string literal like "hello" or "premium"
 */
class StringLiteral implements Expression {
    constructor(private value: string) {}
    
    interpret(context: EvaluationContext): string {
        return this.value;
    }
    
    toString(): string {
        return `"${this.value}"`;
    }
}
 
/**
 * Represents boolean literals: true or false
 */
class BooleanLiteral implements Expression {
    constructor(private value: boolean) {}
    
    interpret(context: EvaluationContext): boolean {
        return this.value;
    }
    
    toString(): string {
        return String(this.value);
    }
}
 
/**
 * Represents a variable reference like "age" or "user.name".
 * The actual value is looked up in the context during interpretation.
 */
class VariableExpression implements Expression {
    constructor(private variableName: string) {}
    
    interpret(context: EvaluationContext): any {
        // This is where the Context participant becomes essential
        return context.get(this.variableName);
    }
    
    toString(): string {
        return this.variableName;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// ═══════════════════════════════════════════════════════════════════════
// NON-TERMINAL EXPRESSIONS: Expressions composed of sub-expressions
// ═══════════════════════════════════════════════════════════════════════
 
/**
 * Represents a logical AND: (left AND right)
 * 
 * This is a binary non-terminal expression - it contains two sub-expressions.
 * The recursive nature of interpretation happens here: we interpret the
 * children before computing our result.
 */
class AndExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): boolean {
        // Short-circuit evaluation: if left is false, don't evaluate right
        const leftResult = this.left.interpret(context);
        if (!leftResult) {
            return false;
        }
        return Boolean(this.right.interpret(context));
    }
    
    toString(): string {
        return `(${this.left.toString()} AND ${this.right.toString()})`;
    }
}
 
/**
 * Represents a logical OR: (left OR right)
 */
class OrExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): boolean {
        // Short-circuit evaluation: if left is true, don't evaluate right
        const leftResult = this.left.interpret(context);
        if (leftResult) {
            return true;
        }
        return Boolean(this.right.interpret(context));
    }
    
    toString(): string {
        return `(${this.left.toString()} OR ${this.right.toString()})`;
    }
}
 
/**
 * Represents a logical NOT: NOT(operand)
 * 
 * This is a unary non-terminal expression - it contains one sub-expression.
 */
class NotExpression implements Expression {
    constructor(private operand: Expression) {}
    
    interpret(context: EvaluationContext): boolean {
        return !this.operand.interpret(context);
    }
    
    toString(): string {
        return `NOT(${this.operand.toString()})`;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * Supported comparison operators
 */
type ComparisonOperator = '==' | '!=' | '<' | '>' | '<=' | '>=';
 
/**
 * Represents a comparison: left op right
 * 
 * Examples:
 *   age >= 18
 *   country == "US"
 *   score < threshold
 */
class ComparisonExpression implements Expression {
    constructor(
        private left: Expression,
        private operator: ComparisonOperator,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): boolean {
        const leftValue = this.left.interpret(context);
        const rightValue = this.right.interpret(context);
        
        switch (this.operator) {
            case '==':
                return leftValue === rightValue;
            case '!=':
                return leftValue !== rightValue;
            case '<':
                return leftValue < rightValue;
            case '>':
                return leftValue > rightValue;
            case '<=':
                return leftValue <= rightValue;
            case '>=':
                return leftValue >= rightValue;
            default:
                // TypeScript exhaustiveness check
                const _exhaustive: never = this.operator;
                throw new Error(`Unknown operator: ${this.operator}`);
        }
    }
    
    toString(): string {
        return `(${this.left.toString()} ${this.operator} ${this.right.toString()})`;
    }
}
 
// ═══════════════════════════════════════════════════════════════════════
// ADDITIONAL OPERATORS: Extending the language is straightforward
// ═══════════════════════════════════════════════════════════════════════
 
/**
 * Represents an IMPLIES operator: (condition IMPLIES consequence)
 * 
 * This is logically equivalent to: NOT(condition) OR consequence
 * "If condition is true, then consequence must be true"
 */
class ImpliesExpression implements Expression {
    constructor(
        private condition: Expression,
        private consequence: Expression
    ) {}
    
    interpret(context: EvaluationContext): boolean {
        const conditionResult = this.condition.interpret(context);
        if (!conditionResult) {
            // If condition is false, implication is true (vacuously)
            return true;
        }
        // If condition is true, consequence must be true
        return Boolean(this.consequence.interpret(context));
    }
    
    toString(): string {
        return `(${this.condition.toString()} IMPLIES ${this.consequence.toString()})`;
    }
}

Using the Interpreter: AST Construction and Evaluation

Example: Building and evaluating expressions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// ═══════════════════════════════════════════════════════════════════════
// EXAMPLE: Form Validation Rule Evaluation
// ═══════════════════════════════════════════════════════════════════════
 
// Rule: (age >= 18) AND ((country == "US") OR (verified == true))
// 
// This rule requires:
// - User must be at least 18 years old, AND
// - Either be from the US, OR be verified
 
// Step 1: Build the expression tree (normally done by a parser)
const validationRule: Expression = new AndExpression(
    // Left side: age >= 18
    new ComparisonExpression(
        new VariableExpression('age'),
        '>=',
        new NumberLiteral(18)
    ),
    // Right side: (country == "US") OR (verified == true)
    new OrExpression(
        new ComparisonExpression(
            new VariableExpression('country'),
            '==',
            new StringLiteral('US')
        ),
        new ComparisonExpression(
            new VariableExpression('verified'),
            '==',
            new BooleanLiteral(true)
        )
    )
);
 
// Step 2: Create context with form data
const formData = new SimpleContext({
    age: 25,
    country: 'UK',
    verified: true
});
 
// Step 3: Evaluate the rule
const isValid = validationRule.interpret(formData);
console.log(`Validation result: ${isValid}`);  // true (age >= 18 AND verified)
console.log(`Rule: ${validationRule.toString()}`);
// Output: ((age >= 18) AND ((country == "US") OR (verified == true)))
 
// ═══════════════════════════════════════════════════════════════════════
// EXAMPLE: Different contexts, same expression
// ═══════════════════════════════════════════════════════════════════════
 
// The same expression can be evaluated with different contexts
const testCases = [
    { age: 25, country: 'US', verified: false },  // true: age OK, country is US
    { age: 25, country: 'UK', verified: true },   // true: age OK, verified
    { age: 16, country: 'US', verified: true },   // false: age too low
    { age: 30, country: 'UK', verified: false },  // false: not US, not verified
];
 
testCases.forEach((data, index) => {
    const context = new SimpleContext(data);
    const result = validationRule.interpret(context);
    console.log(`Test ${index + 1}: ${JSON.stringify(data)} => ${result}`);
});
 
// Output:
// Test 1: {"age":25,"country":"US","verified":false} => true
// Test 2: {"age":25,"country":"UK","verified":true} => true
// Test 3: {"age":16,"country":"US","verified":true} => false
// Test 4: {"age":30,"country":"UK","verified":false} => false

The Power of Separation

• Storing rules in a database • User-defined rules (when combined with a parser) • Rule sharing across different parts of an application • Easy testing with mock contexts

Extending the Pattern: Adding New Expression Types

Example: Adding arithmetic expressions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// ═══════════════════════════════════════════════════════════════════════
// EXTENSION: Adding arithmetic operations to our language
// No changes to existing code required!
// ═══════════════════════════════════════════════════════════════════════
 
/**
 * Represents addition: left + right
 */
class AddExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): number {
        const leftValue = Number(this.left.interpret(context));
        const rightValue = Number(this.right.interpret(context));
        return leftValue + rightValue;
    }
    
    toString(): string {
        return `(${this.left.toString()} + ${this.right.toString()})`;
    }
}
 
/**
 * Represents subtraction: left - right
 */
class SubtractExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): number {
        const leftValue = Number(this.left.interpret(context));
        const rightValue = Number(this.right.interpret(context));
        return leftValue - rightValue;
    }
    
    toString(): string {
        return `(${this.left.toString()} - ${this.right.toString()})`;
    }
}
 
/**
 * Represents multiplication: left * right
 */
class MultiplyExpression implements Expression {
    constructor(
        private left: Expression,
        private right: Expression
    ) {}
    
    interpret(context: EvaluationContext): number {
        const leftValue = Number(this.left.interpret(context));
        const rightValue = Number(this.right.interpret(context));
        return leftValue * rightValue;
    }
    
    toString(): string {
        return `(${this.left.toString()} * ${this.right.toString()})`;
    }
}
 
/**
 * Represents function calls like MAX(a, b) or SUM(items)
 */
class FunctionCallExpression implements Expression {
    constructor(
        private functionName: string,
        private args: Expression[]
    ) {}
    
    interpret(context: EvaluationContext): any {
        const argValues = this.args.map(arg => arg.interpret(context));
        
        switch (this.functionName.toUpperCase()) {
            case 'SUM':
                return argValues.reduce((sum, val) => sum + Number(val), 0);
            case 'MAX':
                return Math.max(...argValues.map(Number));
            case 'MIN':
                return Math.min(...argValues.map(Number));
            case 'AVG':
                const nums = argValues.map(Number);
                return nums.reduce((a, b) => a + b, 0) / nums.length;
            case 'LEN':
            case 'COUNT':
                return argValues.length;
            default:
                throw new Error(`Unknown function: ${this.functionName}`);
        }
    }
    
    toString(): string {
        const argsStr = this.args.map(a => a.toString()).join(', ');
        return `${this.functionName}(${argsStr})`;
    }
}
 
// ═══════════════════════════════════════════════════════════════════════
// USING THE EXTENDED LANGUAGE
// ═══════════════════════════════════════════════════════════════════════
 
// Rule: total <= creditLimit * 1.1 (allow 10% grace on credit limit)
const creditCheckRule = new ComparisonExpression(
    new VariableExpression('total'),
    '<=',
    new MultiplyExpression(
        new VariableExpression('creditLimit'),
        new NumberLiteral(1.1)
    )
);
 
// Rule: averageOrderValue > 100
const premiumCustomerRule = new ComparisonExpression(
    new FunctionCallExpression('AVG', [
        new VariableExpression('order1'),
        new VariableExpression('order2'),
        new VariableExpression('order3')
    ]),
    '>',
    new NumberLiteral(100)
);
 
const customerData = new SimpleContext({
    total: 1050,
    creditLimit: 1000,
    order1: 150,
    order2: 80,
    order3: 200
});
 
console.log(creditCheckRule.interpret(customerData));    // true (1050 <= 1100)
console.log(premiumCustomerRule.interpret(customerData)); // true (avg 143.33 > 100)

Extension Without Modification

The Context's Role: Beyond Simple Variables

The Context participant deserves special attention. While our simple example used a flat variable lookup, production interpreters often need richer context capabilities.

What a robust context might provide:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/**
 * A production-grade evaluation context with advanced features.
 */
interface EnhancedContext {
    // Variable access (potentially nested: "user.address.city")
    get(path: string): any;
    has(path: string): boolean;
    
    // Scoping for local variables
    pushScope(): void;
    popScope(): void;
    defineLocal(name: string, value: any): void;
    
    // Function registry
    getFunction(name: string): ((...args: any[]) => any) | undefined;
    registerFunction(name: string, fn: (...args: any[]) => any): void;
    
    // Type information (for type checking)
    getType(path: string): string | undefined;
    
    // Execution metadata
    incrementEvalCount(): void;
    getEvalCount(): number;
    setMaxEvalCount(limit: number): void;
}
 
/**
 * Implementation of enhanced context
 */
class RichContext implements EnhancedContext {
    private scopes: Map<string, any>[] = [new Map()];
    private functions: Map<string, (...args: any[]) => any> = new Map();
    private evalCount = 0;
    private maxEvalCount = 10000;  // Prevent infinite loops
    
    constructor(rootData: Record<string, any>) {
        // Initialize root scope with data
        for (const [key, value] of Object.entries(rootData)) {
            this.scopes[0].set(key, value);
        }
        
        // Built-in functions
        this.registerBuiltins();
    }
    
    private registerBuiltins(): void {
        this.functions.set('NOW', () => new Date());
        this.functions.set('TODAY', () => {
            const d = new Date();
            return new Date(d.getFullYear(), d.getMonth(), d.getDate());
        });
        this.functions.set('UPPER', (s: string) => String(s).toUpperCase());
        this.functions.set('LOWER', (s: string) => String(s).toLowerCase());
        this.functions.set('TRIM', (s: string) => String(s).trim());
        this.functions.set('ABS', (n: number) => Math.abs(n));
        this.functions.set('ROUND', (n: number, decimals = 0) => 
            Math.round(n * 10**decimals) / 10**decimals
        );
    }
    
    get(path: string): any {
        this.incrementEvalCount();
        
        // Handle dot notation: "user.address.city"
        const parts = path.split('.');
        
        // Find variable in scopes (inner to outer)
        let value: any = undefined;
        for (let i = this.scopes.length - 1; i >= 0; i--) {
            if (this.scopes[i].has(parts[0])) {
                value = this.scopes[i].get(parts[0]);
                break;
            }
        }
        
        if (value === undefined) {
            throw new Error(`Undefined variable: ${parts[0]}`);
        }
        
        // Navigate nested path
        for (let i = 1; i < parts.length; i++) {
            if (value === null || value === undefined) {
                throw new Error(`Cannot access '${parts[i]}' of ${value} in path '${path}'`);
            }
            value = value[parts[i]];
        }
        
        return value;
    }
    
    has(path: string): boolean {
        try {
            this.get(path);
            return true;
        } catch {
            return false;
        }
    }
    
    pushScope(): void {
        this.scopes.push(new Map());
    }
    
    popScope(): void {
        if (this.scopes.length > 1) {
            this.scopes.pop();
        }
    }
    
    defineLocal(name: string, value: any): void {
        this.scopes[this.scopes.length - 1].set(name, value);
    }
    
    getFunction(name: string): ((...args: any[]) => any) | undefined {
        return this.functions.get(name.toUpperCase());
    }
    
    registerFunction(name: string, fn: (...args: any[]) => any): void {
        this.functions.set(name.toUpperCase(), fn);
    }
    
    getType(path: string): string | undefined {
        try {
            const value = this.get(path);
            return typeof value;
        } catch {
            return undefined;
        }
    }
    
    incrementEvalCount(): void {
        this.evalCount++;
        if (this.evalCount > this.maxEvalCount) {
            throw new Error(`Evaluation limit exceeded (${this.maxEvalCount}). Possible infinite loop.`);
        }
    }
    
    getEvalCount(): number {
        return this.evalCount;
    }
    
    setMaxEvalCount(limit: number): void {
        this.maxEvalCount = limit;
    }
}

Context Responsibilities in Production Systems

•Nested path resolution — Supporting paths like user.profile.settings.theme for accessing nested data structures.
•Scoping — When expressions define local variables (in loops, comprehensions), the context manages scope chains.
•Function registry — Custom functions that expressions can call are registered in the context.
•Evaluation limits — Protecting against infinite loops or excessive computation through evaluation counting.
•Type information — For type-checked languages, the context provides type information for semantic analysis.
•External services — The context might provide access to external APIs, databases, or services that expressions need.

Composite Structure and Recursive Evaluation

The Composite connection:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
┌─────────────────────────────────────────────────────────────────────────────┐
│               INTERPRETER PATTERN AS COMPOSITE STRUCTURE                     │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  COMPOSITE PATTERN       INTERPRETER PATTERN                                │
│  ═══════════════════     ═══════════════════                                │
│                                                                             │
│  Component               Expression (interface)                             │
│    └─ operation()          └─ interpret(context)                            │
│                                                                             │
│  Leaf                    TerminalExpression                                 │
│    └─ no children          └─ Literal, Variable                             │
│    └─ direct operation     └─ returns value directly                        │
│                                                                             │
│  Composite               NonTerminalExpression                              │
│    └─ has children         └─ And, Or, Comparison, etc.                     │
│    └─ delegates to         └─ interprets children, combines results         │
│       children                                                              │
│                                                                             │
│  RECURSIVE STRUCTURE:                                                       │
│                                                                             │
│                         [AndExpression]                                     │
│                         interpret() {                                       │
│                           left.interpret() &&                               │
│                           right.interpret()                                 │
│                         }                                                   │
│                              │                                              │
│               ╭──────────────┴──────────────╮                               │
│               │                             │                               │
│      [ComparisonExpr]               [OrExpression]                          │
│      interpret() {                  interpret() {                           │
│        left.interpret()               left.interpret() ||                   │
│        op                             right.interpret()                     │
│        right.interpret()            }                                       │
│      }                                   │                                  │
│               │                    ╭─────┴─────╮                            │
│         ╭─────┴──────╮             │           │                            │
│         │            │        [Compare]   [Compare]                         │
│    [Variable]  [Literal]                                                    │
│    interpret() interpret()     ...and so on recursively...                  │
│    = context   = value                                                      │
│      .get()                                                                 │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

How recursive evaluation works:

Base case (Terminal expressions): When interpret() is called on a terminal expression (literal or variable), it returns a value directly—no recursion.
Recursive case (Non-terminal expressions): When interpret() is called on a non-terminal expression, it first calls interpret() on its children, then combines the results.
Tree traversal: Evaluation naturally performs a post-order traversal of the AST—children are fully evaluated before their parent combines the results.
Stack management: The call stack implicitly manages the recursion; each level of the tree corresponds to a stack frame.

Stack Overflow Risk

Deeply nested expressions can cause stack overflow due to deep recursion. For languages that allow very deep nesting (100+ levels), consider:

For typical DSLs with reasonable nesting depth (< 50 levels), the standard recursive approach is fine.

Summary: Grammar as Class Hierarchy

We've explored the complete solution architecture of the Interpreter Pattern. Let's consolidate the key insights:

Key Takeaways: The Interpreter Pattern Solution

•Grammar maps to class hierarchy — Each grammar production becomes a class; the grammar structure becomes the inheritance/composition structure.
•Four key participants — AbstractExpression defines the interface; TerminalExpression handles atoms; NonTerminalExpression handles composites; Context provides runtime data.
•Polymorphic interpretation — Each expression type knows how to interpret itself, eliminating type-checking switches in the evaluator.
•Recursive composition — Non-terminal expressions contain other expressions, enabling arbitrary nesting and complexity.
•Extension is additive — New expression types are new classes implementing the interface; existing code remains unchanged.
•Context decouples data from rules — The same expression tree can be evaluated against different contexts, enabling rule reuse.
•Composite Pattern relationship — The Interpreter Pattern is structurally a Composite with specialized semantics for language interpretation.

What's next:

Page Complete

2 / 4