What is the intent of the Interpreter design pattern, and what kind of problem is it a good fit for?
answer
- one class per grammar rule
- sentence = AST of expression objects
- interpret(context) recurses to leaves
- terminal vs non-terminal nodes
- small + stable grammars only
basics
~20 sInterpreter gives a small language a class per grammar rule, each with an interpret operation. A sentence is turned into a tree of these objects, and evaluating the tree executes the sentence. Best for small, stable mini-languages.
solid answer
~50 sInterpreter is a behavioral pattern: given a simple language, you define a class for each rule of its grammar, and each class exposes a single `interpret(context)` operation. A sentence in that language is represented as an abstract syntax tree (AST) whose nodes are instances of those classes; evaluating the sentence means calling `interpret` on the root, which recursively calls `interpret` on children. Terminal rules (literals, variables) are leaves; non-terminal rules (and, or, plus, comparison) are composites holding sub-expressions. The `context` carries whatever the evaluation needs — variable bindings, input data, accumulated output. It fits small, stable domain-specific languages: boolean filter rules, price/discount rules, simple arithmetic, matching predicates, retry/permission policies. It is a poor fit once the grammar is large or changes often, because every rule costs a class and every new operation touches every class. Note the pattern only covers evaluation; parsing text into the tree is a separate concern.
code
pseudocode · 13 linesinterface Expr { Value interpret(Context ctx) }
// terminals
class Literal(v) : Expr { interpret(ctx) = v }
class Variable(n) : Expr { interpret(ctx) = ctx.lookup(n) }
// non-terminals (one class per grammar rule)
class And(l, r) : Expr { interpret(ctx) = l.interpret(ctx) && r.interpret(ctx) }
class Not(e) : Expr { interpret(ctx) = !e.interpret(ctx) }
// sentence: NOT (open AND urgent)
expr = Not(And(Variable("open"), Variable("urgent")))
expr.interpret(Context{ open: true, urgent: false }) // -> truego deeper
State the intent: one class per grammar rule, each with interpret(); a sentence is a tree of those objects; evaluate by walking the tree. Give one example, like a boolean filter.
Add the role names (AbstractExpression, Terminal, Non-terminal, Context), the Composite relationship, and the fit condition: small, stable grammar.
Separate parsing from evaluation, discuss class explosion and the add-operation problem (Visitor), and name when you'd instead use a parser generator plus a compiled evaluator.
Frame it as a build-vs-buy and risk decision: DSL surface area, grammar evolution cost, evaluation performance, caching parsed trees, and sandboxing untrusted rules (depth/step limits, no side effects).
## The problem Sometimes a system has to accept **rules expressed as text or data rather than as compiled code**: a search filter like `status = OPEN AND (priority > 3 OR owner = 'me')`, a pricing rule, an access policy, a log filter, a validation expression. Hard-coding every possible rule is impossible because the rules come from users or configuration and change without a redeploy. What you need is a way to *represent* such a rule as data and then *run* it. ## The idea in one sentence > Given a language, define a representation for its grammar along with an interpreter that uses that representation to interpret sentences in the language. (Gang of Four, 1994) ## Vocabulary (defined, assume nothing) - **Grammar** — the set of rules describing which sentences are legal in a language. Written as productions, e.g. `expr := literal | variable | expr AND expr | NOT expr`. - **Terminal** — a rule with no sub-parts: a literal `true`, a number `42`, a variable name `status`. - **Non-terminal** — a rule composed of other expressions: `AND`, `OR`, `NOT`, `+`. - **Sentence** — one concrete program/rule in the language, e.g. `NOT (a AND b)`. - **Abstract syntax tree (AST)** — a tree whose nodes are the grammar constructs of one sentence, with the operator at the node and operands as children. `NOT (a AND b)` becomes `Not( And( Var(a), Var(b) ) )`. - **Context** — an object passed through evaluation that supplies whatever evaluation needs: variable values, the record being tested, an output buffer, a clock. It is *not* global state; it is the evaluation environment. - **Interpret operation** — the single method (`interpret(context)`, `evaluate(env)`, `eval(ctx)`) every node implements. ## The structure ``` AbstractExpression <-- common interface: interpret(context) ├── TerminalExpression <-- Literal, Variable: returns a value directly └── NonterminalExpression <-- And, Or, Not, Plus: holds child expressions, calls interpret on them and combines results ``` **One class per grammar rule** is the defining structural commitment: the production `expr AND expr` becomes class `AndExpression` with two `AbstractExpression` fields. The shape of the code mirrors the shape of the grammar, which is the pattern's main selling point — the grammar is readable directly from the class list, and adding a rule means adding a class, not editing a giant `switch`. ## How evaluation works Evaluation is **recursive descent over the tree**. `Not.interpret(ctx)` calls `child.interpret(ctx)` and negates it; `And.interpret(ctx)` interprets left, and (usually short-circuiting) right; `Variable.interpret(ctx)` looks its name up in the context. The recursion terminates at terminals. Because the tree *is* the program, the same tree can be evaluated many times against different contexts — that is why a parsed rule is worth caching. ## What the pattern does NOT include Interpreter says nothing about **how text becomes a tree**. Lexing and parsing are a separate job — hand-written recursive-descent parser, parser combinator, or a generator like ANTLR/yacc. In many real systems the AST is not parsed from text at all: it is built with a fluent builder API, deserialized from JSON, or assembled by a UI query builder. Interpreter is only the *evaluation* half. ## Relationship to other patterns - **Composite** — Interpreter's AST is literally a Composite: uniform interface, leaves and containers treated alike. Interpreter is Composite plus a domain meaning for the tree. - **Visitor** — an alternative to putting `interpret` on each node; lets you add new operations (print, optimize, type-check, compile) without editing every node class. - **Flyweight** — terminal nodes (a literal `0`, the variable `x`) are immutable and can be shared across trees. - **Iterator / Strategy** — sometimes used inside to traverse or to swap evaluation policy. ## When it fits Good: the grammar is **small** (a handful of rules), **stable** (rarely gains new constructs), and efficiency is not critical; you want rules to be data. Classic sightings: specification/rules engines, boolean search filters, simple calculators, regex matchers for a toy subset, feature-flag targeting rules. Bad: real programming languages, grammars with dozens of productions, grammars that change every sprint, or hot paths where per-node virtual calls and object allocation matter. Then you want a parser generator for the front end and a table-driven or bytecode-compiled evaluator for the back end. ## Trade-offs summary | Upside | Downside | |---|---| | Grammar visible in the class structure | Class explosion: N rules → N classes | | Easy to add a new grammar rule (new class) | Hard to add a new *operation* (touch every class) unless you use Visitor | | Rules become data: composable, serializable, testable | Tree-walking is slow versus compiled code | | Each node is small and unit-testable | No parsing help; you still need a front end | | Same tree re-evaluated with different contexts | Deep trees risk stack overflow; untrusted input needs sandboxing |
- Does the Interpreter pattern include the parser that turns text into the tree?No. Interpreter only defines the representation and the evaluation operation. Producing the AST — lexing and parsing text, deserializing JSON, or building it with a fluent API — is a separate concern, often handled by a hand-written recursive-descent parser or a parser generator.
- How does Interpreter relate to Composite?The AST is a Composite: a common interface implemented by both leaves (terminals) and containers (non-terminals), so clients treat single nodes and whole subtrees uniformly. Interpreter adds the grammar semantics and the interpret operation on top of that structure.
- Give a realistic example where you'd reach for it.A user-editable filter or rule engine: search filters, feature-flag targeting rules, discount/pricing rules, alert conditions. The grammar is a handful of comparisons and boolean connectives, it barely changes, and the rules must be stored as data rather than compiled in.
Think of a nested paper form. Each section has its own specialist clerk who knows exactly one kind of section and nothing else. A clerk who handles an "AND" section doesn't evaluate anything itself — it hands the two sub-sections to the clerks who own them and combines their verdicts. Hand the top clerk the applicant's file (the context) and the answer bubbles back up.
saying these in an interview costs you the question
- Claiming Interpreter includes parsing or is 'how you write a compiler front end'
- Proposing Interpreter for a full programming language or a grammar with dozens of productions
- Confusing it with Strategy — Strategy swaps one algorithm; Interpreter composes a tree of grammar constructs
- Thinking the context is just global mutable state instead of an explicit evaluation environment passed in
- Saying it makes evaluation fast — tree walking is slower than compiled code