Interpreter Pattern

Represent each rule of a small grammar as a class, build sentences as a tree of those objects, and evaluate the tree against a context.

Overview

The problem: rules that change faster than the code

A product team wants to switch a feature on for some users only: people in the US on the pro plan, or adults anywhere, but never beta testers. Next week the rule changes. If every rule is an if statement in the code, each change is a code review and a deploy. If the rule is a string run through Python's eval(), anyone who can edit the rule can run any code on your server; the Python docs warn that eval() with untrusted input leads to security vulnerabilities.

The middle path is a small language of your own. Rules are stored as text, such as country == 'US' and (plan == 'pro' or age >= 21) and not beta, and the program understands exactly that grammar and nothing more.

Hard-coded if statements — Code change and deploy — Low, but slow to change
eval() on a stored string — Edit the string — Any Python code can run
A small rule language (Interpreter) — Edit the string — Only what the grammar allows

The pattern

Interpreter is one of the 23 patterns in the 1994 Gang of Four book (Gamma, Helm, Johnson and Vlissides), and it is a behavioral pattern. The idea in one sentence: give each rule of a small grammar its own class, build a sentence of the language as a tree of those objects, and evaluate the sentence by asking the root of the tree to interpret itself.

There are four parts.

Abstract expression: the shared interface, one method interpret(context).
Terminal expressions: leaves of the tree that need no children, such as a literal 21 or a variable age.
Nonterminal expressions: one class per grammar rule that combines smaller expressions, such as And, Or, Not and Compare. Each holds its children and interprets them first.
Context: the outside information the sentence is evaluated against. For a feature flag rule, that is the user's attributes.

The pattern itself says nothing about how the tree gets built. In practice a tokenizer and a parser build it from text, and that part is usually most of the code.

From text to tree

The tokenizer cuts the text into tokens (names, numbers, strings, operators). The parser reads the tokens and builds the tree, following the grammar. A common way to write the parser by hand is recursive descent: one function per grammar rule, where the rule with the lowest precedence (or) calls the next one (and), and so on down to single values. Precedence then falls out of the call order.

Here is the tree the parser builds for the example rule. Because and binds tighter than or, the parentheses are needed to group the plan check with the age check.

The plan and age comparisons have their own two leaves each, left out of the picture to keep it readable.

A runnable example

A complete rule language in one file: the expression classes, a context, a tokenizer, a recursive descent parser, and asserts that cover a match, two misses, a syntax error and an unknown attribute.

The expression classes are about 40 lines; the tokenizer and parser are the rest. That ratio is normal, and it is why the pattern is only worth it when the grammar is small.

Composite and Visitor

The expression tree is a Composite: leaves and containers share one interface, and a container's method calls the same method on its children. Interpreter is Composite with a grammar behind it and one fixed operation, interpret.

Composite — The shape of the tree: And holds expressions, Literal holds none, both are an Expr
Interpreter — What the tree means: each class evaluates its own grammar rule
Visitor — A way to add more operations (print, list variables, type check, optimize) without adding a method to every node class

The first operation lives on the nodes. Once you need a second and a third, such as printing a rule back as text or listing the attributes it reads, move them out into visitors or match functions, as the Visitor Pattern topic shows; otherwise every new operation touches every node class.

When it fits, and when it does not

Interpreter fits a grammar that is small (a dozen rules or fewer) and stable, read by people who are not programmers, and evaluated many times.

Feature flag targeting rules — A full programming language: use an existing one
Rule engines with a few operators (pricing, routing, alerts) — A grammar of dozens of rules or one that changes often: a parser generator such as ANTLR or Lark
Search query syntax like status:open and assignee:me — Filters, policies and validation where a ready-made safe language exists, such as CEL
Filters in a config file or an admin screen — Hot paths over millions of records: compile the rule or push it into the database query

CEL (Common Expression Language) is worth knowing by name: its site describes it as non-Turing complete, able to read only the data the host application provides, and aimed at list filters, validation constraints and authorization rules. A team that needs a rule language rarely has to write one.

Performance

A tree-walking interpreter does a method call per node per evaluation, so it is slower than the same logic written in code. It is usually fast enough for rules, and the main costs are easy to avoid.

Parsing the text on every request — Parse once when the rule is saved, cache the tree
Evaluating every branch — Short-circuit and / or, as Python's own operators do; put cheap checks first
Method dispatch and attribute lookups at every node — Compile the tree once into nested closures, or into a database query
Very deep nesting — A recursive interpreter hits Python's recursion limit and raises RecursionError; cap rule depth and length

What you will be able to do

Explain Interpreter in one sentence and name its four parts: abstract expression, terminal, nonterminal, context.
Write a tokenizer, a recursive descent parser and an expression tree for a small boolean rule language.
Place Interpreter next to Composite (the tree) and Visitor (more operations on the tree).
Say when a hand-written interpreter is right and when to reach for a parser generator or an existing expression language.
Name the performance and safety limits of a tree-walking interpreter and how to handle them.

Interview questions

Show the smell Interpreter fixes, and the fix.
How does Interpreter relate to Composite and Visitor?
When should you not write your own interpreter?
How do you make a rule interpreter fast?
How do you keep a user-editable rule language safe?