Evaluating Software Design Patterns
— the "Gang of Four" patterns implemented in Java 6

@Pattern(name="Interpreter", scope=Class, purpose=Behavioural, participants={"AbstractExpression","TerminalExpression","NonTerminalExpression","Context","Client"})

Package dk.rode.thesis.interpreter

Implementations and examples of the Interpreter design pattern [Gamma95, p.243].


Interface Summary
Expression<E> An expression represents grammar rules in form or non terminal expressions and actual functionality in form of terminal expressions that will be enforced when the expression is evaluated.
InitialisableExpression<E> An initialisable expression represents an expression that require several steps to be constructed, and hence must be initialised before actual use.
NonTerminalExpression<E> A non terminal expression represents a grammar rule, but this interface is a marker interface only as it offers no specific functionality.
TerminalExpression<E> A terminal expression represents an operation to be performed on a given sequence, but this interface is a marker interface only as it offers no specific functionality.
TypedExpression<E> A typed expression exposes the type of the value its evaluation produces via its TypedExpression.type() method.

Class Summary
AbstractExpression<E> An abstract expression represents the basic traits of any expression.
AndExpression A logical and expression for two expressions evaluating to a Boolean value.
AssignmentExpression<E> An assignment expression assigns the result of the evaluation of an expression to a variable.
BinaryExpression<T,E> A binary expression represents any expression that involves (at least) two sub-expressions as operands.
BreakExpression<E> A break expression allows the interpretation of a given expression syntax-tree to break at the point of the break expression, and possibly continue the interpretation starting from a specified target expression.
CompareExpression<E extends Comparable<? super E>> A compare expression can compare two expressions evaluating to the same Comparable type as smaller than, smaller than or equal, equal, not equal, greater than, or equal or greater than.
ConditionalExpression<E> A conditional expression represents an if-then-else expression.
ConstantExpression<E> A constant expression represents an expression that can be assigned a constant value.
Context A context represents an evaluation context where variables (and constants) are stored during interpretation.
CurrentExpression<E> A current expression will invoke current() on a given sequence when evaluated.
EqualExpression An equal expression can determine if the result of evaluating two expressions is equal or not, regardless of types.
Expression.SymbolIdiom The symbol idiom ensures that cyclic expression references will be represented correctly in symbolic representation starting from a given expression.
FlowExpression<E> A flow expression represents one or more expressions to be evaluated in order, one at a time.
Interpreter<T> An interpreter can interpret expressions.
Main Interpreter tests.
NextExpression<E> A next expression will invoke next() a number of times on a given sequence when evaluated.
NotExpression A not expression (!)
OrExpression A logical or expression for two expressions evaluating to a Boolean value.
ResetExpression<E> A reset expression will invoke reset() on a given sequence when evaluated.
ReverseExpression<E> A reverse expression will invoke reverse() on a given reversible sequence when evaluated, if so specified and only if possible.
SequenceExpression<T,E> A sequence expression represents a terminal expression used to manipulate a given sequence.
SetExpression<E extends Comparable<? super E>> A set expression will fast-forward the value of a given bounded sequence to match a specific value, if possible.
TypedExpressionDecorator<E> A type expression decorator allows any expression to be explicitly associated with the type of the values the evaluation of it will produce.
VariableExpression<E> A variable expression represents an expression that can be assigned a given value, which will be stored in a given context supplied at evaluation time.

Enum Summary
CompareExpression.Comparison The comparison type to be performed by a compare expression.

Exception Summary
BreakExpression.BreakException A break exception is thrown when an break expression is evaluated.
ExpressionException An expression exception is thrown in case of context, evaluation, or expression errors.

Package dk.rode.thesis.interpreter Description

Implementations and examples of the Interpreter design pattern [Gamma95, p.243].


Here, a small language have been constructed that can manipulate Sequence objects and perform simple tests using boolean expressions that may or may not depend on sequence values.

The AbstractExpression participant is represented by the Expression interface. Any expression can be evaluated by invoking its Expression.evaluate(Context) method, but the Interpreter class should be used for interpretation.

The TerminalExpression participant is represented by literals that describe sequence actions, such as 'next' for Sequence.next(), 'reset' for Sequence.reset(), etc. The TerminalExpression marker interface denotes terminal symbols, and any terminal expression manipulating a given Sequence inherits the SequenceExpression class. The 'next' literal, for example, is represented by the NextExpression class. The other terminal expressions are CurrentExpression, SetExpression, ResetExpression, and ReverseExpression.

The grammar rules are represented by the NonTerminalExpression participant. In this package, each class that implements the marker interface NonTerminalExpression is a non terminal. Examples include FlowExpression, ConditionalExpression, AssignmentExpression, etc.

The Context participant is represented by the Context class, which can store both variables and constants.

The Client participant is the test application, i.e. the Main class.

Below, an informal description of the grammar is presented:

    expression            ::= literal | constant | assignment | condition | argument | flow | '(' expression ')' | break
    flow                  ::= expression ',' expression
    break                 ::= expression (break and evaluate) | null (terminate)
    argument              ::= expression<literal> '[' expression ']'   
    expression<literal>   ::= current-expression | next-expression | set-expression | reset-expression | reverse-expression
    expression<boolean>   ::= and-expression | or-expression | not-expression | equal-expression | comparison-expression
    and-expression        ::= expression1<boolean> '&&' expression2<boolean>  
                            | expression1<boolean> '&'  expression2<boolean> 
    or-expression         ::= expression1<boolean> '||' expression2<boolean> 
                            | expression1<boolean> '|'  expression2<boolean>
    not-expression        ::= '!' expression<boolean>
    equal-expression      ::= expression1 '==' expression2 
    comparison-expression ::= expression1<comparable> '<'  expression2<comparable>
                            | expression1<comparable> '==' expression2<comparable>
                            | expression1<comparable> '>'  expression2<comparable> 
    condition             ::= expression<boolean> '?' expression1 ':' expression2
    assignment            ::= variable '=' expression
    constant              ::= any 
    variable              ::= [a-zA-Z]+ 
    literal               ::= 'current' | 'next' | 'set' | 'reset' | 'reverse'
Precedence is the responsibility of the object that constructs the syntax-tree (here, the Main class). Cyclic expression references based on identity is allowed at the discretion of the developer at the cost of a potentially very deep call stack. Certain expressions methods will not function properly in case of cyclic references, though! Furthermore, in general, there is no guarantee that the interpretation of a given expression and/or syntax tree will terminate!

An example of a syntax-tree for manipulating a single Sequence, say foo, could be:

   1     next[20], 
   2     y = current, 
   3     reverse 
   4       ? next[10], x = current, x < 11 
   5                                  ? x 
   6                                  : break[y] 
   7       : exit
Which reads:

  1. call next() 20 times on foo;
  2. set the value of y to the current value of foo;
  3. try and reverse foo
  4. if reversed (line 3), call next() 10 times on foo, set x to the current value of foo, and test if x is smaller than 11;
  5. if x is smaller, return x;
  6. if x is equal or larger, break out of the current evaluation, and transfer control to y, which will be evaluated and its result returned;
  7. if not reversed (line 3), exit evaluation with no value (null).

If foo is a reversible integer sequence having the initial value 1, the evaluation exits by evaluating y in line 6, which yields 21 because of the assignment in line 2; y could be any kind of expression, not just simple values. If the initial value is 0, the evaluation stops normally and returns 10, which is the value of x in line 5. Assuming foo is not reversible in line 3, null will be returned from line 7.

UML Class Diagram:

Implementation notes:
The Expression interface is generic, having a single type parameter, E, that specifies the type of value returned by the evaluation. An implication of this is that a given syntax-tree can only evaluate expressions evaluating the same (sub-) type of values. As Sequence objects are the target of the terminal expressions, the type parameter of the given sequence is often what determines the value of E. The Gamma et al. examples all operate on a single type only, e.g. boolean or string, and the type is fixed! This is not the case here: any Sequence can be used, regardless of which values it deliver. Furthermore, some expressions can operate on sub-types of expression values, i.e. <? extends E>, as is the case with AssignmentExpression and FlowExpression, for example. When collaborating with Context and AssignmentExpression, VariableExpression type allows polymorphic values as well.

More so, the type parameter provide type safety and makes certain things easier. There is, for example, no need for a specific boolean expression class, since any type matching Expression<Boolean> will do, and we do not have to cast the result of the evaluation to the desired type. However, certain things become much more difficult with type parameters, especially in Java where type erasure ensures that the type information is not available at runtime. For example, replacement of expressions as described in the Gamma et al. C++ example [Gamma95, p.252-254] is very tricky, if not impossible, when expressions use different type parameters, as for example the ConditionalExpression class. In ConditionalExpression, the condition is expressed as Expression<Boolean>, while the two operands are expressed as Expression<? extends E>. Clearly, the two type parameters are incompatible unless E is a Boolean or a sub-type of it; but no such sub-class exist since Boolean is declared final! Now consider a replace method declared in Expression<E> as:

   public Expression<E> replace(String name, Expression<E> exp);
How should ConditionalExpression implement this? An attempt could be the following:
 1   public Expression<E> replace(String name, Expression<E> exp) {
 2     return new ConditionalExpression<E>(
 3       this.condition.replace(name, exp),       // Expression<Boolean>
 4       this.first.replace(name, exp),           // Expression<? extends E>
 5       this.second.replace(name, exp)           // Expression<? extends E>
 6     );
 7   }    
But, lines 3-5 will generate compiler errors because of incompatible types. Replacing E with <? extends E> in the method signature will not help. Pure will cards cannot be utilised either as the type information is vital for the condition check to work and for the creating of a new expression eventually when an actual replacement occurs. Hence, the Expression type do not have a such a replace method.

Of cause, one could simply choose not to use type parameters and store Class objects in expression with the type information, but then compile-time type safety is gone.

Here, we provide a mixture of the two approaches: the Expression interface uses type parameters to enforce compile-time type safety for expressions as well the sequences they operate on at the expense of replacement of existing expressions, but we also provide the TypedExpression interface that can associate the type of the expression values with the expression it self at runtime.

An example of explicit usage of type parameters is the NextExpression class. It can use any expression of the type Expression<? extends Number> to deliver the number of times next() should be invoked on a given sequence. An example where the type of the expression value must be known is the BreakExpression class. It aids the Interpreter class to transfer control to any expression having a sub-type of the original expression value type. Furthermore, the TypedExpressionDecorator class can be used to associate any expression with type of the expression value to which it evaluates.

In line with the Gamma et al. definition of an interpreter (method) [Gamma95, p.255], Expression declares a Expression.copy(), a Expression.asSymbol(Context), and a Expression.contains(Expression) method as well, the latter quite similar in nature to the replacement functionality described by Gamma et al.

The traversal of the expression syntax tree is handled by the expressions themselves, though with some aid from the Context class. External visitors could easily be constructed to traverse the expression graph as well, as expressions expose their composite structure in form of their expression operands. The Builder pattern illustrates such an external traversal of expressions.

There are many similarities between terminal expressions and the commands used in the Command pattern.

Gunni Rode / rode.dk

Gunni Rode / rode.dk

Feel free to use and/or modify the Java 6 source code developed for this thesis AT YOUR OWN RISK, but note that the source code comes WITHOUT ANY — and I do mean WITHOUT ANY — form of warranty WHAT SO EVER!

The original thesis and source code are available at rode.dk/thesis.