Visitor Pattern: which one?
In fact, several variations of what we call Visitor Pattern do exist. Many times these variations are simply called "Visitor Pattern", without suffixes which would be necessary to differentiate them. This certainly causes confusion. In addition, lots of articles about this pattern fail to explain properly what it is, how it works and how it should be employed in real world applications. Add to that some intrinsic complexity this pattern involves and sometimes confusion caused by the nomenclature or definitions adopted.
This article aims to present a clear, non-ambiguous and non-misleading definition of what the Visitor pattern is, with examples in the real world. We will demonstrate how a pair of interfaces is plenty enough for solving a vast range of problems, without any need of any modification in this pair of interfaces in order to accommodate unforeseen situations. Complex use cases can be addressed by defining additional interfaces, which extend the original concept, but without changing the original pair of interfaces in any way.
Definition
From Wikipedia we read: In object-oriented programming and software engineering, the Visitor Design Pattern is a way of separating an algorithm from an object structure on which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying those structures.
Let's clarify a little bit this definition: In object-oriented programming and software engineering, the Visitor Pattern is a way of separating a computation (or operation) from the data structure it operates on.
A practical result of this separation is the ability to add new operations to existing data structures without modifying those data structures.
In particular, we will employ the word computation instead of algorithm because the former is more restrictive and more specific than the later. This article shows that obtaining elements from a data structure also involves an algorithm, which could cause confusion. For this reason, it's better to avoid the word algorithm at all.
Interpretation
The definition says that the Visitor Pattern separates concerns, i.e:
- on one hand you have data access which knows how a data structure can be traversed;
- on the other hand you are interested on a certain computation you need to be executed.
Besides, there's a very important restriction which is: you cannot change the original data structure. In other words:
- the data access knows the data structure but does not know anything about the computation to be performed;
- the computation knows how to operate on a certain element of the data structure but doesn't know anything about how the data structure can be traversed;
- you are not allowed to amend the data structure in any way: imagine a data structure which belongs to a third-party library, which you don't have the source code;
A key point here is the introduction of the concept of data access. In other words, we are saying that the data structure is not accessed directly, but via some sort of data access logic. This will become clear later.
Use cases
Let's invent scenarios which evolve in complexity. Our aim is to demonstrate why the Visitor Pattern is needed and how it should behave and operate.
Scenario 1: simple array
Suppose we have a very simple array of Integers. We need to visit all elements and calculate the sum of all these elements.
Anyone will immediately think on something like below, isn't it?
public int sumArray(Integer[] array) {
int sum = 0;
for (int i=0; i<array.length; i++) sum += array[i];
return sum;
}
Yes. It solves the problem. Actually, the problem is so simple that you must be asking yourself why we need anything more complicated than a simple one liner. Isn't it?
OK. Let's go ahead to another use case.
Scenario 2: different data structures
This scenario is pretty similar to the previous one, but now we can have either a Integer[], a List<Integer> or a Map<T,Integer>. In this case, one immediately think on something like this:
public int sumList(List<Integer> list) {
int sum = 0;
for (int i=0; i<list.size(); i++) sum += list.get(i);
return sum;
}
public <T> int sumMap(Map<T, Integer> map) {
int sum = 0;
for (Entry<T, Integer> key : map.entrySet()) {
sum += map.get(key);
}
return sum;
}
OK. In this use case we can start to understand that there are different structures: Integer[], List<Integer> and Map<T,Integer> but, in the end, all you need to do is obtain an individual Integer from whatever data structure it is and add it to sum variable.
Let's complicate things a little more now.
Scenario 3: different data structures and several computations
This scenario is pretty similar to the previous one, but now we have several different computations: sum of all elements, calculate mean value of them, calculate the standard deviation, tell if they form an arithmetical progression, tell if they form a geometric progression, tell if they are all prime numbers, etc, etc, etc.
Well, in this case, you can figure out what will happen: you will face a proliferation of methods. Multiply the quantity of computations you are willing to provide by the number of different data structures you are willing to support. This proliferation of methods may not be desirable.
The point is: it does not make sense to implement the same logic over and over again just because the data structure is slightly different. Even when data structures are very different, what matters is that we are willing to perform a certain computation on all elements stored in it, does not matter if it is a plain array, a map, a tree structure, a graph or whatever. The computation only needs to know what needs to be done once an element is at hand; the computation does not need to know how an element can be obtained.
Another aspect is that it may not be desirable or may not be convenient to touch existing code, or existing data structures, to be more precise.
Yet another aspect: Imagine that a certain computation requires additional variables, possibly associated to each element of the original data structure (or several data structures). These additional variables are only needed when you are performing the computations we described; they are not needed anywhere else. In certain constrained scenarios, you will not be allowed to waste memory like this.
Scenario 4: do not touch data structures
Imagine now that you have the problem proposed by scenario 3, but you cannot touch any data structures. Imagine that it's a legacy library in binary format; imagine that you don't have the source. You simply cannot add a single field anywhere in order to keep partial computations or keep response values. You cannot change the provided source code in any way simply because you don't have it. You obviously cannot add any methods intended to perform the computation.
What would be a solution in this case? Well... there's only one: you will have to implement something, whatever it is, outside the provided legacy library.
Conclusion of Use Cases
You may not be allowed to change the original source code in regards to the data structure (or data structures) you have. Or this may not desirable, like in the case of proliferation of methods we mentioned before. This may not be even possible, like in the case of the provided legacy library. This is definitely the most important aspect of the Visitor Pattern: you are not allowed to change the original data structures in any way.
This aspect is commonly misunderstood by many people posting on the Internet and even in many academic works. It's very common to see implementations where data structures are changed, like when the object model is changed; or data structures suddenly start to implement new interfaces, etc.
If you find articles proposing changes in the original data structures, does not matter how, you can be sure that these articles are misunderstanding what Visitor Pattern really means.
Introducing the Visitor Pattern
It's time to present how the Visitor Pattern works.
The Visitor Pattern is defined as a pair of interfaces: a Visitor and a Visitable. There's also some additional expedient your code needs to perform when you call implementations of these interfaces.
Let's learn by example, showing how it can be applied to some real world situations.
A naive Visitor
Remember: a visitor defines a computation
The idea here is that we need an interface which defines how a computation works in respect to a single data element. It does not matter how data elements are organised in the data structure at this point.
Once the interface is defined, we then define a class which performs the computation. Because the interface does not know anything about how data elements are organised in data structures, the implementing class does not have any dependency on how data is organised. The class only cares about details strictly related to how the computation needs to be done; not what needs to be done in order to obtain data elements.
For the sake of brevity, lets present the Visitor interface and demonstrate only one of the several computations we may be interested:
public interface Visitor<T> {
public void visit(T element);
}
private class Sum<T extends Integer> implements Visitor<T> {
private int sum = 0;
@Override
public void visit(T element) {
sum += element;
}
public T value() {
return sum;
}
}
The interface Visitor defines a method which is responsible for receiving a single element from the data structure, whatever data structure it is. Classes which implement the Visitor interface are responsible for defining the computation, receiving one element at a time, without caring about how such element was obtained in the first place.
A naive Visitable
Remember: a Visitable defines data access
The idea is that we need an interface which defines a how data can be obtained in general.
Once the interface is defined, we then define a class which knows how data can be obtained from a given data structure in particular. It means to say that, if we have several different data structures, we will need several classes implementing the Visitable interface, one class for each data structure involved.
Notice that nothing was said about the computation. It's not responsibility of interface Visitable anything involving the computation: it only cares about how single data elements can be obtained from a given data structure.
For the sake of brevity, lets present the Visitable interface and demonstrate only one of the several possible data access expedients we may eventually need:
public interface Visitable<T> {
public void accept(Visitor<T> v);
}
private class VisitableArray<T extends Integer> implements Visitable<T> {
private final T[] array;
public VisitArray(final T[] array) {
this.array = array;
}
@Override
public void accept(Visitor<T> v) {
for (int i=0; i<array.length; i++) {
v.visit(array[i]);
}
}
}
The interface Visitable defines a method which is responsible for accepting an object which implements interface Visitor: a Visitable does not know anything about the computation, but it knows how a single data element must be passed to another class which is, in turn, responsible for performing the computation.
Classes implementing the Visitable interface are responsible for traversing the data structure, obtaining a single data element at a time. Also, once a single element is obtained, the class knows how another step of the computation can be triggered for the current data element at hand.
Putting it all together
Your code must now perform the following steps:
- instantiate a Visitor;
- instantiate a Visitable
- bootstrap a Visitable with a Visitor;
- request the result of the computation;
public int computeSumArray(final Integer[] array) {
// instantiate a Visitor (i.e: the computation)
final Visitor<Integer> visitor = new Sum<Integer>();
// instantiate a Visitable (i.e: the data access to the data structure)
final Visitable<Integer> visitable = new VisitArray<Integer>(array);
// bootstrap a Visitable with a Visitor
visitable.accept(visitor);
// returns value computed by the Visitor
return ((Sum)visitor).value();
}
Now imagine you'd like to calculate the mean of an array of Integers. All you need to do is defining a class called Mean and reuse everything else, like this:
public int computeMeanArray(final Integer[] array) {
// instantiate a Visitor (i.e: the computation)
final Visitor<Integer> visitor = new Mean<Integer>();
// instantiate a Visitable (i.e: the data access to the data structure)
final Visitable<Integer> visitable = new VisitArray<Integer>(array);
// bootstrap a Visitable with a Visitor
visitable.accept(visitor);
// return value computed by the Visitor
return ((Mean)visitor).value();
}
Now imagine you'd like to obtain a Mean from a List<integer> instead. All you need to do is defining this specific data access for this data structure and reuse everything else, like this:
public int computeMeanList(final List<Integer> list) {
// instantiate a Visitor (i.e: the computation)
final Visitor<Integer> visitor = new Mean<Integer>();
// instantiate a Visitable (i.e: the data access to the data structure)
final Visitable<Integer> visitable = new VisitList<Integer>(list);
// bootstrap a Visitable with a Visitor
visitable.accept(visitor);
// return value computed by the Visitor
return ((Mean)visitor).value();
}
Extended data structures
Now imagine a situation where you need to aggregate fields to a provided legacy data structure, where you don't have access to the source code.
For the sake of simplicity, let's assume there's a way to unmistakably identify data elements: for arrays, it could be employing an index, for maps, trees and more complex data structures, it could be employing some sort of key.
In the example below we'd like to take coordinates of capitals of countries whilst our data structure only contains country names but do not contain coordinates of their capitals. The solution consists on retrieving coordinates as part of the method accept. In the real world, it may be useful to keep additional fields stored in a data structure which keeps complimentary information relative to the original data structure. This is what we show below:
private class VisitableCapitalCoordinates<T extends Coord> implements Visitable<T> {
private final T[] countries;
private final Map<T,Coordinate> capitals; // for storage/caching, if required
public VisitableCapitalCoordinates(
final T[] countries;
final /* @Mutable */ Map<T,Coordinate> capitals) {
this.countries = countries;
this.capitals = capitals;
}
@Override
public void accept(Visitor<T> v) {
for (int i=0; i<array.length; i++) {
String country = countries[i];
T coord = capitals.put(country, coord(country))
v.visit(coord);
}
}
//
// private method: not defined in the interface
//
private Coordinate coord(T country) {
return obtainCoordinateOfCapitalSomehow(country);
}
}
In the example above, the most important changes happen in the class constructor and in private methods. The method accept keeps its original signature and only passes an element of the extended data structure, instead of passing an element of the original data structure.
In the method constructor, we receive two data structures: the original one and the extended one which must be previously created. We show this in the example below:
final String[] countries = { "USA", "United Kingdom", "France", "Holland", "Belgium" };
final Map<T,Coordinate> capitals = new HashMap<T,Coordinate>();
// instantiate a Visitor (i.e: the computation)
final Visitor<Coordinate> visitor = new PlotCoordinate<Coordinate>();
// instantiate a Visitable (i.e: the data access to the data structure)
final Visitable<Coordinate> visitable = new VisitableCapitalCoordinates<Coordinate>(countries, capitals);
// bootstrap a Visitable with a Visitor
visitable.accept(visitor);
We've seen in the previous section that our naive implementation of the Visitor Pattern
- has an interface Visitor which provides the computation;
- has an interface Visitable which provides the data access;
- does not require any modification on existing data structures.
Now let's complicate a little bit more this scenario.
Adding polymorphism
Let's imagine that an investor has an investment portfolio composed of several financial instruments, such as assets, options, bonds, swaps and more exotic financial instruments. Let's suppose we would like to forecast what would be the payoff of this portfolio given certain conditions.
The problem we are facing now is the fact that the data structure is not uniform anymore, like we have seen previously above. Now we have a portfolio which contains several different objects in it. We can think that a portfolio is actually a tree made of several different kinds of nodes in it. Several nodes are leaf nodes, such as an asset, an option or a bond. Some other nodes are not leaf nodes: they aggregate other nodes under it, such as swaps and exotic instruments.
What this use case adds to the initial problem is the fact that now there's not single type <T> which represents all nodes. To be more precise: even if all nodes derive from a base type , we still need to make sure we are handling a certain node properly, according to its type and also we are computing its value properly, according to the type hierarchy. For example:
Object
Payoff
ForwardTypePayoff
NullPayoff
TypePayoff
StrikedTypePayoff
AssetOrNothingPayoff
CashOrNothingPayoff
GapPayoff
PlainVanillsPayoff
At first glance, we can think that we could define a pair of classes PolymorphicVisitor and PolymorphicVisitable which take the node type as a generic parameter. Unfortunately, this is not the case, in spite it makes a lot of sense.
Once Java Generics applies type erasure in general, our application will have troubles to decide between a PolymorphicVisitor<ForwardTypePayoff> and PolymorphicVisitor<NullPayoff> for example, because both will have types erased and will become PolymorphicVisitor<Object>. Going straight to the solution, without spending any more time explaining all intricacies, we need something like this:
public interface PolymorphicVisitor {
public <T> Visitor<T> visitor(Class<? extends T> element);
}
The interface above provides a method visitor which is responsible for providing the actual Visitor for the element data. So, once you have the actual Visitor, you can delegate to the actual visitor. If the actual visitor was not found, you can try again using the PolymorphicVisitor of the base class, and so on, like this:
@Override
public void accept(final PolymorphicVisitor pv) {
final Visitor<FixedRateBondHelper> v = (pv!=null) ? pv.visitor(this.getClass()) : null;
if (v != null) {
v.visit(this);
} else {
super.accept(pv);
}
}
In particular, the definition of the capture type <T> as shown below:
public <T> Visitor<T> visitor(Class<? extends T> element);
helps the Java compiler to perform type inference, which indirectly solves the difficulty with type erasure, because type checking is possible this way at compile time. More information about this topic can be found in this article.
Going ahead, we need to define interface PolymorphicVisitor, which works in conjunction with PolymorphicVisitable, like this:
public interface PolymorphicVisitable {
public void accept(PolymorphicVisitor pv);
}
The same way the actual visitor needs to be obtained for a certain element data; the PolymorphicVisitor needs to verify the actual data type of a given data structure before going ahead, like this:
@Override
public <CashFlow> Visitor<CashFlow> visitor(Class<? extends CashFlow> klass) {
if (klass==org.jquantlib.cashflow.CashFlow.class) {
return (Visitor<CashFlow>) new CashFlowVisitor();
}
if ( klass == SimpleCashFlow.class) {
return (Visitor<CashFlow>) new SimpleCashFlowVisitor();
}
if (klass==Coupon.class) {
return (Visitor<CashFlow>) new CouponVisitor();
}
if (klass==IborCoupon.class) {
return (Visitor<CashFlow>) new IborCouponVisitor();
}
if (klass == CmsCoupon.class) {
return (Visitor<CashFlow>) new CmsCouponVisitor();
}
...
}
Here we can see that type erasure cannot be avoided in this case. Actually, even if type erasure could be avoided, we would have to verify the data type of elements of the data structure anyway, because it cannot be anticipated at compile time. We have to resolve types at runtime.
Observe that there's one difficulty in our example above: Because we need to specify the type capture CashFlow in the method declaration
public <CashFlow> Visitor<CashFlow> visitor(Class<? extends CashFlow> klass)
we ended up having to specify the full class address of CashFlow later in the code, in order to avoid confusion between the generic type name and the actual class name. This is shown in the line below:
if (klass==org.jquantlib.cashflow.CashFlow.class) { ... }
Conclusion
The implementation of the Visitor Pattern we present here is scalable and flexible. This implementation does not need any interfaces or class methods which are crafted for a certain application in particular.
We showed that specific interfaces and classes are necessary only when there's polymorphism involved. We purposely defined PolymorphicVisitor and PolymorphicVisitable in order to take decisions regarding which should be the correct Visitable for traversing a specific data structure and should be the correct Visitor needed once we have a certain data element in our hands. These decisions are not responsibility of the simple Visitor and Visitable interfaces. For this reason, additional interfaces are definitely needed.
The Visitor Pattern as defined here conforms to the definition presented on the top of this article and does not require any change in existing data structures.
On the other hand, even with advantages gained with our implementation, the Visitor Pattern still keeps its relative high complexity. In general, code which employs the Visitor Pattern becomes obscure and difficult to be understood, which means that documentation is key in order to keep code organised and relatively easy to be understood.
-----------------------------------------------------
If you found this article useful, it will be much appreciated if you create a link to this article somewhere in your website. Thanks
[ First published by Richard Gomes on 17:16, 29 January 2011 (GMT) ]
