Automated Design Pattern Detection

The System for Pattern Query and Recognition, or SPQR, is a practical approach to the automated detection of instances of known design patterns directly from source code.  It uses a novel approach, mating a formal semantics of reliances and hierarchical decomposition of software design concepts, then using an inference engine to efficiently traverse the search space.

In a nutshell, source code (from nearly any object-oriented language) is translated into rho-calculus, a relationship-based denotational semantics that I created by extending Abadi & Cardelli’s sigma-calculus.  This formal notation provides a tremendous flexibility in the expression of the reliances between elements of programming and software design.  By distilling the fundamental relationships to a few orthogonal axes of design issues, rho-calculus provides complete conceptual coverage of programming.  Anything that can be created in the OO language of your choice, can be expressed in rho-calculus.

Building off of this, I explored this design space defined by rho-calculus, and developed a suite of the smallest design patterns, the Elemental Design Patterns, that use these axes to describe the most basic building blocks of software design.  The EDP catalog is a well-formed and rich taxonomy of the elements of design and implementation that we all use every day as programmers, made explicit and described in an incremental way.  I am very interested in testing their effectiveness in a teaching environment, as a way of introduced students to the methodologies of good software design from the very beginning of their education, instead of as an afterthought.

The real power of the EDPs comes through when they are used to hierarchically define the more common and interesting design patterns from industry and literature.  In just a few steps, higher-level abstractions such as Decorator or Abstract Factory can be defined in a formal manner that does not lose any of their flexibility or expressiveness, avoiding one of the major failings of most pattern formalization techniques.  This is due to the inherent transitivities in rho-calculus interacting with the discrete design space of EDPs through a technique I have termed isotopes.

Combining the above, the formal representation of the software system under analysis is fed into an inference engine as a series of facts, with the rules of rho-calculus as the guide for the inferences.  The formal definitions of the EDPs can then be rapidly queried for, to prove or disprove their existence, creating additional facts for the inference engine.  Larger patterns are found by simply finding their decompositional components and allowing the isotopic principles to handle the inherent necessary permutations of implementation in a software system.  The process is fast, reliable, and practical.

Using SPQR, software can be documented, understood, and the complexity managed.