Towards a transformational approach to program verification

✍ Scribed by Myla Archer; Amy Lo; Ronald A. Olsson

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 182 KB
• Volume: 9
• Category: Article
• ISSN: 0960-0833
• DOI: 10.1002/(sici)1099-1689(199906)9:2<85::aid-stvr178>3.0.co;2-2

✦ Synopsis

Although most typically used in other contexts, program transformations can simplify program verification by transforming a program containing complex language features into a semantically equivalent program containing only simpler language features. The proof of the transformed program can then be performed using a set of proof rules for only the simpler features. There are tradeoffs between the transformational approach and the standard approach to program verification with regard to proof understandability and compactness of programs and assertions, establishing soundness of the program verification method, and providing mechanized support for the method. The transformational approach has clear advantages in some of these aspects. This paper illustrates this transformational approach by considering proof rules for escape statements in iterative constructs, and discusses the tradeoffs with respect to its use. It also suggests how the approach can be applied to other language constructs, including some involving concurrency, and to solving some problems connected with the development of Hoare axiomatizations.