Deriving the Visitor Pattern: A Review and Discussion
Like most other self-respecting developers I had also read the GoF book, including the section on the visitor pattern. However, when a colleague came over to me with a question, I could not initially justify the complexity of the example code I saw in the book. What follows is a discussion of why the visitor pattern is the way it is.
Brief Review of the Pattern
The definitive description of the pattern is in the GoF book Design Patterns, Chapter 5 (pp 331-344)(see References section). The Wikipedia has a concise and good description, which formed the basis for my brief review here. The visitor pattern is classified as a Behavioral pattern, so the thing to notice is the way in which the classes and objects interact and distribute responsibility. A typical application of this pattern occurs in the following scenario: we have a number of elements in an object structure (common structures include trees & lists) and we want to perform a bunch of disparate operations (e.g. printing or cloning each element) on the elements of the structure.
The visitor pattern is a way of separating the operation from the object structure and a way of collecting together the different implementations of an operation for different kinds of elements in the object structure. A Visitor class is created which knows how to perform a particular operation on the different kinds of elements in the object structure. Each type of element in the structure defines an accept() method that can accept any kind of Visitor. The visitor is passed to each element in the structure in turn, by calling its accept() method and the Visitor then performs the operation on the visited element. One important consequence of this separation of object structure and operation is that we can later add a new operation (a new kind of Visitor) without having to modify the element classes of the object structure.
Each type of Visitor defines several visit()methods, one for each kind of element. The basic insight is that the precise set of instructions to execute (i.e. the method or function to call) depends on the run-time types of both the Visitor & the visited element. Java only lets us call different methods based on the run-time type of one object (via virtual functions), so the pattern advocates a clever solution: The second dependency on the type of element visited is first resolved by polymorphically calling the accept() method of the visited element. accept() then resolves the first dependency by turning around and polymorphically calling the visit()method for its class.
An Example
Before this description gets too confusing, let us study the pattern in the context of a concrete problem: Let us say we need to traverse a list collecting node-specific information. The list has two kinds of nodes, say, Red and Black, which needed to be processed differently. It seems like an ideal application for the visitor pattern. Listing 1 shows the code. (All code samples in this article use a J2SE 5.0 compatible compiler.)
To me and my colleague, this initially seemed like an overly complex solution for a simple problem. NodeVisitor.doVisit() calls into the Node's accept methods, which simply delegates back into NodeVisitor. Furthermore, the accept() methods of RedNode and BlackNode are almost identical. Finally, notice that if we now add a GreenNode class, we need to add a new visitGreen() method to the NodeVisitor class and re-compile it (not to speak of the almost redundant implementation of accept() in the GreenNode class). Ugh! This does not seem kosher by any OO standard.
The Need for the accept() Methods
Novice armchair Java developers might ask why we can't do something simpler, like Listing 2, for example, without touching the Node interface, or the classes RedNode and BlackNode which implement it.
Listing 2 has two significant differences from the previous. First, there is no redundant method (namely accept()) for each node type to implement. Second, we use function name overloading for the visit() implementations, thus enabling the "clever" foreach loop, which iterates over each node and calls the appropriate overloaded version of visit() depending on the type of the current element. With this, we hope to contain all the visiting logic within NodeVisitor.
Alas, real developers have a more difficult job than arm-chair developers! If you are using a language like Java or C++, an overloaded function name like visit() has to get resolved at compile time. Thus line 6.iii will not compile because none of the visit() methods provided in NodeVisitor know how to accept a generic "Node" as argument.
For line 6.iii to work the way we want it to, the decision on what operation needs to be performed has to be delayed until we can determine at runtime the type of the node n being examined in the current iteration of the for-each loop.
Traditional OO languages (Java, C++ etc) provide us with one standard tool for delaying function resolution until run-time: virtual functions. Thus, in Listing 1, 6.iii is modified to a virtual function call n.accept(nv). So the actual function that gets called is decided at run-time. The version called then delegates work by invoking the right version of NodeVisitor.visit().
So Why Not Just Use Plain Vanilla Inheritance?
The explanation I just gave is good, but not good enough. I can almost hear you ask: why doesn't accept() do the work itself? Why does it have to delegate back to NodeVisitor? There are three reasons:
1. Accumulating state: If you read the problem I presented closely, you will notice that I specified a need to collect node-specific information. Since the doVisit passes the same NodeVisitor instance to each accept(), the visitor can be used to accumulate state across the different Node objects. For example, say you have an Employee HR application where the Red nodes represent employees, the Black nodes represent managers, visitRed() calculates the pay raises for programmers, and visitBlack the pay raises for managers. The NodeVisitor nv could print a report of the total increase in salary expense at the end of the for loop.
2. Supporting more than one visitor (the need for double dispatch): Say the next version of your Employee HR application needs to add a new HRPolicyVisitor that checks for compliance with some HR policy and the implementation is different for managers and programmers.
To accommodate both the types of Visitors, we introduce an additional layer of indirection - an abstract EmployeeNodeVisitor interface with virtual visitXXX() functions for each type of element to visit, namely visitProgrammer() & visitManager(). The old PayRaiseVisitor and the new HRPolicyVisitor both implement EmployeeNodeVisitor. The decision on which version of visit() gets called now gets determined by a two-step process. The first step is as before. The node type of the visited element n in the foreach loop determines which version of the virtual function accept() gets called. In the second step, the type of the EmployeeVisitor passed in to accept() determines the (virtual function) version of visitXXX() called. The source files that come with this article show the skeleton of this implementation. Figure 1 illustrates the sequence of calls from both doPayHike(), which uses a PayRaiseVisitor to raise the pay of each employee, and doEnforcePolicy() which uses a HRPolicyVisitor to check HR policy compliance.
This technique, where the types of two objects are used to select the operation invoked is known as double dispatch. By contrast, single dispatch uses the type of one object to select the operation invoked. One known implementation of single dispatch is virtual functions. Since Java and C++ support only this form of single dispatch, the pattern simulates double dispatch by using single dispatch twice!
3. Separation of concerns: A concern is any focus of interest in a program. A classic tenet of good software design is that the different concerns of a program must be broken down into separate modules that have little or no overlap. In the Employee HR program , visitProgrammer and visitManager of a particular visitor have more commonality than the two visitProgrammers of the different visitors or the two visitManagers of the different visitors. In fact, the methods in a given visitor may even share state information as described in 1 above. This makes the Visitor pattern a good way to organize code by separation of concerns.
Notice also that as a consequence of this way of organizing code, it is extremely easy to add a new visitor operation, but adding a new kind of node requires adding a new visitXXX method to all the Visitors.
If none of the above three reasons apply, you would be better off not delegating the work of accept() back to a separate visitXXX() method.i.e. plain vanilla inheritance would be more appropriate than an application of the Visitor pattern. On the other hand, if any of the above reasons apply, the Visitor pattern would be a good solution for you.
But This Still Does Not Preclude Overloading the visit() Methods...
You might still have one lingering question about Listing 1: Why can't we use function name overloading instead of the different visit<
The short answer is that nothing prevents you from doing this; Listing 3 is just as correct as Listing 1 For the last word, however, I will have to defer to the GoF, who write the following in a footnote:
We could use function overloading to give these operations the simple name, like Visit, since the operations are already differentiated by the parameter they're passed. There are pros and cons to such overloading. On the one hand, it reinforces the fact that each operation involves the same analysis, albeit on a different argument. On the other hand, that might make what's going on at the call site less obvious tosomeone reading the code. It really boils down to whether you believe function overloading is good or not [in this situation].
Conclusion
In this article we reviewed the Visitor pattern and "derived" it from an armchair sketch of the functionality we wanted: the ability to accumulate state over elements of an object structure, the separation of the operations from the object structure, and the ability to add new operations without recompiling the element types. These requirements called for a "double dispatch"; i.e. the precise method to call for "visiting" each element in the structure depended on two runtime types: the type of Visitor and the type of the visited element. The Visitor pattern was shown to be a way to simulate double dispatch using virtual functions, a form of single dispatch.
References
* Gamma, et al. Design Patterns: Elements of Reusable Object-Oriented Software, 1995, Addison-Wesley, Reading, MA.
* Wikipedia contributors, "Visitor pattern," Wikipedia: The Free Encyclopedia, http://en.wikipedia.org/wiki/Visitor_pattern (accessed Aug 19, 2005)
© 2008 SYS-CON Media Inc.
No comments:
Post a Comment