Understanding the need of Visitor Pattern

Question

After seeing an article on visitor pattern, it is clear to me how it works. And I created a sample program for my understanding;

main(){
    SortingAlgorithm bubbleSort;
    :
    intList.sort(bubbleSort);
}

class IntList implements Sortable{
    :

    public void sort(SortingAlgorithm algo){
        return algo.sort(this);
    }
}

interface SortingAlgorithm{
    public void sort(IntList list);
    public void sort(DoubleList list);
    public void sort(LongList list);
}

class BubbleSort implements SortingAlgorithm{

    public void sort(IntList list){
    :
    }
    public void sort(DoubleList list){
        :
    }
    public void sort(LongList list){
        :
    }
}

And the advantage I can see is that if I implement new algorithm, I need not to modify IntList;

main(){
    SortingAlgorithm heapSort;
    :
    intList.sort(heapSort);
}

class HeapSort implements SortingAlgorithm{

    public void sort(IntList arr){
    :
    }
    public void sort(DoubleList list){
        :
    }
    public void sort(LongList list){
        :
    }
}

The other thing I can see is that if I create another type of list or map, say IntMap, then I have to just add a method in Sortable interface and need to implement it in all the relevant classes: BubbleSort, HeapSort.

Now what I can't understand is the need of visitor patterns as I can simplify above program like this;

main(){
    BubbleSort.sort(intList);

}

Now my primitives list and maps need not to implement any interface and it's method. And even SortingAlgorithm interface is not required anymore.

Answer 1

The visitor pattern is useful when you want to process a data structure containing different kinds of objects, and you want to perform a specific operation on each of them, depending on its type.

Your example is not the best, since you pass a single homogeneous list as input, so there is really no need for the pattern. As you point out, you can just call the appropriate method directly. (Furthermore a sorting algorithm shouldn't even care it the input is a list of ints or doubles, as long as all items are of the same type, and the type has a comparison function.)

But consider if you have a directory tree, and you want to display the first few lines of text from each file. This would require different logic if the file was plaintext, HTML, Word or PDF. So this would be appropriate use of the visitor pattern since you want a generic way to traverse the tree, but you want the preview of each leaf to be handled depending on its type.

Example

We have PdfFile, HtmlFile and TextFile which all are descendants of the abstract class File. Assume the method dir("path") has the type List<File> but returns instances of PdfFile, HtmlFile etc.

We create a class Head which is supposed to generate the summaries for these different file types, so it will have this interface:

class Head {
  static String of(PdfFile file) { ... }
  static String of(HtmlFile file) { ... }
  static String of(TextFile file) { ... }
}

Then you might be tempted to do something like this:

dir("path").forEach(file -> Head.of(file)))

The problem is this doesn't work! In Java and similar languages, method overloads based on parameter type are resolved at compile time, not runtime. Since the type of the list is something like List<File>, the compiler will look for a single method with the signature of(File file). How do we solve this problem? We could add an override to every subclass of File which looks like this:

public override string acceptHead() { return Head.of(this); }

And then do this:

dir("path").forEach(file -> file.acceptHead()))

This actually works, because dispatch on the instance (before the dot) is resolved at runtime, so we get the correct override which in turn calls the correct overload of of. Then you could generalize the acceptHead method to just accept, and create a generalized FileVisitor interface, which Head is just an instance of, so you can reuse the dispatch logic for other purposes. And now you have a visitor pattern.

In some ways, the visitor pattern is simply a workaround for the fact that Java (and similar languages) are single dispatch, which means overrides are selected at runtime only based on the instance before the dot. If overloads also was selected at runtime based on the parameter types, then you wouldn't need this pattern.

Answer 2

The visitor pattern is a solution to a more general design problem:

I have a hierarchy of different classes. Each class supports various common operations. We would now like to extend that hierarchy, without having to change the existing hierarchy (e.g. because it is defined by a library we do not have the source code to).

• We can add more classes, which must support all required operations.
• We can add more operations, which must be supported by all classes in the hierarchy.

When designing a hierarchy, we can choose which of the two extension directions we want to make easy. (Trying to do both is called the Expression Problem and is extremely tricky.)

Since this is a bit theoretic, let's use an example – various kinds of animals. Each animal has a name() and makes a sound().

Library code:

interface Animal {
  String name();
  String sound();
}

class Dog implements Animal {
  public String name() { return "Dog"; }
  public String sound() { return "Woof"; }
}

class Cat implements Animal {
  public String name() { return "Cat"; }
  public String sound() { return "Meow"; }
}

User code:

Animal[] animals = new Animal[] { new Dog(), new Cat() };
for (Animal animal : animals)
  System.out.println(animal.name() + " goes " + animal.sound());

Output:

Dog goes Woof
Cat goes Meow

Extending by adding classes

We can extend the Animal hierarchy by adding new classes that implement all required methods.

User code:

class Bird implements Animal {
  public String name() { return "Bird"; }
  public String sound() { return "Tweet"; }
}

...


Animal[] animals = new Animal[] { new Dog(), new Cat(), new Bird() };
for (Animal animal : animals)
  System.out.println(animal.name() + " goes " + animal.sound());

Output:

Dog says Woof
Cat says Meow
Bird says Tweet

By allowing new subclasses of Animal to be created, we have also made it impossible to add new operations to the Animal hierarchy. After all, that operation would have to be implemented for all classes both from the library and from any user code – an impossible feat since there can be infinitely many subclasses.

Extending by adding new operations

We can't add new operations without editing the definitions of all classes. This is rather inelegant. Well, we could by checking with instanceof, but that is rather fragile:

public static String favouriteToy(Animal animal) {
  if (animal instanceof Dog)
    return "chewing bone";
  if (animal instanceof Cat)
    return "yarn ball";
  throw new UnsupportedOperationException();
}

This is problematic because it's easy to forget some animal. How can we statically type-check that we covered all cases?

The visitor pattern offers a way out, as long as the designer of the original class hierarchy anticipated the need for additional operations. I'll now assume the original interface has an additional acceptVisitor method:

Library code:

interface Animal {
  String name();
  String sound();
  <R> R acceptVisitor(AnimalVisitor<R> visitor);
}

interface AnimalVisitor<R> {
  R visitDog(Dog dog);
  R visitCat(Cat cat);
}

class Dog implements Animal {
  public String name() { return "Dog"; }
  public String sound() { return "Woof"; }
  public <R> R acceptVisitor(AnimalVisitor<R> visitor) {
    return visitor.visitDog(this);
  }
}

class Cat implements Animal {
  public String name() { return "Cat"; }
  public String sound() { return "Meow"; }
  public <R> R acceptVisitor(AnimalVisitor<R> visitor) {
    return visitor.visitCat(this);
  }
}

User code:

class FavouriteToy implements AnimalVisitor<String> {
  public String visitDog(Dog dog) { return "chewing bone"; }
  public String visitCat(Cat cat) { return "yarn ball"; }
  public static String get(Animal animal) {
    FavouriteToy visitor = new FavouriteToy();
    return animal.acceptVisitor(visitor);
  }
}

...

Animal[] animals = new Animal[] { new Dog(), new Cat() };
for (Animal animal : animals)
  System.out.println(animal.name()
      + " goes " + animal.sound()
      + ", plays with " + FavouriteToy.get(animal));

Output:

Dog goes Woof, plays with chewing bone
Cat goes Meow, plays with yarn ball

Again, the important point is that this effectively allows us to define new methods for all classes in some hierarchy without editing those classes. This is useful in two cases:

• We cannot edit the original hierarchy because it's some external library.

• We need many unrelated operations, and don't want to put different operations into the same class. This is indicated by the Single Responsibility Principle.

The drawback of the Visitor Pattern is that we have now lost the ability to add new Animal subclasses. We would have to add them to the AnimalVisitor interface as well, and that would break all existing visitors.

In practice, the visitor pattern is often used in compilers. Here, the syntax of a program is usually represented through a tree data structure, where each element in the tree may have a different type. Different parts of the compiler do wildly different stuff with this tree: one part pretty-prints the code. One part optimizes the code. Another part compiles the code to another languages, and a further visitor could be an interpreter.

All these unrelated operations can be written as visitors, so that the definitions of the various types in the trees contains nothing more than the data fields, and a bit of visitor boilerplate.

Simple compiler example:

interface Expression { <R> R acceptVisitor(Visitor<R> v); }

interface Visitor<R> {
  R visitConstant(Constant c);
  R visitVariable(Variable v);
  R visitAddition(Addition a);
}

class Constant implements Expression {
  public final int value;
  public Constant(int value) { this.value = value; }
  public <R> R acceptVisitor(Visitor<R> v) { return v.visitConstant(this); }
}

class Variable implements Expression {
  public final String name;
  public Variable(String name) { this.name = name; }
  public <R> R acceptVisitor(Visitor<R> v) { return v.visitVariable(this); }
}

class Addition implements Expression {
  public final Expression left;
  public final Expression right;
  public Addition(Expression left, Expression right) {
    this.left = left;
    this.right = right;
  }
  public <R> R acceptVisitor(Visitor<R> v) { return v.visitAddition(this); }
}

Example syntax tree:

Expression example = new Addition(
  new Variable("x"),
  new Addition(new Constant(2), new Constant(3)));

Pretty printer:

class PrettyPrinting implements Visitor<Void> {
  private StringBuffer sb = new StringBuffer();

  public static String of(Expression e) {
    PrettyPrinting pp = new PrettyPrinting();
    e.acceptVisitor(pp);
    return pp.sb.toString();
  }

  public Void visitConstant(Constant c) {
    sb.append(c.value);
    return null;
  }

  public Void visitVariable(Variable v) {
    sb.append(v.name);
    return null;
  }

  public Void visitAddition(Addition add) {
    sb.append('(');
    add.left.acceptVisitor(this);
    sb.append(" + ");
    add.right.acceptVisitor(this);
    sb.append(')');
    return null;
  }
}

Constant folding optimization:

class ConstantFolding implements Visitor<Expression> {
  public Expression visitConstant(Constant c) { return c; }

  public Expression visitVariable(Variable v) { return v; }

  public Expression visitAddition(Addition add) {
    Expression left = add.left.acceptVisitor(this);
    Expression right = add.right.acceptVisitor(this);

    if (left instanceof Constant && right instanceof Constant) {
      int leftValue = ((Constant) left).value;
      int rightValue = ((Constant) right).value;
      return new Constant(leftValue + rightValue);
    }

    return new Addition(left, right);
  }
}

Interpreter:

class Interpreter implements Visitor<Integer> {
  private final Map<String, Integer> env;
  private Interpreter(Map<String, Integer> env) { this.env = env; }

  public static int eval(Expression e, Map<String, Integer> env) {
    return e.acceptVisitor(new Interpreter(env));
  }

  public Integer visitConstant(Constant c) { return c.value; }
  public Integer visitVariable(Variable v) { return env.get(v.name); }
  public Integer visitAddition(Addition add) {
    return add.left.acceptVisitor(this) + add.right.acceptVisitor(this);
  }
}

Example program:

System.out.println("Expression is: " + PrettyPrinting.of(example));
example = example.acceptVisitor(new ConstantFolding());
System.out.println("Optimized expression is: " + PrettyPrinting.of(example));
Map<String, Integer> variables = new HashMap<>();
variables.put("x", 37);
int result = Interpreter.eval(example, variables);
System.out.println("result is: " + result);

Output:

Expression is: (x + (2 + 3))
Optimized expression is: (x + 5)
result is: 42