On the refinement calculus.
The work at Oxford sprang from the need to develop a rigorous imperative programming course for our first undergraduate computing degree, which began only in 1985. The strong local tradition of specification and refinement, in \(Z\) had not yet reached the level of everyday programming languages (a disadvantage with respect to VDM, for example); the specification statement, like a \(Z\) schema but with \(wp\)-semantics, was to make the connection. The current text for that course [46] rests on the subsequent research, reported in this volume, but has been much informed by the work of others. As an undergraduate programming text, it presents its method mostly by example, and is deliberately light on justification and history. Thus those seeking the background and mathematical underpinnings should look in the present collection. The specification statement introduces specifications to Dijkstra's language of guarded commands, and explores the consequences: increased expressive power, the new prominence of the refinement relation, miracles, and a surprising factorisation at that language into smaller pieces. It is the same factorisation reported independently by Nelson. Specification statements and refinements gives our first collection of `laws of refinement', and lays the emphasis on a calculus of refinement. Procedures, parameters, and abstraction: separate concerns shows ow specifications in a programming language allow the copy rule of ALGOL 60, once again, to give the meaning of procedures. One side effect is the ability to parametrize program fragments which are not procedures. Data refinement using miracles and Auxiliary variable in data refinement describe small aspects of data refinement, independently of the refinement calculus. The former uses the Gries and Prins data-refinement rule only in order to be self-contained. Data refinement is dealt with more generally in Data refinement of predicate transformers and Data refinement by calculation. The first gives a more theoretical, the second a more practical exposition of the way data refinement and the refinement calculus can interact. Types and invariants in the refinement calculus explains the way in which the hitherto informal treatment of types during \(wp\)-based program derivation can be made rigorous without undue formal cost. It expose some surprising connections -- for example that ascribing a type to a variable is a degenerate form of data refinement. It leads also to some unexpected conclusions, one of which is that `ill-typed' programs can be considered well-formed but miraculous. A single complete rule for data refinement brings two separate techniques of data refinement, known to be jointly-complete up to bounded nondeterminism, into a single method.
This page was built for publication: On the refinement calculus.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4278674)