Building program construction and verification tools from algebraic principles.
Saved in:
| Title: | Building program construction and verification tools from algebraic principles. |
|---|---|
| Authors: | Armstrong, Alasdair1, Gomes, Victor1, Struth, Georg1 g.struth@sheffield.ac.uk |
| Source: | Formal Aspects of Computing. Apr2016, Vol. 28 Issue 2, p265-293. 29p. |
| Subjects: | Imperative programming, Kleene algebra, Data flow computing, Semantic computing, Recursive functions |
| Abstract: | We present a principled modular approach to the development of construction and verification tools for imperative programs, in which the control flow and the data flow are cleanly separated. Our simplest verification tool uses Kleene algebra with tests for the control flow of while-programs and their standard relational semantics for the data flow. It is expanded to a basic program construction tool by adding an operation for the specification statement and one single axiom. To include recursive procedures, Kleene algebras with tests are expanded further to quantales with tests. In this more expressive setting, iteration and the specification statement can be defined explicitly and stronger program transformation rules can be derived. Programming our approach in the Isabelle/HOL interactive theorem prover yields simple lightweight mathematical components as well as program construction and verification tools that are correct by construction themselves. Verification condition generation and program construction rules are based on equational reasoning and supported by powerful Isabelle tactics and automated theorem proving. A number of examples shows our tools at work. [ABSTRACT FROM AUTHOR] |
| Copyright of Formal Aspects of Computing is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
