Why does the Interpreter pattern break down for large or evolving grammars, and what would you use instead?

## Where the pattern starts to hurt ### 1. Class explosion, linear in grammar size One class per production is fine for `literal | variable | and | or | not` (five classes). A realistic expression language has literals of several types, field references, arithmetic, comparison, string functions, date functions, `in`, `between`, `like`, `case`, aggregation, null handling — easily 40–80 productions. Each becomes a class with a constructor, equality, hashing, printing, and evaluation. The grammar is now spread across dozens of files with no single place to read it. ### 2. The grammar is implicit and unverified With a parser generator the grammar is a **declarative artifact** the tool checks for ambiguity, and precedence/associativity are declared once. With Interpreter, precedence lives in whatever hand-written builder or parser you wrote; nothing verifies it, and a subtle mistake shows up as `a OR b AND c` evaluating wrongly. ### 3. Cross-cutting changes touch every class Adding three-valued (SQL-style) null logic, adding a step budget, changing the return type from `Boolean` to a `Value` union, adding source positions for error messages — each ripples through every node class. This is the **expression problem** in its painful direction: node types are cheap to add, *operations and shared semantics* are expensive. ### 4. It covers only evaluation Interpreter never defines lexing, parsing, error recovery, or diagnostics. A user-facing DSL needs "unexpected `)` at line 3, column 12" quality errors, which is real work you get largely for free from a generator. ### 5. Performance Tree walking costs a **polymorphic call plus pointer chasing per node**, poor cache locality, and often boxing of intermediate values. For a rule evaluated a few times per request it's irrelevant; for a rule evaluated per row over millions of rows it can be 10–100× slower than a compiled form. ### 6. Deep recursion `interpret` recurses on the call stack, so a pathological or generated expression (a chain of thousands of `OR`s) can blow the stack. Robust systems cap parse depth or use an explicit stack machine. ## What to use instead, by axis **Front end (text → tree)** - **Parser generators** — ANTLR, yacc/bison, JavaCC, Lark: grammar in one file, generated lexer+parser, precedence declarations, error recovery, generated AST/visitor scaffolding. - **Parser combinators** — build parsers by composing functions; grammar stays in code, good for medium DSLs, typically slower and with weaker error messages than generated LR parsers. - **Hand-written recursive descent / Pratt parsing** — what most production language implementations actually use, because it gives the best control over error messages; more work but no tooling dependency. - **Skip parsing entirely** — represent rules as JSON/structured data from a UI builder. Then Interpreter's evaluation half is genuinely all you need. **Back end (tree → result)** - **Visitor over the AST** — keeps node classes dumb data and puts each operation (evaluate, type-check, pretty-print, optimize) in its own class. Standard for generated ASTs. - **Closure compilation / partial evaluation** — walk the tree once and emit a nested function/closure per node; evaluation then avoids re-dispatching on node type and lets constant folding happen at compile time. Often 2–10× faster with modest effort. - **Bytecode compilation + a VM loop** — flatten the tree into an instruction array executed by a switch loop; better locality, easy to add a step budget for untrusted rules. - **Runtime code generation / JIT** — emit native or platform bytecode; fastest, most complex, hardest to sandbox and debug. - **Push it to an existing engine** — translate rules into SQL `WHERE` clauses, a search-engine query, or a mature expression library rather than writing your own. ## Decision checklist Use Interpreter when **all** hold: grammar under roughly 10–15 productions; grammar stable across quarters; trees mostly built programmatically or from structured data, not parsed prose; evaluation is not on a hot path; clarity for the team matters more than throughput. Move to generator + Visitor/compiled evaluator when **any** holds: the grammar keeps growing; users type the language and need good errors; you need multiple operations over the same trees (evaluate, validate, explain, optimize); evaluation is hot; or rules come from untrusted users and need hard resource limits. ## Hybrid, and the usual real answer The common production shape is: **generated or hand-written parser → AST → Visitor-based type checker → closure or bytecode compiler → cached compiled rule keyed by rule hash → evaluate per record with a step budget.** Interpreter's conceptual contribution — the grammar as a typed tree with a uniform evaluation operation — survives; the literal one-class-per-rule-with-an-interpret-method structure often does not. ## What to say when asked "have you used it?" Honest and strong: "Rarely in the textbook form. I've used the AST-plus-evaluation idea for a filter/rule DSL, but with a hand-written parser and a Visitor evaluator, and I cached compiled rules. If the grammar were bigger I'd have reached for ANTLR."