Design and analysis of multidimensional program structures

Software design is an art. More often than not, designers rely on craftsmanship and creativity for designing software products. Just as understanding of the structure of atomic elements is critical to the natural sciences, it too is fundamental to the science behind software engineering. Structural theories simplify our understanding of a convoluted mechanism and allow us to reason in a clear and concise manner. Therefore, decision making can transcend subjective justification and move to quantitative and precise reasoning. Feature-Oriented Programming and compositional programming embody ideas of software decomposition structure. Feature-Oriented Programming treats Features as the building-blocks that are composed to synthesize programs. Its convergence with algebraic transformations has led to AHEAD - a simple algebraic model of Feature-Oriented Programming. Within AHEAD, reasoning over simple algebraic structures enables codification and mechanization of well-understood principles. In this thesis we demonstrate just that by showing that critical properties of a decomposition can be identified and verified efficiently. First, we introduce multidimensional structures, a higher-order structural relationship within conventional decomposition. Multidimensional structures simplify a complex decomposition’s representation, understanding, and compositional specification. However, not all decompositions are fit for a multidimensional arrangement. We identify an essential property of orthogonality that a decomposition and its implementation must satisfy in order to warrant a multidimensional structure. Next, we identify a class of errors that occur at module composition-time. These composition errors are a result of unsatisfied dependencies when feature modules are composed in arbitrary arrangements. AHEAD introduces architectural-level domain constraints that govern the compatibility of feature modules. Besides architectural-level composition constraints, there are also low-level implementation constraints: a feature module can reference classes that are defined in other feature modules. Safe composition is the guarantee that programs composed from feature modules are absent of references to undefined classes, methods, and variables. We show how safe composition can be guaranteed for AHEAD product lines using feature models and SAT solvers. The significance of this work lies in the generality of our approach. Multidimensional structures are not unique to AHEAD; we demonstrate its applicability under any form of decomposition. Likewise, safe composition also extends AHEAD. We draw an analogy between safe composition and C++ linking errors. Moreover, we demonstrate how non-code artifacts benefit from modularization as well as safe composition analysis. In identifying and verifying key properties, we have also demonstrated how the structural model of AHEAD can simplify our understanding and applicability of essential principles. When the fundamental structure is well-understood, software design is amenable to automation.