Highly Incremental: A Simple Programmatic Approach for Many Objectives (Extended Version) Philipp Schröer, Joost-Pieter Katoen Abstract We present a one-fits-all programmatic approach to reason about a plethora of objectives on probabilistic programs. The first ingredient is to add a reward-statement to the language. We then define a program transformation applying a monotone function to the cumulative reward of the program. The key idea is that this transformation uses incremental differences in the reward. This simple, elegant approach enables to express e.g., higher moments, threshold probabilities of rewards, the expected excess over a budget, and moment-generating functions. All these objectives can now be analyzed using a single existing approach: probabilistic wp-reasoning. We automated verification using the Caesar deductive verifier and report on the application of the transformation to some examples. 1 Introduction Probabilistic programs. Probabilistic programs combine ordinary programming structures such as loops and conditionals with probabilistic choices. They are a powerful modeling tool for a wide range of applications, including randomized algorithms, security mechanisms, and probabilistic databases. Due to the intrinsic randomness, the runtime of a probabilistic program follows a probability distribution. Figure 1(a) models a web server retrying a database call until success. Variable done records success; each loop iteration yields a {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{1} (1 second). Each iteration succeeds with probability \nicefrac{{1}}{{2}} and the program terminates with probability one ( almost-sure termination ). Its expected runtime is 2 ( positive almost-sure termination ). Same expected runtime, different variance. We add a cache ( Figure 1(b) ) raising the success probability to \nicefrac{{2}}{{3}} at an initialization cost of \nicefrac{{1}}{{2}} seconds. The new program also terminates almost surely, and perhaps more surprisingly, its expected runtime is also 2 . Despite identical expected runtimes, their runtime distributions differ ( Figure 2 ). The probability that Figure 1(a) terminates earlier is higher, while Figure 1(b) concentrates more tightly around 2s. The variances are 2\,\text{s}^{2} (no cache) versus \nicefrac{{3}}{{4}}\,\text{s}^{2} (cache), making the runtime of the cached variant more predictable. The example shows that the expected value – an average – is not always sufficient to capture the behavior of a probabilistic program. \displaystyle{done}\,{\coloneqq}\,{\texttt{false}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~(\neg done)~\{ \displaystyle\quad{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle\quad\underset{\text{\emph{probabilistic choice}}}{\{{{done}\,{\coloneqq}\,{\texttt{true}}}\}~[{\nicefrac{{1}}{{2}}}]~\{{{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}}\}} \displaystyle\} (a) Program modeling a web server which retries a database call, succeeding with probability \nicefrac{{1}}{{2}} . Each database call takes 1 second. \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{\nicefrac{{1}}{{2}}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{done}\,{\coloneqq}\,{\texttt{false}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~(\neg done)~\{ \displaystyle\quad{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle\quad\underset{\text{\emph{probabilistic choice}}}{\{{{done}\,{\coloneqq}\,{\texttt{true}}}\}~[{\nicefrac{{2}}{{3}}}]~\{{{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}}\}} \displaystyle\} (b) Variant with a cache. It initializes a cache (taking \nicefrac{{1}}{{2}} seconds) and then retries a database call which succeeds with probability \nicefrac{{2}}{{3}} . Each database call takes 1 second. Figure 1 : Example programs modeling a web server retrying a database call. 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 0 0.2 0.4 0.6 Runtime Probability Figure 1(a) Figure 1(b) Figure 2 : Probability distribution of runtimes of the programs in Figure 1 . Deductive verification of probabilistic programs. Dedicated techniques have been developed to reason about different objectives of probabilistic programs. The weakest pre-expectation ( wp ) semantics [ 28 ] is a well-established formalism to reason about expected values on termination. An extensive catalog of proof rules has been developed, including [ 6 , 27 , 14 , 4 , 11 ] . The wp calculus has been extended for reasoning about expected runtimes [ 17 , 20 ] and general rewards [ 8 ] . Tool-assisted wp -based verification includes HOL mechanization [ 16 ] and the Caesar deductive verifier [ 35 ] . Tailored variations have been proposed for covariances [ 19 ] , higher moments of rewards [ 24 , 37 ] , and for amortized complexity analysis [ 5 ] . Programmatic rewards as a unifying abstraction. Different objectives currently require separate wp -calculi, hindering reuse. We aim for a one-fits-all approach so that existing wp semantics, proof rules, and tools can be reused for a broad range of objectives. We do so by adding a reward statement to the programming language, inspired by [ 3 , 5 ] , to collect (non-negative) rewards during program execution. The expected cumulative reward is then the expected sum of all rewards collected during a program run. We show how different objectives can be modeled using reward statements, including expected runtimes, expected visiting times, and discounted rewards. Incremental differences for reward transformations. To tackle objectives like higher moments of expected rewards, we need to reason about transformed expected rewards of program {\color[rgb]{0.5016,0.2203,0}S} such as \mathsf{E}(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}})^{2}) . Our key idea is to make use of incremental differences of rewards, inspired by the aert calculus [ 5 ] . We define a simple program transformation that reduces reasoning about complex expected rewards to reasoning about standard expected rewards, allowing us to reuse existing wp theory, techniques, and tools. Contributions and outline. We provide one programming language and one weakest pre-expectation semantics to reason about a broad range of quantitative objectives of probabilistic programs in a unified way. Section 2 introduces the syntax and semantics for probabilistic programs. Our main contributions are: 1. A programmatic encoding for multiple quantitative objectives ( Section 3 ), 2. A program transformation ( Section 4.1 ) that is proven sound w.r.t. a Markov chain transformation ( Section 4.2 ), 3. Application to different objectives, including higher moments. ( Section 5 ), Finally, we briefly touch on automation in Section 6 , compare related work in Section 7 and conclude in Section 8 . 2 Foundations: Semantics for Probabilistic Programs In this section, we introduce the syntax and semantics of probabilistic programs with reward statements. Our presentation is based on [ 8 ] , with two key adaptations: (1) we allow arbitrary expressions a in {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} statements instead of only constants, and (2) we allow program variables to take on values from the set \mathbb{R}_{\geq 0}^{\infty}=\mathbb{R}_{\geq 0}\cup\Set{\infty} . We formally define the syntax of probabilistic guarded command language ( pGCL ) programs, describe their operational semantics via Markov chains, and present the weakest pre-expectation semantics. 2.1 Syntax of Probabilistic Programs States and expressions. We consider a finite set of variables Vars . A program state \sigma is a mapping from variables to values, i.e., \sigma\in\mathsf{States}=\textsf{{Vars}}\to\mathsf{Vals} . In this work, we will use \mathsf{Vals}=\mathbb{R}_{\geq 0}^{\infty} . We write \sigma[{x}\mapsto{e}] for the state \sigma updated so that x maps to the value of e in \sigma and all other variables are untouched, i.e. \sigma[{x}\mapsto{e}](y)=e(\sigma) if y=x , and \sigma(y) otherwise. An arithmetic expression a\in\textsf{{AExp}} is a mapping from program states to values, i.e. \textsf{{AExp}}=\mathsf{States}\to\mathsf{Vals} . Boolean expressions b\in\textsf{{BExp}} map program states to \Set{\texttt{true},~\texttt{false}} . Programs. The syntax of pGCL programs {\color[rgb]{0.5016,0.2203,0}S} is defined by the following grammar, where x\in\textsf{{Vars}} , a\in\textsf{{AExp}} , p\in[0,1] , and b\in\textsf{{BExp}} : \begin{array}[]{rcl}{\color[rgb]{0.5016,0.2203,0}S}&::=&{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}\mid{x}\,{\coloneqq}\,{a}\mid{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a}\mid{\color[rgb]{0.5016,0.2203,0}S_{1}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S_{2}}\\ &\mid&\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~[{p}]~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\}\mid{\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\}\mid{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S}}~\}~.\end{array} The skip statement does nothing. The assignment {x}\,{\coloneqq}\,{a} assigns the value of expression a to variable x . The {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} statement collects a non-negative reward a when executed. Note that a is an expression that may contain program variables. The sequential composition {\color[rgb]{0.5016,0.2203,0}S_{1}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S_{2}} executes {\color[rgb]{0.5016,0.2203,0}S_{1}} followed by {\color[rgb]{0.5016,0.2203,0}S_{2}} . The probabilistic choice \{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~[{p}]~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\} executes {\color[rgb]{0.5016,0.2203,0}S_{1}} with probability p and {\color[rgb]{0.5016,0.2203,0}S_{2}} with probability 1-p . The conditional {\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\} executes {\color[rgb]{0.5016,0.2203,0}S_{1}} if the boolean expression b evaluates to true, and {\color[rgb]{0.5016,0.2203,0}S_{2}} otherwise. The loop {\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S}}~\} repeatedly executes {\color[rgb]{0.5016,0.2203,0}S} as long as the boolean expression b evaluates to true. 2.2 Operational Semantics s_{1} s_{2} s_{3} \mathsf{rew}({{s_{3}}}){=}1 s_{5} s_{6} s_{4} s_{7} \bot 0.5 0.5 Figure 3 : Operational MC for Figure 1(a) . The operational semantics of programs is given by Markov chains with rewards, whose foundations we briefly recall. A Markov chain is a tuple \mathcal{M}=(\mathfrak{S},\mathsf{Prob},\sigma_{1},\mathsf{rew}) , where \mathfrak{S} is a (countable) set of configurations, \mathsf{Prob}\colon\mathfrak{S}\to\mathsf{Dist}({\mathfrak{S}}) is the transition function, \sigma_{1}\in\mathfrak{S} is the initial configuration, and \mathsf{rew}\colon\mathfrak{S}\to\mathbb{R}_{\geq 0}^{\infty} is the reward function. A (finite) path \pi\in\mathsf{Paths}^{=n}_{\mathcal{M}} of length n in \mathcal{M} is a sequence of configurations \pi=s_{1}s_{2}\ldots s_{n} with \mathsf{Prob}(s_{i})(s_{i+1})>0 for all 1\leq i\rightsquigarrow\>{\color[rgb]{0.5016,0.2203,0}S}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{~{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{[\phi=0]}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\phi}\,{\coloneqq}\,{1}~\} • First Return: {\color[rgb]{0.5016,0.2203,0}S}\>\rightsquigarrow\>{\color[rgb]{0.5016,0.2203,0}S}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{~{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{[\phi=1]}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\phi}\,{\coloneqq}\,{\min(\phi+1,2)}~\} 4 Reward Transformations We now consider f -transformed cumulative rewards , i.e. the expected value of some function f applied to the cumulative reward. Whereas it is simple to apply f to expected rewards on termination using the weakest pre-expectation calculus ( Section 3.1 ), this is not the case for cumulative expected rewards ( Section 3.2 ). Instead of defining yet another variation of wp , we propose a program transformation \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) for monotone functions f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} . The program {\color[rgb]{0.5016,0.2203,0}S} with expected reward \mathsf{E}(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}})) is transformed to program \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) whose expected reward is the f -transformed expected reward, i.e. \mathsf{E}(\mathsf{rew}({\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}))=\mathsf{E}(f(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}}))) . Incremental reward updates. At the heart of the reward transformation is the idea of collecting f -transformed rewards incrementally, an idea inspired by the aert calculus [ 5 ] . A {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} statement simply adds a to the cumulative reward; if the current cumulative reward is \tau , the new cumulative reward is \tau+a . For f -transformed cumulative rewards, the collected reward equals f(\tau) and the new cumulative reward equals f(\tau{+}a) . The key idea is to (1) subtract the previous cumulative reward f(\tau) and (2) add the new cumulative reward f(\tau{+}a) . Consider the modeling of expected runtimes, where 1 reward is collected at each step. Then, the sequence of rewards that starts with f(\tau) has the telescoping property and collapses to the final cumulative reward f(\tau+N) : 6 6 6 We define \infty-x=\infty for all x\in\mathbb{R}_{\geq 0}^{\infty} (in particular \infty-\infty=\infty ) so that the sum is infinite if any f(\tau+i) is infinite. \displaystyle\underbrace{f(\tau)}_{\text{(0) previous}}+\sum_{i=0}^{N-1}\underbrace{-f(\tau+i)}_{\text{(1) reset}}+\underbrace{f(\tau+i+1)}_{\text{(2) set}}~{}={}~f(\tau+N)~. (1) Since f is monotone, the difference f(\tau+a)-f(\tau) is non-negative, and we can encode this change in the program via a reward statement. 4.1 Program Transformation The program transformation is simple: we introduce a ghost variable \tau to track the cumulative reward of the original program {\color[rgb]{0.5016,0.2203,0}S} and transform every {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} statement to collect the difference f(\tau+a)-f(\tau) . In the following, we denote by f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} a monotone function to ensure non-negative reward differences. Definition 1 (Reward Program Transformation) Let {\color[rgb]{0.5016,0.2203,0}S}\in\textsf{{pGCL}} and \tau be a fresh variable not occurring in {\color[rgb]{0.5016,0.2203,0}S} . The f -transformed program \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) is \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})~{}={}~{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{f(0)}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})~, where the auxiliary transformation \mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}) replaces reward statements: \mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a})~{}={}~{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(f(\tau+a)-f(\tau))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a}~, and other statements are left unchanged. Figure 6 shows the transformations of the example programs from Figure 1 using f(x)=x^{2} , where the highlighted statements originate from the transformation. For example, the {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{1} statement in Figure 1(a) is transformed to {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{((\tau+1)^{2}-\tau^{2})}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+1} in Figure 6(a) . \displaystyle{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{done}\,{\coloneqq}\,{\texttt{false}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~(\neg done)~\{ \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{2\cdot\tau+1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\tau}\,{\coloneqq}\,{\tau+1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle\quad\{{{done}\,{\coloneqq}\,{\texttt{true}}}\}~[{\nicefrac{{1}}{{2}}}]~\{{{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}}\} \displaystyle\} (a) Transformed version of Figure 1(a) . \displaystyle{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{\nicefrac{{1}}{{4}}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{done}\,{\coloneqq}\,{\texttt{false}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~(\neg done)~\{ \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{2\cdot\tau+1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\tau}\,{\coloneqq}\,{\tau+1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle\quad\{{{done}\,{\coloneqq}\,{\texttt{true}}}\}~[{\nicefrac{{2}}{{3}}}]~\{{{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}}\} \displaystyle\} (b) Transformed version of Figure 1(b) . Figure 6 : Transformations \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) of programs {\color[rgb]{0.5016,0.2203,0}S} in Figure 1 with f(x)=x^{2} . The expected reward of the transformed program \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) is equal to the expected value of f applied to the reward of the original program {\color[rgb]{0.5016,0.2203,0}S} . Theorem 4.1 (Soundness) For {\color[rgb]{0.5016,0.2203,0}S}\in\textsf{{pGCL}} and monotone f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} : \mathsf{E}(\mathsf{rew}({\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}))=\mathsf{E}(f(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}})))~. In terms of weakest pre-expectation semantics, we can express Theorem 4.1 as \mathsf{E}(\mathsf{rew}({\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}))=\textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)=\mathsf{E}(f(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}}))) . In particular, the wp semantics of the (auxiliary) transformation of a reward statement reflects the telescoping idea from Equation 1 . For an expectation {\color[rgb]{0,0.2695,0.418}X}\in\mathbb{E} , we have: \textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})~{}={}~\lambda{\sigma}.~{\underbrace{f(\sigma(\tau)+a(\sigma))}_{\text{(2) set}}-\underbrace{f(\sigma(\tau))}_{\text{(1) reset}}+\underbrace{{\color[rgb]{0,0.2695,0.418}X}(\sigma[{\tau}\mapsto{\tau+a}])}_{\text{next}}}~. The program transformation preserves healthiness conditions similar to wp . Theorem 4.2 (Monotonicity) Let {\color[rgb]{0.5016,0.2203,0}S}\in\textsf{{pGCL}} and let f,g\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} be monotone with f\preceq g . For all {\color[rgb]{0,0.2695,0.418}X}\in\mathbb{E} , we have \textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})\preceq\textsf{{wp}}\llbracket{\mathcal{T}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) . The transformation is linear with respect to scaling and shifting. Theorem 4.3 (Linearity) Let {\color[rgb]{0.5016,0.2203,0}S}\in\textsf{{pGCL}} and let f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} be monotone. Then, for all \alpha,\beta\in\mathbb{R}_{\geq 0} , we have \textsf{{wp}}\llbracket{\mathcal{T}_{\alpha\cdot f+\beta}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)=\alpha\cdot\textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)+\beta . For linear transformation functions, we can avoid the ghost variable \tau from the transformed program \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) entirely. Theorem 4.4 (Ghost Buster) Let f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} be of the form f(x)=\alpha\cdot x+\beta for some \alpha,\beta\in\mathbb{R}_{\geq 0} . Then, \displaystyle\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})~{}={}~{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{\beta}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})\qquad\text{and}\qquad\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a})~{}={}~{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{\alpha\cdot a}~. The transformation is well-behaved with respect to composition of transformation functions. In essence: \mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}))=\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0.5016,0.2203,0}S}) , where the equality is to be understood modulo the variables introduced by the transformations. Theorem 4.5 (Composition of Transformations) Let {\color[rgb]{0.5016,0.2203,0}S}\in\textsf{{pGCL}} and let f,g\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} be monotone. Assume that \mathcal{T}^{\prime}_{f}(\cdot) and \mathcal{T}^{\prime}_{g\circ f}(\cdot) use the same variable \tau and \mathcal{T}^{\prime}_{g}(\cdot) uses a different variable \tau^{\prime} . Then, \textsf{{wp}}\llbracket{{\tau^{\prime}}\,{\coloneqq}\,{f(\tau)}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}))}\rrbracket=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0.5016,0.2203,0}S}){\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau^{\prime}}\,{\coloneqq}\,{f(\tau)}}\rrbracket~. 4.2 Transforming Rewards of Markov Chains To prove soundness of the program transformation ( Theorem 4.1 ), we define a reward transformation for Markov chains directly. The state space is augmented with a dimension \mathbb{R}_{\geq 0}^{\infty} to track the accumulated reward of the original Markov chain, which is zero in the initial state \sigma_{1}^{\prime} , and the reward function is adjusted to collect the incremental differences. Here, we restrict to monotone f with f(0)=0 for simplicity. Definition 2 (MC Transformation) Let MC \mathcal{M}=(\mathsf{States},\mathsf{Prob},\sigma_{1},\mathsf{rew}) and monotone f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} with f(0)=0 . 7 7 7 The restriction f(0)=0 in \mathcal{T}_{f}(\mathcal{M}) can be easily lifted by using the function g(x)=f(x)-f(0) for \mathcal{T}_{g}(\mathcal{M}) , and prepending a new initial state \sigma_{0}^{\prime} with reward f(0) . The full construction is presented in Section 0.A.3 . We define \mathcal{T}_{f}(\mathcal{M})=(\mathsf{States}\times\mathbb{R}_{\geq 0}^{\infty},~\mathsf{Prob^{\prime}},~\sigma_{1}^{\prime},~\mathsf{rew}^{\prime}) where • \sigma_{1}^{\prime}=(\sigma_{1},0) , • \mathsf{Prob^{\prime}}((\sigma,\alpha),(\sigma^{\prime},\alpha^{\prime}))=\begin{cases}\mathsf{Prob}(\sigma)(\sigma^{\prime})&\text{if }\alpha+\mathsf{rew}({\sigma})=\alpha^{\prime},\\ 0&\text{otherwise}\end{cases} • \mathsf{rew}^{\prime}((\sigma,\alpha))=f(\alpha+\mathsf{rew}({\sigma}))-f(\alpha) . Note that the transformation does not preserve the size of the reachable state space, because the added dimension \mathbb{R}_{\geq 0}^{\infty} tracks the reward accumulation. Example 1 (Reachable States Explosion) Let MC \mathcal{M}=(\mathsf{States},\mathsf{Prob},\sigma_{1},\mathsf{rew}) with \mathsf{States}=\Set{\sigma_{1}} , \mathsf{Prob}(\sigma_{1})(\sigma_{1})=1 , \mathsf{rew}(\sigma_{1})=1 . Let f(x)=x . The transformed MC \mathcal{T}_{f}(\mathcal{M}) has an infinite path (\sigma_{1},0),(\sigma_{1},1),(\sigma_{1},2),\ldots with probability one. The set of reachable states is \Set{(\sigma_{1},\alpha)\mid\alpha\in\mathbb{N}} , which is infinite. The paths of the transformed Markov chain \mathcal{T}_{f}(\mathcal{M}) correspond one-to-one to the paths of the original \mathcal{M} , from which the soundness theorem follows. Lemma 3 Let MC \mathcal{M}=(\mathsf{States},\mathsf{Prob},\sigma_{1},\mathsf{rew}) and f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} be monotone with f(0)=0 . Let n\in\mathbb{N} . For every \sigma_{1}\ldots\sigma_{n}\in\mathsf{Paths}^{=n}_{\mathcal{M}} , there is a one-to-one mapping to (\sigma_{1},\alpha_{1})\ldots(\sigma_{n},\alpha_{n})\in\mathsf{Paths}^{=n}_{\mathcal{T}_{f}(\mathcal{M})} in \mathcal{T}_{f}(\mathcal{M}) such that: 1. same path probabilities: \mathsf{Prob}(\sigma_{1}\ldots\sigma_{n})=\mathsf{Prob^{\prime}}((\sigma_{1},\alpha_{1})\ldots(\sigma_{n},\alpha_{n})) , 2. \alpha_{i} track previous untransformed rewards: \forall 1\leq i\leq n.\,\sum_{j0} yields higher moments of cumulative rewards. By Theorem 4.1 , we have \mathsf{E}(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}})^{k})=\textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0) . Example 2 (Variance of Web Server Runtime) We return to Figure 6 , which shows the transformations of the web server examples from Figure 1 using f(x)=x^{2} , to obtain the second moment of the expected runtime. To calculate the expected reward, i.e. \textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket(0) of Figure 6(a) , we first tackle the loop. The wp of the loop w.r.t. post 0 is given by \mathrm{lfp}\,{{\color[rgb]{0,0.2695,0.418}X}}.~{\left[{\neg done}\right]\cdot((2\cdot\tau+1)+0.5\cdot{\color[rgb]{0,0.2695,0.418}X}[{done}\mapsto{\texttt{true}}]+0.5\cdot{\color[rgb]{0,0.2695,0.418}X})+\left[{done}\right]\cdot 0}. It evaluates to \left[{\neg done}\right]\cdot(4\cdot\tau+6) . Applying wp to the remaining first three lines yields \textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket=6 . Thus, the second moment of the expected reward of Figure 1(a) is 6 . Since the first moment is 2 (c.f. Section 2.3 ), the variance is \mathrm{Var}(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}}))=\mathsf{E}(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}})^{2})-(\mathsf{E}(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}})))^{2}=6-2^{2}=2 . Similarly, one can show that \textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}_{\text{loop}}}\rrbracket(0) of the loop in Figure 6(b) is equal to \left[{\neg done}\right]\cdot(3\cdot(\tau-0.5)+4.5) . Applying wp to the first three lines, we obtain \textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)=4.75 , the second moment of the expected reward of Figure 1(b) . The variance of the expected reward is \mathrm{Var}(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}}))=4.75-2^{2}=0.75 . Example 3 (Biased Random Walk) Consider a random walk starting at position x>1 that moves two steps to the left with probability 0.75 and two steps to the right with probability 0.25 until it reaches position x\leq 1 . The second moment is upper-bounded by x^{2}+3\cdot x , which we verified using the program transformation and wp reasoning. 5.2 Cumulative Distribution Functions We can use f(x)=\left[{x\geq N}\right] for some N\in\mathbb{N} to compute the cumulative distribution function (CDF) of the expected rewards. Example 4 (CDF of Web Server Runtime) To obtain the CDF for Figure 1(a) , we transform it with f(x)=\left[{x\geq N}\right] : \displaystyle\hbox{\pagecolor{white!94!mydarkgreen}$\displaystyle{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{\left[{0\geq N}\right]}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}$\hskip-5.0pt}~{done}\,{\coloneqq}\,{\texttt{false}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({\neg done})~\{ \displaystyle\quad\hbox{\pagecolor{white!94!mydarkgreen}$\displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{[\tau+1\geq N]-[\tau\geq N]}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}$\hskip-5.0pt}~\{{{done}\,{\coloneqq}\,{\texttt{true}}}\}~[{\nicefrac{{1}}{{2}}}]~\{{{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}}\}~\} Note that one may simplify the reward statement to {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{[\tau+1=N]} . For the CDF, we get \textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)=0.5^{N\ominus 1} , where a\ominus b=\max(0,a-b) . 5.3 Expected Excess Consider a fixed budget N\in\mathbb{R}_{\geq 0} and the objective is to determine how much the cumulative reward exceeds this budget in expectation. The following example shows that we can use our program transformation to compute the expected excess of a loop’s runtime, i.e. \mathsf{E}((\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}})\ominus N)) for all N\in\mathbb{R}_{\geq 0} . Example 5 (Loop Splitting for Expected Excess) We compute the expected excess of the web server program from Figure 1(a) , depending on a success probability p\in[0,1] of a database call and a budget N\in\mathbb{N} . Applying the transformation with f(x)=x\ominus N yields, after simplification 8 8 8 We use that (((\tau+1)\ominus N)-(\tau\ominus N)) is equal to [\tau\geq N] . , the following: \displaystyle\hbox{\pagecolor{white!94!mydarkgreen}$\displaystyle{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}$\hskip-5.0pt}~{done}\,{\coloneqq}\,{\texttt{false}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({\neg done})~\{~{\hbox{\pagecolor{white!94!mydarkgreen}$\displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{[\tau\geq N]}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}$\hskip-5.0pt}~\{{{done}\,{\coloneqq}\,{\texttt{true}}}\}~[{p}]~\{{{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}}\}}~\} Now, it is not difficult to see that the loop runs in two phases. The first phase runs until the runtime is below N , collecting no reward, and the second phase collects the excess of the runtime. Splitting the loop in two loops yields: \displaystyle{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{done}\,{\coloneqq}\,{\texttt{false}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({\neg done\land(\tau0} . 5.5 Multiple Rewards Sometimes, it is useful to track multiple rewards simultaneously and aggregate them into a single reward. In some cloud computing platforms, for example, pricing is based on the product of the runtime and memory consumption [ 2 ] . Our transformation can be generalized to a multi-reward setting by introducing multiple reward variables \tau_{i} . The generalized reward statements assign multiple rewards at once, e.g. {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(a_{1},a_{2})} assigns reward a_{1} to reward 1 and reward a_{2} to reward 2 . The transformation \mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}) is generalized to f\colon(\mathbb{R}_{\geq 0}^{\infty})^{n}\to\mathbb{R}_{\geq 0}^{\infty} that maps n rewards to a single reward: \displaystyle\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(a_{1},\ldots,a_{n})})=~ \displaystyle{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{f(\tau_{1}+a_{1},\ldots,\tau_{n}+a_{n})-f(\tau_{1},\ldots,\tau_{n})}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}} \displaystyle{\tau_{1}}\,{\coloneqq}\,{\tau_{1}+a_{1}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\ldots{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau_{n}}\,{\coloneqq}\,{\tau_{n}+a_{n}} Example 7 (Expected Cost with Runtime and Memory Consumption) Consider a program starting with two units of memory and computation each. With probability p it needs more computation, for this, it requests an additional unit of memory with probability q . We can write this as a program, apply our transformation with f(\tau_{1},\tau_{2})=\tau_{1}\cdot\tau_{2} (modeling cost as product of runtime and memory), and compute the expected cost. The result is \textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)=4+(p\cdot(2+(q\cdot 3))) . 6 Automation The off-the-shelf Caesar deductive verifier for probabilistic programs [ 35 ] was used, which supports reward statements and implements various proof rules for reasoning about lower and upper bounds of expected rewards. One example is the induction proof rule [ 33 , 22 ] , to verify upper bounds {\color[rgb]{0,0.2695,0.418}I}\in{\color[rgb]{0,0.2695,0.418}X} on \textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) for {\color[rgb]{0.5016,0.2203,0}S}={\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S}}~\} and {\color[rgb]{0,0.2695,0.418}X}\in\mathbb{E} , where {\color[rgb]{0,0.2695,0.418}I} is a user-provided loop invariant: \left[{b}\right]\cdot\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket({\color[rgb]{0,0.2695,0.418}I})+\left[{\neg b}\right]\cdot{\color[rgb]{0,0.2695,0.418}X}\sqsubseteq{\color[rgb]{0,0.2695,0.418}I}\quad\text{implies}\quad\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S}}~\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})\sqsubseteq{\color[rgb]{0,0.2695,0.418}I}~. We provide Caesar input files for examples in Section 5 in Appendix 0.B , verifying upper bounds on expected rewards using the induction proof rule. In addition, Caesar supports analysis of (finite) operational semantics with integer variables via the probabilistic model checker Storm [ 15 ] . For infinite-state operational semantics (c.f. Figure 3 ), Storm can under-approximate the expected value. 7 Related Work Expected Run-Time Analysis. In Section 3.2 , we discussed the lack of support for e.g. higher moments of the ert calculus [ 17 , 18 ] . The same problems apply to the amortized expected runtime calculus [ 5 ] , which extends the ert calculus to reason about potential functions, see Appendix 0.C for details. Automated inference of ert -style run-times has been studied e.g. in [ 32 ] . We assume non-negative rewards; analyses for mixed-sign rewards include [ 38 , 9 ] . As a complimentary approach, [ 1 ] propose asymptotic bounds for run-time analysis instead of expected values. Higher Moments. \Citeauthor *DBLP:conf/qest/KaminskiKM16 aim to reason about covariances of probabilistic programs [ 19 ] . They define a semantics called \mathsf{rt} that increments a dedicated runtime variable \tau by one for each statement executed and consider the expected value of \tau^{k} on termination. However, as explained in Section 3.2 , this approach is deficient for diverging programs. \Citeauthor *DBLP:conf/tacas/KuraUH19 [ 24 ] focus on tail probabilities of run-times and make use of higher moments to obtain bounds on them. They synthesize upper bounds on the k -th moment via template-based invariants. In [ 37 ] , [ 37 ] present an automated approach for the inference of higher moments of expected runtimes of probabilistic programs. As for the previous approach, proof rules have to be proven specifically for their semantics. Lower bounds are also considered and used to derive central moments. Their approach is automated, and uses template-based invariant synthesis for interval bounds. Algebraic methods for higher moments of step-indexed expected value have been used in [ 30 ] . On programs with certain restrictions, e.g. acyclic non-linear variable dependencies and variables in conditions only assuming finitely many values, they can compute closed-form solutions for all moments. Hardness results for higher moments of step-indexed expected values are presented in [ 31 ] . 8 Conclusion We presented probabilistic programs with reward statements to obtain a one-fits-all approach for analyzing multiple objectives, e.g. expected runtimes, expected visiting times, higher moments of expected rewards, or the expected excess over a threshold. All reduce to the “classical” wp calculus, eliminating the need for dedicated calculi/semantics for each objective. Therefore, existing proof rules and tools for wp can be reused in our setting. Future work includes the incorporation of programs with non-determinism; programmatic reward modeling works in this setting as well, but the reward transformation introduces additional subtleties due to additional information introduced by the counter variable \tau . Appendix 0.A Proofs 0.A.1 Definitions for Section 2 \displaystyle({\Downarrow},\sigma)\xrightarrow{1}\bot\hskip 16.38895pt\hskip 16.38895pt\bot\xrightarrow{1}\bot ({\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}},\sigma)\xrightarrow{1}({\Downarrow},\sigma) ({x}\,{\coloneqq}\,{a},\sigma)\xrightarrow{1}({\Downarrow},\sigma[{x}\mapsto{a}]) ({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a},\sigma)\xrightarrow{1}({\Downarrow},\sigma) \displaystyle({\color[rgb]{0.5016,0.2203,0}S_{1}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S_{2}},\sigma)\xrightarrow{p}({\color[rgb]{0.5016,0.2203,0}S_{2}},\sigma^{\prime})({\color[rgb]{0.5016,0.2203,0}S_{1}},\sigma)\xrightarrow{p}({\Downarrow},\sigma^{\prime}) \displaystyle({\color[rgb]{0.5016,0.2203,0}S_{1}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S_{2}},\sigma)\xrightarrow{p}({\color[rgb]{0.5016,0.2203,0}S_{1}}^{\prime}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S_{2}},\sigma^{\prime})({\color[rgb]{0.5016,0.2203,0}S_{1}},\sigma)\xrightarrow{p}({\color[rgb]{0.5016,0.2203,0}S_{1}}^{\prime},\sigma^{\prime}) \displaystyle(\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~[{p}]~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\},\sigma)\xrightarrow{p}({\color[rgb]{0.5016,0.2203,0}S_{1}},\sigma) \displaystyle(\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~[{p}]~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\},\sigma)\xrightarrow{1-p}({\color[rgb]{0.5016,0.2203,0}S_{2}},\sigma) \displaystyle({\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\},\sigma)\xrightarrow{1}({\color[rgb]{0.5016,0.2203,0}S_{1}},\sigma)\llbracket b\rrbracket_{\sigma}=\texttt{true} \displaystyle({\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\},\sigma)\xrightarrow{1}({\color[rgb]{0.5016,0.2203,0}S_{2}},\sigma)\llbracket b\rrbracket_{\sigma}=\texttt{false} \displaystyle({\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S}}~\},\sigma)\xrightarrow{1}({\color[rgb]{0.5016,0.2203,0}S}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S}}~\},\sigma)\llbracket b\rrbracket_{\sigma}=\texttt{true} \displaystyle({\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S}}~\},\sigma)\xrightarrow{1}({\Downarrow},\sigma)\llbracket b\rrbracket_{\sigma}=\texttt{false} Figure 7 : Operational semantics for pGCL programs, where ({\color[rgb]{0.5016,0.2203,0}S_{1}},\sigma)\xrightarrow{p}({\color[rgb]{0.5016,0.2203,0}S_{2}},\sigma^{\prime}) iff \mathsf{Prob}(({\color[rgb]{0.5016,0.2203,0}S_{1}},\sigma))(({\color[rgb]{0.5016,0.2203,0}S_{2}},\sigma^{\prime}))=p , for \sigma\in\mathsf{States} and {\color[rgb]{0.5016,0.2203,0}S},{\color[rgb]{0.5016,0.2203,0}S_{1}},{\color[rgb]{0.5016,0.2203,0}S_{2}}\in\textsf{{pGCL}} . For a program {\color[rgb]{0.5016,0.2203,0}S} , its operational Markov chain \mathcal{M}_{{\color[rgb]{0.5016,0.2203,0}S}}^{\sigma_{1}}=(\mathfrak{S},\mathsf{Prob},s_{1},\mathsf{rew}) is given by the reachable configurations \mathfrak{S}\subseteq(\textsf{{pGCL}}\cup\Set{{\Downarrow}})\times\mathsf{States}\cup\Set{\bot} with transition probabilities \mathsf{Prob} as the smallest relation defined by the inference rules in Figure 7 , initial configuration s_{1}=({\color[rgb]{0.5016,0.2203,0}S},\sigma_{1}) , and reward function \mathsf{rew} defined as follows: \displaystyle\mathsf{rew}({({\color[rgb]{0.5016,0.2203,0}S},\sigma)})=\begin{cases}r&\text{if }(\exists{\color[rgb]{0.5016,0.2203,0}S}^{\prime}\in\textsf{{pGCL}}.~{\color[rgb]{0.5016,0.2203,0}S}={\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{r}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S}^{\prime})\lor({\color[rgb]{0.5016,0.2203,0}S}={\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{r})\\ 0&\text{otherwise}\end{cases} For the web server program in Figure 1(a) , Figure 8 shows its operational Markov chain from an arbitrary initial state \sigma with explicit configurations, and is a full version of Figure 3 from the main text. \displaystyle B \displaystyle\coloneqq{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\{{{done}\,{\coloneqq}\,{\texttt{true}}}\}~[{\nicefrac{{1}}{{2}}}]~\{{{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}}\},\hskip 16.38895ptL\coloneqq{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({\neg done})~\{~{B}~\}, \displaystyle\sigma_{F} \displaystyle\coloneqq\sigma[{done}\mapsto{\texttt{false}}],\hskip 16.38895pt\sigma_{T}\coloneqq\sigma_{F}[{done}\mapsto{\texttt{true}}] \bigl({done}\,{\coloneqq}\,{\texttt{false}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}L,\sigma\bigr) \bigl(L,\sigma_{F}\bigr) \bigl(B{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}L,\sigma_{F}\bigr) \mathsf{rew}({(B{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}L,\sigma_{F})})=1 \bigl({done}\,{\coloneqq}\,{\texttt{true}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}L,\sigma_{F}\bigr) \bigl(L,\sigma_{T}\bigr) \bigl({\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}L,\sigma_{F}\bigr) \bigl({\Downarrow},\sigma_{T}\bigr) \bot 0.5 0.5 Figure 8 : Configuration-level operational MC for the web server program from Figure 1(a) , instantiated from an arbitrary initial state \sigma ; this is a full version of Figure 3 . 0.A.2 Proofs for Section 3 See 1 Proof Let {\color[rgb]{0.5016,0.2203,0}S}\in\textsf{{pGCL}} , {\color[rgb]{0,0.2695,0.418}X}\in\mathbb{E} , and \sigma\in\mathsf{States} . By wp semantics, we have \textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})(\sigma)=\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket(\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{{\color[rgb]{0,0.2695,0.418}X}}}\rrbracket(0))(\sigma) . By wp soundness, this is equal to \textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{{\color[rgb]{0,0.2695,0.418}X}}}\rrbracket(0)(\sigma)=\mathsf{E}(\mathsf{rew}^{\sigma}_{0}({{\color[rgb]{0.5016,0.2203,0}S}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{{\color[rgb]{0,0.2695,0.418}X}}}))=\mathsf{E}(\mathsf{rew}^{\sigma}({{\color[rgb]{0.5016,0.2203,0}S}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{{\color[rgb]{0,0.2695,0.418}X}}})). {\color[rgb]{0.5016,0.2203,0}S} \textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) skip {\color[rgb]{0,0.2695,0.418}X} {x}\,{\coloneqq}\,{a} {\color[rgb]{0,0.2695,0.418}X}[{x}\mapsto{a}] {\color[rgb]{0.5016,0.2203,0}S_{1}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S_{2}} \textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\rrbracket(\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})) \{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~[{p}]~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\} p\cdot\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})+(1-p)\cdot\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) {\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\} \left[{b}\right]\cdot\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})+\left[{\neg b}\right]\cdot\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) {\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\} \mathrm{lfp}\,{{\color[rgb]{0,0.2695,0.418}Y}}.~{\left[{b}\right]\cdot(1+\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}\rrbracket({\color[rgb]{0,0.2695,0.418}Y}))+\left[{\neg b}\right]\cdot{\color[rgb]{0,0.2695,0.418}X}} Figure 9 : Inductive definition of the expected run-time transformer for program {\color[rgb]{0.5016,0.2203,0}S} , \textsf{{ert}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket\colon\mathbb{E}\to\mathbb{E} where {\color[rgb]{0,0.2695,0.418}X}\in\mathbb{E} is the post-runtime . The only differences to standard wp semantics ( Figure 4 ) is the “ +1 ” in the while loop and missing reward statement. See 2 Proof We consider the expected runtime semantics \textsf{{ert}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket from [ 17 , 18 ] with the runtime model that counts loop iterations only. Figure 9 shows the inductive definition of \textsf{{ert}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket , which only differs from standard wp semantics by the “ +1 ” in the while loop case and the absence of the reward statement. Consider a loop {\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\} . We show for all expectations {\color[rgb]{0,0.2695,0.418}X}\in\mathbb{E} : \textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})~{}={}~\textsf{{ert}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})~. For the programmatic reward loop, we have: \displaystyle\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) \displaystyle=\mathrm{lfp}\,{{\color[rgb]{0,0.2695,0.418}Y}}.~{\left[{b}\right]\cdot\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{1}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}\rrbracket({\color[rgb]{0,0.2695,0.418}Y})+\left[{\neg b}\right]\cdot{\color[rgb]{0,0.2695,0.418}X}} \displaystyle=\mathrm{lfp}\,{{\color[rgb]{0,0.2695,0.418}Y}}.~{\left[{b}\right]\cdot\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{1}}\rrbracket(\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}\rrbracket({\color[rgb]{0,0.2695,0.418}Y}))+\left[{\neg b}\right]\cdot{\color[rgb]{0,0.2695,0.418}X}} \displaystyle=\mathrm{lfp}\,{{\color[rgb]{0,0.2695,0.418}Y}}.~{\left[{b}\right]\cdot(1+\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}\rrbracket({\color[rgb]{0,0.2695,0.418}Y}))+\left[{\neg b}\right]\cdot{\color[rgb]{0,0.2695,0.418}X}}~, which is equal to the expected runtime semantics: \displaystyle\textsf{{ert}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) The last equality holds because \textsf{{ert}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}\rrbracket=\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}\rrbracket since {\color[rgb]{0.5016,0.2203,0}S^{\prime}} is loop-free. This lemma can be extended to nested loops by induction on the structure of the program, and adding the reward statements into every loop body. 0.A.3 Proofs for Section 4 We state the program transformation functions of Definition 1 in more detail here, to aid the proofs below. Figure 10 defines the program transformation \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) and an auxiliary transformation \mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}) . The (outer) transformation \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) simply adds the variable \tau , initializes it to 0 , prepends {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{f(0)} , and invokes the auxiliary transformation \mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}) . The latter handles the transformation of reward statements, recursively applying the transformation to the sub-statements of {\color[rgb]{0.5016,0.2203,0}S} . Every {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} statement is transformed to {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(f(\tau+a)-f(\tau))} , and the variable \tau is updated with {\tau}\,{\coloneqq}\,{\tau+a} . Other statements are left unchanged. {\color[rgb]{0.5016,0.2203,0}S} \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) {\color[rgb]{0.5016,0.2203,0}S} {\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{f(0)}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}) {\color[rgb]{0.5016,0.2203,0}S} \mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}) skip skip {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(f(\tau+a)-f(\tau))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a} {x}\,{\coloneqq}\,{a} {x}\,{\coloneqq}\,{a} \{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~[{p}]~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\} \{{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\}~[{p}]~\{{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\} {\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\} {\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\} {{\color[rgb]{0.5016,0.2203,0}S_{1}}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{{\color[rgb]{0.5016,0.2203,0}S_{2}}} \mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}}){\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}}) {\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\} {\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S^{\prime}})}~\} Figure 10 : Program transformation \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) and auxiliary transformation \mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}) for monotonic f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} and fresh variable \tau not occurring in {\color[rgb]{0.5016,0.2203,0}S} . Theorem 4.1 states that the transformation \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) correctly transforms the expected reward of {\color[rgb]{0.5016,0.2203,0}S} according to f . The proof of Theorem 4.1 is mostly technical; the main conceptual argument is provided by Theorem 4.6 (c.f. Section 4.2 ). See 4.1 Proof Let \sigma_{1}\in\mathsf{States} be an arbitrary initial state. Define \mathcal{M}_{\mathsf{prog}}\coloneqq\mathcal{M}_{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}^{\sigma_{1}},\qquad\mathcal{M}_{\mathsf{mc}}\coloneqq\mathcal{T}_{f}(\mathcal{M}_{{\color[rgb]{0.5016,0.2203,0}S}}^{\sigma_{1}})~. We compare these two Markov chains, where \mathcal{M}_{\mathsf{mc}} is obtained by the Markov chain transformation from Theorem 4.6 . We need to assume that f(0)=0 holds for Theorem 4.6 , but Lemma 4 shows that this restriction can be lifted by another simple transformation. The Markov chains \mathcal{M}_{\mathsf{prog}} and \mathcal{M}_{\mathsf{mc}} are essentially the same, except for the following differences: • The states of \mathcal{M}_{\mathsf{prog}} are program states \sigma\in\mathsf{States} (extended with fresh variable \tau ), while the states of \mathcal{M}_{\mathsf{mc}} are pairs (\sigma,\tau)\in\mathsf{States}\times\mathbb{R}_{\geq 0}^{\infty} . These are equivalent representations of the same states. • The statement {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} is transformed into the sequential composition of {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(f(\tau+a)-f(\tau))} and {\tau}\,{\coloneqq}\,{\tau+a} . Let \sigma_{i} be the state at some point i of the execution of {\color[rgb]{0.5016,0.2203,0}S} and let \alpha_{i} be the cumulative reward collected up to this point. At a reward statement, \mathcal{M}_{\mathsf{mc}} will execute one step: (({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(f(\tau+a)-f(\tau))},\sigma_{i}),\alpha_{i})~. On the other hand, we have three steps in \mathcal{M}_{\mathsf{prog}} : \displaystyle({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(f(\tau+a)-f(\tau))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a},\sigma_{i}^{\prime}) \displaystyle\quad\xrightarrow{1}({\Downarrow}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a},\sigma_{i}^{\prime}) \displaystyle\quad\xrightarrow{1}({\tau}\,{\coloneqq}\,{\tau+a},\sigma_{i}^{\prime})~. However, the probabilities and cumulative rewards of these paths are equal. As a result, we can conclude that the expected rewards of both Markov chains are equal: \displaystyle\mathsf{E}(\mathsf{rew}({\mathcal{M}_{\mathsf{prog}}})) \displaystyle~{}={}~\mathsf{E}(\mathsf{rew}({\mathcal{M}_{\mathsf{mc}}}))~. By Theorem 4.6 , \mathcal{M}_{\mathsf{mc}} satisfies \displaystyle\mathsf{E}(\mathsf{rew}({\mathcal{M}_{\mathsf{mc}}})) \displaystyle~{}={}~\mathsf{E}(f(\mathsf{rew}({\mathcal{M}_{{\color[rgb]{0.5016,0.2203,0}S}}^{\sigma_{1}}})))~. Thus, we have \mathsf{E}(f(\mathsf{rew}^{\sigma_{1}}({{\color[rgb]{0.5016,0.2203,0}S}})))=\mathsf{E}(f(\mathsf{rew}({\mathcal{M}_{{\color[rgb]{0.5016,0.2203,0}S}}^{\sigma_{1}}})))=\mathsf{E}(\mathsf{rew}({\mathcal{M}_{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}^{\sigma_{1}}})) for all \sigma_{1}\in\mathsf{States} , which is equivalent to \mathsf{E}(\mathsf{rew}({\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}))=\mathsf{E}(f(\mathsf{rew}({{\color[rgb]{0.5016,0.2203,0}S}}))) . See 4.2 Proof Let {\color[rgb]{0.5016,0.2203,0}S}\in\textsf{{pGCL}} and let f,g\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} be monotonic functions with f(x)\leq g(x) for all x\in\mathbb{R}_{\geq 0}^{\infty} . We show by structural induction on {\color[rgb]{0.5016,0.2203,0}S} that \displaystyle\forall{\color[rgb]{0,0.2695,0.418}X}\in\mathbb{E}.\quad\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})\leq\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})~. (2) Base cases: \bullet {\color[rgb]{0.5016,0.2203,0}S}={\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}} : \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})={\color[rgb]{0,0.2695,0.418}X} \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0,0.4348,0.3145}{\texttt{skip}}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) \bullet {\color[rgb]{0.5016,0.2203,0}S}={x}\,{\coloneqq}\,{a} : \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({x}\,{\coloneqq}\,{a})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})=\textsf{{wp}}\llbracket{{x}\,{\coloneqq}\,{a}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})={\color[rgb]{0,0.2695,0.418}X}[{x}\mapsto{a}] \displaystyle=\textsf{{wp}}\llbracket{{x}\,{\coloneqq}\,{a}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({x}\,{\coloneqq}\,{a})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) \bullet {\color[rgb]{0.5016,0.2203,0}S}={\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} : \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(f(\tau+a)-f(\tau))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a}) ) \displaystyle=(f(\tau+a)-f(\tau))+{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}] (definition of wp ) \displaystyle\leq(g(\tau+a)-g(\tau))+{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}] (monotonicity of f and g ) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(g(\tau+a)-g(\tau))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}^{\prime}_{g}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a}) ) Now assume the induction hypothesis holds for {\color[rgb]{0.5016,0.2203,0}S_{1}},{\color[rgb]{0.5016,0.2203,0}S_{2}},{\color[rgb]{0.5016,0.2203,0}S^{\prime}}\in\textsf{{pGCL}} . \bullet {\color[rgb]{0.5016,0.2203,0}S}={{\color[rgb]{0.5016,0.2203,0}S_{1}}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{{\color[rgb]{0.5016,0.2203,0}S_{2}}} : \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({{\color[rgb]{0.5016,0.2203,0}S_{1}}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{{\color[rgb]{0.5016,0.2203,0}S_{2}}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}}){\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}^{\prime}_{f}(\cdot) ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\rrbracket(\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})) (definition of wp ) \displaystyle\leq\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\rrbracket(\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})) (induction hypothesis) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{1}}){\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({{\color[rgb]{0.5016,0.2203,0}S_{1}}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{{\color[rgb]{0.5016,0.2203,0}S_{2}}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}^{\prime}_{g}(\cdot) ) \bullet {\color[rgb]{0.5016,0.2203,0}S}=\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~[{p}]~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\} : \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}(\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~[{p}]~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) \displaystyle=\textsf{{wp}}\llbracket{\{{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\}~[{p}]~\{{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}^{\prime}_{f}(\cdot) ) \displaystyle=p\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})+(1-p)\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) \displaystyle\leq p\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})+(1-p)\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (induction hypothesis) \displaystyle=\textsf{{wp}}\llbracket{\{{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\}~[{p}]~\{{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}(\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~[{p}]~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}^{\prime}_{g}(\cdot) ) \bullet {\color[rgb]{0.5016,0.2203,0}S}={\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\} : \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}^{\prime}_{f}(\cdot) ) \displaystyle=\left[{b}\right]\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})+\left[{\neg b}\right]\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) \displaystyle\leq\left[{b}\right]\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})+\left[{\neg b}\right]\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (induction hypothesis) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{1}})}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0,0.4348,0.3145}{\texttt{if}}}~({b})~\{{{\color[rgb]{0.5016,0.2203,0}S_{1}}}\}~{\color[rgb]{0,0.4348,0.3145}{\texttt{else}}}~\{{{\color[rgb]{0.5016,0.2203,0}S_{2}}}\})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}^{\prime}_{g}(\cdot) ) \bullet {\color[rgb]{0.5016,0.2203,0}S}={\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\} : Recall that \textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) is defined as the least fixed point of the functional \Phi_{\color[rgb]{0,0.2695,0.418}X}({\color[rgb]{0,0.2695,0.418}Y})=\left[{b}\right]\cdot\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}\rrbracket({\color[rgb]{0,0.2695,0.418}Y})+\left[{\neg b}\right]\cdot{\color[rgb]{0,0.2695,0.418}X}~. By Kleene’s fixed point theorem, we have \textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})=\sup_{n\in\mathbb{N}}\Phi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0)~. Denote by \Phi_{\color[rgb]{0,0.2695,0.418}X} the functional for the transformed while loop \mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\}) and by \Psi_{\color[rgb]{0,0.2695,0.418}X} the functional for \mathcal{T}^{\prime}_{g}({\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\}) . We show by induction on n that \Phi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0)\leq\Psi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0) holds for all n\in\mathbb{N} . The base case n=0 holds since \Phi_{\color[rgb]{0,0.2695,0.418}X}^{0}(0)=0=\Psi_{\color[rgb]{0,0.2695,0.418}X}^{0}(0) . For the induction step, assume \Phi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0)\leq\Psi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0) . Then, \displaystyle\Phi_{\color[rgb]{0,0.2695,0.418}X}^{n+1}(0)=\Phi_{\color[rgb]{0,0.2695,0.418}X}(\Phi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0)) \displaystyle=\left[{b}\right]\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S^{\prime}})}\rrbracket(\Phi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0))+\left[{\neg b}\right]\cdot{\color[rgb]{0,0.2695,0.418}X} (definition of \Phi_{\color[rgb]{0,0.2695,0.418}X} ) \displaystyle\leq\left[{b}\right]\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S^{\prime}})}\rrbracket(\Psi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0))+\left[{\neg b}\right]\cdot{\color[rgb]{0,0.2695,0.418}X} (induction hypothesis and monotonicity of \textsf{{wp}}\llbracket{\cdot}\rrbracket ) \displaystyle=\Psi_{\color[rgb]{0,0.2695,0.418}X}(\Psi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0)) (definition of \Psi_{\color[rgb]{0,0.2695,0.418}X} ) \displaystyle=\Psi_{\color[rgb]{0,0.2695,0.418}X}^{n+1}(0)~. Thus, by induction, we have \Phi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0)\leq\Psi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0) for all n\in\mathbb{N} . It follows that \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})=\sup_{n\in\mathbb{N}}\Phi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0) \displaystyle\leq\sup_{n\in\mathbb{N}}\Psi_{\color[rgb]{0,0.2695,0.418}X}^{n}(0)=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({b})~\{~{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}~\})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})~. This concludes the induction. Finally, for the full transformation \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) , we have \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) \displaystyle=\textsf{{wp}}\llbracket{{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{f(0)}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) ) \displaystyle=f(0)+\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau}\mapsto{0}] (definition of wp ) \displaystyle\leq g(0)+\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau}\mapsto{0}] ( f(0)\leq g(0) ) \displaystyle\leq g(0)+\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau}\mapsto{0}] ( Equation 2 ) \displaystyle=\textsf{{wp}}\llbracket{{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{g(0)}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}_{g}({\color[rgb]{0.5016,0.2203,0}S}) ) See 4.3 Proof Let f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} monotonic and \alpha,\beta\in\mathbb{R}_{\geq 0} . Denote g=\alpha\cdot f+\beta . First, we show that auxiliary transformation \mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S}) preserves scalar multiplication. For all {\color[rgb]{0.5016,0.2203,0}S}\in\textsf{{pGCL}} and {\color[rgb]{0,0.2695,0.418}X}\in\mathbb{E} , we have \textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(\alpha\cdot{\color[rgb]{0,0.2695,0.418}X})=\alpha\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})~. The proof is by structural induction on {\color[rgb]{0.5016,0.2203,0}S} . The interesting case is {\color[rgb]{0.5016,0.2203,0}S}={\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} : \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a})}\rrbracket(\alpha\cdot{\color[rgb]{0,0.2695,0.418}X}) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{g(\tau+a)-g(\tau)}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a}}\rrbracket(\alpha\cdot{\color[rgb]{0,0.2695,0.418}X}) (def. \mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S}) ) \displaystyle=(g(\tau+a)-g(\tau))+\alpha\cdot{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}] (def. wp ) \displaystyle=((\alpha\cdot f(\tau+a)+\beta)-(\alpha\cdot f(\tau)+\beta))+\alpha\cdot{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}] (def. g ) \displaystyle=\alpha\cdot(f(\tau+a)-f(\tau))+\alpha\cdot{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}] (cancellation of \beta ) \displaystyle=\alpha\cdot(f(\tau+a)-f(\tau)+{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}]) (linearity) \displaystyle=\alpha\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (def. of wp ) The other cases proceed in a straightforward manner. For the full transformation \mathcal{T}_{g}({\color[rgb]{0.5016,0.2203,0}S}) , we have \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(\alpha\cdot{\color[rgb]{0,0.2695,0.418}X}) \displaystyle=\textsf{{wp}}\llbracket{{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{g(0)}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(\alpha\cdot{\color[rgb]{0,0.2695,0.418}X}) (def. \mathcal{T}_{g}({\color[rgb]{0.5016,0.2203,0}S}) ) \displaystyle=g(0)+\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(\alpha\cdot{\color[rgb]{0,0.2695,0.418}X})[{\tau}\mapsto{0}] (def. wp ) \displaystyle=\alpha\cdot f(0)+\beta+\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(\alpha\cdot{\color[rgb]{0,0.2695,0.418}X})[{\tau}\mapsto{0}] (def. g ) \displaystyle=\alpha\cdot f(0)+\alpha\cdot\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau}\mapsto{0}]+\beta (above) \displaystyle=\alpha\cdot\textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})+\beta (def. \mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}) ) Using {\color[rgb]{0,0.2695,0.418}X}=0 , the statement \textsf{{wp}}\llbracket{\mathcal{T}_{g}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)=\alpha\cdot\textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)+\beta follows. See 4.4 Proof Let {\color[rgb]{0.5016,0.2203,0}S}\in\textsf{{pGCL}} , f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} such that f(x)=\alpha\cdot x+\beta for some \alpha,\beta\in\mathbb{R}_{\geq 0} . Let {\color[rgb]{0,0.2695,0.418}X}\in\mathbb{E} such that \tau does not occur in {\color[rgb]{0,0.2695,0.418}X} , i.e. \forall\sigma\in\mathsf{States},v\in\mathsf{Vals}.~{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{v}]={\color[rgb]{0,0.2695,0.418}X} . For the transformation by \mathcal{T}^{\prime}_{{\color[rgb]{0.5016,0.2203,0}S}}(f) for reward statements, we have: \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(f(\tau+a)-f(\tau))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of \mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a}) ) \displaystyle=(f(\tau+a)-f(\tau))+{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}] (definition of wp ) \displaystyle=(\alpha\cdot(\tau+a)+\beta-(\alpha\cdot\tau+\beta))+{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}] (definition of f ) \displaystyle=\alpha\cdot a+{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}] (cancellation of \beta ) \displaystyle=\alpha\cdot a+{\color[rgb]{0,0.2695,0.418}X} ( \tau not in {\color[rgb]{0,0.2695,0.418}X} ) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{\alpha\cdot a}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) For the full transformation \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) , we have: \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})(\sigma) \displaystyle=\textsf{{wp}}\llbracket{{\tau}\,{\coloneqq}\,{0}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{f(0)}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})(\sigma) (definition of \mathcal{T}_{f}({\color[rgb]{0.5016,0.2203,0}S}) ) \displaystyle=f(0)+\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau}\mapsto{0}](\sigma) (definition of wp ) \displaystyle=f(0)+\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) ( \tau not in \textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) ) \displaystyle=(\alpha\cdot 0+\beta)+\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of f ) \displaystyle=\beta+\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (simplification) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{\beta}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) Therefore, the simplification is valid and \tau can be omitted for linear transformations. See 4.5 Proof By definition of wp , it suffices to show \textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S}))}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau^{\prime}}\mapsto{f(\tau)}]=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}[{\tau^{\prime}}\mapsto{f(\tau)}])~. We proceed by induction over the structure of {\color[rgb]{0.5016,0.2203,0}S} . Of the base cases, {\color[rgb]{0.5016,0.2203,0}S}={\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a} is the interesting one: \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a}))}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau^{\prime}}\mapsto{f(\tau)}] \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(f(\tau+a)-f(\tau))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a})}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau^{\prime}}\mapsto{f(\tau)}] (definition of \mathcal{T}^{\prime}_{f}(\cdot) ) \displaystyle=\textsf{{wp}}\left\llbracket{\begin{aligned} &{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(g(\tau^{\prime}+(f(\tau+a)-f(\tau)))-g(\tau^{\prime}))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\\ &{\tau^{\prime}}\,{\coloneqq}\,{\tau^{\prime}+(f(\tau+a)-f(\tau))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\\ &{\tau}\,{\coloneqq}\,{\tau+a}\end{aligned}}\right\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau^{\prime}}\mapsto{f(\tau)}] (definition of \mathcal{T}^{\prime}_{g}(\cdot) ) \displaystyle=(g(\tau^{\prime}+(f(\tau+a)-f(\tau)))-g(\tau^{\prime}) \displaystyle\quad+{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}][{\tau^{\prime}}\mapsto{\tau^{\prime}+(f(\tau+a)-f(\tau))}])[{\tau^{\prime}}\mapsto{f(\tau)}] (definition of wp ) \displaystyle=g(f(\tau)+(f(\tau+a)-f(\tau)))-g(f(\tau)) \displaystyle\quad+{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}][{\tau^{\prime}}\mapsto{f(\tau)+(f(\tau+a)-f(\tau))}] (substitution) \displaystyle=g(f(\tau+a))-g(f(\tau))+{\color[rgb]{0,0.2695,0.418}X}[{\tau}\mapsto{\tau+a}][{\tau^{\prime}}\mapsto{f(\tau+a)}] ( f(\tau)+(f(\tau+a)-f(\tau))=f(\tau+a) ) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(g(f(\tau+a))-g(f(\tau)))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau^{\prime}}\,{\coloneqq}\,{f(\tau+a)}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (definition of wp ) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(g(f(\tau+a))-g(f(\tau)))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau^{\prime}}\,{\coloneqq}\,{f(\tau)}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}) (exchange assignments) \displaystyle=\textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(g(f(\tau+a))-g(f(\tau)))}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{\tau}\,{\coloneqq}\,{\tau+a}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}[{\tau^{\prime}}\mapsto{f(\tau)}]) (definition of wp ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{a})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}[{\tau^{\prime}}\mapsto{f(\tau)}]) (definition of \mathcal{T}^{\prime}_{g\circ f}(\cdot) ) The other base cases are straightforward. For the inductive cases, assume that the claim holds for {\color[rgb]{0.5016,0.2203,0}S_{1}} and {\color[rgb]{0.5016,0.2203,0}S_{2}} . We show the case for sequential composition {\color[rgb]{0.5016,0.2203,0}S}={{\color[rgb]{0.5016,0.2203,0}S_{1}}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{{\color[rgb]{0.5016,0.2203,0}S_{2}}} : \displaystyle\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({{\color[rgb]{0.5016,0.2203,0}S_{1}}}{\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}{{\color[rgb]{0.5016,0.2203,0}S_{2}}}))}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau^{\prime}}\mapsto{f(\tau)}] \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}}){\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}}))}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau^{\prime}}\mapsto{f(\tau)}] (definition of \mathcal{T}^{\prime}_{f}(\cdot) ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}})){\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}}))}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau^{\prime}}\mapsto{f(\tau)}] (definition of \mathcal{T}^{\prime}_{g}(\cdot) ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{1}}))}\rrbracket(\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}}))}\rrbracket({\color[rgb]{0,0.2695,0.418}X}))[{\tau^{\prime}}\mapsto{f(\tau)}] (definition of wp ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g}(\mathcal{T}^{\prime}_{f}({\color[rgb]{0.5016,0.2203,0}S_{2}}))}\rrbracket({\color[rgb]{0,0.2695,0.418}X})[{\tau^{\prime}}\mapsto{f(\tau)}]) (induction hypothesis for {\color[rgb]{0.5016,0.2203,0}S_{1}} ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}[{\tau^{\prime}}\mapsto{f(\tau)}])) (induction hypothesis for {\color[rgb]{0.5016,0.2203,0}S_{2}} ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0.5016,0.2203,0}S_{1}}){\color[rgb]{0,0.4348,0.3145}{\texttt{;}~}}\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0.5016,0.2203,0}S_{2}})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}[{\tau^{\prime}}\mapsto{f(\tau)}]) (definition of wp ) \displaystyle=\textsf{{wp}}\llbracket{\mathcal{T}^{\prime}_{g\circ f}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket({\color[rgb]{0,0.2695,0.418}X}[{\tau^{\prime}}\mapsto{f(\tau)}]) (definition of \mathcal{T}^{\prime}_{g\circ f}(\cdot) ) The other inductive cases are straightforward. Hence, the claim follows by induction. See 4.6 Proof We one-to-one relate every finite path \pi=\sigma_{1}\ldots\sigma_{n} of the original Markov chain \mathcal{M} to a finite path \pi^{\prime}=\sigma_{1}^{\prime}\ldots\sigma_{n}^{\prime} in the transformed Markov chain \mathcal{T}_{f}(\mathcal{M}) . We use two properties of Lemma 3 below to show that the expected rewards of the two paths are equal. (1) \pi and \pi^{\prime} have the same probabilities: \mathsf{Prob}(\pi)=\mathsf{Prob^{\prime}}(\pi^{\prime}) . (3) The f -transformed reward is equal to the reward of \pi^{\prime} : f(\mathsf{rew}({\pi}))=\mathsf{rew}^{\prime}({\pi^{\prime}}) . We obtain: \displaystyle\phantom{=}\mathsf{E}(f(\mathsf{rew}({\mathcal{M}}))) \displaystyle~{}={}~\sup_{n\in\mathbb{N}}\sum_{\pi\in\mathsf{Paths}^{=n}_{\mathcal{M}}(\sigma)}\mathsf{Prob}(\pi)\cdot f(\mathsf{rew}({\pi})) \displaystyle=\mathsf{E}(\mathsf{rew}^{\prime}({\mathcal{T}_{f}(\mathcal{M})})) \displaystyle~{}={}~\sup_{n\in\mathbb{N}}\sum_{\pi^{\prime}\in\mathsf{Paths}^{=n}_{\mathcal{T}_{f}(\mathcal{M})}(\sigma)}\mathsf{Prob^{\prime}}(\pi^{\prime})\cdot\mathsf{rew}^{\prime}({\pi^{\prime}})~. \displaystyle\hfill\square See 3 Proof Let \mathcal{M}=(\mathsf{States},\mathsf{Prob},\sigma_{1},\mathsf{rew}) be a Markov chain and let f\colon\mathbb{R}_{\geq 0}^{\infty}\to\mathbb{R}_{\geq 0}^{\infty} be a monotonic function with f(0)=0 . For each n\geq 1 , define \displaystyle\xi_{n} \displaystyle\colon\mathsf{Paths}^{=n}_{\mathcal{M}}\to\mathsf{Paths}^{=n}_{\mathcal{T}_{f}(\mathcal{M})}, \displaystyle\xi_{n}(\sigma_{1}\ldots\sigma_{n}) \displaystyle\coloneqq(\sigma_{1},\alpha_{1})\ldots(\sigma_{n},\alpha_{n}), where \alpha_{1}=0 and \alpha_{i}=\sum_{j ( y : Int ) 2 pre {\color[rgb]{0,0.2695,0.418}X} 3 post {\color[rgb]{0,0.2695,0.418}Y} 4 { 5 {\color[rgb]{0.5016,0.2203,0}S} 6 } The only difference between proc s and coproc s is that proc s are verified to satisfy lower bounds {\color[rgb]{0,0.2695,0.418}X} on expected values of {\color[rgb]{0,0.2695,0.418}Y} , i.e. {\color[rgb]{0,0.2695,0.418}X}\preceq\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket({\color[rgb]{0,0.2695,0.418}Y})~, and that coproc s are required to satisfy the dual upper bound property, i.e. \textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket({\color[rgb]{0,0.2695,0.418}Y})\preceq{\color[rgb]{0,0.2695,0.418}X}~. To implement probabilistic choices, HeyVL uses the syntax of an ordinary assignment with a distribution expression {\color[rgb]{0,0.4348,0.3145}{\texttt{flip}}}({p}) that returns true with probability p and false with probability 1-p . 0.B.1 Expected Visiting Times for the Fast Dice Roller ( Section 3.3 ) To illustrate the encoding for expected visiting times from Section 3.3 , we consider the fast dice roller (FDR), a runtime-optimal algorithm for sampling uniformly from [1,N] [ 26 ] . s_{0} s_{1} s_{2} s_{3} s_{4} s_{5} s_{6} 1 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 1 1 1 1 1 1 Figure 11 : Markov chain of the fast dice roller (FDR) from [ 29 ] . For N=6 , \Citeauthor DBLP:journals/jar/MertensKQW25 [ 29 ] analyze expected visiting times on the Markov chain shown in Figure 11 . For this example, they compute expected visiting times to reach the states s_{3},s_{4},s_{6} that terminate the algorithm, and from these deduce the expected reachability probabilities of the dice faces. We verify the same bounds on expected visiting times using Caesar, by encoding the Markov chain as simple while loop with probabilistic choices and reward statements. Figure 12 shows the HeyVL code for this encoding. Variable s models the state index, done indicates whether a terminal state has been reached, and res models the sampled dice face. To query the expected visiting time of specific states, we use ghost variables query_s and query_done , and collect reward with {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{\left[{\texttt{query\_s}=s\land\texttt{query\_done}=\texttt{done}}\right]} . The coproc declaration in Figure 12 with {\color[rgb]{0,0.4348,0.3145}{\texttt{pre}}}~{\color[rgb]{0,0.2695,0.418}1/3} specifies that we verify the upper bound of \nicefrac{{1}}{{3}} on the expected visiting time to reach states s\in\{0,\ldots,6\} and done\in\{\texttt{true},\texttt{false}\} . From these bounds, we obtain bounds on the expected reachability probabilities of the terminal states (c.f. [ 29 , Section 6.1.1] ). Since the relevant states s_{3},s_{4},s_{6} have expected visiting time at most \nicefrac{{1}}{{3}} , and each transition from these states to a terminal state has probability \nicefrac{{1}}{{2}} , the expected reachability probability of each terminal state is at most \nicefrac{{1}}{{6}} . One can also verify this last fact by adding more ghost variables to indicate the specific value of the dice face ( res variable) and modifying the reward statements accordingly. The invariant is omitted in Figure 12 for brevity, but given separately in Figure 13 . It specifies, for each queried state and each current state, an upper bound on the expected visiting time from the current state to the queried state. It corresponds to the fundamental matrix , defined in [ 23 , Def. 3.2.2] , originally given as a definition to determine expected visiting times in Markov chains. We also confirmed with Caesar that our invariant is optimal . This was done using the Caesar built-in dual to the wp Park induction proof rule for upper bounds; now we verify a lower bound. Since both lower and upper bounds coincide, the invariant is optimal. 0.B.2 Variance of Web Server ( Example 2 ) For the web server examples in Figure 1 , we made claims about the expected value and variance of the response time. Some details on the calculations were provided in Example 2 , and we add some selected calculations here. We focus on the unmodified example, i.e. Figure 1(a) . For the while loop, the loop-characteristic functional w.r.t. post 0 is given by \Phi_{0}({\color[rgb]{0,0.2695,0.418}X})~{}={}~\left[{\neg done}\right]\cdot((2\cdot\tau+1)+0.5\cdot{\color[rgb]{0,0.2695,0.418}X}[{done}\mapsto{\texttt{true}}]+0.5\cdot{\color[rgb]{0,0.2695,0.418}X})+\left[{done}\right]\cdot 0. To compute the least fixed-point, we make use of Kleene’s fixed point theorem: \textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({\neg done})~\{~{\ldots}~\}}\rrbracket(0)~{}={}~\sup_{n\in\mathbb{N}}\Phi_{0}^{n}(0). The first few iterations give the following results: \displaystyle\Phi_{0}^{0}(0) \displaystyle~{}={}~0, \displaystyle\Phi_{0}^{1}(0) \displaystyle~{}={}~\left[{\neg done}\right]\cdot(2\cdot\tau+1), \displaystyle\Phi_{0}^{2}(0) \displaystyle~{}={}~\left[{\neg done}\right]\cdot(\nicefrac{{1}}{{2}}\cdot(6\cdot\tau+5)), \displaystyle\Phi_{0}^{3}(0) \displaystyle~{}={}~\left[{\neg done}\right]\cdot(\nicefrac{{1}}{{4}}\cdot(14\cdot\tau+15)), \displaystyle\Phi_{0}^{4}(0) \displaystyle~{}={}~\left[{\neg done}\right]\cdot(\nicefrac{{1}}{{8}}\cdot(30\cdot\tau+37))~. From this, we can deduce the following closed form: \displaystyle\Phi_{0}^{n}(0) \displaystyle~{}={}~\left[{\neg done}\right]\cdot\left(\frac{1}{2^{n-1}}\cdot((2^{n+1}-2)\cdot\tau+3\cdot(2^{n}-1)-2\cdot n)\right)~. We make use of the monotone convergence theorem to compute the supremum: \displaystyle\sup_{n\in\mathbb{N}}\Phi_{0}^{n}(0) \displaystyle~{}={}~\lim_{n\to\infty}\Phi_{0}^{n}(0) \displaystyle~{}={}~\left[{\neg done}\right]\cdot(4\cdot\tau+6)~. Hence, we have shown that \textsf{{wp}}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({\neg done})~\{~{\ldots}~\}}\rrbracket(0)~{}={}~\left[{\neg done}\right]\cdot(4\cdot\tau+6) . The full program {\color[rgb]{0.5016,0.2203,0}S} starts with \tau=0 and done=\texttt{false} , therefore \textsf{{wp}}\llbracket{\mathcal{T}_{x^{2}}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)=6 . For a random variable X , we have \mathsf{Var}(X)=\mathsf{E}(X^{2})-\mathsf{E}(X)^{2} . Hence, we compute \textsf{{wp}}\llbracket{\mathcal{T}_{x^{2}}({\color[rgb]{0.5016,0.2203,0}S})}\rrbracket(0)-\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket(0)^{2}=6-2^{2}=2 . For the example program with the cache ( Figure 1(b) ), denoted by {\color[rgb]{0.5016,0.2203,0}S^{\prime}} , we obtain the least fixed-point \left[{\neg done}\right]\cdot(3\cdot(\tau-0.5)+4.5) and obtain the second moment \textsf{{wp}}\llbracket{\mathcal{T}_{x^{2}}({\color[rgb]{0.5016,0.2203,0}S^{\prime}})}\rrbracket(0)=0.25+4.5=4.75 . Since \textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S^{\prime}}}\rrbracket(0)=2 , we obtain the variance 4.75-2^{2}=0.75 . The associated HeyVL code is shown in Figure 14 . Figures 14(a) and 14(b) verify the expected runtime upper bound of 2 for the unmodified and modified examples, respectively. Figures 14(c) and 14(d) verify the second moment upper bounds of 6 and 4.75 , respectively. 0.B.3 Biased Random Walk ( Example 3 ) Recall Example 3 in Section 5.1 , where we consider a biased random walk on the non-negative integers, starting at some initial value init_x . With probability 0.75 , the variable x is decremented by 2 , and with probability 0.25 it is incremented by 2 . After each step, we increment the reward by 1 . It stops when x reaches zero. The HeyVL code for the first moment of the cumulative reward is shown in Figure 16 . The upper bound shown is init_x - ( init_x \% 2) , which means the expected number of steps is upper-bounded by the initial value of x , rounded down to the nearest even number. For the second moment, we apply the transformation \mathcal{T}^{\prime}_{f}(\cdot) to the original program, where f(x)=x^{2} . The resulting program is shown in Figure 16 . As before, the original reward statement is replaced by {\color[rgb]{0,0.4348,0.3145}{\texttt{reward}}}~{(\texttt{tau}+1)^{2}-\texttt{tau}^{2}} and the assignment {\texttt{tau}}\,{\coloneqq}\,{\texttt{tau}+1} . We used the invariant x^{2}+2\cdot x\cdot\texttt{tau}+3\cdot x to to verify the upper bound of x^{2}+3\cdot x . 0.B.4 Cumulative Distribution Function ( Example 4 ) For the web server example in Figure 1(a) , Example 4 in Section 5.2 verifies a bound on the runtime CDF. We encode this objective by applying the transformation with f(x)=\left[{x\geq N}\right] . In the transformed program ( Figure 17 ), \tau tracks runtime and each reward increment is \left[{\tau+1\geq N}\right]-\left[{\tau\geq N}\right]\quad=\quad\left[{\tau+1=N}\right]~, so reward is collected exactly when the run first reaches step N . We use the following loop invariant to verify that \Pr(\text{runtime}\geq N) is at most 0.5^{N\ominus 1} : I~{}={}~\left[{\neg done\land\tau+1\leq N}\right]\cdot\left(\frac{1}{2}\right)^{N-(\tau+1)}~. Note that this invariant requires exponentials, which are not supported by Caesar out of the box, but can be encoded by a user-defined function. This is done using domain Exponentials declaration, which contains a recursive definition of pow , modeling the function a^{b} for a\in\mathbb{R}_{\geq 0} and b\in\mathbb{N} . 0.B.5 Expected Excess ( Example 5 ) Recall Example 5 in Section 5.3 : for the web server loop from Figure 1(a) with per-round success probability p and budget N , the objective is \mathsf{E}(\text{runtime}\ominus N) . Figure 18 encodes the original program, Figure 19 encodes the transformed single-loop variant with f(x)=x\ominus N (hence increment \left[{\tau\geq N}\right] ), and Figure 20 encodes the split two-phase variant. The two transformed encodings both prove the same upper bound \frac{(1-p)^{N}}{p} for all 0 mgf ( x ) < mgf ( y ) ). These axioms fix the initial reward and rule out countermodels such as mgf (0)=1, mgf (1)=0 , where mgf ( tau + x ) - mgf ( tau ) is interpreted in UReal as max (0, mgf ( tau + x )- mgf ( tau )) and the increment is truncated to 0 . 0.B.7 Multiple Rewards ( Example 7 ) Recall Example 7 in Section 5.5 : we track runtime and memory, starting at 2 each, then add runtime with probability p and additional memory with probability q . Figure 22 gives the corresponding Caesar proof encoding in HeyVL. Using f(memory,runtime)=memory\cdot runtime , each update contributes the incremental product difference f(memory^{\prime},runtime^{\prime})-f(memory,runtime) . The file verifies the upper bound 4+(p\cdot(2+(q\cdot 3))) for the expected combined cost. Figure 12 : HeyVL code for verifying expected visiting times in the FDR example. The invariant is given in Figure 13 . ⬇ 1 coproc fdr6 ( query_s : UInt , query_done : Bool ) -> ( res : UInt ) 2 pre !?( query_done == true && query_s <= 6) 3 pre 1/3 4 post 0 5 { 6 var s : UInt = 0 7 var done : Bool = false 8 @invariant (...) 9 while ! done { 10 reward [ query_s == s && query_done == done ] 11 var choice : Bool ; var old_s : UInt = s 12 if old_s == 0 { 13 choice = flip (0.5) 14 if choice { s = 1 } else { s = 2 } 15 } else {}; if old_s == 1 { 16 choice = flip (0.5) 17 if choice { s = 3 } else { s = 4 } 18 } else {}; if old_s == 2 { 19 choice = flip (0.5) 20 if choice { s = 5 } else { s = 6 } 21 } else {}; if old_s == 3 { 22 choice = flip (0.5) 23 if choice { res = 1 } else { res = 2 } 24 done = true 25 } else {}; if old_s == 4 { 26 choice = flip (0.5) 27 if choice { res = 3 } else { res = 4 } 28 done = true 29 } else {}; if old_s == 5 { 30 choice = flip (0.5) 31 if choice { s = 1 } else { s = 2 } 32 } else {}; if old_s == 6 { 33 choice = flip (0.5) 34 if choice { res = 5 } else { res = 6 } 35 done = true 36 } else {} 37 } 38 reward [ query_s == s && query_done == done ] 39 } ⬇ 1 ite ( 2 done , 3 /* then */ [(( query_s == s ) && ( query_done == true ))], 4 /* else */ 5 ite ( 6 ( query_done == false ), 7 /* then */ 8 [ query_s ==0] * [ s ==0] 9 + [ query_s ==1] * ( [ s ==0]*(2/3) + [ s ==1]*(1) + [ s ==2]*(1/3) + [ s ==5]*(2/3) ) 10 + [ query_s ==2] * ( [ s ==0]*(2/3) + [ s ==2]*(4/3) + [ s ==5]*(2/3) ) 11 + [ query_s ==3] * ( [ s ==0]*(1/3) + [ s ==1]*(1/2) + [ s ==2]*(1/6) + [ s ==3]*1 + [ s ==5]*(1/3) ) 12 + [ query_s ==4] * ( [ s ==0]*(1/3) + [ s ==1]*(1/2) + [ s ==2]*(1/6) + [ s ==4]*1 + [ s ==5]*(1/3) ) 13 + [ query_s ==5] * ( [ s ==0]*(1/3) + [ s ==2]*(2/3) + [ s ==5]*(4/3) ) 14 + [ query_s ==6] * ( [ s ==0]*(1/3) + [ s ==2]*(2/3) + [ s ==5]*(1/3) + [ s ==6]*1 ), 15 /* else */ 16 [ query_s ==3] * ( [ s ==0]*(1/3) + [ s ==1]*(1/2) + [ s ==2]*(1/6) + [ s ==3]*1 + [ s ==5]*(1/3) ) 17 + [ query_s ==4] * ( [ s ==0]*(1/3) + [ s ==1]*(1/2) + [ s ==2]*(1/6) + [ s ==4]*1 + [ s ==5]*(1/3) ) 18 + [ query_s ==6] * ( [ s ==0]*(1/3) + [ s ==2]*(2/3) + [ s ==5]*(1/3) + [ s ==6]*1 ) 19 ) 20 ) Figure 13 : Invariant for the FDR expected visiting time verification in Figure 12 . (a) HeyVL code to verify that the expected runtime of the unmodified web server example ( Figure 1(a) ) is upper-bounded by 2 . ⬇ 1 coproc original_moment1 () -> ( done : Bool ) 2 pre 2 3 post 0 4 { 5 done = false 6 @invariant ([! done ] * 2) 7 while ! done { 8 reward 1 9 done = flip (0.5) 10 } 11 } 12 13 coproc caching_moment1 () -> ( done : Bool ) 14 pre 2 15 post 0 16 { 17 done = false 18 reward 0.5 19 @invariant ([! done ] * 1.5) 20 while ! done { 21 reward 1 22 done = flip (2/3) 23 } 24 } 25 26 coproc original_moment2 () -> ( done : Bool ) 27 pre 6 28 post 0 29 { 30 done = false 31 var tau : UInt = 0 32 @invariant ([! done ] * (6 + 4 * tau )) 33 while ! done { 34 reward 2 * tau + 1 35 tau = tau + 1 36 done = flip (0.5) 37 } 38 } 39 40 coproc caching_moment2 () -> ( done : Bool ) 41 pre 4.75 42 post 0 43 { 44 done = false 45 var tau : UReal = 0.5 46 reward 0.25 47 @invariant ([! done ] * (4.5 + 3 * ( tau - 0.5))) 48 while ! done { 49 reward 2 * tau + 1 50 tau = tau + 1 51 done = flip (2/3) 52 } 53 } (b) HeyVL code to verify that the expected runtime of the modified web server example ( Figure 1(b) ) is upper-bounded by 2 . ⬇ 1 coproc original_moment1 () -> ( done : Bool ) 2 pre 2 3 post 0 4 { 5 done = false 6 @invariant ([! done ] * 2) 7 while ! done { 8 reward 1 9 done = flip (0.5) 10 } 11 } 12 13 coproc caching_moment1 () -> ( done : Bool ) 14 pre 2 15 post 0 16 { 17 done = false 18 reward 0.5 19 @invariant ([! done ] * 1.5) 20 while ! done { 21 reward 1 22 done = flip (2/3) 23 } 24 } 25 26 coproc original_moment2 () -> ( done : Bool ) 27 pre 6 28 post 0 29 { 30 done = false 31 var tau : UInt = 0 32 @invariant ([! done ] * (6 + 4 * tau )) 33 while ! done { 34 reward 2 * tau + 1 35 tau = tau + 1 36 done = flip (0.5) 37 } 38 } 39 40 coproc caching_moment2 () -> ( done : Bool ) 41 pre 4.75 42 post 0 43 { 44 done = false 45 var tau : UReal = 0.5 46 reward 0.25 47 @invariant ([! done ] * (4.5 + 3 * ( tau - 0.5))) 48 while ! done { 49 reward 2 * tau + 1 50 tau = tau + 1 51 done = flip (2/3) 52 } 53 } (c) HeyVL code to verify that the second moment of the runtime of the unmodified web server example ( Figure 1(a) ) is upper-bounded by 6 . ⬇ 1 coproc original_moment1 () -> ( done : Bool ) 2 pre 2 3 post 0 4 { 5 done = false 6 @invariant ([! done ] * 2) 7 while ! done { 8 reward 1 9 done = flip (0.5) 10 } 11 } 12 13 coproc caching_moment1 () -> ( done : Bool ) 14 pre 2 15 post 0 16 { 17 done = false 18 reward 0.5 19 @invariant ([! done ] * 1.5) 20 while ! done { 21 reward 1 22 done = flip (2/3) 23 } 24 } 25 26 coproc original_moment2 () -> ( done : Bool ) 27 pre 6 28 post 0 29 { 30 done = false 31 var tau : UInt = 0 32 @invariant ([! done ] * (6 + 4 * tau )) 33 while ! done { 34 reward 2 * tau + 1 35 tau = tau + 1 36 done = flip (0.5) 37 } 38 } 39 40 coproc caching_moment2 () -> ( done : Bool ) 41 pre 4.75 42 post 0 43 { 44 done = false 45 var tau : UReal = 0.5 46 reward 0.25 47 @invariant ([! done ] * (4.5 + 3 * ( tau - 0.5))) 48 while ! done { 49 reward 2 * tau + 1 50 tau = tau + 1 51 done = flip (2/3) 52 } 53 } (d) HeyVL code to verify that the second moment of the runtime of the modified web server example ( Figure 1(b) ) is upper-bounded by 4.75 . ⬇ 1 coproc original_moment1 () -> ( done : Bool ) 2 pre 2 3 post 0 4 { 5 done = false 6 @invariant ([! done ] * 2) 7 while ! done { 8 reward 1 9 done = flip (0.5) 10 } 11 } 12 13 coproc caching_moment1 () -> ( done : Bool ) 14 pre 2 15 post 0 16 { 17 done = false 18 reward 0.5 19 @invariant ([! done ] * 1.5) 20 while ! done { 21 reward 1 22 done = flip (2/3) 23 } 24 } 25 26 coproc original_moment2 () -> ( done : Bool ) 27 pre 6 28 post 0 29 { 30 done = false 31 var tau : UInt = 0 32 @invariant ([! done ] * (6 + 4 * tau )) 33 while ! done { 34 reward 2 * tau + 1 35 tau = tau + 1 36 done = flip (0.5) 37 } 38 } 39 40 coproc caching_moment2 () -> ( done : Bool ) 41 pre 4.75 42 post 0 43 { 44 done = false 45 var tau : UReal = 0.5 46 reward 0.25 47 @invariant ([! done ] * (4.5 + 3 * ( tau - 0.5))) 48 while ! done { 49 reward 2 * tau + 1 50 tau = tau + 1 51 done = flip (2/3) 52 } 53 } Figure 14 : HeyVL code to verify claims about Figure 1 . Figure 15 : HeyVL code representing a biased random walk with initial position init_x . ⬇ 1 coproc random_walk ( init_x : UInt ) -> ( x : UInt ) 2 pre ite ( init_x > 1, init_x - ( init_x % 2), 0) 3 post 0 4 { 5 x = init_x 6 @invariant ( ite ( x > 1, x - ( x % 2), 0)) 7 while x > 1 { 8 var prob_choice : Bool = flip (0.75) 9 if prob_choice { 10 x = x - 2 11 } else { 12 x = x + 2 13 } 14 reward 1 15 } 16 } Figure 16 : HeyVL code after applying transformation function f(x)=x^{2} to compute the second moment of the time to reach x\leq 1 . ⬇ 1 coproc random_walk ( init_x : UInt ) -> ( x : UInt ) 2 pre init_x * init_x + 3* init_x 3 post 0 4 { 5 x = init_x 6 var tau : UInt = 0 7 @invariant ( x * x + 2* x * tau + 3* x ) 8 while x > 1 { 9 var prob_choice : Bool = flip (0.75) 10 if prob_choice { 11 x = x - 2 12 } else { 13 x = x + 2 14 } 15 reward ( tau +1)*( tau +1) - tau * tau 16 tau = tau + 1 17 } 18 } Figure 17 : HeyVL code for Example 4 , verifying upper bounds on the cumulative distribution function of the web server example from Figure 1(a) . ⬇ 1 domain Exponentials { 2 func pow ( base : UReal , exponent : UInt ): UReal = ite ( exponent == 0, 1, base * pow ( base , exponent - 1)) 3 } 4 5 coproc original_server_cdf ( N : UInt ) -> ( done : Bool ) 6 pre pow (5/10, N - 1) 7 post 0 8 { 9 var tau : UInt = 0 10 reward [0 >= N ] 11 12 done = false 13 @invariant ( 14 ite (! done && tau + 1 <= N , 15 pow (0.5, N - ( tau + 1)), 16 0 17 ) 18 ) 19 while ! done { 20 reward [ tau + 1 == N ] 21 tau = tau + 1 22 done = flip (0.5) 23 } 24 } Figure 18 : HeyVL code representing the original program from Example 5 . ⬇ 1 domain Exponentials { 2 func pow ( base : UReal , exponent : UInt ): UReal = ite ( exponent == 0, 1, base * pow ( base , exponent - 1)) 3 } 4 5 coproc expected_excess ( p : UReal ) -> () 6 pre !?( p > 0 && p < 1) 7 pre 1/ p 8 post 0 9 { 10 var done : Bool = false 11 @invariant ( ite (! done , 1/ p , 0)) 12 while ! done { 13 done = flip ( p ) 14 reward 1 15 } 16 } Figure 19 : HeyVL code after applying transformation function f(x)=x\ominus N . ⬇ 1 domain Exponentials { 2 func pow ( base : UReal , exponent : UInt ): UReal = ite ( exponent == 0, 1, base * pow ( base , exponent - 1)) 3 } 4 5 coproc expected_excess ( N : UInt , p : UReal ) -> () 6 pre !?( p > 0 && p < 1) 7 pre pow (1- p , N )/ p 8 post 0 9 { 10 var tau : UInt = 0 11 var done : Bool = false 12 @invariant ( ite (! done , pow (1- p , N - tau )/ p , 0)) 13 while ! done { 14 reward [ tau >= N ] 15 tau = tau + 1 16 done = flip ( p ) 17 } 18 } Figure 20 : HeyVL code after splitting the loops and applying transformation function f(x)=x\ominus N . ⬇ 1 domain Exponentials { 2 func pow ( base : UReal , exponent : UInt ): UReal = ite ( exponent == 0, 1, base * pow ( base , exponent - 1)) 3 } 4 5 coproc expected_excess ( N : UInt , p : UReal ) -> () 6 pre !?( p > 0 && p < 1) 7 pre pow (1- p , N )/ p 8 post 0 9 { 10 var tau : UInt = 0 11 var done : Bool = false 12 @invariant ( ite (! done && tau < N , pow (1- p , N - tau )/ p , ite (! done , 1/ p , 0))) 13 while ! done && ( tau < N ) { 14 done = flip ( p ) 15 reward 0 16 tau = tau + 1 17 } 18 @invariant ( ite (! done , 1/ p , 0)) 19 while ! done { 20 done = flip ( p ) 21 reward 1 22 tau = tau + 1 23 } 24 } Figure 21 : HeyVL code after applying transformation function f(x)=e^{t\cdot x} to compute the MGF of a coin flip with probability p . ⬇ 1 domain MGFs { 2 // uninterpreted function representing e^{t\cdot x} 3 func mgf ( x : UReal ): UReal 4 axiom mgf_zero mgf (0) == 1 5 axiom mgf_increasing forall x : UReal , y : UReal . ( x < y ) ==> ( mgf ( x ) < mgf ( y )) 6 } 7 8 coproc randomized_assignment_mgf ( p : UReal ) -> ( x : UInt ) 9 pre !?( p <= 1) 10 pre p * mgf (1) + (1- p ) 11 { 12 var tau : UInt = 0 13 reward mgf (0) 14 15 var prob_choice : Bool = flip ( p ) 16 if prob_choice { 17 x = 1 18 } else { 19 x = 0 20 } 21 22 reward mgf ( tau + x ) - mgf ( tau ) 23 tau = tau + x 24 } Figure 22 : HeyVL code for a program that combines two reward structures by multiplication. ⬇ 1 coproc multiple_rewards ( p : UReal , q : UReal ) -> () 2 pre !?( p <= 1 && q <= 1) 3 pre (4 + ( p * (2 + ( q * 3)))) 4 { 5 var tau_memory : UInt = 2 6 var tau_runtime : UInt = 2 7 reward tau_memory * tau_runtime 8 9 var prob_choice : Bool = flip ( p ) 10 if prob_choice { 11 12 // extra computation 13 reward ( tau_memory + 0)*( tau_runtime + 1)-( tau_memory * tau_runtime ) 14 tau_memory = tau_memory 15 tau_runtime = tau_runtime + 1 16 17 prob_choice = flip ( q ) 18 if prob_choice { 19 20 // extra memory 21 reward ( tau_memory + 1)*( tau_runtime + 0)-( tau_memory * tau_runtime ) 22 tau_memory = tau_memory + 1 23 tau_runtime = tau_runtime 24 25 } else {} 26 } else {} 27 } Appendix 0.C Details on Related Work 0.C.1 Relation to the Amortized Expected Runtime Calculus An extension of the ert calculus called the amortized expected runtime calculus was presented in [ 5 ] . Its aert transformer computes the expected change of a potential function \pi\colon\mathsf{States}\to\mathbb{R}_{\geq 0}^{\infty} , i.e. an expectation. By [ 5 , Theorem 5.4] : \textsf{{aert}}_{\tau}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket({\color[rgb]{0,0.2695,0.418}X})=\textsf{{wp}}\llbracket{{\color[rgb]{0.5016,0.2203,0}S}}\rrbracket({\color[rgb]{0,0.2695,0.418}X}+\pi)-\pi . Thus, aert operates on the lattice \mathbb{A} of amortized runtimes , which can be negative expectations, bounded below by the negation of the potential function, i.e. \mathbb{A}=\Set{{\color[rgb]{0,0.2695,0.418}X}\colon\mathsf{States}\to(\mathbb{R}\cup\infty)\mid{\color[rgb]{0,0.2695,0.418}X}\geq-\pi} . However, the analysis of the potential function in the aert transformer reasons about the expected value of the potential function on termination only. This is implied by their Theorem 5.4: the potential function \pi is only added to expectation on termination (c.f. Section 3.2 ). For further illustration, consider the infinite loop {\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({\texttt{true}})~\{~{{\tau}\,{\coloneqq}\,{\tau+1}}~\} that uses the assignment {\tau}\,{\coloneqq}\,{\tau+1} to increase the runtime variable \tau by one in each iteration. We attempt to analyze the change in potential of a counter variable \tau , i.e. choose \pi=\tau . We have \textsf{{aert}}_{\tau}\llbracket{{\color[rgb]{0,0.4348,0.3145}{\texttt{while}}}~({\texttt{true}})~\{~{{\tau}\,{\coloneqq}\,{\tau+1}}~\}}\rrbracket(0)=-\tau , meaning that an infinite loop does not result in any change in the expected runtime. To see why the loop’s semantics evaluates to -\pi , one needs only observe that the aert semantics of the while loop is defined as the least fixed point of the function \Phi_{0}(X)=X[{\tau}\mapsto{\tau+1}]+((\tau+1)-\tau)=X[{\tau}\mapsto{\tau+1}]+1 . The least element of the lattice \mathbb{A}_{\pi} is -\tau , but it is already a fixed-point since \Phi_{0}(-\tau)=(-(\tau+1))+1=-\tau . Hence, the potential function \pi of the aert transformer cannot be used to track run-times without reward statements and one could apply our transformation with the trivial potential function \pi=0 instead.