Design Patterns in Rust: Interpreter, making sense of the world

The Interpreter pattern can be used to interpret and evaluate sentences in a language. The idea is to make a class for each symbol, both terminal and non-terminal and construct a syntax tree which can be evaluated and interpreted.

The interpreter pattern I will use here is probably one of the simplest implementations of this pattern. Before you use this pattern, what you need is a well-defined grammar for your language so that it can be evaluated and interpreted.

The simplest form of the interpreter looks like this:

This is not the whole picture, as we also need to build a syntax tree, which can be done in a parser, which is outside the scope of this article.

I think the idea will become much clearer when we implement this pattern.

Open your terminal or commandline in a new directory and type:

cargo new rust_interpreter
cd rust_interpreter

Next open your favourite IDE in this directory and open main.rs

The Expression is quite simple:

trait Expression {
    fn interpret(&self) -> bool;
}

It has only one method, interpret() which returns a bool, for the sake of simplicity.

The non-terminal expressions are the AndExpression and the OrExpression, since they can contain other objects implementing the Expression trait.

They look like this:

struct AndExpression<'a> {
    expr1: &'a Box<dyn Expression>,
    expr2: &'a Box<dyn Expression>,
}

impl<'a> AndExpression<'a> {
    fn new(expr1: &'a Box<dyn Expression>, expr2: &'a Box<dyn Expression>) -> Self {
        Self { expr1, expr2 }
    }
}

impl<'a> Expression for AndExpression<'a> {
    fn interpret(&self) -> bool {
        self.expr1.interpret() && self.expr2.interpret()
    }
}

struct OrExpression<'o> {
    expr1: &'o Box<dyn Expression>,
    expr2: &'o Box<dyn Expression>,
}

impl<'o> OrExpression<'o> {
    fn new(expr1: &'o Box<dyn Expression>, expr2: &'o Box<dyn Expression>) -> Self {
        Self { expr1, expr2 }
    }
}

impl<'o> Expression for OrExpression<'o> {
    fn interpret(&self) -> bool {
        self.expr1.interpret() || self.expr2.interpret()
    }
}

It might look complicated but it is not. A few remarks:

• Both the AndExpression and the OrExpression have two fields of the type Box<dyn Expression>. Because we do not know beforehand how big an Expression object can become we need to Box it in this case. Also notice the lifetime identifier, which make sure that the pointers to the field live as long as the parent object itself.
• Both structs have a simple constructor which is self-explanatory.
• The implementation of the Expression trait is also quite straightforward: the subexpressions are interpreted, and the results are either evaluated using an and-operation, denoted by ‘&&’ or an or-operation denoted by ‘||’

We also need a TerminalExpression which can contain some data, like number or strings. In our case we will use strings:

struct TerminalExpression {
    data: String,
}

impl TerminalExpression {
    fn new(data: String) -> Self {
        Self { data }
    }
}
    
impl Expression for TerminalExpression {
    fn interpret(&self) -> bool {
        self.data.contains("hello")        
    }
}

Some notes:

• In our case the TerminalExpression struct is no more than a wrapper for a string. In practice this can get more complicated.
• A simple constructor is defined.
• The interpret() of the TerminalExpression returns true if the data contains the word ‘hello’.

Now we will see what we can do with it:

fn main() {
    let expression1=Box::new(TerminalExpression::new("hello world".to_string())) as Box<dyn Expression>;
    let expression2=Box::new(TerminalExpression::new("goodbye world".to_string())) as Box<dyn Expression>;

    let expression3=OrExpression::new(&expression1, &expression2);
    println!("{}",expression3.interpret());

    let expression4=Box::new(TerminalExpression::new("hello everyone".to_string())) as Box<dyn Expression>;
    let expression5=AndExpression::new(&expression1, &expression4);
    println!("{}",expression5.interpret());
}

Line by line:

1. We construct two objects of type TerminalExpression, with different pieces of data. We also cast it to Box<dyn Expression> so it can be passed to the different constructors.
2. Then we feed those into an _OrExpression _and interpret the OrExpression. Since one of the _TerminalExpression _objects contains the word ‘hello’, the Interpret() method will return true.
3. Next we construct a new object of type TerminalExpression, also with ‘hello’ in its data
4. We feed both the first and the new TerminalExpression-objects to the AndExpression. Since both objects contain ‘hello’, the Interpret() method should also return true.

Before I wrote this article I worked on the Mediator pattern in Rust which is a whole lot more complicated. This one was quite easy to interpret, especially if you understand the ownership rules. The hardest part to apply this pattern in practice is to build a parser to that Expression objects can be put in some kind of Abstract Syntax Tree.

The beauty of this pattern is the fact that it forms a nice recursive structure, which, with the use of the Box-smartpointer translates elegantly into Rust.