Design Patterns – Interpreter

The Interpreter Design Pattern guides us in constructing a hierarchy of expressions capable of evaluating sequences of symbols. This pattern is commonly used for evaluating expressions, statements, or entire languages. It can be applied to a wide range of applications that involve analyzing sequences of symbols, whether they are words, sentences, or any other type, and make sense of them.

When to use

Use the Interpreter Pattern when you encounter a recurring problem that can be solved by describing a solution, in a form of a language, rather than creating new algorithms from scratch each time similar problems arise.

In situations where similar problems occurs frequently, developing custom solutions for each instance of the problem can become time-consuming. To address this, we can construct a language with specific grammar rules, along with an interpreter that evaluates this language, thereby solving the problem. This way, we shift the problem to a different domain that is more beneficial for us to solve. Our main task then becomes building the interpreter for this language.

For example, regular expressions (Regex) is a language that describes how to split, group or recognize patterns within a string. This is a common problem, that drove the development of a language to handle such cases. Behind the scenes, an interpreter is constructed for this purpose, which evaluates the regex expression and provides the final result. Creating or modifying a regular expression is much simpler than creating algorithms to match patterns, group data, or split strings under specific conditions. In that particular example, the interpreter describes how to define a grammar for a language and how to parse it and interpret/evaluate it.

Use the Interpreter Pattern when building a new language.

With the Interpreter Pattern, you can create the grammar for an entire language, not just expressions, and then model each expression or statement of that language with a class. Some expressions will be terminal, meaning they won’t contain any other expressions, such as a number or a string. Other may be composite, containing additional expressions within them, like an addition expression requiring left and right operands, which could also be expressions as well. Recursively, we can evaluate each expression to obtain the final result.

Another component when building an interpreter for a language is the language tokenizer (or lexer). This component takes the language as a string input and produces the tokens it identifies. Below, we illustrate this concept with a simple assignment statement and how it might be converted into tokens. However, when discussing the Interpreter Pattern, we exclude the Tokenizer and Parser components.

Next, the tokens serve as inputs to the language parser, which converts them to expressions and statements of the language. The result of this process is a tree hierarchy, also known as an Abstract Syntax Tree (AST).

Finally, the Interpreter Pattern helps the evaluation of the expression tree created from the previous steps. In this article, and generally when discussing about the Interpreter Pattern, we delve into the final stage of this process, which involves the interpretation of the expressions. Tokenization and parsing are not part of the Interpreter Pattern.

As an example of an Abstract Syntax Tree, below we demonstrate the composite nature of mathematical expressions for the following expression: 21 + (3-10) / 2

Another aspect of the Interpreter Pattern is the order of evaluation. By examining the expression hierarchy, the interpreter first evaluates the left subtree, followed by the right subtree, and then the root node, implementing a post-order traversal. Below, we illustrate this concept along with the order in which each expression is evaluated:

How to implement

In the Interpreter Pattern, we represent each expression, statement or other language element with a class. Then, by composing those classes hierarchically, we can construct complex expressions and evaluate them.

Define an Abstract Expression.

This represents every expression in our language. We can also create a similar abstraction for statements or other language concepts . The abstract Expression, which can also be an interface, will have an Interpret method that all subclasses must implement.

public abstract class Expression
{
   public abstract object Interpret(Context context);
}

Define a Context class (optional).

Depending on the requirements, we may need to create a context class that holds state needed for various expressions. Each expression can update data in the context .

public class Context
{
   public object Data { get; set; }
}

Define the necessary concrete expressions of the language.

In this step, we model each expression of our language with a separate concrete class. An expression might be terminal, meaning it doesn’t contain other expressions, or composite, consisting of various other expressions.

public class TerminalExpression : Expression
{
   public object Value { get; }

   public TerminalExpression(object value)
   {
      Value = value;
   }

   public override object Interpret(Context context) => Value;
}

The TerminalExpression simply evaluates to the value it contains, such as a number or a string. Next, the ConcreteExpression1 is a unary expression, which means it has one expression as its operand and one operator.

public class ConcreteExpression1 : Expression
{
   public Expression Expression { get; }

   public ConcreteExpression1(Expression expression)
   {
      Expression = expression;
   }

   public override object Interpret(Context context)
   {
      var result = Expression.Interpret(context);
      // Operate on the result, use context if nessesary, and return a new value.
      return result;
   }
}

Finally, ConcreteExpression2 is a binary expression that contains two expressions as its operands.

public class ConcreteExpression2 : Expression
{
   public Expression Left { get; }
   public Expression Right { get; }

   public ConcreteExpression2(Expression left, Expression right)
   {
      Left = left;
      Right = right;
   }

   public override object Interpret(Context context)
   {
      var leftValue = Left.Interpret(context);
      var rightValue = Right.Interpret(context);
      // Operate on the results, use context if necessary, and return a new value.
      return leftValue.ToString() + rightValue.ToString();
   }
}

Each Interpret method involves interpreting its internal expressions first by calling their Interpret methods.

Finally, build and interpret a tree of expressions.

By combining the expressions, we can construct any expression instance our language supports and interpret it by calling the Interpret method of the root expression. An example is shown below:

var root = new ConcreteExpression2(
   new ConcreteExpression1(new TerminalExpression(1)),
   new ConcreteExpression1(new TerminalExpression(2)));

var result = root.Interpret(new Context());

Interpreter Pattern – Class diagram

The class diagram below illustrates the AbstractExpression with the Interpret method. Each TerminalExpression and NonTerminalExpression must implement the Interpret method.

Pros and Cons

Real World Example – Power Fx

In this example, we explore the Power Fx expression engine, a language utilizing the Interpreter Pattern with a Visitor approach to evaluate expressions. Rather than implementing the Interpret method within each expression object, the Visitor Pattern is combined to implement each Interpret method in a separate class. This approach is still valid for the Interpreter Pattern.

The Power Fx Expression language uses the Interpreter Pattern along with the Visitor approach to evaluate expressions. First, The IRNodeVisitor interface contains all the Visit methods for each node (expressions such as BinaryOpNode, UnaryOpNode):

internal abstract class IRNodeVisitor<TResult, TContext>
{
   // code ommited...

   public abstract TResult Visit(NumberLiteralNode node, TContext context);

   public abstract TResult Visit(RecordNode node, TContext context);

   public abstract TResult Visit(ErrorNode node, TContext context);

   public abstract TResult Visit(LazyEvalNode node, TContext context);

   public abstract TResult Visit(CallNode node, TContext context);

   public abstract TResult Visit(BinaryOpNode node, TContext context);

   public abstract TResult Visit(UnaryOpNode node, TContext context);
   
   // code ommited...
}

Below, we show the implementation of the IRNodeVisitor, the EvalVisitor, that has the interpretation of each expression in a single file:

internal class EvalVisitor : IRNodeVisitor<ValueTask<FormulaValue>, EvalVisitorContext>
{
   //  code ommited...
   public override async ValueTask<FormulaValue> Visit(TextLiteralNode node, EvalVisitorContext context)
      => new StringValue(node.IRContext, node.LiteralValue);

   public override async ValueTask<FormulaValue> Visit(NumberLiteralNode node, EvalVisitorContext context)
      => new NumberValue(node.IRContext, node.LiteralValue);

   public override async ValueTask<FormulaValue> Visit(DecimalLiteralNode node, EvalVisitorContext context)
      => new DecimalValue(node.IRContext, node.LiteralValue);

   public override async ValueTask<FormulaValue> Visit(BooleanLiteralNode node, EvalVisitorContext context)
      => new BooleanValue(node.IRContext, node.LiteralValue);
      
   //  code ommited...
   
   private ValueTask<FormulaValue> VisitBinaryOpNode(BinaryOpNode node, EvalVisitorContext context, FormulaValue[] args)
   {
      switch (node.Op)
      {
         case BinaryOpKind.AddNumbers:
            return OperatorBinaryAdd(this, context, node.IRContext, args);
         case BinaryOpKind.AddDecimals:
            return OperatorDecimalBinaryAdd(this, context, node.IRContext, args);
         case BinaryOpKind.MulNumbers:
            return OperatorBinaryMul(this, context, node.IRContext, args);
         case BinaryOpKind.MulDecimals:
            return OperatorDecimalBinaryMul(this, context, node.IRContext, args);
         //  code ommited...
      }
   }

   //  code ommited...
}

This way we can organize all interpret method implementations for each expression in a single class.

Example – Mathematical Expression Interpreter

In this example, we will utilize the Interpreter Pattern to create a calculator app capable of evaluating mathematical expressions. The expressions will support decimal numbers and basic operations such as addition, subtraction, multiplication, and division. Additionally, in the last section, we’ll demonstrate how to extend the existing hierarchy to add a new expression.

Building the Expressions

First, all expressions will implement the IExpression interface, shown below:

public interface IExpression
{
   decimal Evaluate();
}

Next, we define the DivisionExpression, MultiplicationExpression, SubtractionExpression and AdditionExpression. Additionally, the GroupExpression that models the parenthesis, and the NumberExpression which is a terminal expression. The code is shown below:

public class DivisionExpression : IExpression
{
   private readonly IExpression _left;
   private readonly IExpression _right;

   public DivisionExpression(IExpression left, IExpression right)
   {
      _left = left;
      _right = right;
   }

   public decimal Evaluate()
      => this._left.Evaluate() / this._right.Evaluate();
}

public class MultiplicationExpression : IExpression
{
   private readonly IExpression _left;
   private readonly IExpression _right;

   public MultiplicationExpression(IExpression left, IExpression right)
   {
      this._left = left;
      this._right = right;
   }

   public decimal Evaluate()
      => this._left.Evaluate() * this._right.Evaluate();
}

public class SubtractionExpression : IExpression
{
   private readonly IExpression _left;
   private readonly IExpression _right;

   public SubtractionExpression(IExpression left, IExpression right)
   {
      this._left = left;
      this._right = right;
   }

   public decimal Evaluate()
      => this._left.Evaluate() - this._right.Evaluate();   
}

public class AdditionExpression : IExpression
{
   private readonly IExpression _left;
   private readonly IExpression _right;

   public AdditionExpression(IExpression left, IExpression right)
   {
      this._left = left;
      this._right = right;
   }

   public decimal Evaluate()
      => this._left.Evaluate() + this._right.Evaluate();
}

The NumberExpression simply evaluates to the number it contains and the GroupExpression calls the Evaluate method of the expression it contains:

public class NumberExpression : IExpression
{
   private readonly decimal _number;

   public NumberExpression(decimal number)
   {
      this._number = number;
   }

   public decimal Evaluate() => this._number;
}

public class GroupExpression : IExpression
{
   public readonly IExpression _expression;

   public GroupExpression(IExpression expression)
   {
      _expression = expression;
   }

   public decimal Evaluate()
      => _expression.Evaluate();
}

Usage Example

By using the expressions we can build mathematical expressions and evaluate them. For example, to evaluate the expression 1 * (4 - 5) / 6 + 10 we create the following hierarchy:

var subtraction = new SubtractionExpression(new NumberExpression(4), new NumberExpression(5));
var multiplication = new MultiplicationExpression(new NumberExpression(1), subtraction);
var division = new DivisionExpression(multiplication, new NumberExpression(6));
var addition = new SumExpression(division, new NumberExpression(10));

var result = addition.Evaluate(); // Output: 9.8333

The corresponding Abstract Syntax Tree created is illustrated below:

Mathematical Expression Interpreter – Class Diagram

Below, the class diagram illustrates the various expressions that implement the IExpression interface.

Adding a New Expression

In this section we demonstrate how we can support a new expression for our existing interpreter. Suppose we want to add a ModExpression that calculates the mod between two numbers. The mod gives us the remainder between a dividend and divisor. First, we create the ModExpression class that extends the IExpression interface. The ModExpression will have two IExpressions properties, one for the dividend and the other for the divisor as shown below:

public class ModExpression : IExpression
{
   private readonly IExpression _dividend;
   private readonly IExpression _divisor;

   public ModExpression(IExpression dividend, IExpression divisor)
   {
      _dividend = dividend;
      _divisor = divisor;
   }

   public decimal Evaluate()
      => _dividend.Evaluate() % _divisor.Evaluate();
}

We can use the ModExpression for the expression: 2 / mod(2*4, 3) + 2. Also, in the ModExpression the divisor and dividend parameters are of type IExpression, which means we can pass as argument a multiplication expression (or any other expression) as this example shows. The following code demonstrates how to build the appropriate expression hierarchy for this expression:

var multiplication = new MultiplicationExpression(new NumberExpression(2), new NumberExpression(4));
var mod = new ModExpression(multiplication, new NumberExpression(3));
var division = new DivisionExpression(new NumberExpression(2), mod);
var addition = new SumExpression(division, new NumberExpression(2));

var result = addition.Evaluate(); // Output: 3

Using Dependency Injection

Dependency injection is a powerful technique that enables flexible and loosely coupled code. In this section, we’ll explore how to use dependency injection to implement the Interpreter Pattern.

Autofac

C#

We register each expression with a unique key in the ContainerBuilder. Later, we can resolve the expressions we need as IExpression without explicitly referencing any concrete types. Finally, we call the Evaluate() method of the root expression to obtain the final result. Below is the C# code example:

var builder = new ContainerBuilder();

// Registrations
builder.RegisterType<SubtractionExpression>().Keyed<IExpression>("-");
builder.RegisterType<MultiplicationExpression>().Keyed<IExpression>("*");
builder.RegisterType<DivisionExpression>().Keyed<IExpression>("/");
builder.RegisterType<SumExpression>().Keyed<IExpression>("+");
builder.RegisterType<NumberExpression>().Keyed<IExpression>("num");

IContainer container = builder.Build();

// 1 * (4 - 5) / 6 + 10
var num1 = container.ResolveKeyed<IExpression>("num", new NamedParameter("number", 1m));
var num4 = container.ResolveKeyed<IExpression>("num", new NamedParameter("number", 4m));
var num5 = container.ResolveKeyed<IExpression>("num", new NamedParameter("number", 5m));
var num6 = container.ResolveKeyed<IExpression>("num", new NamedParameter("number", 6m));
var num10 = container.ResolveKeyed<IExpression>("num", new NamedParameter("number", 10m));

var subtraction = container.ResolveKeyed<IExpression>("-", 
   new NamedParameter("left", num4),
   new NamedParameter("right", num5));

var multiplication = container.ResolveKeyed<IExpression>("*",
   new NamedParameter("left", num1),
   new NamedParameter("right", subtraction));

var division = container.ResolveKeyed<IExpression>("/",
   new NamedParameter("left", multiplication),
   new NamedParameter("right", num6));

var sum = container.ResolveKeyed<IExpression>("+",
   new NamedParameter("left", division),
   new NamedParameter("right", num10));

var result = sum.Evaluate(); // Output: 9.8333

Similar Patterns

Further Reading

Looking to dive deeper into design patterns and take your programming skills to the next level? Check out the following highly recommended books:

* This website includes affiliate product links. We may earn a commission if you make a purchase after clicking on one of these links. Your support is greatly appreciated!