Interpreter Pattern
Interpreter is the pattern for when the requirement is "let people write their own rules". Instead of hard-coding every condition, you define a tiny language, turn each sentence of that language into a tree of objects, and evaluate the tree. Feature-flag targeting, discount eligibility and search filters are small languages in disguise.
The grouped Behavioral Patterns overview doesn't cover Interpreter. This page builds a complete one, including the parser the classic description leaves out, and is honest about when you should reach for an existing expression engine instead.
Intent
Given a small language, represent its grammar as a class hierarchy, with one class per rule, and evaluate a sentence by calling interpret on the tree of objects built from it.
The key ideas:
- One class per grammar rule. "A rule is two rules joined by
and" becomes anAndclass with two children. "A comparison is a field, an operator and a value" becomes aCompareclass. - Sentences become trees. The text
age >= 18 and country == "IN"becomesAnd(Compare(age >= 18), Compare(country == "IN")). That tree is an abstract syntax tree (AST). - Evaluation is recursive. Each node interprets itself, asking its children for their results first. The context (here, the facts about one customer) is passed down the tree.
The problem
An e-commerce team runs promotions. The first campaign is "free delivery for adult customers in India, or for anyone on the pro plan, unless the account is banned". A developer writes it as code:
import java.util.Map;
class PromotionRules {
// Campaign "FREE-DELIVERY-IN", hard-coded in March.
static boolean freeDelivery(Map<String, Object> c) {
boolean inIndia = "IN".equals(c.get("country"));
boolean adult = c.get("age") instanceof Integer age && age >= 18;
boolean pro = "pro".equals(c.get("plan"));
boolean banned = "banned".equals(c.get("status"));
return inIndia && (adult || pro) && !banned;
}
// Campaign "STUDENT-10", added in April. Campaign "DIWALI", added in May. ...
}
class BeforeDemo {
public static void main(String[] args) {
assert PromotionRules.freeDelivery(Map.of("country", "IN", "age", 30, "plan", "free", "status", "ok"));
assert !PromotionRules.freeDelivery(Map.of("country", "IN", "age", 30, "plan", "free", "status", "banned"));
System.out.println("hard-coded rule works, but every campaign needs a deploy");
}
}
import os
def free_delivery(c: dict) -> bool: # hard-coded, one function per campaign
return c.get("country") == "IN" and (c.get("age", 0) >= 18 or c.get("plan") == "pro") \
and c.get("status") != "banned"
assert free_delivery({"country": "IN", "age": 30, "plan": "free", "status": "ok"})
# The tempting shortcut: store the rule as text and eval() it.
rule_text = "country == 'IN' and (age >= 18 or plan == 'pro')"
assert eval(rule_text, {}, {"country": "IN", "age": 30, "plan": "free"})
# ...which runs ANY code someone types into the admin panel:
stored_by_an_attacker = "__import__('os').getcwd()"
assert eval(stored_by_an_attacker, {}, {}) == os.getcwd()
print("eval executed arbitrary code from a 'rule'")
The hard-coded version is fine for one campaign. It breaks down when:
- Rules change weekly and belong to someone else. The marketing team owns the campaigns. Every new rule is a ticket, a code change, a review and a deploy, for what is really data.
- The number of rules grows without bound. Hundreds of
freeDelivery,student10,diwalimethods, most of them dead after their campaign ends. - Rules need to be shown, stored and audited. "Why did this customer get the discount?" needs the rule as an inspectable thing, not as compiled bytecode.
The shortcut in the Python tab, storing rules as text and calling eval, solves the deploy problem and creates a much worse one. eval runs any expression in the host language, so a "rule" can read files, call the network or delete data. The JavaScript eval and new Function have the same problem. You need a language that can express conditions and nothing else. That's what Interpreter gives you.
Structure
classDiagram
class Rule {
<<interface>>
+matches(facts) boolean
}
class Compare {
+field String
+op String
+literal Object
+matches(facts) boolean
}
class And {
+left Rule
+right Rule
+matches(facts) boolean
}
class Or {
+left Rule
+right Rule
+matches(facts) boolean
}
class Not {
+inner Rule
+matches(facts) boolean
}
class RuleParser {
+parse(text) Rule
}
class Facts {
<<context>>
field to value map
}
class Client
Rule <|.. Compare : terminal
Rule <|.. And : nonterminal
Rule <|.. Or : nonterminal
Rule <|.. Not : nonterminal
And o-- Rule
Or o-- Rule
Not o-- Rule
RuleParser ..> Rule : builds
Client --> RuleParser
Client --> Rule
Rule ..> Facts : reads
Participants
| Participant | In the example | Responsibility |
|---|---|---|
| Abstract expression | Rule | The common interface: matches(facts) (in general, interpret(context)). |
| Terminal expression | Compare | A grammar rule with no sub-rules. Evaluates directly against the context. |
| Nonterminal expression | And, Or, Not | A grammar rule made of other rules. Holds children and combines their results. |
| Context | the facts map | Information the sentence is evaluated against: the customer's fields, variable bindings, an input string. |
| Parser (not in the original pattern, but always needed) | RuleParser | Turns text into the tree. Without it, users would have to build trees in code, which defeats the purpose. |
| Client | main, or a promotion service | Gets the tree (usually by parsing stored text) and calls matches for each customer. |
The grammar
Always write the grammar down before the classes. It settles precedence before it becomes a bug.
rule := orExpr
orExpr := andExpr ( "or" andExpr )*
andExpr := notExpr ( "and" notExpr )*
notExpr := "not" notExpr | "(" rule ")" | comparison
comparison := FIELD OP VALUE
OP := "==" | "!=" | "<" | "<=" | ">" | ">="
VALUE := NUMBER | STRING
Three decisions are encoded here:
andbinds tighter thanor, as in almost every language.a or b and cmeansa or (b and c). The grammar does this by puttingandExprinsideorExpr.notbinds tightest and applies to one comparison or a parenthesised group.not plan == "free" and age > 18means(not plan == "free") and age > 18.- Comparisons are the only leaves. There are no bare booleans, arithmetic or function calls. Every feature you leave out is one you never have to secure, document or support.
Implementation
Each version has three parts: the expression classes (the actual pattern), a small recursive-descent parser that follows the grammar line by line, and a demo with assertions. A missing field, or a field whose type doesn't match the literal (a string compared with a number), makes a comparison false rather than throwing, so a customer with incomplete data simply doesn't qualify.
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
interface Rule {
boolean matches(Map<String, Object> facts);
}
record And(Rule left, Rule right) implements Rule {
public boolean matches(Map<String, Object> f) { return left.matches(f) && right.matches(f); }
public String toString() { return "(" + left + " and " + right + ")"; }
}
record Or(Rule left, Rule right) implements Rule {
public boolean matches(Map<String, Object> f) { return left.matches(f) || right.matches(f); }
public String toString() { return "(" + left + " or " + right + ")"; }
}
record Not(Rule inner) implements Rule {
public boolean matches(Map<String, Object> f) { return !inner.matches(f); }
public String toString() { return "not " + inner; }
}
record Compare(String field, String op, Object literal) implements Rule {
public boolean matches(Map<String, Object> facts) {
Integer c = compare(facts.get(field), literal);
if (c == null) return false; // missing field or type mismatch
return switch (op) {
case "==" -> c == 0;
case "!=" -> c != 0;
case "<" -> c < 0;
case "<=" -> c <= 0;
case ">" -> c > 0;
case ">=" -> c >= 0;
default -> throw new IllegalStateException("unknown operator " + op);
};
}
private static Integer compare(Object actual, Object expected) {
if (actual instanceof Number a && expected instanceof Number b)
return Double.compare(a.doubleValue(), b.doubleValue());
if (actual instanceof String a && expected instanceof String b)
return a.compareTo(b);
return null;
}
public String toString() {
return field + " " + op + " " + (literal instanceof String s ? "\"" + s + "\"" : literal);
}
}
final class RuleParser {
// Simplification: no escape sequences inside strings; add them if a rule ever needs a literal quote
private static final Pattern TOKEN = Pattern.compile(
"\\s*(?:(\\d+(?:\\.\\d+)?)|\"([^\"]*)\"|(==|!=|<=|>=|<|>|\\(|\\))|([A-Za-z_]\\w*))");
private static final Set<String> OPERATORS = Set.of("==", "!=", "<", "<=", ">", ">=");
private static final Set<String> KEYWORDS = Set.of("and", "or", "not");
private record Token(String kind, String text) {}
private final List<Token> tokens = new ArrayList<>();
private int pos = 0;
private RuleParser(String src) {
Matcher m = TOKEN.matcher(src);
int i = 0;
while (i < src.length() && !src.substring(i).isBlank()) {
m.region(i, src.length());
if (!m.lookingAt()) throw new IllegalArgumentException("unexpected input at position " + i);
if (m.group(1) != null) tokens.add(new Token("num", m.group(1)));
else if (m.group(2) != null) tokens.add(new Token("str", m.group(2)));
else if (m.group(3) != null) tokens.add(new Token("sym", m.group(3)));
else tokens.add(new Token("word", m.group(4)));
i = m.end();
}
}
static Rule parse(String src) {
RuleParser p = new RuleParser(src);
Rule rule = p.orExpr();
if (p.pos != p.tokens.size())
throw new IllegalArgumentException("unexpected '" + p.tokens.get(p.pos).text() + "'");
return rule;
}
private Rule orExpr() {
Rule r = andExpr();
while (accept("word", "or")) r = new Or(r, andExpr());
return r;
}
private Rule andExpr() {
Rule r = notExpr();
while (accept("word", "and")) r = new And(r, notExpr());
return r;
}
private Rule notExpr() {
if (accept("word", "not")) return new Not(notExpr());
if (accept("sym", "(")) {
Rule r = orExpr();
if (!accept("sym", ")")) throw new IllegalArgumentException("expected ')'");
return r;
}
return comparison();
}
private Rule comparison() {
Token field = take();
if (field == null || !field.kind().equals("word") || KEYWORDS.contains(field.text()))
throw new IllegalArgumentException("expected a field name");
Token op = take();
if (op == null || !OPERATORS.contains(op.text()))
throw new IllegalArgumentException("expected a comparison operator after " + field.text());
Token value = take();
if (value != null && value.kind().equals("num"))
return new Compare(field.text(), op.text(), Double.valueOf(value.text()));
if (value != null && value.kind().equals("str"))
return new Compare(field.text(), op.text(), value.text());
throw new IllegalArgumentException("expected a number or string after " + field.text() + " " + op.text());
}
private boolean accept(String kind, String text) {
if (pos < tokens.size() && tokens.get(pos).kind().equals(kind) && tokens.get(pos).text().equals(text)) {
pos++;
return true;
}
return false;
}
private Token take() { return pos < tokens.size() ? tokens.get(pos++) : null; }
}
class RuleDemo {
public static void main(String[] args) {
Rule promo = RuleParser.parse(
"country == \"IN\" and (age >= 18 or plan == \"pro\") and not status == \"banned\"");
assert promo.matches(Map.of("country", "IN", "age", 25, "plan", "free", "status", "ok"));
assert promo.matches(Map.of("country", "IN", "age", 16, "plan", "pro", "status", "ok"));
assert !promo.matches(Map.of("country", "IN", "age", 16, "plan", "free", "status", "ok"));
assert !promo.matches(Map.of("country", "US", "age", 30, "plan", "pro", "status", "ok"));
assert !promo.matches(Map.of("country", "IN", "age", 30, "plan", "pro", "status", "banned"));
assert !promo.matches(Map.of("country", "IN", "age", "thirty", "plan", "free", "status", "ok"));
assert RuleParser.parse("a == 1 or b == 1 and c == 1") instanceof Or; // and binds tighter
assert RuleParser.parse(promo.toString()).equals(promo); // printing round-trips
for (String bad : List.of("age >=", "age 18", "(age > 1", "and == 1", "age > 1 extra", "age ~ 3")) {
try {
RuleParser.parse(bad);
throw new AssertionError("should reject: " + bad);
} catch (IllegalArgumentException expected) { }
}
System.out.println(promo);
}
}
from __future__ import annotations
import re
from abc import ABC, abstractmethod
from dataclasses import dataclass
Facts = dict[str, object]
class Rule(ABC):
@abstractmethod
def matches(self, facts: Facts) -> bool: ...
@dataclass(frozen=True)
class And(Rule):
left: Rule
right: Rule
def matches(self, facts: Facts) -> bool:
return self.left.matches(facts) and self.right.matches(facts)
def __str__(self) -> str:
return f"({self.left} and {self.right})"
@dataclass(frozen=True)
class Or(Rule):
left: Rule
right: Rule
def matches(self, facts: Facts) -> bool:
return self.left.matches(facts) or self.right.matches(facts)
def __str__(self) -> str:
return f"({self.left} or {self.right})"
@dataclass(frozen=True)
class Not(Rule):
inner: Rule
def matches(self, facts: Facts) -> bool:
return not self.inner.matches(facts)
def __str__(self) -> str:
return f"not {self.inner}"
_CHECKS = {
"==": lambda c: c == 0, "!=": lambda c: c != 0,
"<": lambda c: c < 0, "<=": lambda c: c <= 0,
">": lambda c: c > 0, ">=": lambda c: c >= 0,
}
@dataclass(frozen=True)
class Compare(Rule):
field: str
op: str
literal: float | str
def matches(self, facts: Facts) -> bool:
actual = facts.get(self.field)
both_numbers = isinstance(actual, (int, float)) and isinstance(self.literal, (int, float))
both_strings = isinstance(actual, str) and isinstance(self.literal, str)
if not (both_numbers or both_strings):
return False # missing field or type mismatch
c = (actual > self.literal) - (actual < self.literal) # type: ignore[operator]
return _CHECKS[self.op](c)
def __str__(self) -> str:
value = f'"{self.literal}"' if isinstance(self.literal, str) else str(self.literal)
return f"{self.field} {self.op} {value}"
# Simplification: no escape sequences inside strings; add them if a rule ever needs a literal quote
_TOKEN = re.compile(r'\s*(?:(\d+(?:\.\d+)?)|"([^"]*)"|(==|!=|<=|>=|<|>|\(|\))|([A-Za-z_]\w*))')
_KEYWORDS = {"and", "or", "not"}
class RuleParser:
def __init__(self, src: str) -> None:
self._tokens: list[tuple[str, str]] = []
self._pos = 0
i = 0
while i < len(src) and src[i:].strip():
m = _TOKEN.match(src, i)
if not m:
raise ValueError(f"unexpected input at position {i}")
num, string, sym, word = m.groups()
if num is not None:
self._tokens.append(("num", num))
elif string is not None:
self._tokens.append(("str", string))
elif sym is not None:
self._tokens.append(("sym", sym))
else:
self._tokens.append(("word", word))
i = m.end()
@classmethod
def parse(cls, src: str) -> Rule:
p = cls(src)
rule = p._or_expr()
if p._pos != len(p._tokens):
raise ValueError(f"unexpected {p._tokens[p._pos][1]!r}")
return rule
def _or_expr(self) -> Rule:
rule = self._and_expr()
while self._accept("word", "or"):
rule = Or(rule, self._and_expr())
return rule
def _and_expr(self) -> Rule:
rule = self._not_expr()
while self._accept("word", "and"):
rule = And(rule, self._not_expr())
return rule
def _not_expr(self) -> Rule:
if self._accept("word", "not"):
return Not(self._not_expr())
if self._accept("sym", "("):
rule = self._or_expr()
if not self._accept("sym", ")"):
raise ValueError("expected ')'")
return rule
return self._comparison()
def _comparison(self) -> Rule:
field = self._take()
if field is None or field[0] != "word" or field[1] in _KEYWORDS:
raise ValueError("expected a field name")
op = self._take()
if op is None or op[1] not in _CHECKS:
raise ValueError(f"expected a comparison operator after {field[1]}")
value = self._take()
if value is not None and value[0] == "num":
return Compare(field[1], op[1], float(value[1]))
if value is not None and value[0] == "str":
return Compare(field[1], op[1], value[1])
raise ValueError(f"expected a number or string after {field[1]} {op[1]}")
def _accept(self, kind: str, text: str) -> bool:
if self._pos < len(self._tokens) and self._tokens[self._pos] == (kind, text):
self._pos += 1
return True
return False
def _take(self) -> tuple[str, str] | None:
if self._pos >= len(self._tokens):
return None
self._pos += 1
return self._tokens[self._pos - 1]
if __name__ == "__main__":
promo = RuleParser.parse(
'country == "IN" and (age >= 18 or plan == "pro") and not status == "banned"')
assert promo.matches({"country": "IN", "age": 25, "plan": "free", "status": "ok"})
assert promo.matches({"country": "IN", "age": 16, "plan": "pro", "status": "ok"})
assert not promo.matches({"country": "IN", "age": 16, "plan": "free", "status": "ok"})
assert not promo.matches({"country": "US", "age": 30, "plan": "pro", "status": "ok"})
assert not promo.matches({"country": "IN", "age": 30, "plan": "pro", "status": "banned"})
assert not promo.matches({"country": "IN", "age": "thirty", "plan": "free", "status": "ok"})
assert isinstance(RuleParser.parse("a == 1 or b == 1 and c == 1"), Or) # and binds tighter
assert RuleParser.parse(str(promo)) == promo # printing round-trips
for bad in ["age >=", "age 18", "(age > 1", "and == 1", "age > 1 extra", "age ~ 3"]:
try:
RuleParser.parse(bad)
raise AssertionError(f"should reject: {bad}")
except ValueError:
pass
print(promo)
function assert(cond: unknown, msg = "assertion failed"): asserts cond {
if (!cond) throw new Error(msg);
}
type Value = number | string;
type Facts = Readonly<Record<string, Value | undefined>>;
interface Rule {
matches(facts: Facts): boolean;
toString(): string;
}
class And implements Rule {
constructor(readonly left: Rule, readonly right: Rule) {}
matches(f: Facts): boolean { return this.left.matches(f) && this.right.matches(f); }
toString(): string { return `(${this.left} and ${this.right})`; }
}
class Or implements Rule {
constructor(readonly left: Rule, readonly right: Rule) {}
matches(f: Facts): boolean { return this.left.matches(f) || this.right.matches(f); }
toString(): string { return `(${this.left} or ${this.right})`; }
}
class Not implements Rule {
constructor(readonly inner: Rule) {}
matches(f: Facts): boolean { return !this.inner.matches(f); }
toString(): string { return `not ${this.inner}`; }
}
const CHECKS = {
"==": (c: number) => c === 0, "!=": (c: number) => c !== 0,
"<": (c: number) => c < 0, "<=": (c: number) => c <= 0,
">": (c: number) => c > 0, ">=": (c: number) => c >= 0,
} as const;
type Op = keyof typeof CHECKS;
const isOp = (s: string): s is Op => Object.hasOwn(CHECKS, s);
class Compare implements Rule {
constructor(readonly field: string, readonly op: Op, readonly literal: Value) {}
matches(facts: Facts): boolean {
const actual = facts[this.field];
if (actual === undefined || typeof actual !== typeof this.literal) return false; // missing or type mismatch
const c = actual < this.literal ? -1 : actual > this.literal ? 1 : 0;
return CHECKS[this.op](c);
}
toString(): string {
const v = typeof this.literal === "string" ? `"${this.literal}"` : String(this.literal);
return `${this.field} ${this.op} ${v}`;
}
}
type Token = { kind: "num" | "str" | "sym" | "word"; text: string };
// Simplification: no escape sequences inside strings; add them if a rule ever needs a literal quote
const TOKEN = /\s*(?:(\d+(?:\.\d+)?)|"([^"]*)"|(==|!=|<=|>=|<|>|\(|\))|([A-Za-z_]\w*))/y;
const KEYWORDS = new Set(["and", "or", "not"]);
class RuleParser {
private readonly tokens: Token[] = [];
private pos = 0;
private constructor(src: string) {
let i = 0;
while (i < src.length && src.slice(i).trim() !== "") {
TOKEN.lastIndex = i;
const m = TOKEN.exec(src);
if (!m) throw new Error(`unexpected input at position ${i}`);
if (m[1] !== undefined) this.tokens.push({ kind: "num", text: m[1] });
else if (m[2] !== undefined) this.tokens.push({ kind: "str", text: m[2] });
else if (m[3] !== undefined) this.tokens.push({ kind: "sym", text: m[3] });
else this.tokens.push({ kind: "word", text: m[4]! });
i = TOKEN.lastIndex;
}
}
static parse(src: string): Rule {
const p = new RuleParser(src);
const rule = p.orExpr();
if (p.pos !== p.tokens.length) throw new Error(`unexpected '${p.tokens[p.pos]!.text}'`);
return rule;
}
private orExpr(): Rule {
let r = this.andExpr();
while (this.accept("word", "or")) r = new Or(r, this.andExpr());
return r;
}
private andExpr(): Rule {
let r = this.notExpr();
while (this.accept("word", "and")) r = new And(r, this.notExpr());
return r;
}
private notExpr(): Rule {
if (this.accept("word", "not")) return new Not(this.notExpr());
if (this.accept("sym", "(")) {
const r = this.orExpr();
if (!this.accept("sym", ")")) throw new Error("expected ')'");
return r;
}
return this.comparison();
}
private comparison(): Rule {
const field = this.take();
if (!field || field.kind !== "word" || KEYWORDS.has(field.text)) throw new Error("expected a field name");
const op = this.take();
if (!op || !isOp(op.text)) throw new Error(`expected a comparison operator after ${field.text}`);
const value = this.take();
if (value?.kind === "num") return new Compare(field.text, op.text, Number(value.text));
if (value?.kind === "str") return new Compare(field.text, op.text, value.text);
throw new Error(`expected a number or string after ${field.text} ${op.text}`);
}
private accept(kind: Token["kind"], text: string): boolean {
const t = this.tokens[this.pos];
if (t && t.kind === kind && t.text === text) { this.pos++; return true; }
return false;
}
private take(): Token | undefined { return this.tokens[this.pos++]; }
}
const promo = RuleParser.parse(`country == "IN" and (age >= 18 or plan == "pro") and not status == "banned"`);
assert(promo.matches({ country: "IN", age: 25, plan: "free", status: "ok" }));
assert(promo.matches({ country: "IN", age: 16, plan: "pro", status: "ok" }));
assert(!promo.matches({ country: "IN", age: 16, plan: "free", status: "ok" }));
assert(!promo.matches({ country: "US", age: 30, plan: "pro", status: "ok" }));
assert(!promo.matches({ country: "IN", age: 30, plan: "pro", status: "banned" }));
assert(!promo.matches({ country: "IN", age: "thirty", plan: "free", status: "ok" }));
assert(RuleParser.parse("a == 1 or b == 1 and c == 1") instanceof Or); // and binds tighter
assert(RuleParser.parse(promo.toString()).toString() === promo.toString()); // printing round-trips
for (const bad of ["age >=", "age 18", "(age > 1", "and == 1", "age > 1 extra", "age ~ 3"]) {
let rejected = false;
try { RuleParser.parse(bad); } catch { rejected = true; }
assert(rejected, `should reject: ${bad}`);
}
console.log(promo.toString());
Things to notice:
- The expression classes are tiny.
And,OrandNotare one line of logic each. That's the pattern's selling point: each grammar rule's meaning is defined in exactly one place, next to its data. - The parser mirrors the grammar.
orExprcallsandExpr, which callsnotExpr. Reading the parser next to the grammar is enough to check it. This style is called recursive descent, and it's the technique most hand-written production parsers use for languages of this size. toStringturns the tree back into text, adding parentheses everywhere so precedence can't be misread. Re-parsing the printed form gives an equal tree. That round-trip assertion is a cheap, powerful test, and it's also how an admin screen can display a stored rule.- Errors are reported when the rule is saved, not when a customer checks out. Bad syntax throws in
parse. Runparsewhen the marketing team clicks "Save", and they get the error immediately.
Parsing is not the pattern, but you can't skip it
The classic statement of Interpreter assumes the tree already exists and says nothing about how to build it. In practice the parser is half the work, and it's where most bugs live. A few rules of thumb:
- Tokenise first, then parse. A separate tokeniser handles whitespace, numbers and quoted strings once, so the parser only deals with clean tokens. The regular expression in each sample above is the whole tokeniser.
- Encode precedence in the grammar, not in ad-hoc checks. One grammar level per precedence level, lowest precedence on the outside. Adding a new operator means adding one level.
- Reject trailing input.
age > 1 extramust fail. Forgetting the "did we consume everything?" check is the most common hand-written parser bug, and it silently ignores the end of a rule. - Validate field names against a schema at save time. Our parser accepts any identifier. A production version should know the fields that exist (
country,age,plan,status) and their types, and rejectagee >= 18orage == "adult"when the rule is saved. Otherwise a typo makes a rule that silently matches nobody. - Limit size and depth. A rule written by a person is short. Reject inputs longer than a few kilobytes or nested deeper than, say, 50 levels, so a malicious or broken input can't exhaust the stack.
If the grammar grows past a screenful (operator precedence for arithmetic, function calls, lists, string escapes), stop hand-writing and use a parser generator such as ANTLR, or adopt an existing expression language. The pattern's classes stay the same, and only the code that builds them changes.
Missing fields: two-valued or three-valued logic?
Our Compare returns false when the field is missing. That has a subtle consequence with not:
| Facts | status == "banned" | not status == "banned" |
|---|---|---|
status: "banned" | true | false |
status: "ok" | false | true |
no status at all | false | true |
A customer with no status passes not status == "banned". That's probably what you want here, but for not country == "IN" it means a customer with an unknown country counts as "not in India". SQL handles this with three-valued logic, where comparisons with NULL give UNKNOWN and NOT UNKNOWN is still UNKNOWN. You have three choices, and you should pick one deliberately and document it:
- Two-valued, missing means false (what we did). Simple and predictable, with the
notsurprise above. - Three-valued (
TRUE,FALSE,UNKNOWN), wherematchesreturns an enum andNotmapsUNKNOWNtoUNKNOWN. Most faithful, but harder to explain to rule authors. - Missing field is an error, raised at evaluation time, and enforced by validating that every fact the rule references exists. Strictest, and good when the facts come from a fixed schema.
Interviewers like this question because it shows whether you've thought about the semantics of your language, not only its syntax.
Speed: walking the tree versus compiling it
Tree-walking is fast enough for most rule engines: evaluating a 10-node rule is a handful of virtual calls. When you evaluate one rule against millions of records, two well-known techniques help.
Compile to closures. Walk the tree once and produce a nested function. Each node becomes a function that calls its children's functions directly, so the per-record work skips the tree's dispatch and the operator lookups.
type Node =
| { kind: "cmp"; field: string; op: ">=" | "=="; value: number | string }
| { kind: "and" | "or"; left: Node; right: Node }
| { kind: "not"; inner: Node };
type Pred = (facts: Record<string, unknown>) => boolean;
function compile(n: Node): Pred {
switch (n.kind) {
case "cmp": {
const { field, op, value } = n; // resolved once, at compile time
return op === "=="
? (f) => f[field] === value
: (f) => typeof f[field] === typeof value && (f[field] as number | string) >= value;
}
case "and": { const l = compile(n.left), r = compile(n.right); return (f) => l(f) && r(f); }
case "or": { const l = compile(n.left), r = compile(n.right); return (f) => l(f) || r(f); }
case "not": { const i = compile(n.inner); return (f) => !i(f); }
}
}
const rule: Node = {
kind: "and",
left: { kind: "cmp", field: "country", op: "==", value: "IN" },
right: { kind: "not", inner: { kind: "cmp", field: "age", op: ">=", value: 65 } },
};
const pred = compile(rule);
const people = [{ country: "IN", age: 30 }, { country: "IN", age: 70 }, { country: "US", age: 30 }];
const hits = people.filter(pred);
if (hits.length !== 1 || hits[0]!.age !== 30) throw new Error("compile() gave the wrong answer");
console.log("compiled predicate matched", hits.length);
Translate to the database. If the facts live in a table, turn the tree into a SQL WHERE clause with bound parameters and let the database's indexes do the work. That's the bridge between Interpreter and the Specification pattern's query translation. Bigger engines go further and compile to bytecode: SQLite, for example, compiles each SQL statement into a program for its own virtual machine rather than walking a tree.
Adding a second operation
Real rule languages soon need more than evaluation: "explain why this customer didn't qualify", "list the fields this rule uses", "render the rule in plain English". With Interpreter as written, each new operation is a new method on every expression class. That's fine with four classes. Beyond that, move operations into Visitors, or use sealed types with pattern matching, and keep the expression classes as plain data.
Real-world uses
- Regular expressions.
java.util.regex.Pattern.compileparses the pattern text into an internal tree of node objects, andMatcherruns the input through that tree. It's a textbook interpreter of a small language, with a compilation step in front. - Spring Expression Language (SpEL). Used in
@Value("#{...}")and Spring Security's@PreAuthorize("hasRole('ADMIN')").SpelExpressionParserbuilds an AST of node objects that is then evaluated against a context. - Common Expression Language (CEL). Google's small, deliberately non-Turing-complete expression language, used for Kubernetes validation rules (
x-kubernetes-validationson custom resources, andValidatingAdmissionPolicy) and for Google Cloud IAM conditions. It exists precisely so that user-written rules can be evaluated safely and in bounded time. - Rule engines and query filters. Business rule engines such as Drools, the JsonLogic format (rules written as JSON trees), and the filter syntax of many search and logging products all parse user text or JSON into an expression tree and evaluate it per record.
When NOT to use it
- The rules rarely change, or developers own them anyway. A language is a product: it needs documentation, error messages, versioning and support. If rules change twice a year, keep them in code, where the compiler and tests protect you.
- A fixed-shape configuration is enough. If every rule is "country in a list, and minimum age", a form with two fields stored as data beats a language. Only build a language when users need arbitrary combinations of conditions.
- The grammar is large. One class per rule works for a dozen rules. A real programming language, with scopes, functions and types, needs a proper compiler architecture: a parser generator, separate passes, visitors and an intermediate representation.
- An existing expression language fits. CEL, SpEL, JEXL, JsonLogic and SQL
WHEREclauses have years of security review and edge-case fixes. Embedding one is almost always cheaper than inventing a language, unless the point is to keep the language tiny and domain-specific. - Throughput is critical and the tree is evaluated in a hot loop. Tree-walking is slower than compiled code. Compile to closures, translate to SQL, or generate code.
Related patterns
- Composite. The expression tree is a composite:
And,OrandNotare composites,Compareis a leaf, and they share one interface. Interpreter adds the idea that the tree represents sentences of a grammar and that the shared operation means "evaluate". - Visitor. Interpreter puts evaluation on the nodes. Visitor moves operations off the nodes into separate classes. Start with Interpreter, and switch to Visitor when the number of operations grows.
- Specification. A specification is a composable predicate built in code (
inStock().and(priceBelow(50))). An interpreted rule language produces the same kind ofand/or/nottree from text. Many systems have both: users write text, the parser builds specifications. - Strategy. A compiled rule is just a predicate function, so a parsed rule can be handed anywhere a filtering strategy is expected.
The smell that suggests it
- A stream of near-identical "rule" methods.
isEligibleForCampaignX,isEligibleForCampaignYand so on, each a different combination of the same five conditions, each needing a deploy. - Nested JSON conditions with hand-written evaluation. A config file grows
{"all": [{"field": "age", "gte": 18}, {"any": [...]}]}and the code that evaluates it is a pile ofifstatements on keys. That's an untyped interpreter. Give it a proper tree of classes. - Someone proposes
eval. That's the clearest signal that users need to express logic, and that you need a restricted language to let them do it safely.
Interview questions
-
"What are terminal and nonterminal expressions?" Terminal expressions are grammar rules with no sub-rules (literals, variables, a comparison against a field). They evaluate directly against the context. Nonterminal expressions are composed of other expressions (
and,or,not,+) and combine their children's results. -
"Where does the parser fit in the Interpreter pattern?" Strictly, it's outside the pattern, which starts from an already-built tree. In practice you always need one. A recursive-descent parser with one method per grammar level is the standard choice for small languages. Larger grammars justify a parser generator.
-
"How do you encode operator precedence?" One grammar rule per precedence level, with lower-precedence rules containing higher-precedence ones:
orcontainsand, which containsnot. Left-associativity comes from the loop in each level that keeps folding the result into a new node. -
"Why not just call
eval?" It executes arbitrary code in the host language, so a stored rule becomes a remote code execution vulnerability. A restricted language can only express what you allow, and you can bound its running time and validate it at save time. -
"How would you add 'explain why this rule failed'?" Either add an
explain(facts)method to every expression class (fine with four classes), or switch to a visitor so evaluation and explanation are separate operations over the same tree. The explanation forAndreports whichever child failed first; forOr, it reports all children. -
"What happens when a field is missing?" You have to decide. Treating it as false is simple but makes
not field == xtrue for missing data. Three-valued logic (as SQL does withNULL) is more faithful but harder to explain. Rejecting rules that reference unknown fields at save time removes most of the problem. -
"How would you make evaluation faster?" Compile the tree once into nested closures, so each evaluation skips the tree's dispatch and operator lookups. If the data is in a database, translate the tree into a parameterised
WHEREclause and let indexes do the filtering. Order cheap conditions first so short-circuiting saves work. -
"When would you not build your own language?" When an existing one such as CEL, SpEL or JsonLogic fits, when the rules have a fixed shape that a form can capture, or when developers are the only ones who change the rules. Building a language means owning its documentation, error messages, semantics and security.
Further reading
- Behavioral Patterns: the grouped overview of the behavioral family.
- Visitor: adding operations over the tree Interpreter builds.
- Specification: the same
and/or/nottree, built in code and translated to queries. - Composite: the structure underneath every expression tree.
- Pattern Selection Guide: choosing between look-alike patterns.