Interpreter pattern explained with examples

Intent and the problem it solves

Intent: given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language. Interpreter is one of the behavioral patterns in the Gang of Four (GoF) book.

Suppose users of a pricing system want to write their own discount rules, such as price * 0.9 or price - 5, and the rules must be stored in a database and evaluated later. Hard-coding each rule is impossible, because users create new ones all the time. You need a small language and a way to evaluate it.

The Interpreter pattern gives you a simple design for that evaluation step. Numbers, variables and operators each become a class. A rule like price * 0.9 becomes a tree: a multiply node with a variable node and a number node as children. To compute the result, you call interpret on the multiply node with a context that holds the current price.

Structure and participants

The grammar for the example below, written in a simple notation:

expression ::= number | variable | expression op expression
op         ::= "+" | "-" | "*" | "/"

TypeScript implementation

Each grammar rule is a class implementing Expression. The parse function turns a space-separated expression in postfix notation (operators after their operands) into a tree, which keeps the parser short.

type Context = Record<string, number>;
interface Expression {
  interpret(ctx: Context): number;
}
class Num implements Expression {
  constructor(private value: number) {}
  interpret() { return this.value; }
}
class Var implements Expression {
  constructor(private name: string) {}
  interpret(ctx: Context) {
    if (!Object.hasOwn(ctx, this.name)) throw new Error("Unknown variable " + this.name);
    return ctx[this.name];
  }
}
const ops = { "+": (a: number, b: number) => a + b, "-": (a: number, b: number) => a - b,
  "*": (a: number, b: number) => a * b, "/": (a: number, b: number) => a / b };
class BinaryOp implements Expression {
  constructor(private op: keyof typeof ops, private left: Expression, private right: Expression) {}
  interpret(ctx: Context) { return ops[this.op](this.left.interpret(ctx), this.right.interpret(ctx)); }
}
function parse(source: string): Expression {
  const stack: Expression[] = [];
  for (const token of source.trim().split(/\s+/)) {
    if (Object.hasOwn(ops, token)) {
      const right = stack.pop()!, left = stack.pop()!;
      stack.push(new BinaryOp(token as keyof typeof ops, left, right));
    } else if (!isNaN(Number(token))) stack.push(new Num(Number(token)));
    else stack.push(new Var(token));
  }
  return stack[0];
}
const rule = parse("price 0.9 * 5 -"); // (price * 0.9) - 5
console.log(rule.interpret({ price: 100 })); // 85
console.log(rule.interpret({ price: 40 })); // 31

The tree for price 0.9 * 5 - is a minus node whose left child is a multiply node (with price and 0.9) and whose right child is the number 5. Once parsed, the same tree can be evaluated many times with different contexts.

When to use it and when not to

• Use it when the language is small and the grammar is simple: search filters, feature-flag rules, permission expressions, unit conversions or spreadsheet-style formulas.
• Use it when the same expression is evaluated many times with different data, so building the tree once pays off.
• Do not use it for large languages. One class per rule becomes hard to maintain; use a parser generator or an existing embedded language instead.
• Do not use it when performance is critical. Walking an object tree is slower than compiling to bytecode or machine code.
• Never solve the problem with eval on user input. A small interpreter only supports the operations you define, which is much safer.

To add new operations over the same tree, such as pretty-printing or type checking, combine Interpreter with Visitor instead of adding more methods to every node class.

Real-world uses

• Regular expression engines compile a pattern into a tree or graph of node objects; matching walks these nodes, which is the Interpreter idea applied to the regex grammar.
• Language tools represent source code as an abstract syntax tree: Python's ast module and the ESTree specification used by JavaScript tools such as Babel and ESLint describe node types for every grammar rule.
• SQL databases parse a WHERE clause into an expression tree and evaluate it for each row.
• Template engines and rule engines evaluate small expressions inside templates or business rules.

Related patterns