Symmetry Breaking in Software Patterns

We shall now prove that the set of all invertible inheritance operations on the classes in a given subtyping path forms a symmetry group.

1. Inverses exist in the sense of the above assumption.
2. Closure follows from transitivity of the equivalence relation. For the inheritance operation D on all classes x, y, and z, the composition of DD is the result of consecutive application of D, such that:

x y = D(x),

y z = D(y) = D(D(x)) = (DD)(x),

x z = (DD)(x),

x z = D²(x)

Thus for the inheritance operation D their compositions D², D³, … are also inheritance operations.

3. Associativety holds for composition by consecutive application. It is evident that using the closure property, we can obtain:

D(DD) = (DD)D = D³

Hence we have proved the associativity.

4. The identity transformation is a null inheritance operation. In other word, it is a do-nothing operation, such that:

     x x x     ;or     I(x) = x x

All the invertible inheritance operations on the classes through a single subtyping path form a symmetry group for class invariants. We may consider inheritance operations as translations that transform classes in time [33]. We can represent such translational symmetries as a linear train of iterations:

… D^-3 = D^-1D^-1D^-1, D^-2 = D^-1D^-1, D^-1, D⁰ = I, D¹ = D, D² = DD, D³ = DDD, …

Translation and other temporal symmetries (transformation over time) are common themes in computer programs, as we shall also see in Section 4.4. In fact, temporal symmetry is a fundamental phenomenon in symmetry breaking in the natural sciences. For example, the idea that time is reversible is called the T symmetry in the classic CPT symmetry model of physics; symmetry breaking in all of these symmetries is the very reason that anything exists ([19], pp. 79-81).

Generalizing the ideas of classification and temporal symmetry, we can define symmetry in terms of any invariant or notion of equality ([32], pp. 395-396) for a system under consideration.

4.4 Overloaded Operators as Symmetries

Operator overloading, and associated friendship relationships in C++, have consciously been provided to express symmetry ([21], p749). Overloaded arithmetic operators support reflection symmetry, freeing the user from distinguishing between the left and the right operands, as A+B = B+A and A*B = B*A.

Overloaded operators not only can support reflection, but also translation as well. For example, overloaded "+", "-", "*", "/" free the user from distinguishing between primitive numbers and objects.

5 Symmetry Breaking and Pattern

When a system encounters stress it loses symmetry. The phenomenon of symmetry breaking may be explained in terms of symmetry groups. Consider the common example of a proto-planet rotating in space, a sphere of symmetry group O(3). If it spins too fast it may become pear-shaped, losing one degree of symmetry so as to fall into O(2). If the spinning continues it may break into a planet/moon system which still has overall symmetry O(2), though it has lost the spherical symmetry of the original system. This is called spontaneous symmetry breaking in physics [24], or symmetry-breaking as we call it here. Symmetry doesn't really "break", but is just reduced or redistributed in the effect produced by symmetry in the cause. When a symmetry group is broken, it results in a new group that is a subgroup of the original. Note in this moon-formation example, each of the parts still has O(3) symmetry, even though the system has been reduced to O(2).

Symmetry breaking results in patterns, or more precisely, reveals patterns, for too much symmetry isn’t perceived as pattern [30]. For example, a regular n-sided polygon belongs to the dihedral group D_n. When n is infinitely large, the polygon is close to a circle, which isn't rich in structure. But if some of the symmetries in this polygon break, or when n becomes smaller, say, 6, 5, 4, or 3, we begin to see the shape of the polygon. The phenomenon of symmetry-breaking was first discovered in 1923 by Ingram Taylor when studied the dynamics of the fluid flow, which was known as hydrodynamic "symmetry paradox":

This paradox, that symmetry can get lost between cause and effect, is called symmetry-breaking. In recent years scientists and mathematicians have begun to realize that it plays a major role in the formation of patterns.

…

From the smallest scales to the largest, many of nature's patterns are a result of broken symmetry; and our aim is to open your eyes to their mathematical unity. ([30], p. xviii)

The idea of symmetry breaking carries through to Alexander's patterns. Varied Ceiling Heights [1] is a symmetry-breaking pattern. Light on Two Sides of Every Room [1] is another example: a perfectly symmetric room would have either no windows or would have windows on four sides. A room with windows on four sides would be perfectly symmetric and would lack the quality Alexander seeks in his work. He remarked that too much symmetry is a bad thing:

Living things, though often symmetrical, rarely have perfect symmetry. Indeed perfect symmetry is often a mark of death in things, rather than life.

I believe the lack of clarity in the subject has arisen because of a failure to distinguish overall symmetry from local symmetries. ([2], The Phenomenon of Life, 44.)

and:

In general, a large symmetry of the simplified neoclassicist type rarely contributes to the life of a thing, because in any complex whole in the world, there are nearly always complex, asymmetrical forces at work--matters of location, and context, and function--which require that symmetry be broken. ([2], The Phenomenon of Life, 45.)

Symmetry breaking also plays an important role in the characterization of Alexander’s 15 structural properties. Local Symmetry requires some symmetry be broken. Roughness, Gradients, Echoes, and Levels of Scale all exhibit symmetry, but lack perfect symmetry characteristic of the next largest symmetry groups (perfect smoothness, bilateral symmetry, and equal size).

The idea of symmetry breaking also extends to software patterns, as we shall see in Sections 6 and 7. For example, class extension is a symmetry; Bridge is a pattern that reflects symmetry breaking under the stress of certain design desiderata.

6 Patterns and Symmetry Breaking in Software

As discussed in Section 4, many programming language constructs express symmetry. When those constructs fail to solve design problems, programmers often resort to patterns to express the design in the programming language. This section attempts to show that most software patterns are a result of symmetry breaking.

6.1 Breaking Type Symmetry

Assume we have a class, List<T> in some library. We wish to derive from it a new type, Set<T>. Let’s see if such derivation can preserve class invariants in List<T>, as discussed in Section 4.3.

First, a set is not a subtype of a list, nor is the reverse true. For example, by the principle of extensionability, sets with the same members are equal [17]. So adding the same member twice to a set is the same as adding the member only once. However, adding the same member twice to a list is different from a single insertion.

Therefore, deriving a set from a list breaks the symmetry that subtyping attempts to conserve. We start with a List and want to transform it into a Set. The symmetry breaks. Where does it go?

Imagine if the symmetry did not break, i.e., in the normal subtyping situation, the relationship between a subtype and its supertype would be denoted as in Figure 1. However, since the symmetry is broken, the new relationship lacks the symmetry of Figure 1, reflecting only local symmetry (Figure 2). This is known as the Adapter pattern. In this pattern, the insert and has methods appear in all three classes.

Most of the structural patterns (Adapter, Bridge, Composite, Decorator, and Proxy) [16] deal with the tension between language constructs that express symmetries, and the small perturbations that make those constructs unsuitable for use. Some of the behavioral patterns (Iterator, Memento, Observer, State, Strategy, Template Method, and Visitor) can also be easily described in terms of temporal symmetry breaking. Other design patterns take more imagination to describe in symmetry-breaking terms, which raises the question of whether they are patterns in the Alexandrian vein.

From the perspective of symmetry breaking, a pattern is a way of redistributing the forces in a symmetric system in light of some instability. Symmetry is reduced, but not lost; it is redistributed in the pattern. The exact way in which it is redistributed is difficult to predict. Global symmetries are lost, but local symmetries are preserved.

We want to point out here that the term local symmetry is not an original Alexandrian formulation, but is a standard term in the symmetry group communities of crystallography ([23], p. 29; [29], p. 567) and quantum physics ([24], p. 173).

6.2 Breaking Function Symmetry

Multiple dispatch is a form of symmetry breaking. In a Liskov type hierarchy, subtype methods have a level of equivalent semantics defined by the bounds of pre- and postconditions, semantics that programmers usually associate (however informally) with the method selector. In a classful language these symmetries in a type hierarchy preserve class invariants, as discussed in Section 4.3.

When a type hierarchy is used for dynamic binding, a member function is chosen according to the type of its instance at run time. The symmetry breaks if the member function depends on the types of more than one object; the LSP no longer holds. . This is a form of symmetry breaking for which the longstanding linguistic solution is multiple dispatch. This of course is the Visitor pattern [16].

The "Promote and Add" pattern is also symmetry breaking. The "+" operator is interesting not only because it supports symmetries as discussed in Section 4.4, but also because it has a highly symmetric signature:

T x T T

If we picture "+" operating between pairs of objects, where each object participates in a class hierarchy, we get a nicely symmetric picture as in Figure 3.

But reality is messier because of the need for heterogeneous addition. For example, it makes sense to ask for 1 + 4.5, as in Figure 4--a broken symmetry (and it's independent of multiple dispatch or polymorphism).

The solution is a geometric transformation, a pattern, called Promote and Add, originally written up as a C++ idiom [13], but which can also appear in broad architectural contexts as patterns such as Add a Switch [9]. It adds local symmetries by promoting heir types to their parent types as a prelude to addition, thereby reducing the problem to that of the first picture. It is a structure-preserving transformation that adds centers (the transformations from derived types to base types) to the first picture. The resulting Smalltalk bears out the pattern explicitly in methods such as sumFromInteger, asDouble, and ArithmeticValue>>retry.

6.3 Breaking Class Symmetry

We usually think of types as abstract specifications with classes as their language realizations. The class structure often follows the type structure. But sometimes, even though the type structure reflects a structure-preserving transformation consistent with the LSP, the class structure does not preserve structure for reasons that owe to language implementation peculiarities. This means that the symmetry of the class structure is broken, and a pattern usually results.

Again consider class Complex, whose implementation is two real numbers. Abstractly we can talk of the symmetry group of type Complex as comprising transformations that preserve class invariants as discussed in Section 4.2. These invariants hold, with respect to member function behavior (type symmetry) for heir classes such as Real and Integer, as one would expect.

Even though the member functions are preserved in the transformations from Complex to derived types, the structure of the Complex class may not be preserved in Real and Integer. In particular, Complex has two reals and Real would have only one. Eiffel would call this restriction inheritance ([27], p. 826). In the representation of the class, there is at best a weakened symmetry between Complex and Real (one could argue that they are symmetric with respect to the preservation of the real component) but all structure is lost by the time we get to Integer. Symmetry slowly breaks as we descend the hierarchy. We find the same case for Ellipse and Circle, as in Meyer ([27], p. 467).

In either of the cases, we lose symmetry when the inheritance transformation is not structure preserving as required in the LSP, so we have symmetry breaking. What results is usually a pattern; in this case, something like Bridge might be in order.

7 Other Examples

We can look beyond object-oriented programming language constructs to find many examples of symmetries and symmetry breaking in software design.

Symmetries abound in programs and can be found beneath almost all programming structures. In addition to symmetries we have discussed in Section 4, loops are spiral time symmetries. Simple conditionals can be viewed as symmetry breaking, while case statements can also be viewed as symmetries that hold the entry and exit points invariant. Argument defaulting is a form of overloading where the symmetry is the preservation of some argument types. Rather than focusing on these programming-in-the-small symmetries, in this paper we focus on the design structures that are of greater interest to the field of object orientation.

Patterns are introduced as a result of symmetry breaking in all of these cases. We showed above, in Section 6.2.2, what happened when the symmetry of overloaded operator + broke. This is hardly an object-oriented phenomenon, either. The work in [10] introduced the notion that functional and applicative languages may succumb to these analyses more readily than object-oriented languages do, owing to the largely geometric nature of the source and translated program structures.

The symmetries supported by language constructs might be used as a basis for objectively comparing the relative expressive power of a programming language. For example, the number of symmetries and the type of symmetry might be used as such an objective indicator. We suggest further empirical work in this area.

We find patterns outside the programming language context, too. Patterns such as Half Object plus Protocol (HOPP) [25] are an obvious example of symmetry-breaking reminiscent of bifurcation symmetry. It should be noted that there is nothing fundamental about the system in which HOPP is embedded that suggests that symmetry break in a way that results in two objects; it could just as well break into three objects, as it does in the pattern Three-Part Call Processing [9].

In the Cascade pattern for a public transport system [34], it was observed that both the driver duty object and its builder were cascades. A driver duty can be seen as a result of a translation of its builder (the Prototype pattern) or as a rotated bilateral symmetry. Other examples in telecommunication software are documented in [9].

Model-View-Controller expresses symmetry between a Model object and a User object. What breaks the symmetry is the need for the User object to maintain multiple views of the Model. That gives rise to the View object itself, and to the Controller as a dispatcher from the User to the Model and View. [Trygve Reenskaug, Personal conversation, June 1999].

Fresh Work before Stale [26] is a classic example of temporal symmetry breaking. The pattern creates a broken symmetry in the flow of work that gives priority to new work over pending work, and throughput increases as a result.

Factory Method and Abstract Factory [16] break the symmetry of the structures of the object produced by instantiation processes. Template Method breaks the symmetry of individual algorithms.

Domain analysis techniques are rooted in axioms of commonality and variation [11]. Group theory may provide constructs for formalizing this structure as well: symmetry is about commonality invariance; symmetry breaking is about variations.

8 Towards A Pattern Formalism

So, what is a pattern? The question is the closest thing to a religious debate in computer science since the debate raged about "What is object orientation?" There are many qualities often used to distinguish, or sometimes distance, patterns from mainstream academic computer science. Among these are beauty, maturity of ideas, and attunement to human comfort. Here we try to put these elements in perspective.

Does Alexander's stipulation that a pattern only exists within a pattern language ([3], p. 312) relate to symmetry and symmetry breaking? Remember that a pattern is a transformation, a transformation that breaks some symmetry present in the original system, adding asymmetry. The original system defines context; without that context, there may in fact be no symmetry to be broken. What might otherwise pass as a pattern, out of context, may simply be a symmetry. We can also explain the relationship between symmetry and symmetry breaking as a causal relationship: the original system exhibiting the original symmetry is the cause; the transformed system in which some symmetry is broken is an effect.

As mentioned early, broken symmetry doesn’t necessarily mean asymmetry unless all the symmetry is lost. Although it is not the topic of this article, we wish to point out that symmetry only exists with respect to asymmetry ([28], p. 161) and asymmetry is a frame of reference to symmetry.

One may criticize the design patterns [16] as not meeting the Alexandrian criterion of necessarily emanating from a whole, from a pattern language. However, some of the design patterns constitute patterns that form a pattern language for a particular design problem. Symmetries that these patterns attempt to preserve or break may be identified. This leaves hope that the design patterns may be legitimized as patterns in a fashion tantamount to, or at least analogous to, the closely related idioms work [13].

One key suggestion for future work is to show that a pattern language forms a contextual framework for the formalization of symmetry breaking (the very definition of individual patterns), and that such a framework forms not only a language, but also an algebra of specification. The outcome seems likely; after all, a geometry is essentially an algebra of symmetries.

Based on the above analysis, we posit the following formal definition of a pattern:

Definition: A pattern characterizes a structure resulted from breaking an original symmetry, where the symmetry is defined in terms of an invariant in a system. Examples of such invariants include class structure (in the vulgar sense as in Section 4.2) and behavior (subtyping as discussed in Section 4.3).

In other words, a pattern represents a symmetry effect that is less symmetric than the symmetry cause, where the symmetry cause is produced by a programming language construct. Patterns precipitate from symmetries in response to both internal and external forces that are the analogy of instability.

A pattern is a design solution that language constructs fail to provide. A pattern language defines a composition law for composing patterns in a specific way to solve a larger design problem. A pattern is in relation to a symmetry that in turn is in relation to a geometric context: a symmetry group.

The formal aspect of the definition is necessary but not sufficient. The articulation of a pattern is also subject to a value system, and in particular to aesthetic and quality considerations. Among these considerations are human comfort, utility, beauty, durability, and maintainability.

This definition is simply a distillation of the findings of this paper, cast in a way that ties the group theoretic foundations with the vernacular definitions. We propose it as a foundation for further work in the formalization of software patterns.

One might use this definition to conclude that because the design patterns reflect different geometric contexts, they could never all be unified in a single pattern language. For example, the context for Observer and Memento is temporal symmetry while the context for most other patterns is more spatial. This contextual modeling might provide a framework for a pattern taxonomy that would be more useful than the current taxonomy (creational, structural, etc.) for the stated purpose of a pattern language: to create whole systems through a piecemeal growth process.

9 Conclusion and Acknowledgements

Other attempts to formalize patterns have striven for implementation automation. That is not our goal here, as automation of pattern assembly is an oxymoron from first principles. Our goal is to provide a formal basis for the characterization of patterns in specific contexts. For example, the symmetry theory foundation for patterns explains why multiple dispatch is a pattern in Smalltalk, and is not a pattern in CLOS. It explains why inheritance for subtyping is a symmetry, lacking the symmetry-breaking properties that are characteristic of patterns, even though Inheritance wrongly appears as a pattern in some collections [31]. This model may provide a foundation for legitimizing other patterns on the basis of temporal symmetry breaking models, even hopelessly non-spatial patterns.

This paper deals with patterns commonly associated with design. There may be other useful patterns of programming, such as indentation style and other modular constructs, that also exhibit symmetry and symmetry breaking and which are equally important to the success of software development.

Ralph Johnson provided initial feedback to the original draft and has continuously provided valuable insights and comments to various versions of the paper. We are also deeply indebted to Michael Benedikt, Ellie D'Hondt, Maja D'Hondt, Ed Remmel, Curtis Tuckey, Gottfried Chen, Edith Adan-Bante, Peter Mataga, Rachel Suddeth, Kevlin Henney, Neil Harrison, Rich Delzenero, Christoph Koegl, and Peter Grogono.

References

1. Alexander, C., et al. A Pattern Language. New York: Oxford, ©1977.
2. Alexander, C. The Nature of Order. Pending publication by Oxford, New York, New York. Citations quoted with permission.
3. Alexander, C. The Timeless Way of Building. New York: Oxford, ©1979.
4. Alexander, C. A Foreshadowing of 21^st Century Art: The Color and Geometry of Very Early Turkish Carpets. New York: Oxford University Press, ©1993.
5. Cook, W., and J. Palsberg. A Denotational Semantics of Inheritance and its Correctness. IN OOPSLA '89 Conference Proceedings, SIGPLAN Notices 24(10), 1989. New York: ACM SIGPLAN, p. 436.
6. Coplien, J. Advanced C++ Programming Styles and Idioms. Reading, MA: Addison-Wesley, ©1992.
7. Coplien, J. Software Patterns. New York: SIGS Publications, ©1996.
8. Coplien, J. Space: The Final Frontier. C++ Report 10(3). New York: SIGS Publications, March 1998, 11-17.
9. Coplien, J. Worth a Thousand Words. C++ Report 10(5). New York: SIGS Publications, May/June 1998, ff. 54.
10. Coplien, J. To Iterate is Human, to Recurse, Divine. C++ Report 10(7). New York: SIGS Publications, July/August 1998, 43-48; 51.
11. Coplien, J. Multi-Paradigm Design for C++. Addison Wesley, Reading MA. 1999. ISBN 0-201-82467-1
12. Coplien, J. Take Me Out to the Ball Game. C++ Report 11(5). New York: SIGS Publications, May 1999, 52-8.
13. Coplien, J. C++ Idioms Patterns. In Pattern Languages of Program Design 4. Reading, MA: Addison-Wesley, ©2000.
14. Eden, A. H., J. Gil, A. Yehudai. A Formal Language for Design Patterns. 3^rd Annual Conference on the Pattern Languages of Programs (Washington University Technical Report WUCS-97-07).
15. Eden. A. H., J. Gil, A. Yehudai. Precise Specification and Automatic Application of Design Patterns. The Twelfth IEEE International Automated Software Engineering Conference (ASE 1997).
16. Gamma, E., et al. Design Patterns: Elements of Reusable Object-Oriented Software. Reading, MA: Addison-Wesley, ©1996.
17. Gordon, C. and N. Hindman. Elementary Set Theory. Hafner Press, 1975.
18. Grenander, U. Elements of Pattern Theory. Baltimore, Maryland: Johns Hopkins University Press, ©1996.
19. Hawking, S. A Brief History of Time. New York: Bantam, ©1996.
20. Kappraff, J. Connections: The Geometric Bridge Between Art and Science. McGraw-Hill, 1990.
21. Lippman, S. B., and J. Lajoie. C++ Primer. 3^rd Ed. Addison-Wesley, 1998.
22. Liskov, B. Data Abstraction and Hierarchy. SIGPLAN Notices 23,5, May 1988, p. 25.
23. Mackay, A. L. Generalized Crystallography. Computers & Mathematics With Applications, 12B(1/2). Exeter, UK: Pergamon Press, 1986.
24. Mannheim, P. D. Symmetry and Spontaneously Broken Symmetry in the Physics of Elementary Particles. In Computers and Mathematics with Applications, 12B(1/2). Exeter, UK: Pergamon Press, 1986, 169-183.
25. Meszaros, G. Pattern: Half-Object plus Protocol (HOPP). In J. O. Coplien and D. Schmidt, eds., Pattern Languages of Program Design, Reading, MA: Addison-Wesley, ©1996, Chapter 8, 129-132.
26. Meszaros, G. A Pattern Language for Improving the Capacity of Reactive Systems. In Pattern Languages of Program Design - 2. Reading, MA: Addison-Wesley, ©1998, p. 586, "Fresh Work Before Stale."
27. Meyer, B. Object-Oriented Software Construction. Upper Saddle River, NJ: Prentice-Hall, ©1997.
28. Rosen, J. Symmetry in Science: An Introduction to the General Theory. New York: Springer-Verlag, 1995.
29. Senechal, M. Geometry and Crystal Symmetry. In Computers and Mathematics with Applications 12B(1/2). Exeter, UK: Pergamon Press, 1986.
30. Stewart, I., and M. Golubitsky. Fearful Symmetry: Is God a Geometer? London: Penguin, ©1992, 1993.
31. Tichy, Walter. Essential Software Design Patterns, http://wwwipd.ira.uka.de/~tichy/patterns/overview.html, n.d.
32. Urmantsev, Y. Symmetry of System and System of Symmetry. Computers and Mathematics with Applications, 12B(1/2). Exeter, UK: Pergamon Press, 1986, 379-405.
33. Weyl, H. Symmetry. Princeton University Press, 1952.
34. Zhao, L, and T. Foster. Driver Duty Constructor: A Pattern for Public Transport Systems. In The Journal of Object-Oriented Programming 12(2), May 1999, 45-51; 77.