predicative programming

Article summary

Predicative programming is the original name of a formal method for program specification and refinement, more recently called a Practical Theory of Programming, invented by Eric Hehner. The central idea is that each specification is a binary (boolean) expression that is true of acceptable computer behaviors and false of unacceptable behaviors. It follows that refinement is just implication. This is the simplest formal method, and the most general, applying to sequential, parallel, stand-alone, communicating, terminating, nonterminating, natural-time, real-time, deterministic, and probabilistic programs, and includes time and space bounds. Commands in a programming language are considered to be a special case of specification—those specifications that are compilable. For example, if the program variables are x , y , and z , the command x := y +1 is equivalent to the specification (binary expression) x' = y +1 ∧ y' = y ∧ z' = z in which x , y , and z represent the values of the program variables before the assignment, and x' , y' , and z' represent the values of the program variables after the assignment. If the specification is x' > y , we easily prove ( x := y +1) ⇒ ( x' > y ), which says that x := y +1 implies, or refines, or implements x' > y . Loop proofs are greatly simplified.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.