The Power of Interpreter Design Pattern in JavaScript

In this post we will go over the Interpreter Design Pattern in JavaScript. We will implement an Interpreter as well as basic grammatical representations of a source code. We will create an interface for client codes to use (like parsers for example)

Design patterns falls into three categories: Behavioral, Creational, and Structural. The Interpreter belongs to the behavior group. Of all patterns, the interpreter seems to be the most confusing to people, but in my experience thinking in a higher level perspective (outside the box) will help make that light bulb in our minds suddenly light everything up.

When do we need to apply the Interpreter Pattern?

Sometimes we might come across situations where we need some interface to tell an interpreter how to interpret based on a particular context. This pattern is also used extensively in SQL parsing, symbol processing engines, etc.

Think of it sort of like creating a scripting "language".

For example, arrays can contain more arrays in one of its indexes which can contain more arrays, etc:

const items = [
  {
    profile: {
      username: 'bob',
      members: [
        {
          username: 'mike',
        },
        {
          username: 'sally123',
        },
        {
          username: 'panera',
          members: [
            {
              username: 'sonOfPanera',
            },
          ],
        },
      ],
    },
  },
]

The goal is to create a some sort of a "grammar" representation that is in most cases capable of recursion.

When we look at its structure, each part in the grammar representation is either a composite or a leaf of a tree. In a higher level perspective notice how these grammatical representations form the structure of the composite design pattern:

Notice how there are some children that contain more children and the depth increases as much as it needs. This is where recursion is crucial and becomes necessary in traversal algorithms.

The main participant in this pattern is the interpreter itself.

Implementing the Interpreter and Grammar Representations

Let's go ahead and create the interpreter. The interpreter will have an interpret method which will be in charge of running through our code and producing tokens out of them. These tokens will contain rules that the interpreter will need to create combinatorial expressions so that client code such as parsers will understand:

Let's look at the first line (we'll initiate this as an empty array to make it simpler to understand as we go along):

const items = []

If we were to read through this line in code, how do we manipulate the name items to collection?

We can read it line by line and do it with something like this:

let srcCode = `const items = [`

let prevChar
let nextChar

for (let index = 0; index < srcCode.length; index++) {
  nextChar = srcCode[index + 1]

  const char = srcCode[index]

  if (
    char === 'i' &&
    nextChar === 't' &&
    srcCode[index + 2] === 'e' &&
    srcCode[index + 3] === 'm' &&
    srcCode[index + 4] === 's'
  ) {
    srcCode = srcCode.split('')
    srcCode = [
      ...srcCode.slice(0, index),
      'collection',
      ...srcCode.slice(index + 'items'.length),
    ].join('')
  }

  prevChar = char
}

However, this isn't very efficient because there isn't a reliable way to peek previous/next indexes as well as being able to tell which line or column begins with certain expressions, declarations, etc. We also don't have a way to do useful things like being able to update the the kind of declarator (var, let, const).

When we utilize the Interpreter pattern we create an actual interface that will take that code, connect related objects together that represent parts of the grammar accordingly and instruct the interpreter on what to do with them (remember, each one of those objects have their own rules that guide the interpreter) and produce output that can be understood by client code like parsers.

So, going back to this line:

const items = []

We can create an interface instead. Now keep in mind that this interface is the most powerful part of this pattern since we can customize each class to do anything we want, like override the default toString method:

class VariableDeclaration {
  constructor() {
    this.kind = null
    this.declarations = []
  }
  toString() {
    let output = ''

    output += `${this.kind} `

    this.declarations.forEach((declaration) => {
      output += declaration.toString()
    })

    return output
  }
}

class VariableDeclarator {
  constructor() {
    this.id = null
    this.init = null
  }
  interpret() {
    return this.init.interpret()
  }
  toString() {
    let output = ''
    output += this.id.toString()
    output += ' = '
    output += this.init.toString()
    return output
  }
}

class ArrayExpression {
  constructor() {
    this.elements = []
  }
  toString() {
    let output = ''

    output += '['

    this.elements.forEach((elem) => {
      output += elem.toString()
    })

    output += ']'

    return output
  }
}

class Identifier {
  constructor(name) {
    this.name = name
  }
  toString() {
    return this.name
  }
}

Perfect! This is the Interpreter Design Pattern in action! We now have some representations for our grammar.

This pattern is very powerful. With this interface in place we can see that we overwritten all of the default toString methods on each class to structure for our domain.

Next we need an interpreter to take in source code and read through them. Our interpreter will be a much more simplified version of those used in actual practice. For the sake of this post I only included the parts necessary to fully represent our one liner:

class Interpreter {
  interpret(srcCode = '') {
    let nodes = []
    let words = srcCode.split(/(\s|\r|\n|\t\|=|\.|\]|\[)/)

    for (let index = 0; index < words.length; index++) {
      const word = words[index]
      if (/var|let|const/.test(word)) {
        const kind = ['var', 'let', 'const'].find((char) => word.includes(char))
        const variableName = words[index + 2]

        words.shift()
        words.shift()
        words.shift()
        words.shift()
        words.shift()
        words.shift()
        words.shift()

        const declaration = new VariableDeclaration()
        const declarator = new VariableDeclarator()
        const variable = new Identifier(variableName)

        if (words[0] === '[') {
          declarator.init = new ArrayExpression()
        }

        declaration.kind = kind
        declaration.declarations = [declarator]
        declarator.id = variable

        nodes.push(declaration)
      }
    }

    return nodes
  }

  toString(nodes) {
    let output = ''

    for (const node of nodes) {
      output += node.toString()
    }

    return output
  }
}

With this in place, the client code can utilize our interpreter and manipulate our line of code:

const interpreter = new Interpreter()
const interpreted = interpreter.interpret(srcCode)
const newCode = interpreter.toString(interpreted) // `const items = []`

const interpreter = new Interpreter()
const interpreted = interpreter.interpret(srcCode)

if (interpreted[0] instanceof VariableDeclaration) {
  interpreted[0].declarations[0].id.name = 'collection'
}

const newCode = interpreter.toString(interpreted) // `const collection = []`

Context

Context objects are commonly used in conjunction Interpreters. If we can override toString in all of our grammar representations objects, we can definitely improve the power of our interpreter by entering in useful state information into an object called the context.

For example, we can give the client code the ability to skip undefined values when constructing array expression outputs:

Tips with other patterns

• The Interpreter pattern is most powerful when working with composite structures. In other words combining the composite pattern with the interpreter pattern is a must when dealing with composite structures.

• In the builder pattern, a builder can be used to create hierarchical structures as grammatical representations of a language and allow the client to use them with the interpreter pattern.

• The abstract factory can be used to create complex objects (for example in javascript this can be a very long function return statement with plenty of binary expressions)

• Like the composite pattern, the visitor and iterator pattern is also powerful with the interpreter. Visitors are often implemented with a recursive traversal algorithm that implement the iterator pattern in itself. Interpreters can utilize visitors to traverse composite trees.

Conclusion

Thank you for reading and look forward for more quality posts coming from me in the future!