1CMSC 433 – Programming LanguageTechnologies and ParadigmsSpring 2006Visitor Design Pattern2Visitor: Implementing Analyses• Often want to implement multiple analyses on thesame kind of object data– Book example: computing with Menus– Project example: Generating code for and analyzing anAbstract Syntax Tree (AST) in a compiler• One solution: implement each analysis as amethod in each object3Abstract Syntax Treespublic interface Node { }public class Number extends Node { public int n;}public class Plus extends Node { public Node left; public Node right;}4Traversing Abstract Syntax Treespublic interface Node { public int sum();}public class Number extends Node { public int n; public int sum() { return n; }}public class Plus extends Node{ public Node left; public Node right; public int sum() { return left.sum() +right.sum(); } }5Naïve approach (not a visitor)One methodfor eachanalysis6Tradeoffs with this Approach• Follows idea “objects are responsible for themselves”• But many analyses will occlude the object’s main code• Result is classes that are hard to maintain7Use a Visitor• Alternatively, can define a separate visitor class– A visitor encapsulates the operations to be performedon an entire structure, e.g., all elements of a parse tree• Allows operations to be separate from structure– But doesn’t necessarily require putting all of thestructure traversal code into each visitor/operation8Sample Visitor class9How to perform traversal?• Now that we have a visitor class, how do we applyits analysis to the objects of interest?– Add accept(visitor) method to each structure class, thatwill invoke the given visitor on this– Builds on Java’s dynamic dispatch– Use an iteration algorithm (like an Iterator) to callaccept() on each relevant object10Sample visited objects11Vistor InteractionaNodeStructureaAssignmentNode aVariableRefNode aTypeCheckingVisitorAccept(aTypeCheckingVisitor)VisitAssignment(aAssignmentNode)VisitVariableRef(aVariableRefNode)Accept (aTypeCheckingVisitor)someOperation()someOperation()12Sample Visitor Classpublic interface Visitor { public void visitNumber(Number n); public void visitPlus(Plus p);}public class SumVisitor implements Visitor { int sum; public void visitNumber(Number n) { sum += n; } public void visitPlus(Plus p) { p.left.accept(this); p.right.accept(this);}13Change to AST Classespublic interface Node { public void accept(Visitor v);}public class Number extends Node { … public void accept(Visitor v) {v.visitNumber(this);}}public class Plus extends Node { … public void accept(Visitor v) {v.visitPlus(this);}}14Visitor pattern• Name– Visitor or double dispatching• Applicability– Related objects must support different operations andactual op depends on both the class and the op type– Distinct and unrelated operations pollute class defs– Key: object structure rarely changes, but ops changedoften15Visitor Pattern Structure• Define two class hierarchies– One for object structure• AST in compiler, Menus and MenuItems in book example– One for each operation family, called visitors• One for typechecking, code generation, pretty printing in compiler• One for printing menus, figuring out the per/item average cost, etc.16Structure of Visitor Pattern17Visitor Pattern Consequences• Adding new operations is easy– Add new op subclass with method for each concrete elt class– Easier than modifying every element class• Gathers related operations and separates unrelated ones• Adding new concrete elements is difficult– Must add a new method to each concrete Visitor subclass• Allows visiting across class hierachies– Iterator needs a common superclass (i.e., composite pattern)• Visitor can accumulate state rather than pass it asparameters18Double-Dispatch• Accept code is always trivial– Just dynamic dispatch on argument, with runtime typeof structure node taking into account in method name• A way of doing d ouble-dispatch– Traversal routine takes two arguments, the visitor andthe object to traverse• o.accept(aVisitor) will dispatch on the actual identity of o (the objectbeing considered)• ...and accept will internally dispatch on the identity of aVisitor (theobject visiting it)19Using Overloading in a Visitor• You can name all of the visitXXX(XXX x)methods just visit(XXX x)– Calls to Visit (AssignmentNode n)and Visit(VariableRefNode n) distinguished bycompile-time overload resolution20Visitors Can Forward Common Behavior• Useful for composites– If subclasses of a particular object all treated the same– Can have visit(SubClass) call visit(SuperClass)• For example– visit(BinaryPlusOperatorNode) can just forward call to superclassvisit(BinaryOperatorNode)21State in a Visitor Pattern• A visitor can contain state– E.g., the results of typechecking the program so farclass TypeCheckingVisitor extends Visitor { private TypeMap map; void visit(VariableDefNode n) { … map.add(n,t) … }}• Or visitors pass around a separate state object– Impacts the type of the Visitor superclass22Implementing Traversal• Who is responsible for traversing object structure?• Plausible answers:– Visitor• But, must replicate traversal code in each concrete visitor– Object structure• Define operation that performs traversal while applying visitor objectto each component– Iterator• Iterator sends message to visitor with current element as arg23Traversals• It’s sometimes preferable to try to keep traversal separatefrom the Visitor– E.g., use an Iterator– Thus traversal and analysis can evolve independently• But can also do it within node or visitor class. Severalsolutions here:– acceptAndTraverse methods• traverse from within accept()– Separating processing from traversal• Visit/process methods– Traversal visitors applying an operational visitor24Accept and Traverse Example• Class BinaryPlusOperatorNode {void accept(Visitor v) {v.visit(this);lhs.accept(v);rhs.accept(v);}…}25acceptAndTraverse Methods• Accept method could be responsible for traversingchildren– Assumes all visitors have same traversal pattern• E.g., visit all nodes in pre-order traversal– Could provide previsit and postvisit methods to allowfor more complicated traversal patterns• Still visit every node• Can’t do out of order traversal• In-order traversal requires inVisit method26Visitor/Process Methods• Can have two parallel sets of methods in
View Full Document