Pattern Hatching:
Perspectives from the "Gang of Four"

John Vlissides

JIM COPLIEN has laid the groundwork for all sorts of discussions on software patterns in "The Column Without a Name." In this column I'll offer another perspective on this emerging discipline, one that reflects my experience as a member of the "Gang of Four." I'm referring not to some group of malefactors, I think, but to Erich Gamma, Richard Helm, Ralph Johnson, and myself. Together we authored Design Patterns: Elements of Reusable Object-Oriented Software, a book of 23 patterns distilled from numerous object-oriented software systems.

In Design Patterns we've tried to describe recurring snippets of object-oriented design that impart those elusive properties of good software: elegance, flexibility, extensibility, and reusability. We've recorded these snippets in a form that, although different from Alexander's, is nevertheless faithful to pattern ideals. More on our pattern form later.

The patterns in the book come from many application domains, including user interfaces, compilers, programming environments, operating systems, distributed systems, financial modeling, and computer-aided design. That's not to say design patterns are domain-specific, however. We were careful to include only proven designs we'd seen again and again across domains.

We call our patterns "design patterns." for at least a couple of reasons. Our work has its roots in Erich Gamma's doctoral dissertation, where he coined the term. He wanted to emphasize that he was capturing design expertise as opposed to other software development skills, such as domain analysis or implementation. Another reason is that "pattern" alone means different things to different people, even among pattern aficionados. Prepending "design" provides some needed qualification. But since I'll be talking mostly about design patterns in this column, I'll dispense with the "design" prefix whenever I can get away with it.

As for the title of this column, I chose "Pattern Hatching" initially for its similarity to a familiar concept in computer science. (Besides, all the good titles were taken.) But I've come around to thinking that it captures my intent for this column rather well. "Hatching" doesn't suggest that we are creating anything. It implies development from preexisting rudiments. That happens to be appropriate: Design Patterns is our incubator of eggs, as it were, from which much new life will hopefully emerge. (I trust we won't have opportunity to take this analogy too much further.)

The "Pattern Hatching" column will not merely echo the book. My aim is to build on what's in the book, to leverage its concepts so that we can learn from them and improve on them.

DESIGN PATTERNS VERSUS ALEXANDER'S PATTERNS

Design patterns are more highly structured by comparison. They have to be. They contain more material than Alexander's patterns: the average design pattern is 10 pages, compared to four (smaller) pages for its Alexandrian counterpart. Design patterns also describe in detail how you might implement the pattern, including sample code and a discussion of implementation trade-offs. Alexander seldom deals with construction details on a comparable level. We could have presented this material using a more Alexander-like structure, but we wanted to allow quick reference in the heat of design or implementation. Since we don't prescribe an order in which to apply the patterns (as would a true pattern language in the Alexandrian tradition), there's less to guide you to the right pattern. Even if you know which pattern you want, its size could make it hard to find the detail that interests you. We had to make it fast and easy for designers to find the patterns that are appropriate to their problems. That led us toward a finer-grained pattern structure.

DESIGN PATTERN STRUCTURE

1. Name
2. Intent
3. Also Known As
4. Motivation
5. Applicability
6. Structure
7. Participants
8. Collaborations
9. Consequences
10. Implementation
11. Sample Code
12. Known Uses
13. Related Patterns

The first three sections identify the pattern. Section 4 approximates the content of an Alexandrian pattern: It gives a concrete example that illustrates the problem, its context, and its solution. Sections 5-9 define the pattern abstractly. Most people seem to understand things better when they're explained in concrete terms first, followed by more abstract terms. That's why a design pattern considers the problem and its solution concretely before describing them in the abstract. Section 10 gets concrete again, and section 11 is the most concrete of all. Section 12 is bibliographic, and section 13 provides cross-references.

BUILDING WITH COMPOSITES

Suppose you are implementing a command that lists the files in a directory. The code you write to get the name of a directory shouldn't have to be different from the code you write to get the name of a file-the same code should work for both. In other words, you should be able to treat directories and files uniformly with respect to their names. The resulting code will be easier to write and maintain. You also want to accommodate new kinds of files (like symbolic links, for example) without reimplementing half the system.

It's clear that files and directories are key elements in our problem domain and that we need a way of introducing specialized versions of these elements after we've finalized the design. An obvious design approach would be to represent these elements as objects, as shown in Figure 1.

Figure 1

How do you implement such a structure? The fact that we have two kinds of objects suggests two classes, one for files and one for directories. We want to treat files and directories uniformly, which means they must have a common interface. In turn, that means the classes must be derived from a common (abstract) base class, which we'll call "Node." We also know that directories aggregate files. Together, these constraints essentially define the class hierarchy for us:

class Node {
public:
	// declare common interface here
protected:
	Node();
};

class File : public Node {
public:
	File();

	// redeclare common interface here
};

class Directory : public Node {
public:
	Directory();

	// redeclare common interface here
private:
	List _nodes;
};

For example, one of the most common things users do is ask for a list of the files in a directory. That means that Directory needs an interface for enumerating its children. Here's a simple one that returns the nth child:

virtual Node* GetChild(int n);

GetChild must return a Node*, because the directory may contain either File objects or Directory objects. The type of that return value has an important ramification: It forces us to define GetChild not just in the Directory class but in the Node class as well. Why? Because we want to be able to list the children of a subdirectory. In fact, the user will often want to descend the file system structure. We won't be able to do that unless we can call GetChild on the object GetChild returns. So, like the attribute operations, GetChild is something we want to be able to apply uniformly.

GetChild is also key to letting us define Directory operations recursively. For example, suppose Node declares a Size operation that returns the total number of bytes consumed by the directory (sub)tree. Directory could define its version of this operation as a sum of the values that its children return when their Size operation is called:

long Directory::Size () {
	long total = 0;
	Node* child;

	for (int i = 0; child = GetChild(i); ++i) {
		total += child->Size();
	}

	return total;
}

• you want to represent part-whole hierarchies of objects.
• you want clients to be able to ignore the difference between compositions of objects and individual objects. Clients will treat all objects in the composite structure uniformly.

The pattern's Structure section presents a modified OMT diagram of the canonical Composite class structure (see Fig. 2). By "canonical" I mean simply that it represents the most common arrangement of classes that we (the Gang of Four) have observed. It can't represent the definitive set of classes and relationships, because the interfaces may vary when we consider certain design or implementation-driven trade-offs. (The pattern will spell those out, too.)

Figure 2

Figure 2 shows the classes that participate in the pattern and their static relationships. Component is the abstract base class to which our Node class corresponds. Subclass participants are Leaf (which corresponds to File) and Composite (corresponding to Directory). The arrowhead line going from Composite to Component indicates that Composite contains instances of type Component. The ball at the tip of the arrowhead indicates more than one instance; if the ball were omitted, it would mean exactly one instance. The diamond at the base of the arrowhead line means that the Composite aggregates its child instances, which implies that deleting the Composite would delete its children as well. It also implies that components aren't shared, thus assuring tree structures. The Participant and Collaboration sections of the pattern explain the static and dynamic relationships, respectively, among these participants.

Composite's Consequences section sums up the benefits and liabilities of the pattern. On the plus side, the pattern supports tree structures of arbitrary complexity. A corollary of this property is that a node's complexity is hidden from clients: they can't tell whether they're dealing with a leaf or a composite component, because they don't have to. That makes client code more independent of the code in the components. The client is also simpler, because it can treat leaves and composites uniformly. No longer do clients have to decide which of multiple code paths to take based on the type of component. Best of all, you can add new types of components without touching existing code.

Composite's down side, however, is that it can lead to a system where the class of every object looks like the class of every other. The significant differences show up only at run-time. That can make the code hard to understand, even if you are privy to class implementations. Moreover, the number of objects may become prohibitive if the pattern is applied at a low level or at too fine a granularity.

As you might have guessed, implementation issues abound for the Composite pattern. Some of the issues we address include:

• when and where to cache information to improve performance,
• what if any storage the Component class should allocate,
• what data structure(s) to use for storing children, and
• whether or not operations for adding and removing children should be declared in the Component class.

Since I'm rapidly running out of space, I'll take a closer look at these and other implementation questions in future columns.

WINDING DOWN

Picture an electronics hobbyist who, though bereft of formal training, has nevertheless designed and built a slew of useful gadgets over the years: a ham radio, a Geiger counter, a security alarm, and many others. One day the hobbyist decides it's time to get some official recognition for this talent by going back to school and earning a degree in electronics. As the coursework unfolds, the hobbyist is struck by how familiar the material seems. It's not the terminology or the presentation that's familiar but the underlying concepts. The hobbyist keeps seeing names and rationalizations for stuff he's used implicitly for years. It's just one epiphany after another.

Cut now to the first year undergraduate taking the same classes and studying the same material. The undergrad has no electronics background---lots of rollerblading, yes, but no electronics. The stuff in the course is intensely painful for him, not because he's dumb, but because it's so totally new. It takes quite a bit more time for the undergrad to understand and appreciate the material. But eventually he does, with hard work and a bit of perseverance.

If you feel like a design pattern hobbyist, then more power to you. If on the other hand you feel more like the undergrad, take heart: the investment you make in learning good patterns will pay for itself each time you apply them in your designs. That's a promise.

But maybe electronics, with its "techie" connotations, isn't the best analogy for everyone. If you agree, then consider something Alfred North Whitehead said in 1943, admittedly in a different context, which might nonetheless make a more appealing connection:

Art is the imposing of a pattern on experience, and our aesthetic enjoyment in recognition of the pattern.

References

John Vlissides is a member of the research staff at IBM's Thomas J. Watson Research Center in Hawthorne, NY. He can be reached at vlis@watson.ibm.com.