Interpreter: a small language of your own

  • Lesson 28 of 32
  • 11 min
  • Intermediate
  • 13 steps

A rule like «country MX and (age ≥ 18 or plan pro)» copied into three files. You will turn it into a tree of objects that evaluates itself, and see when an existing language is the better call.

Copies of the rule
—
Result
true
checkout.tscheckout.tsMX · 16 · prorules.jsonAndAnd · true&&PatternAnd · truecountry =MXcountry ·truefailure()country · trueOrOr · true== 'push'Or · trueage ≥ 18age ·falseage · falseplan = proplan ·trueplan · trueRuleinterfaceRuleEqEqAndAndOrOrthe rule lives in the codecheckout.tsconst promo =▸u.country === "MX" &&▸(u.age >= 18 || u.plan === "pro");if (promo) showPromo();checkout · banner · emailWhere the rule livescheckout.tsage >= 18banner.tsage >= 18email.tsage >= 18change to 21: 3 filesroot: AndOr inside AndThe sentence as a treeAndcountry = "MX"Orage ≥ 18plan = "pro"leaves: Eq, Gtecomposites: And, OrOne contract, four classestype Ctx = Record<string, unknown>;interface Rule {▸evaluate(ctx: Ctx): boolean;}class Eq implements Rule { … }class Gte implements Rule { … }class And implements Rule { … }class Or implements Rule { … }c.country === "MX"c.age >= 18A leafclass Eq implements Rule {constructor(private key: string,private value: unknown) {}evaluate(c: Ctx) {▸return c[this.key] === this.value;}}asks its 2 childrenthe same, with ||A compositeclass And implements Rule {constructor(private a: Rule,private b: Rule) {}evaluate(c: Ctx) {▸return this.a.evaluate(c)▸&& this.b.evaluate(c);}}evaluate(user)16 < 18rule.evaluate(user)Andtruecountry = "MX"trueOrtrueage ≥ 18falseplan = "pro"trueuser = { MX, 16, pro }, example valuesthe rule as databuild(json) makes the treerules.json{ "and": [{ "eq": ["country", "MX"] },{ "or": [{ "gte": ["age", 18] },{ "eq": ["plan", "pro"] }]}] }text → tree: another jobonly does what you definedThree wrong ideas«it is a programming language»usually, just a rule«it includes the parser»starts from the tree«it is like eval()»only your nodesGitHub evaluates the sentence.github/workflows/ci.yml- name: Notify the team▸if: ${{ failure() &&▸github.event_name == 'push' }}run: ./notify.shcompiled oncestate of each matchLanguages that already exist// Java: regex → Pattern▸Pattern p = Pattern.compile("a*b");Matcher m = p.matcher("aaaaab");boolean b = m.matches(); // true-- SQLite: SQL → bytecodeEXPLAIN SELECT * FROM users;one class per ruleWhen not to use ita language existsregex, SQL, JSON Schemalarge grammarone class per rulehot loopwalking the tree costsmany operationsevaluate with a Visitorone tree, one evaluate()Interpreter in a tableproblema rule copied into the codesolutionone class per rule, a treeleavescompare one valuecompositesask their childrenskip itwhen a language exists
  • request
  • response
  • event

Step 1 of 13

Problem

A business rule written by hand

Your shop shows a promo to anyone who matches this: lives in Mexico and is an adult or has the pro plan. In checkout.ts you wrote it as one expression with && and ||.

It works. But that rule is not your app's code: it is a business decision marketing will want to change, and it is buried between calls and variables.

Step 2 of 13

Problem

The same rule, in three files

The promo also shows up in the banner and in an email, so the rule is copied into banner.ts and email.ts. Three copies in this example.

Marketing asks to raise the minimum age to 21. You open all three files, change the number and deploy. Forget one and the banner promises a promo the checkout will not let you use.

What changed

  • age >= 18 → age >= 21, three times

Step 3 of 13

Concept

The rule is a sentence in a small language

Read the rule as a sentence: country = "MX" And (age ≥ 18 Or plan = "pro"). It uses words from a tiny vocabulary: comparisons, And and Or.

Any sentence like this can be drawn as a tree: And on top, with two children; one of them is an Or, which has two children of its own. The comparisons are the leaves.

Step 4 of 13

Concept

One class per grammar rule

The idea of Interpreter: each kind of word in the language is a class, and they all keep the same contract, Rule, with a single method: evaluate(ctx), which answers true or false.

Eq and Gte are leaves: they compare one value. And and Or are composites: they hold other rules. It is the same tree you saw in Composite, now with a concrete job.

What changed

  • interface Rule
  • Eq, Gte, And, Or

Step 5 of 13

Technique

Leaves compare one value from the context

Eq stores a key and a value. Its evaluate looks that key up in the context (the user's data) and compares: c["country"] === "MX".

Gte is the same with >=: Number(c[this.key]) >= this.min. No leaf knows And or Or exist; each one only answers its own question.

Step 6 of 13

Solution

And and Or ask their children

And stores two Rules without knowing their type. Its evaluate calls evaluate on each child and combines them with &&. Or does the same with ||.

Since a child can be another And or Or, the sentence can nest as deep as you like and nobody writes a traversal: the recursion comes for free.

What changed

  • And.evaluate: a && b
  • Or.evaluate: a || b

Step 7 of 13

Technique

A context goes in, a true comes out

You call rule.evaluate(user) with the user { country: "MX", age: 16, plan: "pro" }. And asks country: true. Then it asks Or, which asks age: false, because 16 < 18. So Or asks plan: true.

Or answers true, and And answers true: promo shown. Questions go down and answers come back up, just like && and ||: if country were false, And would not even ask Or.

Step 8 of 13

Solution

The rule lives in a file, not in the code

Now the rule can be data: a JSON with and, or, eq and gte. A build(json) function walks it and creates the tree of objects, calling itself on every and and or.

All three files call rule.evaluate(user) on the same tree: a single copy. Raising the age to 21 is changing one number in rules.json, and if the app reads that file at startup or from a remote config, you do not even need to deploy.

What changed

  • rules.json
  • build(json): Rule
  • three copies of the rule

Step 9 of 13

Concept

Three wrong ideas about Interpreter

«It means writing a programming language.» Hardly ever: the usual case is a filter or a rule with four or five node types. «It includes reading text.» In this lesson we start from a tree or from JSON; turning text such as age >= 18 into a tree is another job, a parser's.

«It is the same as eval().» No: eval runs any code it receives. Your tree can only do what Eq, Gte, And and Or do. That is why accepting outside rules as data is safer than accepting them as code.

Step 10 of 13

Technique

The GitHub Actions if is a small language

In a GitHub Actions workflow, if: takes an expression between ${{ and }} with literals, comparisons such as ==, the && and || operators, and functions such as failure() or contains().

This step notifies the team only if something failed and the event was a push. GitHub evaluates that sentence with the workflow's context, like your rule.evaluate(user). Every if: you write in your CI is a sentence in that language.

Step 11 of 13

Technique

Regex and SQL: languages you do not have to write

Regular expressions are the classic example. In Java, Pattern.compile("a*b") turns the text into a Pattern; the state of each match lives in a Matcher, so many Matchers can share one Pattern.

SQLite goes further: it compiles each SQL statement into a bytecode program that its virtual machine runs, and EXPLAIN lets you see it. Big engines do not walk a tree of objects on every run.

Step 12 of 13

Trade-off

When your own language is too much

Skip it when a language or library already fits, or when the grammar is large: with one class per rule the classes pile up fast, and you have to build the error messages and tooling yourself. Walking the tree in a hot loop costs too.

And if you ask the tree for many things (evaluate, print, validate), do not cram them all into the nodes. Robert Nystrom, in *Crafting Interpreters*, says the Gang of Four style «gets messy» when you fill the tree classes with logic, and evaluates with a Visitor instead.

Step 13 of 13

Summary

One rule, one tree, one evaluate()

When a business rule repeats and changes often, treat it as a sentence: one class per kind of word, all with evaluate(ctx), and a tree built from data.

Leaves compare and composites ask their children. If a language that fits already exists, such as regex, SQL or your CI's expressions, use it instead of writing your own.

You will learn

  • Recognise when a business rule is really a sentence in a small language.
  • Represent each grammar rule with a class that implements `evaluate()`.
  • Evaluate the tree with a context and follow how questions go down and answers come back up.
  • Store the rule as data (JSON) and build the tree from it.
  • Know when to use an existing language or library instead of writing your own.