Home

Documentation

* Programming Guide * CJDT User Guide * Publications * Tutorial * Language Spec.

Examples

Downloads

Source Code

FAQ

Community Info

About Us

 

 
Search:
 
ST Logo
TUD Logo
<< Observer Example | Contents | Subject-Oriented Views >>

Expression Problem

Overview

Supposing we have a data hierarchy and a set of algorithms which operate on that hierarchy. Extending this structure we can go in two directions, namely, (1) we can extend the data hierarchy, by appending new leafs, or (2) we can add new operations working on that hierarchy. This is called expression problem. What we want to achieve is: (i) extensibility in both dimensions, (ii) strong static type safety, (iii) avoiding code duplication or modification.

Let us consider the structure of the abstract syntax tree of a small programming language capable of understanding simple integer addition.

 
EXPR ::= EXPR + EXPR | LITERAL
LITERAL ::= [0|...|9]* 

Transformed to a class hierarchy we get following structure:

 
public abstract class Expression {...}
public class AddExpression extends Expression {
   Expression left, right;
   ...
}
public class Literal extends Expression {...}

Now let us consider the extensibility in both dimensions. Adding new data types is a simple task using OOP techniques. However, adding new algorithms operating on the AST is rather complicated. Using common OOP techniques we have two solutions: interpreter pattern and visitor pattern.

(1) Interpreter Pattern
The AST elements implement from a common interface, which declares the operations available.
 
public abstract class Expression {
	public abstract void op1();
	public abstract void op2();
	...
}
This makes adding of new types easy, but the drawback is, if we want to add a new operation, we have to change the interface, which results in changing every implementing class.

(2) Visitor Pattern
The idea behind the visitor pattern is to encapsulate the functionality in a single class. However, this method has the drawback, that adding a new type requires modification of the whole visitor hierarchy.

Solving the Expression Problem with Caesar

In the following example we present how virtual classes can be used to solve the expression problem.

First we introduce the basic AST structure, consisting of Expression, AddExpression, and Literal.
 
public cclass AST  {
   abstract public cclass Expression {      
   }
   public cclass AddExpression extends Expression {
      protected Expression r;
      protected Expression l;

      public AddExpression(Expression l, Expression r) {
         this.r = r;
         this.l = l;
      }
   }
   public cclass Literal extends Expression { 
      protected int val;
      public Literal(int val) {
         this.val = val;         
      }
   }
}

The following code demonstrates how to add a new functionality to the AST, namely the evaluation operation.
 
public cclass EvalAST extends AST {
   abstract public class Expression {
      abstract public int eval();
   }
   public cclass AddExpression {
      public int eval() { return l.eval() + r.eval(); }
   }
   public cclass Literal {
      public int eval() { return val;	}
   }
}

Here we extend the base AST with a new data type (NegExpression).
 
public cclass NegAST extends AST {
   public cclass NegExpression extends Expression {
      protected Expression expr;
      public NegExpression(Expression expr) {
         this.expr = expr;
      }
   }
}

Here we merge the EvalAST and NegAST. Note that we only need to provide the delta of change we have introduced. The existing code has not to be touched at all.
 
public cclass EvalNegAST extends EvalAST & NegAST {
   public cclass NegExpression {  
      public int eval() {
         return -expr.eval(); }
      }
}

Finally, we demonstrate how to add an additional operation to the merged AST itself.
 
public cclass EvalPrettyPrintNegAST extends EvalNegAST {
   abstract public cclass Expression {
      abstract public String print();
   }
   public cclass AddExpression {
      public String print() {
         return "(" + l.print() + "+" + r.print() + ")";
      }
   }
   public cclass Literal {
      public String print() {
         return ""+val;
      }
   }	
   public cclass NegExpression {		
      public String print() {
         return "-(" + expr.print() + ")";
      }
   }
}

<< Observer Example | Contents | Subject-Oriented Views >>