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.

Alternatives to Object Oriented Programming

Object oriented programming is extremely popular these days. It's so popular that some people aren't even aware of alternatives to it. The reason its popular is clear: OOP works well a lot of the time. Traditional object oriented programming styles have some significant disadvantages in some circumstances, however. Some of the alternatives are worth looking into when those disadvantages become awkward.

As part of the static analysis project that I'm working on, I'm trying to use alternatives wherever I can. In part, this is because the advantages are substantial for the project I'm working on, but I'm also curious how far it can go and what will happen when I push it too far.

So far, I love it. Inheritance is a relationship between classes that is only a small step from C++ friendship. The derived class becomes extremely tightly coupled to the base class, and, in some cases, the base class can even become coupled to the derived class. The temptation to add functionality to the base class can be large as well.

I'll talk about two ways of partially avoiding inheritance. Both of them rely on compile time polymorphism and cannot (or should not) be used if runtime polymorphism is required.

How often do OO programmers actually need the runtime polymorphism that they enjoy so much? Certainly it's needed some of the time, but it's not nearly as useful as it looks at first. For example, my static analysis project contains a different class for each of several dozen different Lua constructions. This sounds a lot like a case for inheritance, but it's only got one virtual function in the whole project, and that's there only to merge the C and C++ code. If the whole thing had been in C++, it wouldn't have been needed.

Free Functions

Many programmers in the OOP world will happily add new functions to the public interface of classes whenever they can. For example, the C++ string class that PC-Doctor uses has a public member function to return a uuencoded version of the string. This is an extreme case, but it's still worth looking at.

In this case, we've got some functionality that we want to give to a small number of users of a class. There aren't many places in our code base that use this function, and essentially everything uses the string class. Furthermore, the function can easily be implemented using the existing public interface to the string. In this case, it's pretty obvious that everyone would be happier if the function was a free function. As a free function, most users of the string won't ever have to see it. In fact, they don't have to include the appropriate header file or even link to the appropriate module. The interface to string becomes a bit easier to understand for the majority of string users, too.

Furthermore, if you wanted to implement uuencoding for multiple types of strings, you could still do it. For example, if you had different types for UTF-8 and UTF-16 strings, you could overload the free function for both them.

As I said, this was an extreme case. There are disadvantages to free functions, however. Let's look at the other extreme for a bit. For this, let's see what Herb Sutter has to say about free functions in Exceptional C++ Style. He claims that all you should construct your interface to classes by exposing the minimal set of public member functions with everything else as a free function. His argument in the book also looks at a string class, std::basic_string.

Strings, however, are a bad example to generalize from. Some of his arguments get much weaker if you look at a highly specialized class that will only be used in a few places in a single program. Since the vast majority of code that I write is exactly that, I'd rather study this case.

With that in mind, I've made the 40 classes that form the abstract syntax tree for Lua into classes that only have constructors, destructors, and access to internal data. This is, perhaps, a bit more than even Herb Sutter would recommend. I give public access to all of the member data so that there isn't a chance that any member functions could be needed.

I've written most of the code, and it works fine. However, it hasn't survived the maintenance phase, and it's not clear that it will.

However, I'm not going to change the way I write normal application code. At PC-Doctor, I'll write many more classes that get used by only a few other classes. I won't create many free functions for them. Why?

First, free functions clutter the namespace they reside in. I only want that function to be seen by the small number of programmers that might be interested in the class I just wrote. Considerably more people will see the namespace that the class is in.

Let's look at an example. Suppose I want to write a function that appends an alert to a collection of alerts that will be shown to the user. The function might be named "append". If this is a free function, it'll get lost. I want users of my AlertCollection class to know that they can append alerts to it. I don't want them to have to dig around. My users are not going to be using it for long, and they don't want to remember the details later. They just want a complete catalog of everything they can do so they can quickly do what needs to be done.

If a programmer at PC-Doctor decided that they were fans of handling alerts and they wanted to actually remember my API, then putting some of the functions as free functions is, again, a problem. There's one extra bit of information that the user has to remember for each function.

Finally, languages like Java and C# can't have free functions. This is their loss, unfortunately. While I can't give a hard and fast rule for when to use free functions, I can say that they are a valuable tool when developing some APIs.

Visitor Pattern

Well, that was more than I wanted to write in one week. (Remember, I'm a programmer!) The visitor pattern will have to wait until next week. It's probably worth a whole post on its own anyway. It's tricky to use effectively, but it's occasionally extremely effective.

This originally appeared on PC-Doctor's blog.