Visitor Pattern – AST Processing and Usefulness

ccompilerdesign-patternsvisitor-pattern

I know the visitor pattern is typically used to traverse a hierarchy of heterogeneous objects (inheriting a same abstract object) and dissociate the processing of these objects from the data within them. A classic use of the visitor pattern (often quoted), is the processing of an abstract syntax tree in a compiler. Indeed, the structure of the tree is only known at runtime (once the program is parsed), and one want to traverse the tree modifying the nodes according to semantic passes implemented as visitor. But the visitor pattern looked like an overkill to me since it allow a double (dynamic) dispatch as a function of the ASTNode type and the Visitor type, or one statically know the order of the visitor we will use to process the AST during the semantic phase. If I had to code this in C++ (done on the spot without compiling), I would do :

struct AstNode
{
    //virtual void accept() = 0; //this won't work since template does not override virtual pure method
    virtual ~AstNode();
};

struct SpecificNode : public AstNode
{
    template <class Visitor>
    void accept(Visitor v)
    {
        v.visit(*this);
    }
};

//other AST nodes

class MyVisitor
{
    void visit(SpecificNode n) {/*...*/}

    //other visit methods for other AST nodes
};

//other visitors

There is no double dispatch here, that is not a true visitor. But I can figure out why I would need this double dispatch.

Notes :

This wikipedia pages list other uses of double dispatch but not AST : http://en.wikipedia.org/wiki/Double_dispatch#Examples.

Best Answer

One thing the Visitor Pattern does that is often not talked about, is enabling to choose which side of the Expression Problem you want to tackle.

So, what is the Expression Problem? It refers to the basic problem of extensibility: our programs manipulate data types using operations. As our programs evolve, we need to extend them with new data types and new operations. And particularly, we want to be able to add new operations which work with the existing data types, and we want to add new data types which work with the existing operations. And we want this to be true extension, i.e. we don't want to modify the existing program, we want to respect the existing abstractions, we want our extensions to be separate modules, in separate namespaces, separately compiled, separately deployed, separately type checked. We want them to be type-safe.

The Expression Problem is, how do you actually provide such extensibility in a language?

It turns out that for typical naive implementations of procedural and/or functional programming, it is very easy to add new operations (procedures, functions), but very hard to add new data types, since basically the operations work with the data types using some sort of case discrimination (switch, case, pattern matching) and you need to add new cases to them, i.e. modify existing code:

func print(node):
  case node of:
    AddOperator => print(node.left) + '+' + print(node.right)
    NotOperator => '!' + print(node)

func eval(node):
  case node of:
    AddOperator => eval(node.left) + eval(node.right)
    NotOperator => !eval(node)

Now, if you want to add a new operation, say, type-checking, that's easy, but if you want to add a new node type, you have to modify all the existing pattern matching expressions in all operations.

And for typical naive OO, you have the exact opposite problem: it is easy to add new data types which work with the existing operations (either by inheriting or overriding them), but it is hard to add new operations, since that basically means modifying existing classes/objects.

class AddOperator(left: Node, right: Node) < Node:
  meth print:
    left.print + '+' + right.print

  meth eval
    left.eval + right.eval

class NotOperator(expr: Node) < Node:
  meth print:
    '!' + expr.print

  meth eval
    !expr.eval

Here, adding a new node type is easy, because you either inherit, override or implement all required operations, but adding a new operation is hard, because you need to add it either to all leaf classes or to a base class, thus modifying existing code.

Several languages have several constructs for solving the Expression Problem: Haskell has typeclasses, Scala has implicit arguments, Racket has Units, Go has Interfaces, CLOS and Clojure have Multimethods.

However, in an OO language that doesn't have a way of solving the Expression Problem (such as Java or C#), the Visitor Pattern at least allows you to "pick your poison". What the pattern does, is turn your design 90° to the side: the operations become classes (PrintVisitor, EvalVisitor) and conversely, the types become methods (visitAddOperator, visitNotOperator (or just visit, if your language supports argument-based overloading)). This does not solve the Expression Problem (i.e. how to make it easy to add both types and operations), but it does allow you to choose which one to make easy.

So, if your language does support a way to solve the Expression Problem, then you don't need this workaround.

Note, however, this is not the only thing the Visitor Pattern does.

Note: you will note the conspicuous absence of any mention of C++, whatsoever. Unfortunately, I simply don't know enough about it. I suspect that between its overloading and argument-based dispatch, virtual inheritance, free functions, macros, and most importantly compile-time template metaprogramming, the Expression Problem is solved in C++, but I don't know for sure.

The problem is that once someone finds a solution for the Expression Problem, they redefine it to make it even harder so solve, so that new solutions are even more powerful and expressive. For example, the original formulation by the Haskell community did not require modular typechecking, but the Scala community proposed that the Expression Problem should not only include modular extension (separate compilation etc.) of types and operations, but also modular typechecking and type inference of those extensions, which at the moment is something only Scala's implicits can do and Haskell's typeclasses and ML's functors can't.

Related Topic