[Compiler-sig] Visitor pattern

[Jeremy Hylton]

I've been meaning to get the compiler package's visitor documented,
but I'm not yet sure where to start.  (That is, I'm not sure which
things are novel or unusual and which are obvious.)

I think there are three key features:

    - Embed the name of the class being visited in the visitor
      method.  This wouldn't be necessary in Java, I assume, because
      each method would have the same name buts its argument list
      would be different.

    - The AST walker exploits knowledge of the AST structure to
      provide a default visit() method that will work on any node
      type.   

    - Responsibility for implementing the pattern is divided between a
      visitor and a walker.

The visitor implements a visitXXX() method for each node of interest.
The walker takes a visitor instance and the root of a node graph.  It
applies the visitor methods to the node graph starting with the root.

The second seems to apply regardless of language and can be quite
convenient.  If you're writing a simple symbol table visitor, you only
care about a few of the node types.  The If stmt, e.g., has no effect
on the symbol table, only its children do.  The default method makes
it possible to write a visitor that only has methods for the nodes it
cares about.

If we have a full specification of the AST (we do: python.asdl) and we
assume that the spec includes the children of each node in a "natural"
order, then we can generate a visitor method automatically.  By
natural, I mean a pre-order traversal of the tree, which has always
been what I've needed.

In the compiler package, each node type has a method getChildren()
that returns a tuple containing the children in the natural order.  

class If:

    def getChildren(self):
        return self.test, self.body, self.orelse

We should be able to define these as well, since the python.asdl
presents the children in the natural order.

If we have a visitor that isn't interested in If nodes, then it simply
doesn't define a visitIf() method.  If the AST contains an If node,
the default method of the walker handles it instead.

The default method on the walker does the following:

    for child in node.getChildren():
        if child is not None:
            self.visit(child)

The visit() method is defined by the walker.  It takes an arbitrary
node as its argument, looks up the appropriate method on the
visitor, and calls it.  The visitor can also use this method to
delegate responsibility for method lookup to the walker.

Does that help?  

I'm not sure how much of this maps naturally from Python to Java.

Jeremy