Demens Deum

What’s included

The Interpreter Pattern is a Behavioral Design Pattern. This pattern allows you to implement your own programming language by working with an AST tree, the vertices of which are terminal and non-terminal expressions that implement the Interpret method, which provides the functionality of the language.

• Terminal expression – e.g. string constant – “Hello World”
• Non-terminal expression – e.g. Print(“Hello World”), contains Print and an argument from the Terminal expression “Hello World”

What’s the difference? The difference is that the interpretation on terminal expressions ends, and for non-terminal expressions it continues deep into all incoming nodes/arguments. If the AST tree consisted only of non-terminal expressions, then the application would never complete, because some end of any process is required, this end is what terminal expressions are, they usually contain data, for example, strings.

An example of an AST tree is below:

Dcoetzee, CC0, via Wikimedia Commons

As you can see, terminal expressions are constant and variable, non-terminal expressions are the rest.

What is not included

The implementation of the Interpreter does not parse the string input of the language into the AST tree. It is enough to implement classes of terminal, non-terminal expressions, Interpret methods with the Context argument at the input, form an AST tree from expressions, run the Interpret method at the root expression. The context can be used to store the state of the application at runtime.

Implementation

Participants in the pattern:

• Client – returns AST tree and runs Interpret(context) on root node (Client)
• Context – contains the state of the application, passed to expressions when interpreted (Context)
• Abstract expression – an abstract class containing the method Interpret(context) (Expression)
• Terminal expression is a final expression, a descendant of an abstract expression (TerminalExpression)
• A non-terminal expression is not a final expression, contains pointers to nodes deep into the AST tree, subordinate nodes usually affect the result of interpreting a non-terminal expression (NonTerminalExpression)

C# Client Example

class Application {
        static void Main(string[] args)
        {
            var context = new Context();
            var initialProgram = new PerformExpression(
                new IExpression[] {
                    new SetExpression("alpha", "1"),
                    new GetExpression("alpha"),
                    new PrintExpression(
                        new IExpression[] {
                            new ConstantExpression("Hello Interpreter Pattern")
                        }
                    )
                }
            );
            System.Console.WriteLine(initialProgram.interpret(context));
        }
}

Example of an Abstract Expression in C#

interface IExpression
{
    String interpret(Context context);
}

C# Terminal Expression Example (String Constant)

class ConstantExpression : TerminalExpression
{
    private String constant;

    public ConstantExpression(String constant) {
        this.constant = constant;
    }

    override public String interpret(Context context) {
        return constant;
    }
}

Example of a Non-Terminal Expression in C# (Launching and concatenating the results of subordinate nodes, using the delimiter “;”

class PerformExpression : NonTerminalExpression
{
    public PerformExpression(IExpression[] leaves) : base(leafs) {
        this.leafs = leaves;
    }
    
    override public String interpret(Context context) {
        var output = "";
        foreach (var leaf in leaves) {
            output += leaf.interpret(context) + ";";
        }
        return output;
    }
}

Functionally, can you?

As you know, all Turing-complete languages ​​are equivalent. Can the Object-Oriented pattern be transferred to a Functional Programming language?

You can, for the experiment, let’s take the FP language for the web called Elm. There are no classes in Elm, but there are Records and Types, so the following records and types are involved in the implementation:

• Expression – enumeration of all possible language expressions (Expression)
• Subordinate expression – an expression that is subordinate to a non-terminal expression (ExpressionLeaf)
• Context – a record that stores the state of the application (Context)
• Functions that implement the Interpret(context) methods – all the necessary functions that implement the functionality of Terminal, Non-Terminal expressions
• Auxiliary records of the Interpreter state – necessary for the correct operation of the Interpreter, store the state of the Interpreter, the context

For example function that implements the interpretation for the entire set of possible expressions on Elm:

run input =
  case input.expression of
    Constant text ->
      {
        output = text
        context = input.context
      }
    Perform leafs ->
      let inputs = List.map (\leaf -> { expressionLeaf = leaf, context = input.context } ) leafs in
        let startLeaf = { expressionLeaf = (Node (Constant "")), context = { variables = Dict.empty } } in
          let outputExpressionInput = List.foldl mergeContextsAndRunLeafs startLeaf inputs in
            {
              output = (runExpressionLeaf outputExpressionInput).output,
              context = input.context
            }
    Print printExpression ->
      run
      {
        expression = printExpression,
        context = input.context
      }
    Set key value ->
      let variables = Dict.insert key value input.context.variables in
      {
        output="OK",
        context = { variables = variables }
      }
    get key ->
      {
        output = Maybe.withDefault("No value for key: " ++ key)(Dict.get key input.context.variables),
        context = input.context
      }

What about parsing?

Parsing source code into an AST tree is not part of the Interpreter pattern, there are several approaches to parsing source code, but more on that some other time.
In the implementation of the Interpreter for Elm, I wrote the simplest parser into the AST tree, consisting of two functions – parsing a vertex, parsing subordinate vertices.

parseLeafs: ParseLeafsState -> ParseLeafsState
parseLeafs state =
    let tokensQueue = state.tokensQueue in
        let popped = pop state.tokensQueue in
            let tokensQueueTail = tail state.tokensQueue in
                if popped == "Nothing" then
                    state
                else if popped == "Perform(" then
                    {
                        tokensQueue = tokensQueue,
                        result = (state.result++[Node(parse tokensQueue)])
                    }
                else if popped == ")" then
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = state.result
                    }
                else if popped == "Set" then
                    let key = pop tokensQueueTail in
                        let value = pop(tail tokensQueueTail) in
                            parseLeafs {
                                tokensQueue = tail(tail tokensQueueTail),
                                result = (state.result++[Node(Set key value)])
                            }
                else if popped == "Get" then
                    let key = pop tokensQueueTail in
                        parseLeafs {
                            tokensQueue = tail tokensQueueTail,
                            result = (state.result++[Node(Get key)])
                        }
                else
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = (state.result++[Node(Constant popped)])
                    }

parse tokensQueue =
    let popped = pop tokensQueue in
        let tokensQueueTail = tail tokensQueue in
            if popped == "Perform(" then
                Perform(
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = []
                    }
                ).result
            else if popped == "Set" then
                let key = pop tokensQueueTail in
                    let value = pop(tail tokensQueueTail) in
                        set key value
            else if popped == "Print" then
                Print(parse tokensQueueTail)
            else
                Constant popped

Links

https://gitlab.com/demensdeum /patterns/-/tree/master/interpreter/elm
https://gitlab.com/demensdeum/patterns/ -/tree/master/interpreter/csharp

Sources

https://en.wikipedia.org/wiki/Interpreter_pattern
https://elm-lang.org/
https://docs.microsoft.com/en-us/dotnet /csharp/