Interpreter pattern

In computer programming, the interpreter pattern is a design pattern that specifies how to evaluate sentences in a language. The basic idea is to have a class for each symbol (terminal or nonterminal) in a specialized computer language. The syntax tree of a sentence in the language is an instance of the composite pattern and is used to evaluate (interpret) the sentence for a client.[1]^:243 See also Composite pattern.

Overview

The Interpreter [2] design pattern is one of the twenty-three well-known GoF design patterns that describe how to solve recurring design problems to design flexible and reusable object-oriented software, that is, objects that are easier to implement, change, test, and reuse.

What problems can the Interpreter design pattern solve? [3]

A grammar for a simple language should be defined
so that sentences in the language can be interpreted.

When a problem occurs very often, it could be considered to represent it as a sentence in a simple language (Domain Specific Languages) so that an interpreter can solve the problem by interpreting the sentence.

For example, when many different or complex search expressions must be specified. Implementing (hard-wiring) them directly into a class is inflexible because it commits the class to particular expressions and makes it impossible to specify new expressions or change existing ones independently from (without having to change) the class.

What solution does the Interpreter design pattern describe?

Define a grammar for a simple language by defining an Expression class hierarchy and implementing an interpret() operation.
Represent a sentence in the language by an abstract syntax tree (AST) made up of Expression instances.
Interpret a sentence by calling interpret() on the AST.

The expression objects are composed recursively into a composite/tree structure that is called abstract syntax tree (see Composite pattern).
The Interpreter pattern doesn't describe how to build an abstract syntax tree. This can be done either manually by a client or automatically by a parser.

See also the UML class and object diagram below.

Uses

Specialized database query languages such as SQL.
Specialized computer languages that are often used to describe communication protocols.
Most general-purpose computer languages actually incorporate several specialized languages.

Structure

UML class and object diagram

A sample UML class and object diagram for the Interpreter design pattern.[4]

In the above UML class diagram, the Client class refers to the common AbstractExpression interface for interpreting an expression interpret(context).
The TerminalExpression class has no children and interprets an expression directly.
The NonTerminalExpression class maintains a container of child expressions (expressions) and forwards interpret requests to these expressions.

The object collaboration diagram shows the run-time interactions: The Client object sends an interpret request to the abstract syntax tree. The request is forwarded to (performed on) all objects downwards the tree structure.
The NonTerminalExpression objects (ntExpr1,ntExpr2) forward the request to their child expressions.
The TerminalExpression objects (tExpr1,tExpr2,…) perform the interpretation directly.

UML class diagram

Examples

BNF

The following Backus–Naur form example illustrates the interpreter pattern. The grammar

expression ::= plus | minus | variable | number
plus ::= expression expression '+'
minus ::= expression expression '-'
variable ::= 'a' | 'b' | 'c' | ... | 'z'
digit = '0' | '1' | ... | '9'
number ::= digit | digit number

defines a language that contains Reverse Polish Notation expressions like:

a b +
a b c + -
a b + c a - -

C#

This structural code demonstrates the Interpreter patterns, which using a defined grammar, provides the interpreter that processes parsed statements.

using System;
using System.Collections.Generic;

namespace OOP
{
    class Program
    {
        static void Main()
        {
            var context = new Context();
            var input = new MyExpression();

            var expression = new OrExpression
            {
                Left = new EqualsExpression
                {
                    Left = input, 
                    Right = new MyExpression { Value = "4" }
                },
                Right = new EqualsExpression
                {
                    Left = input,
                    Right = new MyExpression { Value = "four" }
                }
            };
            
            input.Value = "four";
            expression.Interpret(context);
            // Output: "true" 
            Console.WriteLine(context.Result.Pop());

            input.Value = "44";
            expression.Interpret(context);
            // Output: "false"
            Console.WriteLine(context.Result.Pop());
        }
    }

    class Context
    {
        public Stack<string> Result = new Stack<string>();        
    }

    interface Expression
    {
        void Interpret(Context context);
    }

    abstract class OperatorExpression : Expression
    {
        public Expression Left { private get; set; }
        public Expression Right { private get; set; }        

        public void Interpret(Context context)
        {
            Left.Interpret(context);
            string leftValue = context.Result.Pop();

            Right.Interpret(context);
            string rightValue = context.Result.Pop();

            DoInterpret(context, leftValue, rightValue);
        }

        protected abstract void DoInterpret(Context context, string leftValue, string rightValue);
    }

    class EqualsExpression : OperatorExpression
    { 
        protected override void DoInterpret(Context context, string leftValue, string rightValue)
        {
            context.Result.Push(leftValue == rightValue ? "true" : "false");
        }
    }

    class OrExpression : OperatorExpression
    {
        protected override void DoInterpret(Context context, string leftValue, string rightValue)
        {
            context.Result.Push(leftValue == "true" || rightValue == "true" ? "true" : "false");
        }
    }

    class MyExpression : Expression
    {
        public string Value { private get; set; }

        public void Interpret(Context context)
        {
            context.Result.Push(Value);
        }
    }
}

Java

Following the interpreter pattern, we need to implement the interface Expr with a lambda (it can be a class) for each grammar rule.

public class Interpreter {
    @FunctionalInterface
    public interface Expr {
        int interpret(Map<String, Integer> context);
        
        static Expr number(int number) {
            return context -> number;
        }
        
        static Expr plus(Expr left, Expr right) {
            return context -> left.interpret(context) + right.interpret(context);
        }
        
        static Expr minus(Expr left, Expr right) {
            return context -> left.interpret(context) - right.interpret(context);
        }
        
        static Expr variable(String name) {
            return context -> context.getOrDefault(name, 0);
        }
    }

While the interpreter pattern does not address parsing,[1]^:247 a parser is provided for completeness.

    private static Expr parseToken(String token, ArrayDeque<Expr> stack) {
        Expr left, right;
        switch(token) {
        case "+":
            // It's necessary to remove first the right operand from the stack
            right = stack.pop();
            // ...and then the left one
            left = stack.pop();
            return Expr.plus(left, right);
        case "-":
            right = stack.pop();
            left = stack.pop();
            return Expr.minus(left, right);
        default:
            return Expr.variable(token);
        }
    }
    public static Expr parse(String expression) {
        ArrayDeque<Expr> stack = new ArrayDeque<Expr>();
        for (String token : expression.split(" ")) {
            stack.push(parseToken(token, stack));
        }
        return stack.pop();
    }

Finally evaluating the expression "w x z - +" with w = 5, x = 10, and z = 42.

    public static void main(final String[] args) {
        Expr expr = parse("w x z - +");
        Map<String, Integer> context = Map.of("w", 5, "x", 10, "z", 42);
        int result = expr.interpret(context);
        System.out.println(result);        // -27
    }
}

PHP (Example 1)

/**
 * AbstractExpression
 */
interface Expression
{
    public function interpret(array $context): int;
}

/**
 * TerminalExpression
 */
class TerminalExpression implements Expression
{
    /** @var string */
    private $name;

    public function __construct(string $name)
    {
        $this->name = $name;
    }

    public function interpret(array $context): int
    {
        return intval($context[$this->name]);
    }
}

/**
 * NonTerminalExpression
 */
abstract class NonTerminalExpression implements Expression
{
    /** @var Expression $left */
    protected $left;

    /** @var ?Expression $right */
    protected $right;

    public function __construct(Expression $left, ?Expression $right)
    {
        $this->left = $left;
        $this->right = $right;
    }

    abstract public function interpret(array $context): int;
    
    public function getRight()
    {
        return $this->right;
    }

    public function setRight($right): void
    {
        $this->right = $right;
    }
}

/**
 * NonTerminalExpression - PlusExpression
 */
class PlusExpression extends NonTerminalExpression
{
    public function interpret(array $context): int
    {
        return intval($this->left->interpret($context) + $this->right->interpret($context));
    }
}

/**
 * NonTerminalExpression - MinusExpression
 */
class MinusExpression extends NonTerminalExpression
{
    public function interpret(array $context): int
    {
        return intval($this->left->interpret($context) - $this->right->interpret($context));
    }
}

/**
 * Client
 */
class InterpreterClient
{
    protected function parseList(array &$stack, array $list, int &$index)
    {
        /** @var string $token */
        $token = $list[$index];

        switch($token) {
            case '-':
                list($left, $right) = $this->fetchArguments($stack, $list, $index);
                return new MinusExpression($left, $right);
            case '+':
                list($left, $right) = $this->fetchArguments($stack, $list, $index);
                return new PlusExpression($left, $right);
            default:
                return new TerminalExpression($token);
        }
    }

    protected function fetchArguments(array &$stack, array $list, int &$index): array
    {
        /** @var Expression $left */
        $left = array_pop($stack);
        /** @var Expression $right */
        $right = array_pop($stack);
        if ($right === null) {
            ++$index;
            $this->parseListAndPush($stack, $list, $index);
            $right = array_pop($stack);
        }

        return array($left, $right);
    }

    protected function parseListAndPush(array &$stack, array $list, int &$index)
    {
        array_push($stack, $this->parseList($stack, $list, $index));
    }

    protected function parse(string $data): Expression
    {
        $stack = [];
        $list = explode(' ', $data);
        for ($index=0; $index<count($list); $index++) {
            $this->parseListAndPush($stack, $list, $index);
        }

        return array_pop($stack);
    }

    public function main()
    {
        $data = "u + v - w + z";
        $expr = $this->parse($data);
        $context = ['u' => 3, 'v' => 7, 'w' => 35, 'z' => 9];
        $res = $expr->interpret($context);
        echo "result: $res" . PHP_EOL;
    }
}

// test.php

function loadClass($className)
{
    require_once __DIR__ . "/$className.php";
}

spl_autoload_register('loadClass');

(new InterpreterClient())->main();
//result: -16

PHP (Example 2)

based on the example above with another realization of the Client

/**
 * Client
 */
class InterpreterClient
{
    public function parseToken(string $token, array &$stack): Expression
    {
        switch($token) {
            case '-':
                /** @var Expression $left */
                $left = array_pop($stack);
                /** @var Expression $right */
                $right = array_pop($stack);
                return new MinusExpression($left, $right);
            case '+':
                /** @var Expression $left */
                $left = array_pop($stack);
                /** @var Expression $right */
                $right = array_pop($stack);
                return new PlusExpression($left, $right);
            default:
                return new TerminalExpression($token);
        }
    }

    public function parse(string $data): Expression
    {
        $unfinishedData = null;
        $stack = [];
        $list = explode(' ', $data);
        foreach ($list as $token) {
            $data = $this->parseToken($token, $stack);
            if (
                ($unfinishedData instanceof NonTerminalExpression) &&
                ($data instanceof TerminalExpression)
            ) {
                $unfinishedData->setRight($data);
                array_push($stack, $unfinishedData);
                $unfinishedData = null;
                continue;
            }
            if ($data instanceof NonTerminalExpression) {
                if ($data->getRight() === null) {
                    $unfinishedData = $data;
                    continue;
                }
            }
            array_push($stack, $data);
        }

        return array_pop($stack);
    }

    public function main()
    {
        $data = "u + v - w + z";
        $expr = $this->parse($data);
        $context = ['u' => 3, 'v' => 7, 'w' => 35, 'z' => 9];
        $res = $expr->interpret($context);
        echo "result: $res" . PHP_EOL;
    }
}

JavaScript

As JavaScript do not support real Object Orientation, we do not implement a interface.

// Nonterminal expression
class Plus {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) + this.b.interpret(context);
    }
}
// Nonterminal expression
class Minus {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) - this.b.interpret(context);
    }
}
// Nonterminal expression
class Times {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) * this.b.interpret(context);
    }
}
// Nonterminal expression
class Divide {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) / this.b.interpret(context);
    }
}
// Terminal expression
class Number {
    a;
    constructor(a, b) {
        this.a = a;
    }
    interpret(context) {
        return this.a; 
    }
}
// Terminal expression
class Variable {
    a;
    constructor(a) {
        this.a = a;
    }
    interpret(context) {
        return context[this.a] || 0;
    }
}
// Client
class Parse {
    context;
    constructor(context) {
        this.context = context;
    }
    parse(expression) {
        let tokens = expression.split(" ");
        let queue = [];
        for (let token of tokens) {
            switch (token) {
                case "+":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Plus(a, b);
                    queue.push(exp);
                break;
                case "/":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Divide(a, b);
                    queue.push(exp);
                break;
                case "*":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Times(a, b);
                    queue.push(exp);
                break;
                case "-":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Minus(a, b);
                    queue.push(exp);
                break;
                default:
                    if(isNaN(token)) {
                        var exp = new Variable(token);
                        queue.push(exp);   
                    } else {
                        var number = parseInt(token);
                        var exp = new Number(number);
                        queue.push(exp);
                    }
                break;
            } 
        }
        let main = queue.pop();
        return main.interpret(this.context);
    }
}
var res = new Parse({v: 45}).parse("16 v * 76 22 - -");
console.log(res)
//666

References

Gamma, Erich; Helm, Richard; Johnson, Ralph; Vlissides, John (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley. ISBN 0-201-63361-2.
Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley. pp. 243ff. ISBN 0-201-63361-2.CS1 maint: multiple names: authors list (link)
"The Interpreter design pattern - Problem, Solution, and Applicability". w3sDesign.com. Retrieved 2017-08-12.
"The Interpreter design pattern - Structure and Collaboration". w3sDesign.com. Retrieved 2017-08-12.

External links

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[GoF-1] Gamma, Erich; Helm, Richard; Johnson, Ralph; Vlissides, John (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley. ISBN 0-201-63361-2.

[GoF2-2] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley. pp. 243ff. ISBN 0-201-63361-2.CS1 maint: multiple names: authors list (link)

[3] "The Interpreter design pattern - Problem, Solution, and Applicability". w3sDesign.com. Retrieved 2017-08-12.

[4] "The Interpreter design pattern - Structure and Collaboration". w3sDesign.com. Retrieved 2017-08-12.

Software design patterns
Creational	Abstract factory Builder Dependency injection Factory method Lazy initialization Multiton Object pool Prototype RAII Singleton
Structural	Adapter Bridge Composite Decorator Delegation Facade Flyweight Front controller Marker interface Module Proxy Twin
Behavioral	Blackboard Chain of responsibility Command Interpreter Iterator Mediator Memento Null object Observer Servant Specification State Strategy Template method Visitor
Functional	Monoid Functor Applicative Monad Comonad Free monad HOF Currying Function composition Closure Generator
Concurrency	Active object Actor Balking Barrier Binding properties Coroutine Compute kernel Double-checked locking Event-based asynchronous Fiber Futex Futures and promises Guarded suspension Immutable object Join Lock Messaging Monitor Nuclear Proactor Reactor Read write lock Scheduler STM Thread pool Thread-local storage
Architectural	ADR Active record Broker Client–server CBD DAO DTO DDD ECB ECS EDA Front controller Identity map Interceptor Implicit invocation Inversion of control Model 2 MOM Microservices MVA MVC MVP MVVM Monolithic Multitier Naked objects ORB P2P Publish–subscribe PAC REST SOA Service locator Specification
Cloud Distributed	Ambassador Anti-Corruption Layer Bulkhead Cache-Aside Circuit Breaker CQRS Compensating Transaction Competing Consumers Compute Resource Consolidation Event Sourcing External Configuration Store Federated Identity Gatekeeper Index Table Leader Election MapReduce Materialized View Pipes Filters Priority Queue Publisher-Subscriber Queue-Based Load Leveling Retry Scheduler Agent Supervisor Sharding Sidecar Strangler Throttling Valet Key
Other	Business delegate Composite entity Intercepting filter Lazy loading Mangler Mock object Type tunnel Method chaining
Books	Design Patterns Enterprise Integration Patterns Code Complete POSA
People	Christopher Alexander Erich Gamma Ralph Johnson John Vlissides Grady Booch Kent Beck Ward Cunningham Martin Fowler Robert Martin Jim Coplien Douglas Schmidt Linda Rising
Communities	The Hillside Group The Portland Pattern Repository