No Such Thing as a Free Lunch

I’m leery of engineers who believe patterns are the answer to all problems. These engineers are easy to spot. They carry around that GoF book like a bible, and as you discuss designs with your peers, they will snarkily murmur things like “flyweight” and “decorator” in the background. I tend to view patterns as yet another tool in the toolchest, and all tools have their strengths and weaknesses.

I would never discourage new engineers from learning patterns. In fact, I quite enjoyed the Gang of Four book, and I’ve recommended it to people on numerous occasions. But I also stress to young engineers to truly examine the pros and cons of using some pattern to solve some problem. Is the boilerplate of the pattern worth the flexibility? Will the pattern truly be elegant given the warts of the problem? Does the pattern incur some additional cost that is unnecessary? These are all important questions, and you should be asking yourself these questions if you think you’ve found a silver bullet to solve your problem.

Okay, now that I’ve gotten that rant off my chest, I’d like to tell you about a pattern I really like: the visitor pattern.

The Problem

Programming big systems can be thought of as a herculean task of organization. Most problems that need to be solved on a daily basis are probably not that difficult. The difficulty lies in creating a cohesive web of components that inter-operate well together, and are isolated enough so that the complexity of one component does not bleed over into the complexity of another component.

The Visitor is a pattern which allows you to separate algorithmic complexity from structural complexity. In other words, it allows you to create new behavior for a class hierarchy, but define that behavior outside of the hierarchy.

Let’s use an example we’ve used before: Abstract Syntax Trees.

I’ve discussed abstract syntax trees in the past. They are an incredibly powerful tool that can be used to represent things like mathematical expressions or languages (programming and otherwise). Typically, you will have some overarching interface, such as:

And then each syntactical element of your languages will extend or implement this interface. For this post, we’ll use a simple programming language as an example. The language will have integers, variables, operators, and a for loop.

Let’s do something with this class hierarchy. We’ll start with evaluation. We have to add a method to the interface, then implement the method on all the classes:

Now we can execute a simple program! I’ve created a mini-DSL for creating the various expression types. It’s nothing fancy, I’ll include a small snippet of it so you get the idea:

The executed program prints 35. Great! Okay, but now we need to add more functionality to our expr hierarchy. First, we need to be able to print the AST as code, then we need to be able to print the AST as a tree, then we need type checking utilities (for instance, is the for loop conditional a boolean expression?). Then, if you recall from an earlier blog post, we may need the ability to rotate an Operation node if operator precedence is out of whack. After a few weeks, our Expr interface ends up looking like this:

Each one of these methods has to be implemented in all of our expression classes. In some cases, the logic of each method will be very different from the others (printing trees and validating types probably won’t share a lot of code).

If only there was a way to define algorithms and operations separately from our data structure! Oh wait, there is, it’s called the Visitor pattern :-)

In our next chapter, we’ll discuss how the Visitor pattern is implemented and show a few examples.