The Visitor Pattern as an Alternative to OOP

The visitor pattern from the GoF is frequently overlooked by programmers who are used to object oriented programming. However, in some cases, it is significantly cleaner and easier to use than an overridden function. Unfortunately, it's easier to misuse as well, and, when it is used poorly, it can be a real mess.

I was going to tell you about my static analysis project and how I'm using the visitor pattern there. Then I took a glance at the wikipedia article on the visitor pattern. It's clearly written by a OOP fanatic who's never seen the alternatives, so I'm going to contrast my implementation of visitor with the one there.

The contrast is useful because wikipedia's implementation is written using object oriented principles. Part of my goal with this post is to explain about OO alternatives. My implementation is written using compile time polymorphism rather than runtime polymorphism. As we'll see, this is significantly prettier and more flexible than runtime polymorphism.

Java-Style Visitors

I recommend clicking on the wikipedia link and reading a bit. Like all good OOP C++ programmers, he's got loads of virtual functions in a variety of interfaces.

Some of those are used to implement a completely unnecessary runtime double dispatch mechanism. The double dispatch functions can be eliminated by avoiding the use of the interfaces in the first place. This immediately cleans up his classes a bit.

If the compiler always knows the type of a class, then the accept() and visit() messiness disappear. The accept function essentially acts as a safe cast from the base interface to the derived type. If we never let the compiler forget what the derived type is, then we don't need a cast.

Yes, I'll admit that I laughed when the author confidently says that those functions are required. They're only required because the author wanted to do dispatch at runtime instead of compile time. The visitor pattern does not require this.

There's another interesting point to notice about the interface. He's got one virtual function for every single derived class in his visitor. There are no functions that handle a collection of derived classes. This is because he's forced to use the class hierarchy to tell the compiler which function to call. He cannot use any other properties of the derived classes for this. Without that flexibility, he'll often be forced to write a separate function for each derived class.

Traditional OOP techniques

I'd like to briefly touch on what would happen if a visitor pattern wasn't used at all.

In this case, the visitor class in the wikipedia code gets replaced by a virtual function that gets implemented for every single derived class in the hierarchy. If you want to perform that function, you simply call it. This is often the correct thing to do, too.

However, it's worth looking at some of the disadvantages that are solved by using a visitor. First, the code in each of those functions gets spread out over the entire class hierarchy. If those functions are more tightly coupled to each other than to the object that they're attached to, then this will be awkward to maintain.

Second, each one of those derived classes has to be known and available for modification. You can't make it so that third parties can add additional derived classes, for example. Every derived class has to be found as well. In some cases, that can be a serious problem.

Finally, the functionality provided by your new function has to be advertised to every single author and user of the hierarchy. If the functionality is obscure and only useful in limited cases, then a visitor (or a free function) should be considered instead. The only one who has to know about the functionality provided by the visitor is the author of the visitor. Nothing else gets touched.

Compile Time Polymorphism

The visitors that I'm writing for my static analysis project are dramatically different.

They act on the abstract syntax tree (AST) of the parsed Lua program. There are about 40 or so different grammatical constructs in Lua, and so there are about 40 classes in the AST.

The visitors themselves act on each of these classes, but they frequently only have a few functions in them. For example, I've got one visitor that calls an aggregated visitor on each node in the abstract syntax tree.

The ForEach visitor has to know about several different ways that the classes can hold child nodes, but it can act on each of those techniques in a single function. For example, it's got a function to handle a vector of pointers to child nodes. It's got another one for a single pointer to a child node. It's got a few others, but it certainly doesn't have 40 member functions in it! I suspect that that's what the author of the wikipedia article would have ended up doing, and it would have been miserable.

I've got a bunch of visitors other than the ForEach visitor. Each of these describe an algorithm that acts on the AST. The algorithms end up almost completely separated from the data structure that the algorithm acts on. I can add a new algorithm (and visitor) without recompiling or editing the data structure code. This separation is what the visitor pattern is great at.

The reverse is certainly not true, however. If the data structure code changes, then the visitors will at least have to be recompiled. In my case, I've written a lot of the visitors generically enough that most of the code doesn't have to change, but a recompile of C++ code that contains a lot of template metaprogramming can be expensive even without having to edit the code. I wanted to be somewhat immune to changes in the data structures, though.

For example, Lua has a "repeat...until" statement as well as a "while" statement. (They do exactly what you'd expect.) Internally, I decided that the repeat...until statement should store the test and statement block in the reverse order of the while loop. I want to be able to change that without changing the ForEach visitor. I want the ForEach visitor to be mostly independent of the internal organization of the AST classes. Because ForEach uses template metaprogramming instead of manual coding to figure out how to traverse the AST, this works perfectly.

All of this works reasonably well with compile time polymorphism. Most of this would be impossible without it.

In my case, the disadvantages aren't all that bad. However, they do exist, so let's look at them.

The largest problem is that small amounts of template metaprogramming were required to pull this off. This means that compile times are longer than a Java programmer would think was possible. (It takes a 5 seconds or so per source file for me.)

It also means that you get some really ugly functions with lots of the "typename" keyword messing up the flow of the code. I suppose you're supposed to get used to that, but I hate it. This isn't really a problem with the visitor pattern, however. It's really a problem with C++. It may be cleaner in other languages.

Overall, however, there weren't many disadvantages to using this type of visitor. However, traversing an AST appears to be exactly what visitors are good for; The GoF book uses that as their example, and quite a few web pages have emulated them. In retrospect, it makes me feel a bit foolish for writing this article!

This originally appeared on PC-Doctor's blog.