On Composite and Interpreter Design Patterns

I often see references to the

interpreter

design pattern in articles related to programming language design. this short article is here to help me remember what this model reference generally means, as well as documenting its relationship to the

composite

pattern design.

the short wikipedia definition of the interpreter design pattern is:

given a language, define a representation for its grammar with an interpreter that uses the representation to interpret sentences in the language.

on the page dedicated to the boss, it is also written:

the syntax tree of a sentence in the language is an instance of the composite model and is used to evaluate (interpret) the sentence for a client.

as a compiler hacker, this all sounds very familiar. indeed, if you’ve ever written an interpreter or compiler for even a simple programming language or domain-specific language, you’ve almost certainly used both the interpreter and the composite patterns.

suppose we have a very simple language for evaluating mathematical expressions and we want to write an interpreter for it. Using the classic compiler workflow, we’ll tokenize the language, parse it to produce a syntax tree, and then either interpret that tree directly or compile it down to a lower-level representation. for the purposes of this article, we will assume:

  1. direct evaluation (interpretation) on the tree is used. a compiler would use the exact same pattern, except it would emit some sort of code instead of direct results.

  2. we don’t care how the tree is constructed, i.e. the syntax of the language. The sample code in this article starts with the syntax tree built in memory and focuses on how it is represented and interpreted.

With that in mind, here’s a simple c++ program that represents expressions and evaluates them. I’ll show the code step by step to explain what it does; the full sample code is available here.

we’ll start with an abstract interface called expr that all syntax elements must implement:

// maps symbol names to their values. an expression is evaluated in the context
// of a symbol table, in order to assign concrete values to variables referenced
// within it.
typedef std::map symboltable;

// abstract interface for expressions in the language.
class expr {
public:
  // evaluate the expression in the context of the given symbol table, which
  // is to be used to resolve (or update) variable references.
  virtual double eval(symboltable* st) const = 0;
};

and some simple expression types:

class constant : public expr {
public:
  constant(double value) : value_(value) {}

  double eval(symboltable* st) const {
    return value_;
  }

private:
  double value_;
};

class varref : public expr {
public:
  varref(const char* varname) : varname_(varname) {}

  double eval(symboltable* st) const {
    // ignore errors: assuming the symbol is defined.
    return (*st)[varname_];
  }

private:
  std::string varname_;
};

expressions such as constants and variable references are often called

Terminal

or

sheet

expressions, since they do not contain other expressions within them. let’s add a more complex non-leaf expression:

// a function type for computing the result of a binary operation.
typedef std::function binaryfunction;

class binaryop : public expr {
public:
  binaryop(binaryfunction func, const expr& lhs, const expr& rhs)
      : func_(func), lhs_(lhs), rhs_(rhs) {}

  double eval(symboltable* st) const {
    return func_(lhs_.eval(st), rhs_.eval(st));
  }

private:
  binaryfunction func_;
  const expr& lhs_;
  const expr& rhs_;
};

note how binaryop implements the same interface as leaf expressions. its eval defers to the eval method of its left and right constituent expressions. it is an embodiment of the composite design pattern, defined as:

[…] describes that a group of objects should be treated the same as a single instance of an object. the intent of a composite is to “compose” objects into tree structures to represent part-whole hierarchies. the implementation of the composite model allows customers to treat individual objects and compositions uniformly.

in the language of the composite pattern, there is

sheet

and

composite

classes, which are both

Components

. in our example, a constant is a leaf, just like a varref. a binary operation is a composite. both inherit from expr, which is the

making up

.

the core of the composite pattern manifests itself here in the uniform interface (expr) implemented by both constant (“individual object” in the definition quoted above) and binaryop (“composition”).

I’m not a big fan of uml, but since we’re talking about design patterns, I couldn’t help it 😉 here is our class diagram described in uml. note the close conceptual resemblance to the uml diagram on the composite model wikipedia page.

let’s finally see these classes in action. Here is a main function that assembles a simple expression by hand and evaluates it. this is a toy for demonstration purposes; in a real program, the syntax tree would be built automatically, most likely by a parser.

int main(int argc, const char** argv) {
  // define a couple of constants and a reference to the variable 'a'.
  std::unique_ptr c1(new constant(2.0));
  std::unique_ptr c2(new constant(3.3));
  std::unique_ptr v(new varref("a"));

  // define a binary expression representing "2.0 * 3.3 + a"
  std::unique_ptr e1(new binaryop(std::multiplies(), *c1, *c2));
  std::unique_ptr e2(new binaryop(std::plus(), *e1, *v));

  // evaluate in the context of a symbol table where a has the value 1.1
  symboltable st{{"a", 1.1}};
  std::cout << e2->eval(&st) << "n";

  return 0;
}

the expression tree created by this code is:

expression tree for 2.0*3.3+a

it is then evaluated with the context of a = 1.1, and the result is 7.7, as expected.

Finally, I’ll mention that while this example is very typical of a scenario where I usually encounter these two patterns, it’s by no means the only one.

the composite model has a life outside of the performers, of course. this is useful whenever a group of objects can be treated uniformly as a single object. for example, in the graphics world, we can have shape objects that can be moved, rotated, etc. ; we may want to treat a “group of shapes” the same way (move all shapes within it equally, rotate the group, etc.). this requires the use of the composite model where all shapes, as well as a “group of shapes” derive from a common component interface.

the interpreter pattern is useful whenever a problem can be described by a language of any type. some examples are sql or other logical query methods, regular expressions, many types of rule-based systems, etc.

Abdul J. Gaspar