Skip to content

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:

engine/src/adawars-worlds.adb
   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:

engine/src/adawars-worlds.ads
   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:

  1. P := P + 1 never takes P past the end of the array, or out of Player_Id.
  2. The loop ends.
  3. When it ends, P is the sole survivor.

The invariant

engine/src/adawars-worlds.adb
         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

engine/src/adawars-worlds.adb
         pragma Loop_Variant (Increases => P);

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

Try: engine/src/adawars-worlds.adb
            and then (for all Q in Jets'First .. P => not Flying (Jets, Q)));
-         pragma Loop_Variant (Increases => P);
          P := P + 1;
Expect: prove adawars-worlds.adb fails
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:

engine/src/adawars-guidance.adb
   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:

Try: engine/src/adawars-guidance.adb
-         pragma Loop_Invariant
+         pragma Assert
            (if Best = No_Target
Expect: prove adawars-guidance.adb fails
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:

engine/src/adawars-views.adb
   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 while loop ends; for loops end by construction.
  • pragma Assert proves a fact at one point and makes it available after.