Skip to content

9. Sums by recursion

When missiles detonate, a jet can be caught by several at once. It loses the sum of their damage. A sum is easy to compute with a loop, but awkward to specify: there is no built-in "sum over" in Ada's expressions, and a postcondition cannot contain a loop. This chapter shows the engine's answer, a sum defined by recursion, and how its properties are proved.

When a missile detonates

First, the rules, as expression functions:

engine/src/adawars-simulation.ads
   --  An armed missile detonates near a flying jet, or near a burning
   --  flare (a decoyed missile is spent on the flare); never near its
   --  owner's own jet or flares.
   function Detonates
     (M : Missile; Owner : Player_Id; Jets : Jet_Array;
      Flares : Flare_Table) return Boolean
   is (M.Active
       and then Armed (M)
       and then ((for some Q in Jets'Range =>
                    Q /= Owner and then Near (M, Jets (Q)))
                 or else (for some P in Flares'Range =>
                            P /= Owner
                            and then (for some S in Flare_Slot =>
                                        Near_Flare (M, Flares (P) (S))))));

   --  Whether missile M's detonation catches jet J. The blast catches
   --  every flying jet near it, its owner's included.
   function Catches
     (M : Missile; Owner : Player_Id; Jets : Jet_Array;
      Flares : Flare_Table; J : Jet) return Boolean
   is (Detonates (M, Owner, Jets, Flares) and then Near (M, J));

These encode a design decision worth noticing. A missile never detonates on its owner, so you cannot shoot yourself down. But once it detonates, its blast catches every jet near it, its owner's included, so firing at point-blank range still hurts.

A recursive sum

The damage a jet takes from one row of missiles (one player's) is defined like this:

engine/src/adawars-simulation.ads
   function Row_Blast
     (Row    : Missile_Row; Owner : Player_Id; Jets : Jet_Array;
      Flares : Flare_Table; J : Jet; Upto : Natural) return Natural
   is (if Upto = 0 then 0
       else Row_Blast (Row, Owner, Jets, Flares, J, Upto - 1)
            + Damage_From (Row (Upto), Owner, Jets, Flares, J))

The damage from slots 1 .. Upto is the damage from 1 .. Upto - 1 plus slot Upto's. That is the definition of a sum, and because it is an expression function, the prover sees it as one.

The contract:

engine/src/adawars-simulation.ads
   with
     Pre                => Upto <= Slots_Per_Player,
     Subprogram_Variant => (Decreases => Upto),
     Post               =>
       Row_Blast'Result <= Upto * Max_Hull
       and then (if Row_Blast'Result > 0
                 then (for some S in 1 .. Upto =>
                         Catches (Row (S), Owner, Jets, Flares, J)))
       and then (for all S in 1 .. Upto =>
                   (if Catches (Row (S), Owner, Jets, Flares, J)
                    then Row_Blast'Result >= Weapons (Row (S).Kind).Damage));

Subprogram_Variant is a loop variant for recursion. It names a value that decreases on every recursive call, here Upto. That proves the recursion ends.

The postcondition is proved by induction, without any help. To prove it for Upto, the prover may assume it for the recursive call on Upto - 1: the induction hypothesis. Then each part is one step:

  • the sum is at most Upto * Max_Hull, because the smaller sum is at most (Upto - 1) * Max_Hull and one missile adds at most Max_Hull;
  • if the sum is positive, some missile caught the jet: either one in the smaller sum, or the one in slot Upto;
  • every missile that caught it contributes its full damage.

The first property is what proves the addition cannot overflow. The other two are what the game needs: a jet loses hull only if some missile caught it, and it takes the full damage of each one.

The same pattern sums across players, Table_Blast, using Row_Blast for each row. Then detonation's postcondition uses both:

engine/src/adawars-simulation.ads
       and then (for all Q in 1 .. W.Players =>
                   (if W.Jets (Q).State = Flying
                    then
                      --  A flying jet loses exactly the blast damage, ...
                      Detonation'Result.Jets (Q).Hull
                      = Integer'Max
                          (0, W.Jets (Q).Hull
                              - Blast (W.Missiles, W.Jets, W.Flares, Q))

Why not a loop?

A loop could compute the sum, and with a loop invariant it could be proved correct. But a postcondition is an expression, and an expression cannot run a loop. To state "the jet loses exactly the sum of the damage", the sum must be a function that can appear in a contract. A recursive expression function can, and it is both the computation and the specification.

Try it

Lose the variant.

Try: engine/src/adawars-simulation.ads
      Pre                => Upto <= Slots_Per_Player,
-     Subprogram_Variant => (Decreases => Upto),
      Post               =>
        Row_Blast'Result <= Upto * Max_Hull

Without it, GNATprove cannot show that the recursion ends:

Expect: prove adawars-simulation.ads fails
implicit aspect Always_Terminates on "Row_Blast" could be incorrect, subprogram is recursive
possible fix: annotate "Row_Blast" with a Subprogram_Variant aspect

Recap

  • A sum is specified by a recursive expression function, which is both computation and specification.
  • Subprogram_Variant proves that recursion ends.
  • Postconditions of recursive functions are proved by induction: the recursive call's postcondition is the induction hypothesis.
  • A bound in the postcondition is what proves the arithmetic cannot overflow.