Notes for cs164 Section 1

• The Visitor pattern
• If we can edit AST source code, we can add operations by adding a method to ASTNode and all subclasses, eg. interpret() or prettyPrint().
• What if we can't edit the AST code? We must define new operations externally. Consider interpret():
• Put all interpret() methods together. Since they aren't inside AST node classes anymore, need to pass AST node as parameter.

interpret(InfixExpression e) { interpret(e.getLeftOp()); interpret(e.getRightOp()); ... }
interpret(WhileStatement w) { ... }

• Problem: Java method dispatch based on declared type of arguments. Example (InfixExpression extends ASTNode):

ASTNode n = new ASTNode();
InfixExpression e = new InfixExpression();
ASTNode n2 = new InfixExpression();
interpret(n); // calls interpret(ASTNode)
interpret(e); // calls interpret(InfixExpression)
interpret(n2); // calls interpret(ASTNode)!

So, calling interpret(e.getLeftOp()) above may not invoke the correct interpret() method. We need to add explicit dispatch code:

o if (e.getLeftOp() instanceof InfixExpression) { interpret((InfixExpression)e.getLeftOp()); }
else if (e.getLeftOp() instanceof NumberLiteral) { interpret((NumberLiteral)e.getLeftOp()); }
...

o This is ugly!

o A better solution: AST designed with a "hook" allowing for new operations to easily be added externally. Each AST node class has an accept() method that takes a visitor object as a parameter. Each visitor class contains some operation to be performed on the AST, defined in visit() methods for each type of AST node. The accept() methods are simple:

accept(Visitor v) { v.visit(this); }

Since the declared type of this is always the type of the enclosing class, the correct visit() method will be invoked. Written as a visitor, the original interpret() method for InfixExpression looks like this:

visit(InfixExpression e) { e.getLeftOp().accept(this); e.getRightOp().accept(this); ... }

o Other advantages of visitor: all the code for an operation is in one place, avoids cluttering interface of AST nodes, easy to share state between methods (through fields).