Interpreter — heyrian.dev

Definition

An interpreter represents the grammar of a small language as one type per rule and interprets a sentence by asking each part of its tree for its meaning in a context.

After Gamma et al., Design Patterns (1994), Interpreter

01When a rule becomes data

A fixed filter can stay a function.

For one fixed support view, a predicate is simple: inspect a ticket and return a boolean. The rule lives in code, which is a good fit while the product asks the same question every time (a fragment: the ticket’s type is the one the next section’s program defines):

filter.ts

// The help desk's attention view, written as a function: open, and either
// urgent or assigned to whoever is looking.
function needsAttention(ticket: Ticket, viewer: string): boolean {
  return (
    ticket.status === 'open' &&
    (ticket.priority === 'urgent' || ticket.assignee === viewer)
  );
}

Now people can save nested groups of conditions. One might ask for open tickets that are urgent or theirs; another might group the conditions differently. Writing a new function for every combination would make each saved view a code change.

Interpreter represents a small language as expressions and gives each expression a rule for answering in context. An atom reads a fact. A compound expression asks its children for answers and combines them. The saved tree is the question; the current ticket and viewer supply the facts.

02Give each expression a meaning

Grouping changes the question.

In open AND (urgent OR mine), open must be true, then urgent or mine may be true. Move the grouping to (open AND urgent) OR mine, and mine becomes an alternative to the entire first group. A closed ticket assigned to Maya now matches.

The filter language and the result of one evaluation
Expression	Meaning
open · urgent	Read the ticket and return true or false.
mine	Compare the assignee with the supplied viewer. No assignee is false; no viewer is an error if mine is reached.
left AND right	Read left first. False decides the result; true requires right. An error propagates.
left OR right	Read left first. True decides the result; false requires right. An error propagates.
NOT expression	Negate a boolean and preserve an error.

Each node is an expression in a recursive tree. The editor builds that structure; the interpreter supplies its meaning. The same tree can answer for Maya, then Rian, because the current ticket and viewer arrive with each evaluation. This is the whole program the lab runs: the forms, the search that uses them, and one saved view answered for two viewers.

filter.ts

// A help-desk ticket, and what one evaluation reads: the ticket and who is
// looking (null until the viewer's sign-in has finished).
type Ticket = {
  id: string;
  status: 'open' | 'closed';
  priority: 'urgent' | 'normal';
  assignee: string | null;
};
type Context = { ticket: Ticket; viewer: string | null };
type Result = { ok: true; value: boolean } | { ok: false; error: string };

// Every expression in the filter language answers for itself in a context.
interface Expression {
  interpret(context: Context): Result;
}

// An atom reads one fact about the ticket or the viewer.
class Atom implements Expression {
  name: 'open' | 'urgent' | 'mine';
  constructor(name: 'open' | 'urgent' | 'mine') {
    this.name = name;
  }
  interpret({ ticket, viewer }: Context): Result {
    if (this.name === 'open') {
      return { ok: true, value: ticket.status === 'open' };
    }
    if (this.name === 'urgent') {
      return { ok: true, value: ticket.priority === 'urgent' };
    }
    if (viewer === null) return { ok: false, error: 'missing-viewer' };
    return { ok: true, value: ticket.assignee === viewer };
  }
}

// AND reads its left side first; only a true left needs the right side.
class And implements Expression {
  left: Expression;
  right: Expression;
  constructor(left: Expression, right: Expression) {
    this.left = left;
    this.right = right;
  }
  interpret(context: Context): Result {
    const left = this.left.interpret(context);
    if (!left.ok || !left.value) return left;
    return this.right.interpret(context);
  }
}

// OR reads its left side first; only a false left needs the right side.
class Or implements Expression {
  left: Expression;
  right: Expression;
  constructor(left: Expression, right: Expression) {
    this.left = left;
    this.right = right;
  }
  interpret(context: Context): Result {
    const left = this.left.interpret(context);
    if (!left.ok || left.value) return left;
    return this.right.interpret(context);
  }
}

// NOT negates an answer and passes an error on unchanged.
class Not implements Expression {
  child: Expression;
  constructor(child: Expression) {
    this.child = child;
  }
  interpret(context: Context): Result {
    const child = this.child.interpret(context);
    return child.ok ? { ok: true, value: !child.value } : child;
  }
}

// The saved view's caller: the matching IDs in order, or the first failure,
// never a partial list.
function search(
  rule: Expression,
  tickets: Ticket[],
  viewer: string | null,
): string {
  const ids: string[] = [];
  for (const ticket of tickets) {
    const result = rule.interpret({ ticket, viewer });
    if (!result.ok) return `error ${result.error} at ${ticket.id}`;
    if (result.value) ids.push(ticket.id);
  }
  return ids.join(', ') || '(none)';
}

const tickets: Ticket[] = [
  { id: 'T-101', status: 'open', priority: 'urgent', assignee: 'rian' },
  { id: 'T-102', status: 'open', priority: 'normal', assignee: 'maya' },
  { id: 'T-103', status: 'closed', priority: 'normal', assignee: 'maya' },
];

// open AND (urgent OR mine): saved once, answered for each viewer.
const saved = new And(
  new Atom('open'),
  new Or(new Atom('urgent'), new Atom('mine')),
);
const forMaya = search(saved, tickets, 'maya');
const forRian = search(saved, tickets, 'rian');
console.log('maya: ' + forMaya);
console.log('rian: ' + forRian);

Who owns what
Role	Responsibility	What it handles
Expression (each form)	Owns one rule’s meaning.	An atom reads a fact; AND, OR and NOT ask their children and combine the answers, in order. Each has its own interpret.
The saved tree	Is the question.	Built once from what the person saved, and kept. It holds its children, never a ticket, a viewer or a previous answer.
Context	Supplies this evaluation’s facts.	A fresh ticket and viewer for every call, so one tree answers for Maya, then for Rian.
The caller	Decides what results mean.	search keeps matches in order and stops at the first error rather than show a partial list. That policy belongs to this application, not to the language.

What a production interpreter addsA trace, a checked builder, a typed search result

The same forms with a contract. Every evaluation gets a fresh trace: each node records its path (root, .L, .R, .N), its kind and its outcome as it returns, so children appear before their parents and a skipped node has no entry. The interpret method takes the trace and the path as well as the context; that is the only change to its shape.

fromSpec builds the tree from the authored structure and throws unsupported authored expression on an unknown kind before anything is evaluated: a branch that short-circuiting would skip is still checked. The search returns a SearchResult union naming the ticket that failed.

Still the loader’s job, and not shown: checking a saved rule’s version, size and depth before evaluation. Recursion follows depth, so an unbounded tree can exhaust the stack.

filter.ts

export class Or implements Expression {
	readonly left: Expression;
	readonly right: Expression;
	constructor(left: Expression, right: Expression) {
		this.left = left;
		this.right = right;
	}
	interpret(context: Context, trace: Step[], path: string): Result {
		const left = this.left.interpret(context, trace, path + '.L');
		const result =
			!left.ok || left.value ? left : this.right.interpret(context, trace, path + '.R');
		return record(trace, path, 'or', result);
	}
}
export class Not implements Expression {
	readonly child: Expression;
	constructor(child: Expression) {
		this.child = child;
	}
	interpret(context: Context, trace: Step[], path: string): Result {
		const child = this.child.interpret(context, trace, path + '.N');
		return record(trace, path, 'not', child.ok ? value(!child.value) : child);
	}
}
// A typed builder produces this structure. This is not a validator for outside JSON.
export type RuleSpec =
	| { kind: AtomName }
	| { kind: 'and' | 'or'; left: RuleSpec; right: RuleSpec }
	| { kind: 'not'; child: RuleSpec };
export function fromSpec(spec: RuleSpec): Expression {
	switch (spec.kind) {
		case 'open':
		case 'urgent':
		case 'mine':
			return new Atom(spec.kind);
		case 'and':
			return new And(fromSpec(spec.left), fromSpec(spec.right));
		case 'or':
			return new Or(fromSpec(spec.left), fromSpec(spec.right));
		case 'not':
			return new Not(fromSpec(spec.child));
		default:
			throw new Error('unsupported authored expression');
	}
}
export function evaluate(expression: Expression, context: Context): Report {
	const trace: Step[] = [];
	return { result: expression.interpret(context, trace, 'root'), trace };
}
export type SearchResult =
	{ ok: true; ids: string[] } | { ok: false; ticket: string; error: EvaluationError };
export function search(
	expression: Expression,
	tickets: readonly Ticket[],
	viewer: string | null
): SearchResult {
	const ids: string[] = [];
	for (const ticket of tickets) {
		const { result } = evaluate(expression, { ticket, viewer });
		// The saved-view service aborts rather than publishing a partial filtered list.
		if (!result.ok) return { ok: false, ticket: ticket.id, error: result.error };
		if (result.value) ids.push(ticket.id);
	}
	return { ok: true, ids };
}

03Predict a missing viewer

Rian’s view loads before his sign-in does.

Experiment

One saved view, two viewers

filter.ts

const forRian = search(saved, tickets, null);

Step through it in the lab

Reading the TypeScriptClasses behind one interface, a result union

Expression is the shared operation, and each form is a class that implements it. An And stores two expressions, which may themselves be atoms or compound nodes. The fields are ordinary fields set in the constructor rather than parameter properties, so the file also runs under Node’s type stripping.

Result keeps an evaluation error separate from a boolean, so an error cannot quietly become false, and nothing is thrown for a fact that is missing: the caller reads ok and decides. Returning left unchanged hands its answer, or its error, straight to the parent.

04Meet it in your language

You already write rules that something else interprets.

A regular expression is a small language, and RegExp is its interpreter: the pattern is compiled once and asked about each string. The bug readers meet is a saved search that is not stateless. With the g flag, test remembers where its last match ended in lastIndex and starts the next string from there, so filtering subjects with one compiled search skips every other match.

That is a rule keeping one evaluation’s state for the next, the thing the lesson’s tree must not do. test needs no position to remember, so the fix is to drop g (keep it for matchAll or replace, which use it).

search.ts

const subjects = [
  'Refund not received',
  'Refund for order 1182',
  'Login fails after reset',
];

// Before: the saved search, compiled once with the g flag.
const careless = new RegExp('refund', 'gi');
const before = subjects.filter((subject) => careless.test(subject));
console.log(before); // [ 'Refund not received' ]

// After: test needs no position to remember, so no g.
const saved = new RegExp('refund', 'i');
const after = subjects.filter((subject) => saved.test(subject));
console.log(after); // [ 'Refund not received', 'Refund for order 1182' ]

Whatever the language, a rule that is asked many questions should carry nothing from one answer to the next; the facts arrive with each question.

05Choose how much language

Keep the language as small as the product allows.

A fixed predicate is easier to read while every caller asks one question. A short menu of complete policies fits Strategy when callers only select among those choices. Interpreter earns its vocabulary and validation cost when people need to compose, save, explain, or reuse nested rules.

What changes when another requirement arrives?
Change	Fixed predicate	Expression tree	Cost to keep
A person saves a new grouping	Write and deploy another function.	Save another tree; no code changes.	Saved trees must be validated when loaded.
Add a condition (overdue)	Edit the functions that need it.	Add one form with its meaning, its validation and its place in the editor.	Every language and every stored version must agree on it.
Explain why a ticket matched	Add logging inside the function.	Record each node’s result as it returns (the production trace).	A skipped node has no entry, and that must be read as “not needed”.
Filter millions of rows	Write the query by hand.	Compile the tree to the database’s own predicates instead of interpreting each row.	The compiler must keep the grouping and the missing-viewer policy.

The pattern leaves several decisions open. What a missing fact means is yours: this language returns an error and the search stops, while CSS container queries treat an unknown condition as unknown and SQL has its own three-valued logic. A real saved-rule loader must check the vocabulary, child count, value types, version, and size/depth before evaluation; a skipped branch may still contain an invalid rule. And a saved filter is not access control: only records the viewer may already read should reach it.

What belongs where: a form’s meaning belongs to the form, facts belong to the context and arrive fresh with every evaluation, and what a result means for the product (stop, retry, show nothing) belongs to the caller. The tree holds its children and nothing else.

Start with the question your product needs to store. If it grows into a substantial language, compare an established engine’s syntax, type system, limits, and embedding contract before adding more forms here. The Common Expression Language documentation separates parsing, checking, and evaluation, and an application can prepare an expression, then evaluate it with different bindings: the same rule-and-context split, with a larger syntax and type-checking contract. JsonLogic is another documented rule/data API; its operator vocabulary and value semantics differ from this example.

Its neighbours: Composite is the recursive shape that lets groups and single conditions share one interface; Interpreter gives that tree a language’s meaning. Visitor keeps operations outside the node types, for a tree that needs many operations; each expression here interprets itself. Strategy lets the caller choose one complete policy rather than compose one. And Command turns one request into an object, where an interpreter turns a sentence of requests into a tree.

06Make the call

Rule, context, or caller?

Before you open the answer below, try saying it without the pattern name: what does the saved rule hold, what must each evaluation receive from its caller, and what happens when you add a condition?

One way to say itThe question, the facts, and who decides

The saved tree is the question and holds only its structure; each form knows how to answer in a context, and compound forms ask their children in order, stopping when the answer is decided. Every evaluation gets fresh facts, the ticket and the viewer, so one tree answers for anyone, and no answer from one run leaks into the next. A fact that is missing when a form needs it is an error, not false: false is an answer, and NOT would turn it into true. A skipped branch has no result and proves nothing, including that it is valid, so validation happens when the rule is loaded. The caller decides what an error means for the product. Adding a condition means one new form with its meaning, its validation and its place in the editor, in every language that runs the rule. And while nobody composes rules, a predicate says the same thing in one place.

Practice in the lab

A feature-flag service stores each flag’s targeting rule as an expression tree, as the lesson’s help desk stores a saved view, and interprets it for every request against that request’s user: their plan, whether they joined the beta, and the country the geo lookup found, which can be unknown. Each level starts from the previous level’s finished code, so you can begin at any of them.

INTERPRETER-101 (easy) The Brazil launch turns on in Germany
INTERPRETER-102 (medium) Flags that require another flag are never on Pro
INTERPRETER-103 (hard) Review: the second user gets the first user’s answer Pro