Visitor Pattern Versus Multimethods

    The Visitor Pattern

    The visitor pattern is a programming pattern that has been advocated strongly for writing code operating on a hierarchy of classes. A thorough description is available there from the Design Patterns book.

    A typical example is the definition of operations on an Abstract Syntax Tree. Here is Java code using a Visitor:

    package syntax;
    
    abstract class ExpressionVisitor 
    { 
      abstract void visitIntExp(IntExp e); 
      abstract void visitAddExp(AddExp e); 
    } 
    
    abstract class Expression 
    { 
      abstract void accept(ExpressionVisitor v); 
    } 
    
    class IntExp extends Expression 
    { 
      int value; 
    
      void accept(ExpressionVisitor v)
      {
        v.visitIntExp(this);
      }
    } 
    
    class AddExp extends Expression 
    { 
      Expression e1, e2; 
    
      void accept(ExpressionVisitor v)
      {
        v.visitAddExp(this);
      }
    } 
    
    The interest of this construction is that it is now possible to define operations on expressions by subclassing ExpressionVisitor. This can even be done in a different package, without modifying the expression hierarchy classes.
    // Behaviour can now be defined on Expressions 
    
    package tools;
    
    class PrettyPrint extends ExpressionVisitor 
    {
      void visitIntExp(IntExp e) 
      { 
        System.out.print(e.value); 
      } 
    
      void visitAddExp(AddExp e) 
      { 
        e.e1.accept(this); 
        System.out.print(" + "); 
        e.e2.accept(this); 
      } 
    }
    Without visitors, the classes have to be modified each time a new operations is added. In this case, a prettyPrint member method would be added to each class.

    Another possibility would be to define a static method in the new package. But then it would be necessary to test the argument with instanceof and use downcasts. In short, lose the benefits of object-orientation.
     

    Shortcomings of the Visitor pattern

    However, the Visitor pattern has serious flaws:
    1. An obvious problem is that the arguments and the return type of visiting methods have to be known in advance. In this example, to define a prettyPrint function that returns a String, a new Visitor class has to be defined, as well as a new accept method in every class of the hierarchy. And the same job has to be done again to define an evaluation function that returns an integer. The same problem occurs if the visiting methods needs parameters.
    2. The code is more obscure. In particular with recursive calls: in e.e1.accept(this) one cannot see that the call is indeed a prettyprint. One would expect prettyPrint(e.e1) there.
    3. A lot of code has to be written to prepare the use of visitors: the visitor class with one abstract method per class, and a accept method per class. This code is tedious and boring to write. If we add a new class, the visitor class needs a new method. Furthermore, it is indeed likely that a new visiting method will need the definition of a new visitor pattern, as seen in point 1. At the least, several patterns have often to be written.
    4. If a visitor pattern has not been written in the first time, the hierarchy has to be modified to implement it. In particular, if the hierarchy cannot be modified because you are not allowed to, the visitor pattern cannot be applied at all.

    Alternative solution with Multimethods

    Here is the same example, using multi-methods, in Nice. As you can see, it is much shorter and natural, and it solves all the problems above.

    package syntax;
    
    abstract class Expression { } 
    
    class IntExp extends Expression 
    { 
      int value; 
    } 
    
    class AddExp extends Expression 
    { 
      Expression e1, e2; 
    } 
    
    // Behaviour can now be defined on Expressions 
    
    package tools;
    
    void prettyPrint(Expression e); 
    
    prettyPrint(IntExp e) 
    { 
      System.out.print(e.value); 
    } 
    
    prettyPrint(AddExp e) 
    { 
      prettyPrint(e.e1); 
      System.out.print(" + "); 
      prettyPrint(e.e2); 
    } 
    

    Comparison of the two approaches

    Multi-methods allow to solve the situation at which the Visitor pattern aims, without carrying its disadvantages:
    1. There is no need to write preliminary code to "prepare the way" for visitors. This solves points 1, 2 and 4 above.
    2. The code is shorter and more natural. Recursive calls appear as such.


    The Visitor pattern is a trick to introduce multiple dispatch in a language that lacks it. However, it raises serious issues. Language support for multi-methods makes it much easier and elegant to handle the common situation where the Visitor pattern applies.
     

    General information about Nice : the Nice home page