Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Predicate transformer semantics
open-in-new
<p>Predicate transformer semantics were introduced by <a href="/facts/Edsger_W._Dijkstra/910x0MjT">Edsger Dijkstra</a> in his seminal paper "<a href="/facts/Guarded_commands/fpojgtkM">Guarded commands, nondeterminacy and formal derivation of programs</a>". They define the semantics of an <a href="/facts/Imperative_programming/6b5dUnE1">imperative programming</a> paradigm by assigning to each <i>statement</i> in this language a corresponding <i>predicate transformer</i>: a <a href="/facts/Total_function/0vJMw0Nm">total function</a> between two <i><a href="/facts/Predicate_(mathematical_logic)/5WazAvKF">predicates</a></i> on the state space of the statement. In this sense, predicate transformer semantics are a kind of <a href="/facts/Denotational_semantics/yRs3ygRA">denotational semantics</a>. Actually, in <a href="/facts/Guarded_commands/fpojgtkM">guarded commands</a>, Dijkstra uses only one kind of predicate transformer: the well-known weakest preconditions (see below). </p><p>Moreover, predicate transformer semantics are a reformulation of <a href="/facts/Floyd%25E2%2580%2593Hoare_logic/UoMg08wo">Floyd–Hoare logic</a>. Whereas Hoare logic is presented as a <a href="/facts/Deductive_system/KaeDAjK7">deductive system</a>, predicate transformer semantics (either by weakest-preconditions or by strongest-postconditions see below) are complete strategies to build <a href="/facts/Deductive_reasoning/HadA1zWS">valid deductions</a> of Hoare logic. In other words, they provide an effective <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> to reduce the problem of verifying a Hoare triple to the problem of proving a <a href="/facts/First-order_logic/lcISqWIg">first-order formula</a>. Technically, predicate transformer semantics perform a kind of <a href="/facts/Symbolic_execution/EvcoXl9m">symbolic execution</a> of statements into predicates: execution runs <i>backward</i> in the case of weakest-preconditions, or runs <i>forward</i> in the case of strongest-postconditions. </p>