Section 11.3. EXAMPLE: MIXIN LAYER COMPOSITION

11.3. EXAMPLE: MIXIN LAYER COMPOSITION

In this section, we give a concrete example of mixin layer composition [30] implemented as a compositional style in SPiccola (the Squeak implementation of Piccola [25]). Mixin layers are (in our view) a less well-known and non-trivial composition style. Implementing mixin layers requires an object-oriented language that supports nested classes and mixins. The language P++, for example, extends C++ to support static and type-safe mixin layer composition [29]. Implementing mixin layer composition in Piccola thus serves to validate that Piccola is expressive enough to tackle high-level composition abstractions. Finally, mixin layers are a good candidate to illustrate component algebras, because composed mixin layers are again mixin layers.

We present the graph traversal application proposed by Holland [10]. This application defines different operations on an undirected graph. VertexNumbering numbers the nodes in a depth-first order, CycleChecking determines whether the graph contains a cycle, and ConnectedRegions partitions the nodes of the graph into connected regions. Holland implemented the application based on a framework. Later, Van Hilst and coworkers [33] reimplemented it using roles and mixins. Smaragdakis and Batory finally used mixin layers to implement the same application [30, 31].

The three main implementation classes are Graph, Vertex, and Workspace. The Graph class defines a container of vertices with the usual graph properties. The nodes are stored as instances of the class Vertex. The Workspace class includes the specific part of a traversal. For instance, the workspace object plays the role WorkspaceNumber in the VertexNumbering application to associate numbers to the nodes. This role specifies a slot in which to store a current number and to assign and increment this number each time a new node is visited during depth-first traversal. We can implement such a role using a mixin. The mixin adds the specific members and operations to its superclass when composed. Similarly, a mixin adds the number slot to a vertex class.

Smaragdakis and Batory use the GenVoca model [9] to keep the different mixins applied to classes in synch. A GenVoca component is a mixin layer. In essence, a mixin layer encapsulates all the mixins necessary for a single collaboration. For instance, the mixin layer Number to implement the VertexNumbering collaboration contains two mixins: one to add the vertex numbering during traversal and one to add the number to a vertex. The advantages of using mixin layers instead of isolated mixins are clear: Design or change elements in the application are encapsulated and implemented in a single component.

11.3.1. Mixin Layers in Piccola

We now seek a simple way to model and compose mixins and mixin layers. We would like to achieve the kind of simplicity illustrated by the following example. graph provides constructors for graphs and vertices. We then compose it, using the ** mixin layer composition operator, with mixin layers dft, numberNodes, and cycle, which, respectively, provide services for depth-first traversal, automatic numbering of nodes, and cycle detection:

 layers = graph ** dft ** numberNodes ** cycle newGraph: layers.asGraph() asVertex: layers.asVertex() g = newGraph() ... 

We claim that the model of explicit namespaces offered by forms provides us with a good way of modeling compositional abstractions like mixin layers.

First of all, although Piccola provides only forms, not objects or classes, it is relatively simple to model objects and classes as forms. An object is just a form providing services that access some private state, such as the semaphores we saw earlier. A class is a form offering services shared by all instances, such as constructors, and services to create subclasses [6].

In our example, graph represents a base-level mixin layer, that is, one that provides services asGraph and asVertex to create new graphs and vertices. A graph itself provides services like insert and each to insert a new vertex or visit each vertex. The other mixin layers wrap the asGraph and asVertex of the layer below to create graphs and vertices with new or adapted services. In each case, it is important that the mixin layer simultaneously wrap both constructors since the new and adapted services typically depend on each other.

How do the mixin layers work? Let consider the numberNodes layer:

 numberNodes =   asVertex V:     V     number = newVar(0)   asGraph G:     G     visit:       n = newCounter()       G.each(do V: V.number.set(n.inc())) 

asVertex wraps a vertex to provide it with a number. asGraph wraps a graph to provide it with a visit service that increments the number of each of its vertices. These two services simultaneously wrap vertices and graphs from the layer below, so we are sure that when a vertex is visited, it actually provides a number binding.

Next, we need to implement a composition operator ** such that "A ** B" is a composite mixin layer, provided that A and B are mixin layers. We could implement a generic mixin layer composition operator in the style of our wrapPrePost service, but for simplicity we just consider the specific problem of composing graph mixin layers:

 'Defaults = (asVertex X:X, asGraph X: X) _**_ A B:   'A = (Defaults, A) # set defaults   'B = (Defaults, B)   asVertex X: B.asVertex(A.asVertex(X))   asGraph X: B.asGraph(A.asGraph(X)) 

The form Defaults contains default values for the asVertex and asGraph wrappers, namely the identity function. We rebind A and B so that the actual arguments may override these defaults. Finally, we compose new asVertex and asGraph wrappers from those provided by the arguments.

Note that the order in which the mixin layers are composed affects the end result. numberNodes, for example, depends on the each service provided by graphs of the layer below. The graph layer provides such a service, but the dft layer happens to replace this service by a depth-first traversal each service. As a consequence, graph**dft**numberNodes and graph**numberNodes**dft exhibit different behaviors.

11.3.2. Software Evolution with Mixin Layers

The resulting separation of concerns enables us now to combine or replace mixin layers in a straightforward way. Suppose, for example, that graphs may be exposed to concurrent clients. In this case, we might want to apply a synchronization policy to the graph. The mixin layer exclusive applies a mutual exclusion synchronization policy to all the methods of graph. Since the order of mixin layer composition is significant, we apply this layer last of all:

 layers = graph ** dft ** numberNodes ** cycle ** exclusive 

We can also change the depth-first traversal to a breadth-first traversal by replacing a component:

 layers = graph ** bft ** numberNodes ** cycle 

We can adapt a layer that (by chance) does not follow the naming conventions by introducing some glue code:

 myLayer =   asGraph = legacyLayer.addFancyFeatureToGraph   asVertex = legacyLayer.addFancyFeatureToNode 

In case there are many components that need to be adapted in the same way, we can abstract from the glue code to obtain a general-purpose glue abstraction:

 LegacyAdaptor legacyLayer:   asGraph = legacyLayer.addFancyFeatureToGraph   asVertex = legacyLayer.addFancyFeatureToNode myLayer = legacyAdaptor(myLegacyLayer) 

As a final validation of mixin layers, we found it straightforward to extend the graph traversal mixin layer framework with a new mixin layer for visualizing graphs.

The visual layer in Piccola packages the glue code needed to display graphs in Squeak:

 visual =   asGraph G:     G     'defaultColor = Smalltalk("Color").yellow()     morph = newVar(0)        ...     # replace G.each by an animated version     each Block:       ... 

This new mixin layer can now be added to any graph traversal mixin layer composition at the appropriate point.

In Figure 11-2, we see visualizations of thread-unsafe and thread-safe graphs that have been subjected to two concurrent traversals that mark and unmark the nodes (i.e., by changing their color).

Figure 11-2. graph()**dft**visual vs. graph()**sdft**visual.

The visualization clearly shows that only the thread-safe graph is uniformly colored at the end.