Deriving Patterns from Design Principles

Published in Journal of Object Oriented Programming, October 1998.

Note: this is a pre-publishing draft. However, it closely matches the final paper.

Abstract
A good design pattern has many desirable properties. Most of these properties are also embodied in abstract design principles. However, there is a large gap between abstract principles and the concrete architectures of patterns; so, design remains hard in spite of the wealth of knowledge on principles and applications. Systematic transformation techniques, which enforce observance of design principles and rules, can be used to derive well-known patterns starting from trivial designs. Here the Observer and Mediator are derived from the Stratification Rule, using simple transformation techniques. The same techniques, and the same approach, can be used in everyday work to improve the quality of design.>

Design patterns1 convey important knowledge, in the form of elegant solutions to recurring design problems. Looking at patterns, however, I always feel that the most interesting question is: "How was the underlying structure conceived the first time?". Most likely, under the guidance of sound software engineering principles and rules. Still, the pattern does not tell us the whole story. It seems we can reuse the pattern, but not the steps who gave it birth.
In this article, I’ll consider one of the fundamental design principles, derive a formally verifiable rule from it, and then describe two transformation techniques to enforce the observance of the rule. Then I’ll consider a naive design for a document/view problem, using only concrete classes, which among other things violates said rule. I’ll show how the Observer pattern can be derived from the naive design, by applying the first transformation technique. I’ll then present a trivial design for a font selection dialog, again breaking the rule, and show how the structure of the Mediator pattern can be derived from it using the second technique.
Along the same lines, other patterns can be derived applying transformation techniques guided by principles and rules. The usefulness of design rules and transformation techniques obviously transcends pattern derivation, and they can be adopted as part of a more systematic approach to software design.

From Principles to Rules
There are several ways to formulate a principle. Usually, the choice is between an informal, but highly intuitive statement, and a rigorous formulation, maybe amenable to measurement but often less intuitive. Often, the rigorous formulation is classified as a "rule", whereas the intuitive form takes the name of "principle".
The design principle I’ll consider here can be informally stated as "each class should only depend on more general classes". The underlying concept is highly intuitive: if a class depends on more specialized classes, reuse is hindered because when you try to reuse the general class, you have to carry the burden of the more specialized, potentially extraneous classes. Also, if the specialized classes are modified, the general class may need changes, or at least recompilation. Unit testing becomes more problematic, as the general class cannot be tested without (at least) a stub for the specialized classes. Finally, in more than a few cases a violation of this principle leads to a violation of Meyer’s Open/Closed principle2: you may have to "open" the general class for modification, to make it operate on some other specialized class.
This design principle is also known as the Dependency Inversion Principle3, which states "Details should depend upon abstractions. Abstractions should not depend upon details". Words change, but the meaning does not.
Note, however, that the principle cannot be verified formally. There is not a formal notion of "abstraction" (or "detail") that can be used to verify whether a design is following the principle or not. This has longer been known: in one of the early software engineering papers4, David Parnas said "I have not found a relation, "more abstract than", that would allow me to define an abstraction hierarchy. Although I am myself guilty of using it, in most cases the phrase "levels of abstraction" is an abuse of language". Also, even if you realize that your design does not respect the principle, there is little in the principle itself that guides you toward a better design.
Still, we can often settle for weaker necessary conditions that can be formally verified. If those rules are not took weak, they can provide most of the benefits of the principle, together with the benefits of being unambiguous.
One of these rules is the Stratification Rule. Given two classes A and B, we say that A depends on B if and only if A refers to B, in its interface or implementation. Using the "depends on" relationship, you can easily build a dependency graph for classes: (A,B) belongs to the dependency graph if and only if A depends on B. The graph is directed, as the "depends on" relationship is not symmetrical. The Stratification Rule requires the dependency graph to be acyclic; if you violate the rule, the unit of reuse becomes the cycle, not the class. This may be acceptable in some cases, or a huge mistake in others: as a designer, you have the responsibility to discriminate.
I call a class diagram with an acyclic dependency graph a stratified system, since it is possible to stratify the graph, obtaining several layers of classes which depends only on classes belonging to upper-level layers.
The definition given is similar to Lakos’ Levelization5, but Lakos’ work is directed at the physical level and deals with files, inclusions, and other low-level details. However, a stratified system is more easily implemented as a levelizable program, because if you start without cycles in the structure, you only have to avoid the introduction of cycles in the coding phase, not to remove structural cycles during the implementation.
If we consider each layer in the stratified system as an abstraction level, it is obvious that an acyclic dependency graph is a necessary condition for the principle given above. Note that while the intuitive principle given above is stronger, the definition of stratified design lend itself easily to objective measurement, while the informal definition of the principle contains some inherently non-measurable semantics: "general", "abstraction" and "details" are not measurable entities. Since the rule is weaker, it is possible to build a system that respects the Stratification Rule, but not the spirit of the principle. In practice, however, in a significant number of cases a violation of the principle reflect itself in a violation of the rule. Other rules can cover parts of the remaining cases.

A Rule, Two Techniques
A design principle (or rule) provides useful guidance in terms of goals; however, often it says little or nothing about how to reach those goals. Unfortunately, without a good injection of pragmatism, principles are condemned to remain in the crowded realm of the "academically interesting, but practically useless" topics. You can find several good books and papers about what makes a design good, but substantially less about how to make it good; in other words, there is much more knowledge on the principles than on the practical techniques.
The pattern community took the opposite path, starting with real-world solutions to real-world problems. To reconcile the two views, it is not enough to move from principles to rules: each rule must be accompanied by concrete transformation techniques, which can be used to enforce observance of the rule itself.
Consider the non-stratified system in fig. 1: here, each class knows about the other, e.g. for control and notification. This is the simplest form of a non-stratified system, so it’s the best suited to discuss transformations. I’ve identified several transformation techniques which, applied to the system in fig.1, lead to an equivalent but stratified design: here I’ll present two of them, and then show how they can be used to derive well-known design patterns.

The first transformation technique is represented in fig. 2: the part of the interface (and possibly of the implementation) of class A which is used by class B is abstracted in class A*; then A is derived from A* and continues to use B, while B uses only A*. This technique introduces an asymmetry in the class diagram: in fact, we will use it to leverage an existing asymmetry in the original problem. I call this technique Asymmetrical Splitting. The technique has another interesting benefit (extensibility on the A side) which I’ll not consider further in this article.

The second technique is represented in fig. 3: here part of the implementation of A and B is extracted into a concrete class C, while A and B refers to an abstract class C* whenever they need a service (formerly provided by the other party). Class C is derived from C* and provides concrete implementation for the services. The technique is symmetrical, and we will use it when the problem is symmetrical by nature. I call the technique Symmetrical Splitting.

It is worthy to note that the usefulness of the techniques above is not restricted to pattern derivation: in fact, I’ve applied them routinely in several real-world projects, to correct design flaws due to inexperience or haste. They are also very simple, and most people whom I’ve taught the rule and the techniques grasped them easily, and again used them routinely to improve their design. Most of the experienced designers use them intuitively; less experienced developers can easily learn to do so.

The Observer
The Observer1 is one of the most widely used patterns, especially in its document-view incarnation (which I’ll use as an example). Consider the class diagram in fig. 4: here an inexperienced designer modeled two documents, with two views each, in the most trivial way. There is a concrete class for each document, and a concrete class for each view. Since documents must notify views when data change, and views must be able to access the document, documents and views end up as strongly coupled classes, and the design is not stratified. Also, the Document Manager must be able to create the documents, and each document must be able to notify the manager of its destruction. Hence a cycle between each Document class and the Document Manager.

We can apply the Asymmetrical Splitting technique here. In fact, it can be applied once for each concrete view class. The resulting diagram is represented in fig. 5. The class View (corresponding to A* in fig. 2) decouples the concrete documents from the concrete views, by introducing an higher-level, abstract class. Note that I’ve merged the various A* classes (one for each concrete view class) into a single class View: it is possible to make this intermediate step explicit, and then merge the classes under another rule (Role Abstraction) mentioned below.

We can now apply the same technique between Document and Document Manager. The result is the class diagram in fig. 6 (I’ve left out Document2 for simplicity): the same structure of the Observer pattern.

It is worthy to note that the problem structure guided the selection of the Asymmetrical Splitting transformation. Indeed, the problem itself is asymmetrical by nature: a Document may have many views attached, but a View is always attached to one, and only one, Document. Also, there is only one document manager, but several documents.
The Stratification Rule pointed out a flaw in the design, and the problem structure helped choosing the appropriate transformation technique to remove the flaw. From a trivial, flawed design we obtained the structure of Observer, in a systematic and straightforward way.

The Mediator
The Mediator1 is often used to implement dialog boxes. Here I consider a simplification of the example given in Design Patterns1, where only a text box and a list box (which contains a list of available fonts) must be synchronized. A trivial design in represented in fig. 7. A FontDialog owns an EditFont and a ListFont, and each of them knows the other, in order to keep their contents synchronized; again, this results in a non-stratified design.

We can apply the Symmetrical Splitting technique here. The resulting diagram is represented in fig. 8. The class Mediator (corresponding to C* in fig. 3) decouples EditFont and ListFont by introducing an abstract class which receives notifications. The concrete class FontMediator (corresponding to C in fig. 3) implements the handling of such notifications.

FontMediator and FontDialog can now be merged into a single class, since they have the same data and the same role, that is, to control the edit box and the list box. Also, once decoupled from any concrete class, the role of EditFont (notification of an abstract container) can be lifted up in Edit. Therefore, Edit and EditFont can be merged, and so can List and ListFont. The resulting class diagram is represented in fig. 9: the structure of the Mediator pattern.

Again, it is the problem structure that provides guidance in the selection of the transformation technique. The problem here is symmetrical by nature: each control is coupled with another, and from a sufficiently abstract perspective, there is no difference in their behaviour (which, in fact, may be further abstracted in a Widget class). Hence the selection of the Symmetrical Splitting technique.
The Mediator is a form of manager class, and in fact, the Symmetrical Splitting technique tends to decouple classes by introducing a third party. This does not mean that manager classes are inherently good: as I’ve discussed in depth elsewhere6, manager classes are only tools at the service of design principles, not first principles in themselves.
It is important to understand that, once again, the technique is not limited to the derivation of the Mediator pattern. In several practical cases, once the technique is applied the final step from figure 8 to figure 9 is not performed. Instead, we use other transformation techniques to separate the GUI part from a Business Object part. The C and C* classes become part of the business object and don’t get merged with the GUI. C* allows to substitute concrete business rules (class C) without changes to the managed classes.
The Mediator pattern is just a specific instance of use of the technique, useful when GUI and control can be safely merged, and is obtained by combining Symmetric Splitting with a basic transformation technique which I’ll only touch upon here: recognizing commonality in data and behaviour and merging classes is a common refactoring technique that can be ascribed to the Occam’s Razor principle (entities should not be multiplied unnecessarily).

A Systematic Approach to Design
Many experienced designers use transformation techniques intuitively as they proceed in their work. Recognizing and formalizing the techniques, and the rules they try to enforce, is not an easy step. However, rules and transformation techniques form a say-how bridge between the say-what of principles and the show-how of patterns7. I’ve applied this transformational approach to design (that I call Systematic Object Oriented Design) to medium and large-scale systems, and found it reasonably easy to follow, and reasonably easy to teach. Among other things, small-granularity transformation techniques proved very useful during maintenance, when locality of changes is often an highly desirable property.
So far, I’ve identified 4 major rules and 15 simple transformation techniques. These techniques combined are powerful enough to derive most of the GoF patterns and some others as well. I’m still working on cleaning up other techniques, and eagerly looking for more rules. Inspiration can be taken from abstract principles, from the concrete architecture of patterns, from the emerging works on refactoring, and from the large body of heuristics. While the time necessary to formalize each heuristics to obtain measurable semantics is not small, the pay-off I’ve seen so far does definitely worth the effort.

Conclusions
A couple of years ago, Jim Coplien (a respected member of the pattern community) wrote8: "Perhaps a good, general design method would "generate" those patterns from higher level design principles. That would allow the designer to remember just a few simple principles [...] instead of the many patterns that embody the principles".
Indeed, design patterns can be derived from first principles. That does not reduce the importance of patterns, since software engineers need solutions to design problems on different scales. However, in the same sense as we don’t have to memorize all the steps in a theorem proof, but only learn the relevant spots, we may not want to memorize the exact structure of each pattern, but only the underlying rules and the relevant transformation techniques. This will also make it easier to adapt known patterns to slightly different problems, working on a smaller scale than most design patterns do.
Practicing and teaching design is very difficult, because there isn’t an accepted body of knowledge to bridge the gap between principles and applications. Systematic rules and transformation techniques, backed up by solid software engineering principles, may be one step in the right direction.

Bibliography
1. Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, "Design Patterns", Addison-Wesley, 1994.
2. Bertrand Meyer, "Object Oriented Software Construction, 2nd edition", Prentice Hall, 1997.
3.Robert Martin, "The Dependency Inversion Principle", C++ Report, May 1996.
4. David Lorge Parnas, "Designing Software for Ease of Extension and Contraction", IEEE Transactions on Software Engineering, Vol. 5 No. 2, March 1979.
5. John Lakos, "Large-Scale C++ Software Design", Addison-Wesley, 1996.
6. Carlo Pescio, "Manager Classes: a Software Engineering Perspective", Object Expert, May/June 1997.
7. Carlo Pescio, "Principles Vs. Patterns", IEEE Computer, Vol. 30 No. 9, September 1997.
8. James O. Coplien, "After All, We Can't Ignore Efficiency", C++ Report, May 1996.

Biography
Carlo Pescio holds a doctoral degree in Computer Science and is a consultant and mentor for various European companies and corporations, including the Directorate of the European Commission. He specializes in object oriented technologies and is a member of IEEE Computer Society, the ACM, and the New York Academy of Sciences. He lives in Savona, Italy and can be contacted at pescio@eptacom.net.