Positive Almost-Sure Termination
Positive almost-sure termination (PAST for short) means that a program terminates almost surely and the expected runtime to termination is finite.
In HeyVL, reward statements model the cost measured by the expected runtime calculus.
tick is an alias for reward.
Upper Bounds on ert
Park induction suffices to prove PAST when every nonterminating execution accumulates infinite total reward.
A finite upper bound then establishes both almost-sure termination and finite expected reward.
If each execution of the loop body terminates, adding reward 1 per iteration makes the iteration count at most the total reward.
PAST from Ranking Superinvariants
In an @ert coproc, @past(I, epsilon, K) proves that a loop terminates almost surely using a ranking superinvariant .
From an initial state , it bounds the expected number of iterations by and the expected sum of the loop's rewards by .
The soundness proof derives these guarantees by Park induction.
If the coproc omits its calculus annotation, @past selects least-fixed-point semantics.
The rule follows the ranking-superinvariant argument [Kaminski 2019, Theorem 6.3]. Related results use the term ranking supermartingale [Chakarov and Sankaranarayanan 2013, Theorem 4], [Fioriti and Hermanns 2015, Theorem 5.6].
Verification Conditions
Let be a loop while G { Body } with a loop-free probabilistic body and valid sampling parameters.
The body may use local declarations, assignments, conditionals, built-in sampling, and rewards.
The constants and are UReal literals with .
- Exit. when is false.
- Ranking. in every state and when is true.
- Decrease. when is true.
In the decrease check, adds the body's expected reward to the expected value of after the iteration. The sum must be at least below the entry value of .
Generated HeyVL checks
Here vars denotes the variables used by the loop or annotation, excluding loop-local variables.
proc I_bounded_on_exit(vars: ...) -> ()
{
assert ?(([!G(vars)] * I(vars)) <= K)
}
proc K_bounded_by_I(vars: ...) -> ()
{
assert ?(I(vars) < ∞ && ([G(vars)] * K <= [G(vars)] * I(vars) + [!G(vars)]))
}
coproc I_decreases(init_vars: ...) -> (vars: ...)
pre [G(init_vars)] * (I(init_vars) - epsilon)
post 0
{
vars = init_vars
if G {
Body
assert I(vars)
assume 0
} else {}
}
Usage
To bound the procedure's expected reward, set post 0 and give a finite upper bound in pre.
The countdown charges one reward per coin flip and decrements x on heads.
Caesar verifies almost-sure termination and an upper bound of on the expected number of flips.
@ert
coproc main(init_x: UInt) -> (x: UInt)
pre 3 * init_x + 1
post 0
{
var prob_choice: Bool
x = init_x
@past(
/* invariant: */ 3 * x + 1,
/* epsilon: */ 0.5,
/* K: */ 1)
while 0 < x {
reward 1
prob_choice = flip(0.5)
if prob_choice {
x = x - 1
} else {}
}
}
On heads, drops by , so the expected drop after charging the reward is .
Loop Summary
The summary adds the reward bound , evaluated at entry, to the supremum of the postexpectation over states that satisfy and agree with the entry state outside modified.
Here modified lists the variables assigned by the body that remain in scope after the loop.
When is false on entry, the summary acts as skip.
if G {
tick I
cohavoc modified
coassume ?(G)
} else {}
This over-approximation can yield spurious counterexamples.
Soundness
We prove that the verification conditions imply almost-sure termination and bound the expected number of iterations and the expected reward.
Under , the parameter and ranking checks give .
Starting from the decrease check, we derive a bound for Body; reward epsilon, which charges an extra per completed iteration.
The last inequality and when is false give the Park induction premises for while G { Body; reward epsilon } with postexpectation .
For a run with iterations the extra reward contributes , so from an initial state we have
Every nonterminating execution has because each execution of the body terminates. Since , the loop terminates almost surely.