Teaching Formal Methods: Practice and Experience (TFM)
Teaching Formal Methods: Practice and Experience
15 December 2006
There are a few standard approaches to constructing verified programs. The original approach, by Floyd, Naur and Hoare, assumes that the program code is given, together with an informal description of what the program is supposed to do. Program verification amounts to expressing the requirements as precise pre- and postconditions, finding the appropriate loop invariants, constructing the verification conditions and proving them correct. This is known as a posteriori verification. Dijkstra popularized an alternative approach, correct-by-construction, where we also start by formulating precise pre- and postconditions. Program code and loop invariants are then derived at the same time, hand in hand, and verification conditions are proved as they arise. The third possibility, invariant based programming (Reynolds, van Emden, Back, see ), moves the construction of program code to an even later stage. Pre- and postconditions are formulated first, as in the other approaches. The next step is then to formulate the loop invariants, before any code is written. The code is constructed last, as transitions between the different situations (precondition, postcondition, loop invariants) that can occur during program execution. The verification conditions corresponding to these transitions are verified as they arise.