[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]

COMP2100/2500
Lecture 9: Recursive Data Types III

Summary

The third lecture on recursive data types. This lecture answers the question posed at the end of the last lecture, creating a more flexible form of expression tree.

---

Data types with a Visitor Facility

If the class hierarchy representing the recursive data type isn't going to change much but we might want to add more and more operations, it may make sense to define a corresponding Visitor class hierarchy and add appropriate accept() methods to the classes of the original hierarchy.

Here is the abstract (deferred) class that we would need for Expressions. Notice that we need a routine for each of the classes in the original hierarchy, and each method takes one parameter which is an instance of that class.

public abstract class ExpressionVisitor {

    public abstract void visitConstant(Constant4 c);

    public abstract void visitAddition(Addition4 a);

    public abstract void visitMultiplication(Multiplication4 m);

    public abstract void visitNegation(Negation4 n);
}

---

Expression Implementation (Version 4)

Class Expression4 is now pretty simple.

public abstract class Expression4 {

    public abstract void accept(ExpressionVisitor visitor);

}

The different subclasses implement accept(), which tells expression visitors what type they are and thus which of their routines to run on them.

public class Constant4 extends Expression4 {

    int value;

    public Constant4(int v) {
	value = v;
    }

    public void accept(ExpressionVisitor visitor) {
	visitor.visitConstant(this);
    }
}

---

public class Addition4 extends Expression4 {

    Expression4 left, right;
   
    public Addition4(Expression4 l, Expression4 r) {
	left = l;
	right = r;
    }
   
    public void accept(ExpressionVisitor visitor) {
	visitor.visitAddition(this);
    }
}

Classes for Multiplication and Negation are similar.

Note that the fields in these classes (value in Constant and left and right in Addition) have no visibility modifier (public, protected or private). This means that these fields have package visibility. Only instances of classes in the same package can access this field. If we organise our program so that Expression and its subclasses, and ExpressionVisitor and its subclasses are all in the same package (and nothing else is), then this will work correctly. Those fields will be accessible to the classes that need access, but hidden from everything else. Alternatively we would have to do the usual nonsense with making the fields private and having public accessor methods.

Now we can define visitors to evaluate and format Expressions.

public class ExpressionEvaluator extends ExpressionVisitor {

    /** The calculated value */
    private int value;

    /** public view of the value */
    public int getValue() { return value; }

    /** Get the value of a constant expression */
    public void visitConstant(Constant4 c) {
	value = c.value;
    }

    /** Get the value of a sum */
    public void visitAddition(Addition4 a) {
	ExpressionEvaluator leftEvaluator = new ExpressionEvaluator();
	ExpressionEvaluator rightEvaluator = new ExpressionEvaluator();
	a.left.accept(leftEvaluator);
	a.right.accept(rightEvaluator);
	value = leftEvaluator.value + rightEvaluator.value;
    }

    /** Get the value of a product */
    public void visitMultiplication(Multiplication4 a) {
	ExpressionEvaluator leftEvaluator = new ExpressionEvaluator();
	ExpressionEvaluator rightEvaluator = new ExpressionEvaluator();
	a.left.accept(leftEvaluator);
	a.right.accept(rightEvaluator);
	value = leftEvaluator.value * rightEvaluator.value;
    }

    /** Get the value of a negation */
    public void visitNegation(Negation4 n) {
	n.expression.accept(this);
	value = -value;
    }
}

---

public class ExpressionFormatter extends ExpressionVisitor {

    /** The formatted string being built  */
    private String string;
    
    /** Public access to the string */
    public String getString() { return string; }

    /** Initialise with an empty string */
    public ExpressionFormatter() {
	string = "";
    }

    /** Get the string for a constant */
    public void visitConstant(Constant4 c) {
	string += c.value;
    }

    /** Build the string for a sum */
    public void visitAddition(Addition4 a) {
	string += "(";
	a.left.accept(this);
	string += " + ";
	a.right.accept(this);
	string += ")";
    }

    /** Build the string for a product */
    public void visitMultiplication(Multiplication4 a) {
	string += "(";
	a.left.accept(this);
	string += " * ";
	a.right.accept(this);
	string += ")";
    }

    /** Build the string for a negation */
    public void visitNegation(Negation4 n) {
	string += "-(";
	n.expression.accept(this);
	string += ")";
    }
}

This design leads to a delicate (confusing?) exchange of messages between the objects in an expression tree and the objects performing operations on them.

The reason for this apparent complexity is that this is an example of double dispatch. If I make the routine call ‘expression.accept(visitor)’, the actual operation that is carried out depends on two runtime types: the actual type of ‘expression’ and that of ‘visitor’.

(Usually only the type of the target matters. That is, in a method call a.b(), the version of b() that actually executes is determined at runtime based on the actual type of a. This is called dynamic dispatch.)

---

Using Expression (Version 4)

Expression4 a, b, c, d, e;
ExpressionFormatter f = new ExpressionFormatter();
ExpressionEvaluator v = new ExpressionEvaluator();

a = new Constant4(1);
b = new Constant4(2);
c = new Addition4(a, b);
a = new Constant4(3);
b = new Constant4(4);
d = new Addition4(a, b);
e = new Multiplication4(c, d);

e.accept(f);
e.accept(v);
System.out.println(f.getString() + " = " + v.getValue());

---

Assessment of Expression (Version 4)

+ Class Expression is now very simple.

+ Easy to create new visitors for Expression without modifying any existing classes.

+ No subtle manipulation of object references.

+ Each expression type has only relevant attributes.

+ All the code for a particular operation is in the one concrete subclass of ExpressionVisitor, rather than spread across all the different subclasses of Expression.

- Interaction between Expression and ExpressionVisitor is subtle.

- Difficult to add new kinds of expression, e.g., division.

• ExpressionVisitor must be modified to add a new routine for division.

• All subclasses (here ExpressionEvaluator and ExpressionFormatter) must now implement the new routine.

This style of interaction is called the Visitor pattern.

---

Extension work

• Find a book on design patterns and learn about the Visitor pattern.

• Learn a functional programming language (e.g. Haskell, Miranda or Lisp) and compare the higher-order functions map and fold with the Visitor pattern. Is the Visitor pattern just a trick for getting around the limitations of languages like Java, Eiffel and C++?

[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]