Conditioning in Probabilistic Programming
Nils Jansen
and Benjamin Lucien Kaminski
and Joost-Pieter Katoen
and Federico Olmedo

Friedrich Gretz
and Annabelle McIver
Macquarie University
Sydney, Australia

arXiv:1504.00198v1 [] 1 Apr 2015

RWTH Aachen University
Aachen, Germany

Abstract—We investigate the semantic intricacies of conditioning, a main feature in probabilistic programming. We provide a
weakest (liberal) pre–condition (w(l)p) semantics for the elementary probabilistic programming language pGCL extended with
conditioning. We prove that quantitative weakest (liberal) pre–
conditions coincide with conditional (liberal) expected rewards in
Markov chains and show that semantically conditioning is a truly
conservative extension. We present two program transformations
which entirely eliminate conditioning from any program and
prove their correctness using the w(l)p–semantics. Finally, we
show how the w(l)p–semantics can be used to determine conditional probabilities in a parametric anonymity protocol and
show that an inductive w(l)p–semantics for conditioning in non–
deterministic probabilistic programs cannot exist.

I. I NTRODUCTION
Probabilistic programming is en vogue [1], [2]. It is mainstream in machine learning for describing distribution functions; Bayesian inference is pivotal in their analysis. It is used
in security for describing both cryptographic constructions
such as randomized encryption and experiments defining security notions [3]. Probabilistic programs, being an extension
of familiar notions, render these various fields accessible to
programming communities. A rich palette of probabilistic
programming languages exists including Church [4] as well
as modern approaches like probabilistic C [5], Tabular [6]
and R2 [7].
Probabilistic programs are sequential programs having two
main features: (1) the ability to draw values at random from
probability distributions, and (2) the ability to condition values
of variables in a program through observations. The semantics of languages without conditioning is well–understood.
Kozen [8] considered denotational semantics, whereas McIver
and Morgan [9] provided a weakest (liberal) precondition
(w(l)p) semantics; a corresponding operational semantics is
given by Gretz et al. [10]. Other relevant works include
probabilistic power–domains [11], semantics of constraint
probabilistic programming languages [12], and semantics for
stochastic λ–calculi [13].
Conditioning of variables through observations is less well–
understood and raises various semantic difficulties as we will
discuss in this paper. Previous work on semantics for programs
with observe statements [7], [14] do neither consider the
possibility of non–termination nor the powerful feature of
non–determinism. In this paper, we thoroughly study a more

general setting which accounts for non–termination by means
of a very simple yet powerful probabilistic programming
language supporting non–determinism and observations. Let
us first study a few examples that illustrate the semantic
intricacies. The sample program snippet Pobs1
{x := 0} [1/2] {x := 1}; observe x = 1
assigns zero to the variable x with probability 1/2 while x is
assigned one with the same likelihood, after which we condition to the outcome x being one. The observe statement
blocks all runs violating its condition and prevents those runs
from happening. It differs, e.g., from program annotations
like (probabilistic) assertions [15]. The interpretation of the
program is the expected outcome conditioned on permitted
runs. For the sample program Pobs1 this yields the outcome
1 · 1—there is one feasible run that happens with probability
one with x being one. Whereas this is rather straightforward,
a slight variant like Pobs2
{x := 0; observe x = 1} [1/2] {x := 1; observe x = 1}
is somewhat more involved, as the entire left branch of the
probabilistic choice is infeasible. Is this program equivalent to
the sample program Pobs1 ?
The situation becomes more intricate when considering
loopy programs that may diverge. Consider the programs Pdiv
(left) and Pandiv (right):
x := 1;
while (x = 1) {
x := 1
}

x := 1;
while (x = 1) {
{x := 1} [1/2] {x := 0};
observe x = 1
}

Program Pdiv diverges and therefore yields as expected outcome zero. Due to the conditioning on x=1, Pandiv admits
just a single—diverging—feasible run but this run almost
surely never happens. Its conditional expected outcome can
thus not be measured. It should be noted that programs with
(probabilistic) assertions must be loop–free to avoid similar
problems [15]. Other approaches insist on the absence of
diverging loops [16].
Intricacies also occur when conditioning is used in programs
that may abort. Consider the program


abort [1/2] {x := 0} [1/2] {x := 1};

{y := 0} [1/2] {y := 1}; observe x=0 ∨ y=0

wp[P ](f ) with respect to wlp[P ](1). The latter yields the
wp under which P either does not terminate or terminates
while passing all observe statements. This is proven to
correspond to conditional expected rewards in the RMDP–
semantics, extending a similar result for pGCL [10]. Our
semantic viewpoints are thus consistent for fully probabilistic
programs. Besides, we show that conditioning is semantically
a truly conservative extension. That is to say, our semantics is
backward compatible with the (usual) pGCL semantics; this
does not apply to alternative approaches such as R2 [7].
Finally, we show several practical applications of our results. We present two program transformations which entirely
eliminate conditioning from any program and prove their
correctness using the w(l)p–semantics. In addition, we show
how the w(l)p–semantics can be used to determine conditional probabilities in a simplified version of the parametric
anonymity protocol Crowds [18].
Summarized, we provide the first operational semantics for
imperative probabilistic programming languages with conditioning and both probabilistic and non–deterministic choice.
Furthermore we give a denotational semantics for the fully
probabilistic case, which in contrast to [7], [14], where every program is assumed to terminate almost surely, takes
the probability of non–termination into account. Finally, our
semantics enables to prove the correctness of several program
transformations that eliminate observe statements.

where abort is the faulty aborting program which by definition does nothing else but diverge. The above program tosses
a fair coin and depending on the outcome either diverges or
tosses a fair coin twice. It finally conditions on at least once
heads (x=0 or y=0). What is the probability that the outcome
of the last coin toss was heads? The main issue here is how
to treat the possibility of abortion.
Combining conditioning with non–determinism is complicated, too.1 Non–determinism is a powerful means to deal with
unknown information, as well as to specify abstractions in
situations where details are unimportant. Let program Pnondet
be:
{{x := 5}  {x := 2}} [1/4] {x := 2};
observe x > 3
where with probability 1/4, x is set to either 5 or 2 non–
deterministically (denoted {x := 5}  {x := 2}), while x is
set to 2 with likelihood 3/4. Resolving the non–deterministic
choice in favour of setting x to five yields an expectation of
5 for x, obtained as 5 · 1/4 rescaled over the single feasible
run of Pnondet . Taking the right branch however induces an
infeasible run due to the violation of the condition x > 3,
yielding a non–measurable outcome.
The above issues—loops, divergence, and non–determinism—indicate that conditioning in probabilistic programs
is far from trivial. This paper presents a thorough semantic treatment of conditioning in a probabilistic extension of
Dijkstra’s guarded command language (known as pGCL [9]),
an elementary though foundational language that includes
(amongst others) parametric probabilistic choice. We take several semantic viewpoints. Reward Markov Decision Processes
(RMDPs) [17] are used as the basis for an operational semantics. This semantics is rather simple and elegant while covering
all aforementioned phenomena. In particular, it discriminates
the programs Pdiv and Pandiv while it does not discriminate
Pobs1 and Pobs2 .
We also provide a weakest pre–condition (wp) semantics à
la [9]. This is typically defined inductively over the structure of
the program. We show that combining both non–determinism
and conditioning cannot be treated in this manner. Given this
impossibility result we present a wp–semantics for fully probabilistic programs, i.e., programs without non–determinism.
To treat possibly non–terminating programs, due to e.g., diverging loops or abortion, this is complemented by a weakest
liberal pre–condition (wlp) semantics. The wlp–semantics
yields the weakest pre–expectation—the probabilistic pendant
of weakest pre–condition—under which program P either
does not terminate or establishes a post–expectation. It thus
differs from the wp–semantics in not guaranteeing termination.
The conditional weakest pre–expectation (cwp) of P with
respect to post–expectation f is then given by normalizing

II. P RELIMINARIES
In this section we present the probabilistic programming
language used for our approaches and recall the notions of
expectation transformers and (conditional) expected reward
over Markov decision processes used to endow the language
with a formal semantics.
a) Probabilistic programs and expectation transformers: We adopt the probabilistic guarded command language
(pGCL) [9] for describing probabilistic programs. pGCL is
an extension of Dijkstra’s guarded command language (GCL)
[19] with a binary probabilistic choice operator and its syntax
is given by clause
P ::= skip | abort | x := E | P; P | ite (G) {P} {P}
| {P} [p] {P} | {P}  {P} | while (G) {P} .
Here, x belongs to V, the set of program variables; E is an
arithmetical expression over V, G a Boolean expression over
V and p a real–valued parameter with domain [0, 1]. Most
of the pGCL instructions are self–explanatory; we elaborate
only on the following: {P } [p] {Q} represents a probabilistic
choice where programs P is executed with probability p and
program Q with probability 1−p. {P }  {Q} represents a
non–deterministic choice between P and Q.
pGCL programs are given a formal semantics through the
notion of expectation transformers. Let S be the set of program
states, where a program state is a variable valuation. Now
assume that P is a fully probabilistic program, i.e. a program
without non–deterministic choices. We can see P as a mapping
from an initial state σ to a distribution over final states JP K(σ).

1 As stated in [2], “representing and inferring sets of distributions is more
complicated than dealing with a single distribution, and hence there are several
technical challenges in adding non–determinism to probabilistic programs”.

2

Given a random variable f : S → R≥0 , transformer wp[P ]
maps every initial state σ to the expected value EJP K(σ) (f )
of f with respect to the distribution of final states JP K(σ).
Symbolically,

Definition II.1 (Parametric Discrete–time Reward Markov
Decision Process). Let AP be a set of atomic propositions.
A parametric discrete–time reward Markov decision process
(RMDP) is a tuple R = (S, sI , Act, P, L, r) with a countable set of states S, a unique initial state sI ∈ S, a finite set of
actions Act, a transition probability function
P : S × Act →
P
Distr(S) with ∀(s, α) ∈ S × Act•
P(s,
α)(s′ ) = 1,
′
s ∈S
AP
a labeling function L : S → 2 , and a reward function
r : S → R≥0 .

wp[P ](f )(σ) = EJP K(σ) (f ) .
In particular, if f = χA is the characteristic function of
some event A, wp[P ](f ) retrieves the probability that the
event occurred after the execution of P . (Moreover, if P is a
deterministic program in GCL, EJP K(σ) (χA ) is {0, 1}–valued
and we recover the ordinary notion of weakest pre–condition
introduced by Dijkstra [19].)
In contrast to the fully probabilistic case, the execution of
a non–deterministic program P may lead to multiple—rather
than a single—distributions of final states. To account for
these kind of programs, the definition of wp[P ] is extended as
follows:
wp[P ](f )(σ) = ′ inf Eµ′ (f )

A path of R is a finite or infinite sequence π = s0 α0 s1 α1 . . .
such that si ∈ S, αi ∈ Act, s0 = sI , and P(si , αi )(si+1 ) > 0
for all i ≥ 0. A finite path is denoted by π̂ = s0 α0 . . . sn for
n ∈ N with last (π̂) = sn and |π| = n. The i-th state si of π is
denoted π(i). The set of all paths of R is denoted by PathsR
R
and sets of infinite or finite paths by PathsR
inf or Pathsfin ,
R
respectively. Paths (s) is the set of paths starting in s and
PathsR (s, s′ ) is the set of all finite paths starting in s and
ending in s′ . This is also lifted to sets of states. If clear from
the context we omit the superscript R.
An MDP operates by a non–deterministic choice of an
action α ∈ Act that is enabled at state s and a subsequent
probabilistic determination of a successor state according to
P(s, α). We denote the set of actions that are enabled at s by
Act(s) and assume that Act(s) 6= ∅ for each state s. A state
s with |Act(s)| = 1 is called fully probabilistic, and in this
case we use P(s, s′ ) as a shorthand for P(s, α)(s′ ) where
Act(s) = {α}. For resolving the non–deterministic choices,
so–called schedulers are used. In our setting, deterministic
schedulers suffice, which are partial functions S : PathsR
fin →
Act with S(π̂) ∈ Act(last (π̂)). A deterministic scheduler is
called memoryless if the choice depends only on the current
state, yielding a function S : S → Act. The class of all
(deterministic) schedulers for R is denoted by Sched R .
A parametric discrete–time reward Markov chain (RMC) is
an RMDP with only fully probabilistic states. For an RMC
we use the notation R = (S, sI , P, L, r) where P : S →
Distr(S) is called a transition probability matrix. For RMDP
R, the fully probabilistic system S R induced by a scheduler
S ∈ Sched R is an induced RMC. A probability measure
is defined on the induced RMCs. The measure for RMC R
R
is given by PrR : PathsR
fin → [0, 1] ⊆ R with Pr (π̂) =
Qn−1
i=0 P(si , si+1 ), for π̂ = s0 . . . sn . The probability measure
can be lifted to sets of (infinite) paths using a cylinder set
construction, see [21, Ch. 10]. The cumulated
of a
Preward
n−1
finite path π̂ = s0 . . . sn is given by r(π̂) = i=0 r(si ) as
the reward is “earned” when leaving the state.
We consider reachability properties of the form ♦ T for a
set of target states T = {s ∈ S | T ∈ L(s)} where T is
overloaded to be a set of states and a label in AP . The set
♦ T = {π ∈ Paths(sI , T ) | ∀0 ≤ i < |π|• π(i) 6∈ T } shall
be prefix–free and contain all paths of R that visit a target
state. Analogously, the set ¬♦ T = {π ∈ PathsR (sI ) | ∀i ≥
0• π(i) 6∈ T } contains all paths that never reach a state in T .
Let us first consider reward objectives for fully probabilistic
models, i.e., RMCs. The expected reward for a finite set of

µ ∈JP K(σ)

In other words, wp[P ](f ) represents the tightest lower bound
that can be guaranteed for the expected value of f (we assume
that non-deterministic choices are resolved demonically2, attempting to minimize the expected value of f ).
In the following, we use the term expectation to refer to a
random variable mapping program states to real values. The
expectation transformer wp then transforms a post–expectation
f into a pre–expectation wp[P ](f ) and can be defined inductively, following the rules in Figure 2 (second column),
Page 7. The transformer wp also admits a liberal variant wlp,
which differs from wp on the way in which non–termination
is treated.
Formally, the transformer wp operates on unbounded expectations in E = S → R∞
≥0 and wlp operates on bounded
expectations in E≤1 = S → [0, 1]. Here R∞
≥0 denotes the
set of non–negative real values with the adjoined ∞ value.
In order to guarantee the well–definedness of wp and wlp we
need to provide E and E≤1 the structure of a directed–complete
partial order. Expectations are ordered pointwise, i.e. f ⊑ g
iff f (σ) ≤ g(σ) for every state σ ∈ S. The least upper bound
of directed subsets is also defined pointwise.
In what follows we use bold fonts for constant expectations,
e.g. 1 denotes the constant expectation 1. Given an arithmetical
expression E over program variables we simply write E for
the expectation that in state σ returns σ(E). Given a Boolean
expression G over program variables we use χG to denote
the {0, 1}–valued expectation that returns 1 if σ |= G and 0
otherwise.
b) MDPs and conditional expected rewards: Let V be
a finite set of parameters. A parametric distribution
over a
P
countable set S is a function µ : S → ZV with s∈S µ(s) =
1, where ZV denotes the set of all polynomials3 over V .
Distr (S) denotes the set of parametric distributions over S.
2 Demonic schedulers induce the most pessimistic expected outcome while
in [20] also angelic schedulers are considered which guarantee the most
optimistic outcome.
3 Although parametric distributions are defined as polynomials over the
parameters, we only use p and 1 − p for p ∈ V

3

paths ♦ T ∈ PathsR
fin is
X

ExpRewR (♦ T ) ,

the observe statements do not only block further execution
but condition resulting distributions on the program’s state to
only those executions satisfying the observations. Consider
two small example programs:

PrR (π̂) · r(π̂) .

π̂∈♦ T

For a reward bounded by one, the notion of the liberal
expected reward also takes the mere probability of not reaching
the target states into account:

{x := 0} [p] {x := 1};
{y := 0} [q] {y := −1}

{x := 0} [p] {x := 1};
{y := 0} [q] {y := −1};
observe x + y = 0

LExpRewR (♦ T ) , ExpRewR (♦ T ) + PrR (¬♦ T )

The left program establishes that the probability of x=0
is p, whereas for the right program this probability is
pq
pq+(1−p)(1−q) . The left program admits all (four) runs, two of
which satisfy x=0. Due to the observe statement requiring
x+y=0, the right program, however, admits only two runs
(x=0, y=0 and x=1, y=−1), satisfying x=0.
In Section V we will focus on the subclass of fully probabilistic programs in cpGCL, which we denote cpGCL⊠ .

A liberal expected reward will later represent the probability
of either establishing some condition or not terminating.
To explicitly exclude the probability of paths that reach
“undesired” states, we let U = {s ∈ S | ∈ L(s)} and define
the conditional expected reward for the condition ¬♦ U by4
CExpRewR (♦ T | ¬♦ U ) ,

ExpRewR (♦ T ∩ ¬♦ U )
.
PrR (¬♦ U )

For details about conditional probabilities and expected rewards, we refer to [22]. Conditional liberal expected rewards
are defined by
CLExpRewR (♦ T | ¬♦ U ) ,

IV. O PERATIONAL S EMANTICS

ExpRew (♦ T ) ,

LExpRew (♦ T ∩ ¬♦ U )
.
PrR (¬♦ U )

h i
hinit i

inf

S∈Sched R

ExpRew

R

S

S∈Sched R

CExpRew
S

=

inf

S∈Sched R

X

XXXX

hsink i

(♦ T ) .
diverge

Terminating runs eventually end up in the hsink i state; other
runs are diverging (never reach hsink i). A program terminates
either successfully, i.e. a run passes a X–labelled state, or
terminates due to a false observation, i.e. a run passes h i.
Squiggly arrows indicate reaching certain states via possibly
multiple paths and states; the clouds indicate that there might
be several states of the particular kind. The X–labelled states
are the only ones with positive reward. Note that the sets of
paths that eventually reach h i, eventually reach X, or diverge,
are pairwise disjoint.

CExpRewR (♦ T | ¬♦ U )
inf

X

S

The scheduler for conditional expected reward properties minimizes the value of the quotient:

,

cpGCL

This section presents an operational semantics for cpGCL
using RMDPs as underlying model inspired by [10]. Schematically, the operational RMDP of a cpGCL program shall have
the following structure:

R

Reward objectives for RMDPs are now defined using a demonic scheduler S ∈ Sched R minimizing probabilities and
expected rewards for the induced RMC SR. For the expected
reward this yields
R

FOR

ExpRew

R

R

SR

Pr

(♦ T | ¬♦ U )

(♦ T ∩ ¬♦ U )
(¬♦ U )

The liberal reward notions for RMDPS are analogous. Regarding the quotient minimization we assume “ 00 < 0” as we see
0
0 —being undefined—to be less favorable than 0.
III. C ONDITIONAL pGCL

Definition IV.1 (Operational cpGCL semantics). The operational semantics of P ∈ cpGCL for σ ∈ S and f ∈ E is
the RMDP Rfσ JP K = (S, hP, σi, Act, P, L, r), such that S
is the smallest set of states with h i ∈ S, hsink i ∈ S, and
hQ, τ i, h↓, τ i ∈ S for Q ∈ pGCL and τ ∈ S. hP, σi ∈ S is
the initial state. Act = {left , right } is the set of actions. P is
formed according to the rules given in Figure 1. The labelling
and the reward function are given by:

{X},
if s = h↓, τ i, for some τ ∈ S



{sink }, if s = hsink i
L(s) ,

{ },
if s = h i



∅,
otherwise,

As mentioned in Section II, pGCL programs can be considered as distribution transformers. Inspired by [2], we extend
pGCL with observe statements to obtain conditional pGCL
(cpGCL, for short). This is done by extending the syntax
of pGCL (p. 2) with observe G where G is a Boolean
expression over the program variables. When a program’s execution reaches observe G with a current variable valuation
σ 6|= G, further execution of the program is blocked as with
an assert statement [23]. In contrast to assert, however,
4 Note that strictly formal one would have to define the intersection of sets
of finite and possibly infinite paths by means of a cylinder set construction
considering all infinite extensions of finite paths.

4

(terminal)

(skip)

h↓, σi −→ hsink i

(abort)

(undesired)

h i −→ hsink i
σ |= G
σ 6|= G
(observe)
(assign)
hx := E, σi −→ h↓, σ[x ← JEKσ ]i
hobserve G, σi −→ h↓, σi
hobserve G, σi −→ h i
hP, σi −→ h i
hP, σi −→ µ
(concatenate)
, where ∀P ′ . ν(hP ′ ; Q, σ′ i) := µ(hP ′ , σ′ i)
h↓; Q, σi −→ hQ, σi
hP ; Q, σi −→ h i
hP ; Q, σi −→ ν
σ 6|= G
σ |= G
(if)
hite (G) {P } {Q}, σi −→ hP, σi
hite (G) {P } {Q}, σi −→ hQ, σi
σ 6|= G
σ |= G
(while)
hwhile (G) {P }, σi −→ hP ; while (G) {P }, σi
hwhile (G) {P }, σi −→ h↓, σi
(prob. choice)

h{P } [p] {Q}, σi −→ ν

(non–det. choice)

hskip, σi −→ h↓, σi

habort, σi −→ habort, σi

, where ν(hP, σi) := p, ν(hQ, σi) := 1 − p

left

right

h{P }  {Q}, σi −−−→ hP, σi

h{P }  {Q}, σi −−−−→ hQ, σi

Fig. 1. Rules for the construction of the operational RMDPs. If not stated otherwise, hsi−→hti is a shorthand for hsi−→µ ∈ Distr (S) with µ(hti) = 1. A
terminal state of the form h↓, σi indicates successful termination. Terminal states and h i go to the hsink i state. skip without context terminates successfully.
abort self–loops, i.e. diverges. x := E alters the variable valuation according to the assignment then terminates successfully. For the concatenation, h↓; Q, σi
indicates successful termination of the first program, so the execution continues with hQ, σi. If for P ; Q the execution of P leads to h i, P ; Q does so, too.
Otherwise, for hP, σi−→µ, µ is lifted such that Q is concatenated to the support of µ. If for the conditional choice σ |= G holds, P is executed, otherwise
Q. The case for while is similar. For the probabilistic choice, a distribution ν is created according to p. For {P }  {Q}, we call P the left choice and Q
the right choice for actions left, right ∈ Act. For the observe statement, if σ |= G observe acts like skip. Otherwise, the execution leads directly to
h i indicating a violation of the observe statement.

r(s) ,

(

f (τ ),
0,

hP, σI i

if s = h↓, τ i, for some τ ∈ S
otherwise

q

where a state of the form h↓, τ i denotes a terminal state in
which no program is left to be executed.

hP4 ; P3 , σI i

To determine the conditional expected outcome of program
P given that all observations are true, we need to determine
the expected reward to reach hsink i from the initial state
conditioned on not reaching h i under a demonic scheduler.
f
For Rfσ JP K this is given by CExpRewRσ JP K (♦sink | ¬♦ ).
Recall for the condition ¬♦ that all paths not eventually
reaching h i either diverge (thus collect reward 0) or pass by
a X–labelled state and eventually reach hsink i. This gives us:

h↓; P3 , σI [x/5]i

CExpRew

Rfσ JP K

5

=

inf

(♦sink ∩ ¬♦ )

S

f
S∈Sched Rσ JP K

Rfσ JP K

Pr

(¬♦ )

S

=

inf

f
S∈Sched Rσ JP K

ExpRew

Rfσ JP K

(♦sink )

S

Pr

Rfσ JP K

right

hP2 ; P3 , σI i

hP3 , σI [x/5]i

h↓; P3 , σI [x/2]i

h↓, σI [x/5]i

h P3 , σI [x/2]i

h i

The only state with positive reward is s′ := h↓, σI [x/5]i and
its reward is indicated by number 5. Assume first a scheduler
choosing action left in state hP1 ; P3 , σI i. In the induced RMC
the only path accumulating positive reward is the path π going
from hP, σI i via s′ to hsink i with r(π) = 5 and Pr(π) = q.
This gives an expected reward of 5 · q. The overall probability
of not reaching h i is also q. The conditional expected reward
of eventually reaching hsink i given that h i is not reached
is hence 5·q
= 5. Assume now the minimizing scheduler
q
choosing right at state hP1 ; P3 , σI i. In this case there is
no path having positive accumulated reward in the induced
RMC, yielding an expected reward of 0. The probability of
not reaching h i is also 0. The conditional expected reward in
this case is undefined (0/0) thus the right branch is preferred
over the left branch.
In general, the operational RMDP is not finite, even if the
program terminates almost–surely (i.e. with probability 1).

S

Rfσ JP K

hP1 ; P3 , σI i

hsink i

(♦sink | ¬♦ )

ExpRew

left

1−q

(¬♦ )

f

This is analogous for CLExpRewRσ JP K (♦sink | ¬♦ ).
Example IV.1. Consider the program P ∈ cpGCL:
{{x := 5}  {x := 2}} [q] {x := 2};
observe x > 3
where with parametrized probability q a non–deterministic
choice between x being assigned 2 or 5 is executed, and
with probability 1 − q, x is directly assigned 2. Let for
readability P1 = {x := 5}  {x := 2}, P2 = x := 2,
P3 = observe x > 3, and P4 = x := 5. The operational
RMDP RxσI JP K for an arbitrary initial variable valuation σI
and post–expectation x is depicted below.

V. D ENOTATIONAL S EMANTICS

FOR

cpGCL⊠

This section presents an expectation transformer semantics
for the fully probabilistic fragment cpGCL⊠ of cpGCL. We

5

cwp[P1 ] and cwp[P2 ], weighted according to p. cwp[while
(G) {P ′ }] is defined using standard fixed point techniques.6
The cwlp transformer follows the same rules as cwp, except
for the abort and while statements. cwlp[abort] takes any
post–expectation to pre–expectation (1, 1) and cwlp[while
(G) {P }] is defined as a greatest fixed point rather than a
least fixed point.

formally relate this to the wp/wlp–semantics of pGCL as well
as to the operational semantics from the previous section.
A. Conditional Expectation Transformers
An expectation transformer semantics for the fully probabilistic fragment of cpGCL is defined using the operators:
cwp[ · ] : E × E≤1 → E × E≤1
cwlp[ · ] : E≤1 × E≤1 → E≤1 × E≤1

Example V.1. Consider the program P ′
{x := 0} [1/2] {x := 1};

ite (x = 1) {y := 0} [1/2] {y := 2}

{y := 0} [4/5] {y := 3} ;
observe y = 0

1

These functions can intuitively be viewed as the counterpart
of wp and wlp respectively, as shortly shown. The weakest
conditional pre–expectation cwp[P ](f ) of P ∈ cpGCL⊠ with
respect to post–expectation f is now given as
cwp[P ](f ) ,

2

3

Assume we want to compute the conditional expected value
of the expression 10+x given that the observation y=0 is
passed. This expected value is given by cwp[P ′ ](10+x) and
the computation of cwp[P ′ ](10+x, 1) goes as follows:

cwp1 [P ](f, 1)
,
cwp2 [P ](f, 1)

where cwp1 [P ](f, g) (resp. cwp2 [P ](f, g)) denotes the first
(resp. second) component of cwp[P ](f, g) and 1 is the constant expectation one. The weakest liberal conditional pre–
expectation cwlp[P ](f ) is defined analogously. In words,
cwp[P ](f )(σ) represents the expected value of f with respect
to the distribution of final states obtained from executing P in
state σ, given that all observe statements occurring along
the runs of P were satisfied. The quotient defining cwp[P ](f )
is interpreted is the same way as the quotient

cwp[P ′ ](10+x, 1)
′
= cwp[P1-2
](cwp[observe y = 0](10+x, 1))
′
= cwp[P1-2
](f, g) where (f, g) = χy=0 · (10+x, 1)
′
= cwp[P1-1 ](cwp[ite (x=1) {. . .} {. . .}](f, g))
′
= cwp[P1-1
](χx=1 · (h, i) + χx6=1 · (h′ , i′ )) where
(h, i) = cwp[{y := 0} [1/2] {y := 2}](f, g)

=

1
2

=

4
5

· (10 + x, 1) , and
(h , i ) = cwp[{y := 0} [4/5] {y := 3}](f, g)

Pr(A ∩ B)
Pr(B)

′

encoding the conditional probability Pr(A|B). However, here
we measure the expected value of random variable f 5 . The
denominator cwp2 [P ](f, 1)(σ) measures the probability that
P satisfies all the observations (occurring along valid runs)
from the initial state σ. If cwp2 [P ](f, 1)(σ) = 0, program P
is infeasible from state σ and in this case cwp[P ](f )(s) is not
well–defined (due to the division by zero). This corresponds
to the conditional probability Pr(A|B) being not well–defined
when Pr(B) = 0.
The operators cwp and cwlp are defined inductively on the
program structure, see Figure 2 (last column). Let us briefly
explain this. cwp[skip] behaves as the identity since skip
has no effect on the program state. cwp[abort] maps any pair
of post–expectations to the pair of constant pre–expectations
(0, 1). Assignments induce a substitution on expectations,
i.e. cwp[x := E] maps (f, g) to pre–expectation (f [x/E],
g[x/E]), where h[x/E](σ) = h(σ[x/E]) and σ[x/E] denotes the usual variable update on states. cwp[P1 ; P2 ] is
obtained as the functional composition (denoted ◦) of cwp[P1 ]
and cwp[P2 ]. cwp[observe G] restricts post–expectations to
those states that satisfy G; states that do not satisfy G
are mapped to 0. cwp[ite (G) {P1 } {P2 }] behaves either
as cwp[P1 ] or cwp[P2 ] according to the evaluation of G.
cwp[{P1 } [p] {P2 }] is obtained as a convex combination of

=
=

′

· (10 + x, 1)

1
2

· 54 · (10 + 0, 1) + 12 · 12 · (10



4, 52 + 11
, 41 = 27
, 13
4
4 20

+ 1, 1)

and the conditional expected
Then cwp[P ′ ](10+x) = 135
13
value of 10+x is approximately 10.38.
In the rest of this section we investigate some properties of
the expectation transformer semantics of cpGCL⊠ . As every
fully probabilistic pGCL program is contained in cpGCL⊠ ,
we first study the relation of the cw(l)p– to the w(l)p–
semantics of pGCL. To that end, we extend the weakest
(liberal) pre–expectation operator to cpGCL as follows:
wp[observe G](f ) = χG ·f

wlp[observe G](f ) = χG ·f .

To relate the cw(l)p– and w(l)p–semantics we heavily rely
on the following result which says that cwp (resp. cwlp) can
be decoupled as the product wp × wlp (resp. wlp × wlp).
Theorem V.1 (Decoupling of cw(l)p). For P ∈ cpGCL⊠ ,
f ∈ E, and f ′ , g ∈ E≤1 :

cwp[P ](f, g) = wp[P ](f ), wlp[P ](g)

cwlp[P ](f ′ , g) = wlp[P ](f ), wlp[P ](g)
6 We define cwp[while (G) {P }] by the least fixed point w.r.t. the order
(⊑, ⊒) in E×E≤1 . This way we encode the greatest fixed point in the second
component w.r.t. the order ⊑ over E≤1 as the least fixed point w.r.t. the dual
order ⊒.

5 In fact, cwp[P ](f )(σ) corresponds to the notion of conditional expected
value or in simpler terms, the expected value over a conditional distribution.

6

P

wp[P ](f )

cwp[P ](f, g)

skip
abort
x := E

f
0

(f, g)
(0, 1)

observe G

f [x/E]
χG · f

(f [x/E], g[x/E])
χG · (f, g)

P1 ; P2
ite (G) {P1 } {P2 }

(wp[P1 ] ◦ wp[P2 ])(f )
χG · wp[P1 ](f ) + χ¬G · wp[P2 ](f )

(cwp[P1 ] ◦ cwp[P2 ])(f, g)
χG · cwp[P1 ](f, g) + χ¬G · cwp[P2 ](f, g)

{P1 } [p] {P2 }
{P1 }  {P2 }

P

p · wp[P1 ](f ) + (1 − p) · wp[P2 ](f )
λσ • min{wp[P
1 ](f )(σ), wp[P2 ](f

 )(σ)}
′ ˆ
ˆ
µ f • χG · wp[P ](f ) + χ¬G · f

wlp[P ](f )

p · cwp[P1 ](f, g) + (1 − p) · cwp[P2 ](f, g)
— not defined —

µ⊑,⊒ (fˆ, ĝ)• χG · cwp[P ′ ](fˆ, ĝ) + χ¬G · (f, g)

abort

1

(1, 1)

while (G) {P ′ }

ν fˆ•

while (G) {P ′ }



χG · wp[P ′ ](fˆ) + χ¬G · f



cwlp[P ](f, g)
ν ⊑,⊑ (fˆ, ĝ)•




χG · cwp[P ′ ](fˆ, ĝ) + χ¬G · (f, g)

Fig. 2. Definitions for the wp/wlp and cwp/cwlp operators. The wlp (cwlp) operator differs from wp (cwp) only for abort and the while–loop. A
scalar multiplication a · (f, g) is meant componentwise yielding (a · f, a · g). Likewise an addition (f, g) + (f ′ , g ′ ) is also meant componentwise yielding
(f + f ′ , g + g ′ ).

cpGCL⊠ . By Theorem V.1, the transformers cwlp[P ] and
cwlp[P ] can be recast as:

Proof. By induction on the program structure. See Appendix B
for details.
Let pGCL⊠ denote the fully probabilistic fragment of pGCL.
We show that the cwp–semantics is a conservative extension
of the wp–semantics for pGCL⊠ . The same applies to the
weakest liberal pre–expectation semantics.

f 7→

wp[P ](f )
wlp[P ](1)

and f 7→

wlp[P ](f )
,
wlp[P ](1)

respectively. Recall that wlp[P ](1) yields the weakest pre–
expectation under which P either does not terminate or
does terminate while passing all observe–statements. An
alternative is to normalize using wp in the denominator instead
of wlp, yielding:

Theorem V.2 (Compatibility with the w(l)p–semantics). For
P ∈ pGCL⊠ , f ∈ E, and g ∈ E≤1 :
wp[P ](f ) = cwp[P ](f ) and wlp[P ](g) = cwlp[P ](g)

f 7→

Proof. By Theorem V.1 and the fact that cwlp[P ](1) = 1 (see
Lemma V.3).

wp[P ](f )
wp[P ](1)

and

f 7→

wlp[P ](f )
wp[P ](1)

Proof. Using Theorem V.1 one can show that the transformers cwp/cwlp inherit these properties from the transformers
wp/wlp. For details we refer to Appendix D.

The transformer on the right is not meaningful, as the denominator wp[P ](1)(σ) may be smaller than the numerator
wlp[P ](f )(σ) for some state σ ∈ S. This would lead to
probabilities exceeding one. The transformer on the left normalizes w.r.t. the terminating executions. This interpretation
corresponds to the semantics of the probabilistic programming
language R2 [7], [14] and is only meaningful if programs
terminate almost surely (i.e. with probability one).
A noteworthy consequence of adopting this semantics is that
observe G is equivalent to while (¬G) {skip} [14], see the
discussion in Section VI.
Let us briefly compare the four alternatives. To that end
consider the program P below


abort [1/2] {x := 0} [1/2] {x := 1};

We conclude this section by discussing alternative approaches
for providing an expectation transformer semantics for P ∈

P tosses a fair coin and according to the outcome either
diverges or tosses a fair coin twice and observes at least
once heads (y=0 ∨ x=0). We measure the probability that

We now investigate some elementary properties of cwp and
cwlp such as monotonicity and linearity.
Lemma V.3 (Elementary properties of cwp and cwlp). For
every P ∈ cpGCL⊠ with at least one feasible execution
(from every initial state), post–expectations f, g ∈ E and non–
negative real constants α, β:
i) f ⊑ g implies cwp[P ](f ) ⊑ cwp[P ](g) and likewise for
cwlp.
ii) cwp[P ](α · f + β · g) = α · cwp[P ](f ) + β · cwp[P ](g).
iii) cwp[P ](0) = 0 and cwlp[P ](1) = 1.

{y := 0} [1/2] {y := 1}; observe x = 0 ∨ y = 0

7

the outcome of the last coin toss was heads according to each
transformer:
2
wp[P ](χy=0 )
=
wlp[P ](1)
7

wlp[P ](χy=0 )
6
=
wlp[P ](1)
7

wp[P ](χy=0 )
2
=
wp[P ](1)
3

wlp[P ](χy=0 )
=2
wp[P ](1)

VI. A PPLICATIONS
In this section we study approaches that make use of our
semantics in order to analyze fully probabilistic programs with
observations. We first present a program transformation based
on hoisting observe statements in a way that probabilities
of conditions are extracted, allowing for a subsequent analysis
on an observation–free program. Furthermore, we discuss how
observations can be replaced by loops and vice versa. Finally,
we use a well–known case study to demonstrate the direct
applicability of our cwp–semantics.

](f )
As mentioned before, the transformer f 7→ wlp[P
wp[P ](1) is
not significant as it yields a “probability” exceeding one.
Note that our cwp–semantics yields a probability of y=0 on
termination—while passing all observe–statements—of 27 .
As shown before, this is a conservative and natural extension
of the wp–semantics. This does not apply to the R2–semantics,
as this would require an adaptation of rules for abort and
while.

A. Observation Hoisting
In what follows we give a semantics–preserving transformation for removing observations from cpGCL⊠ programs.
Intuitively, the program transformation “hoists” the observe
statements while updating the probabilities in case of probabilistic choices. Given P ∈ cpGCL⊠ , the transformation
delivers a semantically equivalent observe–free program
P̂ ∈ pGCL⊠ and—as a side product—an expectation ĥ ∈ E≤1
that captures the probability of the original program to establish all observe statements. For intuition, reconsider the
program from Example V.1. The transformation yields the
program

B. Correspondence Theorem
We now investigate the connection between the operational
semantics of Section IV (for fully probabilistic programs) and
the cwp–semantics. We start with some auxiliary results. The
first result establishes a relation between (liberal) expected
rewards and weakest (liberal) pre–expectations.
Lemma V.4. For P ∈ cpGCL⊠ , f ∈ E, g ∈ E≤1 , and σ ∈ S:
f

ExpRewRσ JP K (♦hsink i) = wp[P ](f )(σ)
LExpRew

Rgσ JP K

(♦hsink i) = wlp[P ](g)(σ)

(i)

{x := 0} [8/13] {x := 1};
ite (x = 1) {{y := 0} [1] {y := 2}}
{{y := 0} [1] {y := 3}}

(ii)

Proof. By induction on P , see Appendix E and F.
The next result establishes that the probability to never reach
h i in the RMC of program P coincides with the weakest
liberal pre–expectation of P w.r.t. post–expectation 1 :

13
. By eliminating dead code in both
and expectation ĥ = 20
probabilistic choices and coalescing the branches in the conditional, we can simplify the program to:

Lemma V.5. For P ∈ cpGCL⊠ , g ∈ E≤1 , and σ ∈ S:

{x := 0} [8/13] {x := 1}; y := 0

g

PrRσ JP K (¬♦ ) = wlp[P ](1)(σ)

As a sanity check note that the expected value of 10+x in this
8
5
program is equal to 10 · 13
+ 11 · 13
= 135
13 , which agrees with
the result obtained in Example V.1 by analyzing the original
program. Formally, the program transformation is given by a
function

Proof. See Appendix G
We now have all prerequisites in order to present the main
result of this section: the correspondence between the operational and expectation transformer semantics of cpGCL⊠ programs. It turns out that the weakest (liberal) pre–expectation
cwp[P ](f )(σ) (respectively cwlp[P ](f )(σ)) coincides with the
conditional (liberal) expected reward in the RMC Rfσ JP K of
terminating while never violating an observe-statement, i.e.,
avoiding the h i states.

T : cpGCL⊠ × E≤1 → cpGCL⊠ × E≤1 .
To apply the transformation to a program P we need to
determine T (P, 1), which gives the semantically equivalent
program P̂ and the expectation ĥ.
The transformation is defined in Figure 3 and works by
inductively computing the weakest pre–expectation that guarantees the establishment of all observe statements and
updating the probability parameter of probabilistic choices
so that the pre–expectations of their branches are established
in accordance with the original probability parameter. The
computation of these pre–expectations is performed following
the same rules as the wlp operator. The correctness of the
transformation is established by the following Theorem, which
states that a program and its transformed version share the
same terminating and non–terminating behavior.

Theorem V.6 (Correspondence theorem). For P ∈ cpGCL⊠ ,
f ∈ E, g ∈ E≤1 and σ ∈ S,
f

CExpRewRσ JP K (♦sink | ¬♦ ) = cwp[P ](f )(σ)
g

CLExpRewRσ JP K (♦sink | ¬♦ ) = cwlp[P ](g)(σ) .
Proof. The proof makes use of Lemmas V.4, V.5, and Theorem V.1. For details see Appendix H.
Theorem V.6 extends a previous result [10] that established a
connection between an operational and the wp/wlp semantics
for pGCL programs to the fully probabilistic fragment of
cpGCL.

8

while(rerun) { x1 , . . . , xn := s1 , . . . , sn ; P ′ }

Theorem VI.1 (Program Transformation Correctness). Let
P ∈ cpGCL⊠ admit at least one feasible run for every initial
state and T (P, 1) = (P̂ , ĥ). Then for any f ∈ E and g ∈ E≤1 ,

Here, s1 , . . . , sn are fresh variables and x1 , . . . , xn are all
program variables of P . The first assignment stores the initial
state in the variables si and the first line of the loop body,
ensures that the loop always starts with the same (initial)
values.

wp[P̂ ](f ) = cwp[P ](f ) and wlp[P̂ ](g) = cwlp[P ](g).
Proof. See Appendix I.
A similar program transformation has been given in [7].
Whereas they use random assignments to introduce randomization in their programming model, we use probabilistic
choices. Consequently, they can hoist observe statements
only until the occurrence of a random assignment, while we
are able to hoist observe statements through probabilistic
choices and completely remove them from programs. Another
difference is that their semantics only accounts for terminating
program behaviors and thus can guarantee the correctness of
the program transformation for terminating behaviors only.
Our semantics is more expressive and enables establishing the
correctness of the program transformation for non–terminating
program behavior, too.

Theorem VI.2. Let programs P and P ′′ be as above. Then
cwp[P ](f ) = wp[P ′′ ](f ) .
Proof. See Appendix J.
Example VI.1. Consider the following cpGCL program:
{x := 0} [p] {x := 1}; {y := 0} [p] {y := 1}
observe x 6= y;
We apply the program transformation to it and obtain:
s1 , s2 := x, y; rerun := true;
while(rerun){
x, y := s1 , s2 ; rerun := false;
{x := 0} [p] {x := 1};

B. Replacing Observations by Loops
For semantics that normalize with respect to the terminating
behavior of programs, observe statements can readily be
replaced by a loop [24], [14]. In our setting a more intricate
transformation is required to eliminate observations from
programs. Briefly stated, the idea is to restart a violating
run from the initial state until it satisfies all encountered
observations. To achieve this we consider a fresh variable
rerun and transform a given program P ∈ cpGCL⊠ into a
new program P ′ as described below:
observe G
abort
while (G) {. . .}

{y := 0} [p] {y := 1};
if(x = y){ rerun := true}
}
This program is simplified by a data flow analysis: The variables s1 and s2 are irrelevant because x and y are overwritten
in every iteration. Furthermore, there is only one observation
so that its predicate can be pushed directly into the loop’s
guard. Then the initial values of x and y may be arbitrary
but they must be equal to make sure the loop is entered. This
gives the final result

→ ite (¬G) {rerun := true} {skip}
→ ite (¬rerun) {abort} {skip}

x, y := 0, 0;

→ while (G ∧ ¬rerun) {. . .}

while(x = y){
{x := 0} [p] {x := 1}; {y := 0} [p] {y := 1}

For conditional and probabilistic choice, we apply the above
rules recursively to the subprograms.
The aim of the transformation is twofold. First, the program
P ′ flags the violation of an observe statement through the
variable rerun. If a violation occurs, rerun is set to true
while in contrast to the original program we continue the
program execution. As a side effect, we may introduce some
subsequent diverging behavior which would not be present in
the original program (since the execution would have already
been blocked). The second aim of the transformation is to
avoid this possible diverging–behavior. This is achieved by
blocking while–loops and abort statements once rerun is
set to true.
Now we can get rid of the observations in P by repeatedly
executing P ′ from the same initial state till rerun is set to
false (which would intuitively correspond to P passing all its
observations).
This is implemented by program P ′′ below:

}
This program is a simple algorithm that repeatedly uses a
biased coin to simulate an unbiased coin flip. A proof that x is
indeed distributed uniformly over {0, 1} has been previously
shown e.g. in [25].
Theorem VI.2 shows how to define and effectively calculate
the conditional expectation using a straightforward program
transformation and the well established notion of wp. However
in practice it will often be infeasible to calculate the fixed point
of the outer loop or to find a suitable loop invariant – even
though it exists.
C. Replacing Loops by Observations
In this section we provide an overview on how the aforementioned result can be “applied backwards” in order to
replace a loop by an observe statement. This is useful as
it is easier to analyze a loop–free program with observations

s1 , . . . , sn := x1 , . . . , xn ; rerun := true;

9

T (skip, f )

= (skip, f )

T (abort, f )
T (x := E, f )

= (abort, 1)
= (x := E, f [E/x])

T (observe G, f )
= (skip, χG · f )
T (ite (G) {P } {Q}, f ) = (ite (G) {P ′ } {Q′}, χG · fP + χ¬G · fQ )
where (P ′ , fP ) = T (P, f ), (Q′ , fQ ) = T (Q, f )
T ({P } [p] {Q}, f )
T (while (G) {P }, f )
T (P ; Q, f )

= ({P ′ } [p′ ] {Q′ }, p · fP + (1−p) · fQ )
p·fP
where (P ′ , fP ) = T (P, f ), (Q′ , fQ ) = T (Q, f ), and p′ = p·fP +(1−p)·f
Q
= (while (G) {P ′ }, f ′ )
where f ′ = ν X • (χG · (π2 ◦ T )(P, X) + χ¬G · f ) , and (P ′ , ) = T (P, f ′ )
= (P ′ ; Q′ , f ′′ ) where (Q′ , f ′ ) = T (Q, f ), (P ′ , f ′′ ) = T (P, f ′ )

Fig. 3. Program transformation for eliminating observe statements in cpGCL⊠ .

delivered := 0; counter := 1

than a program with loops for which fixed points need to be
determined.
The transformation presented in Section VI-B yields programs of a certain form: In every loop iteration the variable
values are initialized independently from their values after
the previous iteration. Hence the loop iterations generate a
sequence of program variable valuations that are independent
and identically distributed (iid loop), cf. Example VI.1 where
no “data flow” between iterations of the loop occurs.
In general, if loop = while(G){P } is an iid loop we can
obtain a program Q = P ; observe ¬G with

loop :

[p]
{delivered := 1}
};
observe(counter ≤ k)
Our goal is to determine the probability of a message not
being intercepted by a collaborator. We condition this by the
observation that a message is forwarded at most k times.
Note that the operational semantics of P produce an infinite
parametric RMC since the value of k is fixed but arbitrary.
Using Theorem V.1 we express the probability that a message
is not intercepted given that it was rerouted no more than k
times by

wp[loop](f ) = cwp[Q](f )
for any expectation f ∈ E. To see this, apply Theorem VI.2
to program Q. Let the resulting program be loop’. As in
Example VI.1, note that there is only one observe statement
at the end of loop’ and furthermore there is no data flow
between iterations of loop’. Hence by the same simplification
steps we arrive at the desired program loop.
D. The Crowds Protocol
To demonstrate the applicability of the cwp-semantics to
a practical example, consider the Crowds-protocol [18]. A
set of nodes forms a fully connected network called the
crowd. Crowd members would like to exchange messages
with a server without revealing their identity to the server.
To achieve this, a node initiates communication by sending its
message to a randomly chosen crowd member, possibly itself.
Upon receiving a message a node probabilistically decides to
either forward the message once again to a randomly chosen
node in the network or to relay it to the server directly.
A commonly studied attack scenario is that some malicious
nodes called collaborators join the crowd and participate in the
protocol with the aim to reveal the identity of the sender. The
following cpGCL-program P models this protocol where p is
the forward probability and c is the fraction of collaborating
nodes in the crowd. The initialization corresponds to the
communication initiation.
init :

while(delivered = 0) {

counter := counter + 1;
{intercepted := 1} [c] {skip}

cwp[P ]([¬intercepted]) =

wp[P ]([¬intercepted])
wlp[P ](1)

(1)

The computation of this quantity requires to find fixed points,
cf. Appendix K for details. As a result we obtain a closed
form solution parametrized in p, c, and k:
(1 − c)(1 − p)

1 − (p(1 − c))k
1
·
1 − p(1 − c)
1 − pk

The automation of such analyses remains a challenge and
is part of ongoing and future work.
VII. D ENOTATIONAL S EMANTICS

FOR

F ULL cpGCL

In this section we argue why (under mild assumptions) it
is not possible to come up with a denotational semantics in
the style of conditional pre–expectation transformers (CPETs
for short) for full cpGCL. To show this, it suffices to consider
a simple fragment of cpGCL containing only assignments,
observations, probabilistic and non–deterministic choices. Let
x be the only program variable that can be written or read in
this fragment. We denote this fragment by cpGCL− . Assume

{intercepted := 1} [c] {intercepted := 0};

10

cwp∗ [P2+ε ] = d2+ε , with Jd2+ε K = 2 + ε
cwp∗ [observe false] = of, with JofK = ⊥

D is some appropriate domain for representing conditional
expectations of the program variable x with respect to some
fixed initial state σ0 and let J · K : D → R ∪ {⊥} be an
interpretation function such that for any d ∈ D we have that
JdK is equal to the (possibly undefined) conditional expected
value of x.

for some appropriate d1 , d2 , d2+ε , of ∈ D. By Definition
VII.1, cwp∗ being inductive requires the existence of a function K, such that
cwp∗ [P4 ] = K (cwp∗ [observe false], 1/2, cwp∗ [P2+ε ])

Definition VII.1 (Inductive CPETs). A CPET is a function
cwp∗ : cpGCL− → D xsuch that for any P ∈ cpGCL− ,
Jcwp[P ]K = CExpRewRσ0 JP K (♦ sink | ¬♦ ). cwp∗ is called
inductive, if there exists some function K : cpGCL− × [0, 1]×
cpGCL− → D such that for any P1 , P2 ∈ cpGCL− ,
∗

∗

= K(of, 1/2, d2+ε ) .
In addition, there must be an N with:
cwp∗ [P5 ] = N (cwp∗ [P2 ], cwp∗ [P4 ])
= N (d2 , K(of, 1/2, d2+ε )) .

∗

cwp [{P1 } [p] {P2 }] = K(cwp [P1 ], p, cwp [P2 ]) ,
and some function N : cpGCL− × cpGCL− → D with
∗

∗

Since P4 is a probabilistic choice between an infeasible branch
and P2+ε , the expected value for x has to be rescaled to the
feasible branch. Hence P4 yields Jcwp∗ [P4 ]K = 2 + ε, whereas
Jcwp∗ [P2 ]K = 2. Thus:

∗

cwp [{P1 }  {P2 }] = N (cwp [P1 ], cwp [P2 ]) ,
where ∀d1 , d2 ∈ D : N (d1 , d2 ) ∈ {d1 , d2 }.
This definition suggests that the conditional pre–expectation
of {P1 } [p] {P2 } is determined only by the conditional pre–
expectation of P1 , the conditional pre–expectation of P2 , and
the probability p. Furthermore the above definition suggests
that the conditional pre–expectation of {P1 }  {P2 } is also
determined by the conditional pre–expectation of P1 and the
conditional pre–expectation of P2 only. Consequently, the
non–deterministic choice can be resolved by replacing it either
by P1 or P2 . While this might seem like a strong limitation, the
above definition is compatible with the interpretation of non–
deterministic choice as demonic choice: The choice is deterministically driven towards the worst option. The requirement
N (d1 , d2 ) ∈ {d1 , d2 } is also necessary for interpreting non–
deterministic choice as an abstraction where implementational
details are not important.
As we assume a fixed initial state and a fixed post–
expectation, the non–deterministic choice turns out to be
deterministic once the pre–expectations of P1 and P2 are
known. Under the above assumptions (which do apply to the
wp and wlp transformers) we claim:

Jd2 K

JK(of, 1/2, d2+ε )K

(2)

As non–deterministic choice is demonic, we have:
cwp∗ [P5 ] = N (d2 , K(of, 1/2, d2+ε )) = d2

(3)

As N (cwp∗ [P2 ], cwp∗ [P4 ]) ∈ {cwp∗ [P2 ], cwp∗ [P4 ]} we can
resolve non–determinism in P by either rewriting P to
{P1 } [1/2] {P2 } which gives
Jcwp∗ {P1 } [1/2] {P2 }K =

3
,
2

or we rewrite P to {P1 } [1/2] {P4 }, which gives
Jcwp∗ {P1 } [1/2] {P4 }K =

4+ε
.
3

For a sufficiently small ε the second option should be preferred
by a demonic scheduler. This, however, suggests:
cwp∗ [P5 ] = N (d2 , K(of, 1/2, d2+ε ))
= K(of, 1/2, d2+ε )

Theorem VII.1. There exists no inductive CPET.
Proof. The proof goes by contradiction. Consider the program
P = {P1 } [1/2] {P5 } with

hP i
1
2

P1 = x := 1
P5 = {P2 }  {P4 }
P2 = x := 2

1
2

hP1 i

hP5 i

1

P4 = {observe false} [1/2] {P2+ε }
P2+ε = x := 2 + ε ,

hP2 i
2

Rxσ0 JP K

where ε > 0. A schematic depiction of the RMDP
is given in Figure 4. Assume there exists an inductive CPET
cwp∗ over some appropriate domain D. Then,

hP4 i
1
2

1
2

hP2+ε i
2+ε

cwp∗ [P1 ] = d1 , with Jd1 K = 1
cwp∗ [P2 ] = d2 , with Jd2 K = 2

Fig. 4. Schematic depiction of the RMDP Rx
σ0 JP K

11

Together with Equality (3) we get d2 = K(of, 1/2, d2+ε ),
which implies Jd2 K = JK(of, 1/2, d2+ε )K. This is a contradiction to Inequality (2).

[8] D. Kozen, “Semantics of probabilistic programs,” J. Comput. Syst. Sci.,
vol. 22, no. 3, pp. 328–350, 1981.
[9] A. McIver and C. Morgan, Abstraction, Refinement And Proof For
Probabilistic Systems. Springer, 2004.
[10] F. Gretz, J.-P. Katoen, and A. McIver, “Operational versus weakest preexpectation semantics for the probabilistic guarded command language,”
Perform. Eval., vol. 73, pp. 110–132, 2014.
[11] C. Jones and G. D. Plotkin, “A probabilistic powerdomain of evaluations,” in Logic in Computer Science. IEEE Computer Society, 1989,
pp. 186–195.
[12] V. Gupta, R. Jagadeesan, and V. A. Saraswat, “Probabilistic concurrent
constraint programming,” in Concurrency Theory, ser. LNCS, vol. 1243.
Springer, 1997, pp. 243–257.
[13] D. S. Scott, “Stochastic λ-calculi: An extended abstract,” J. Applied
Logic, vol. 12, no. 3, pp. 369–376, 2014.
[14] C.-K. Hur, A. V. Nori, S. K. Rajamani, and S. Samuel, “Slicing
probabilistic programs,” in Proc. of PLDI. ACM Press, 2014, pp. 133–
144.
[15] A. Sampson, P. Panchekha, T. Mytkowicz, K. S. McKinley, D. Grossman, and L. Ceze, “Expressing and verifying probabilistic assertions,”
in ACM SIGPLAN Conference on Programming Language Design and
Implementation. ACM, 2014, p. 14.
[16] A. Chakarov and S. Sankaranarayanan, “Expectation invariants for
probabilistic program loops as fixed points,” in Proc. of SAS, ser. LNCS,
vol. 8723. Springer, 2014, pp. 85–100.
[17] M. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic
Programming. John Wiley and Sons, 1994.
[18] M. K. Reiter and A. D. Rubin, “Crowds: Anonymity for web transactions,” ACM Trans. Inf. Syst. Secur., vol. 1, no. 1, pp. 66–92, 1998.
[19] E. W. Dijkstra, A Discipline of Programming. Prentice Hall, 1976.
[20] A. McIver and C. Morgan, “Partial correctness for probabilistic demonic
programs,” Theoretical Computer Science, vol. 266, no. 12, pp. 513 –
541, 2001.
[21] C. Baier and J. Katoen, Principles of Model Checking. MIT Press,
2008.
[22] C. Baier, J. Klein, S. Klüppelholz, and S. Märcker, “Computing conditional probabilities in Markovian models efficiently,” in Proc. of TACAS,
ser. LNCS, vol. 8413. Springer, 2014, pp. 515–530.
[23] G. Nelson, “A generalization of Dijkstra’s calculus,” ACM Trans. Program. Lang. Syst., vol. 11, no. 4, pp. 517–561, 1989.
[24] G. Claret, S. K. Rajamani, A. V. Nori, A. D. Gordon, and J. Borgström,
“Bayesian inference using data flow analysis,” in Proc. of ESEC/SIGSOFT FSE. ACM Press, 2013, pp. 92–102.
[25] F. Gretz, J.-P. Katoen, and A. McIver, “Prinsys - on a quest for
probabilistic loop invariants,” in Proc. of QEST, ser. LNCS, vol. 8054.
Springer, 2013, pp. 193–208.
[26] M. E. Andrés and P. van Rossum, “Conditional probabilities over
probabilistic and nondeterministic systems,” in Proc. of TACAS, ser.
LNCS, vol. 4963. Springer, 2008, pp. 157–172.
[27] J. Katoen, A. McIver, L. Meinicke, and C. C. Morgan, “Linear-invariant
generation for probabilistic programs: - automated support for proofbased methods,” in Proc. of SAS, ser. LNCS, vol. 6337. Springer,
2010, pp. 390–406.
[28] P. Cousot and M. Monerau, “Probabilistic abstract interpretation,” in
Proc. of ESOP, ser. LNCS, H. Seidl, Ed., vol. 7211. Springer, 2012,
pp. 169–193.
[29] H. Bekic, “Definable operation in general algebras, and the theory
of automata and flowcharts,” in Programming Languages and Their
Definition. Springer, 1984, pp. 30–55.

As an immediate corollary of Theorem VII.1 we obtain the
following statement:
Corollary VII.2. We cannot extend the cwp rules in Figure 2
for non–deterministic programs such that Theorem V.6 extends
to full cpGCL.
This result is related to the fact that for minimizing conditional
(reachability) probabilities in RMDPs positional, i.e. history–
independent, schedulers are insufficient [26]. Intuitively speaking, if a history–dependent scheduler is required, this necessitates the inductive definition of cwp∗ to take the context
of a statement (if any) into account. This conflicts with the
principle of an inductive definition. Investigating the precise
relationship with the result of [26] requires further study.
VIII. C ONCLUSION

AND

F UTURE W ORK

This paper presented an extensive treatment of semantic
issues in probabilistic programs with conditioning. Major
contributions are the treatment of non–terminating programs
(both operationally and for weakest liberal pre–expectations),
our results on combining non–determinism with conditioning,
as well as the presented program transformations. We firmly
believe that a thorough understanding of these semantic issues
provides a main cornerstone for enabling automated analysis
techniques such as loop invariant synthesis [16], [27], program
analysis [28] and model checking [22] to the class of probabilistic programs with conditioning. Future work consists of
investigating conditional invariants and a further investigation
of non–determinism in combination with conditioning.
ACKNOWLEDGMENT
This work was supported by the Excellence Initiative of the
German federal and state government. Moreover, we would
like to thank Pedro d’Argenio and Tahiry Rabehaja for the
valuable discussions preceding this paper.
R EFERENCES
[1] N. D. Goodman and A. Stuhlmüller, The Design and Implementation of Probabilistic Programming Languages.
(electronic), 2014,
http://dippl.org.
[2] A. D. Gordon, T. A. Henzinger, A. V. Nori, and S. K. Rajamani,
“Probabilistic programming,” in Proc. of FOSE. ACM Press, 2014,
pp. 167–181.
[3] G. Barthe, B. Köpf, F. Olmedo, and S. Z. Béguelin, “Probabilistic
relational reasoning for differential privacy,” ACM Trans. Program.
Lang. Syst., vol. 35, no. 3, p. 9, 2013.
[4] N. D. Goodman, V. K. Mansinghka, D. M. Roy, K. Bonawitz, and J. B.
Tenenbaum, “Church: a language for generative models,” in Proc. of
UAI. AUAI Press, 2008, pp. 220–229.
[5] B. Paige and F. Wood, “A compilation target for probabilistic programming languages,” in Proc. of ICML, vol. 32. JMLR.org, 2014, pp.
1935–1943.
[6] A. D. Gordon, T. Graepel, N. Rolland, C. V. Russo, J. Borgström,
and J. Guiver, “Tabular: a schema-driven probabilistic programming
language,” in Proc. of POPL. ACM Press, 2014, pp. 321–334.
[7] A. V. Nori, C.-K. Hur, S. K. Rajamani, and S. Samuel, “R2: An efficient
MCMC sampler for probabilistic programs,” in Proc. of AAAI. AAAI
Press, July 2014.

12

d) The Observation observe G.: For cwp we have:

A PPENDIX
A. Continuity of wp and wlp

cwp[observe G](f, g)
= (f · χG , g · χG )

Lemma A.1 (Continuity of wp/wlp). Consider the extension
of wp and wlp to cpGCL given by
wp[observe G](f ) = χG · f

The argument for cwlp is completely analogous.
e) The Induction Hypothesis:: Assume in the following
that for two arbitrary but fixed programs P, Q ∈ cpGCL⊠ it
holds that both

cwp[P ](f, g) = wp[P ](f ), wlp[P ](g) , and

cwlp[P ](f ′ , g) = wlp[P ](f ′ ), wlp[P ](g) .

wlp[observe G](g) = χG · g .
Then for every P ∈ cpGCL the expectation transformers
wp[P ] : E → E and wlp[P ] : E≤1 → E≤1 are continuous
mappings over (E, ⊑) and (E≤1 , ⊒), respectively.
Proof. For proving the continuity of wp we have to show that
for any directed subset D ⊆ E we have
!
sup wp[P ](f ) = wp[P ]

sup f

f ∈D

f ∈D

.

Then for the induction step we have:
f) The Concatenation P ; Q.: For cwp we have:

(4)

cwp[P ; Q](f, g)
= cwp[P ](cwp[Q](f, g)

This can be shown by structural induction on P . All cases except for the observe statement have been covered in [10]. It
remains to show that Equality (4) holds for P = observe G:


= cwp[P ] wp[Q](f ), wlp[Q](g)
=

sup wp[observe G](f ) = sup χG · f
f ∈D


wp[observe G](f ), wlp[observe G](g)

=

=

f ∈D


wp[P ](wp[Q](f )), wlp[P ](wlp[Q](g))

wp[P ; Q](f ), wlp[P ; Q](g)

(I.H. on Q)
(I.H. on P )

The argument for cwlp is completely analogous.
g) The Conditional Choice ite (G) {P } {Q}.: For cwp
we have:

= χG · sup f
f ∈D

= wp[observe G](sup f )
f ∈D

cwp[ite (G) {P } {Q}](f, g)
= χG · cwp[P ](f, g) + χ¬G · cwp[Q](f, g)

= χG · wp[P ](f ), wlp[P ](g)

+ χ¬G · wp[Q](f ), wlp[Q](g)

The proof for the liberal transformer wlp is analogous.
B. Proof of Theorem V.1
Theorem V.1 (Decoupling of cwp/cwlp). For P ∈ cpGCL⊠ ,
f ∈ E, and f ′ , g ∈ E≤1 :

cwp[P ](f, g) = wp[P ](f ), wlp[P ](g)

cwlp[P ](f ′ , g) = wlp[P ](f ′ ), wlp[P ](g)

Proof. The proof of Theorem V.1 goes by induction over all
cpGCL⊠ programs. For the induction base we have:
a) The Effectless Program skip.: For cwp we have:

wp[skip](f ), wlp[skip](g)

cwp[abort](f, g) = (0, 1)


wp[abort](f ), wlp[abort](g)

=

Analogously for cwlp we have:

=

′

cwlp[abort](f , g) = (1, 1)
=

=

wp[ite (G) {P } {Q}](f ),


χG · wlp[P ](g) + χ¬G · wlp[Q](g)


wlp[ite (G) {P } {Q}](g)

cwp[{P } [p] {Q}](f, g)
= p · cwp[P ](f, g) + (1 − p) · cwp[Q](f, g)

= p · wp[P ](f ), wlp[P ](g)

+ (1 − p) · wp[Q](f ), wlp[Q](g)

The argument for cwlp is completely analogous.
b) The Faulty Program abort.: For cwp we have:
=

χG · wp[P ](f ) + χ¬G · wp[Q](f ),

The argument for cwlp is completely analogous.
h) The Probabilistic Choice {P } [p] {Q}.: For cwp we
have:

cwp[skip](f, g) = (f, g)
=

=

(I.H.)


wlp[abort](f ′ ), wlp[abort](g)

(I.H.)

p · wp[P ](f ) + (1 − p) · wp[Q](f ),


p · wlp[P ](g) + (1 − p) · wlp[Q](g)


wp[{P } [p] {Q}](f ), wlp[{P } [p] {Q}](g)

The argument for cwlp is completely analogous.
i) The Loop while (G) {P }.: For cwp we have:

c) The Assignment x := E.: For cwp we have:

cwp[while (G) {P }](f, g)
= µ⊑,⊒ (X1 , X2 )• χG · cwp[P ](X1 , X2 ) + χ¬G · (f, g)

= µ⊑,⊒ (X1 , X2 )• χG · wp[P ](X1 ), wlp[P ](X2 )

cwp[x := E](f, g) = (f [x/E], g[x/E])

= wp[x := E](f ), wlp[x := E](g)

+ χ¬G · (f, g)

The argument for cwlp is completely analogous.

13

(I.H.)

= µ⊑,⊒ (X1 , X2 )• χG · wp[P ](X1 ) + χ¬G · f,

χG · wlp[P ](X2 ) + χ¬G · g

k) The Faulty Program abort.:
wp[abort](α · f + β · g)
=0

Now let H(X1 , X2 ) = χG · wp[P ](X1 ) + χ¬G · f, χG ·
wlp[P ](X2 ) + χ¬G · g and let H1 (X1 , X2 ) be the projection
of H(X1 , X2 ) to the first component and let H2 (X1 , X2 ) be
the projection of H(X1 , X2 ) to the second component.
Notice that the value of H1 (X1 , X2 ) does not depend on
X2 and that it is given by
H1 (X1 ,

= α · wp[abort](f ) + β · wp[abort](g)
l) The Assignment x := E.:
wp[x := E](α · f + β · g)
= (α · f + β · g)[x/E]

) = χG · wp[P ](X1 ) + χ¬G · f .

= α · f [x/E] + β · g[x/E]
= α · wp[x := E](f ) + β · wp[x := E](g)

By the continuity of wp (Lemma A.1) we can establish that
H1 is continuous. Analogously the value of H2 (X1 , X2 ) does
not depend on X1 and it is given by

m) The Observation observe G.:
wp[observe G](α · f + β · g)

H2 ( , X2 ) = χG · wlp[P ](X2 ) + χ¬G · g .

= χG · (α · f + β · g)

By the continuity of wlp (Lemma A.1) we can establish that
H2 is continuous.
As both H1 and H2 are continuous, we can apply Bekić’s
Theorem [29] which
 tells us that the least fixed point of H is
c1 , X
c2 with
given as X

= α · χG · f + β · χG · g
= α · wp[observe G](f ) + β · wp[observe G](g)
n) The Concatenation P ; Q.:
wp[P ; Q](α · f + β · g)


c1 = µ⊑ X1 • H1 X1 , µ⊒ X2 • H2 (X1 , X2 )
X

= µ ⊑ X 1 • H1 X 1 ,

= wp[P ](wp[Q](α · f + β · g))

= µ⊑ X1 • χG · wp[P ](X1 ) + χ¬G · f

= wp[while (G) {P }](f )
and
c2 = µ⊒ X2 • H2 µ⊒ X1 • H1 (X1 , X2 ), X2
X

= µ ⊒ X 2 • H2 , X 2



cwp[while (G) {P }](f, g) =
=

c1 , X
c2
X

+ β · wp[P ](wp[Q](g))
= α · wp[P ; Q](f ) + β · wp[P ; Q](g)

(I.H. on P )

wp[ite (G) {P } {Q}](α · f + β · g)
= χG · wp[P ](α · f + β · g)

= ν ⊑ X2 • χG · wlp[P ](X2 ) + χ¬G · g
= wlp[while (G) {P }](g) ,


(I.H. on Q)

o) The Conditional Choice ite (G) {P } {Q}.:

= µ⊒ X2 • χG · wlp[P ](X2 ) + χ¬G · g

which gives us in total

= wp[P ](α · wp[Q](f ) + β · wp[Q](g))
= α · wp[P ](wp[Q](f ))

+ χ¬G · wp[Q](α · f + β · g)
= χG · (α · wp[P ](f ) + β · wp[P ](g))
+ χ¬G · (α · wp[Q](f ) + β · wp[Q](g))
= α · (χG · wp[P ](f ) + χ¬G · wp[Q](f ))



(I.H.)

+ β · (χG · wp[P ](g) + χ¬G · wp[Q](g))
= α · wp[ite (G) {P } {Q}](f )


wp[while (G) {P }](f ), wlp[while (G) {P }](f ) .

+ β · wp[ite (G) {P } {Q}](g)

The argument for cwlp is completely analogous.

p) The Probabilistic Choice {P } [p] {Q}.:

C. Linearity of wp
⊠

Lemma A.2 (Linearity of wp). For any P ∈ cpGCL ,
any post–expectations f, g ∈ E and any non–negative real
constants α, β,

wp[{P } [p] {Q}](α · f + β · g)
= p · wp[P ](α · f + β · g)
+ (1 − p) · wp[Q](α · f + β · g)

wp[P ](α · f + β · g) = α · wp[P ](f ) + β · wp[P ](g) .

= p · (α · wp[P ](f ) + β · wp[P ](g))
+ (1 − p) · (α · wp[Q](f ) + β · wp[Q](g))

Proof. The proof proceeds by induction on the structure of P .
j) The Effectless Program skip.:

= α · (p · wp[P ](f ) + (1 − p) · wp[Q](f ))
+ β · (p · wp[P ](g) + (1 − p) · wp[Q](g))

wp[skip](α · f + β · g)
= α·f +β·g
= α · wp[skip](f ) + β · wp[skip](g)

= α · wp[{P } [p] {Q}](f )
+ β · wp[{P } [p] {Q}](g)

14

(I.H.)

q) The Loop while (G) {P }.: The main idea of the
proof is to show that linearity holds for the n-th unrolling
of the loop and then use a continuity argument to show that
the property carries over to the loop.
The fact that linearity holds for the n–unrolling of the loop
is formalized by formula H n (0) = α·I n (0)+β ·J n (0), where

r) Proof of i): We do the proof for transformer cwp;
the proof for cwp is analogous. On view of Theorem V.1, the
monotonicity of cwp reduces to the monotonicity of wp which
follows immediately from its continuity (see Lemma A.1).
s) Proof of ii): Once again, on view of Theorem V.1, the
linearity of cwp follows from the linearity of wp, which we
prove in Lemma A.2.7
t) Proof of iii): Let us begin by proving that
cwp[P ](0) = 0. On account of Theorem V.1 this assertion
reduces to wp[P ](0) = 0, which has already been proved
for pGCL programs (see e.g. [9]). Therefore we only have
to deal with the case of observe statements and the claim
holds since wp[observe G](0) = χG ·0 = 0. Finally formula
cwlp[P ](1) = 1 follows immediately from Theorem V.1.

H(X) = χG · wp[P ](X) + χ¬G · (α · f + β · g)
I(X) = χG · wp[P ](X) + χ¬G · f
J(X) = χG · wp[P ](X) + χ¬G · g
We prove this formula by induction on n. The base case n = 0
is immediate. For the inductive case we reason as follows
H n+1 (0)

E. Proof of Lemma V.4 (i)

= H(H n (0))
= H(α · I n (0) + β · J n (0))
= χG · wp[P ](α · I (0) + β · J (0))
+ χ¬G · (α · f + β · g)

For proving Lemma V.4 (i) we rely on the fact that allowing
a bounded while–loop to be executed for an increasing number
of times approximates the behavior of an unbounded while–
loop. We first define bounded while–loops formally:

= χG · (α · wp[P ](I n (0)) + β · wp[P ](J n (0)))
+ χ¬G · (α · f + β · g)
(I.H. on P )

Definition A.1 (Bounded while–Loops). Let P ∈ pGCL.
Then we define:

(I.H. on n)

n

n

= α · (χG · wp[P ](I n (0)) + χ¬G · f )
+ β · (χG · wp[P ](J n (0)) + χ¬G · g)

while<0 (G) {P } , abort
while<k+1 (G) {P } , ite (G) {P k } {skip}

= α · I(I n (0)) + β · J(J n (0))

P k , P ; while<k (G) {P }

= α · I n+1 (0) + β · J n+1 (0)

We can now establish that by taking the supremum on the
bound k we obtain the full behavior of the unbounded while–
loop:

Now we turn to the proof of the main claim. We apply
the Kleene Fixed Point Theorem to deduce that the least fixed
points of H, I and J can be built by iteration from expectation
0 since the three transformers are continuous (due to the
continuity of wp established in Lemma A.1). Then we have

Lemma A.4. Let G be a predicate, P ∈ pGCL, and f ∈ E.
Then it holds that
sup wp[while<k (G) {P }](f ) = wp[while (G) {P }](f ) .

wp[while (G) {P }](α · f + β · g)
G
=
H n (0)

k∈N

Proof. For any predicate G, any program P ∈ pGCL, and any
expectation f ∈ E let

n

=

G
n

=α·

α · I n (0) + β · J n (0)
G
n

I n (0) + β ·

G

F (X) = χG · wp[P ](X) + χ¬G · f .
J n (0)

We first show by induction on k ∈ N that

n

wp[while<k (G) {P }](f ) = F k (0) .

= α · wp[while (G) {P }](f )
+ β · wp[while (G) {P }](g)

For the induction base we have k = 0. In that case we have
wp[while<0 (G) {P }](f )
= wp[abort](f )

D. Proof of Lemma V.3
Lemma V.3 (Elementary properties of cwp and cwlp). For
every P ∈ cpGCL⊠ with at least one feasible execution
(from every initial state), post–expectations f, g ∈ E and non–
negative real constants α, β:

= 0
= F 0 (0) .
As the induction hypothesis assume now that

i) f ⊑ g implies cwp[P ](f ) ⊑ cwp[P ](g) and likewise for
cwlp (monotonicity).

wp[while<k (G) {P }](f ) = F k (0)(f )

ii) cwp[P ](α · f + β · g) = α · cwp[P ](f ) + β · cwp[P ](g).
7 We cannot adopt the results from the original work [9] because their
analyses is restricted to bounded expectations.

iii) cwp[P ](0) = 0 and cwlp[P ](1) = 1.

15

holds for some arbitrary but fixed k. Then for the induction
step we have
wp[while<k+1 (G) {P }](f )

habort, σi

hsink i

0

0

In this RMC we have Π := Paths(habort, σi, hsink i) = ∅.
Then we have for the expected reward:

= wp[P ; ite (G) {while<k (G) {P }} {skip}](f )
= (χG · wp[P ] ◦ wp[while<k (G) {P }]

f

ExpRewRσ JabortK (♦sink )
X
=
Pr(π̂) · r(π̂)

+ χ¬G · wp[skip])(f )
= χG · wp[P ](wp[while<k (G) {P }](f ))

π̂∈Π

+ χ¬G · wp[skip](f )
= χG · wp[P ](F k (0)) + χ¬G · f

=

(I.H.)

X

Pr(π̂) · r(π̂)

π̂∈∅

= F k+1 (0)(f ) .

= 0
= 0(σ)

We have by now established that

= wp[abort](f )(σ)

wp[while<k (G) {P }](f ) = F k (0)

The Assignment x := E. The RMC for this program is of
the following form:

holds for every k ∈ N. Ergo, we can also establish that
sup wp[while<k (G) {P }](f )
k∈N

= sup F k (0)
k∈N

= µ X. F (X)

hx := E, σi

h↓, σ[E/x]i

hsink i

0

f (σ[E/x])

0

In this RMC we have Π := Paths(hx := E, σi, hsink i) =
{π̂1 } with π̂1 = hx := E, σi → h↓, σ[E/x]i → hsink i. Then
we have for the expected reward:

= wp[while (G) {P }](f ) .
With Lemma A.4 in mind, we can now restate and prove
Lemma V.4 (i):

f

ExpRewRσ Jx:=EK (♦sink )
X
=
Pr(π̂) · r(π̂)

Lemma V.4 (i). For P ∈ cpGCL⊠ , f ∈ E, g ∈ E≤1 , and
σ ∈ S:

π̂∈Π

f

ExpRewRσ JP K (♦hsink i) = wp[P ](f )(σ)

= Pr(π̂1 ) · r(π̂1 )

Proof. The proof goes by induction over all cpGCL⊠ programs. For the induction base we have:
The Effectless Program skip. The RMC for this program
is of the following form:8

= 1 · f (σ[E/x])
= f (σ[E/x])

hskip, σi

h↓, σi

hsink i

0

f (σ)

0

= f [E/x](σ)
= wp[x := E](f )(σ)
The Observation observe G. For this program there are
two cases: In Case 1 we have σ |= G, so we have χG (σ) = 1.
The RMC in this case is of the following form:

In the above RMC we have Π := Paths(hskip, σi, hsink i) =
{π̂1 } with π̂1 = hskip, σi → h↓, σi → hsink i. Then we have
for the expected reward:
Rfσ JskipK

ExpRew
(♦sink )
X
=
Pr(π̂) · r(π̂)

hobserve G, σi

h↓, σi

hsink i

0

f (σ)

0

In this RMC we have Π := Paths(hobserve G, σi, hsink i)
= {π̂1 } with π̂1 = hobserve G, σi → h↓, σi → hsink i.
Then we have for the expected reward:

π̂∈Π

= Pr(π̂1 ) · r(π̂1 )
= 1 · f (σ)

f

ExpRewRσ Jobserve
X
=
Pr(π̂) · r(π̂)

= f (σ)
= wp[skip](f )(σ)

GK

(♦sink )

π̂∈Π

= Pr(π̂1 ) · r(π̂1 )

The Faulty Program abort. The RMC for this program
is of the following form:

= 1 · f (σ)
= χG (σ) · f (σ)

8 If transitions have probability 1, we omit this in our figures. Moreover,
all states—with the exception of hsink i—are left out if they are not reachable
from the initial state.

= (χG · f )(σ)
= wp[observe G](f )(σ)

16

In Case 2 we have σ 6|= G, so we have χG (σ) = 0. The RMC
in this case is of the following form:
hobserve G, σi

h i

hsink i

0

0

0

= wp[P ; Q](f )
The Conditional Choice ite (G) {P } {Q}. For this program there are two cases: In Case 1 we have σ |= G, so we
have χG (σ) = 1 and χ¬G (σ) = 0. The RMC in this case is
of the following form:

In this RMC we have Π := Paths(hobserve G, σi, hsink i)
= {π̂1 } with π̂1 = hobserve G, σi → h i → hsink i. Then
for the expected reward we also have:
f

ExpRewRσ Jobserve
X
=
Pr(π̂) · r(π̂)

GK

hite (G) {P } {Q} G, σi

hP, σi
0

0

(♦sink )

..
.

π̂∈Π

In this RMC every path in Paths(hite (G) {P } {Q}, σi,
hsink i) starts with hite (G) {P } {Q}, σi → hP, σi → · · · .
As the state hite (G) {P } {Q}, σi collects zero reward, the
expected reward of the above RMC is equal to the expected
reward of the following RMC:

= Pr(π̂1 ) · r(π̂1 )
= 1·0
= 0
= 0 · f (σ)
= χG (σ) · f (σ)
= (χG · f )(σ)

hP, σi
0

= wp[observe G](f )(σ)

But the above RMC is exactly Rfσ JP K for which the expected
reward is known by the induction hypothesis. So we have

The Concatenation P ; Q. For this program the RMC is of
the following form:
′

hP ; Q, σi

h↓; Q, σ i

hQ, σ i

0

0

0

h↓; Q, σ ′′ i

hQ, σ ′′ i

0

0

..
.

f

ExpRewRσ Jite (G) {P } {Q}K (♦sink )

...

′

f

= ExpRewRσ JP K (♦sink )
= wp[P ](f )(σ)
= 1 · wp[P ](f )(σ) + 0 · wp[Q](f )(σ)

...

In Case 2 we have σ 6|= G, so we have χG (σ) = 0 and
χ¬G (σ) = 1. The RMC in this case is of the following form:
hite (G) {P } {Q} G, σi
0

0

ExpRew

..
.
(♦sink )

In this RMC every path in Paths(hite (G) {P } {Q}, σi,
hsink i) starts with hite (G) {P } {Q}, σi → hQ, σi → · · · .
As the state hite (G) {P } {Q}, σi collects zero reward, the
expected reward of the above RMC is equal to the expected
reward of the following RMC:

h↓, σ ′′ i
..
.

f

ExpRewRσ′′ JQK (♦sink )
f

λτ.ExpRewRτ JQK (♦sink )

hQ, σi
0

But the above RMC is exactly Rσ
JP K for
which the expected reward is also known by the induction
hypothesis. So we have
ExpRew
= ExpRew

hQ, σi

h↓, σ ′ i
Rfσ′ JQK

Rfσ JP ; QK

wp[Q](f )

JP K
= ExpRewRσ
(♦sink )
= wp[P ](wp[Q](f ))(σ)

...

But the above RMC is exactly Rfσ JQK for which the expected
reward is known by the induction hypothesis. So we also have

(♦sink )

f
Rτ JQK (♦sink )
Rλτ.ExpRew
JP K
σ

(I.H.)

= χG (σ) · wp[P ](f )(σ) + χ¬G (σ) · wp[Q](f )(σ)
= wp[ite (G) {P } {Q}](f )(σ) .

In this RMC every path in Paths(hP ; Q, σi, hsink i) starts
with hP ; Q, σi, eventually reaches h↓; Q, σ ′ i, and then immediately after that reaches hQ, σ ′ i which is the initial
state of Rfσ′ JQK for which the expected reward is given by
f
ExpRewRσ′ JQK (♦sink ). By this insight we can transform the
above RMC into the RMC with equal expected reward below:
hP, σi
0

...

f

ExpRewRσ Jite (G) {P } {Q}K (♦sink )

(♦sink )

f

= ExpRewRσ JQK (♦sink )
= wp[Q](f )(σ)

(I.H. on Q)
(I.H. on P )

17

(I.H.)

f

= ExpRewRσ Jwhile (G) {P }K (♦sink ) .

= 0 · wp[P ](f )(σ) + 1 · wp[Q](f )(σ)
= χG (σ) · wp[P ](f )(σ) + χ¬G (σ) · wp[Q](f )(σ)

While the above is intuitively evident, it is a tedious and technically involved task to prove it. Herefore we just provide an
intuition thereof: For showing (5) ≤ (6), we know that every
path in the RMDP Rfσ Jwhile<k (G) {P }K either terminates
properly or is prematurely aborted (yielding 0 reward) due
to the fact that the bound of less than k loop iterations was
reached. The RMDP Rfσ Jwhile (G) {P }K for the unbounded
while–loop does not prematurely abort executions, so left–
hand–side is upper bounded by the right–hand–side of the
equation. For showing (5) ≥ (6), we know that a path that
collects positive reward is necessarily finite. Therefore there
exists some k ∈ N such that Rfσ Jwhile<k (G) {P }K includes
this path. Taking the supremum over k we eventually include
every path in Rfσ Jwhile (G) {P }K that collects positive reward.

= wp[ite (G) {P } {Q}](f )(σ) .
The Probabilistic Choice {P } [p] {Q}. For this program
the RMC is of the following form:
p

h{P } [p] {Q}, σi
1−p

0

hP, σi
0

...

hQ, σi
0

...

In this RMC every path in Paths(h{P } [p] {Q}, σi, hsink i)
starts with h{P } [p] {Q}, σi and immediately after that
reaches hP, σi with probability p or hQ, σi with probability
1 − p. hP, σi is the initial state of Rfσ JP K and hQ, σi is the
initial state of Rfσ JQK. By this insight we can transform the
above RMC into the RMC with equal expected reward below:

F. Proof of Lemma V.4 (ii)
Lemma V.4 (ii). For P ∈ cpGCL⊠ , f ∈ E, g ∈ E≤1 , and
σ ∈ S:
g

p

LExpRewRσ JP K (♦hsink i) = wlp[P ](g)(σ)

h{P } [p] {Q}, σi

hP, σi
f
ExpRewRσ JP K (♦sink )

1−p

0

Proof. The proof goes by induction over all cpGCL⊠ programs. For the induction base we have: The Effectless Program skip. The RMC for this program is of the following
form:

hQ, σi
f
ExpRewRσ JQK (♦sink )
The expected reward of the above RMC is given by p ·
f
f
ExpRewRσ JP K (♦sink ) + (1 − p) · ExpRewRσ JQK (♦sink ), so
in total we have for the expected reward:
f

hsink i

0

f (σ)

0

g

f

+ (1 − p) · ExpRewRσ JQK (♦sink )
= p · wp[P ](f )(σ) + (1 − p) · wp[Q](f )(σ)

π̂∈Π

(I.H.)

= Pr(π̂) · r(π̂) + 0
= 1 · g(σ)

= wp[{P } [p] {Q}](f ) .
The Loop while (G) {Q}. By Lemma A.4 we have

= g(σ)
= wlp[skip](g)(σ)

wp[while (G) {P }](f ) = sup wp[while<k (G) {P }](f )
k∈N

The Faulty Program abort. The RMC for this program
is of the following form:

and as while<k (G) {P } is a purely syntactical construct
(made up from abort, skip, conditional choice, and P )
we can (using what we have already established on abort,
skip, conditional choice, and using the induction hypothesis
on P ) also establish that
wp[while (G) {P }](f )
<k

h↓, σi

LExpRewRσ JskipK (♦sink )
X
=
Pr(π̂) · r(π̂) + Pr(¬♦hsink i)

f

= p · ExpRewRσ JP K (♦sink )

= sup ExpRewRσ Jwhile

hskip, σi

In this RMC we have Π := Paths(hskip, σi, hsink i) = {π̂1 }
with π̂1 = hskip, σi → h↓, σi → hsink i. Then we have for
the liberal expected reward:

ExpRewRσ J{P } [p] {Q}K (♦sink )

f

(G) {P }K

habort, σi

hsink i

0

0

In this RMC we have Π := Paths(habort, σi, hsink i) = ∅.
Then we have for the liberal expected reward:

(♦sink ) .

k∈N

g

ExpRewRσ JabortK (♦sink )
X
=
Pr(π̂) · r(π̂) + Pr(¬♦hsink i)

It is now left to show that
f

(6)

<k

sup ExpRewRσ Jwhile

(G) {P }K

(♦sink )

(5)

π̂∈Π

k∈N

18

=

X

Pr(π̂) · r(π̂) + 1

In this RMC we have Π := Paths(hobserve G, σi, hsink i)
= {π̂1 } with π̂1 = hobserve G, σi → h i → hsink i. Then
we have for the liberal expected reward:

π̂∈∅

= 0+1
= 1
= 1(σ)

g

LExpRewRσ Jobserve GK (♦sink )
X
=
Pr(π̂) · r(π̂) + Pr(¬♦hsink i)

= wlp[abort](g)(σ)

π̂∈Π

= Pr(π̂1 ) · r(π̂1 ) + 0
= 1·0

The Assignment x := E. The RMC for this program is of
the following form:
hx := E, σi

h↓, σ[E/x]i

hsink i

0

f (σ[E/x])

0

= 0
= 0 · g(σ)
= χG (σ) · g(σ)
= (χG · g)(σ)
= wlp[observe G](g)(σ)

In this RMC we have Π := Paths(hx := E, σi, hsink i) =
{π̂1 } with π̂1 = hx := E, σi → h↓, σ[E/x]i → hsink i. Then
we have for the liberal expected reward:

The Concatenation P ; Q. For this program the RMC is of
the following form:

Rgσ Jx:=EK

LExpRew
(♦sink )
X
=
Pr(π̂) · r(π̂) + Pr(¬♦hsink i)

diverge. . .

π̂∈Π

diverge. . .

= Pr(π̂1 ) · r(π̂1 ) + 0
= 1 · g(σ[E/x])

= g(σ[E/x])
= g[E/x](σ)
= wlp[x := E](g)(σ)

hP ; Q, σi
0

The Observation observe G. For this program there are
two cases: In Case 1 we have σ |= G, so we have χG (σ) = 1.
The RMC in this case is of the following form:
hobserve G, σi

h↓, σi

hsink i

0

f (σ)

0

h↓; Q, σ ′ i
0

hQ, σ ′ i
0

...

h↓; Q, σ ′′ i
0

hQ, σ ′′ i
0

...

In this RMC every path in Paths(hP ; Q, σi, hsink i) starts
with hP ; Q, σi, eventually reaches h↓; Q, σi, and then immediately after that reaches hQ, σi which is the initial state
of Rgσ JQK. Every diverging path either diverges because the
program P diverges or because the program Q diverges. If
we attempt to make the RMC smaller (while preserving the
liberal expected reward) by cutting it off at states of the form
h↓; Q, τ i, we haveg to assign to them the liberal expected
reward LExpRewRτ JQK (♦sink ) in order to not loose the non–
termination probability caused by Q. By this insight we can
now transform the above RMC into the RMC with equal liberal
expected reward below:

In this RMC we have Π := Paths(hobserve G, σi, hsink i)
= {π̂1 } with π̂1 = hobserve G, σi → h↓, σi → hsink i.
Then we have for the liberal expected reward:
g

LExpRewRσ Jobserve GK (♦sink )
X
=
Pr(π̂) · r(π̂) + Pr(¬♦hsink i)
π̂∈Π

= Pr(π̂1 ) · r(π̂1 ) + 0
= 1 · g(σ)

diverge. . .

= χG (σ) · g(σ)
= (χG · g)(σ)
= wlp[observe G](g)(σ)

hP, σi

f

In Case 2 we have σ 6|= G, so we have χG (σ) = 0. The RMC
in this case is of the following form:
hobserve G, σi

h i

hsink i

0

0

0

h↓, σ ′ i

0

LExpRewRσ′ JQK (♦sink )
h↓, σ ′′ i
f

LExpRewRσ′′ JQK (♦sink )

19

g

LExpRewRσ JQK (♦sink )

expected reward of the above RMC is equal to the expected
reward of the following RMC:

JP K for
But the above RMC is exactly Rσ
which the liberal expected reward is known by the induction
hypothesis. So we have for the liberal expected reward:
LExpRew
= LExpRew

Rgσ JP ; QK

(♦sink )

g
LExpRewRσ JQK (♦sink )
Rσ
JP K

But the above RMC is exactly Rgσ JQK for which the expected
reward is known by the induction hypothesis. A similar
argument can be applied to the probability of not eventually
reaching hsink i. So we also have for the liberal expected
reward:

(♦sink )

wlp[Q](g)

JP K
= LExpRewRσ
(♦sink )
= wlp[P ](wlp[Q](g))(σ)

...

hQ, σi
0

(I.H. on Q)
(I.H. on P )

= wlp[P ; Q](g) .

g

LExpRewRσ Jite (G) {P } {Q}K (♦sink )

The Conditional Choice ite (G) {P } {Q}. For this program there are two cases: In Case 1 we have σ |= G, so we
have χG (σ) = 1 and χ¬G (σ) = 0. The RMC in this case is
of the following form:
hite (G) {P } {Q} G, σi

g

= ExpRewRσ Jite (G) {P } {Q}K (♦sink )
g

+ PrRσ Jite (G) {P } {Q}K (¬♦hsink i)
g

hP, σi

= wlp[Q](g)(σ)
= 0 · wlp[P ](g)(σ) + 1 · wlp[Q](g)(σ)

0

0

The Probabilistic Choice {P } [p] {Q}. For this program
the RMC is of the following form:

As the state hite (G) {P } {Q}, σi collects zero reward, the
expected reward of the above RMC is equal to the expected
reward of the following RMC:

p

h{P } [p] {Q}, σi

...

1−p

0

But the above RMC is exactly Rgσ JP K for which the expected
reward is known by Lemma . A similar argument can be
applied to the probability of not eventually reaching hsink i.
So we have for the liberal expected reward:
g

= ExpRewRσ Jite (G) {P } {Q}K (♦sink )
g

+ PrRσ Jite (G) {P } {Q}K (¬♦hsink i)
g

= ExpRewRσ JP K (♦sink ) + PrRσ JP K (¬♦hsink i)
= wlp[P ](g)(σ)
(I.H.)
= 1 · wlp[P ](g)(σ) + 0 · wlp[Q](g)(σ)
= χG (σ) · wlp[P ](g)(σ) + χ¬G (σ) · wlp[Q](g)(σ)

h{P } [p] {Q}, σi

In Case 2 we have σ 6|= G, so we have χG (σ) = 0 and
χ¬G (σ) = 1. The RMC in this case is of the following form:

0

...

hQ, σi
0

...

p

= wlp[ite (G) {P } {Q}](g)(σ) .

hite (G) {P } {Q} G, σi

hP, σi
0

In this RMC every path in Paths(h{P } [p] {Q}, σi, hsink i)
starts with h{P } [p] {Q}, σi and immediately after that
reaches hP, σi with probability p or hQ, σi with probability
1 − p. hP, σi is the initial state of Rfσ JP K and hQ, σi is the
initial state of Rfσ JQK. The same holds for all paths that do not
eventually reach hsink i. By this insight we can transform the
above RMC into the RMC with equal liberal expected reward
below:

g

LExpRewRσ Jite (G) {P } {Q}K (♦sink )

g

(I.H.)

= χG (σ) · wlp[P ](g)(σ) + χ¬G (σ) · wlp[Q](g)(σ)
= wlp[ite (G) {P } {Q}](g)(σ) .

..
.

hP, σi
0

g

= ExpRewRσ JQK (♦sink ) + PrRσ JQK (¬♦hsink i)

1−p

0

hQ, σi

hP, σi
f
ExpRewRσ JP K (♦sink )

hQ, σi
f
ExpRewRσ JQK (♦sink )

0

The liberal expected reward of the above RMC is given by
f
f
p·LExpRewRσ JP K (♦sink )+(1−p)·LExpRewRσ JQK (♦sink ),
so in total we have for the liberal expected reward:

..
.
In this RMC every path in Paths(hite (G) {P } {Q}, σi,
hsink i) starts with hite (G) {P } {Q}, σi → hQ, σi → · · · .
As the state hite (G) {P } {Q}, σi collects zero reward, the

f

LExpRewRσ J{P } [p] {Q}K (♦sink )
f

= p · LExpRewRσ JP K (♦sink )

20

f

+ (1 − p) · LExpRewRσ JQK (♦sink )
= p · wlp[P ](f )(σ) + (1 − p) · wlp[Q](f )(σ)

I. Proof of Theorem VI.1
(I.H.)

Theorem VI.1 (Program Transformation Correctness). Let
P ∈ cpGCL⊠ admit at least one feasible run for every initial
state and T (P, 1) = (P̂ , ĥ). Then for any f ∈ E and g ∈ E≤1 ,

= wlp[{P } [p] {Q}](f ) .
The Loop while (G) {Q}.
The argument is dual to the case for the (non–liberal)
expected reward.

wp[P̂ ](f ) = cwp[P ](f ) and wlp[P̂ ](g) = cwlp[P ](g).
In view of Theorem V.1, the proof reduces to showing equations ĥ·wp[P̂ ](f ) = wp[P ](f ), ĥ·wlp[P̂ ](f ) = wlp[P ](f ) and
ĥ = wlp[P ](1), which follow immediately from the auxiliary
Lemma A.5 below by taking h = 1.

G. Proof of Lemma V.5
Lemma V.5. For P ∈ cpGCL⊠ , g ∈ E≤1 , and σ ∈ S:
g

PrRσ JP K (¬♦ ) = wlp[P ](1)(σ) .

Lemma A.5. Let P ∈ cpGCL⊠ . Then for all expectations
f ∈ E and g, h ∈ E≤1 , it holds

Proof. First, observe that paths on reaching Xor immediately move to the state hsink i. Moreover, all paths that never
visit either (a) visit a terminal X–state (which are the only
states that can possibly collect positive reward) or (b) diverge
and never reach hsink i and therefore neither reach Xnor .
Furthermore the set of “(a)–paths” and the set of “(b)–paths”
are disjoint. Thus:
Pr
= Pr

Rfσ JP K
Rfσ JP K

(♦X) + Pr

and by assigning reward one to every X–state, and zero to
all other states, we can turn the probability measure into an
expected reward, yielding
g

= ExpRewRσ JP K (♦X) + PrRσ JP K (¬♦sink )

= LExpRew

g

(9)

h = wlp[skip](h).

(♦sink )

= wlp[P ](1)

ĥ = wlp[P ](h),

and

= ExpRewRσ JP K (♦sink ) + PrRσ JP K (¬♦sink )
R1
σ JP K

(8)

h · wp[skip](f ) = h · f = wp[skip](h · f )

As every path that reaches sink over a –state cumulates zero
reward, we finally get:
1

ĥ · wlp[P̂ ](g) = wlp[P ](h · g)

Proof. We prove only equations (7) and (9) since (8) follows
a reasoning similar to (7). The proof proceeds by induction
on the structure of P . In the remainder we will refer to the
inductive hypothesis about (7) as to IH1 and to the inductive
hypothesis about (9) as to IH2 .
The Effectless Program skip. We have T (skip, h) =
(skip, h) and the statement follows immediately since

(¬♦sink )

1

(7)

where (P̂ , ĥ) = T (P, h).

(¬♦ )
Rfσ JP K

ĥ · wp[P̂ ](f ) = wp[P ](h · f )

The Faulty Program abort. We have T (abort, h) =
(abort, 1) and the statement follows immediately since

(Lemma V.4)

1 · wp[abort](f ) = 1 · 0 = wp[abort](h · f )
H. Proof of Theorem V.6
and

Theorem V.6 (Correspondence theorem). For P ∈ cpGCL⊠ ,
f ∈ E, g ∈ E≤1 and σ ∈ S,

1 = wlp[abort](h).

f

CExpRewRσ JP K (♦sink | ¬♦ ) = cwp[P ](f )(σ)
CLExpRewRσ JP K (♦sink | ¬♦ ) = cwlp[P ](g)(σ) .

The Assignment x := E. We have T (x := E, h) = (x :=
E, h[x/E]) and the statement follows immediately since

Proof. We prove only the first equation. The proof of the
second equation goes along the same arguments.

h[x/E] · wp[x := E](f ) = h[x/E] · f [x/E]
= (h · f )[x/E] = wp[x := E](h · f )

g

f

CExpRewRσ JP K (♦sink | ¬♦ )

and

f

=

ExpRewRσ JP K (♦sink )

h[x/E] = wlp[x := E](h).

f

PrRσ JP K (¬♦ )
wp[P ](f )
=
wlp[P ](1)
cwp1 [P ](f, 1)
=
cwp2 [P ](f, 1)
= cwp[P ](f )

The Observation observe G. We have T (observe G, h)
= (skip, χG · h) and the statement follows immediately since

(Lemmas V.4, V.5)
(Theorem V.1)

χG · h · wp[skip](f ) = χG · h · f
= wp[observe G](h · f )

21

and

of the lemma we need to make a case distinction between
those states that are mapped by ĥ to a positive number and
those that are mapped to 0. In the first case, i.e. if ĥ(s) > 0,
we reason as follows:


ĥ(s) · wp[{P̂ } φ·ĥP/ĥ {Q̂}](f )(s)

= ĥ(s) · φ·ĥĥP (s) · wp[P̂ ](f )(s)

(1−φ)·ĥQ
+
(s)
·
wp[
Q̂](f
)(s)
ĥ

χG · h = wlp[observe G](h).
The Concatenation P ; Q. Let (Q̂, ĥQ ) = T (Q, h) and
(P̂ , ĥP ) = T (P, ĥQ ). In view of these definitions, we obtain
T (P ; Q, h) = (P̂ ; Q̂, ĥP ).
Now
ĥP · wp[P̂ ; Q̂](f )



= ĥP · wp[P̂ ] wp[Q̂](f )
= wp[P ](ĥQ · wp[Q̂](f ))
= wp[P ](wp[Q](h · f ))

= φ(s) · ĥP (s) · wp[P̂ ](f )(s)

+ (1 − φ)(s) · ĥQ (s) · wp[Q̂](f )(s)
= φ(s) · wp[P ](h · f )(s)
+ (1 − φ)(s) · wp[Q](h · f )(s)

(IH1 on P )
(IH1 on Q)

= wp[{P } [φ] {Q}](h · f )(s)

= wp[P ; Q](h · f )

while in the second case, i.e. if ĥ(s) = 0, the claim holds
because we will have wp[{P } [φ] {Q}](h · f )(s) = 0. To see
this note that if ĥ(s) = 0 then either φ(s) = 0 ∧ ĥQ (s) = 0 or
φ(s) = 1 ∧ ĥP (s) = 0 holds. Now assume we are in the first
case (an analogous argument works for the other case); using
the IH1 over Q we obtain

and
ĥP = wlp[P ](ĥQ )
= wlp[P ](wlp[Q](h))

(IH1 )

(IH2 on P )
(IH2 on Q)

= wlp[P ; Q](h).
The Conditional Choice ite (G) {P } {Q}. Let (P̂ , ĥP ) =
T (P, h) and (Q̂, ĥQ ) = T (Q, h). On view of these definitions,
we obtain

wp[{P } [0] {Q}](h · f )(s) = wp[Q](h · f )(s)
= ĥQ (s) · wp[Q](f )(s) = 0.
The proof of the second claim of the lemma is straightforward:

T (ite (G) {P } {Q}, h) =
(ite (G) {P̂ } {Q̂}, χG · ĥP + χ¬G · ĥQ ).

φ · ĥP + (1 − φ) · ĥQ
= φ · wlp[P ](h) + (1 − φ) · wlp[Q](h)

Now
(χG · ĥP + χ¬G · ĥQ )

= wlp[{P } [φ] {Q}](h).

· wp[ite (G) {P̂ } {Q̂}](f )

The Loop while (G) {Q}. Let ĥ = ν F where F (X) =
χG ·TP (X)+χ¬G ·h and TP (·) is a short–hand for π2 ◦T (P, ·).
Now if we let (P̂ , θ) = T (P, ĥ) by definition of T we obtain

= (χG · ĥP + χ¬G · ĥQ )
· (χG · wp[P̂ ](f ) + χ¬G · wp[Q̂](f ))
= χG · ĥP · wp[P̂ ](f ) + χ¬G · ĥQ · wp[Q̂](f )
= χG · wp[P ](h · f ) + χ¬G · wp[Q](h · f )
= wp[ite (G) {P } {Q}](h · f )

(IH2 )

T (while (G) {P }, h) = (while (G) {P̂ }, ĥ).

(IH1 )

The first claim of the lemma says that
ĥ · wp[while (G) {P̂ }](f ) = wp[while (G) {P }](h · f ).

and

Now if we let H(X) = χG · wp[P̂ ](X) + χ¬G · f and
I(X) = χG · wp[P ](X) + χ¬G · h · f , the claim can be
rewritten as ĥ · µ H = µ I and a straightforward argument
using the Kleene fixed point theorem (and the continuity of
wp established in Lemma A.1) shows that it is entailed by
formula ∀n• ĥ · H n (0) = I n (0). We prove the formula by
induction on n. The case n = 0 is trivial. For the inductive
case we reason as follows:

χG · ĥP + χ¬G · ĥQ
= χG · wlp[P ](h) + χ¬G · wlp[Q](h)
= wlp[ite (G) {P } {Q}](h)

(IH2 )

The Probabilistic Choice {P } [p] {Q}. Let (P̂ , ĥP ) =
T (P, h) and (Q̂, ĥQ ) = T (Q, h). On view of these definitions, we obtain
T ({P } [φ] {Q}, h) =


({P̂ } φ·ĥP/ĥ {Q̂}, φ · ĥP + (1 − φ) · ĥQ )

ĥ · H n+1 (0)
= F (ĥ) · H n+1 (0)
= (χG · TP (ĥ) + χ¬G · h) · H

with ĥ = φ · ĥP + (1 − φ) · ĥQ .
To prove the first claim


ĥ · wp[{P̂ } φ·ĥP/ĥ {Q̂}](f ) = wp[{P } [φ] {Q}](h · f )

(def. ĥ)
n+1

(0)

(def. F )

= (χG · TP (ĥ) + χ¬G · h)
· (χG · wp[P̂ ](H n (0)) + χ¬G · f )

22

(def. H)

= χG · TP (ĥ) · wp[P̂ ](H n (0))
+ χ¬G · h · f

=
(def. θ)

= χG · wp[P ](ĥ · H n (0)) + χ¬G · h · f

(IH1 on P)

= I(ĥ · H n (0))

(def. I)

=I

(0)

= F (ĥ)

(def. F )

= ĥ

(def. ĥ)

K. Detailed calculations for Section VI-D
We refer to the labels init and loop introduced in the
program P in Section VI-D. Further let body denote the
program in the loop’s body. For readability we abbreviate
the variable names delivered as del, counter as cntr and
intercepted as int. In the following we consider del and int
as boolean variables. In order to determine (1) we first start
with the numerator. This quantity is given by

(def. F )

= χG · wlp[P ](ν J) + χ¬G · h
= J(ν J)

(IH2 on P )
(def. J)

=νJ

(def. ν J)

J. Proof of Theorem VI.2

cwp[P ](f )(sI )

=
=

ExpRew
P

Pr

∞
X

1 − Pr

(12)
(13)

· f (π̂)

(14)

(♦ rerun)

′

f

PrRsI JP K (♦ rerun)i

i=0

=

RfsI JP ′ K

·
X

Φ(0) = [¬del] · wp[body](0) + [del ∧ cntr ≤ k ∧ ¬int]

X

f

π̂∈♦ sink ∩¬♦ rerun
∞ 
X
Rfs JP ′ K

π̂∈♦ sink ∩¬♦ rerun i=0

′

PrRsI JP K (π̂) · f (π̂)
Pr

(23)

where Φn denotes the n-fold application of Φ. Equation (21)
is given directly by the semantics of sequential composition
of cpGCL commands. In the next line we apply the definition
of loop semantics in terms of the least fixed point. Finally,
(23) is given by the Kleene fixed point theorem as a solution
to the fixed point equation in (22). We can explicitly find the
supremum by considering the expression for several n and
deducing a pattern. Let Φ(F ) = [¬del] · wp[body](F ) + [del ∧
cntr ≤ k ∧ ¬int]. Then we have

(¬♦ rerun)

Rfs JP ′ K
I
(π̂)
π̂∈♦ sink ∩¬♦ rerun Pr

(22)

n

(11)

(♦ sink ∩ ¬♦ rerun)

RfsI JP ′ K

= wp[init](µF • ([¬del] · wp[body](F )
+[del ∧ cntr ≤ k ∧ ¬int]))

+[del ∧ cntr ≤ k ∧ ¬int]) )

f

(♦ sink | ¬♦ rerun)

(20)
(21)

n

(10)

= CExpRewRsI JP K (♦ sink | ¬♦ )

wp[init; loop; observe(cntr ≤ k)]([¬int])
= wp[init](wp[loop]([cntr ≤ k ∧ ¬int]))

= wp[init](sup ([¬del] · wp[body](0)

Proof. Let us take the operational point of view. Let sI be
some initial state of P .

=

(19)

Rewriting (15) into (16) precisely captures the expected cumulative reward of all terminating paths in P ′′ which is the
expression in the following line. Finally we return from the
operational semantics to the denotational semantics and obtain
the desired result.

(def. J)
(IH2 on P )
(def. θ)

I

(18)

∞

= χG · TP (ĥ) + χ¬G · h

Rfs JP ′ K
I

(♦ sink )

X
r
ai r .
=
1−a
i=0

of the lemma. By letting J(X) = χG · wlp[P ](X) + χ¬G · h,
the claim reduces to ν F = ν J, which we prove showing
that ĥ = ν F is a fixed point of J and ν J is a fixed point
of F . (These assertions basically imply that ν F ≥ ν J and
ν J ≥ ν F , respectively.)

= CExpRew

K

The equality (12) holds because, by construction, the probability to violate an observation in P agrees with the probability
to reach a state in P ′ where rerun is true. In order to obtain
equation (15) we use the fact that for a fixed real value r and
probability a it holds

ĥ = wlp[while (G) {P }](h)

Rfs JP ′ K

′′

= wp(P , f )(sI ) .

We now turn to proving the second claim

F (ν J) = χG · TP (ν J) + χ¬G · h

(17)

′′

(IH on n)

J(ĥ) = χG · wlp[P ](ĥ) + χ¬G · h
= χG · θ + χ¬G · h

f

= ExpRewRsI JP

= χG · θ · wp[P̂ ](H (0)) + χ¬G · h · f

n+1

′′

f

PrRsI JP K (π̂) · f (π̂)

π̂∈♦ sink

(algebra)

n

X

I

= [del ∧ cntr ≤ k ∧ ¬int]
(15)
Φ2 (0) = Φ([del ∧ cntr ≤ k ∧ ¬int])
= [¬del] · wp[body]([del ∧ cntr ≤ k ∧ ¬int])

(♦ rerun)i


f
′
·PrRsI JP K (π̂) · f (π̂)

+ [del ∧ cntr ≤ k ∧ ¬int]
= [¬del] · (p(1 − c) · [del ∧ cntr + 1 ≤ k ∧ ¬int]

(16)

23

+ [¬del ∧ cntr + 1 ≤ k ∧ ¬int]

+(1 − p) · [cntr ≤ k ∧ ¬int])
+ [del ∧ cntr ≤ k ∧ ¬int]

1 − p(1 − c)k−cntr
·(1 − p)
1 − p(1 − c)
= [del ∧ cntr ≤ k ∧ ¬int]
+ [¬del ∧ cntr ≤ k ∧ ¬int] · (1 − p)

= [¬del ∧ cntr ≤ k ∧ ¬int] · (1 − p)
+ [del ∧ cntr ≤ k ∧ ¬int]

+ [¬del ∧ cntr + 1 ≤ k ∧ ¬int]

Φ3 (0) = Φ([¬del ∧ cntr ≤ k ∧ ¬int] · (1 − p)
+ [del ∧ cntr ≤ k ∧ ¬int])

· (1 − p)(p(1 − c))

= ...
= [¬del ∧ cntr ≤ k ∧ ¬int] · (1 − p)

+ [¬del ∧ cntr + 1 ≤ k ∧ ¬int] · (1 − p)
+ [¬del ∧ cntr + 1 ≤ k ∧ ¬int]

As we continue to compute Φn (0) in each step we add a
summand of the form

· (1 − p)(p(1 − c))

[¬del ∧ cntr + i ≤ k ∧ ¬int] · (1 − p)(p(1 − c))i

+ [¬del ∧ cntr = k ∧ ¬int] · (1 − p)
+ [¬del ∧ cntr + 1 ≤ k ∧ ¬int]
1 − p(1 − c) + (p(1 − c)) 1 − p(1 − c)k−cntr
· (1 − p)
1 − p(1 − c)
= [del ∧ cntr ≤ k ∧ ¬int]

[del ∧ cntr ≤ k ∧ ¬int]
[¬del ∧ cntr + i ≤ k ∧ ¬int] · (1 − p)(p(1 − c))i

1 − p(1 − c)k−cntr+1
1 − p(1 − c)
Moreover this fixed point is the only fixed point and therefore
the least. The justification is given by [9] where they show
that loops which terminate almost surely have only one fixed
point. We can now continue our calculation from (23).

= [del ∧ cntr ≤ k ∧ ¬int]

· (1 − p)

k−cntr
X

(1 − p)(p(1 − c))i

i=0

= [del ∧ cntr ≤ k ∧ ¬int]
+ [¬del ∧ cntr ≤ k ∧ ¬int]
· (1 − p)

1 − (p(1 − c))k−cntr+1
.
1 − p(1 − c)

= wp[init]([del ∧ cntr ≤ k ∧ ¬int]
+ [¬del ∧ cntr ≤ k ∧ ¬int]

ark = a

k=0

(24)

1 − (p(1 − c))k−cntr+1
· (1 − p)
)
1 − p(1 − c)
1 − (p(1 − c))k
.
(25)
= (1 − c)(1 − p)
1 − p(1 − c)
This concludes the calculation of the numerator of (1). Analogously we find the denominator

where for the last equation we use a property of the finite
geometric series, namely that for r 6= 1
n−1
X



+ [¬del ∧ cntr ≤ k ∧ ¬int]

i=0

+ [¬del ∧ cntr ≤ k ∧ ¬int] ·

1 − p(1 − c)k−cntr
1 − p(1 − c)

= [del ∧ cntr ≤ k ∧ ¬int]

However we see that the predicate evaluates to false for all
i > k − cntr. Hence the non-zero part of the fixed point is
given by
k−cntr
X

1 − p(1 − c)k−cntr
1 − p(1 − c)

= [del ∧ cntr ≤ k ∧ ¬int]
+ [¬del ∧ cntr = k ∧ ¬int] · (1 − p)

+ [¬del ∧ cntr + 1 ≤ k ∧ ¬int] · (1 − p)p(1 − c)
+ [del ∧ cntr ≤ k ∧ ¬int]

+



1 − rn
.
1−r

The result coincides with the intuition that in a state where
del = false, the probability to fail to reach the goal ¬int ∧
cntr ≤ k is distributed geometrically with probability p(1 −
c). It is easy to verify that our educated guess is correct by
checking that we indeed found a fixed point of Φ:

wlp[init; loop; observe(cntr ≤ k)](1)
= wlp[init](wlp[loop]([cntr ≤ k]))
= wlp[init](νF • ([¬del] · wlp[body](F )
+[del ∧ cntr ≤ k]))
= wlp[init](sup ([¬del] · wlp[body](1)

Φ([del ∧ cntr ≤ k ∧ ¬int]
+ [¬del ∧ cntr ≤ k ∧ ¬int]

n

1 − (p(1 − c))k−cntr+1
)
1 − p(1 − c)
= [del ∧ cntr ≤ k ∧ ¬int]

+ [¬del] · (1 − p) · [cntr ≤ k ∧ ¬int]

+ p(1 − c) [del ∧ cntr + 1 ≤ k ∧ ¬int]

n

+[del ∧ cntr ≤ k]) )

· (1 − p)

= wlp[init]([del ∧ cntr ≤ k]
+ [¬del ∧ cntr ≤ k] · (1 − pk−counter+1 ))
= 1 − pk .

(26)

The only difference is that here the supremum is taken with
respect to the reversed order ≥ in which 1 is the bottom

24

0.9
0.8
0.7
0.6
0.5

0

5

10

c = 0.1 p = 0.6
c = 0.2 p = 0.6

15

20

c = 0.1 p = 0.8
c = 0.2 p = 0.8

Fig. 5. The conditional probability that a message is intercepted as a function
of k for fixed c and p.

and 0 is the top element. However as mentioned earlier loop
terminates with probability one and the notions of wp and wlp
coincide. We divide (25) by (26) to finally arrive at
cwp[P]([¬intercepted])
= (1 − c)(1 − p)

1
1 − (p(1 − c))k
.
·
1 − p(1 − c)
1 − pk

One can visualise it as a function in k by fixing the parameters c and p. For example, Figure 5 shows the conditional
probability plotted for various parameter settings.

25

