Skip to main content

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 ert⟦C⟧(0)≤g<∞\mathrm{ert}\llbracket C \rrbracket(0) \leq g < \infty 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 II. From an initial state ss, it bounds the expected number of iterations by I(s)/ϵI(s) / \epsilon and the expected sum of the loop's rewards by I(s)I(s). 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 LL 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 ϵ\epsilon and KK are UReal literals with 0<ϵ<K0 < \epsilon < K.

  1. Exit. I≤KI \leq K when GG is false.
  2. Ranking. I<∞I < \infty in every state and K≤IK \leq I when GG is true.
  3. Decrease. ert⟦Body⟧(I)≤I−ϵ\mathrm{ert}\llbracket \mathtt{Body} \rrbracket(I) \leq I - \epsilon when GG is true.

In the decrease check, ert\mathrm{ert} adds the body's expected reward to the expected value of II after the iteration. The sum must be at least ϵ\epsilon below the entry value of II.

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 3⋅init_x+13 \cdot \mathtt{init\_x} + 1 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, 3⋅x+13 \cdot x + 1 drops by 33, so the expected drop after charging the reward is 12⋅3−1=12\tfrac12 \cdot 3 - 1 = \tfrac12.

Loop Summary​

The summary adds the reward bound II, evaluated at entry, to the supremum of the postexpectation over states that satisfy ¬G\neg G 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 GG 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 GG, the parameter and ranking checks give ϵ<K≤I<∞\epsilon < K \leq I < \infty. Starting from the decrease check, we derive a bound for Body; reward epsilon, which charges an extra ϵ\epsilon per completed iteration.

ert⟦Body⟧(I)≤I−ϵ(decrease check)  ⟺  ert⟦Body⟧(I)+ϵ≤I(add ϵ)  ⟺  ert⟦Body⟧(I+ϵ)≤I(the body terminates)  ⟺  ert⟦Body; reward ϵ⟧(I)≤I(composition).\begin{aligned} &\mathrm{ert}\llbracket \mathtt{Body} \rrbracket(I) \leq I - \epsilon && \text{(decrease check)} \\ \iff{} &\mathrm{ert}\llbracket \mathtt{Body} \rrbracket(I) + \epsilon \leq I && \text{(add }\epsilon\text{)} \\ \iff{} &\mathrm{ert}\llbracket \mathtt{Body} \rrbracket(I + \epsilon) \leq I && \text{(the body terminates)} \\ \iff{} &\mathrm{ert}\llbracket \mathtt{Body};\,\mathtt{reward}\,\epsilon \rrbracket(I) \leq I && \text{(composition).} \end{aligned}

The last inequality and 0≤I0 \leq I when GG is false give the Park induction premises for while G { Body; reward epsilon } with postexpectation 00. For a run with TT iterations the extra reward contributes ϵ⋅T\epsilon \cdot T, so from an initial state ss we have

I(s)≥ert⟦while G {Body; reward ϵ}⟧(0)(s)=ert⟦L⟧(0)(s)+ϵ⋅Es[T].\begin{aligned} I(s) &\geq \mathrm{ert}\llbracket \mathtt{while}\ G\ \{\mathtt{Body};\,\mathtt{reward}\,\epsilon\} \rrbracket(0)(s) \\ &= \mathrm{ert}\llbracket L \rrbracket(0)(s) + \epsilon \cdot \mathbb{E}_s[T]. \end{aligned}

Every nonterminating execution has T=∞T = \infty because each execution of the body terminates. Since Es[T]≤I(s)/ϵ<∞\mathbb{E}_s[T] \leq I(s) / \epsilon < \infty, the loop terminates almost surely.