So far we have looked at two ways to represent the following expression forms,
number Literal expr + expr Add expr - expr Subtract expr * expr Multiply expr / expr Divide
The first was procedural and the second object-oriented. Using the procedural approach, it was easier to add operations than data types. Using an object-oriented approach, the opposite was true. What I will demonstrate now is a technique that balances some of the advantages and disadvantages of both into a hybrid approach called the Visitor Pattern.
There are several ways to apply the visitor problem to expressions, each with their own unique set of advantages and disadvantages, but I will only cover one of these approaches.
The visitor pattern is a modification of the the object-oriented approach that allows an operation to be separated from the class hierarchy into its own class. To demonstrate how a visitor pattern can be applied, I will first created a visitor interface that will be implemented by all visitors. It looks like,1
Here I use a generic type to leave the type of the return result open. The
expression evaluator will use
double isn't an appropriate return
result for printing, for example. Using a type parameter allows different visitors
to have their own result types.
Now I will create the class hierarchy that will be visited. I will first create an abstract class to represent the expressions, just as I did in the previous object oriented example.
Accept() is key to the visitor pattern.
It accepts the visitor and, in turn, calls the correct
method on the visitor, based on the type of the instance being visited. To do this, each descendant overrides
Accept() method and calls the correct method. To
show how this is done I will implement the Literal expression form.
Literal class is very similar to the
original pure object oriented version with the addition of the
Accept() method. The implementation of the method is trivial, simply call
visitor.Visit(this). The compiler will determine that
IExprVisitor<R>.Visitor(Literal literal) is the method
to bind to based on the type of the
Next, as before, I introduce a base class to represent an abstraction of a binary operator.
Notice that I do not yet implement the
I could have, after adding
R Visit(BinaryOperator binop)
IExprVisitor interface, but I didn't need it
for the visitors I wanted to create. I have found that it is usually best to only have
the visitors visit the concrete classes and avoid the abstract. A visitor can
always simulate visiting a abstract base class by calling a common routine in
each of the concrete class visitor methods (you will see this technique below in
Printer visitor). This leaves the visitor less
cluttered when the abstract class doesn't need to be visited separately. In other
Accept() methods only calls one
Visit() method for each instance, and that for the most derived type. This has the
additional advantage of allowing the
Visit() method to
have a meaningful result, which wouldn't be possible if the
Accept() method called more than one
Now that I have a base class for binary operators, I can now implement the binary operator expression forms.
The implementation of these should come as no surprise. They each
Accept() method and call the visitor
method associated with their type.
Now that we have the class hierarchy in place, I will now implement the expression evaluator as a visitor.
The expression evaluator can be used by creating a new visitor and calling
Evaluate() method of the evaluator, passing the root of the expression tree.
The visitor pattern makes it easy to add new operations. To demonstrate this, as before, I will add a print operation. This looks very much like the expression evaluator above.
As this shows, using a parameterized type for the visitor interface is awkward
when you don't have anything to return. What I would want to do is implement
is not allowed as a type parameter so I use
instead. This means I have to return something, so I always return
null. This should be seen as awkwardness introduced by
my choice of interface styles, not of the visitor pattern itself.
The visitor pattern shares some of the advantages of the procedural approach,
in that it is easy to add new operations and new operations can be added
dynamically, but we lose the natural ability to add new data types that is
normally associated with an object-oriented approach as well as lose
representation encapsulation since the instance fields need to be visible to the
visitors. We kept the natural size optimization and the completeness
verification by the compiler, however. To demonstrate the difficult of adding a
new type, I will again add Power. The first step is to add the new
Now we need to add a method to
Power type that each visitor will need to implement. It looks like,
Next I need to add a method for in each visitor to handle the new class. For
Evaluator it is,
And and for the
Printer class it looks like.
This is just one way to apply the visitor pattern to the expression problem. Other ways have their own strengths and weaknesses by trading off different advantages and disadvantages of the the procedural and object-oriented styles. Some visitor pattern applications have their own unique advantages, such as being able to mesh functionality by executing several visitors concurrently such as evaluating and printing.
Next time we will investigate a different modified object-oriented approach that is sometimes dubbed groups but I will call layers.
1 - This application of the visitor pattern is patterned after one from Generalized Algebraic Data Types and Object-Oriented Programming. << back <<