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
SortingAlgorithm
interface.