Transcript CS 501 Introduction to Design Patterns

CS 501
Introduction to Design Patterns
Nate Nystrom
Eric Melin
November 9, 1999
Motivation
• Designing reusable software is hard
– usually impossible to get right the first time
– takes several uses of a design to get it right
• Experts base new designs on prior
experience
• In many systems, you find recurring
patterns of software components
– classes, protocols, etc.
Design patterns
• Idea: extract these common patterns and
create a catalog of design patterns
– allows other designers to reuse successful
designs and avoid unsuccessful ones
– creates a common vocabulary for discussing
designs
– 1995: Design Patterns book by the Gang of
Four (Gamma, Helm, Johnson, Vlissides)
» describes 21 common patterns
What is a design pattern?
• A pattern has four components:
– A name
– A problem
– A solution
– Consequences
Name
• Immediately allows you to design at a
higher level of abstraction
• Allows you to discuss the pattern with
others
Problem
• What problem does the pattern solve?
• When do you apply the pattern?
Solution
• Elements that make up the design
• Relationships, responsibilities,
collaborations
• NOT a particular concrete design or
implementation
– A pattern is a template that can be applied in
many different situations
Consequences
• Results and trade-offs of applying the
pattern
• Impact on system's flexibility, extensibility,
portability
What is not a design pattern?
•
•
•
•
A
A
A
A
design of a data structure
domain-specific design
design of an entire application
design used only once
– A design pattern should capture mature,
proven practices
Classifying design patterns
• GoF identified two criteria for classifying
design patterns
– Purpose
– Scope
Purpose
• Creational patterns
– describe how objects are created
• Structural patterns
– describe the composition of classes or objects
• Behavioral patterns
– describe the interaction of classes or objects
and how responsibility is distributed
Scope
• Class patterns
– Deal with relationships between classes and
their subclasses
• Object patterns
– Deal with relationships between objects
– Relationships can change at run-time and are
thus more dynamic
Non-OO design patterns
• Design patterns are not limited to objectoriented software
• Objects are just one way to partition a
system, sometimes not the best way
• You will find many more mature patterns
in legacy systems than you will in OO
software
Before Patterns: Motorola
• Factors preventing software reuse
– Strong coupling of classes/objects
– Short-term needs superseded longer-term
• Architecture specifications suffered from
– Ambiguity and lack of precision in the specs
– Differing terminology
– No direct access to the architects
Review of OO concepts
• OO programs are made up of objects
– An object packages both data and operations
on that data
– An object's operations are called methods
– An object's implementation is defined by its
class
– New classes can be defined using existing
classes through inheritance
Encapsulation
• In pure OO: method invocations
(messages) are the only way an object
can execute an operation
– The object's internal state is encapsulated
– Encapsulation is often violated for efficiency
Polymorphism
• Different objects can handle identical
messages with different implementations
• Dynamic binding: Run-time association of
a message to an object and one of the
object's operations
• Can substitute objects that implement the
same interface at run-time
Inheritance
• There is a distinction between an object's
class and its type
– Class defines how an object is implemented
– Type defines the object's interface
– Java thus defines two forms of inheritance
» Implementation inheritance
– Ex: class B extends A { m() {} }
» Interface inheritance
– Ex: class C implements I { m() {} }
Reuse through subclassing
• Easier to modify the implementation being
reused
• But, breaks encapsulation
» Implementation of the subclass bound to that of
the parent
– any change to the parent requires change to the
subclass
» Must reimplement parent if any aspect of the its
implementation is not appropriate to the new
context in which it is used
Reuse through composition (1)
• Requires carefully designed interfaces
• Doesn’t break encapsulation
– Any object can be replaced by another at runtime if it implements the same interface
– Fewer implementation dependencies
• Helps design
– keeping each class encapsulated forces you
to keep classes simple
Reuse through composition (2)
• But, composition leads to more objects in
the system
– Behavior depends on interrelationships
between many objects not on one class
GoF’s Principles of OO design
• Program to an interface, not an
implementation
• Favor composition over inheritance
» Ideally, get all the functionality you need by
composing existing components
» In practice, available components aren’t rich
enough
» Reuse by inheritance easier to create new
components that can be composed of old ones
Summary
• Patterns
– are a good team communication medium
– are extracted from working designs
– capture the essential parts of a design in
compact form
– can be used to record and encourage the
reuse of "best practices"
– are not necessarily object-oriented
The Iterator pattern
• Provides a way to access elements of an
aggregate object without exposing the
underlying representation
– Ex: a List class
» Want to traverse the list in several ways
–
–
–
–
–
forward
backward
filtered
sorted
...
Motivation for iterators
• Don't want to bloat the List interface with
several different traversals
» Even if you do, you can't anticipate all the possible
traversals
• Might want >1 traversal on the same list
• Iterator moves responsibility for access
and traversal from the aggregate to an
iterator object
Iterator example (1)
class List {
size() {}
add() {}
remove() {}
}
interface ListIterator {
getFirst();
getNext();
}
Iterator example (2)
class FilteredListIterator implements ListIterator {
List.Node curr;
FilteredListIterator(List list, Filter f) {}
getFirst() {
curr = list.head;
while (curr != null) {
if (f.accepts(curr.data))
break;
curr = curr.next;
}
return curr;
}
getNext() {}
}
More on the Iterator pattern
• Iterators provide a common interface for
accessing aggregates
– Can use the same interface for lists
implemented as arrays and lists implements
as linked lists
– Easier to change data structure
implementations
• See java.util in JDK 1.2 for good examples
The Visitor pattern
• Represent an operation to be performed
on the elements of an object structure
• Lets you defined a new operation without
changing the classes of the elements on
which it operates
Visitor example: a compiler
• Consider a compiler that represents a
program as an abstract syntax tree
• Need to perform operations on the AST
– type checking
– optimization
– code generation
Example AST
ForLoop
Assign
Var i
Compare
Int 0
Op(<)
Var i
Increment
Var n
Var i
List
Assign
Var t
List
Call
Var f
ArgList
Var i
for (i = 0; i < 100; i++) {
t = f(i,true);
a[i] = t;
}
Assign
ArrayRef
ArgList
Bool true
Var a
nil
Var i
nil
Var t
Design 1
• Operations treat nodes of different types
differently
– Ex: code generated for assignments is
different than code generated for calls
• Proposed design: add a method to each
node class to perform a particular
operation on that node type
Design 1 example
class Assign {
genCode() {}
typeCheck() {}
optimize() {}
}
class Call {
genCode() {}
typeCheck() {}
optimize() {}
}
Problem with Design 1
• Every time we add or modify an
operation, we have to change the class for
each node type
– Ex: one Java bytecode analyzer has 61
different node types
Design 2
• Better solution:
– Put each operation in a different class called a
visitor
– Works well if we assume adding new node
types is uncommon
» We have to update all the visitors when a new
node type is added
Design 2 example (1)
interface ASTVisitor {
visitAssign(Assign a);
visitCall(Call c);
...
}
class Assign
{
Exp left;
Exp right;
...
accept(ASTVisitor v) {
left.accept(v);
right.accept(v);
v.visitAssign(this);
}
}
Design 2 example (2)
class TypeCheckVisitor implements ASTVisitor
{
visitAssign(Assign a)
{
Type ltype = a.getLeft().getType();
Type rtype = a.getRight().getType();
if (! Ltype.isSuperOf(rtype)) {
errors.add(...);
}
}
...
}
Creational and Structural
Patterns
• Creational
– Encapsulate knowledge about which concrete classes
the system uses
– Hide how instances of these classes are created and
put together
– Examples: Singleton, Abstract Factory
• Structural
– Describe how classes and objects are composed into
larger structures
– Examples: Proxy, Façade, Composite
Singleton
Intent – Ensure a class has only one instance and provide a global point of access
• Motivation
– Some classes need exactly one instance
» One window manager, one file system, one print spooler
– Need global access, but global variable does not prevent
multiple instantiation
– Have class keep track of it’s sole instance
Singleton (2)
• Applicability
– There must be exactly one instance of a class and it must be accessible
to multiple clients
– The sole instance should be extensible by subclassing, and clients
should be able to use subclass without modifying code
• Consequences
–
–
–
–
Controlled access to sole instance
Reduced name space (over global variable)
Extendable implementation
Permits a variable number of instances – (easy to change if don’t want
singleton)
– More flexible than static member functions – allows subclassing and
easy to change to multiple number of instances
Abstract Factory
Intent – Provide an interface for creating families of related objects
without specifying their concrete classes
Example of Abstract Product and Concrete Products
Abstract Factory (2)
Abstract Factory (3)
• Applicability
– A system should be independent of how its products
are created, composed, and represented
– A system should be configured with multiple families
of products
– Need to enforce constraint “a family of related
product objects should be glued together”
– Want to provide library of products and reveal only
their interfaces
Abstract Factory (4)
• Consequences
–
–
–
–
Concrete classes are isolated to concrete factory
Allows easy exchanging of product families
Promotes consistency amongst products
It is hard to add new types of products
Proxy
A proxy provides a placeholder for another object to access it
Proxy (2)
• Structure
– The proxy has the same interface or superclass as the real subject
– The proxy contains a reference to real subject which the proxy can
use to forward requests to the real subject
• Applicability
– A remote proxy acts as a local representation for a remote object
– A virtual proxy creates expensive objects on demand
» Example – a proxy for a graphical image when image is not on screen
– A protection proxy controls access to the original object
– A firewall proxy protects local clients from outside world
– A cache proxy (server proxy) saves network resources by
storing results
– Smart Reference
» Example - garbage collector reference counter (Smart Pointers)
Proxy (3)
• Consequences
– Proxy introduces a level of indirection.
– Remote proxy can hide fact that object resides elsewhere
– Copy-on-write is possible – this is a significant optimization for
heavy-weight components
Façade
Intent - provide a unified interface to a set of interfaces in a subsystem
Façade (2)
• Motivation
– Structuring a system into subsystems reduces complexity
– Want to reduce communications and dependencies between
subsystems
• Applicability
– Want to provide a simple interface to a complex subsystem
– There are many dependencies between clients and
implementation classes in a subsystem. Want to decouple the
subsystem from clients and other subsystems
– Want to layer subsystems – Can use a façade to define entry
point to each subsystem level
Façade (3)
• Consequences
– Façade reduces the number of objects that clients
deal with to make the subsystem easier to use
– Promotes weak coupling between subsystem and
clients. This allows you to change subsystem
implementation without affecting clients
– Allows clients to use subsystem classes if they need
to
– Subsystem components are not aware of façade
Comparison of Patterns
• Proxy vs. Façade
– A facade represents a system of objects
– A proxy represents a single object
– A facade simplifies the interact between client and
the system
– A proxy controls the access to the single object
Composite
Compose objects into tree structures to let clients treat individual
objects and compositions of objects uniformly
Composite (2)
Composite (3)
• Motivation
– How does a window hold and deal with the different items it has
to manage?
– Graphics - Containers and widgets
» Panel, Menu, Window
» Line, Rectangle, Text
– Cut And Paste
Composite (4)
• Applicability
– Want to represent part-whole hierarchies of objects
– Want clients to be able to ignore the difference between
compositions of objects and individual objects.
• Consequences
– Whenever client code expects a primitive object, it can also
receive a composite object
– Makes the client simple
– Facilitates adding of new components
– Can make design overly general – makes it hard to restrict the
components of a composite
Composite Implementation Issues
• Explicit parent references
• Sharing parents – wasteful not to, but need ability for child to
have multiple parents
• Maximize Component interface – Component should define as
many common operations as possible
• Child management operations are tricky
– Can define child management operations in Component Class (root
of hierarchy)
» Unsafe - What does adding a child to a leaf node mean?
– Can define child management in Composite class
» Safety, but – Now downcasts or instanceof checks into components and
leaves are necessary
References
• Design Patterns: Elements of Reusable Object-Oriented Software,
Gamma, Helm, Johnson, Vlissides, Addison Wesley, 1995, pp 207217
• http://www.eli.sdsu.edu/courses/spring98/cs635/index.html
• http://st-www.cs.uiuc.edu/cgi-bin/wikic/wikic
• http://www.tcm.hut.fi/~pnr/GoF-models/html/