Introduction to Software Patterns

Producing a large software system is the most challenging technical activity that the human race attempts to carry out.
Darrel Ince

Programming is unique

The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination. Few media of creation are so flexible, so easy to polish and rework, so readily capable of realizing grand conceptual structures.
Fred Brooks
The Mythical Man-Month

Building software is vastly different from building computers, building bridges, and building skyscrapers. Software is at its core a conceptual entity, made up of algorithms and relationships between data items. It is very difficult to visualize with a schematic, a scale model, or a floor plan. It doesn't have verbatim repeated elements; these are compressed into loops and subroutines. Software has a very large number of states, most of which can never be tested. Software "maintenance" is not the same as computer, bridge, or skyscraper maintenance. Software parts do not wear out or need oiling. Instead, their functionality is changed to suit new cases. Software, even after it is fielded, is changed far more frequently than computers, bridges, and skyscrapers, mostly because it is much cheaper to change.

These differences create opportunities which are not possible in other forms of engineering, as well as create new challenges. Computer, bridge, and skyscraper engineering, because they use relatively few basic architectures, have detailed handbooks on design: when and why to use an architecture, how to use it, and consequences of using it. Algorithm and data structure catalogs, while useful, have not addressed system design at the same level. Software patterns are a first step toward a design handbook for software engineering: the enumeration and elaboration of the basic parts of the conceptual side of software.

Opportunities in modern programming

Evolutionary prototyping

Grow, don't build, software.
Fred Brooks
No Silver Bullet

For decades, software engineers have practiced the "waterfall" model of development. It proceeds in a straight line through five stages:

  1. Requirements analysis. Determining what the program needs to do and what it doesn't.
  2. Design. Defining modules, their functional purposes, and their relationships. Usually done at several levels of detail.
  3. Implementation. Translating the design into efficient formal instructions.
  4. Testing. Verifying that the implementation meets the requirements.
  5. Delivery and maintenance. Fixing mistakes; changing the design and implementation to suit extra requirements.
This style was probably taken from computer, building, and skyscraper engineers, because it assumes that each stage is relatively straightforward and that changes are infrequent. Unfortunately, that is not true of software. Requirements constantly change, because of hardware advances, new compatibility requirements, and misunderstanding the customer. Design and implementation are prone to error, partly because software is so complex and invisible. Maintenance is based on change rather than simple part replacement.

An alternative form of software development is instead based on the ability and necessity of software to change, and does not distinguish between change after delivery (maintenance) with change before delivery (construction). The idea is to iterate steps 1-4, each time producing a working system that has a few additional features. Darrel Ince calls it evolutionary prototyping, where a prototype is constantly refined, to distinguish it from throw-away prototyping, where a prototype is built in a quick-and-dirty manner and then rewritten. The motivation behind the latter is to minimize your investment; the motivation behind the former is to maximize the value of your investment. In evolutionary prototyping, features accumulate rather than needing to be rewritten each time. Tested code does not need to be constantly re-verified. Pieces of the problem are removed from consideration instead of being re-considered on every rewrite.

The key to evolutionary prototyping is to incorporate flexibility as an explicit design requirement. The program must stay flexible even after numerous enhancements, or it will turn into rubble. This isn't easy, mostly because we lack the ability to document exactly where and to what degree the program must remain flexible. This is the challenge of variabilities and decoupling, described below. Design patterns are well suited to providing such documentation.

Formal specification and architecture languages

Programming languages have grown from machine code to high levels of mathematical abstraction, and there is no inherent limit to their future growth. Formal languages are starting to be used for analysis and design, but it is tough going. The advantage of formal languages, over English and simple diagrams, is that they are less ambiguous and therefore a better medium for communication in the team. Ideally, the same language would be used throughout the project, even after implementation, to avoid the perils of language conversion.

A difficulty is that software design has not yet been simplified enough so that we can express a design as the combination of a few basic parts. This is necessary for a linguistic approach to work. Unicon is a first attempt at an architecture language which is based on a handful of basic architectures. Such languages potentially allow instantiation of ready-made architectures, verification that an architecture is being used properly, substituting one architecture for another, and composition of architectures. This is a more ambitious approach than the current use of patterns: as mental and documentation aids.

Component software

Component software offers a unique possibility over computers, bridges, and skyscrapers. Software can be assembled at run-time from independently engineered and possibly distributed parts, thanks to software's ability to instantaneously replicate and transmit itself. Ideally, this would be under the control of the user, who might combine his favorite text editor, spreadsheet, drawing program, and graphing program together to make an integrated desktop publishing system. This creates a high level of competition and a smaller development cost for component developers. (Also see the notes from Programming Language Exploration.)

The obstacle to component software is not just standardization but also the complexity of its implementation. Object-oriented component software requires a distributed shared memory based on objects which can exist in and migrate between many different formats (distributed object management). It requires component containers which manage a coherent visual and persistent representation (compound documents). It also requires the ability to transfer data and objects between independently engineered components (uniform data transfer).

Compilers were once very complex and mysterious, consequently language development was slow, because it was quite a feat to implement a high-level language (e.g. Algol 68). But the patterns in compiler implementations were studied, and found to be similar to other programming tasks, like regular expression matching and rewrite systems. Then books appeared on compiler development and the basic patterns were taught in programming courses. Nowadays we write excellent compilers for sophisticated languages like C++, Common LISP, and Haskell. The same can happen with component software, once we find the patterns.

Challenges in modern programming

Coupling and variabilities

Two pieces of code are coupled if there is a high probability that changing one piece will require changing the other. Because of its complexity, software is highly susceptible to coupling. Coupling can be quantified by a dependence matrix containing the probability that module A will have to change in response to a change in module B. High probabilities are bad because an upgrade can have a cascade effect of changes throughout the system, and the duration of this cascade is exponential in the probability of coupling. Thus we expect that coupling correlates with the cost of maintenance, and indeed Darrel Ince cites confirming studies. Coupling is essentially the opposite of modularity and must be minimized for evolutionary prototyping to be cost-efficient.

A global technique to reduce coupling is to distribute knowledge on a "need-to-know" basis. That is, module A doesn't know about module B unless B has an immediate role in A's job. This is the main reason to avoid sprawling global namespaces. Furthermore, what A knows about B is limited to the role that B has to A. This is the motivation behind encapsulation and multiple interfaces.

A more localized technique to reduce coupling is to anticipate where change will occur and then to facilitate that kind of change. Such places of likely change are called variabilities. Marshall Cline has used the analogy of joints along a skeleton. To extend the analogy, the degree of variability is like the range of motion, and coupling is like a stray vein connecting your elbow to your torso. Requirements analysis can help in determining the placement and degree of variabilities.

However, it is the job of the designer to make sure that encapsulation and variabilities are preserved through changes. Encapsulation says "these modules should not interact", while a variability says "this module should be replaceable." The word "should" stresses that these are policies, not mechanisms. Decoupling is a non-functional requirement: it does not, by itself, make code fulfill its job any better. Unfortunately, analysis and design has traditionally focused on functional requirements. Patterns are designed to express policies, and so form a valuable addition to the designer's vocabulary.

Increased emphasis on design

Languages, as yet, have not reduced the importance of good design. Thus one of the few truly effective productivity techniques is nuturing good designers, as Brooks has pointed out. Poor design cannot be made up for by clever implementation or marketing. Ince notes that "programming is easiest task that occurs on a software project" once the detailed design is done.

In the waterfall model, errors in design are much worse than errors in implementation or testing, because they occur earlier in the cycle. Evolutionary prototyping exacerbates this imbalance, because it also requires self-preserving designs.

Because designs are conceptual, we need novel ways to test them. The most common technique is to have the design reviewed by peers (see evaluating a design), including a "walk-through" where the design is mentally executed step-by-step. Patterns offer another, much simpler, technique: use a design which has proved successful in the past.

What is a good design?

Now we have some basic tools in which to evaluate competing designs:
  1. First and foremost, a design must make it possible for an implementation to meet the functional requirements within the allotted resources.

  2. A good design should also be understandable, so that others might repair or even improve it. A good question to ask yourself is: "If I make a small mistake in the design, can anyone notice and fix it?" This means that the design should be simple and coherent, regardless of how complex the task is. Basing the design on a common pattern is a great way to do this. Thus, oversimplifying one component at the expense of another is not a good design.

  3. A good design should be amenable to change. Applying the same design to many different problems, i.e. making it a pattern, is a good way of ensuring this. The design should therefore minimize coupling and identify variabilities.

  4. A good design should preserve itself through change. It should focus on policies, not mechanisms. Avoid the possibility that a careless bug fix will erase a variability or induce unnecessary coupling. Supplying a rationale with the design is a good way to do this.

Many different architectures can be good designs for the same task. Hopefully, this course will expand your mind to the possible designs, as well as give you the ability to choose and articulate a design. In this course, we will use these four basic principles to evaluate patterns. Afterwards, you can use the patterns themselves to evaluate designs.

Design patterns

Designing object-oriented software is hard, and designing reusable object-oriented software is even harder. Experience shows that many object-oriented systems exhibit recurring structures or design patterns of communicating and collaborating objects that promote extensibility, flexibility, and reusability.
Erich Gamma

What patterns are

A design pattern is a bite-sized chunk of engineering knowledge. It gives a name to a relationship between objects which is used time and time again by software professionals. Patterns also include a rationale for their context of applicability, and situate themselves among the other known patterns. Ideally, all programs would be describable as a collection of standard design patterns. See the Patterns Home Page for a more complete definition. Also see Douglas Schmidt's allegory.

The pattern form used in this course is:

The general problem to be solved. When to apply the pattern.

Potential consequences that a good solution must take into account. Forces are often non-functional, such as reducing coupling or providing a variability.

Objects that make up the design, their roles, and their relationships. What each object needs to know about the others.

The costs and benefits of applying the pattern. How well it resolves the Forces. Used for evaluating competing solutions.

Suggestions and pitfalls in implementing the pattern.

Known Uses
Examples of the pattern found in real systems.

A pattern is not a new way of solving the problem: by definition, the solution has been used before, usually many times. The value of a pattern is how it is presented. Because of pattern form, patterns articulate design decisions concisely, including how they meet non-functional requirements. In this way, they communicate successful design knowledge between programmers. Patterns help develop good habits that make it easy to write good code.

What patterns are not

Design patterns do not lead to direct code reuse, because they are not linguistic entities. They are not macros or class libraries. They can be implemented in many different ways, each with its own resource efficiency (though most patterns are designed to have efficient implementations). What defines a pattern is its design policy: the qualities that should survive functional changes. Thus patterns are only instructions for the human mind.

Design patterns usually do not entail complex implementations. The difficulty in patterns is knowing when and why to use them. This course focuses on case study of patterns in action, not implementing the patterns yourself. Therefore, an important complement to this course is looking for where patterns could be applied in your own software projects.

Further reading

Fredrick Brooks. The Mythical Man-Month. Addison-Wesley, Reading, MA, 1975.

Fredrick Brooks. "No Silver Bullet", in Communications of the ACM, April, 1987.

Darrel Ince. Software Development: Fashioning the Baroque. Oxford University Press, Oxford, 1988.

Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA, 1994.

Mary Shaw and David Garlan. Software Architecture: Perspectives on an Emerging Discipline. Prentice Hall, 1996.

"Software Patterns" in Communications of the ACM, October, 1996.

Robert Orfali, Dan Harkey, Jeri Edwards. The Essential Distributed Objects Survival Guide. John Wiley & Sons, 1996.

Thomas Minka
Last modified: Sun Aug 17 15:04:45 EDT 1997