'''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''
	* Simple pattern matching
	* Building a GUI widget based on a set of properties or a resource bundle
	* Graph drawing program
	* Processing an XML document
	* Anything that requires parsing

'''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 Abstract''''''Expression {
       private Abstract''''''Expression left, right ;
       public Addition(Abstract''''''Expression left,
 		       Abstract''''''Expression 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 Abstract''''''Expression {
       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 Abstract''''''Expression {
       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:
	* It is easy to implement the grammar
	* It is easy to change the grammar
	* Complex grammars are hard to maintain	
	* It is easy to add new ways of interpreting sentences

Implementation details:
	* No hints about parsing
	* Don't have to put ''interpret'' in the expression classes; we can 	  use Visitor, for example, or Iterator
	* We can share terminal symbols using Flyweight