1CMSC 433 – Programming LanguageTechnologies and ParadigmsFall 2006Design Patterns2So far…• We discussed the following design patterns– Adapter– Abstract Factory– Bridge– Observer3What else we’re going to cover• Some quickies– Iterator– Decorator– Singleton• One important and big pattern– Visitor pattern4Midterm• Tuesday, Oct 24th– Let me know now if you have a scheduled conflict, orneed to take the test in anyway other than being in thisroom on the 24th• Cover everything discussed so far– plus, refactoring and bad code smells5Iterator Pattern• There are lots of things you can iterate over.• Lots of places where you want to iterate over oneof those things• Rather than have each place worry about “how doI iterate over the elements here”– use a design pattern, and standard interface, so we canuse the same idiom and the same code6What could we iterate over?• Collection• Tree (pre-order, post-order, in-order)• Lines of text in a file• Prime numbers• Random numbers7More on Iterators• Java 5 added Iterable– anything that has an iterator method• Can use the new for loop syntax over anything thatimplements Iterable• Iterating over something shouldn’t change it• Java’s Iterator class provides a remove method– not supported by all implementations• The semantics of iterating over something that is modifiedduring the iteration is implementation dependent8Decorator pattern• Read sample chapter from Head First DesignPatterns– http://www.oreilly.com/catalog/hfdesignpat/chapter/ch03.pdf9Comments on decorators• Multiple decorators results in a sequences ofdecorators– not all orders give the same behaviors– if a decorator adds any new methods, they are onlyvisible if outermost• or if a reference to the inner decorator is retained10Singleton• A class for which you want to create at most oneinstance in any JVM– You want any code in the JVM using this class to beusing the same instance of the class• Singletons often implement an interface or extenda class– otherwise, you could just use static methods11Two basic cases• Stateless singletons– the advantage of a stateless singleton is that you onlycreate is once (which might have side effects) and youdon’t pay the cost of duplicated instances• Stateful singletons– everyone needs to see updates to the state of the oneand only singleton• everyone includes multiple threads12Creating a singleton• Far easier than you might suspect.• Lot of books and references get this wrong.final class Elvis extends Person { public static final Elvis INSTANCE = new Elvis(); private Elvis() { ... }}13Guaranteed Lazy and Thread Safe• The field will be set by the class’s static initializer• The static initializer is not invoked until the firstactive use of the class:– invoking a static method or accessing a static field– creating an instance of the class– initializing a subclass• JVM uses locking so that even if multiple threadstry to access INSTANCE at the same time, it justworks14Double Checked Locking• If someone tells you should use double checkedlocking for a singleton, tell them they are wrong• Double checked locking does have some use cases– lazy thread safe initialization• But you need to use volatile to make it work– we’ll come back to this15Visitor Pattern16Visitor: 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 object17Abstract Syntax Treespublic interface Node { }public class Number extends Node { public int n;}public class Plus extends Node { public Node left; public Node right;}18Traversing Abstract Syntax Treespublic interface Node { public int sum();}public class Number extends Node { public int n; public int sum() { return n; }}public class Plus { public Node left; public Node right; public int sum() { return left.sum() +right.sum(); } }19Naïve approach (not a visitor)One methodfor eachanalysis20Tradeoffs 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 maintain21Use 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/operation22Sample Visitor class23How 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 object24Sample visited objects25Vistor InteractionaNodeStructureaAssignmentNode aVariableRefNode aTypeCheckingVisitorAccept(aTypeCheckingVisitor)VisitAssignment(aAssignmentNode)VisitVariableRef(aVariableRefNode)Accept (aTypeCheckingVisitor)someOperation()someOperation()26Sample 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);}27Change 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);}}28Visitor 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 changedoften29Visitor Pattern Structure• Define two class hierarchies– One for object structure• AST in compiler, Glyphs in Lexi– One for each operation family, called visitors• One for typechecking, code generation, pretty printing in compiler• One for spellchecking or hyphenation in
View Full Document