This article is a segment from a chapter of Advanced Principles, Patterns, and Process of Object Oriented Software Development, by Robert C. Martin, Prentice Hall, 2001. Copyright © 2001 Robert C. Martin, All rights reserved.
Way, way back in the early 90s — back in the early days of OO — we were all quite taken with the notion of inheritance. The implications of the relationship were profound. With inheritance we could program by difference! That is, given some class that did something almost useful for us, we could create a subclass and change only the bits we didn't like. We could reuse code simply by inheriting it! We could establish whole taxonomies of software structures; each level of which reused code from the levels above. It was a brave new world.
Like most brave new worlds, this one turned out to be a bit too starry-eyed. By 1995 it was clear that inheritance was very easy to over use, and that over-use of inheritance was very costly. So we cut back on our use of inheritance, often replacing it with delegation.
This column is the story of two patterns that epitomize the difference between inheritance and delegation. The Template Method and Strategy patterns solve similar problems and can often be used interchangeably. However, Template Method uses inheritance to solve the problem, whereas Strategy uses delegation.
Intent of Template Method and Strategy
Template Method and Strategy both solve the problem of separating a generic algorithm from a detailed context. We see the need for this very frequently in software design. We have an algorithm that is generically applicable. In order to conform to the DIP (Dependency Inversion Principle) [1], we want to make sure that the generic algorithm does not depend upon the detailed implementation. Rather we want the generic algorithm and the detailed implementation to depend upon abstractions. Consider the following two examples.
Application
Consider all the programs you have written. Many probably have this fundamental main-loop structure.
Initialize(); while (!done()) // main loop { Idle(); // do something useful. } Cleanup();First we initialize the application. Then we enter the main loop. In the main loop, we do whatever the program needs to do. We might process GUI events or perhaps process database records. Finally, once we are done, we exit the main loop and clean up before we exit.
This structure is so common that we can capture it in a class named Application. Then we can reuse that class for every new program we want to write. Think of it! We never have to write that loop again!
For example, consider Listing 1. Here we see all the elements of the standard program. The InputStreamReader and BufferedReader are initialized. There is a main loop that reads Fahrenheit readings from the BufferedReader and prints out Celsius conversions. At the end, an exit message is printed.
This program has all the elements of the main-loop structure above. It does a little initialization, does its work in a main-loop, and then cleans up and exits.
We can separate this fundamental structure from the ftoc program by employing the Template Method pattern. This pattern places all the generic code into an implemented method of an abstract base class. The implemented method captures the generic algorithm, but defers all details to the abstract methods of the base class.
So, for example, we can capture the main-loop structure in an abstract base class called Application (see Listing 2).
This class describes a generic main-loop application. We can see the main loop in the implemented run function. We can also see that all the work is being deferred to the abstract methods init, idle, and cleanup. The init method takes care of any initialization we need done. The idle method does the main work of the program and will be called repeatedly until setDone is called. The cleanup method does whatever needs to be done before we exit.
We can rewrite the ftoc class by inheriting from Application and just filling in the abstract methods. Listing 3 show what this looks like.
Dealing with the exception made the code get a little longer, but it's easy to see how the old ftoc application has been fit into the Template Method pattern.
Template Method is used when you have a generic algorithm that applies across a variety of detailed contexts. In the example above, the generic algorithm is the main-loop of nearly every application. It was applied to the detailed context of ftoc. The generic algorithm is written into an abstract base class and is made to call abstract methods. A derivative class provides the detailed context by implementing the abstract methods of the base.
Bubble Sort
As another example, lets look at what it takes to write a bubble sort (see Listing 4).
The BubbleSorter class knows how to sort an array of integers using the bubble sort algorithm. The sort method of BubbleSorter contains the algorithm that knows how to do a bubble sort. The two ancillary methods, swap and compareAndSwap, deal with the details of integers and arrays and handle the mechanics that the sort algorithm requires.
Using the Template Method pattern, we can separate the bubble sort algorithm into an abstract base class named BubbleSorter. BubbleSorter contains an implementation of the sort function that calls an abstract method named outOfOrder and another called swap. The outOfOrder method compares two adjacent elements in the array and returns true if the elements are out of order. The swap method swaps two adjacent cells in the array.
The sort method does not know about the array, nor does it care what kinds of objects are stored in the array. It just calls outOfOrder for various indices into the array and determines whether those indices should be swapped or not (see Listing 5).
Given BubbleSorter, we can now create simple derivatives that can sort any different kind of object. For example, we could create IntBubbleSorter, which sorts arrays of integers, and DoubleBubbleSorter, which sorts arrays of doubles (see Figure 1, Listing 6, and Listing 7).
The Template Method pattern shows one of the classic forms of reuse in object-oriented programming. Generic algorithms are placed in the base class and inherited into different detailed contexts. But this technique is not without its costs. Inheritance is a very strong relationship. Derivatives are inextricably bound to their base classes.
For example, the outOfOrder and swap functions of IntBubbleSorter are exactly what are needed for other kinds of sort algorithms. And yet, there is no way to reuse outOfOrder and swap in those other sort algorithms. By inheriting BubbleSorter we have doomed IntBubbleSorter to forever be bound to BubbleSorter. The Strategy method provides another option.
Strategy
The Strategy pattern solves the problem of inverting the dependencies of the generic algorithm and the detailed implementation in a very different way. Consider, once again, the Application problem.
Rather than placing the generic application algorithm into an abstract base class, we place it into a concrete class named ApplicationRunner. We define the abstract methods that the generic algorithm must call within an interface named Application. We derive ftocStrategy from this interface and pass it into the ApplicationRunner. ApplicationRunner then delegates to this interface (see Figure 2, Listing 8, Listing 9, and Listing 10).
It should be clear that this structure has both benefits and costs over the Template Method structure. Strategy involves more total classes and more indirection than the Template Method. The delegation pointer within ApplicationRunner incurs a slightly higher cost in terms of run time and data space than inheritance would. On the other hand, if we had many different applications to run, we could reuse the ApplicationRunner instance and pass in many different implementations of Application, thereby reducing the code space overhead.
None of these costs and benefits is overriding. In most cases, none of them matters in the slightest. In the typical case, the most worrisome is the extra class needed by the Strategy pattern. However, there is more to consider.
Sorting Again
Consider an implementation of the bubble sort that uses the Strategy pattern (see Listing 11, Listing 12, and Listing 13).
Notice, the IntSortHandle class knows nothing whatsoever of the BubbleSorter. It has no dependency upon the bubble sort implementation. This is not the case with the Template Method pattern. Look back at Listing 6 and you can see that the IntBubbleSorter depended directly on BubbleSorter, the class that contains the bubble sort algorithm.
The Template Method approach partially violates DIP. The implementation of the swap and outOfOrder methods depends directly upon the bubble sort algorithm. The Strategy approach contains no such dependency. Thus, we can use the IntSortHandle with a Sorter implementation other than BubbleSorter.
For example, we can create a variation of the bubble sort that terminates early if a pass through the array finds it in order (see Listing 14). QuickBubbleSorter can also use IntSortHandle or any other class derived from SortHandle.
Thus, the Strategy pattern provides one extra benefit over the Template Method pattern. Whereas the Template Method pattern allows a generic algorithm to manipulate many possible detailed implementations, by fully conforming to the DIP, the Strategy pattern additionally allows each detailed implementation to be manipulated by many different generic algorithms.
A Case for Template Method
From 1993 to 1998, we (Object Mentor) developed a system for the ETS (Educational Testing Service). The system automated the architectural registration exam used by the NCARB (National Council of Architects Registry Board). Folks who want to become architects in the United States and Canada have to pass this test. The system we developed delivered and scored the test.
Delivery was via GUI. Candidates were given architectural problems to solve. They drew their solutions using the CAD-like interface offered by our system. Their solutions were typical architectural drawings like floor plans, elevation plans, roof plans, landscaping plans, etc. Their solutions were then transmitted to a central location where the scoring programs could be run. The scoring programs assessed the solutions for sound architectural principles and assigned a grade.
The test was broken up into 18 different vignettes. Each vignette presented a problem to be solved and tested for particular architectural skills. One vignette tested for the candidate's ability to put a roof on a building. Another tested the ability to subdivide a large tract of land. Still another tested the candidate's ability to design sound structures.
One of the vignettes tested the candidate's abilities to layout the floor plan of a building such as a library or a police station. In this vignette, the candidate had to draw rooms, corridors, doors, windows, wall-openings, stairs, elevators, etc. The program converted the drawing into a data structure that the scoring program could interpret. The object model looked something like Figure 3.
Make no mistake about this: the objects in this data structure had very minimal functionality. They were not polymorphic objects in any sense of the word. Rather they were simple data carriers, a purely representational model.
A building was composed of two floors. Each floor had many spaces. Each space contained many portals, each of which separated two spaces. Portals could be windows or could allow a human to pass through. Human portals were either wall openings or doors.
Scoring was done by testing the solution for a set of features. The features were things like:
- Did the candidate draw all the required spaces?
- Does each space fall within the range of acceptable square footage?
- Does each space have an acceptable aspect ratio?
- Does each space have a way in?
- Do external spaces have windows?
- Are the men's and ladies' washrooms connected by a door (a bad thing)?
- Does the president's office have a view of the mountains?
- Does the kitchen have easy access to back alley?
- Does the lunchroom have easy access to the kitchen?
- Can a person navigate the corridor system and get to each room?
- Is there any point in the building where you are more than 20 feet from two completely separate ways out of the building?
These features were grouped into a hierarchy. Similar features were grouped together and made children of the same node. Groups with similar characteristics were placed under higher nodes, etc. Each node was given a weight depending upon its significance to the overall score.
A data structure was created that represented this hierarchy. As the scores for the features were calculated, they rippled up the hierarchy, being multiplied by their weights. All the calculations culminated at the top of the hierarchy with a single score.
The psychometricians at ETS wanted to be able to change the shape of the scoring matrix on a whim. They wanted to be able to change the weightings, regroup the features into different sub-hierarchies, etc. They wanted to be able to take out features that they considered worthless or add new features.
For performance reasons, we only wanted to calculate the features that were included in the matrix, so we created classes for each feature. Each of these Feature classes had an Evaluate method that would walk the data structure in Figure 3 and calculate a score. This meant that we had dozens and dozens of Feature classes that all walked the same data structure. The code duplication was horrendous.
Write a Loop Once
To deal with the code duplication, we started using the Template Method pattern. This was 1993, long before we knew anything about patterns. We called what we were doing "Write a Loop Once." See Listing 15 and Listing 16; these are the actual C++ modules from that program.
As you can see from the comment header, this code was written in 1994. So it will look a bit strange to those of you who are used to STL. Still, if you ignore the cruft and the bizarre iterators, you'll see the classic Template Method pattern in there. The DoEval function loops through all the SolutionSpace objects. It then calls the pure virtual NewSolutionSpace function. Derivatives of SolutionSpaceFeature implement NewSolutionSpace and measure each space against a particular scoring criterion.
The derivatives of SolutionSpaceFeature that we implemented included features that measured whether the appropriate spaces were placed into the solution, whether the spaces had the appropriate area and aspect ratio, whether elevators stacked properly, etc.
The neat thing about this is that the loop that traverses the data structure is located in one place. All the scoring features inherit it rather than reimplement it.
Some of the features had to measure characteristics of the portals attached to a space, so we reproduced the pattern and created the class PortalFeature derived from SolutionSpaceFeature. The implementation of NewSolutionSpace within PortalFeature looped through all the portals in the SolutionSpace argument and called the pure virtual function NewPortal(const Portal&) (see Figure 4).
This structure allowed us to create dozens of different scoring features, each one of which walked the floor-plan data structure, without knowing what the floor-plan data structure looked like. If the details of the floor-plan data structure changed (e.g., we decided to use STL instead of our own iterators), we'd have to change two classes rather than several dozen.
Why did we choose Template Method over Strategy [2]? Consider how much looser the coupling would have been had we used Strategy (see Figure 5)!
Using the Template Method structure, if we had to make a change to the algorithms that walked the data structure, we would have had to change SpaceFeature and PortalFeature. In all likelihood, this would have forced us to recompile all the features. However, using the Strategy pattern, the change would have been to the two Driver classes. There is virtually no chance that the features would need to be recompiled.
So, why did we choose the Template Method? Because it was simpler, because the data structure was not something that was going to change frequently, and because recompiling all the features cost just a few minutes.
So, even though the use of inheritance in the Template Method pattern resulted in a more tightly coupled design, and even though the Strategy pattern conforms to the DIP better than the Template Method pattern does, in the end it wasn't worth the two extra classes to implement the Strategy.
The Template Method That Wasn't
Recently my son Micah was working on an application that used SOAP [3]. His application was full of stretches of code that looked roughly like Listing 17. These stretches were all virtually identical except for the number and types of parameters that were loaded into the d_params vector. Since we don't like lots of duplicate code, he asked me what he ought to do about it.
Being an object designer of immense experience, and deriving great joy from showing off my deep knowledge of design patterns to my son, I leapt to a whiteboard and sketched the diagram in Figure 6. Clearly I had Template Method in mind.
The idea was simple. Since the only difference between all the stretches of code was in the loading of the d_params vector, why not just make that vector a variable of the SoapInvoker and then let derived classes of SoapInvoker implement the setParams method to load the vector with the appropriate parameters.
So we wrote the SoapInvoker class as shown in Listing 18. Notice that the invoke method calls setParams. This is the classic Template Method.
With this in place, we could now replace the duplicate code stretches with much smaller stretches that looked like Listing 19. This vastly reduces the amount of duplicated code.
Things went swimmingly at first. We hunted through the code finding the target stretches and refactoring them using SoapInvoker. But after the first few, we ran across a function that looked like Listing 20. This function took an argument that it then passed to the SOAP invocation.
This just doesn't fit very nicely into the SoapInvoker. Listing 21 shows why. We have to add private variables and special setters to the anonymous inner class.
After writing this, my son looked over at me and said: "Dad, that's awful." I had to agree; it was pretty awful. Then he said, why don't we get rid of the Template Method and just put an addParam method in SoapInvoker. So that's what we did (see Listing 22).
This worked much better. Now all the code stretches simply created a SoapInvoker, loaded it with parameters, and then called invoke.
This is typical. When faced with a problem, we find a possible way to deal with it. As we apply the solution, we find it is not ideal because of factors we haven't anticipated, so we adjust the solution in response.
Design patterns are good to know. If you know them well, then they can give you good ideas about how to solve problems. But you have to remember that the pattern you choose may not actually be the best solution. You have to be prepared to change direction when you see that your ideas aren't working well.
Notes
[1] See the Dependency Inversion Principle in the "publications" section of <www.objectmentor.com>.
[2] Clearly we didn't think of it in those terms. The names of the patterns hadn't been invented at the time we made this decision.
[3] Yet another middleware product for Java.
Bibliography
Gamma, et. al. Design Patterns (Addison Wesley, 1995).
Robert C. Martin, et. al. Pattern Languages of Program Design 3 (Addison Wesley, 1998).
Robert C. Martin has been a software professional since 1970. He is president of Object Mentor Inc., a firm of highly experienced experts that offers high level object-oriented software design consulting, training, and development services to major corporations around the world. In 1995, he authored the best-selling book: Designing Object Oriented C++ Applications using the Booch Method, published by Prentice Hall. In 1997, he was chief editor of the book: Pattern Languages of Program Design 3, published by Addison Wesley. In 2000, he was editor of the book More C++ Gems, published by Cambridge Press. From 1996 to 1998, he was the editor-in-chief of the C++ Report. He has published dozens of articles in various trade journals and is a regular speaker at international conferences and trade shows. He is currently working in the area of lightweight productive processes and is a strong advocate and supporter of Extreme Programming.