Tree Transformations Using Visitor Pattern

Question

(Disclaimer: these examples are given in the context of building a compiler, but this question is all about the Visitor pattern and does not require any knowledge of compiler theory.) I'm going through Andrew Appel's Modern Compiler Implementation in Java to try to teach myself compiler theory (so no, this isn't homework) and I'm having trouble understanding how he wants to use the Visitor pattern to transform an AST to an IR tree. (Note: I'm doing this in Python so I can learn Python also, which is why the upcoming examples are not in Java.) As I understand it, the visit and accept methods in the Visitor pattern are void-typed by design, so if I have something like

class PlusExp(Exp):
    def __init__(self, exp_left, exp_right):
        self.exp_left = exp_left
        self.exp_right = exp_right

    def accept(self, v):
        v.visit_plus_exp(self)

then I would like to be able to write a visitor method like

def visit_plus_exp(self, plus_exp):
    return BINOP(BinOp.PLUS, 
                 plus_exp.exp_left.accept(self), 
                 plus_exp.exp_right.accept(self))

which would translate the two child expressions into IR and then link them up with the BINOP representing the plus expression. Of course, this isn't possible unless I modify all the accept functions to return extra info, and that is also messy because sometimes you just want a print visitor that doesn't return anything. Yet, this text insists that a visitor is the right way to go, and in Java at that, which means it can be done without the flexibility of Python. I can't think of any solutions that aren't incredibly hacky - can anyone enlighten me as to the intended design?

Answer 1

Caveat: I haven't read that book.

The method may be void-typed, but in Java (which the book was written for) it is also part of an object. So, the visitor method can build up the structure in a local member variable, thus maintaining the necessary context between calls.

So, for instance, your print visitor would be appending to a StringBuilder that is held as a member variable (or as a final local variable in a method that created the visitor object -- this is fairly common in Java, where creating small anonymous-inner-class objects is a common habit).

In python, you could similarly let the visitor method access a non-method-local variable to maintain context and build the structure. Eg, closure, or a small object.

Update -- small bit of code added as example from comment below

result = new Node();
result.left.add(n1.accept(this)); 
result.right.add(n2.accept(this)); 
return result;

or

result = new Node(); 
this.nextLoc.add(result); 
this.nextLoc = result.left; 
n1.accept(this); 
this.nextLoc = result.right; 
n2.accept(this);

The first is prettier (though still crappy comment example code), but the second would let you keep the void return type if you really needed to.

Answer 2

Look at source code of THIS compiler. I think that the guy has used Visitor pattern.

Answer 3

A SAX parser is a kind of visitor. To avoid adding a return value to the method, you can use a stack:

class Visitor {
    Stack<Node> stack = new Stack<Node>();

//    . . .

    void visitPlus(PlusExp pe) {
        pe.left.accept(this);
        pe.right.accept(this);
        Node b = stack.pop();
        Node a = stack.pop();
        stack.push(new BinOp(BinOp.PLUS, a, b));
    }