Complexity Control in Logic-based Programming

There is growing awareness of the high risk and excessive cost of poor-quality software design. The problem is especially critical in complex programs where design errors are most frequently committed, and latent errors are particularly difficult to diagnose and correct.21 The origin of this ‘software crisis’ lies in the late realisation that there is much more to good software design than knowledge of a programming language. Structured programming and the various software design methodologies seek to control software quality by imposing a discipline on the designer which controls the complexity of design tasks and supplements the rules of the programming language. This paper outlines the process of evolving a complexity-controlling software design methodology, based on the general principles of sound engineering design, but devised particularly for logic-based programming. It reports on experience with the use of the methodology16, 27, 30, 5, 31 and compares the complexity properties of programs designed using different methods. An example is given to show how complexity control may also be achieved retrospectively, or in the course of software maintenance. The procedure is to measure the complexity parameters of a finished program, identifying its most complex parts; these are then reconstructed as hierarchical structures of simple autonomous components, while maintaining functional equivalence. Based on experience, the paper proposes further refinements of the well-tried complexity measures, suggesting the next stage of evolution of the complexity-controlling methodology for logic-based programming. Finally, the paper proposes areas for further research into complexity control and its applications to logic-based programming.