Visitor Pattern for our Labs

In other classes, you discovered several patterns and their uses. It turns out that one of the more useful patterns for this course is the Visitor pattern. We consider this pattern essentially because Java (and the other common OO language-that-must-not-be-named) do not offer multiple dispatch.

What is multiple dispatch? Read on.

Multiple Dispatch

First, recall that a virtual method invocation allows a method to be tailored to the actual run-time type of the receiving object. For example (using Java syntax throughout)
  STYPE obj = new RTYPE();, (B)b, (C)c)
will call the foo method on the instance obj. While obj is declared to be of type STYPE, its actual run-time type is that of its constructor, namely RTYPE, which (in the above example) must be a subtype (extension) of STYPE. If both of these types define a method for foo with parameter signature A, B, C, then the method actually called is that of the more refined type, namely RTYPE's version.

In summary, the dispatch for foo is based solely on the actual run-time type of obj, and has nothing at all to do with the run-time type of the supplied parameters. Most compilers will search for an appropriate definition of foo based on the supplied parameters' declared types. But that is done at compile-time, when the parameters' actual types may be unknown. The parameters' run-time types may be more refined, but that fact will not affect the dispatch.

Multiple dispatch is a concept that allows method dispatch to be based not only on the receiving object but also on the parameters of the method's invocation.

Why should we care? Read on.

AST traversals

We are creating an abstract syntax tree (AST) for our compiler, and that tree will eventually have many different kinds of nodes, all derived from AbstractNode. If we want the behavior of the nodes to differ, then this is nicely accomplished by overriding methods in the nodes' class definitions.

We also want to traverse an AST for many different purposes. We may want to print the AST, perform semantic analysis, or generate code. Each of these could be accomplished by refining the notion of tree traversal in extensions of some common superclass.

Thus, the actual work performed upon a node depends on two things: the node type and the traversal type. But without multiple dispatch, we cannot have both refinements participate in method dispatch simultaneously.

One solution is to sprinkle elements of a traversal in all of the nodes' classes. So, an IntegerNode would contain code to print itself out, to perform semantic analysis, and to generate code. The problem here is that the code for a given traversal is spread through all the classes, which makes both the traversal and the node-based classes more difficult to read and maintain.

Visitor Pattern

The Visitor pattern was introduced to address the above scenario. Instead of spreading all the code for a given traversal throughout the nodes' classes, the code is concentrated in a particular traversal class. That code is called by arranging for each node to
  1. Accept a call from a visitor that performs the traversal
  2. Call the visitor back using a method in that visitor that is customized to the node
Let's suppose we wish to traverse our AST to print out its nodes. The traversal class is a particular kind of visitor, and (in the style of GoF) it contains the following kind of code:
  public class PrintTraversal extends Visitor {
     public visitStringNode(StringNode n) {....}
     public visitIntNode   (IntNode n)    {....}
     public visitSymbolNode(SymbolNode n) {....}
Each of the above methods knows how to print out its own particular kind of node.

Each node in turn accepts a call from a particular visitor:

  public class StringNode extends AbstractNode {
     pubic accept(Visitor v) {  v.visitStringNode(this); }
Because the supplied visitor's actual type could be any subclass of Visitor, this implies that the superclass Visitor must have (potentially abstract) methods.
  public abstract class Visitor {
     public abstract visitStringNode(StringNode n) ;
     public abstract visitIntNode   (IntNode n)    ;
     public abstract visitSymbolNode(SymbolNode n) ;

Drawbacks of Visitor

Although Visitor nicely solves the double-dispatch problem, there are a few drawbacks associated with Visitor:

Reflective Visitor

Adapted from

Java offers a nice solution through reflection. Double-dispatch is achieved by having each node call the same method (dispatch), through a superclass to avoid duplication, and that method then causes the type-specific method to be called through reflection on the supplied object's type.

In other words, at the point where a StringNode would call-back its Visitor:

  public class StringNode extends AbstractNode {
     pubic accept(Visitor v) {  v.visitStringNode(this); }
the node instead inherits accept from its superclass:
   public final void accept(NodeVisitor v) { v.dispatch(this); }
The v.dispatch(this) method is reflectively responsible for making it look like the StrongNode actually executed v.visitStringNode(this). In fact, since parameter names participate in the signature of a method, all such methods can be named visitor and can be distinguished by the type of their parameter. Thus, v.dispatch(this) is really responsible for invoking v.visit(StringNode). The code for dispatch is as follows:
   public final void dispatch(Object o) {
      Method m = getBestMethodFor(o);
      try {
	 m.invoke(this, new Object[] { o });
      } catch (IllegalAccessException e) {
         throw new Error("Method " + m + " aborting, bad access: "+e);
      } catch (InvocationTargetException e) {
         // This exception is thrown if the reflectively called method
         // throws anything for any reason
         throw new Error("Method " + m + " aborting: "+e);
The code for getMethod, which figures out which method to invoke is as follows:
     * Find the closest visit method that handles the supplied object

   protected Method getBestMethodFor(Object o) {
      Class nodeClass = o.getClass();
      Method ans = null;

      // Try the superclasses

      for (Class c = nodeClass; 
           c != objectClass && ans == null; 
           c = c.getSuperclass()) {
         debugMsg("Looking for class match for " + c.getName());
         try {

            // Unlike GoF, all methods are "visit" and are 
            // distinguished by their param type

            ans = getClass().getMethod("visit", new Class[] {c});

         } catch (NoSuchMethodException e) { }

      // Try the interfaces.  The code below will find the last 
      // interface listed for
      // which "this" visitor can handle the type

      Class iClass = nodeClass;
      while (ans == null && iClass != objectClass) {
	debugMsg("Looking for interface  match in " + iClass.getName());
	Class[] interfaces = iClass.getInterfaces();
         for (int i = 0; i < interfaces.length; i++) {
	   debugMsg("   trying interface " + interfaces[i]);
            try {
               ans = getClass().getMethod("visit", new Class[] {interfaces[i]});
            } catch (NoSuchMethodException e) { }
	 iClass = iClass.getSuperclass();

      if (ans == null) {
         try {
            debugMsg("Giving up");
            ans = getClass().getMethod("defaultVisit", 
                    new Class[] {(new Object()).getClass()});
         } catch (NoSuchMethodException e) {
             // Just stop, because throwing an exception will cascade upwards
             debugMsg("Cannot happen -- could not find defaultVisit(Object)");
      debugMsg("Best method for " + o + " is " + ans);
      return ans;

It gets better

This form of Visitor opens up an interesting opportunity. Visitors often find it useful to group the Visitable objects by the similary of the action performed on them during the visit. For example, nodes that represent loads and stores of memory might deserve the same treatment by a given visitor. Unfortunately, while a grouping along those lines might suffice for one visitor, another may wish that nodes could be grouped by the type of data they handle (integer, float, etc.).

The getMethod method shown above searches for a method in the visitor that matches the supplied object's type, where the notion of type is widened to include any interfaces implemented by that object.

Thus, by arraninging for objects to implement a common interface, they can be offered common treatment by a visitor.