Interpreter

Purpose

Interpreter says: if you have a small language, give every rule of its grammar a class, and let a sentence in that language be a tree of instances of those classes. Evaluating the sentence is then a recursive walk over the tree, where every node knows how to evaluate itself given a context.

The case for it is narrow and specific. You want it when the same kinds of expression are evaluated over and over, when the grammar is small and stable, and when the expressions themselves must be editable by somebody who cannot rebuild your software. Outside that intersection there is nearly always a better answer, and I will make that argument properly further down.

Design

An AbstractExpression declares one operation, interpret(Context). Terminal expressions are the leaves: a literal, a variable reference, a single comparison. Nonterminal expressions hold child expressions and combine their results, which is what makes them the composite rules of the grammar. The Context carries whatever the evaluation needs that is not in the tree: variable bindings, the input being matched, accumulated output.

The pattern deliberately says nothing about parsing. It assumes you already have the tree, however you built it: from a hand-written recursive descent parser, from a parser generator, or from a client that constructs the nodes directly in code. That omission is significant, because on any real language parsing is most of the work and all of the error messages.

Example

Autobot Robotics' vision system measures features on a finished board and has to decide pass or fail. The criteria are the customer's, not Autobot's: hole diameter within a tolerance, four holes present, no solder bridge, and the tolerance is different for every board they run. In the first release those criteria were C# written by Autobot, compiled into the vision system, and shipped as a release. Changing a tolerance from 0.05 to 0.06 was a release cycle, a regression test and a site visit.

The team gave the customers a tiny rule language instead: comparisons on named measurements, joined by and, or and not, and nothing else. Deliberately nothing else. Every construct in that grammar is a class implementing one evaluate() method, a rule file is parsed once when a board program is loaded, and the resulting tree is evaluated for every board that comes down the line.

The reason this was the right call is the size of the grammar rather than the elegance of the pattern. Eight node types, no variables, no loops, no functions, no user-defined names. The moment anyone asked for a variable the team's answer was going to be to embed a real scripting language and delete all of this, and they said so in writing at the time.

interface Rule
{
    bool evaluate(Reading r);
}

class WithinTolerance : Rule            // terminal
{
    private string feature;
    private double nominal, tolerance;

    public bool evaluate(Reading r) {
        return Math.Abs(r.get(feature) - nominal) <= tolerance;
    }
}

class CountEquals : Rule { }            // terminal, same shape

class And : Rule                        // nonterminal
{
    private Rule left, right;

    public And(Rule l, Rule r) { left = l; right = r; }

    public bool evaluate(Reading r) {
        return left.evaluate(r) && right.evaluate(r);
    }
}

class Or  : Rule { }                    // same shape as And
class Not : Rule { }                    // holds one child Rule

class Client
{
    public void inspect(Reading r) {
        Rule pass = new And(new WithinTolerance("dia", 6.0, 0.05),
                            new CountEquals("holes", 4));

        if (pass.evaluate(r)) {
            // accept the board
        }
    }
}

Seen in the Wild

Java's java.util.regex.Pattern compiles a regular expression into a linked structure of internal Node objects, each of which implements a match method, which is the pattern applied to exactly the example the Gang of Four used. In .NET, System.Linq.Expressions builds a tree of typed node classes for a lambda, and LINQ providers walk that tree, although the in-process case compiles it rather than interpreting it. Spring Expression Language and Apache Commons JEXL are interpreters over small embedded grammars, and most template engines work the same way once the template has been parsed.

Comparisons

• Composite is the underlying structure. Interpreter is a Composite whose tree happens to be a parsed sentence and whose operation happens to be evaluation.
• Visitor is what you reach for when one operation is not enough. Evaluate, pretty-print, type-check and optimize are four operations over the same nodes, and putting all four in every node class is how this pattern rots.
• Flyweight applies to terminals. A tree with ten thousand references to the literal 0 does not need ten thousand objects.
• Iterator is how you traverse the finished tree for anything other than evaluating it.
• Command is the shallow end of the same idea: a request as an object, without a grammar behind it.

Why It Exists

Criticisms

The class count is the standard complaint and it is fair. One class per production rule means the grammar is spread over dozens of files, and the only way to understand the language is to read all of them and reassemble the grammar in your head. Ironically, a one page BNF description would have told you more, and unless somebody maintains that description by hand it does not exist anywhere.

The deeper problem is that evaluation is fused into the node types. As soon as you want a second operation over the tree, every node class grows a second method, and every new node type must remember to implement both. The escape is Visitor, which works but is itself unpleasant, and between them you have now paid for two patterns to do the work a tagged union and a switch statement would do in a language with pattern matching.

Finally, performance. Tree walking with a virtual call per node is roughly an order of magnitude slower than compiled code, and it allocates. That is fine for a rule evaluated once per board and not fine for one evaluated inside a control loop. If you find yourself caching interpretation results to make this pattern viable, the pattern has already told you it is the wrong choice.