The most famous interpreter we can talk about is probably SQL. It's defined as a special-purpose programming language for managing data held in relational databases. SQL is quite complex and big but, all in all, is a set of words and operators that allow us to perform operations such as insert, select, or delete.

Another typical example is musical notation. It's a language itself and the interpreter is the musician who knows the connection between a note and its representation on the instrument they are playing.

In computer science, it can be useful to design a small language for a variety of reasons: repetitive tasks, higher-level languages for non-developers, or Interface Definition Languages (IDL) such as Protocol buffers or Apache Thrift.

Designing a new language, big or small, can be a time consuming task so it's very important to have the objectives clear before investing time and resources on writing an interpreter of it:

SQL allows the use of relational databases in a very easy-to-use syntax (that can become incredibly complex too) but the idea is to not need to write your own functions to make insertions and searches.

A very typical example of an interpreter is to create a reverse polish notation calculator. For those who don't know what polish notation is, it's a mathematical notation to make operations where you write your operation first (sum) and then the values (3 4), so + 3 4 is equivalent to the more common 3 + 4 and its result would be 7. So, for a reverse polish notation, you put first the values and then the operation, so 3 4 + would also be 7.

For our calculator, the acceptance criteria we should pass to consider it done are as follows:

So the 3 4 sum 2 sub notation is the same than (3 + 4) - 2 and result would be 5.

In this case, we will only have a public method called Calculate that takes an operation with its values defined as a string and will return a value or an error:

func Calculate(o string) (int, error) { 
  return 0, fmt.Errorf("Not implemented yet") 
} 

So, we will send a string like "3 4 +" to the Calculate method and it should return 7, nil. Two tests more will check the correct implementation:

func TestCalculate(t *testing.T) { 
  tempOperation = "3 4 sum 2 sub" 
  res, err = Calculate(tempOperation) 
  if err != nil { 
    t.Error(err) 
  } 
 
  if res != 5 { 
    t.Errorf("Expected result not found: %d != %d
", 5, res) 
  } 

First, we are going to make the operation we have used as an example. The 3 4 sum 2 sub notation is part of our language and we use it in the Calculate function. If an error is returned, the test fails. Finally, the result must be equal to 5 and we check it on the last lines. The next test checks the rest of the operators on slightly more complex operations:

  tempOperation := "5 3 sub 8 mul 4 sum 5 div" 
  res, err := Calculate(tempOperation) 
  if err != nil { 
    t.Error(err) 
  } 
 
  if res != 4 { 
    t.Errorf("Expected result not found: %d != %d
", 4, res) 
  } 
} 

Here, we repeated the preceding process with a longer operation, the (((5 - 3) * 8) + 4) / 5 notation which is equal to 4. From left to right, it would be as follows:

(((5 - 3) * 8) + 4) / 5
  ((2 * 8) + 4) / 5
    (16 + 4) / 5
      20 / 5
        4

The test must fail, of course!

$ go test -v .
  interpreter_test.go:9: Not implemented yet
  interpreter_test.go:13: Expected result not found: 4 != 0
  interpreter_test.go:19: Not implemented yet
  interpreter_test.go:23: Expected result not found: 5 != 0
exit status 1
FAIL

Implementation is going to be longer than testing this time. To start, we will define our possible operators in constants:

const ( 
  SUM = "sum" 
  SUB = "sub" 
  MUL = "mul" 
  DIV = "div" 
) 

Interpreter patterns are usually implemented using an abstract syntax tree, something that is commonly achieved using a stack. We have created stacks before during the book so this should be already familiar to readers:

type polishNotationStack []int 
 
func (p *polishNotationStack) Push(s int) { 
  *p = append(*p, s) 
} 
 
func (p *polishNotationStack) Pop() int { 
  length := len(*p) 
 
  if length > 0 { 
    temp := (*p)[length-1] 
    *p = (*p)[:length-1] 
    return temp 
  } 
 
  return 0 
} 

We have two methods--the Push method to add elements to the top of the stack and the Pop method to remove elements and return them. In case you are thinking that the line *p = (*p)[:length-1] is a bit cryptic, we'll explain it.

The value stored in the direction of p will be overridden with the actual value in the direction of p (*p) but taking only the elements from the beginning to the penultimate element of the array (:length-1).

So, now we will go step by step with the Calculate function, creating more functions as far as we need them:

func Calculate(o string) (int, error) { 
  stack := polishNotationStack{} 
  operators := strings.Split(o, " ") 

The first two things we need to do are to create the stack and to get all different symbols from the incoming operation (in this case, we aren't checking that it isn't empty). We split the incoming string operations by the space to get a nice slice of symbols (values and operators).

Next, we will iterate over every symbol by using range but we need a function to know whether the incoming symbol is a value or an operator:

func isOperator(o string) bool { 
  if o == SUM || o == SUB || o == MUL || o == DIV { 
    return true 
  } 
 
  return false 
} 

If the incoming symbol is any of the ones defined in our constants, the incoming symbol is an operator:

func Calculate(o string) (int, error) { 
  stack := polishNotationStack{} 
  operators := strings.Split(o, " ") 
 
for _, operatorString := range operators {
  
  if isOperator(operatorString) {
      
    right := stack.Pop()
      
    left := stack.Pop()
    
  } 
  else 
  {
      
    //Is a value
    
  }

}

If it is an operator, we consider that we have already passed two values so what we have to do is to take those two values from the stack. The first value taken would be the rightmost and the second the leftmost (remember that in subtractions and divisions, the order of the operands is important). Then, we need some function to get the operation we want to perform:

func getOperationFunc(o string) func(a, b int) int { 
  switch o { 
  case SUM: 
    return func(a, b int) int { 
      return a + b 
    } 
  case SUB: 
    return func(a, b int) int { 
      return a - b 
    } 
  case MUL: 
    return func(a, b int) int { 
      return a * b 
    } 
  case DIV: 
    return func(a, b int) int { 
      return a / b 
    } 
  } 
  return nil 
} 

The getOperationFunc functions returns a two-argument function that returns an integer. We check the incoming operator and we return an anonymous function that performs the specified operation. So, now our for range continues like this:

func Calculate(o string) (int, error) { 
  stack := polishNotationStack{} 
  operators := strings.Split(o, " ") 
 
for _, operatorString := range operators { 
  if isOperator(operatorString) { 
      right := stack.Pop() 
      left := stack.Pop() 
      mathFunc := getOperationFunc(operatorString)
      res := mathFunc(left, right)
      stack.Push(res) 
    } else { 
      //Is a value 
    } 
} 

The mathFunc variable is returned by the function. We use it immediately to perform the operation on the left and right values taken from the stack and we store its result in a new variable called res. Finally, we need to push this new value to the stack to keep operating with it later.

Now, here is the implementation when the incoming symbol is a value:

func Calculate(o string) (int, error) { 
  stack := polishNotationStack{} 
  operators := strings.Split(o, " ") 
 
for _, operatorString := range operators { 
    if isOperator(operatorString) { 
      right := stack.Pop() 
      left := stack.Pop() 
      mathFunc := getOperationFunc(operatorString) 
      res := mathFunc(left, right) 
      stack.Push(res) 
    } else { 
      val, err := strconv.Atoi(operatorString)
      
      if err != nil {
        
        return 0, err
      
      }
      
      stack.Push(val) 
    } 
  } 

What we need to do every time we get a symbol is to push it to the stack. We have to parse the string symbol to a usable int type. This is commonly done with the strconv package by using its Atoi function. The Atoi function takes a string and returns an integer from it or an error. If everything goes well, the value is pushed into the stack.

At the end of the range statement, just one value must be stored on it, so we just need to return it and the function is done:

func Calculate(o string) (int, error) { 
  stack := polishNotationStack{} 
  operators := strings.Split(o, " ") 
 
for _, operatorString := range operators { 
    if isOperator(operatorString) { 
      right := stack.Pop() 
      left := stack.Pop() 
      mathFunc := getOperationFunc(operatorString) 
      res := mathFunc(left, right) 
      stack.Push(res) 
    } else { 
      val, err := strconv.Atoi(operatorString) 
      if err != nil { 
        return 0, err 
      } 
 
      stack.Push(val) 
    } 
  } 
  return int(stack.Pop()), nil
}

Time to run the tests again:

$ go test -v .
ok

Great! We have just created a reverse polish notation interpreter in a very simple and easy way (we still lack the parser, but that's another story).

In this example, we haven't used any interfaces. This is not exactly how the Interpreter design pattern is defined in more object-oriented languages. However, this example is the simplest example possible to understand the objectives of the language and the next level is inevitably much more complex and not intended for beginner users.

With a more complex example, we will have to define a type containing more types of itself, a value, or nothing. With a parser, you create this abstract syntax tree to interpret it later.

The same example, done by using interfaces, would be as in the following description section.

The main interface we are going to use is called the Interpreter interface. This interface has a Read() method that every symbol (value or operator) must implement:

type Interpreter interface { 
  Read() int 
} 

We will implement only the sum and the subtraction from the operators and a type called Value for the numbers:

type value int 
 
func (v *value) Read() int { 
  return int(*v) 
} 

The Value is a type int that, when implementing the Read method, just returns its value:

type operationSum struct { 
  Left  Interpreter 
  Right Interpreter 
} 
 
func (a *operationSum) Read() int { 
  return a.Left.Read() + a.Right.Read() 
} 

The operationSum struct has the Left and Right fields and its Read method returns the sum of each of their Read methods. The operationSubtract struct is the same but subtracting:

type operationSubtract struct { 
  Left  Interpreter 
  Right Interpreter 
} 
 
func (s *operationSubtract) Read() int { 
  return s.Left.Read() - s.Right.Read() 
} 

We also need a Factory pattern to create operators; we will call it the operatorFactory method. The difference now is that it not only accepts the symbol but also the Left and Right values taken from the stack:

func operatorFactory(o string, left, right Interpreter) Interpreter { 
  switch o { 
  case SUM: 
    return &operationSum{ 
      Left: left, 
      Right: right, 
    } 
  case SUB: 
    return &operationSubtract{ 
      Left: left, 
      Right: right, 
    } 
  } 
 
  return nil 
} 

As we have just mentioned, we also need a stack. We can reuse the one from the previous example by changing its type:

type polishNotationStack []Interpreter 
 
func (p *polishNotationStack) Push(s Interpreter) { 
  *p = append(*p, s) 
} 
 
func (p *polishNotationStack) Pop() Interpreter { 
  length := len(*p) 
 
  if length > 0 { 
    temp := (*p)[length-1] 
    *p = (*p)[:length-1] 
    return temp 
  } 
 
  return nil 
} 

Now the stack works with Interpreter pointers instead of int but its functionality is the same. Finally, our main method also looks similar to our previous example:

func main() { 
  stack := polishNotationStack{} 
  operators := strings.Split("3 4 sum 2 sub", " ") 
 
  for _, operatorString := range operators { 
    if operatorString == SUM || operatorString == SUB { 
      right := stack.Pop() 
      left := stack.Pop() 
      mathFunc := operatorFactory(operatorString, left, right) 
      res := value(mathFunc.Read()) 
      stack.Push(&res) 
    } else { 
      val, err := strconv.Atoi(operatorString) 
      if err != nil { 
        panic(err) 
      } 
 
      temp := value(val) 
      stack.Push(&temp) 
    } 
  } 
 
  println(int(stack.Pop().Read())) 
} 

Like before, we check whether the symbol is operator or value first. When it's a value, it pushes it into the stack.

When the symbol is an operator, we also take the right and left values from the stack, we call the Factory pattern using the current operator and the left and right values that we just took from the stack. Once we have the operator type, we just need to call its Read method to push the returned value to the stack too.

Finally, just one example must be left on the stack, so we print it:

$ go run interpreter.go
5

This pattern is extremely powerful but it must also be used carefully. To create a language, it generates a strong coupling between its users and the functionality it provides. One can fall into the error of trying to create a too flexible language that is incredibly complex to use and maintain. Also, one can create a fairly small and useful language that doesn't interpret correctly sometimes and it could be a pain for its users.

In our example, we have omitted quite a lot of error-checking to focus on the implementation of the Interpreter. However, you'll need quite a lot of error checking and verbose output on errors to help the user correct its syntax errors. So, have fun writing your language but be nice to your users.