Burstall, Rod


Some techniques for proving correctness of programs which alter data structures

Classics

We will extend Floyd's proof system for flow diagrams to handle commands Which process lists. McCarthy and Painter (1967) deal with arrays by introducing'change' and'access' functions so as to write a[i]: a[j] 1 as a: change (a, i, access 24 BURSTALL King (1969) in mechanising Floyd's technique gives a method for such assignments which, however, introduces case analysis that sometimes becomes unwieldy. Let us recall briefly the technique of Floyd (1967) for proving correctness of programs in flow diagram form. We will here retain the inductive method of Floyd for dealing with flow diagrams containing loops, but give methods for coping with more complex kinds of assignment command.