...Removing All Doubt

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,

    public interface IExprVisitor<R> {
        R Visit(Literal literal);
        R Visit(Add add);
        R Visit(Subtract subtract);
        R Visit(Multiply multiply);
        R Visit(Divide divide);
    }

Here I use a generic type to leave the type of the return result open. The expression evaluator will use double but 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.

    public abstract class Expr {
        public abstract R Accept<R>(IExprVisitor<R> visitor);
    }

The method Accept() is key to the visitor pattern. It accepts the visitor and, in turn, calls the correct Visit() method on the visitor, based on the type of the instance being visited. To do this, each descendant overrides the Accept() method and calls the correct method. To show how this is done I will implement the Literal expression form.

    public class Literal: Expr {
        public double Value;

        public Literal(double value) { Value = value; }

        public override R Accept<R>(IExprVisitor<R> visitor) {
            return visitor.Visit(this);
        }
    }

The above 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 this parameter.

Next, as before, I introduce a base class to represent an abstraction of a binary operator.

    public abstract class BinaryOperator: Expr {
        public Expr Right;
        public Expr Left;

        public BinaryOperator(Expr left, Expr right) {
            Right = right;
            Left = left;
        }
    }

Notice that I do not yet implement the Accept() method. I could have, after adding R Visit(BinaryOperator binop) to the 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 the Printer visitor). This leaves the visitor less cluttered when the abstract class doesn't need to be visited separately. In other words, my 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 Visit() methods.

Now that I have a base class for binary operators, I can now implement the binary operator expression forms.

    public class Add: BinaryOperator {
        public Add(Expr left, Expr right) : base(left, right) { }

        public override R Accept<R>(IExprVisitor<R> visitor) {
            return visitor.Visit(this);
        }
    }

    public class Subtract: BinaryOperator {
        public Subtract(Expr left, Expr right) : base(left, right) { }

        public override R Accept<R>(IExprVisitor<R> visitor) {
            return visitor.Visit(this);
        }
    }

    public class Multiply: BinaryOperator {
        public Multiply(Expr left, Expr right) : base(left, right) { }

        public override R Accept<R>(IExprVisitor<R> visitor) {
            return visitor.Visit(this);
        }
    }

    public class Divide: BinaryOperator {
        public Divide(Expr left, Expr right) : base(left, right) { }

        public override R Accept<R>(IExprVisitor<R> visitor) {
            return visitor.Visit(this);
        }
    }

The implementation of these should come as no surprise.  They each override the 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.

    public class Evaluator: IExprVisitor<double> {
        public Evaluator() { }

        public double Evaluate(Expr expr) {
            return expr.Accept(this);
        }

        double IExprVisitor<double>.Visit(Literal literal) {
            return literal.Value;
        }

        double IExprVisitor<double>.Visit(Add add) {
            return Evaluate(add.Left) + Evaluate(add.Right);
        }

        double IExprVisitor<double>.Visit(Subtract subtract) {
            return Evaluate(subtract.Left) - Evaluate(subtract.Right);
        }

        double IExprVisitor<double>.Visit(Multiply multiply) {
            return Evaluate(multiply.Left) * Evaluate(multiply.Right);
        }

        double IExprVisitor<double>.Visit(Divide divide) {
            return Evaluate(divide.Left) / Evaluate(divide.Right);
        }
    }

The expression evaluator can be used by creating a new visitor and calling the Evaluate() method of the evaluator, passing the root of the expression tree. For example,

Expr expr = new Add(new Multiply(new Literal(10), new Literal(4)),
    new Literal(2));

Evalutor evaluator = new Evaluator();
double result = evaluator.Evaluate(expr);
  
Console.WriteLine("The answer is {0}", result);

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.

    public class Printer: IExprVisitor<object> {
        public Printer() { }

        public void Print(Expr expr) {
            expr.Accept(this);
        }

        object IExprVisitor<object>.Visit(Literal literal) {
            Console.Write(literal.Value);
            return null;
        }

        void PrintBinaryOperator(BinaryOperator binOp, char opChar) {
            Print(binOp.Left);
            Console.Write(" {0} ", opChar);
            Print(binOp.Right);
        }

        object IExprVisitor<object>.Visit(Add add) {
            PrintBinaryOperator(add, '+');
            return null;
        }

        object IExprVisitor<object>.Visit(Subtract subtract) {
            PrintBinaryOperator(subtract, '-');
            return null;
        }

        object IExprVisitor<object>.Visit(Multiply multiply) {
            PrintBinaryOperator(multiply, '*');
            return null;
        }

        object IExprVisitor<object>.Visit(Divide divide) {
            PrintBinaryOperator(divide, '/');
            return null;
        }
    }

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 IExprVisitor<void> but void is not allowed as a type parameter so I use object 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 Power type.

    public class Power: BinaryOperator {
        public Power(Expr left, Expr right) : base(left, right) { }

        public override R Accept<R>(IExprVisitor<R> visitor) {
            return visitor.Visit(this);
        }
    }

Now we need to add a method to IExprVisitor<R> for the Power type that each visitor will need to implement. It looks like,

        R Visit(Power power);

Next I need to add a method for in each visitor to handle the new class. For Evaluator it is,

        double IExprVisitor<double>.Visit(Power power) {
            return Math.Pow(Evaluate(power.Left), Evaluate(power.Right));
        }

And and for the Printer class it looks like.

        object IExprVisitor<object>.Visit(Power power) {
            PrintBinaryOperator(power, '^');
            return null;
        }

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 <<