6. Loops the prover can follow¶
Expression functions are easy for a prover: the body is a formula. Loops are harder. A loop might run any number of times, and the prover cannot simulate it. You have to tell it what stays true as the loop runs. That is a loop invariant, and learning to write them is most of learning to prove loops.
Finding the survivor¶
When one jet is left flying, Survivor finds it:
function Survivor (Jets : Jet_Array) return Player_Id is
P : Player_Id := Jets'First;
begin
-- Some jet is flying, so the search stops before running out.
while not Flying (Jets, P) loop
pragma Loop_Invariant
(P in Jets'Range
and then (for all Q in Jets'First .. P => not Flying (Jets, Q)));
pragma Loop_Variant (Increases => P);
P := P + 1;
end loop;
return P;
end Survivor;
Its contract, from chapter 4:
function Survivor (Jets : Jet_Array) return Player_Id
with
Pre => Has_Survivor (Jets),
Post => Sole_Survivor (Jets, Survivor'Result);
P is a variable: unlike a constant, it can be assigned again. The
while loop runs as long as jet P is not flying.
Three things need proving:
P := P + 1never takesPpast the end of the array, or out ofPlayer_Id.- The loop ends.
- When it ends,
Pis the sole survivor.
The invariant¶
pragma Loop_Invariant
(P in Jets'Range
and then (for all Q in Jets'First .. P => not Flying (Jets, Q)));
A loop invariant is a condition that is true every time execution reaches it. GNATprove proves it by induction, in two steps:
- it holds the first time round;
- if it holds on one iteration, it holds on the next.
Then, at that point in any iteration, the prover forgets everything about earlier iterations except the invariant. That is what makes loops provable: the invariant summarises all of history in one formula.
This one says: P is a valid index, and no jet up to and including P is
flying. With the precondition, that there is a flying jet somewhere, it
follows that the flying jet is after P, so P + 1 is still in range. That
is the first thing to prove.
The variant¶
A loop variant proves that the loop ends. It names a value that strictly
increases (or decreases) each time round. Since P is bounded and goes up
every iteration, the loop cannot run forever. That is the second thing.
The third follows from the precondition: the survivor is the only jet flying, and the loop stops at the first jet that is.
Try it: lose the variant¶
and then (for all Q in Jets'First .. P => not Flying (Jets, Q)));
- pragma Loop_Variant (Increases => P);
P := P + 1;
implicit aspect Always_Terminates on "Survivor" could be incorrect, loop might be nonterminating
possible fix: add loop variant in the loop body
Every SPARK function is implicitly required to terminate (Always_Terminates).
Without a variant, GNATprove cannot show that this one does.
The hottest target¶
Lock_On, whose contract you read in chapter 4, is a loop over every
target, keeping the best seen so far:
function Lock_On
(M : Missile; Owner : Player_Id; Jets : Jet_Array; Flares : Flare_Table)
return Target
is
Best : Target := No_Target;
begin
for T in 1 .. Max_Target loop
if Is_Candidate (M, Owner, Jets, Flares, T)
and then (Best = No_Target
or else Heat_Of (Jets, Flares, T)
> Heat_Of (Jets, Flares, Best))
then
Best := T;
end if;
pragma Loop_Invariant
(Best = No_Target
or else (Best in 1 .. T
and then Is_Candidate (M, Owner, Jets, Flares, Best)));
pragma Loop_Invariant
(if Best = No_Target
then (for all U in 1 .. T =>
not Is_Candidate (M, Owner, Jets, Flares, U))
else (for all U in 1 .. T =>
(if Is_Candidate (M, Owner, Jets, Flares, U)
then Heat_Of (Jets, Flares, U)
<= Heat_Of (Jets, Flares, Best))));
end loop;
-- No_Target is never a candidate.
pragma Assert (not Is_Candidate (M, Owner, Jets, Flares, No_Target));
return Best;
end Lock_On;
A for loop runs over a range, so it always ends: no variant is needed.
The invariants are the postcondition, restricted to the targets seen so
far: 1 .. T instead of every target. This is the standard way to write
an invariant for a search. Ask what the postcondition says about the whole
range, and say it about the part the loop has covered. When the loop ends,
T has reached Max_Target, so the invariant covers every target, and it
is the postcondition (apart from target 0, which the pragma Assert deals
with).
pragma Assert states a fact the prover must prove at that point, and can
use afterwards. Here it bridges the gap between "every target from 1" and
"every target".
Try it: lose an invariant¶
Turn the second invariant into a plain assertion, so it is checked but no longer carried from one iteration to the next:
assertion might fail, cannot prove not Is_Candidate (M, Owner, Jets, Flares, U)
The assertion fails because, without the invariant, the prover knows nothing about the targets checked on earlier iterations. Each iteration on its own cannot show a fact about all of them.
Counting¶
Some loops need only a bound. Flying_Count counts the jets still flying:
function Flying_Count (W : World) return Natural is
N : Natural := 0;
begin
for P in 1 .. W.Players loop
if W.Jets (P).State = Flying then
N := N + 1;
end if;
pragma Loop_Invariant (N <= P);
end loop;
return N;
end Flying_Count;
The invariant N <= P is all it takes to prove that N + 1 cannot
overflow, and with it the postcondition Flying_Count'Result <= W.Players.
Recap¶
- A loop invariant must hold every time round. The prover proves it by induction, then forgets everything else about earlier iterations.
- For a search, the invariant is usually the postcondition, restricted to the part of the range covered so far.
- A loop variant proves that a
whileloop ends;forloops end by construction. pragma Assertproves a fact at one point and makes it available after.