6.170 / Spring 2001 / Lab 7: Design Patterns

Handout B7

• Purpose
  • Interpreter Pattern
• Visitor Pattern
• An Example: Calculator
  • Setup
  • Running the Code
  • Exercise 1: Object models
  • Exercise 2: Outputting expressions in prefix form
  • Exercise 3: Sequencing definitions
  • Exercise 4: Outputting expressions as textual trees

Purpose

Interpreter Pattern

expression       ::= literal | binary_operation | unary_operation
binary_operation ::= {expression '+' expression} | 
                     {expression '-' expression} | 
                     {expression '*' expression} | 
                     {expression '/' expression}
unary_operation  ::= '-' expression
literal          ::= {0|1|2|3|4|5|6|7|8|9}+ {'.'{0|1|2|3|4|5|6|7|8|9}+}?

This description basically says that the grammar is composed of expressions. Each expression is either a literal, a binary_operation, or a unary_operation. A binary_operation is then defined as an expression followed by either a '+', '-', '*' or '/'. A unary_expression is a '-' followed by an expression

The Interpreter pattern would use a class to represent each of the grammar rules defined above. Symbols on the right-hand side of the rule are instance variables of the classes that represent the left-hand side of each rule. So this grammar would be represented by 4 classes: (abstract) Expression, BinaryOperation, UnaryOperation, and Literal.

abstract class Expression {
  ...
}

class BinaryOperation extends Expression {
  ...
}

class UnaryOperation extends Expression {
  ...
}

class Literal extends Expression {
  ...
}

Often, the Interpreter pattern is used when there is a language to interpret, and you can represent statements in the language as abstract syntax trees. The Interpreter pattern works best when:

• the grammar is simple. For complex grammars, the class hierarchy for the grammar becomes large and unmanageable.
• efficiency is not a critical concern -- for instance, the structure only needs to be interpreted once. If repeated interpretation is required, the most efficient interpreters are usually not implemented by traversing parse trees directly but by first translating them into another form.

It is common for implementations of the Interpreter pattern to define an interpret() operation in each of the syntax tree classes. In that manner, interpret() operations at each node can use the context to store and access the state of the interpreter as it traverses the syntax tree. However, you don't have to define the interpret() operation in the expression classes. If it's common to create a new interpreter, then it is better to use the Visitor pattern to move the operation into a separate Visitor object.

The advantage of the Interpreter pattern is that it makes it easy to change and extend the grammar. Because the pattern uses clauses to represent grammar rules, you can use inheritance to change or extend the grammar. Existing expressions can be modified incrementally, and new expressions can be defined as variations on old ones. The disadvantage is that it is difficult to add new operations to the expression tree as it requires adding it to each expression class.

Visitor Pattern

Consider a class hierarchy of Nodes (an AbstractNode, and several subclasses of AbstractNode). Every AbstractNode can contain zero or more sub-AbstractNodes as children. Let's say that every AbstractNode defines several operations that can be performed on it, and consequently its children. (For example, a printYourself() method that prints each node in the hierarchy tree.) The problem here is that distributing all these operations across the various node classes leads to a system that is hard to understand, maintain, and change. It will be confusing to have code for multiple Node operations mixed together especially because they are all unrelated one another. Moreover, adding a new operation will require touching and recompiling all of these classes. It would be better if each new operation could be added separately, and the node classes were independent of the operations that apply to them.

We can have both by packaging related operations from each class in a separate object, called a visitor, and passing it to elements of the Node hierarchy as it is traversed. When an element "accepts" the visitor, it sends a request to the visitor that communicates its runtime type. This is often called a double-dispatch mechanism.

As a consequence of separating the operation logic from the class hierarchy on which the visitor operates, it makes it relatively easy to define new operations on the class hierarchy. It is also easy to then classify and gather related operations together and separate unrelated operations through a separate Visitor class hierarchy. However, the Visitor pattern makes adding classes to the Node hierarchy difficult, as each new Node class gives rise to a new abstract operation on Visitor and a corresponding implementation in each of its subclasses.

Descriptions of the design patterns were largely borrowed from Design Patterns: Elements of Reusable Object-Oriented Software by Gamma, Helm, Johnson, and Vlissides (more commonly referred to as the "Gang of Four" book), which contains more detailed information about these and other design patterns.

An Example: Calculator

Setup

mkdir ~/6.170/lab7 
cd ~/6.170/lab7
cp /mit/6.170/www/labs/lab7/*.java .
javac *.java

Running the Code

LET var = expression         // binds expression to var
WHO	                     // lists all bindings in current environment
CLEAR var                    // clears var from bindings
CLEAR                    // clears all bindings
QUIT                     // exits the calculator

You can start the calculator by invoking:

java lab7.Driver

Now take the calculator for a spin. Enter some commands like:

COMMAND =>  3-4
COMMAND =>  LET x = 25
COMMAND =>  x + 25
COMMAND =>  x - 3
COMMAND =>  LET y = 3*x
COMMAND =>  y
COMMAND =>  LET x = 4
COMMAND =>  y
COMMAND =>  WHO
COMMAND =>  QUIT

Exercise 1: Object models

command          ::= clear | let | 'WHO' | expression
let              ::= 'LET' var '=' expression
clear            ::= 'CLEAR' {var}?
expression       ::= literal | binary_operation | unary_operation | var
var              ::= {character}({character}|{digit})*
binary_operation ::= {expression '+' expression} | 
                     {expression '-' expression} | 
                     {expression '*' expression} | 
                     {expression '/' expression}
unary_operation  ::= '-' expression
literal          ::= {digit}+ {'.'{digit}+}?

Draw a Problem Object Model for the calculator grammar that is described above.

The Interpreter pattern makes the class hierarchy parallel the grammar definition. This makes it easier to define operations that rely on the rules of the grammar. To see this point, suppose that the implementation of the grammar looked like this:

How would that affect the implementation of the EvalVisitor?

Hint: think about how each hierarchy would evaluate the following expressions trees (assuming that the parser allowed them as input):

COMMAND =>  LET x = LET x = 3

COMMAND =>  3 + CLEAR

COMMAND =>  LET x = 3 + WHO

Exercise 2: Outputting expressions in prefix form

Examples of prefix notation are:

<+ 2 4>             // corresponds to "2 + 4" infix
<+ x <* 4 5>>       // corresponds to "x + 4 * 5" infix

Modify the method getPrintVisitor() in Driver.java to return your PrefixPrintVisitor instead.

Exercise 3: Sequencing definitions

COMMAND =>  CLEAR
COMMAND =>  LET x = 5
COMMAND =>  LET y = x + 2
COMMAND =>  y
COMMAND =>  LET x = 10
COMMAND =>  y

Now try this set of commands:

COMMAND =>  CLEAR
COMMAND =>  LET x = y + 2
COMMAND =>  LET y = 3 * x
COMMAND =>  y

Modify EvalVisitor, or create another Visitor class to curtail this aberrant behavior by throwing an EvalVisitor.RecursiveDefinitionException. This is a little tricky; think about how the EvalVisitor traverses the expression tree and how it might go about dealing with this issue.

If you get stuck on this exercise, you can copy the staff implementation by doing:

cp /mit/6.170/www/labs/lab7/.EvalVisitor.class ~/6.170/lab7/EvalVisitor.class

Exercise 4: Outputting expressions as textual trees

     +
    / \
   3   *
      / \
     4  ( )
         |
         +
        / \
       x   5

There are many other more creative representations, the key is for you to become more familiar with the ease of defining new operations on the syntax tree.