A Rose without Thorns

The world is full of symmetry, which is defined as the property of invariance against change. But out of all possible symmetries, invariance against changes in scale or 'self similarity' is surely the most elegant and inspiring. In 1963 Benoit Mandelbrot noticed that fluctuations in world cotton prices are the same despite the time scale that they range across. Whether it is over a year or only a week, the price of cotton rises and falls equally rapidly in proportion to the time frame and, although such phenomena had been observed before, it was Mandelbrot who coined the term 'fractal'.

This article examines the relationship between fractals and the Composite design-pattern, and explores these structures in terms of XML.

The picture shows a fractal structure, that of smoke generated by stubble-burning in late summer. It is a fractal because the plume consists of large billows that contain smaller billows that contain still smaller billows and so on recursively.

In fact, fractals and their associated 'power laws' are ubiquitous in the world about us. Whether it is the distribution of craters on the Moon, the chain reaction in a nuclear explosion, or the recursive branching in a cauliflower, the same pattern is present in all. With a similar ubiquity, any discussion of patterns in software design must include the Composite, which, as shown below, is simply our fractal rose by another name.

The essence of the Composite is recursive sub-composition, and a familiar example is a binary search tree. In such a structure it is possible to locate a given object by applying a comparison rule and descending to the left or right-hand child accordingly. The beauty of this is that the rule can be applied recursively — the algorithm is then applied to the selected child, whereupon a child is selected from there, and so on, until the object is found or the search is exhausted.

Given that the algorithm works equally well at any level in the structure, the binary tree can be said to be self-similar, and the applicability of the algorithm is therefore 'scale invariant'.

Composites, that is to say, designs that that exhibit this property, are to be found everywhere in software systems, and instances include compiler parse-trees, scene graphs in graphical modelling systems, and the visual tree-control used in the Windows Explorer application. In the last example, it makes (virtually) no difference where you click and drag on the structure, the drag-drop functionality is the same. I.e. a childless sub-directory, or a parent with children and descendants, can be copied or moved with the same operation.

Given that the defining quality of both composites and fractals is self-similarity or scale invariance, one can view the two concepts as being one and the same. Any fractal is an instance of the Composite design pattern and therefore to talk of Composites in programming is, tantalisingly, to speak of fractals in system design. Given this, it is appropriate to examine how the Composite manifests in UML and, from there, in XML.

The Composite can be illustrated in a variety of ways in UML. Using the binary tree example from above, the diagram is very simple (assuming that nodes with less than two children do not point to a 'sentinel' object).

A variant on this model is to differentiate child objects into a number of forms and this is illustrated in the next diagram. All types in the hierarchy are nodes but only some nodes are branches that can be associated with other child nodes.

In comparison with a binary tree, this means that the self-similarity is more limited or relaxed, as the instance diagram shows. However, a slight variation in the type model can ensure that all objects behave in the same way as every other. The next diagram shows a concrete example that describes an aspect of British company-law.

In the UK a company is regarded as an individual. Individuals can employ other individuals, can make money, pay tax and own assets including companies. A company can do the same, i.e. employ individuals, make money, pay tax and own other companies and the association, shown on the diagram, between the Individual-type and itself describes these relationships.

Whatever the variations however, all of these examples share this common principle of reflexive association, which captures the recursive nature of the Composite. Note however that a reflexive association does not imply fractal properties. For example, the UML for a Decorator pattern uses a reflexive association but is not a Composite because the Decorator does not mandate the notion of scale.

Given these points, let us now turn to XML.

The Composite manifests in a number of ways in XML documents and, using a simple instance of the company law type-model, the listing shows a fractal XML-element structure. Here a Company element contains other company elements and so on.

This document, however, is a little verbose; therefore the use of attributes for the Name and AssetValue data gives a structure that is smaller and easier to understand. In addition, applications can (in principle) read and parse this more quickly.

Another, more sophisticated, approach is to combine content and markup in a 'mixed' content model and using this technique gives us the next example, which in effect, is a fractal story. Here a sub-plot element is composed of text and further sub-plots, which can be nested to an arbitrary depth. The recursive structure means that it reads equally 'well' regardless of how deep or shallow one navigates through the structure. (Agreed, however, it'll never win the Booker Prize.)

For example:

He needed to speak to this intriguing woman in person. After some thought he concluded that Wednesday was probably a better day for it.

Alternatively:

He needed to speak to this intriguing woman in person. But he had to call his business partner to arrange the delivery. Plus there was the car hire for the journey across Spain. After some thought he concluded that Wednesday was probably a better day for it.

Or the full-blown version:

He needed to speak to this intriguing woman in person. But he had to call his business partner to arrange the delivery. Plus there was the car hire for the journey across Spain. Even so, he felt as if Casablanca was within his grasp. After some thought he concluded that Wednesday was probably a better day for it.

However, some child elements cannot be taken in isolation. For example, 'Even so, he felt as if etc.' does not read well on its own because the 'Even so' demands a preceding sentence. Therefore, the use of a 'connector' attribute refines the technique and provides better decoupling between parent and child elements. This then allows the structure to be navigated from the inside out.

For example, the nested SubPlot yields a simple assertion:

He felt as if Casablanca was within his grasp.

However, using the connector enables the parent and child to be concatenated as in:

There was the car hire for the journey across Spain. Even so, he felt as if Casablanca was within his grasp.

This, however, is only half the story (so to speak), as we need to express rules for the structures we have seen so far. The declarations for the above would therefore be as shown.

The first two are fairly straightforward but the mixed content model is a little more challenging. In this instance the group must be a choice group (the OR operator), the entire content model must have zero or more multiplicity and the PCDATA token must come first. (These restrictions are a throwback from XML's SGML heritage.)

However, syntactic constraints aside, what is common among all of these is the nesting of a type within its own content model, which echoes the reflexive associations shown in the UML examples.

The Composite pattern is very important in system design, because of its combination of simplicity and power. However, space constraints mean that this exposition has barely scratched the (fractal?) surface. For example, the different forms of self-similarity (strict, asymptotic, statistical etc.) have not been explored. Additionally, in terms of XML, the argument can be developed to the point of constructing Composites by nesting entity references recursively within other entities' replacement texts, although this would raise certain issues regarding processing.