Gof Interpreter

---
name: gof-interpreter
description: >
  Interpreter in modern Java: representing a small language as a typed tree and evaluating it,
  using per-node interpretation or a sealed AST with an exhaustive switch according to the extension contract.
  Covers parsing as a separate problem the pattern does not solve, when an existing expression
  language beats writing one, how general expression engines become code-execution surfaces when
  exposed with unsafe capabilities,
  the resource bounds an interpreter over untrusted input needs, and closure compilation when tree
  walking is too slow. Use when a filter, rule or formula language is designed, when configuration
  has grown conditionals, when someone proposes embedding an expression evaluator, or when an
  expression from a request is passed to a template or EL engine. Does not cover adding operations over an existing tree (gof-visitor), the tree structure
  itself (gof-composite), query specifications over a database
  (query-objects-and-specifications), or JIT compilation of Java
  (jit-compilation).
---

# Interpreter

## Purpose

Give a small language a typed representation and an evaluator. The pattern is worth its cost when
users — or configuration, or another service — must express conditions the code cannot enumerate:
filter expressions, pricing formulas, routing rules, feature-flag conditions, alert predicates.

Two boundaries help scope it. Parsing is a separate responsibility even though a usable language
normally needs it. And the GoF class-per-production approach fits small grammars best; scoping,
user functions, recursion, optimization or strict isolation may justify a mature runtime, bytecode
VM, or existing language rather than an ever-growing `switch`.

Start with actual consumer expressions, existing configuration/query APIs and accepted language
semantics. Identify who authors rules, which inputs and capabilities they may use, and whether
rules must also be explained, stored or translated. Resolve material type/error/authorization gaps
before prescribing a language; retain an adequate existing mechanism when no new grammar is needed.

The sealed AST plus pattern-switch examples require Java 21 or later without preview features.
Inspect the target compiler/runtime and engine versions; adopting Interpreter does not authorize
an upgrade. On older baselines use supported per-node dispatch or an existing evaluator.

## When it is the answer

```text
Users must express conditions you cannot enumerate at compile time,
in a language you control and can keep small
        → consider Interpreter; choose dispatch from the extension contract.

Rules change more often than releases and must be stored as data
        → compare fixed configuration with a language; version stored syntax/AST
          and semantic configuration if interpretation is needed.

Expressions must be inspected as well as evaluated — explained,
optimised, translated to SQL, shown in a UI
        → a typed AST is the point; evaluation is one operation over it
          (and several operations suggest gof-visitor).
```

## When it is not

- **The conditions are known and few.** Named rules or configuration with a fixed shape can
  be simpler than a language. They still need validation of values and combinations.
- **A suitable language already exists.** CEL, JSONLogic, a rules engine or a query DSL is
  usually cheaper than designing, documenting, versioning and securing your own.
- **Parsing is the unresolved problem.** Choose recursive descent, combinators or a generator
  for the grammar and maintenance needs; Interpreter alone does not supply that parser.
- **The expression comes from an untrusted source and the chosen engine exposes constructors,
  reflection, bean/type access or host functions.** That can become arbitrary code execution.
  Prefer a purpose-built restricted language or isolation. SpEL `SimpleEvaluationContext` limits
  features but is not a sandbox guarantee: reachable getters/accessors/functions may have effects.
- **It has an unverified latency target.** A tree walk need not allocate per node and may be fast
  enough. Profile parsing and evaluation before adding closure or bytecode compilation.

## Modern Java expression

```text
Classical                            Modern
───────────────────────────────────  ───────────────────────────────────
abstract class Expression            sealed interface Expr
  abstract Value interpret(Context)    permits Literal, Var, And, Or, Cmp

one interpret() per node class       one exhaustive switch — the whole
                                     evaluator readable in one place, and
                                     rebuilding exposes missing exhaustive coverage

Context as a mutable map             an immutable context record, or a
                                     Function<String, Value> resolver

evaluation only                      several folds over the same AST:
                                     evaluate, describe, toSql, validate
```

Compare a central fold with per-node `interpret()` using the actual changing axis and existing API.
A stable operation with growing node types can suit polymorphism even when you own every type;
closed node sets with independent operations can suit folds (`java-composition-over-inheritance`).
Adding a node exposes missing coverage only in recompiled exhaustive switches without a covering
fallback. Old binaries can encounter `MatchException`; neither sealing nor a fallback establishes
semantic compatibility.

## Decision rules

```text
IF expressions come from users or another service
THEN they are untrusted input. Bound text size, parse depth/node count,
     function capabilities and evaluation work. In-process wall-clock timeout alone
     cannot safely stop arbitrary non-cooperative code; use cooperative budgets or isolation.

IF a general-purpose engine (SpEL, OGNL, MVEL, EL, a template engine)
is being fed a string that a request can influence
THEN audit the evaluation context and reachable capabilities. Full reflection/type/
     method access can become arbitrary code execution; a documented restricted mode
     may be acceptable after adversarial tests.

IF grammar complexity exceeds what a small, bounded recursive-descent parser can maintain
THEN consider a generator or combinators. Precedence alone does not mandate a dependency;
     every option needs full-input consumption, position errors and adversarial limit tests.

IF the AST is walked repeatedly
THEN consider caching only after measuring parse cost. Bound size/weight, key by grammar/schema
     and relevant semantic configuration, and recheck caller permissions. Do not cache another
     caller's authorization or captured context under expression text alone.

IF evaluation is in a hot path
THEN compare tree walking, specialized closures, bytecode and vectorized/batched
     evaluation. Compilation has warm-up, code-cache and eviction costs; benchmark
     representative expressions and polymorphism (jmh-microbenchmarks).

IF an expression must run in more than one process or version
THEN the grammar is a contract: version it, and decide what an older
     evaluator does with a node it does not know.

IF nodes hold caller-specific mutable evaluation state
THEN do not share that state across calls. Prefer immutable nodes and a per-call context;
     any shared cache needs its own synchronization and complete input/key contract.

IF the language grows scoping, user functions, loops or recursion
THEN revisit parser/runtime, resource accounting, stack behavior, debugging and
     compatibility. This is a complexity trigger, not an automatic prohibition.
```

## Cross-cutting checks

- **Concurrency.** A deeply immutable, safely published AST can be shared; context values and
  resolvers must still obey their own ownership and capability contracts. The failure is a node
  that caches its last caller's result or holds a reference to the
  context — then the same expression evaluated concurrently for two users can return one user's
  answer to the other. Evaluation state belongs in a per-call context
  (`java-immutability`).
- **Distribution.** An expression transmitted between services makes the grammar a wire contract.
  A node type added by a newer producer must have a defined meaning for an older evaluator —
  usually "reject the expression", never "ignore the node", which silently changes a filter's
  meaning and can widen an authorisation rule (`rpc-and-api-contracts`).
- **Performance.** Tree walking incurs dispatch/branching but need not allocate per node after the
  AST exists. Cache parsing only with bounded cardinality, specialize only hot stable expressions,
  and reorder predicates only when error, null and short-circuit semantics permit it. Measure
  parse, evaluation, allocation and generated-code retention separately
  (`jfr-and-async-profiler`, `allocation-profiling`).
- **Testing.** Property-based testing suits this unusually well: generate expressions, assert
  semantic laws valid for the language's null/error model, and compare the compiled
  evaluator against the tree walker on random inputs. Add fuzzed text against the parser, and
  assert that pathological input is rejected by the limits rather than by a `StackOverflowError`.

## Review checklist

- [ ] The language is small, and its growth is deliberately bounded
- [ ] An existing expression language was considered and rejected for a stated reason
- [ ] Any user-influenced engine input runs with an audited allowlist/capability model or isolation
- [ ] Text/token sizes, AST depth/nodes, expensive primitive work and result sizes have enforced bounds
- [ ] Evaluation exposes only authorized, bounded capabilities; the pure filter design excludes I/O, reflection and ambient host access
- [ ] Parsing is separated; any AST cache is measured, bounded and resistant to key-cardinality abuse
- [ ] AST nodes are immutable; evaluation state lives in a per-call context
- [ ] An unknown node type from a newer producer is rejected, not ignored
- [ ] Performance claims about compilation are backed by a benchmark

Deliver the justified language or no-change decision, type/null/error/short-circuit contract, capability and resource limits,
validated execution boundary, and relevant checks. Label missing parser, SQL dialect or engine
validation explicitly; AST immutability and a sealed hierarchy alone do not establish safety.

## References

- [Grammar, alternatives and safety](references/grammar-and-alternatives.md) — when to embed CEL,
  JSONLogic or a rules engine instead; the expression-language RCE class with the shapes to look
  for; parsing options and their maintenance trade-offs; resource limits for untrusted
  expressions; and closure compilation with its measurement requirements. Read before designing
  a language.
- [Worked example](references/worked-example.md) — a filter language for a search API: the sealed
  AST, the evaluator as a fold, a second fold that compiles to SQL, closure compilation for the
  hot path, and the limits applied at the boundary. Read when implementing.