Predicate transformer semantics: Difference between revisions

Revision as of 18:49, 9 September 2005

Revision as of 18:50, 6 October 2005

Line 1:

'''Predicate transformer semantics''' is an extension of [[Hoare_logic|Floyd-Hoare Logic]] invented by [[Dijkstra]] and extended and refined by other researchers. It was first introduced in Dijkstra's paper "Guarded commands, nondeterminacy and formal derivation of programs". It is a method for defining the semantics of an [[Imperative_programming|imperative programming]] language by assigning to each ''command'' in the language a corresponding ''predicate transformer''. A ''[[predicate transformer]]'' is a [[Total function|total function]] mapping between two ''[[assertion (computing)|predicates]]'' on the state space of a program.

The canonical ''predicate transformer'' of sequential imperative programming is the so-called "[[weakest pre-condition]]" <math>wp(S, R)</math>. Here ''S'' denotes a list of ''commands'' and ''R'' denotes a predicate on the space, called the "[[post-condition]]". The result of applying this function gives the "weakest pre-condition" for ''S'' terminating with ''R'' true. An example is the following definition of the assignment statement:

:<math> wp(x := E, R) = R_E^x </math>

Line 15:

Dijkstra also defined alternative ('''if''') and repetitive ('''do''') constructs as well as a composition operator (''';''') using ''wp''. The alternative and repetitive constructs used ''[[guarded commands]]'' to influence execution. Because of the rules he imposed on the definition of ''wp'', both constructs allow for non-deterministic execution if the ''[[guard (computing)|guard]]s'' in the commands are non disjoint.

Unlike many other semantic formalisms, predicate transformer semantics was not designed as an investigation into foundations of computation. Rather, it is intended to provide programmers with a methodology to develop their programs as "correct by construction" in a "calculational style". This style was advocated by Dijkstra and others, and also developed further in a [[Higher-order_logic|higher order logic]] setting by [[Ralph-John Back|R.-J. Back]] in the [http://www.ecs.soton.ac.uk/~mjb/refcalc-tut/home.html Refinement Calculus].

Although the most common and most widely discussed because of their relevance to sequential programming, "weakest pre-conditions" are not the only ''predicate transformers''. For example, [[Leslie Lamport]] has suggested ''win'' and ''sin'' as ''predicate transformers'' for [[concurrent programming]].

Line 21:

== References ==

* [[Edsger W. Dijkstra.]], "Guarded commands, nondeterminacy and formal derivation of programs". ''[[Communications of the [[Association for Computing Machinery|ACM]]'', 18(8):453-&ndash;457, August 1975. [http://doi.acm.org/10.1145/360933.360975]

* [[Leslie Lamport. ]], "''win'' and ''sin'': Predicate Transformers for Concurrency". ''[[Association for Computing Machinery|ACM]] Transactions on Programming Languages and Systems'', 12(3), July 1990. [http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-win]

* [[Ralph-Johan J. Back]] ''et al.'', "''Refinement Calculus: A Systematic Introduction'', 1st edition"., 1998. ISBN 0-387-98417-8.

* Edsger W. Dijkstra:. "''A Discipline Ofof Programming"'' (A systematic introduction with examples.). ISBN 0-613-92411-8.

[[Category:Computer science]]

[[Category:Theoretical computer science]]

[[Category:Logic in computer science]]

[[Category:Formal methods]]