Design Patterns Uncovered: The Interpreter Pattern

Today's pattern is the Interpreter pattern, which defines a grammatical representation for a language and provides an interpreter to deal with this grammar.

Interpreter in the Real World 

The first example of interpreter that comes to mind, is a translator, allowing people to understand a foreign language. Perhaps musicians are a better example: musical notation is our grammar here, with musicians acting as interpreters, playing the music.

Design Patterns Refcard
For a great overview of the most popular design patterns, DZone's Design Patterns Refcard is the best place to start. 

The Interpreter Pattern

The Interpreter pattern is known as a behavioural pattern, as it's used to manage algorithms, relationships and responsibilities between objects.. The definition of Interpreter as provided in the original Gang of Four book on Design Patterns states: 

Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

The following diagram shows how the interpreter pattern is modelled.

 

Context contains information that is global to the interpreter. The AbstractExpression provides an interface for executing an operation. TerminalExpression implements the interpret interface associated with any terminal expressions in the defined grammar. 

The Client either builds the Abstract Syntax Tree, or the AST is passed through to the client. An AST is composed of both TerminalExpressions and NonTerminalExpressions. The client will kick off the interpret operation. Note that the syntax tree is usually implemented using the Composite pattern

The pattern allows you to decouple the underlying expressions from the grammar. 

When Would I Use This Pattern?

The Interpreter pattern should be used when you have a simple grammar that can be represented as an Abstract Syntax Tree. This is the more obvious use of the pattern. A more interesting and useful application of Interpreter is when you need a program to produce different types of output, such as a report generator. 

So How Does It Work In Java?

I'll use a simple example to illustrate this pattern. We're going to create our own DSL for searching Amazon. To do this, we'll need to have a context that uses an Amazon web service to run our queries.

//Context 
public class InterpreterContext
{
	//assume web service is setup
	private AmazonWebService webService;
   
	public InterpreterContext(String endpoint)
	{	
		//create the web service.
	}
   
	public ArrayList<Movie> getAllMovies()
	{
	   return webService.getAllMovies();
	}
	
	public ArrayList<Book> getAllBooks()
	{
	  return webService.getAllBooks();
	
	}
}

Next, we'll need to create an abstract expression: 

//Abstract Expression 
public abstract class AbstractExpression
{
   public abstract String interpret( InterpreterContext context);
}

We'll have many different expressions to interpret our queries. For illustration,let's create just one: 

//Concrete Expression 
public class BookAuthorExpression extends AbstractExpression
{

	private String searchString;

   public BookAuthorExpression(String searchString)
   {
		this.searchString = searchString;
   }

   public String interpret(InterpreterContext context)
   {
		ArrayList<Book> books = context.getAllBooks();
		StringBuffer result = new StringBuffer();
		for(Book book: books)
		{
			 if(book.getAuthor().equalsIgnoreCase(searchString))
			 {
				result.append(book.toString());
			 }
		}
		return result;
		
   }

}

Finally, we need a client to drive all of this. Let's assume that our language is of the following type of syntax: 

books by author 'author name'

The client will determine which expression to use to get our results: 

//client 
public class AmazonClient 
{
 
 private InterpreterContext context;
 
 public AmazonClient(InterpreterContext context)
 {
	this.context = context;
 }
 
 /**
  * Interprets a string input of the form 
  *   movies | books by title | year | name '<string>'
  */
 public String interpret(String expression)
 {
	//we need to parse the string to determine which expression to use 
	
	AbstractExpression exp = null; 
	
	String[] stringParts = expression.split(" ");
	
	String main = stringParts[0];
	String sub = stringParts[2];
	
	//get the query part
	String query = expression.substring(expression.firstIndexOf("'"), expression.lastIndexOf("'"));
	
	
	if(main.equals("books"))
	{
		if(sub.equals("title")
		{
		  exp = new BookTitleExpression(query);
		}
		if(sub.equals("year")
		{
		   exp = new BookYearExpression(query);
		}
	}
	else  if(main.equals("movie"))
		  {
			//similar statements to create movie expressions
		  }
		  
		  
	if(exp != null)
	{
		exp.interpret(context);
	}
	
	
 }
 
 
 public static void main(String[] args) 
 {
	InterpreterContext context  = new InterpreterContext("http://aws.amazon.com/");
	AmazonClient client = new AmazonClient();
	
	//run a query
	String result = client.interpret("books by author 'John Connolly'");
	
	System.out.println(result);
 }

}

I admit the example is a bit simple, and you would probably have a more intelligent context, but that should give you the idea of how this pattern works.

Watch Out for the Downsides

Efficiency is a big concern for any implementation of this pattern. Introducing your own grammar requires extensive error checking, which will be time consuming for the programmer to implement, and needs careful design in order to run efficiently at runtime. Also, as the grammar becomes more complicated, the maintainence effort is increased. 

Other Articles in This Series
The Observer Pattern
The Adapter Pattern
The Facade Pattern
The Factory Method Pattern
The Abstract Factory Pattern
The Singleton Pattern
The Strategy Pattern
The Visitor Pattern
The Decorator Pattern
The Proxy Pattern
The Command Pattern
The Chain of Responsibility Pattern

Next Up

As we've mentioned the Composite pattern in this article when dealing with Abstract Syntax Trees, I'll cover Composite in the next article.