1 Introduction

Design patterns allow people to understand computer software in terms of stylized relationships between program entities: a pattern identifies the roles of the participating entities, the responsibilities of each participant, and the reasons for the connections between them. Patterns are valuable during the initial development of a system because they help software architects outline and plan the static and dynamic structure of software before the structure is implemented. Documented patterns are useful for subsequent system maintenance and evolution because they help maintainers understand the software implementation in terms of well-understood, abstract structuring concepts and goals.

The conventional approach to realizing patterns  [12] primarily uses classes and objects to implement participants and uses inheritance and object references to implement relationships between participants. The parts of patterns defined using classes and inheritance are static and therefore easier to understand and analyze. However, they are less flexible because their role in patterns and in the whole system is hardwired into their implementation. In contrast, parts of patterns that are defined using objects and references are more dynamic, and therefore more flexible but harder to understand and analyze.

This paper describes a complementary approach to realizing patterns based on separating the static parts of a pattern from the dynamic parts. The static participants and relationships in a pattern are realized by component instances and component interconnections that are set at compile- or link-time, while the dynamic participants continue to be realized by objects and object references. Expressing static pattern relationships as component interconnections provides more flexibility than the conventional approach while retaining much of the ease of understanding and analysis.

To illustrate the tradeoffs between these approaches, consider writing a network stack consisting of a TCP layer, an IP layer, an Ethernet layer, etc. The usual implementation strategy, used in mainstream operating systems, is for the implementation of each layer to directly refer to the layer above and below it except in cases where the demand for diversity is well-understood (e.g., to support different network interface cards). This approach commits to a particular network stack when the layers are being written, making it hard to change decisions later (e.g., adding low-level packet filtering in order to drop denial-of-service packets as early as possible).

An alternative implementation strategy is to implement the layers using the Decorator¹ pattern with objects: each layer is implemented by an object that invokes methods in objects directly above and below it. The objects implementing each layer provide exactly the same interface (e.g., methods for making and breaking connections, and for sending and receiving packets on connections) allowing the designer to build a large variety of network stacks. In fact, network stacks can be reconfigured at run-time, but that is more flexibility than most users require.

Our design and implementation approach offers a middle ground. Having identified the decorator pattern and having decided that the network stack may need to be reconfigured,but not at run-time, each decorator would be implemented as a component that imports an interface for sending and receiving packets and exports the same interface. The choice of network stack is then statically expressed by connecting different sets of components together. The basis of our approach is to permit system configuration and realization of design patterns at compile- and link-time (i.e., before software is deployed) rather than at init- and run-time (i.e., after it is deployed).

By matching the expected need for reconfiguration against the degree of abstraction, we achieve the following. (1) We are able to build a range of different network stacks meeting both our current and anticipated needs. (2) Network stacks are configured using a separate language that hides the implementation details of each component. This makes it possible for the system to be reconfigured at the component level. (3) We can statically detect configuration errors such as connecting a layer that expects IP packets to a layer that provides Ethernet packets. Such mistakes are most commonly made by non-domain experts but even domain experts can lose track of all the different architectural invariants in a complex system if the system is reconfigured enough times. (For example, Linux kernel developers plan to use the CML2 constraint language  [22] to prevent inconsistent kernel configurations from being built.) (4) The system is sufficiently constrained that it can be optimized effectively. Cornell’s Ensemble project  [16] shows how far one can go when statically optimizing stacks of network layers: they were able to double the performance of a 4-layer network stack. In the network stack example, the benefits come at some cost in flexibility: we have eliminated the ability to reconfigure the network stack at run-time. Our design strategy helps the programmer identify such trade-offs and consider how they affect the implementation.

Our contributions are as follows:

In summary, although the benefits of separating system architecture from component implementations are well-known, the distinctive features of this paper are: we show a general approach that can be applied to many patterns and in multiple language paradigms; we consider the static-dynamic decision in the context of design patterns; and we thoroughly evaluate when to apply and when not to apply our approach.

2 The Unit Model

Three separate implementations of the unit model exist: Knit  [23] for C, Jiazzi  [18] for Java, and MzScheme  [10] for Scheme. The implementations differ in details both because of technical differences in the base languages and because of stylistic differences in the way the base languages are used. For the purposes of this paper, we focus on the common features of the three implementations.

2.1 Atomic and Compound Units

An atomic unit can be thought of as a module with three parts: (1) a set of imports, which name the dependencies of the unit: i.e., the definitions that the unit requires; (2) a set of exports, which name the definitions that are provided by the unit and made available to other units; and (3) an implementation, which must include a definition for each export, and which may use any of the imports as required. Each import and export is a port with a well-defined interface. An interface has a name and serves to group related terms, much like an interface or abstract class in an OOP language. The three implementations of the unit model make different choices about what makes up an interface. In Knit, an interface refers to sets of related C types, function prototypes, and variable declarations. In Jiazzi, port interfaces are like Java packages: they describe partial class hierarchies and the public methods and fields of classes. In MzScheme, because Scheme uses run-time typing, interfaces are simply lists of function names.

Definitions that are not exported are inaccessible from outside the unit. The implementation of a unit is usually stored in a file separate from the unit definition, allowing code that was not intended for use as a unit to be packaged up as a unit.

Although all implementations of the unit model use a textual language to define units, in this paper we use a graphical notation to avoid inessential details and to emphasize the underlying structure of our systems. The smaller boxes in Figure 1 represent atomic units. The export interfaces are listed at the top of a unit, the import interfaces are listed at the bottom, and the name of the unit is shown in the center. Consider the topmost unit, called Draw. It has the ability to load, save, and render images, encapsulating the main parts of a simple image viewing program. Draw exports (i.e., implements) one port with interface I_Main and imports two ports: one with interface I_Widget and a second with interface I_File.

Units are instantiated and interconnected in compound units. Like atomic units, compound units have a set of imports and a set of exports that define connection points to other units. The implementation of a compound unit consists of a set of unit instances and explicit interconnections between ports on these instances and the imports and exports of the compound unit. The result of composing units is a new unit, which is available for further linking.

Figure 1 as a whole represents a compound unit composed of three other units. In this figure, an instance of Draw is composed with an instance of Win32_Widgets and an instance of Win32_Files. Within a compound unit, connections are defined explicitly: this is necessary when there is more that one way to connect the units. Although not shown in this example, a system designer may freely create multiple unit instances from a single unit definition (e.g., two instances of Draw).

2.2 Exploiting Static Configuration

One of the key properties of programming with the unit component model is that component instantiation and interconnection are performed when the program is built instead of when the program is executed. This allows implementations of the unit model to make use of additional resources that may be available at compile- and link-time: powerful analysis and optimization techniques; in the case of embedded systems, orders of magnitude more cycles and memory with which to perform analyses; test cases, test scaffolding, and debugging builds; and finally, freedom from real-world constraints such as real-time deadlines. All three unit implementations check the component composition for type errors. Knit, however, implements additional features that exploit the static nature of unit compositions.

Constraint checking. Even if every link in a unit composition is “correct” according to local constraints such as type safety, the system as a whole may be incorrect because it does not meet global constraints. For example,  [23] describes a design constraint used by operating system designers: “bottom-half code,” executed by interrupt handlers, must not invoke “top-half code” that executes in the context of a particular process. The reason is that while top-half code typically blocks when a resource is temporarily unavailable, storing its state in the process’s stack, an interrupt handler lacks a process context and therefore must not block. The problem with enforcing this constraint is that units containing bottom-half code (e.g., device drivers) may invoke code from other units that, transitively, invokes a top-half unit. Keeping track of such conditions is difficult, especially when working with low-level systems code that is highly interconnected and not strictly layered. To address this problem, Knit unit definitions can include constraint annotations that describe the properties of imports and exports. Constraints can be declared explicitly (e.g., that imported functions are invoked by bottom-half code) or by description (e.g., that the import properties are set by the exports). At system build-time, Knit propagates unit properties in order to ensure that all constraints are satisfied.

Cross-component inlining. When source is available, Knit inlines function definitions across component boundaries with the help of the C compiler. By eliminating most of the overhead associated with componentization, Knit reduces the need to choose between a clean design and a fast implementation.

2.3 Using Units Without Language Support

The unit model makes it possible for a software architect to design a system from components, describe local and global relationships between components, and reuse components both within and across system designs. These are the features that make it useful to develop and apply units for expressing design patterns. In particular, our unit-based approach to realizing patterns relies on these features of the unit model:

It is possible to make use of features of the unit component model without support from languages such as Knit, Jiazzi, and MzScheme. However, without support, some benefits of the model may be lost. For instance, a C++ programmer might use template classes to describe units: this can provide optimization benefits but does not help the system designer check constraints of the sort described previously. A C programmer might use the C preprocessor to achieve similar results. In sum, although unit tools can provide important benefits, people who cannot or decide not to use our unit description languages can nevertheless take advantage of our general approach to realizing design patterns.

3 Expressing Patterns with Units

The key idea of this paper is that it is both possible and fruitful to separate static knowledge about a pattern application from dynamic knowledge. In particular, we believe that static information should be “lifted out” of the ordinary source code of the system, and should be represented at the level of unit definitions and connections. The unit model allows a system architect to describe the static properties of a system in a clear manner, and to separate “configuration concerns” from the base implementations of the system’s parts.

Consider, for example, an application of the Decorator pattern: this pattern allows a designer to add additional responsibilities to an entity (e.g., component or object) in a way that is transparent to the clients of that entity. One might apply Decorator to protect a non-thread-safe singleton component with a mutual exclusion decorator (which acquires a lock on entering a component and releases the lock on exit) when using the component in a multi-threaded environment. In an object-oriented setting this pattern would often be realized by defining three classes: one abstract class to define the component interface, and two derived classes corresponding to the concrete component and decorator. At init-time, the program would create instances of each concrete class and establish the appropriate object connections. While workable, this implementation of the pattern can disguise valuable information about the static properties of this system. First, it hides the fact that there will be only one instance each of the component and decorator. Second and more important, it hides the design constraint that the base component must be accessed only through the decorator: because the realization of the pattern doesn’t enforce the constraint, future changes to the program may violate the rule.

(a) Decorator (b) Strategized Decorator Figure 2: Units realizing Decorator patterns

To overcome these problems, we would realize the Decorator pattern at the level of units, as illustrated in Figure 2(a). We create one unit definition to encapsulate the base component definition; by instantiating this definition exactly once, we make it clear that there will be only one instance in the final program. Further, we annotate the unit definition with the constraint that the implementation is non-thread-safe. We then create a separate unit definition to encapsulate our decorator, and include in the definition a specification that it imports a non-thread-safe interface and exports a thread-safe one. The resulting structure in Figure 2(a) makes it clear that there is one instance of each participant and that there is no access to the base component except through the decorator. Units make the static structure of the system clear, and unit compositions can be checked by tools to enforce design constraints. Of course, unit definitions are reusable between systems (and within a single system): we can include the decorator instances only as needed. If we desire greater reuse, we can apply the Strategy pattern to our decorator to separate its wrapping and locking aspects as shown in Figure 2(b). This structure provides greater flexibility while still allowing for cross-component reasoning and optimization when the strategy is statically known.

In sum, our approach to realizing patterns promotes the benefits of static knowledge within patterns by moving such information to the level of units. The unit model allows us to describe and separate the static and dynamic properties of a particular pattern application, thus making it possible for us to exploit the features described in Section 2.2. In the rest of this section we define a method for applying our approach, demonstrate the method in detail on a small example, demonstrate the effect of our method on a large example, and consider how the method applies to each of the patterns in Gamma et al.’s Design Patterns catalog  [12].

3.1 A Method for Expressing Patterns with Units

We have found the following general procedure to be useful in analyzing the application of a pattern and translating that pattern into unit definitions, instances, and linkages. Because patterns are ordinarily described in terms of object-oriented structures (classes, interfaces, and inheritance), we describe our method as a translation from object-oriented concepts to parts of the unit model.

3.2 Example: Managing Block Devices

As an initial example, consider the problem of managing block I/O device drivers, which provide low-level access to block-oriented storage media such as disks and tapes. An operating system is generally configured at build-time to include one device driver for each kind of supported block device: e.g., IDE bus, SCSI bus, and floppy disk drive. At run-time, the operating system queries each driver for information (e.g., the type and capabilities of the driver): the driver discovers the physical devices that it manages, and at the request of the OS, creates run-time objects to represent each of these devices. To make it easy to configure OSKit-based systems with different sets of block device drivers, we apply the Abstract Factory pattern as illustrated in Figure 3. In OOP terms, we define a common abstract class (BlockDevice) to be supported by all block devices, and we define abstract classes (BlkIO and DriverInfo) for the products that each driver may produce. The actual drivers and products map to concrete classes as shown.

Having identified the pattern at hand, we can now apply the steps of our method to translate the pattern structure into appropriate unit definitions. First (step 1) we identify the abstract classes: clearly, these are BlockDevice, BlkIO, and DriverInfo. Next (step 2): because each device driver can manage multiple physical devices, we need at most one instance of each driver in any system we might build. (We need zero or one, depending on whether or not we choose to support a particular kind of device.) Thus, each of our concrete factories is a static participant. In contrast, since wedo not know the number of physical devices that will be present at run-time, each concrete product class is a dynamic participant.

We now define the interfaces for our static participants (step 3). The interface to each concrete factory class is defined by the abstract BlockDevice class: we therefore define a corresponding I_BlockDevice interface. As described in Section 3.1, we translate the BlockDevice methods into ordinary C functions, because we do not need to represent our static participants as run-time objects.

In defining the interfaces for our dynamic participants (step 4), we need to translate the participant’s methods in a way that allows us to identify instances at run-time. Because we are using Knit, we translate the BlkIO and DriverInfo classes into unit port interfaces that include C types for the products. In addition, each product method becomes a C function that takes a run-time instance.

Next (step 5) we create the unit definitions for each of our concrete participants. This is a straightforward mapping from the pattern structure: the exports of each unit are determined by the provided interfaces (i.e., the participants’ classes), and the imports are determined by the connections in the pattern structure.

Finally, we create a compound unit in which we instantiate the units that we need, and connect those instances according to the pattern (step 6). For example, to create a system with just IDE support, we would define the unit instances and links shown in Figure 4. The unit definitions that we created in steps 1-5 are reusable for many systems, but the structure of the final unit composition in step 6 is often specific to a particular system configuration.

Our method describes the process of creating appropriate unit definitions, but it does not address the problem of unit implementation: i.e., the source code. We have found, however, that appropriate implementation is often straightforward. In the example above, the OSKit units are implemented by existing OS device drivers with little or no modification. Most changes, if needed at all, can be implemented by Adapter units that wrap the existing code. Further, the device-specific code can be isolated in the units that define our products. This means that we can write one unit definition for our factory instead of one each for IDE, SCSI, and Floppy. Each instance of this factory imports the units that define a related family of products. Knit’s constraint system can be used to statically ensure that the system designer does not accidentally connect a mismatched set of products.

3.3 Example: OSKit Filesystems

Having illustrated the method in detail in the previous section, we now show the result of applying the method to a more complex example. Figure 5 shows one possible configuration of a filesystem in the OSKit. The primary parts of the system are: Main, an application that reads and writes files; FS Namespace, which implements filepaths (like /usr/bin/latex) on top of the more primitive file and directory abstraction; Ext2FS, a filesystem from the Linux kernel distribution; and Linux IDE, a Linux device driver for IDE disks. The other units in the system connect these primary parts according to the Abstract Factory, Adapter, Decorator, Strategy, Command, and Singleton patterns. All participants in these patterns are currently implemented as described with one exception (Command) described below.

Abstract Factory. Figure 5 contains two abstract factories: the Linux IDE and OSEnv/x86 units. (In both cases, only the enclosing compound unit is shown.) The OSKit defines an interface (called the “OS Environment Interface”) for all components to use when manipulating interrupts, setting timers, allocating memory, and so on. This interface abstracts the more obtrusive details of the underlying platform. In Figure 5, this interface is implemented by OSEnv/x86 for the Intel x86 hardware but we could have chosen OSEnv/StrongARM for the StrongARM architecture or OSEnv/Linux to run as a user-mode Linux program. (The latter choice would necessitate a different choice of device driver.) It is appropriate to fix on a particular platform at this stage because moving to another would require the system to be rebuilt.

Adapter. The hybrid nature of the OSKit gives rise to many adapters. The OSEnvLinux adapter implements Linux internal interfaces in terms of the OSKit-standard I_OSEnv, allowing us to include Linux-derived units in the system. The LinuxFSFS and LinuxBlkDev adapters implement standard OSKit interfaces for filesystems and block devices using the internal Linux interfaces for these things. Being able to use Linux-derived units is extremely useful for OSKit systems: instead of writing and maintaining new filesystems and device drivers, the OSKit exploits the hard work of the Linux community. The OSKit uses this approach to provide 30 Ethernet drivers, 23 SCSI drivers, and 11 filesystems.

An interesting part of the LinuxFSFS and LinuxBlkDev adapters is that they have both static and dynamic aspects. The static aspect adapts the static interfaces of the participants: those used for initialization, finalization, and mounting a filesystem on a disk partition. The dynamic aspect adapts the interfaces of dynamic participants, wrapping Linux block device objects as OSKit block device objects, Linux filesystem objects as OSKit filesystem objects, and Linux file and directory objects as their OSKit equivalents. This illustrates how our approach complements the conventional approach: our units make it apparent which decisions are static (e.g., the decision to use Linux components with OSKit components) and which are dynamic (e.g., how many files will be opened, which files will be opened).

Decorator. If this is a multi-threaded system, we must take care to acquire and release locks when accessing the filesystem and device driver objects. The decorators Lock Filesys and Lock BlockDevice acquire locks when entering the decorated objects and release locks when leaving.

It would be a serious error to omit one of these lock decorators (leading to race conditions) or to insert it in the wrong place (leading to deadlock), so we use the constraint system to check that they are placed correctly. This may seem like overkill in such a simple configuration, but the reader will appreciate that this is just one of many rules that must be enforced and that we have omitted many units that would appear in a complete system. The complete system—including units for bootstrapping, console I/O, memory allocation, threads and locks, etc.—consists of over 100 unit instances.

Strategy. Disk drivers can optimize disk operations by coalescing reads and writes on adjacent blocks and can optimize disk seeks by reordering read and write requests. The series of actual requests issued to the disk is determined by a strategy unit. In Figure 5, we have selected the Simple Disk Strategy unit (which queues requests in the order they are issued) but we could have chosen a strategy that coalesces disk operations or reorders requests using an elevator algorithm. (The elevator strategy is not yet implemented.)

Command. The Simple Disk Strategy unit manipulates a list of outstanding requests, and these requests are parts of a Command pattern. The participants in this pattern are currently integrated within the implementation of the Simple Disk Strategy unit, but could be separated as shown in Figure 5 into a separate unit Encode BlockOp which provides a separate function for each kind of request (e.g., read or write). This unit would construct request objects and pass them to Simple Disk Strategy, which would process the requests.

Singleton. In this system, we made a design decision to have a single device and a single filesystem instance. One could imagine using a device driver implementation that supports just one instance of that device type or a filesystem implementation that supports just one instance of that filesystem type. But this is not what Linux components do. Most Linux device drivers and filesystems are written to support multiple instances of a device or filesystem. To overcome this mismatch, we use the BlkDev Instance and FS Instance units that each create and manage a single instance of the corresponding dynamic objects. These units are effectively adapters, making dynamic pattern participants appear as if they were static.

3.4 Discussion

Although the static and dynamic parts of many patterns will vary from situation to situation in general, in common use, most pattern structures contain many participants and connections that are in fact static: these parts can be fruitfully lifted out of the participants’ source implementations and then managed at the level of units. To test this claim, we analyzed the structures of all of the patterns described in Gamma et al.’s Design Patterns catalog  [12]. For each, we considered common uses of the pattern in the domain of OSKit-based systems (i.e., component-based systems software). We then applied our method to translate the pattern structures into appropriate units and unit parts.

Table 1 summarizes the results of our study. Each row of the table shows the translation of the participants within a single pattern, according to their application in the OSKit. Overall, the table shows that most participants frequently correspond to static, design-time information and are therefore realizable within our unit model as design-time entities. (These are the columns under the “Design-Time/Static Participants” heading.) Abstract classes map naturally to unit interfaces. Participants that are singletons within the context of a pattern map naturally to unit instances that implement these participants. In some cases, a participant both defines an interface and represents a concrete instance, as indicated in the table. For example, in the Facade pattern, the Facade entity has both interface and implementation roles. In some cases, the designer may choose to implement a particular participant in more than one way: for instance, the designer may choose to implement a Client participant as a unit instance, or as a set of ports that allow the client to be connected at a later stage of the overall design. In other cases, the appropriate implementation of one participant depends on the characteristics of another: in the Decorator pattern, for example, the appropriate realizations of Decorator and Concrete Decorator differ according to the “singleton-ness” of the Concrete Component. Where the common translation or use varies, we have indicated this with italics, and we list the participant in multiple categories.

In summary, Table 1 shows that our approach to realizing patterns is applicable to many patterns: most have common applications in which many or all of the participants represent static system design knowledge that can be utilized by tools for design rule checking, code generation, and system optimization. This applies even when a participant is dynamic and is realized by a unit that produces objects at run-time. In these cases, we can use our unit model to define our run-time classes/types in terms of mixins, thus increasing the potential reuse of our unit definitions and implementations.

4 Analysis

The key feature of our approach is that we express static pattern relationships in a component configuration language instead of expressing those relationships in the component implementation language. In this section, we detail the benefits and costs of this separation of concerns.

4.1 Benefits of Our Approach

Our technique for realizing patterns has three main consequences. First, because static pattern information is located in single place (our compound units) and because component interconnections are fully resolved at build-time, it is possible for tools to perform a more thorough analysis of the software architecture than in the conventional approach to realizing patterns. Second, because the unit language has a single purpose—to express components, their instantiations, and their interconnections—it is possible to provide features in the language that make this task easier. Third, because the task of pattern composition is moved out of the implementations of the participants, those implementations can be simpler and are less likely to be hard-wired to function only in fixed pattern roles. These three consequences lead to benefits in the areas of error detection, performance, and ease of understanding and reuse, which we explore in the following sections.

4.1.1 Checking Architectural Constraints

In the conventional approach to realizing design patterns, it can be difficult to enforce static system design constraints: the rules are encoded “implicitly” in the implementation, making them difficult for people to find and for tools to enforce in the face of future system evolution. Our approach to realizing patterns has the following advantages over the conventional method.

The constraint checker detects global, high-level errors. The constraint checker within the Knit unit compiler can detect “global” errors that involve many parts of a system, whereas a conventional language type system is restricted to detecting relatively local errors. Such global constraints often deal with high-level system composition issues—e.g., ensuring that domain-specific properties hold across many interconnected components—whereas conventional type systems and tools are restricted to detecting relatively low-level and general types of errors such as uncaught exceptions  [1], dereferenced null pointers  [6], and race conditions  [8].

Constraints express domain-specific design rules. As just mentioned, a software architect is often interested in detecting domain-specific errors. For example, recent versions of RTLinux  [26] permit normal (user-level) application code to be called from a hard real-time kernel. Without going into detail, an essential requirement of such applications is that they never invoke a system call while running in real-time mode. We have used Knit’s constraint system to check this constraint for RTLinux applications: i.e., to verify, at compile-time, that there are no paths from an application’s real-time signal handler into the Linux kernel.

Design errors are separated from implementation errors. In particular, this reduces the level of expertise required in order to use (or reuse) a component correctly, inside or outside of a pattern.

The constraint checker need not deal with the base implementation language. Our constraint checker deals only with the unit specification language, not with the source code of the components. Because the unit language is simple, the constraint checker is simple and precise. Further, it would be easy to extend with more powerful and perhaps more pattern-specific reasoning methods in the future. In contrast,to detect design errors in a conventionally realized design pattern, a tool would need to deal with all the complexities of the base implementation language: loops, recursion, exceptions, typecasts, virtual functions, pointers, and so on. Such a tool is therefore difficult to create—greatly raising the barrier to developing domain-specific analyses—and is often imprecise.

Many architecture description languages can provide the advantages described above: like our tools, they achieve this by separating the description of the architecture from the implementation of the components, and by being domain-specific instead of general-purpose. Bringing these features to bear on the realization of design patterns is one of the strengths of our tools and approach.

4.1.2 Performance Optimization

Another strength of our approach is that static pattern knowledge is readily available for system optimization. The conventional approach to realizing patterns uses language features that introduce indirections to achieve greater flexibility. These indirections—principally indirect function calls—impose a performance penalty that can often be avoided in our approach.

Static implementation enables many optimizations. When component instances are connected statically, indirect function calls are often turned into direct calls. This affords the compiler the opportunity to inline function calls, thus eliminating overhead and exposing additional and often more significant opportunities for optimization, especially those that specialize a function for a particular context. In addition, highly optimizing compilers, or compilers aided by a source transformation that Knit can perform, are able to inline functions across module boundaries. In previous work  [23], we used Knit to implement a network router made of very small components. (Each packet traversed 10-20 components while being forwarded.) Applying cross-component inlining eliminated the cost of many function calls but, more significantly, enabled the C compiler to apply all of its intra-procedural optimizations. The overall effect of this optimization was to reduce the execution time of the routing components by 35%.

Static implementation makes performance less sensitive to code changes. To eliminate virtual function calls, a compiler relies on a global (or near global) analysis of the program being optimized. These analyses are necessarily affected by subtle features of how the program is expressed: a consequence is that any change to that program could potentially change the analysis result and therefore change whether or not the optimization can be applied. In a performance-sensitive situation (e.g., in real-time code), loss of an optimization may affect program correctness. By making static knowledge explicit, our approach to patterns helps to reduce the complexity of the resulting system, thus promoting compile-time analysis and making “global” performance less sensitive to local code changes.

4.1.3 Ease of Understanding and Code Reuse

In the conventional approach to realizing design patterns, one takes into account the role of each participant when implementing the participant—or, if the pattern is applied after implementation, one modifies the participant to reflect their roles in the pattern. In our approach, because units do not contain direct references to other participants, units often need no modification in order to be used in a particular role in a pattern. Avoiding even small changes to the participants leads to significant benefits.

The approach is usable when code cannot be changed. The implementation of a participant may be unchangeable if the code has multiple users with different needs, if the source code is not available, or if the code is being actively maintained by a separate organization. For instance, the developers of the OSKit cannot practically afford to change the Linux components that they incorporate: they must deal with the code as it is written.

A participant can be used in multiple patterns. Separating a participant’s role from its implementation is beneficial when the implementation can be “reused” to serve in many different roles, perhaps concurrently in several different patterns. The unit model allows a programmer to separate a participant’s primary implementation from any code needed to adapt that implementation to a particular pattern role: by creating a unit composition, a programmer can “weave” code at the imports and exports of a participant unit instance.

Code is not obfuscated with indirections. The conventional realization of a design pattern often achieves flexibility by introducing additional levels of indirection that are apparent in the implementations of the participants. This indirection can obscure the primary purpose of the code. For example, before applying the unit model to the OSKit, we relied on objects, factories, and registries to enable reconfiguration. Over time, much OSKit code came to look like the following:

The code was often further complicated to deal with run-time errors. In any particular system, however, the values of clientos and fsn were fixed in the system configuration, and knowable at compile-time. After applying our approach, such code could often be simplified to just:

making it clear that the selection of lookup_path’s implementation is a static, not dynamic, system property.

4.2 Costs of Our Approach

Our approach to realizing design patterns is not appropriate for all situations and design problems. The following paragraphs summarize the costs and potential problems of our approach.

Our approach only specifies the static parts of patterns. The main goal of our approach is to use an external component language to specify the static aspects of a system architecture. It is inappropriate (and often infeasible) to use our approach to specify fundamentally dynamic elements of software architecture.

Our approach commits code to being static or dynamic. One can imagine that having carefully used our approach (with its emphasis on static participants and relationships) to realize a pattern, a change of requirements might turn a relationship from static to dynamic, requiring that the pattern be re-implemented using the conventional object-oriented approach (with its emphasis on dynamic participants and relationships). This is a problem: while it is easy to use a dynamic system in a static situation, it is not so easy to use a static system in a dynamic way. Therefore, when using our approach, one should design systems in such a way that expected changes in the system requirements are unlikely to require changing the static and dynamic natures of pattern participants—but we recognize that this is not always possible.

Our approach requires support for the unit component model. To fully benefit from our approach, one needs language support in the form of an advanced module or component system and, ideally, a constraint checking system. This implies several costs: one must switch to using new tools, learn the component definition and linking language, learn to use the constraint checking language, and convert existing codebases to use the component language. This can be a significant undertaking. As described in Section 2, however, it is possible to use existing tools and techniques to achieve some (but not all) of the benefits of the unit component model.

Our approach can obscure the differences between patterns. When one looks at the unit diagrams of participants and relationships, it is clear that sometimes, different patterns look the same when realized in our approach. However, this observation is also true of the conventional approach to realizing patterns: many patterns are realized in similar ways but differ significantly in their purpose.

5 Related Work

Gamma et al.’s Design Patterns book  [12] triggered a flurry of papers on implementing patterns in object-oriented languages. Here, we consider representatives of particular styles of implementation. Bosch  [3] describes a language LayOM for constructing C++ classes by adding a number of layers to a simple class. By using layers corresponding to particular patterns, Bosch solves the traceability problem—that it is hard to find and identify patterns in one’s code—and enables pattern implementations to be reused. However, because the layers form part of the class description, the role of each pattern participant is hardwired and the participants cannot be used in other patterns without being modified. Bosch makes no mention of static analysis, detecting design errors, or optimization. Marcos et al.  [17] describe an approach that is closer to ours: the code that implements participants is clearly separated from the code that defines their roles in patterns. The difference is that their approach is based on run-time reflection within a metaprogramming system (CLOS), and so they do not support static analysis or optimization. Tatsubori and Chiba  [25] describe a similar approach to that of Marcos et al., except that it uses OpenJava’s compile-time metaprogramming features. Like Marcos et al., they separate roles from participants and, because they use compile-time metaprogramming, it should be possible to perform static analysis. However, OpenJava does not provide anything like Knit’s unit constraint system.

Krishnamurthi et al.  [15] describe an approach to pattern implementation based on McMicMac, an advanced macro system for Scheme. Their approach is like that of Tatsubi and Chiba: patterns are expanded statically (enabling optimization) and the application of patterns is not separated from the definitions of the participants. Unlike OpenJava, McMicMac provides source-correlation and expansion-tracking facilities that allow errors to be reported in terms of the code that users wrote instead of its expansion, but there is no overall framework for detecting global design errors.

Baumgartner et al.  [2] discuss the influence of language features on the implementation of design patterns. Like us, they note that Gamma et al.’s pattern descriptions  [12] would be very different in a language that directly supports abstract interfaces and a module mechanism separate from class hierarchies. Baumgartner also lists a number of other useful features including mixins and multimethods. MultiJava  [5] adds some of these features to Java, enabling them to cleanly support the Visitor pattern and to describe “open classes.” Our colleagues’ paper on Jiazzi  [18] shows how the open class pattern can be realized with units. Bruce et al.  [4] describe virtual types and show how they apply to the Observer pattern. All of these papers describe language features that address problems in implementing patterns in object-oriented languages, but their focus is on the technology, not the approach enabled by that technology.

At the other end of the spectrum, there are component programming models, module interconnection languages (MILs)  [21], and architecture description languages (ADLs)  [19]. Our implementations of the unit model lie at the intersection of these three approaches. Units are like COM or CORBA components except that units play a more static role in software design; units are like MILs in that each implementation of the unit model supports just one kind of unit interconnection; and units are like ADLs in that units support static reasoning about system design.

Module interconnection languages are perhaps closest in purpose to the unit model. The best example we know of using a MIL in the way this paper suggests is FoxNet  [14], a network stack that exploits ML’s powerful module language. However, although FoxNet clearly uses a number of patterns, there is no explicit statement of this fact and consequently no discussion of implementing a broad range of patterns using a MIL.

Architecture description languages provide a similar but higher-level view of the system architecture to MILs. This higher-level view is the key difference. ADLs describe software designs in terms of architectural features, which may include patterns. ADLs may also provide implementations of these features: the details of implementation need not concern the user. In contrast, this paper is all about those implementation issues: we describe a method that ADL implementors could apply when adding new patterns to the set provided by their ADL. That said, ADLs provide more expressive languages for describing design rules, specifying components, and reasoning about system design than is currently supported by the unit model. We plan to incorporate more high-level ADL features into our unit languages in the future.

6 Conclusion

Design patterns can be realized in many ways: although they are often described in object-oriented terms, a pattern need not always be realized in an OOP language nor always with objects and interconnections created at run-time. In this paper we have presented a complementary realization of design patterns, in which patterns are statically specified in terms of the unit model of components. While this approach is not applicable to all software architectures, it can yield benefits when applied to static systems, and to static aspects of dynamic systems. These benefits include verification of architectural constraints on component compositions, and increased opportunities for optimization between components.

7 Acknowledgments

We thank Mike Hibler for his expert help with the OSKit, and Sean McDirmid for many fruitful discussions about the unit model and design patterns. Matthew Flatt, Jason Baker, David Coppit, and Joe Loyall provided valuable comments on drafts of this paper.

This research was supported by the Defense Advanced Research Projects Agency and the Air Force Research Laboratory, under agreement number F33615-00-C-1696. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation hereon.

8 REFERENCES