DOC PREVIEW
UMD CMSC 433 - Visitor Design Pattern

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UMD CMSC 433 - Visitor Design Pattern

Documents in this Course
Trace 1

Trace 1

62 pages

Reflection

Reflection

137 pages

Testing

Testing

25 pages

Paradigms

Paradigms

10 pages

Testing

Testing

17 pages

Java RMI

Java RMI

17 pages

Java RMI

Java RMI

17 pages

Java RMI

Java RMI

17 pages

Trace 1

Trace 1

46 pages

Jini

Jini

4 pages

Final

Final

15 pages

Java RMI

Java RMI

13 pages

Testing

Testing

16 pages

Load more
Download Visitor Design Pattern
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Visitor Design Pattern and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Visitor Design Pattern 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?