Tactic: while
The while tactic applies to program-logic goals where the next
statement to reason about is a while loop.
Applying while replaces the original goal with proof obligations that let
you reason about the loop via an invariant (and, in some variants, a
termination variant). Intuitively, you prove that the invariant is initially
true, is preserved by one iteration of the loop, and you then use the invariant
to justify what follows once the loop condition becomes false.
Variant: Hoare logic
Syntax
while ({formula})
The formula is a loop invariant that must hold whenever the loop condition is evaluated (at the start of each iteration). It may reference variables of the program.
Applying this form of while generates (at least) the following goals:
Preservation goal (one iteration): assuming the invariant holds and the loop condition is true, executing the loop body re-establishes the invariant.
Exit/continuation goal: you must show that the invariant holds when the loop is entered, and that when the loop condition becomes false, the invariant is strong enough to derive the desired postcondition.
Variant: Probabilistic relational Hoare logic (one-sided)
Syntax
while {side} {formula} {expr}
Here {formula} is a relational invariant, and {expr} is an integer-valued
termination variant. This variant applies when the program designated by
{side} ends with a while loop.
Applying this form of while generates two main goals:
Loop-body goal (designated side): assuming the invariant holds and the loop condition is true, executing the loop body re-establishes the invariant and decreases the variant with probability 1.
Remaining relational goal: the loop is removed from the designated program, and the postcondition is strengthened with the invariant together with pure logical conditions connecting loop exit to the desired postcondition.
Variant: Probabilistic Hoare logic with (<=) bound
Syntax
while {formula}
[easycrypt failed]
Variant: Probabilistic Hoare logic with strict variant
Syntax
while {formula} {expr}
Variant: Probabilistic Hoare logic with non-strict variant and >= or = bound
This variant only works on pHL goals whose body only contains a while loop.
It can be seen as a variation of the variant pHL with >= bounds
with some additional requirements to handle issues with termination.
Syntax
while {formula} {var} {varbd} {prob}
Here {formula} is an invariant, {var} is an integer
termination variant, {varbd} is an upper bound on the variant,
and {prob} is a lower bound on the probability that the variant decreases.
Program variables used in {varbd} and {prob} need to be unmodified by the loop body.
Though this tactic can be used to prove non-1%r bounds, it only works with
almost certain termination. The bounds are proven using co-induction,
similarly to the variant of while for pHL with >= bounds. Using this
requires carefully setting up the precondition and bounds to facilitate this.
The tactic generates 6 goals
A goal that connects the precondition to the invariant
A goal that handles the case where the loop is never entered, connecting the bound of the pHL statement to both the precondition and postcondition.
A goal requiring that
{varbd}bounds the variant from above, and that the loop condition fails when the variant reaches 0.A goal requiring that the pHL holds from coinduction.
A goal requiring that the invariant is always preserved
A goal requiring that
{prob}is positive and lower bounds the probability of the variant decreasing.
The previous example is simpler and more well motivated, but does not fully demonstrate the power of the tactic, which we demonstrate with the following example.