Small Objects, Big Systems

Behavioral pattern

Interpreter

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

Participants

RoleIn this exampleResponsibility
Abstract ExpressionExpression, #evaluate(context)The interface every node in the grammar shares, plus the + and * operators.
Terminal ExpressionNumber, VariableLeaves of the tree. They interpret themselves directly.
Nonterminal ExpressionAdd, MultiplyOne class per grammar rule. They interpret themselves in terms of their parts.
ContextHash, e.g. { wave: 3 }The values the variables refer to.

Ruby implementation

interpreter.rb 
# A tiny language for wave formulas, such as "5 + 2 × wave" goblins.
# Operators are shared by every expression, so formulas read like arithmetic.
module Expression
  def +(other) = Add.new(left: self, right: other)
  def *(other) = Multiply.new(left: self, right: other)
end

# Terminal expressions.
Number = Data.define(:value) do
  include Expression

  def evaluate(_context) = value
  def to_s = value.to_s
end

Variable = Data.define(:name) do
  include Expression

  def evaluate(context) = context.fetch(name)
  def to_s = name.to_s
end

# Nonterminal expressions: each one interprets itself in terms of its parts.
Add = Data.define(:left, :right) do
  include Expression

  def evaluate(context) = left.evaluate(context) + right.evaluate(context)
  def to_s = "(#{left} + #{right})"
end

Multiply = Data.define(:left, :right) do
  include Expression

  def evaluate(context) = left.evaluate(context) * right.evaluate(context)
  def to_s = "(#{left} * #{right})"
end

In use

wave = Variable.new(:wave)

# Ruby operators build the syntax tree for us:
goblins = Number.new(5) + Number.new(2) * wave

goblins.to_s               # => "(5 + (2 * wave))"
goblins.evaluate(wave: 1)  # => 7
goblins.evaluate(wave: 3)  # => 11

The game’s wave sizes are formulas in code. As expressions, they become data: a level designer could write them, and the game can print, store or check them.

Notes

Ruby idioms

  • Operators are methods. Defining + and * in a shared module lets ordinary Ruby syntax build the tree. Ruby’s precedence rules give the right grouping for free.
  • Data.define makes each grammar rule a tiny immutable value with structural equality, so two identical sub-expressions compare equal.
  • A Hash is a fine context. fetch raises KeyError on an unbound variable instead of quietly giving nil.
  • Arel, the SQL builder inside Active Record, is a large interpreter of this kind.

Reach for it when

  • The language is small and stable: wave formulas, map layouts, search filters, pricing rules.
  • Designers or configuration need to describe behaviour as data.

Watch for

  • The pattern says nothing about parsing text into the tree. For a real grammar, use a parser such as Parslet or Racc and keep the interpreter for evaluation.
  • With one class per rule, large grammars get unwieldy. Visitor can move operations out of the nodes.

Represent each grammar rule as a small object, and every sentence becomes a tree you can evaluate, print or check.

See also