Notes
The problem
Here is how it usually starts. A discount method with a growing list of if statements. Total at least fifteen hundred and at least three items gives ten percent. First order, or a big cart, gives fifteen. Every change is a code edit, a review and a deploy, and the method keeps getting longer. The rules are really data that changes often, trapped inside code that should change rarely.
int discount(Cart c) {
if (c.total() >= 1500 && c.items() >= 3)
return 10;
if (c.firstOrder() || c.total() >= 5000)
return 15;
// next week: another if, another deploy
return 0;
} The idea
The idea: define a small grammar for your rules, make one class for each grammar rule, turn a sentence into a tree of those objects, then ask the root of the tree to evaluate itself. The formal version: Interpreter represents a grammar as a class hierarchy, and interprets sentences by walking an expression tree with a shared context. A rule like items at least three and total at least fifteen hundred becomes a tiny tree.
- define a small grammar,
- make one class per rule of
- the grammar, build a tree
- from a sentence, and ask
- the root to evaluate itself
- rule text:
- "items >= 3 and total >= 1500"
The grammar
Here is the whole grammar, just four lines. A rule is one or more and expressions joined by the word or. An and expression is one or more unary parts joined by and. A unary part is either not followed by another unary part, or a comparison. A comparison is a field name, an operator and a number. Because and sits lower in the grammar, it binds tighter than or, just like in Java.
rule := andExpr ( "or" andExpr )* andExpr := unary ( "and" unary )* unary := "not" unary | compare compare := FIELD OP NUMBER FIELD: total, items, firstOrder OP: >= <= > < == and binds tighter than or
Structure
Each grammar rule maps to a class, and all of them implement one Condition interface with a test method. Compare is a terminal expression, a leaf of the tree, because it holds no other conditions. AndRule, OrRule and NotRule are non-terminal expressions: they hold child conditions and combine their answers. Notice this is the Composite pattern underneath. Interpreter is Composite with a grammar on top.
Code: terminal
The Condition interface has one method, test, which takes the context. Compare is a record holding a field name, an operator and a number. Its test method reads the field from the context and applies the operator. The operator is an enum, so only the five known comparisons can exist. There is no string evaluation and no scripting engine. That matters for safety, since rule text may come from a web form.
interface Condition {
boolean test(CartFacts facts);
}
record Compare(String field, Op op,
long value)
implements Condition {
public boolean test(CartFacts f) {
return op.apply(f.get(field), value);
}
} Code: non-terminals
The non-terminals are just as small. AndRule holds a left and a right condition and returns true only when both are true. OrRule returns true when either is. NotRule flips its one child. They do not care whether a child is a leaf or another big subtree. Java's own short circuit rules apply too: if the left side of an and is false, the right side is never evaluated.
record AndRule(Condition l, Condition r)
implements Condition {
public boolean test(CartFacts f) {
return l.test(f) && r.test(f);
}
}
OrRule: l.test(f) || r.test(f)
NotRule: !inner.test(f) The context
The context is the input for one evaluation. Here it is CartFacts, a map from field names to numbers: total, number of items, and first order as one or zero. The tree is built once and reused, while a fresh context comes with every cart. Asking for an unknown field throws a clear error. That keeps a typo in a rule from quietly evaluating to zero and giving everyone a discount.
record CartFacts(Map<String, Long> v) {
long get(String name) {
Long x = v.get(name);
if (x == null) throw new
IllegalArgumentException(
"unknown field " + name);
return x;
}
} Building the tree
Who builds the tree? Strictly, parsing is not part of the pattern, but you need it. With a grammar this small, a recursive descent parser is enough: one method per grammar line. The or method reads an and expression, then while the next word is or, it reads another and wraps both in an OrRule. The other methods follow the same shape. Each rule is parsed once when marketing saves it, so a bad rule is rejected at save time, not at checkout.
Condition orExpr() {
Condition left = andExpr();
while (peek("or")) {
pos++;
left = new OrRule(left, andExpr());
}
return left;
}
// andExpr, unary, compare: same shape A run-through
Let us run one cart through it. The engine calls test on the root, an OrRule. The OrRule asks its left child, an AndRule. The AndRule asks its first comparison, which reads items from the cart facts: three, which is at least three, so true. The second comparison checks the total, also true. The AndRule returns true, so the OrRule can stop without asking its right side. The promotion applies.
Using it
Now promotions are data. Each one is a rule string and a percentage, stored in a table and edited from an admin screen. On startup, or when a rule is saved, the engine parses it once. At checkout it tests every promotion against the cart facts and picks the best match. Adding a campaign is now a row, not a release, and the code you test stays the same.
- "items >= 3 and total >= 1500"
- -> 10% off
- "firstOrder == 1 or
- total >= 5000" -> 15% off
- "not items < 2 and
- total >= 800" -> 5% off
- parse once, store the tree,
- test every cart, best wins
When to use it
Use Interpreter when the language is small, the rules change more often than the code, and you want users to have limited, safe power. Skip it when the grammar is large or keeps growing: one class per rule becomes hard to manage, and a parser generator or an existing expression library is better. Walking a tree of objects is also slower than compiled code, which matters only on very hot paths.
- use it when:
- • the language is small
- • rules change more than code
- • you need safe, limited power
- skip it when:
- • grammar is large or growing
- • speed is critical: compile
- instead of walking a tree
- • a library already fits
Safety
A word on safety. Rule text often comes from a form, so treat it as untrusted. Our design only allows known fields and five operators, so a rule cannot call a method or read a file. Validate rules when they are saved, cap their length and nesting depth, and never hand rule text to a general script engine. A tiny language you control is much safer than a full one you do not.
- • whitelist the fields
- • enum for operators
- • validate when the rule is
- saved, not at checkout
- • limit rule length and depth
- • never pass rule text to a
- script engine or eval
Where you see it
You meet this idea often. Java's regex Pattern class compiles a regular expression into an internal tree of node objects and then runs that tree against your text. Expression languages in popular frameworks parse a string into a tree of nodes and evaluate it against a context. Feature flag targeting, alert rules and search filters all follow the same plan: small grammar, tree of objects, evaluate with a context.
- java.util.regex.Pattern:
- compiles a regex into an
- internal tree of match nodes
- expression languages in
- frameworks parse text into
- node trees they evaluate
- search filters, feature flag
- targeting, alert rules
Related patterns
How does it relate to its neighbours? Composite is the shape: a tree where groups and leaves share one interface. Interpreter is a Composite whose nodes follow a grammar and know how to evaluate themselves. If you later need many operations on the same tree, like pretty printing, optimising or validating, you add a Visitor rather than a new method on every node class.
- Composite: a tree where a
- group and a leaf share
- one interface
- Interpreter: a Composite
- whose nodes follow a grammar
- and evaluate themselves
- Visitor: add print, optimise
- or check to the same tree
In LLD interviews
In interviews this fits coupon and discount engines, access rules based on role and time, alert conditions in a monitoring tool, and workflow conditions. Common mistakes are evaluating user text as code, skipping validation until checkout, and writing one giant class that switches on token types instead of one small class per grammar rule. Keep the grammar tiny and say why.
- coupon and discount engine
- access rules: role and time
- alerting: cpu > 90 for 5m
- workflow conditions
- common mistakes:
- • eval() on user text
- • no validation at save time
- • one giant class with a
- switch on token type