Walk through the participants of the Interpreter pattern — AbstractExpression, TerminalExpression, NonterminalExpression, Context, and Client — and explain what belongs in the context object.

middleshould knowfreq 18%

answer

AbstractExpression = interpret(context)
terminals = leaves, non-terminals = hold children
context = bindings + subject + guards, passed as parameter
nodes immutable → reusable, thread-safe
client parses/builds tree, calls root

basics

~20 s

AbstractExpression declares interpret(context). Terminals are leaves like literals and variables. Non-terminals hold child expressions and combine their results. Context carries variable values and input needed while evaluating. The client builds the tree and calls interpret on the root.

solid answer

~50 s

AbstractExpression is the common interface with a single interpret(context) operation, so every node is substitutable. TerminalExpression implements rules with no sub-parts — literals, variable references, constants — and returns a value straight from the context or from itself. NonterminalExpression implements composite rules (And, Or, Not, Plus, GreaterThan); it holds one or more child AbstractExpression fields, interprets them, and combines the results, which is where operator semantics like short-circuiting live. Context is the evaluation environment threaded through the recursion: variable bindings, the record or event being evaluated, a clock, an output buffer, sometimes a step budget. Keeping it a parameter rather than node state is what makes one parsed tree reusable across many inputs and safe to share between threads. Client builds or obtains the tree (parser, builder, deserializer) and calls interpret on the root. Nodes should be immutable; all per-evaluation state belongs in the context.

`AbstractExpression` is the common interface with a single `interpret(context)` operation, so every node is substitutable. `TerminalExpression` implements rules with no sub-parts — literals, variable references, constants — and returns a value straight from the context or from itself. `NonterminalExpression` implements composite rules (`And`, `Or`, `Not`, `Plus`, `GreaterThan`); it holds one or more child `AbstractExpression` fields, interprets them, and combines the results, which is where operator semantics like short-circuiting live. `Context` is the evaluation environment threaded through the recursion: variable bindings, the record or event being evaluated, a clock, an output buffer, sometimes a step budget. Keeping it a parameter rather than node state is what makes one parsed tree reusable across many inputs and safe to share between threads. `Client` builds or obtains the tree (parser, builder, deserializer) and calls `interpret` on the root. Nodes should be immutable; all per-evaluation state belongs in the context.

code

pseudocode · 18 lines

pseudocode

interface Expr { Value interpret(Context ctx) }

class Context {
  subject          // the record being evaluated
  bindings         // name -> value
  var stepsLeft    // guard for untrusted rules
  lookup(name) = bindings[name] ?: throw UnboundVariable(name)
}

class FieldRef(name) : Expr { interpret(ctx) = ctx.subject[name] }        // terminal
class Literal(v)     : Expr { interpret(ctx) = v }                        // terminal
class And(l, r)      : Expr {                                             // non-terminal
  interpret(ctx) = if (!l.interpret(ctx)) false else r.interpret(ctx)      // short-circuit
}

// one immutable tree, many contexts, safe in parallel
rule = And(GreaterThan(FieldRef("total"), Literal(100)), ...)
orders.parallelForEach { o -> rule.interpret(Context(subject = o)) }

go deeper

for a junior

Name the participants and say what each does in one line; show a two-level tree and trace evaluation.

for a middle

Explain why context is a parameter, what goes in it, and where operator semantics like short-circuiting live.

for a senior

Discuss immutability and thread safety, return-type/typing choices, error strategy, and a separate validation pass before evaluation.

for a principal

Talk about the rule lifecycle: authoring, validation at save time, caching compiled trees, evaluation guards for untrusted rules, and observability of which rules fired.

The five participants

1. AbstractExpression

The common abstraction — an interface or abstract class declaring the single operation, conventionally interpret(context). Everything else in the tree is substitutable through it. Its return type matters: a boolean-only rule language can return Boolean; a mixed language needs a Value type (tagged union / sealed hierarchy) or generics, otherwise you end up casting and losing type safety.

2. TerminalExpression

One class per terminal grammar rule — a rule with no sub-expressions:

Literal(42) → returns its own constant.
Variable("status") → asks the context for the current binding.
FieldRef("order.total") → pulls a value out of the subject in the context.

Terminals are typically immutable and often shared (a Flyweight): one canonical Literal(true) instance can appear in thousands of trees.

3. NonterminalExpression

One class per composite grammar rule. Each holds references to child AbstractExpressions matching the rule's right-hand side:

Not(e) — one child.
And(left, right) / Or(left, right) — two children.
Sum(children[]) — variadic.

Its interpret recursively interprets children and combines. Operator semantics live here: short-circuit And interprets right only when left is true; a strict And always interprets both, which matters if sub-expressions can have observable cost or side effects.

4. Context

The evaluation environment, passed down the recursion as a parameter. Typical contents:

Variable bindings / scope — name → value; for nested scopes (let, lambdas) a chained environment where lookup walks to the parent.
The subject — the order, event, user, or log line being tested.
Ambient services — clock, random source, feature-flag reader (injecting these keeps evaluation deterministic and testable).
Output or accumulation — buffer for a printing interpreter, list of matched rules.
Guards — remaining step budget / fuel, recursion depth, deadline, when rules come from untrusted authors.

Design rule: nodes hold grammar structure, context holds per-evaluation state. If a node caches the last evaluated value, the tree stops being reusable and stops being thread-safe. With an immutable tree and a per-call context, the same compiled rule can be evaluated concurrently against thousands of records.

A context is not mandatory in the GoF sense — a trivial arithmetic interpreter has nothing to look up — but any rule referring to variables or input needs one.

5. Client

Builds the AST and kicks off evaluation. Sources of the tree:

a parser over text (hand-written recursive descent, parser combinators, ANTLR),
a fluent builder in code: and(gt(field("total"), lit(100)), eq(field("country"), lit("DE"))),
deserialization of a JSON/YAML rule stored in a database,
a UI query builder producing nodes directly.

The client then calls root.interpret(context) — usually once per input record, reusing the tree.

Worked trace

Sentence: total > 100 AND country = "DE"

Tree: And( GreaterThan( FieldRef(total), Literal(100) ), Equals( FieldRef(country), Literal("DE") ) )

Client calls And.interpret(ctx) where ctx.subject = order.
And interprets its left child GreaterThan.
GreaterThan interprets FieldRef(total) → context reads order.total = 250; interprets Literal(100) → 100; compares → true.
And short-circuit check: left is true, so it interprets the right child Equals → false.
And returns false. Recursion unwinds; the client gets one boolean.

Common design decisions

Return type: uniform Value type versus generic Expr<T>. Generics give compile-time safety but complicate heterogeneous trees; a Value union pushes type errors to runtime unless you add a separate type-checking pass over the tree.
Errors: undefined variable, divide by zero, type mismatch. Decide between exceptions, a result/either type, or a null/unknown value with three-valued logic (common in SQL-like filters).
Immutability: make nodes immutable with final fields; construct fully-formed. This enables caching, sharing, and safe concurrency.
Validation before evaluation: a separate pass (often a Visitor) that type-checks or checks referenced fields exist, so bad rules fail at save time rather than at 3 a.m. in a hot loop.

Anti-patterns to avoid

Putting mutable per-evaluation state in the nodes.
Reaching for globals/singletons instead of the context — kills testability and concurrency.
One god class with a big switch on node type instead of one class per rule — that abandons the pattern's only real structural benefit.
Doing I/O inside interpret (database calls per node) — pre-load into the context instead.

## The five participants ### 1. AbstractExpression The common abstraction — an interface or abstract class declaring the single operation, conventionally `interpret(context)`. Everything else in the tree is substitutable through it. Its return type matters: a boolean-only rule language can return `Boolean`; a mixed language needs a `Value` type (tagged union / sealed hierarchy) or generics, otherwise you end up casting and losing type safety. ### 2. TerminalExpression One class per **terminal** grammar rule — a rule with no sub-expressions: - `Literal(42)` → returns its own constant. - `Variable("status")` → asks the context for the current binding. - `FieldRef("order.total")` → pulls a value out of the subject in the context. Terminals are typically immutable and often shared (a **Flyweight**): one canonical `Literal(true)` instance can appear in thousands of trees. ### 3. NonterminalExpression One class per **composite** grammar rule. Each holds references to child `AbstractExpression`s matching the rule's right-hand side: - `Not(e)` — one child. - `And(left, right)` / `Or(left, right)` — two children. - `Sum(children[])` — variadic. Its `interpret` recursively interprets children and combines. **Operator semantics live here**: short-circuit `And` interprets `right` only when `left` is true; a strict `And` always interprets both, which matters if sub-expressions can have observable cost or side effects. ### 4. Context The evaluation environment, passed **down the recursion as a parameter**. Typical contents: - **Variable bindings / scope** — name → value; for nested scopes (`let`, lambdas) a chained environment where lookup walks to the parent. - **The subject** — the order, event, user, or log line being tested. - **Ambient services** — clock, random source, feature-flag reader (injecting these keeps evaluation deterministic and testable). - **Output or accumulation** — buffer for a printing interpreter, list of matched rules. - **Guards** — remaining step budget / fuel, recursion depth, deadline, when rules come from untrusted authors. **Design rule: nodes hold grammar structure, context holds per-evaluation state.** If a node caches the last evaluated value, the tree stops being reusable and stops being thread-safe. With an immutable tree and a per-call context, the same compiled rule can be evaluated concurrently against thousands of records. A context is *not* mandatory in the GoF sense — a trivial arithmetic interpreter has nothing to look up — but any rule referring to variables or input needs one. ### 5. Client Builds the AST and kicks off evaluation. Sources of the tree: - a **parser** over text (hand-written recursive descent, parser combinators, ANTLR), - a **fluent builder** in code: `and(gt(field("total"), lit(100)), eq(field("country"), lit("DE")))`, - **deserialization** of a JSON/YAML rule stored in a database, - a **UI query builder** producing nodes directly. The client then calls `root.interpret(context)` — usually once per input record, reusing the tree. ## Worked trace Sentence: `total > 100 AND country = "DE"` Tree: `And( GreaterThan( FieldRef(total), Literal(100) ), Equals( FieldRef(country), Literal("DE") ) )` 1. Client calls `And.interpret(ctx)` where `ctx.subject = order`. 2. `And` interprets its left child `GreaterThan`. 3. `GreaterThan` interprets `FieldRef(total)` → context reads `order.total = 250`; interprets `Literal(100)` → `100`; compares → `true`. 4. `And` short-circuit check: left is true, so it interprets the right child `Equals` → `false`. 5. `And` returns `false`. Recursion unwinds; the client gets one boolean. ## Common design decisions - **Return type**: uniform `Value` type versus generic `Expr<T>`. Generics give compile-time safety but complicate heterogeneous trees; a `Value` union pushes type errors to runtime unless you add a separate type-checking pass over the tree. - **Errors**: undefined variable, divide by zero, type mismatch. Decide between exceptions, a result/either type, or a null/unknown value with three-valued logic (common in SQL-like filters). - **Immutability**: make nodes immutable with final fields; construct fully-formed. This enables caching, sharing, and safe concurrency. - **Validation before evaluation**: a separate pass (often a Visitor) that type-checks or checks referenced fields exist, so bad rules fail at save time rather than at 3 a.m. in a hot loop. ## Anti-patterns to avoid - Putting mutable per-evaluation state in the nodes. - Reaching for globals/singletons instead of the context — kills testability and concurrency. - One god class with a big `switch` on node type instead of one class per rule — that abandons the pattern's only real structural benefit. - Doing I/O inside `interpret` (database calls per node) — pre-load into the context instead.

Why pass the context as a parameter instead of storing state inside the expression nodes?
Because the tree then stays immutable and stateless: one parsed rule can be cached, shared, and evaluated concurrently against many inputs. Node-held state makes evaluation non-reentrant, breaks thread safety, and prevents reuse.
How would you support nested scopes, such as a let-binding or a lambda parameter?
Use a chained environment: the context holds a map plus a pointer to its enclosing context. A binding node creates a child context with the new name bound and interprets its body in it; lookups walk the chain outward until found.
Where do you handle errors like an undefined variable or a type mismatch?
Either at evaluation time (exception or result type from the terminal/comparison node) or, better for user-authored rules, in a separate validation pass over the tree at save time, so bad rules never reach production evaluation.

saying these in an interview costs you the question

Caching per-evaluation results inside node fields, breaking reuse and thread safety
Using global/static state instead of an explicit context
Implementing every rule in one class with a switch on a node-type enum — that is not the pattern
Performing database or network I/O inside interpret rather than pre-loading into the context
Assuming a context is always required — a pure arithmetic interpreter may need none

Walk through the participants of the Interpreter pattern — AbstractExpression, TerminalExpression, NonterminalExpression, Context, and Client — and explain what belongs in the context object.

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The five participants

1. AbstractExpression

2. TerminalExpression

3. NonterminalExpression

4. Context

5. Client

Worked trace

Common design decisions

Anti-patterns to avoid

▾common follow-ups3 questions

▾red flags5 flags

§ context

▾related questions4 questions

▾related topics4 topics

The five participants

1. AbstractExpression

2. TerminalExpression

3. NonterminalExpression

4. Context

5. Client

Worked trace

Common design decisions

Anti-patterns to avoid

answer

go deeper

context