Partial correctness for probabilistic demonic programs.
Recent work in sequential program semantics has produced both an operational (He et al., Sci. Comput. Programming 28(2, and an axiomatic (Morgan et al., ACM Trans. Programming Languages Systems 18(3) (1996) 325-353; Seidel et al., Tech Report PRG-TR-6-96, Programming Research group, February 1996) treatment of total correctness for probabilistic demonic programs, extending Kozen's original work (J. Comput. System Sci. 22 (1981) 328-350; Kozen, Proc. 15th ACM Symp. on Theory of Computing, ACM, New York, 1983) by adding demonic nondeterminism. For practical applications (e.g. combining loop invariants with termination constraints) it is important to retain the traditional distinction between partial and total correctness. Jones (Monograph ECS-LFCS-90-105, Ph.D. Thesis, Edinburgh University, Edinburgh, UK, 1990) defines probabilistic partial correctness for probabilistic, but again not demonic programs. In this paper we combine all the above, giving an operational and axiomatic framework for both partial and total correctness of probabilistic and demonic sequential programs; among other things, that provides the theory to support our earlier---and practical---publication on probabilistic demonic loops (Morgan, in: Jifeng et al. (Eds.), Proc. BCS-FACS Seventh Refinement Workshop, Workshops in Computing, Springer, Berlin, 1996. Copyright 2001 Elsevier Science B.V.
Introduction
Deterministic computation over a state space S can be modelled as functions
of type S ! S, from initial to final states. A 'powerdomain' construction
extends that to nondeterminism, and although the traditional powerdomains
- Smyth, Hoare and Plotkin - differ in their treatment of non-termination,
they all agree that nondeterminism is 'demonic', resolved in some arbitrary
way.
The probabilistic powerdomain [7, 6] instead resolves nondeterminism according
to some specified distribution over final states: demonic choice is
removed, and replaced by probabilistic choice.
He et al. [4] do not remove demonic choice; rather they model demonic
and probabilistic nondeterminism jointly by combining a special case of the
probabilistic powerdomain, for imperative programs [9], with the Smyth (de-
monic) construction. Morgan et al. [13] then complement that with a programming
logic of 'greatest pre-expectations' (extending Kozen's work [10]),
resulting overall in a treatment of total correctness for probabilistic and demonic
sequential programs.
In this paper we extend the constructions of He and Morgan to partial
correctness also. One important application for both forms of correctness
is the justification of invariant/variant principles for probabilistic demonic
loops: although published [11], those principles are based on (only) postulated
connections between wp and wlp for probabilistic programs - here we
provide the theory for their proof.
Another application is in the abstraction from probabilistic to demonic
choice; we discuss both issues in the conclusion.
To model partial (Hoare-style) and total (Smyth-style) correctness within
the same framework, we choose the Egli-Milner construction for demonic
choice (rather than the Smyth); and its being based on distributions rather
than simple states introduces some novel considerations (in particular the
need for linear interpolation between distributions). For the logic we are
then able to formulate both greatest- and greatest liberal pre-expectations,
reflecting the same total/partial distinction as in standard programming logic
[2].
In Sec. 2 we construct the probabilistic Plotkin-style powerdomain, the
'convex' powerdomain (which is a subset of the general representation in
Abramsky and Jung [1]), and we show how to extract partial and total information
from it; in Sec. 3 we link that to greatest-precondition-based probabilistic
programming logic; and in Sec. 4 and Sec. 5 we specialise to both a
liberal and 'ordinary' logic for a sequential programming language with both
probabilistic and demonic nondeterminism.
An extensive discussion of examples, and the general treatment of loops,
is given elsewhere [11].
Throughout we use infix dot ':' for function application, associating to
the left so that f:x:y means (f(x))(y); and we write ': =' for 'is defined to
be equal to'. Quantifications (including set comprehensions) are written in
the order quantifier (or 'f' for sets), bound variable with optional type, range
and finally term - thus for example
is the set of the first ten squares.
2 A convex powerdomain of distributions
In program semantics, powerdomains are used to study nondeterminism, a
phenomenon arising when a program outputs an arbitrary result (drawn from
a set of possible results) rather than a single, determined function of its input.
Here we consider powerdomains over a domain of probability distributions
rather than of 'definite' single states.
There are several ways of ordering sets of distributions (each resulting
in a different powerdomain): the choice depends on criteria which can
be explained in terms of the desired treatment of programs' possible non-terminating
behaviour. The Smyth order 1 (Def. B2) treats non-termination
as the worst behaviour and thus the Smyth powerdomain models total cor-
rectness. Similarly the Hoare order (Def. B3) models partial correctness: non-termination
is treated as the best outcome in that order. The Plotkin power-
domain uses the Egli-Milner order (Def. B4) which combines both views, and
is useful when both partial and total correctness are to be modelled within
a single framework.
In general the Plotkin powerdomain is not decomposable into the Smyth
and Hoare powerdomains, but in some special cases it is: Abramsky and Jung
[1] show that one such case is when the underlying domain is !-continuous
(Def. B9). In this section we show how Abramsky and Jung's results apply
to an appropriately-defined powerdomain of distributions, thus providing a
single semantic space for both partial and total correctness of programs exhibiting
probabilistic and demonic nondeterminism.
1 For this and other facts and definitions from domain theory, we follow the conventions
set out in [1]. We summarise the details for this paper (often specialising them to our
particular application) in Appendix B.
We write S for the state space, and assume it is finite. The space of
probability distributions over S is defined as follows.
Definition 2.1 For state space S, the space of distributions 2 (S; v) over S
is defined
and for F; F 0 in S we define
show first that (S; v) is an !-continuous complete partial order.
Lemma 2.2 For S a finite state space, its distributions (S; v) form an !-
continuous complete partial order.
Proof: The completeness of (S; v) is trivial, given the completeness of
the interval [0; 1] under - over the reals.
To show that S is !-continuous we only need exhibit a countable basis
(Def. B8). Since S is finite, we use the set of distributions contained in
since any real is the least upper bound of the rationals way-below it (Def. B7).We now define a Plotkin-style powerdomain over S. For subset A of S
we write "A for its up-closure and #A for its down-closure (Def. B1). We
say that A is up-closed (Smyth-closed) if "A = A, that it is down-closed
(Hoare-closed) if A and that it is Egli-Milner-closed 3 if
A further closure condition is related to continuity.
These special distributions are more precisely called discrete sub-probability measures
[9]; they do not necessarily sum to 1, and the deficit gives the probability of nontermination.
The 'everywhere zero' distribution for example, that assigns zero probability to all states,
models nowhere-terminating behaviour. (An alternative though less convenient treatment
would assign probability 1 to some special state ?.)
3 This is often called convex closed ; but we will need that term for another purpose.
Definition 2.3 For subset A of S we define its limit closure lc:A to be the
smallest set containing A itself, together with tA 0 and uA 00 for all up-directed
(Def. B5) subsets A 0 and down-directed (Def. B6) subsets A 00 of A. 4 We say
that A is limit-closed if
Before defining our powerdomain we must introduce one further closure
condition, specific to distributions. For distributions F; F 0 in S and p in
[0; 1] we can form F p \Phi F 0 , the weighted average, defined pointwise over S
as p \Theta F + (1\Gammap) \Theta F 0 (with usual scalar multiplication and addition). For
sets of distributions we define p-averaging as follows.
Definition 2.4 For p in [0; 1] and subsets A; A 0 of S we define
We say that A is convex if A p \Phi
We now can define our powerdomain over S; it is a subset of the Plotkin
powerdomain.
Definition 2.5 The convex powerdomain (CS; vEM ) over the space of distributions
S comprises those subsets of S that are non-empty, Egli-Milner
closed, limit closed and convex. Its order vEM is the usual Egli-Milner order
(Def. B4). 2
The convex powerdomain is a subset of the Plotkin powerdomain because
it includes only the convex subsets of the latter. Our aim for this section is to
show that CS is itself limit complete, and that from its limits the Smyth and
Hoare limits can be extracted - for that is what makes it suitable for our
application of it to probabilistic program semantics. Thus we show that the
least upper bound of an Egli-Milner-directed subset of CS lies within
CS, and that it is a combination of the Hoare least upper bound (tH ) and
the Smyth least upper bound (t S ).
The next lemma is the specialisation of a general decomposition result of
Plotkin powerdomains to (S; v). We write Lens(S) (Def. B10) for the set of
non-empty, Egli-Milner closed, limit closed subsets of S. 5
4 Note that both tA and uA exist for all subsets A of S in particular, directed or not.
5 Thus CS comprises just the convex lenses of S.
Lemma 2.6 For any Egli-Milner-directed subset A of Lens(S) the limit
tEMA exists, and satisfies
(Insisting on limit closure after tH can be seen here as a continuity 6 condi-
tion.)
Proof: The decomposition will be a consequence of the isomorphim between
the abstract Plotkin powerdomain (Def. B12) and the space of lenses of
an !-continuous domain with the topological Egli-Milner ordering (Def. B13).
The isomorphism is given by Abramsky and Jung [1] and is reproduced here
in Thm. B.1. The decomposition (1) holds for abstract Plotkin powerdomains
in general [8].
To establish the isomorphism, note first that the closure conditions on
Lens(S) imply that vEM between lenses reduces to the topological Egli-
Milner ordering; then Lem. 2.2 ensures the conditions of Thm. B.1, namely
that (S; v) is an !-continuous complete partial order. 2
Since CS is a subset of Lens(S), we have in the following corollary our
closure under limits.
Corollary 2.7 For any Egli-Milner-directed subset A of CS the limit tEM
exists in CS, and satisfies
Proof: Given Lem. 2.6, we need only show that t S A " lc:(t H
if all the elements of A are, and that follows from these elementary facts: up-
closing preserves convexity (v-monotonicity of p \Phi); the intersection of convex
sets is convex; down-closing preserves convexity (similar to up-closing); the
union of a '-directed set of convex sets is convex; and limit-closing preserves
convexity (v-continuity of p \Phi). 2
6 Consider the Egli-Milner chain on sets of real intervals in [0; 1],
which has limit f1g (the limit point of the underlying series). The union of the down sets
is the half-closed interval [0; 1) however, and the intersection of the up sets is f1g. Failing
to limit-close the Hoare limit would produce an empty result.
Cor. 2.7 gives us our main result, that the Egli-Milner limit determines
the Smyth limit (in the Smyth ordering) and the Hoare limit (in the Hoare
ordering). We write respectively (Def. B14) for Smyth equivalence
and Hoare equivalence between elements of CS: our theorem below shows
in addition that the limits are indistinguishable relative to the appropriate
equivalences.
Theorem 2.8 For any vEM -directed subset A of CS, the following equivalences
hold:
Proof: This too is a property of abstract Plotkin powerdomains [8], and
so follows from the isomorphism (Thm. B.1) used in the proof of Thm. 2.7.This section has defined the convex powerdomain, whose use for modelling
probabilistic imperative programs now follows from the constructions
for the Smyth-style domain [4]: for example sequential composition is a generalised
functional composition; nondeterministic choice is union (then convex
closure); and probabilistic choice is weighted average as defined above. In
Sec. 4 we give further details.
For recursion one takes limits of chains, and here is the significance of
Thm. 2.8: we must be sure that taking the limit in the convex domain agrees
with the more specialised limit in the Smyth domain and with the more
specialised limit in the Hoare domain - for that is what allows us to use the
more general convex domain for either. It is known that the equivalence holds
for standard (nonprobabilistic) domains 7 ; Thm. 2.8 confirms the preservation
of the property when probability is included.
In the next section we link the convex powerdomain with its partial/total
probabilistic programming logic.
7 In fact the same general argument of this section establishes that, since the standard
approach takes a flat domain S for the state space, trivially !-continuous if S is finite, or
even countable.
3 Probabilistic programs and logic
In this section we use the convex powerdomain CS of Sec. 2 to construct a
model for both total and partial correctness of probabilistic demonic programs. 8
We begin with a review of methods that treat the two aspects separately.
Over standard (non-probabilistic) demonic programs, a popular model for
total correctness is S ! SS? , where S? is the flat domain extending state
space S with ? for non-termination, and S forms the Smyth powerdomain
over that; Dijkstra's weakest `ordinary' preconditions PS ! PS [2] support a
programming logic suitable for total correctness. For partial correctness one
can use S ! HS? (Hoare) for the model and weakest 'liberal' preconditions
for the logic. Finally, although partial and total correctness are available
simultaneously via S ! KS? (Plotkin), for r in S ! KS? and postcondition
Q in PS still it is more convenient to define separately
weakest precondition
weakest liberal precondition (2)
to give the total (wp) and partial (wlp) programming logics. Note that the
definitions (2) work together only over KS (the intersection of HS? and SS? )
- wp does not work over HS? and wlp does not work over SS? . (Nelson
[14] gives a nice treatment of the issues.)
For probabilistic programs, He et al. [4] propose S ! C S S for total
correctness, where C S S is like CS of the previous section, but based on
the Smyth order. Morgan et al. [13] provide a probabilistic 'greatest pre-
expectation' logic for that, where expectations are non-negative real-valued
functions over the state space (extending Kozen's treatment [10] for non-
programs).
To access total and partial correctness simultaneously, by analogy with
the standard case we simply replace He's Smyth-based C S by our Egli-Milner-
based C. Yet rather than define two forms of logic (as at (2) above) we
generalise as do Morgan and McIver [12] by allowing expectations to take
negative values: roughly speaking, for total correctness one uses non-negative
post-expectations and for partial correctness one uses non-positive.
Kozen [9] has modelled total correctness of probabilistic (but not demonic) programs,
and Jones [6] extended that to partial correctness. He [4] models total (but not partial)
correctness of probabilistic demonic programs.
We begin the details with the construction of the probabilistic, demonic
model of programs.
Definition 3.1 For (finite) state space S the space of probabilistic, demonic
programs (MS;vEM ) is given by
with the order induced pointwise from CS, so that for in MS we have
We occasionally use v S and vH over MS, analogously lifted from CS. 2
Thus our programs take initial states to sets of final distributions: the plurality
of the sets represents demonic nondeterminism; the distributions they
contain each represent probabilistic nondeterminism.
The next task is to investigate the dual representation of programs as
expectation transformers. We extend the expectations found in Morgan et
al. [13, 11], where the topic was total correctness (the Smyth order and
up-closed sets) and expectations were of type S ! [0; 1], by using [\Gamma1; 1]
instead: we write ES for S ! [\Gamma1; 1], and use lower-case Greek letters for
typical elements.
Expectation transformers T S are thus functions of type ES ! ES. We
R
F ff for the expected value of ff in ES averaged over distribution F
in S. As a special case of expectations, we interpret predicates as f0; 1g-
valued functions of the state space, and for predicate A holding at state s
we convenient. For a scalar c we write
c for the constant expectation evaluating to c over all of S. With those
conventions the predicates true and false correspond to the expectations 1
and 0 respectively. Finally, for relations between expectations we write
everywhere no more than
everywhere equal to
so that we generalise respectively implication, equivalence and reverse implication
on predicates.
Our logic is based on the 'extended greatest pre-expectation transformer',
defined as follows.
Definition 3.2 Let r be a program in MS, taking initial states in S to sets
of final distributions over S. Then the greatest pre-expectation at state s of
program r, with respect to post-expectation ff in ES, is defined: 9
Z
F
ff) :The effect of the definition is to consider all possible post-distributions F in
r:s, and then demonically to choose the one that gives the least (the 'worst')
expectation for ff: thus nondeterminism is demonic in that it minimises
the pre-expectation at each initial state, and Def. 3.2 is then the greatest
expectation everywhere no more than those pointwise minima.
For standard programs, if executing a program r from a state s is certain
to establish a postcondition A then that state is contained in the associated
weakest precondition; with our definition we would have ewp:r:A:s = 1. For
probabilistic programs, if the standard postcondition A is established with
only a probability at least p say, then the greatest pre-expectation on executing
r from s initially is at least p and we have Thus as a
special case, when A is a predicate we can interpret ewp:r:A:s as the greatest
assured probability that A holds after execution of r from s.
Now we discover the various refinement orders over T S that correspond
via ewp with orders over MS. First, we generalise the observation from standard
programming (eg. [14]) that the Smyth order on programs corresponds
to the implication order lifted to predicate transformers and that the Hoare
order similarly corresponds to (lifted) reverse implication. We use PS (typi-
cal element -) to denote the set of non-negative valued expectations and NS
(typical element -) for the non-positive valued expectations. They are both
subsets of ES.
Lemma 3.3 For
r
9 This reduces to Kozen's definition [9] for deterministic programs. There programs
are functions from initial state to distributions, so that the minimisation ranges over a
singleton set and is thus superfluous.
10 The apparent confusion between expectations and probabilities is deliberate and harm-
less: the probability of an event A over a distribution is equal to the expected value of
(the characteristic function of) A over that same distribution.
Proof: For in MS, any s in S and - in PS we reason as follows
r
implies "(r:s) ' ''(r 0 :s) definition v S
implies
R
R
F -)
R
R
For the deferred justification we appeal to the monotonicity of the arithmetic
over non-negative arguments without subtraction: r:s differs from
"(r:s) only by the addition of 'larger elements' according to Def. 2.1, and
so the minimum selection made in Def. 3.2 cannot be increased by making
the selection over the up-closure instead.
The result now follows by generalising on s, and a similar argument justifies
the second statement (but note the reversal W). 2
Lem. 3.3 is the key to defining the expectation-transformer equivalents
to the Smyth, Hoare and Egli-Milner orders where, as usual, the Egli-Milner
order is the intersection of the Smyth and Hoare orders.
Definition 3.4 For t; t 0 in T S we define
:That the Egli-Milner order between programs is preserved under ewp now
directly.
Corollary 3.5 For
Proof: Lem. 3.3 and Def. 3.4. 2
The corollary shows only that ewp is an order-preserving mapping between
(MS;vEM ) and (T S; vEM ). The next result of this section is to show
that it is also an injection, and therefore that programs can be modelled
equivalently either as relations or as expectation transformers. To establish
that ewp is an embedding we prove the converse to Cor. 3.5.
Lemma 3.6 For
Proof: Suppose for a contradiction that ewp:r vEM ewp:r 0 but r 6v EM r 0 ,
for some in MS. Without loss of generality assume r 6v S r 0 , so that for
some distribution F and state s we have both
F 62 "(r:s) (3)
From (3), with the aid of the separating hyperplane lemma A.1, we have for
some expectation - in PS that
Z
F
Z
and thus that
R
ewp:r:-:s. From (4) however we have ewp:r 0 :-:s - R
directly, giving together
Z
F
and contradicting the hypothesis (at the state s). 2
Since in the proof of Lem. 3.6 we have actually proved the converse to
Lem. 3.3, we can now state the correspondence between the relational model
and program logic for all three orders.
Theorem 3.7 The following equivalences hold for all
r
r vEM r 0 iff ewp:r vEM ewp:r 0 :We have shown that ewp injects MS into T S - but there are many vEM -
monotonic expectation transformers that are not ewp-images of MS. The
final result of this section identifies the exact sub-space of expectation transformers
that form the image of MS through ewp. We identify 'healthiness
in the style of Dijkstra [2] - for standard programs
11 The relevance of the healthiness conditions applied to the programming logic are
treated in Sec. 5.
- and of Morgan et al. [13] - for probabilistic programs - that identify
the (images of) programs of MS within it. The importance of that result
is that theorems proved within T S about healthy expectation transformers
correspond to theorems about programs in MS.
The first healthiness condition is a slight generalisation of the sublinearity
of Morgan [13]. To state it we define, for expectations ff; fi in ES and real
non-negative scalar c, the expectations ff+fi and cff, where (as for p-averaging
of distributions) we mean a pointwise lifting of standard addition and scalar
multiplication.
Definition 3.8 An expectation transformer, t: T S is sublinear iff for all ff; fi
in ES, and a; b; c non-negative reals,
note first that sublinearity is satisfied by all images of MS under
ewp.
Lemma 3.9 Any expectation transformer ewp:r, for r in MS, is sublinear.
Proof: Def. 3.2 and properties of arithmetic. (Morgan [13] gives a more
detailed proof.) 2
For total correctness (for the Smyth C S ), sublinearity tells the whole story
[13, Thm. 8.7]; in our more general CS however, there are sublinear elements
of MS that are not ewp-images: take S to be the two-element state space
fx; yg, and consider the result set
It is convex, but not Egli-Milner closed 12 ; its associated expectation transformer
formed by ewp is sublinear, but it is not the ewp-image of any element
of MS.
The characterisation of Egli-Milner closure is captured by a second healthiness
condition - 'partial linearity' - which states that t:ff depends only
on the pre-expectations of t applied to expectations in PS [ NS.
In fact its closure is fF which it is indistinguishable using
ewp for any ff in PS [ NS.
Definition 3.10 An expectation transformer, t in T S is said to be partially
linear if for all states s in S, and all expectations ff in ES, there are expectations
- in PS and - in NS such that
:Note that the implicit existential quantification in Def. 3.10 means there may
be many decompositions of ff as a sum -. 13
We complete the correspondence between healthy expectation transformers
and MS with the next theorem, which we state only. The proof is omitted
as it is overly technical and not necessary for the rest of the paper.
Theorem 3.11 An expectation transformer t in T S is both sublinear and
partially linear if and only if there is r in MS such that
4 Probabilistic Guarded Commands
In this section we illustrate the constructions of the previous two sections by
giving equivalent relational (MS) and expectation transformer (T S) semantics
for a simple sequential programming language that extends Dijkstra's
guarded commands [2] with a binary probabilistic choice operator p \Phi. 14
The relational semantics of Fig. 1 writes s for the point distribution 15
13 A perhaps more alluring healthiness condition would be that t:ff is determined by its
positive part (ff t 0) and its negative part (ff u 0); but
does not hold for general probabilistic programs, although it does in the restricted set of
standard programs and f0; 1; \Gamma1g-valued expectations [12].
14 He et al. [4] and Morgan et al. [13] give similar presentations of semantics, but for
total rather than partial correctness, and more detailed motivation can be found there.
Note that demonic choice is retained, not replaced.
15 For state s in S we define the point distribution s: S ! [0; 1] to be
As a special case, we write ? for (-s:0), the distribution that evaluates to 0 everywhere
on S.
R
MS !MS
For p \Phi, u and sequential composition, the Egli-Milner closure should be taken of
the right-hand side.

Figure

1: Probabilistic relational semantics
concentrated on a single state s, and u for the demonic combination of pro-
grams. The symbol p \Phi is used both for probabilistic combination of programs
and for the p\Gammaaveraging explained in Sec. 2 between sets of distributions.
Because they contain no demonic nondeterminism, the three primitive
commands all yield singleton result sets. Probabilistic choice p \Phi returns
the weighted average of the result sets of its operands, a singleton set if
its arguments are. 16 The result set of the demonic nondeterministic choice
between two programs is the convex closure of the union of the results of the
operands - the closure models operationally that a demon could resolve the
choice by flipping a coin of arbitrary bias.
In sequential composition, both r and r 0 can be considered as sets of
purely probabilistic programs 'compatible' with them: such programs, say
are thus of type S ! S, and we write r 3 f for compatibility, meaning
(8s: S \Delta f:s 2 r:s). Since the effect of two purely probabilistic programs in
sequence is just a single distribution over s 00 say, defined
Z
f:s
ds 0 (5)
by 'averaging' the effects of f 0 over the intermediate distribution produced
by f:s, for the general case we vary (5) over all f; f 0 to give
In fact p can depend on the state; but for simplicity we assume here that it's constant.
F is the v T -monotonic
function such that F

Figure

2: Probabilistic ewp semantics, where oe is in PS [NS and s is in S.
That simplifies to the definition in Fig. 1 if we regard f 0 in
R
parametrised
by s 00 , abbreviating (-s 0
R
ds 0 ).
In the ewp-semantics of Fig. 2 the post-expectation oe varies only over
PS [NS; 17 we use u also for the pointwise minimum between expectations.
Here probabilistic choice p \Phi returns the weighted average of the results of
its expectation operands; and u takes the pointwise minimum, reflecting the
demon's striving for the worst (least) result. Sequential composition becomes
simple functional composition (as for standard predicate transformers [2]).
In both cases recursion is dealt with by least fixed points in the appropriate
orders: Thm. 3.7 shows that the two orders correspond.
Our concern in the next section will be to recover total and partial semantics
separately from Fig. 2: we will show how to define probabilistic
wp and wlp that generalise Dijkstra's operational interpretations and that
satisfy probabilistic versions of the standard laws for combining partial and
total correctness.
5 Partial and total correctness
Athough ewp acts over all of ES, we can extract two more-specialised logics
from it: each acts conventionally over just the non-negative expectations PS.
17 Because an Egli-Milner-closed set is determined by its Smyth- and Hoare closures,
that is sufficient.
For a total correctness logic we merely restrict to PS directly, and use
the order V.
Definition 5.1 Let r be a program in MS; then the greatest pre-expectation
of program r with respect to post-expectation - in PS, associating 0 with
non-termination, is defined:
easily from sublinearity: if - is in PS then
so that wp:r:- is in PS also. Moreover Lem. 3.3 shows that this wp semantics
of programs corresponds to a relational model with the Smyth ordering [13]
- non-termination is the worst outcome in both semantics.
For partial correctness we define a probabilistic wlp, again we restrict to
the subspace (PS; V).
Definition 5.2 r be a program in MS; then the greatest liberal pre-
expectation of program r with respect to the post-expectation - in PS,
associating 1 with non-termination, is
easily from sublinearity of ewp:r that for - in NS,
3.2 we can readily show Def. 5.2 to be identical to
Z
F
which is a demonic generalisation of the probabilistic wlp defined only for nondemonic
programs by Jones [6]. Morgan [12] shows that (6) also generalises standard wlp [2].
and thus since lies in NS, so does ewp:r:(- \Gamma 1) from which we deduce
that wlp:r is a well-defined expectation transformer in PS ! PS. Also
Lem. 3.3 implies that the wlp semantics corresponds to a relational model
with the Hoare ordering - accordingly non-termination is the best outcome.
For example, let S be some finite portion of N , and for natural number N
for the assignment taking every initial state to the final state
N . The program
illustrates the difference between wp and wlp. Writing for the expectation
that evaluates to 1 when s is N and to 0 otherwise, we have
indicating that the greatest expectation of termination in state 0 is pq, for
all initial states.
The greatest expectation of either termination at 0 or nontermination is
found with wlp; we have
Thus the wp observation gives the greatest guaranteed probability 19 of termination
at 0 - and non-termination guarantees nothing. The wlp observation
on the other hand returns the probability that either 0 is reached or the program
fails to terminate - the usual interpretation for partial correctness.
19 This follows from the usual interpretation of the expected value of a f0; 1g-valued
random variable A with respect to a probability distribution: it is the chance that the
random outcome will establish the event "A evaluates to 1".
F is the v T -monotonic
function such that F

Figure

3: Probabilistic wlp semantics, where - is in PS and s is in S. The
greatest fixed point - is used for recursion.
Similarly the wlp semantics of a looping program is calculated as the
greatest fixed point 20 of a monotonic function over PS (rather than the
least, as for wp). It is easily checked that specialising Fig. 2 to wlp produces
only the changes shown in Fig. 3. (Note that PS [NS is closed under \Sigma1.)
An alternative view of wlp and wp often put forward is to regard them
as functions on programs which satisfy certain properties - for example
Nelson [14] defines (standard) wp and wlp axiomatically by enforcing both
the coupling law (at (7) below) and conjunctivity properties (both wp and
wlp induce conjunctive predicate transformers). Thus the efficacy of the
probabilistic definitions lies in the generalisation of those properties: Lem. 5.3
and Thm. 5.4 (also below) generalise respectively conjunctivity and coupling
(7), and as such they form the main results of this section.
We state the coupling here for standard programs [5]:
where r is a program and A a predicate and we are using (though only here)
the original meanings for wp and wlp [2], with V for 'implies at all states'.
Law (7) implies that wp:r and wlp:r agree on initial states from which
termination is guaranteed, and thus it underlies the practical treatment of
looping programs - to prove total correctness of an iteration the work is
divided between ensuring partial correctness (with a loop invariant), and
an independent termination argument (with a variant). The probabilistic
coupling Thm. 5.4 will allow a similar treatment for probabilistic looping
programs.
This follows from Def. 5.2 since the least fixed point of a v T -monotonic function
becomes specialised first to W on NS ! NS which order is then shifted to PS ! PS by
applying "1+".
We consider first the appropriate generalisation of conjunctivity: conjunction
of predicates is replaced by probabilistic conjunction [17] defined for
non-negative expectations - 0
where t is pointwise maximum between expectations.
Probabilistic conjunction reduces to ordinary conjunction when specialised
to predicates. 21 Its importance in probabilistic reasoning is that it subdis-
tributes through both wp and wlp images of programs - another consequence
of sublinearity. 22
Lemma 5.3 For r in MS and - 0 in PS,
Proof: Sublinearity (with monotonicity of ewp:r, and
Defs. 5.1, 5.2. 2
Next we deal with coupling - Thm. 5.4, generalising (7), is the main
result of this section.
Theorem 5.4 For r in MS and - 0 in PS,
Proof:
take only the extreme values 0 and 1, then
22 One might have guessed that u is the appropriate generalisation of - but u does
not (even sub-) distribute [6, 17].
Having established wp:r:(- 0
taking t0 on both sides: since on the left it has no effect, we achieve our
result. 2
As a corollary we recover the standard rule (generalised) for combining
partial and total correctness.
Corollary 5.5 For r in MS and - in PS,
Proof: Thm. 5.4 and that - j - & 1 for - in PS. 2
As a special case note that the wlp result implies the wp result at those
states from which termination occurs with probability 1 - where wp:r:1
because (&1) is the identity.
6 Conclusion
The technical contribution of this paper is to extend the Plotkin construc-
tion, with its Egli-Milner order, to act over probability distributions rather
than points, then showing that the decomposition [15] into respectively the
convex Hoare (partial correcness) and convex Smyth (total correctness) pow-
erdomains continues to hold - even under taking limits.
A key feature is the imposition of convexity (linear interpolation) between
distributions.
Jones [6] defines a partial correctness logic based on expectations, but
only for non-demonic programs, and she does not discuss the healthiness
conditions on which the applicability of such logics (as calculational tools)
depends. It was the realisation [13] that adding nondeterminism to Kozen's
model corresponds to a weakening of the additive property of his logic to
sublinearity that makes proofs such as in Thm. 5.4 and those in [11] reduce
to simple arithmetic arguments. The use of general expectations (thus superseding
purely non-negative expectations [13]) leads to an even simpler
presentation of sublinearity - the more useful of the two healthiness conditions
described here.
There are two immediate applications. The first is the discovery of proof
rules for loops in which partial and total correctness are separated: with wp
and wlp together it can be shown [11] that
I preserved by loop body
is sufficient for I V wp:(do G ! body od):(I u :G) provided I V T , where
T gives for each initial state the probability of the loop's termination.
The second application is abstraction. For some programs only termination
is probabilistic, and (partial) correctness can be established informally
by considering all probabilistic choices to be demonic: algorithms falling in
to that category typically use randomization as a method for searching a
large space of potential witnesses, and examples include finding perfect hash
functions and finding irreducible polynomials (Mehlhorn, Rabin [3]).
Suppose the loop do G ! body od contains probabilistic choices in body ,
and denote by body the result of replacing them all with demonic choice.
If (the fairness of) probability was essential for the loop's termination, the
resulting standard loop
do
though probability-free, would not terminate and so a wp analysis of it would
be useless.
With a theory of partial correctness however we can reason as follows:
for a standard loop invariant I,
G u I V wlp:body:I established by standard reasoning say
hence I V wlp:loop:(I u :G) standard loop rule
hence I V wlp:loop:(I u
where loop and loop are the two loops containing body and body respectively.
Thus from standard reasoning about body we reach probabilistic conlusions
about loop.
The last step relies only on loop v loop, which by wlp-monotonicity of
do od follows from body v body ; that in turn is guaranteed by (u) v ( p \Phi)
for all p. Note that probabilistic wlp is essential - the last step would not
hold if we had written wp:body .
One would conclude the argument by determining T j wp:loop:1 sepa-
rately, then having
I
from Thm. 5.4.
A Standard results from linear programming
Lemma A.1 The separating hyperplane lemma. Let C be a convex and
(limit-) closed subset of R N , and F a point in R N that does not lie in C.
Then there is a separating hyperplane ff with F on one side of it and and all
of C on the other.
Proof: See for example Trustrum [18]. 2
Our use in Lem. 3.6 is based on interpreting distribution F as a point
in R N , and an expectation ff as the collective normal of a family of parallel
hyperplanes. The integral
R
F ff then gives the constant term for the
ff-hyperplane that passes through the point F .
More generally, for a convex region C in R N , the minimum
Z
F
gives the constant term for the ff-hyperplane that touches C, with its normal
pointing into C.
Thus when specialised for the applications in this paper, the lemma implies
that if F 62 C for some closed convex set of distributions C, then there
is an expectation ff with
Z
F
Z
Moreover if C is up-closed (down-closed) then the range of ff above specialises
to PS (NS).
Facts and definitions from domain theory
We summarise here Abramsky and Jung's presentation [1] of facts from domain
theory, giving page numbers where appropriate. Assume (D; v) is a
complete partial order - i.e. that every directed (defined below) set has a
least upper bound.
1. up-, down-closure For subset A of D we define its up-closure "A to
be the set
Similarly we define its down-closure #A to be the set
2. Smyth order (p.97) The Smyth order v S on PD, for subsets A; A 0 of
D, is given by
A
3. Hoare order (p.97) The Hoare order vH on PD, for subsets A; A 0 of
D, is given by
A vH A 0 iff A ' #A
4. Egli-Milner order The Egli-Milner order vEM between subsets combines
the Smyth (Def. B2) and Hoare (Def. B3) order. For subsets
of D we define
A vEM A 0 iff "A ' A 0 and A ' #A
5. up-directed (Def. 2.1.8, p.10) A subset A of D is up-directed (or
simply directed) iff for any u; v in A there is a w also in A such that
for the least upper bound of A (if it
exists).
6. down-directed A subset A of D is down-directed iff for any u; v in A
there is a w also in A such that w v u and w v v. We write uA for
the greatest lower bound of A (if it exists).
7. way-below (Def. 2.2.1, p.15) The way-below relation - on D is defined
as follows: for u; v in D we say u up-directed subsets A
of D with v v tA there is some w in A with u v w. We also say u
approximates v iff u - v.
8. basis (Def. 2.2.3, p.16) A basis for D is a subset B such that every
element of D is the t-limit of the elements way below it in B.
9. !-continuity (Def. 2.2.6, p.17) D is !-continuous if it has a countable
basis.
10. lens (Def. 6.2.15, p.100) We define the lenses of D, Lens(D), to be the
set of non-empty, Egli-Milner closed, limit-closed subsets of D.
11. ideal (p.10) A subset I is an ideal if it is directed and down-closed.
12. Plotkin powerdomain (Theorem 6.2.3, p.95) The Plotkin powerdo-
main of D with basis B is given by the ideal (Def. B11) completion
of
where F(B) denotes the set of finite, nonempty subsets of B.
13. topological Egli-Milner order (Def. 6.2.16, p.101) Define the topological
Egli-Milner order v TEM on the set of Egli-Milner closed subsets,
Lens(D), of D as follows:
14. Smyth-, Hoare-equivalence Two subsets A; A 0 of D are Smyth equivalent
are Hoare-equivalent if
Theorem B.1 (Theorem 6.2.19, p.101) If D is an !-continuous complete
partial order, its Plotkin powerdomain is isomorphic to (Lens(D); v TEM ). 2



--R

Domain theory.
A Discipline of Programming.

Probabilistic models for the guarded command language.

Probabilistic nondeterminism.
A probabilistic powerdomain of evaluations.
Private communication.
Semantics of probabilistic programs.
A probabilistic PDL.
Proof rules for probabilistic loops.
Unifying wp and wlp.
Probabilistic predicate transformers.
A generalization of Dijkstra's calculus.
"Pisa Notes"

An introduction to probabilistic predicate transformers.
Linear Programming.
--TR
Parallel program design: a foundation
A generalization of Dijkstra''s calculus
Probabilistic non-determinism
Building on the unity experience
On randomization in sequential and distributed algorithms
Domain theory and integration
Domain theory
Probabilistic predicate transformers
PCF extended with real numbers
Modeling and verification of randomized distributed real-time systems
Unifying <italic>wp</italic> and <italic>wlp</italic>
Probabilistic models for the guarded command language
A Discipline of Programming
A probabilistic PDL

--CTR
Joe Hurd , Annabelle McIver , Carroll Morgan, Probabilistic guarded commands mechanized in HOL, Theoretical Computer Science, v.346 n.1, p.96-112, 23 November 2005
Yuxin Deng , Rob van Glabbeek , Matthew Hennessy , Carroll Morgan , Chenyi Zhang, Remarks on Testing Probabilistic Processes, Electronic Notes in Theoretical Computer Science (ENTCS), 172, p.359-397, April, 2007
program logic;partial correctness;probability;verification