Design Patterns – Expandable Alternative to Visitor Pattern for Tree Traversal

I have been using the visitor pattern to represent expression trees over the course of 10+ years on six large-scale projects in three programming languages, and I am very pleased with the outcome. I found a couple of things that made applying the pattern a lot easier:

Do not use overloads in the interface of the visitor

Put the type into the method name, i.e use

IExpressionVisitor {
    void VisitPrimitive(IPrimitiveExpression expr);
    void VisitComposite(ICompositeExpression expr);
}

rather than

IExpressionVisitor {
    void Visit(IPrimitiveExpression expr);
    void Visit(ICompositeExpression expr);
}

Add an "catch unknown" method to your visitor interface.

It would make it possible for users who cannot modify your code:

IExpressionVisitor {
    void VisitPrimitive(IPrimitiveExpression expr);
    void VisitComposite(ICompositeExpression expr);
    void VisitExpression(IExpression expr);
};

This would let them build their own implementations of IExpression and IVisitor that "understands" their expressions by using run-time type information in the implementation of their catch-all VisitExpression method.

Provide a default do-nothing implementation of IVisitor interface

This would let users who need to deal with a subset of expression types build their visitors faster, and make their code immune to you adding more methods to IVisitor. For example, writing a visitor that harvests all variable names from your expressions becomes an easy task, and the code will not break even if you add a bunch of new expression types to your IVisitor later on.

It is up to the visitor implementation to decide whether to visit child nodes and in which order. That's the whole point of the visitor pattern.

In order to adapt the visitor for more situations it is helpful (and quite common) to use generics like this (it's Java):

public interface ExpressionNodeVisitor<R, P> {
    R visitNumber(NumberNode number, P p);
    R visitBinary(BinaryNode expression, P p);
    // ...
}

And an accept method would look like this:

public interface ExpressionNode extends Node {
    <R, P> R accept(ExpressionNodeVisitor<R, P> visitor, P p);
    // ...
}

This allows to pass additional parameters to visitor and retrieve a result from it. So, the expression evaluation can be implemented like this:

public class EvaluatingVisitor
    implements ExpressionNodeVisitor<Double, Void> {
    public Double visitNumber(NumberNode number, Void p) {
        // Parse the number and return it.
        return Double.valueOf(number.getText());
    }
    public Double visitBinary(BinaryNode binary, Void p) {
        switch (binary.getOperator()) {
        case '+':
            return binary.getLeftOperand().accept(this, p)
                + binary.getRightOperand().accept(this, p);
        // More cases for other operators here.
        }
    }
}

The accept method parameter isn't used in the above example, but just believe me: it is quite useful to have one. For example, it can be a Logger instance to report errors to.