1.13.2 Openness in Data Design

Recall our definition for an arithmetic expression without variables:

ArithExpr := Const(int) | Sum(ArithExpr, ArithExpr) ....

Our implementation of this data definition using the composite pattern would be more robust and more flexible if we could define new operations on ArithExprs without modifying any existing code. Fortunately, there is a clever design pattern called the visitor pattern that lets us do this. The idea underlying the visitor pattern is to bundle the methods defining the new operation for each concrete subclass together in a new class called a visitor class. An instance of such a class is called a visitor.

First, we will define a new interface IVisitor that specifies what methods must be included in every visitor class for ArithExpr:

interface IVisitor {
  int forConst(Const c);
  int forSum(Sum s);
  ...
}

Notice that each method takes an instance of the class that it processes. This argument, called the host, is needed to give it access to all the information that would be available through this if the method were defined inside that class, e.g., the values of the object's fields returned by accessors.

Now we will create a new concrete class EvalVisitor to hold all the methods for evaluation of an ArithExpr:

class EvalVisitor implements IVisitor {
  int forConst(Const c) {
    return c.getValue();
  }
  int forSum(Sum s) {
    return s.left().accept(this) + s.right().accept(this);
  }
  ...
}

We need to install a hook in each subclass of ArithExpr to execute the corresponding visitor method. The hook is a new method, accept, which takes a visitor as an argument and calls the appropriate method in that visitor.

abstract class ArithExpr {}
  abstract int accept(IVisitor v);
}

class Const {
  ...
  int accept(IVisitor v) {
    return v.forConst(this);
  }
}

class Sum {
  ...
  int accept(IVisitor v) {
    return v.forSum(this);
}

...

To evaluate an arithmetic expression, we simply call

a.accept(new EvalVisitor())

If we wish to add more operations to arithmetic expressions, we can define new visitor classes to hold the methods, but there is no need to modify the existing subclasses of ArithExpr.

Notice that, since a visitor has no fields, all instances of a particular visitor class are identical. So it is wasteful to create new instances of the visitor every time we wish to pass it to an accept method. We can eliminate this waste by using the singleton design pattern which places a static field in the visitor class bound to an instance of that class.

class EvalVisitor {
  static ONLY = new EvalVisitor();
  ...
}

Then, instead of

accept(new EvalVisitor()),

we may simply write

accept(EvalVisitor.ONLY).

Another elegant way to define visitors is to define each visitor as an anonymous class. Since an anonymous class definition defines only one instance of the new class, it produces results similar to the singleton pattern. The principal difference is that the new class has no name; the unique instance must be bound to a local variable or field declared in the enclosing program text.

Recall that an anonymous class has the following syntax:

new className( $arg_1, ..., arg_m$) { $member_1{\tt\small ; ...;} member_n$ }

In most cases, the class className is either an abstract class or an interface, but it can be any class. The argument list $arg_1, ..., arg_m$ is used to call the constructor for the class className; if className is an interface, the argument list must be empty. The member list $member_1{\tt\small ; ...;} member_n$ is a list of the member definitions for the new class separated by semicolons.

For example, to create an instance of a visitor that evaluates an arithmetic expression, we write:

new IVisitor() {
  int forConst(Const c) {...}
  int forSum(Sum s) {...}
  ...
}

Since we generally want to use a visitor more than once, we usually bind the anonymous class instance to a variable, so we can access it again! The statement:

visitor ev = new IVisitor() {
               int forConst(Const c) {...};
               int forSum(Sum s) {...};
               ...
               };

binds the variable ev to our anonymous class instance.

Finger Exercise 1.13.2.1 Convert your solution to exercise 1.13.1.1 to a visitor-based implementation using the IVisitor interface given in the subsection.