WICSA 2005:SPQR
From WICSA Conference Wiki
Design patterns have been one of the more successful software innovations of the past decade, helping engineers produce high-quality software by describing a common language. They are, however, a one-way technology for all practical purposes. It has been highly difficult to find existing implementations of design patterns in source code, but doing so would be of great benefit to comprehending large systems, training of new engineers, and validation of design. Current and previous attempts at detecting design patterns have been based on the detection of source code constructs. Design patterns are not properly thought of as constructs however, but concepts. It is this mismatch that has been at the root of the lack of practical pattern detection.
The System for Pattern Query and Recognition (SPQR) is a research project that takes a different approach. By treating design patterns as the embodiment and encapsulation of concepts, not constructs, it becomes possible to treat object-oriented systems as a graph of related concepts of programming. Defining the mapping between the static constructs in source code and the flexible abstract concepts such that they can be reliably detected is a task with several distinct stages.
Analyzing the base literature of design patterns, namely the seminal Design Patterns text by Gamma et al., reveals many shared concepts between patterns that fulfill very different purposes. By deconstructing the established patterns into subpatterns, we can show well formed relationships between more fundamental concepts of programming. In taking this to its logical conclusion, I have established a set of Elemental Design Patterns (EDPs). These are binary relationships between elements found directly from source code: objects, methods, fields, and types. As such, they are immediately detectable from source code. The EDPs can be considered the DNA of programming, but from the viewpoint of concepts, not constructs.
Once we have these fundamental pieces of design patterns detected from source code, we need to be able to build them back into the higher level abstractions for which we are searching. An extension to the sigma-calculus of Abadi and Cardelli, which I have named rho-calculus, defines how these conceptual items can interrelate. The rho-calculus also defines these interrelationships as a series of reliances, formalized as reliance operators. The reliance operators are the description of how the EDPs can be integrated back into larger design patterns in well formed and precise ways. The addition of transitivity operations allows these integrations to be extremely flexible with respect to the original source code. The same concept can be written in a myriad of ways in source code, but the rho-calculus and EDPs capture them all through formal means.
These formalizations of EDPs and rho-calculus provide a unique opportunity, to use formal theorem proving techniques to deduce relationships of note within a system. These inferences can be performed using an automated theorem prover such as Otter from Argonne National Laboratories. Using our detected EDPs from a source code base, and the rho-calculus as inputs, we can query Otter about the existence of higher level patterns quickly and methodically. The results are considered potential patterns due to the currently highly conservative nature of SPQR. It is much quicker, however, for an engineer to double-check the existence of a pattern whose location is known, than to find it in the first place.
The results from SPQR can then be used to provide feedback to the architects of a system, establishing the presence (or absence) of patterns they intended to be implemented. It can also, perhaps more interestingly, find unintentional patterns, giving designers an opportunity to make hidden functionality more explicit in the design. To take this further, SPQR can be trained to detect any relationship of concepts that one wishes to find, leading to the possibility of finding pattern fragments. These last two features can be used as the inputs for a refactoring plan, and SPQR can then establish the validity of the final product.
The lingua franca of SPQR is the Pattern Object Markup Language (POML), an XML schema designed specifically to map the salient features of sigma- and rho-calculus into an easily parsed format. Currently, POML is used as the input and output format for SPQR, with a sequence of XSL transforms providing the translations between the necessary forms, including human-ready charts and reports. Other XSLTs have been created to quickly produce code metrics on any code base that has been reduced to a POML form. Because of this, source code written in any language that can be mapped to sigma-calculus can be analyzed in a simple and methodical manner.
SPQR was designed to be a practical toolset for engineers while providing a robust platform for future research. It has the necessary ease of use and flexibility that real world situations demand, but retains a rich formal basis. The choice of using an automated theorem prover has proven to be important, as it allows for deductive reasoning to be performed efficiently on large systems.
Here at WICSA/WCRE, I am looking forward to investigating the application of SPQR to the larger and more abstract patterns of software architecture.
