Wednesday, December 29, 2004

Patterns 3 : Behavioral patterns

Chain of Responsibility
The Chain of Responsibility pattern allows a number of classes to attempt to handle a request, without any of them knowing about the capabilities of the other classes. It provides a loose coupling between these classes; the only common link is the request that is passed between them. The request is passed along until one of the classes can handle it.

We use the Chain of Responsibility when
· You have more than one handler that can handle a request and there is no way to know which handler to use. The handler must be determined automatically by the chain.
· You want to issue a request to one of several objects without specifying which one explicitly.
· You want to be able to modify the set of objects dynamically that can handle requests.

A Chain or a Tree?
Of course, a Chain of Responsibility does not have to be linear. The Smalltalk Companion suggests that it is more generally a tree structure with a number of specific entry points all pointing upward to the most general node.

Another way of handling a tree-like structure is to have a single entry point that branches to the specific button, menu or other widget types, and then “un-branches” as above to more general help cases. There is little reason for that complexity -- you could align the classes into a single chain, starting at the bottom, and going left to right and up a row at a time until the entire system had been traversed.

Consequences of the Chain of Responsibility
1. The main purpose for this pattern, like a number of others, is to reduce coupling between objects. An object only needs to know how to forward the request to other objects.
2. This approach also gives you added flexibility in distributing responsibilities between objects. Any object can satisfy some or all of the requests, and you can change both the chain and the responsibilities at run time.
3. An advantage is that there may not be any object that can handle the request, however, the last object in the chain may simply discard any requests it can’t handle.
4. Finally, since Java can not provide multiple inheritance, the basic Chain class needs to be an interface rather than an abstract class, so that the individual objects can inherit from another useful hierarchy, as we did here by deriving them all from JPanel. This disadvantage of this approach is that you often have to implement the linking, sending and forwarding code in each module separately.

Command pattern
The Chain of Responsibility forwards requests along a chain of classes, but the Command pattern forwards a request only to a specific module. It encloses a request for a specific action inside an object and gives it a known public interface. It lets you give the client the ability to make requests without knowing anything about the actual action that will be performed, and allows you to change that action without affecting the client program in any way.

One important purpose of the Command pattern is to keep the program and user interface objects completely separate from the actions that they initiate. In other words, these program objects should be completely separate from each other and should not have to know how other objects work. The user interface receives a command and tells a Command object to carry out whatever duties it has been instructed to do. The UI does not and should not need to know what tasks will be executed.

The Command object can also be used when you need to tell the program to execute the command when the resources are available rather than immediately. In such cases, you are queuing commands to be executed later. Finally, you can use Command objects to remember operations so that you can support Undo requests.

Consequences of the Command Pattern
The main disadvantage of the Command pattern is a proliferation of little classes that either clutters up the main class if they are inner or clutters up the program namespace if they are outer classes.
Now even in the case where we put all of our actionPerformed events in a single basket, we usually call little private methods to carry out the actual function. It turns out that these private methods are just about as long as our little inner classes, so there is frequently little difference in complexity between inner and outer class approaches.

Anonymous Inner Classes
We can reduce the clutter of our name space by creating unnamed inner classes by declaring an instance of a class on the spot where we need it. For example, we could create our Red button and the class for manipulating the background all at once

btnRed.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
} );

This is not very readable, however, and does not really improve the number of run-time classes since the compiler generates a class file even for these unnamed classes.

In fact, there is very little difference in the compiled code size among these various methods, once you create classes in any form at all.

Byte code size of Command class implementations
Program type Byte code size
No command classes 1719
Named inner classes 4450
Unnamed inner classes 3683
External classes 3838

Providing Undo
Another of the main reasons for using Command design patterns is that they provide a convenient way to store and execute an Undo function. Each command object can remember what it just did and restore that state when requested to do so if the computational and memory requirements are not too overwhelming.

Interpreter pattern
Some programs benefit from having a language to describe operations they can perform. The Interpreter pattern generally describes defining a grammar for that language and using that grammar to interpret statements in that language.

When a program presents a number of different, but somewhat similar cases it can deal with, it can be advantageous to use a simple language to describe these cases and then have the program interpret that language. Such cases can be as simple as the sort of Macro language recording facilities a number of office suite programs provide, or as complex as Visual Basic for
Applications (VBA). VBA is not only included in Microsoft Office products, but can be embedded in any number of third party products quite simply.

One of the problems we must deal with is how to recognize when a language can be helpful. The Macro language recorder simply records menu and keystroke operations for later playback and just barely qualifies as a language; it may not actually have a written form or grammar. Languages such as VBA, on the other hand, are quite complex, but are far beyond the
capabilities of the individual application developer. Further, embedding commercial languages such as VBA, Java or SmallTalk usually require substantial licensing fees, which make them less attractive to all but the largest developers.

As the SmallTalk Companion notes, recognizing cases where an Interpreter can be helpful is much of the problem, and programmers without formal language/compiler training frequently overlook this approach. There are not large numbers of such cases, but there are two general places where languages are applicable:

1. When the program must parse an algebraic string. This case is fairly obvious. The program is asked to carry out its operations based on a computation where the user enters an equation of some sort. This frequently occurs in mathematical-graphics programs, where the program renders a curve or surface based on any equation it can evaluate.
Programs like Mathematica and graph drawing packages such as Origin work in this way.

2. When the program must produce varying kinds of output. This case is a little less obvious, but far more useful. Consider a program that can display columns of data in any order and sort them in various ways. These programs are frequently referred to as Report Generators, and
while the underlying data may be stored in a relational database, the user interface to the report program is usually much simpler then the SQL language which the database uses. In fact, in some cases, the simple report language may be interpreted by the report program and translated into SQL.

Consequences of the Interpreter Pattern
Whenever you introduce an interpreter into a program, you need to provide a simple way for the program user to enter commands in that language. It can be as simple as the Macro record button we noted earlier, or it can be an editable text field like the one in the program above.

However, introducing a language and its accompanying grammar also requires fairly extensive error checking for misspelled terms or misplaced grammatical elements. This can easily consume a great deal of programming effort unless some template code is available for implementing this checking. Further, effective methods for notifying the users of these errors are not easy to design and implement.

In the Interpreter example above, the only error handling is that keywords that are not recognized are not converted to ParseObjects and pushed onto the stack. Thus, nothing will happen, because the resulting stack sequence probably cannot be parsed successfully, or if it can, the item represented by the misspelled keyword will not be included.

You can also consider generating a language automatically from a user interface of radio and command buttons and list boxes. While it may seem that having such an interface obviates the necessity for a language at all, the same requirements of sequence and computation still apply. When you have to have a way to specify the order of sequential operations, a language is a good way to do so, even if the language is generated from the user interface.

The Interpreter pattern has the advantage that you can extend or revise the grammar fairly easily one you have built the general parsing and reduction tools. You can also add new verbs or variables quite easily once the foundation is constructed.

In the simple parsing scheme we show in the Parser class above, there are only 6 cases to consider, and they are shown as a series of simple if statements. If you have many more than that, Design Patterns suggests that you create a class for each one of them. This again makes language extension easier, but has the disadvantage of proliferating lots of similar little classes. Finally, as the syntax of the grammar becomes more complex, you run the risk of creating a hard to maintain program. While interpreters are not all that common in solving general programming problems, the Iterator pattern we take up next is one of the most common ones you’ll be using.

Iterator pattern
The Iterator is one of the simplest and most frequently used of the design patterns. The Iterator pattern allows you to move through a list or collection of data using a standard interface without having to know the details of the internal representations of that data. In addition you can also define special iterators that perform some special processing and return only specified elements of the data collection.

Mediator pattern
When a program is made up of a number of classes, the logic and computation is divided logically among these classes. However, as more of these isolated classes are developed in a program, the problem of communication between these classes become more complex. The more each class needs to know about the methods of another class, the more tangled the class structure can become. This makes the program harder to read and harder to maintain. Further, it can become difficult to change the program, since any change may affect code in several other classes. The Mediator pattern addresses this problem by promoting looser coupling between these classes. Mediators accomplish this by being the only class that has detailed knowledge of the methods of other classes. Classes send inform the mediator when changes occur and the Mediator passes them on to any other classes that need to be informed.

Consequences of the Mediator Pattern
1. The Mediator makes loose coupling possible between objects in a program. It also localizes the behavior that otherwise would be distributed among several objects.
2. You can change the behavior of the program by simply changing or subclassing the Mediator.
3. The Mediator approach makes it possible to add new Colleagues to a system without having to change any other part of the program.
4. The Mediator solves the problem of each Command object needing to know too much about the objects and methods in the rest of a user interface.
5. The Mediator can become monolithic in complexity, making it hard to change and maintain. Sometimes you can improve this situation by revising the responsibilities you have given the Mediator. Each object should carry out it’s own tasks and the Mediator should only manage the
interaction between objects.
6. Each Mediator is a custom-written class that has methods for each Colleague to call and knows what methods each Colleague has available. This makes it difficult to reuse Mediator code in different projects. On the other hand, most Mediators are quite simple and writing this code is far easier than managing the complex object interactions any other way.

Implementation Issues
The Mediator pattern we have described above acts as a kind of Observer pattern, observing changes in the Colleague elements. Another approach is to have a single interface to your Mediator, and pass that method various constants or objects which tell the Mediator which operations to perform. In the same fashion, you could have a single Colleague interface that each Colleague would implement, and each Colleague would then decide what operation it was to carry out.
Mediators are not limited to use in visual interface programs, however, it is their most common application. You can use them whenever you are faced with the problem of complex intercommunication between a number of objects.

Memento pattern
Suppose you would like to save the internal state of an object so you can restore it later. Ideally, it should be possible to save and restore this state without making the object itself take care of this task, and without violating encapsulation. This is the purpose of the Memento pattern.

Objects frequently expose only some of their internal state using public methods, but you would still like to be able to save the entire state of an object because you might need to restore it later. In some cases, you could obtain enough information from the public interfaces (such as the drawing position of graphical objects) to save and restore that data. In other cases, the color, shading, angle and connection relationship to other graphical objects need to be saved and this information is not readily available. This sort of information saving and restoration is common in systems that need to support

Undo commands.
If all of the information describing an object is available in public variables, it is not that difficult to save them in some external store. However, making these data public makes the entire system vulnerable to change by external program code, when we usually expect data inside an object to be private and encapsulated from the outside world.

The Memento pattern attempts to solve this problem by having privileged access to the state of the object you want to save. Other objects have only a more restricted access to the object, thus preserving their encapsulation. This pattern defines three roles for objects:
1. The Originator is the object whose state we want to save.
2. The Memento is another object that saves the state of the Originator.
3. The Caretaker manages the timing of the saving of the state, saves the Memento and, if needed, uses the Memento to restore the state of the Originator.

Consequences of the Memento
The Memento provides a way to preserve the state of an object while preserving encapsulation, in languages where this is possible. Thus, data that only the Originator class should have access to effectively remains private. It also preserves the simplicity of the Originator class by delegating the saving and restoring of information to the Memento class. On the other hand, the amount of information that a Memento has to save might be quite large, thus taking up fair amounts of storage. This further has an effect on the Caretaker class (here the Mediator) which may have to design strategies to limit the number of objects for which it saves state. In our simple example, we impose no such limits. In cases where objects change in a predictable manner, each Memento may be able to get by with saving only incremental changes of an object’s state.

Other Kinds of Mementos
While supporting undo/redo operations in graphical interfaces is one significant use of the Memento pattern, you will also see Mementos used in database transactions. Here they save the state of data in a transaction where it is necessary to restore the data if the transaction fails or is incomplete.

Observer pattern
Consequences of the Observer Pattern
Observers promote abstract coupling to Subjects. A subject doesn’t know the details of any of its observers. However, this has the potential disadvantage of successive or repeated updates to the Observers when there are a series of incremental changes to the data. If the cost of these updates is high, it may be necessary to introduce some sort of change management, so that the Observers are not notified too soon or too frequently. When one client makes a change in the underlying data, you need to decide which object will initiate the notification of the change to the other observers. If the Subject notifies all the observers when it is changed, each client is not responsible for remembering to initiate the notification. On the other hand, this can result in a number of small successive updates being triggered. If the clients tell the Subject when to notify the other clients, this cascading notification can be avoided, but the clients are left with the responsibility of telling the Subject when to send the notifications. If one client “forgets,” the program simply won’t work properly. Finally, you can specify the kind of notification you choose to send by defining a number of update methods for the Observers to receive depending on the type or scope of change. In some cases, the clients will thus be able to ignore some of these notifications

State pattern
The State pattern is used when you want to have an enclosing class switch between a number of related contained classes, and pass method calls on to the current contained class. Design Patterns suggests that the State pattern switches between internal classes in such a way that the enclosing object appears to change its class. In Java, at least, this is a bit of an exaggeration, but the actual purpose to which the classes are put can change significantly.

Many programmers have had the experience of creating a class which performs slightly different computations or displays different information based on the arguments passed into the class. This frequently leads to some sort of switch or if-else statements inside the class that determine which behavior to carry out. It is this inelegance that the State pattern seeks to replace.

Consequences of the State Pattern
1. The State pattern localizes state-specific behavior in an individual class for each state, and puts all the behavior for that state in a single object.
2. It eliminates the necessity for a set of long, look-alike conditional statements scattered through the program’s code.
3. It makes transition explicit. Rather than having a constant that specifies which state the program is in, and that may not always be checked correctly, this makes the change explicit by copying one of the states to the state variable.
4. State objects can be shared if they have no instance variables. Here only the Fill object has instance variables, and that color could easily be made an argument instead.
5. This approach generates a number of small class objects, but in the process, simplifies and clarifies the program.
6. In Java, all of the States must inherit from a common base class, and they must all have common methods, although some of those methods can be empty. In other languages, the states can be implemented by function pointers with much less type checking, and, of course, greater chance of error.

Strategy pattern
The Strategy pattern is much like the State pattern in outline, but a little different in intent. The Strategy pattern consists of a number of related algorithms encapsulated in a driver class called the Context. Your client program can select one of these differing algorithms or in some cases the Context might select the best one for you. The intent, like the State pattern, is to switch easily between algorithms without any monolithic conditional statements. The difference between State and Strategy is that the user generally chooses which of several strategies to apply and that only one strategy at a time is likely to be instantiated and active within the Context class. By contrast, as we have seen, it is likely that all of the different States will be active at once and switching may occur frequently between them. In addition, Strategy encapsulates several algorithms that do more or less the same thing, while State encapsulates related classes that each do something somewhat different. Finally, the concept of transition between different states is completely missing in the Strategy pattern.

A program which requires a particular service or function and which has several ways of carrying out that function is a candidate for the Strategy pattern. Programs choose between these algorithms based on computational efficiency or user choice. There can be any number of strategies and more can be added and any of them can be changed at any time.

There are a number of cases in programs where we’d like to do the same thing in several different ways. Some of these are listed in the Smalltalk Companion:
· Save files in different formats.
· Compress files using different algorithms
· Capture video data using different compression schemes
· Use different line-breaking strategies to display text data.
· Plot the same data in different formats: line graph, bar chart or pie chart.

In each case we could imagine the client program telling a driver module (Context) which of these strategies to use and then asking it to carry out the operation.
The idea behind Strategy is to encapsulate the various strategies in a single module and provide a simple interface to allow choice between these strategies. Each of them should have the same programming interface, although they need not all be members of the same class hierarchy. However, they do have to implement the same programming interface.

Consequences of the Strategy Pattern
Strategy allows you to select one of several algorithms dynamically. These algorithms can be related in an inheritance hierarchy or they can be unrelated as long as they implement a common interface. Since the Context switches between strategies at your request, you have more flexibility than if you simply called the desired derived class. This approach also avoids the sort of condition statements than can make code hard to read ad maintain. On the other hand, strategies don’t hide everything. The client code must be aware that there are a number of alternative strategies and have some criteria for choosing among them. This shifts an algorithmic decision to the client programmer or the user.
Since there are a number of different parameters that you might pass to different algorithms, you have to develop a Context interface and strategy methods that are broad enough to allow for passing in parameters that are not used by that particular algorithm.

Template pattern
Whenever you write a parent class where you leave one or more of the methods to be implemented by derived classes, you are in essence using the Template pattern. The Template pattern formalizes the idea of defining an algorithm in a class, but leaving some of the details to be implemented in subclasses. In other words, if your base class is an abstract class, as often happens in these design patterns, you are using a simple form of the Template pattern.

Templates are so fundamental, you have probably used them dozens of times without even thinking about it. The idea behind the Template pattern is that some parts of an algorithm are well defined and can be implemented in the base class, while other parts may have several implementations and are best left to derived classes. Another main theme is recognizing that there are some basic parts of a class that can be factored out and put in a base class so that they do not need to be repeated in several subclasses.

Kinds of Methods in a Template Class
A Template has four kinds of methods that you can make use of in derive classes:
1. Complete methods that carry out some basic function that all the subclasses will want to use, such as calcx and calcy in the above example. These are called Concrete methods.
2. Methods that are not filled in at all and must be implemented in derived classes. In Java , you would declare these as abstract methods, and that is how they are referred to in the pattern description.
3. Methods that contain a default implementation of some operations, but which may be overridden in derived classes. These are called Hook methods. Of course this is somewhat
arbitrary, because in Java you can override any public or protected method in the derived class, but Hook methods are intended to be overridden, while Concrete methods are not.
4. Finally, a Template class may contain methods which themselves call any combination of abstract, hook and concrete methods. These methods are not intended to be overridden, but describe an algorithm without actually implementing its details. Design Patterns refers to these as Template methods.

Summary and Consequences
Template patterns occur all the time in OO software and are neither complex nor obscure in intent. They are normal part of OO programming and you shouldn’t try to make them more abstract than they actually are.
The first significant point is that your base class may only define some of the methods it will be using, leaving the rest to be implemented in the derived classes. The second major point is that there may be methods in the base class which call a sequence of methods, some implemented in the base class and some implemented in the derived class. This Template method defines a general algorithm, although the details may not be worked out completely in the base class.
Template classes will frequently have some abstract methods that you must override in the derived classes, and may also have some classes with a simple “place-holder” implementation that you are free to override where this is appropriate. If these place-holder classes are called from another method in the base class, then we refer to these overridable methods are “Hook” methods.

Visitor pattern
The Visitor pattern turns the tables on our object-oriented model and creates an external class to act on data in other classes. This is useful if there are a fair number of instances of a small number of classes and you want to perform some operation that involves all or most of them.

While at first it may seem “unclean” to put operations that should be inside a class in another class instead, there are good reasons for doing it. Suppose each of a number of drawing object classes has similar code for drawing itself. The drawing methods may be different, but they probably all use underlying utility functions that we might have to duplicate in each class. Further, a set of closely related functions is scattered throughout a number of different classes

When to Use the Visitor Pattern
You should consider using a Visitor pattern when you want to perform an operation on the data contained in a number of objects that have different interfaces. Visitors are also valuable if you have to perform a number of unrelated operations on these classes. On the other hand, as we will see below, Visitors are a good choice only when you do not expect many new classes to be added to your program.

Sample Code
We have a simple Employee object which maintains a record of the employee’s name, salary, vacation taken and number of sick days taken. A simple version of this class is:

public class Employee
int sickDays, vacDays;
float Salary;
String Name;
public Employee(String name, float salary,
int vacdays, int sickdays)
vacDays = vacdays; sickDays = sickdays;
Salary = salary; Name = name;
public String getName() { return Name; }
public int getSickdays() { return sickDays; }
public int getVacDays() { return vacDays; }
public float getSalary() { return Salary; }
public void accept(Visitor v) { v.visit(this); }

Note that we have included the accept method in this class. Now let’s suppose that we want to prepare a report of the number of vacation days that all employees have taken so far this year. We could just write some code in the client to sum the results of calls to each Employee’s getVacDays function, or we could put this function into a Visitor.
Since Java is a strongly typed language, your base Visitor class needs to have a suitable abstract visit method for each kind of class in your program. In this first simple example, we only have Employees, so our basic abstract Visitor class is just

public abstract class Visitor
public abstract void visit(Employee emp);

Notice that there is no indication what the Visitor does with each class in either the client classes or the abstract Visitor class. We can in fact write a whole lot of visitors that do different things to the classes in our program. The Visitor we are going to write first just sums the vacation data
for all our employees:

public class VacationVisitor extends Visitor
protected int total_days;
public VacationVisitor() { total_days = 0; }
public void visit(Employee emp)
total_days += emp.getVacDays();
public int getTotalDays()
return total_days;

Visiting the Classes
Now, all we have to do to compute the total vacation taken is to go through a list of the employees and visit each of them, and then ask the Visitor for the total.

VacationVisitor vac = new VacationVisitor();
for (int i = 0; i < employees.length; i++)

Let’s reiterate what happens for each visit:

1. We move through a loop of all the Employees.
2. The Visitor calls each Employee’s accept method.
3. That instance of Employee calls the Visitor’s visit method.
4. The Visitor fetches the vacation days and adds them into the total.
5. The main program prints out the total when the loop is complete.

Double Dispatching
No article on the Visitor pattern is complete without mentioning that you are really dispatching a method twice for the Visitor to work. The Visitor calls the polymorphic accept method of a given object, and the accept method calls the polymorphic visit method of the Visitor. It this bidirectional calling that allows you to add more operations on any class that has an accept method, since each new Visitor class we write can carry out whatever operations we might think of using the data available in these classes.

Traversing a Series of Classes
The calling program that passes the class instances to the Visitor must know about all the existing instances of classes to be visited and must keep them in a simple structure such as an array or Vector. Another possibility would be to create an Enumeration of these classes and pass it to the Visitor. Finally, the Visitor itself could keep the list of objects that it is to visit. In our simple example program, we used an array of objects, but any of the other methods would work equally well.

Consequence of the Visitor Pattern
The Visitor pattern is useful when you want to encapsulate fetching data from a number of instances of several classes. Design Patterns suggests that the Visitor can provide additional functionality to a class without changing it. We prefer to say that a Visitor can add functionality to a collection of classes and encapsulate the methods it uses. The Visitor is not magic, however, and cannot obtain private data from classes: it is limited to the data available from public methods. This might force you to provide public methods that you would otherwise not have provided. However, it can obtain data from a disparate collection of unrelated classes and utilize it to present the results of a global calculation to the user program.

It is easy to add new operations to a program using Visitors, since the Visitor contains the code instead of each of the individual classes. Further, Visitors can gather related operations into a single class rather than forcing you to change or derive classes to add these operations. This can make the program simpler to write and maintain.

Visitors are less helpful during a program’s growth stage, since each time you add new classes which must be visited, you have to add an abstract visit operation to the abstract Visitor class, and you must add an implementation for that class to each concrete Visitor you have written. Visitors can be powerful additions when the program reaches the point where many new classes are unlikely. Visitors can be used very effectively in Composite systems


Post a Comment

<< Home