The University of Sussex

Improving software designs via the minimum description length principle

Joseph Arthur Wood

This thesis studies the creation of good quality, modular software designs. It focuses on architectural design, that is, the identification of components, their purpose, and interactions. This view of software architecture naturally leads to representing a design's structure as a graph. Complexity can be viewed along several dimensions including coupling and cohesion. Cohesion is the `togetherness' of a software component, and coupling is the `separateness' of software components. These two concepts have been studied for some time, and various definitions have been proposed. Indeed, both concepts have widely accepted ordinal measurement scales. However, a design must achieve a trade-off between these two concepts, and little has been written about how to achieve this trade-off. Complexity needs to be controlled in order to create understandable, maintainable and cost effective solutions. This thesis investigates design complexity at the architectural level, by applying Kolmogorov complexity to the graph's structure. To measure complexity, we use the Minimum Description Length principle; such that when a proposed design's structure is represented by a message, the length of this message is taken as a measure of the design's complexity. We show that this metric satisfies all of Weyuker's complexity properties. We propose that this model of complexity is an improvement over using disjoint and less precise measures of coupling and cohesion. Our metric captures information about the structure of a software design; it says nothing about ease of construction, maintenance or even satisfying the requirements. However, we suggest that ceteris paribus a simpler structure is preferred over a more complex structure, because it is cheaper and more reliable. A prototype tool, Morpheus, is described which manipulates a design's architecture, to produce a shorter representation, we suggest that this new design is simpler than the original. We demonstrate its use with a medium sized example in Hood notation.

Download compressed postscript file