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:
-- 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:
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:
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_Hulland one missile adds at mostMax_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:
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.
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:
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_Variantproves 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.