Quotient Zone Exclusion

Interpreter

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

At first sight it seems a little hard to find uses for this pattern. The example in GoF is a regular expression matching interpreter which most of us either take for granted or do without. However, the first sentence of the motivation gives a clue as to how to use this pattern:

If a particular type of problem occurs often enough, then it might be worthwhile to express instances of the problem as sentences in a simple language.

Examples

Warning: this pattern is not Parser. It specifically does not address the issue of parsing your sentence.

Method:

First define your grammar, and then construct a class hierarchy that describes your grammar. Each rule is a class; each symbol in the rule is an instance of the class.

Example: Graph Drawing

Suppose your are writing a graph drawing application. You want to graph simple functions such as y = 2x^2 + ln x + 1. This is a simple sentence in mathematics. The grammar may be described something like

constant ::= '0'|'1'| ... |'9'| {'0'|...|'9'}* |
{'0'|...|'9'}*'.'{'0'|...|'9'}*
variable ::= 'x'
add ::= expression '+' expression
subtract ::= expression '-' expression
multiply ::= expression '*' expression
divide ::= expression '/' expression
power ::= expression '^' expression
unary ::= '-'expression | 'ln('expression')' |
'sin('expression')'|...|'function('expression')'
expression ::= constant | variable | add | subtract | multiply |
divide | power | unary | '('expression')'

There are two types of expression class: those that represent terminal expressions (they hold no references to further expression classes) e.g. constant and variable, and non-terminal classes which are typically rules that represent compound expressions.

Classes representing the binary operators add, subtract, multiply, divide and power may be written as

public class Addition extends AbstractExpression {
private AbstractExpression left, right ;
public Addition(AbstractExpression left,
AbstractExpression right) {
this.left = left ;
this.right = right ;
}
}

while those representing unary expressions will be similar but take a single AbstractExpression. Finally:

public class Constant extends AbstractExpression {
private double value ;
public Constant(double value) {
this.value = value ;
}
}

and the class representing the variable has nothing in it so far.

public class Variable extends AbstractExpression {
public Variable() {}
}

As mentioned above, the problem this pattern does not address is that of parsing sentences in the grammar. Specifically it provides no way to get from the equation y = 2 * x^2 + ln(x) + 1 to its class representation. This is someone else's problem. The class representation looks something like:

Addition
_________/ \_________
/ \
Multiplication Addition
/ \ / \
Constant Power Logarithm Constant
/ \ |
/ \ |
/ \ |
Variable Constant Variable

Where the lines represent is a member of.

Finally, we must implement an interpret method for each concrete subclass of AbstractExpression. In this case we shall make interpret a member function of the concrete subclasses. It will take a double as its single parameter. The way the graph drawing program will use this structure is as follows. Suppose it wants to graph the equation above with the x-range from 0 to five, plotting points every 0.1. Then it would call interpret on the structure above for each value of x from 0 to 5 in intervals of 0.1. Let the top addition class be a field called function. The the program would do

for (double x = 0; x<=5; x += 0.1) {
double y = function.interpret(x) ;
plot(x, y) ;
}

Now, the interpret function is implemented as:

public class Addition {
double interpret (double x) {
return left.interpret(x) + right.interpret(x) ;
}
}
 public class Logarithm {
double interpret (double x) {
return Math.log(expression.interpret(x)) ;
}
}
 public class Constant {
double interpret (double x) {
return value ;
}
}
 public class Variable {
double interpret (double x) {
return x ;
}
}

That's all there is to it!

Here are some consequences:

Implementation details: