Evolvable Behavior Specifications Using Context-Sensitive Wildcards

The development and maintenance of today's software systems is an increasingly effort-consuming and error-prone task. A major cause of the effort and errors is the lack of human-readable and formal documentation of software design. In practice, software design is often informally documented, or not documented at all. Therefore, (a) the design cannot be properly communicated between software engineers, (b) it cannot be automatically analyzed for finding and removing faults, (c) the conformance of an implementation to the design cannot be automatically verified, and (d) source code maintenance tasks have to be manually performed, although some of these tasks can be automated using formal documentation. In this thesis, we address these problems for the design and documentation of the behavior implemented in procedural programs. We present the following solutions each addressing the respective problem stated above: (a) A graphical language called VisuaL, which enables engineers to specify constraints on the possible sequences of function calls from a given procedural program, (b) an algorithm called CheckDesign, which automatically verifies the consistency between multiple specifications written in VisuaL, (c) an algorithm called CheckSource, which automatically verifies the consistency between a given implementation and a corresponding specification written in VisuaL, and (d) an algorithm called TransformSource, which uses VisuaL specifications for automatically inserting additional source code at well-defined locations in existing source code. Empirical evidence indicates that CheckSource is beneficial during some of the typical control-flow maintenance tasks: 60% effort reduction, and prevention of one error per 250 lines of source code. These results are statistically significant at the level 0,05. Moreover, the combination of CheckSource and TransformSource is beneficial during some of the typical control-flow maintenance tasks: 75% effort reduction, and prevention of one error per 140 lines of source code. These results are statistically significant at the level 0,01. The main contribution of this thesis is the graphical language VisuaL with its formal underpinning Deterministic Abstract Recognizers (DARs), which defines a new family of formal languages called Open Regular Languages (ORLs). The key feature of VisuaL is the context-sensitive wildcard, which makes VisuaL specifications more evolvable (i.e. less susceptible to changes), and more concise.