You are here: Home Teaching Comp 373/473 Handouts The Visitor Pattern
Document Actions

The Visitor Pattern

The Visitor Pattern

References

  • Gamma et al., Design Patterns and Object Oriented Programming, Pages 331-345.
  • Felleisen and Friedman, A Little Java, a Few Patterns, last chapter.

Aims

  • Introduction to a basic design pattern.

Lecture

In this material, we will explore the Visitor pattern In the last couple of lectures,we have looked at arithmetic expressions built out of +,-, *, / and constants. We had been interested in the following operations:

  • Evaluation via an inorder traversal
  • Preorder traversal for display
  • Postorder traversal for display

This had led us to begin by defining an interface to capture the desired functionality:

public interface Expr {
public void preorder();
public void postorder();
public int evaluate();
}

We had proceeded by defining a subclass for each constructor of arithmetic expressions that we are interested in. Now, let us say that we want to add a print() operation to this scenario.

A bad solution

One way to proceed would be to add the print() method to the Expr interface. Notice however, that this forces us to perform changes to the code of each and every subclass of Expr. In general, the addition of each new operation to the Expr interface causes nonlocal (ie. spread over several files) changes.

A nicer solution

An approach to a nicer solution to this problem is yielded by viewing the problem through the following light. Let Operation be a class that is intended to handle operations on Expr. Concretely, we intend the operations on Expr to arise as subclasses of Operation. For example:

  • Print would be a subclass of Operation to handle the printing
  • Evaluate would be a subclass of Operation to handle the evaluation

So, basically the situation can be visualized as a matrix of possibilities. In this matrix, we are listing the operations (ie. subclasses of Operation) along columns, and the subclasses of Expr along rows. The design of the earlier lectures, via the Composite pattern, assumed a fixed number of columns, and provided us the flexbility to add new rows (ie. new subclasses of Expr). In this lecture, we desire to add new columns (ie. new operations).

  evaluate preorder postorder print
constant        
plus        
minus        
times        
div        

If we had a multimethod execute() as follows:

Object execute(Expr e, Operation f)

where the code chosen for execution is based on the position in the matrix, our problem is solved. In this scenario, the code chosen for execute() is based on two types --- the type of Expr and the type of Operation. If such a solution worked, we have solved the two problems that we faced in our earlier approach:

  • New operations can be realized by creating new subclasses of Operation
  • All the code for each operation is localized and collected together --- eg, the code for printing is not strewn around the Expr subclasses.

The problem that we face is that dynamic dispatch in Java/C++ is single dispatch and is based solely on the type of the receiver. In contrast, what we desire above is dispatch based on the types of two arguments. How do we realize such a design in the context of a language such as Java or C++??

The Visitor pattern

In this approach, we proceed as follows. We define the interface Expr as follows:

interface Expr {
public Object accept(ExprVisitor v);
}

Thus, we are viewing objects implementing the interface Expr as primarily having the capability to accept ExprVisitors. The interface ExprVisitor is defined as follows:

interface ExprVisitor {
Object visitConstant(Constant t);
Object visitPlus(Plus t);
Object visitMinus(Minus t);
Object visitDiv(Div t);
Object visitTimes(Times t)
}

Each class that implements the interface ExprVisitor provides a way to handle each of the possible cases of Expr. Thus, the interface ExprVisitor encapsulates the idea of "operation" on the Expr interface. Notice however, that the known subclasses of Expr are "wired" into the interface, ie. this design pattern is suitable only when the collection of subclasses of Expr does not change. In terms of the matrix analogy above, the Visitor pattern lets us add new columns, but is very fragile with respect to the addition of new rows. We discuss some relief for this dilemma below.

We begin by looking at the implementation of the print operation.

class Print implements ExprVisitor {
  public Object visitPlus(Plus t) {
    System.out.println("Plus");
    t.left().accept(this);
    t.right().accept(this);
return null;
} public Object visitMinus(Minus t) {
    System.out.println("Minus");
    t.left().accept(this);
    t.right().accept(this);
return null;
} public Object visitTimes(Times t) {
    System.out.println("Times");
    t.left().accept(this);
    t.right().accept(this);
return null;
} public Object visitDiv(Div t) {
    System.out.println("Div");
    t.left().accept(this);
    t.right().accept(this);
return null;
} public Object visitConstant(Constant t) {
System.out.println("Const(" + t.getValue() + ")");
return null;
} }

The Expr subclasses are set up to perform the case analysis on Expr.

class Constant implements Expr {
    int w;
    public Constant(int w) { this.w = w; }
    public Object accept(ExprVisitor v) { return v.visitConstant(this); }
int getValue() { return w; }
}
class Plus implements Expr {
    Expr lt, rt;
    public Plus(Expr l, Expr r) { lt = l; rt = r; }
    public Object accept(ExprVisitor v) { return v.visitPlus(this); }
    Expr left() { return lt; }
    Expr right() { return rt; }
}
class Minus implements Expr {
    Expr lt, rt;
    public Minus(Expr l, Expr r) { lt = l; rt = r; }
    public Object accept(ExprVisitor v) { return v.visitMinus(this); }
    Expr left() { return lt; }
    Expr right() { return rt; }
}
class Times implements Expr {
    Expr lt, rt;
    public Times(Expr l, Expr r) { lt = l; rt = r; }
    public Object accept(ExprVisitor v) { return v.visitTimes(this); }
    Expr left() { return lt; }
    Expr right() { return rt; }
}
class Div implements Expr {
    Expr lt, rt;
    public Div(Expr l, Expr r) { lt = l; rt = r; }
    public Object accept(ExprVisitor v) { return v.visitDiv(this); }
    Expr left() { return lt; }
    Expr right() { return rt; }
}

For example the following code fragment prints out the expression coded by m in preorder form.

        Expr one = new Constant(1);
        Expr two = new Constant(2);
        Expr onePtwo = new Minus(one, two);
        Expr three = new Constant(3);
        Expr m = new Plus(onePtwo, three);
        Print p = new Print();
        m.accept(p);

Consider a small prefix of the trace of m.accept(p).

  • In m.accept(p), the method invoked is the accept() method of the class of m, namely Plus.
  • This leads to the invocation p.visitPlus(m).
  • In p.visitPlus(m), the method invoked is the visitPlus() method of the class of p, namely Print.

This trace of t summarizes the key division of reponsibilities between Expr and ExprVisitor:

  • Dynamic dispatch on the Expr objects chooses the correct subclass of Expr.
  • Dynamic dispatch on the ExprVisitor objects chooses the correct operation to execute.

The combination yields the desired effect: the code chosen for execution is determined by the types of the Expr subclass AND the type of the ExprVisitor subclass.

Another Example

class Evaluate implements ExprVisitor {
    public Object visitConstant(Constant t) {
return new Integer(t.get());
}
    public Object visitPlus(Plus t) {
        Integer leftv = (Integer) t.left().accept(this);
        Integer rightv = (Integer) t.right().accept(this);
        return new Integer(leftv.intValue() + rightv.intValue());
    }
    public Object visitMinus(Minus t) {
        Integer leftv = (Integer) t.left().accept(this);
        Integer rightv = (Integer) t.right().accept(this);
        return new Integer(leftv.intValue() - rightv.intValue());
    }
    public Object visitTimes(Times t) {
        Integer leftv = (Integer) t.left().accept(this);
        Integer rightv = (Integer) t.right().accept(this);
        return new Integer(leftv.intValue() * rightv.intValue());
    }
    public Object visitDiv(Div t) {
        Integer leftv = (Integer) t.left().accept(this);
        Integer rightv = (Integer) t.right().accept(this);
        return new Integer(leftv.intValue() / rightv.intValue());
    }
}

For example the following code fragment sets i to 2.

        Expr one = new Constant(1);
        Expr two = new Constant(2);
        Expr onePtwo = new Minus(one, two);
        Expr three = new Constant(3);
        Expr m = new Plus(onePtwo, three);
        Evaluate p = new Evaluate();
        int i = ((Integer) m.accept(p)).intValue();

An analogy from ML

The Visitor pattern is similar in spirit to the datatypes and pattern matching constructs in a language such as ML. (This paragraph is written for those familiar with ML. Those not familiar with ML can safely skip this section.) In ML, the datatype Expr would have been written as;

datatype Expr = Constant of int
  | Plus of Expr* Expr
  | Minus of Expr* Expr
  | Times of Expr * Expr
  | Div of Expr* Expr

and the functions are written by pattern matching (ie. case selection) on the type of constructor (note the striking similarity to the code for evaluate written above)

fun evaluate(Constant(i)) = i
| evaluate(Plus(e1,e2)) = evaluate(e1) + evaluate(e2)
| evaluate(Minus(e1,e2) = evaluate(e1) - evaluate(e2)
| evaluate(Times(e1,e2)) = ...
| evaluate(Div(e1,e2)) = ...

Thus, in ML we have the freedom to define many new operations on the datatype. All the code for each new operation is collected together and each new operation is a local change. As in the Visitor pattern, however, what we give up is the ability to extend the datatype Expr. Changes to the datatype Expr will cause changes in all operations that operate on it. In addition, the ML compiler yields warnings if the cases handled by each operation are non-exhaustive.

Extending the datatype in the context of the Visitor pattern

We observed above that it was hard to add rows to the table once we started using the Visitor pattern. To extend the data structure, in our case Expr, we only need to add each new subclass separately without modifying any existing code. But we would then have to track down each existing visitor class and add a visitX method for each new Expr implementation class X. At best, this would be tedious; at worst, impossible if the sources for these visitor classes are not available.

However, it is possible to "have your cake and eat it too", sort of. Instead of modifying existing visitor classes, we extend the existing visitor interface and classes by creating new extended versions of them that include the visitation methods for the new Expr implementation classes. Although this requires creating a new extended version of each visitor that you want to use, it does not require changing existing visitor classes directly. Therefore, this is possible even if the source code for the existing classes is not available.

One remaining detail arises when visitors create new visitor instances just like themselves but with different arguments passed to the constructor. The new instances would be an instance of the original version instead of the extended one because the constructor of the original version is invoked directly. We can solve this problem by using the Factory Method pattern, which uses a designated factory method to invoke the right constructor indirectly. This allows the extended versions of the visitor classes to override the factory methods so that they invoke the constructor for the extended version instead of the original one.

The VisitorExpressions example illustrates this approach in detail.

Issues to explore and think about

The following points are worth considering.

  • The Visitor often requires liberal access to the data structure to perform its job efficiently. In this case, the instance variable v in Constant and the methods left(), right() in other classes. In a Java context, this may mean that is is often convenient to make the Visitors part of the same package as the underlying data structure. That is the solution that we will adopt for this example.
  • In our example, iteration through the data structure is built into the Visitor, as revealed by the invaocation of the methods left() etc. This is common, but not necessary. A visitor can often access a data structure only via the Iterators provided by the data structure, especially when it is not possible to add a new visitor to an existing package. Iterators support efficient traversal of a data structure while revealing as little about its implementation as possible.