Skip to content

7. A tick as a function

The game runs at 30 ticks a second. Each tick, the whole world moves on one step, and the rule for that step is a single function:

engine/src/adawars-simulation.ads
   function Step (W : World; C : Control_Array) return World is
     (if W.Result.Kind /= Running then W else Advance (W, Masked (W, C)))

It takes the world and every player's controls, and returns the next world. It changes nothing: the old world is still there afterwards. That is what makes it provable, and also what makes replays exact. Feed the same controls into the same world and you get the same match, every time.

This chapter reads how Step is built, and what is proved about it.

Phases

A tick goes through phases in a fixed order. The header of Adawars.Simulation lists them:

engine/src/adawars-simulation.ads
--    Flight      jets turn, change speed and move, as their controls say
--    Guided      missiles lock on, steer, move and burn fuel
--    Detonation  armed missiles near a jet explode, damaging jets nearby
--    Launch      jets fire, where the firing rule allows
--    Drop        flares burn down, and jets drop new ones where allowed
--    Rearm       jets regain rounds and flares over time
--    Self_Destruct  armed fuses burn; a spent one destroys every jet near
--    Zone_Burn   jets outside the zone lose hull
--    Finish      the clock ticks, the zone shrinks, the outcome is decided
flowchart LR
  W[World] --> Flight --> Guided --> Detonation --> Launch --> Drop
  Drop --> Rearm --> Self_Destruct --> Zone_Burn --> Finish --> W2[Next world]

Each phase is a function from world to world, and Advance composes them:

engine/src/adawars-simulation.adb
   function Advance (W : World; C : Control_Array) return World is
     (Finish
        (Zone_Burn
           (Self_Destruct
              (Rearm (Drop (Launch (Detonation (Guided (Flight (W, C))), C),
                            C)),
               C))));

Changing one part of a record

A phase changes some of the world and leaves the rest alone. Ada 2022 has a notation for exactly that, the delta aggregate:

engine/src/adawars-simulation.ads
   function Flight (W : World; C : Control_Array) return World is
     ((W with delta
         Jets =>
           [for P in W.Jets'Range =>
              (if W.Jets (P).State = Flying then Flown_Jet (W.Jets (P), C (P))
               else W.Jets (P))]))

(W with delta Jets => ...) is a copy of W with Jets replaced. Here the new jets are built by an iterated aggregate: each flying jet is flown, and each destroyed one is left as it was.

Frame conditions

Here is Flight's contract:

engine/src/adawars-simulation.ads
   with
     Pre  => Fits (W, C),
     Post =>
       Flight'Result.Now = W.Now
       and then Flight'Result.Zone = W.Zone
       and then Flight'Result.Missiles = W.Missiles
       and then Flight'Result.Flares = W.Flares
       and then (for all P in 1 .. W.Players =>
                   Flight'Result.Jets (P).Rearmed = W.Jets (P).Rearmed)
       and then (for all P in 1 .. W.Players =>
                   (if W.Jets (P).State = Destroyed
                    then Flight'Result.Jets (P) = W.Jets (P)));

Most of it says what does not change: the clock, the zone, the missiles, the flares, and destroyed jets. These are frame conditions. They look too obvious to write, but the prover needs them. When it reasons about Guided (Flight (W, C)), all it knows about Flight's result is this postcondition. If the postcondition did not say the clock is unchanged, then as far as the prover was concerned, Flight might have changed it.

Every phase has frame conditions like these, and they chain: since no phase changes a destroyed jet, the whole tick does not.

Defining a rule exactly

Some postconditions go further, and pin down a rule completely. Firing is one. First, the rule itself:

engine/src/adawars-simulation.ads
   --  The firing rule: a flying jet asking to fire, with that weapon's
   --  ammunition left, its cooldown over and a free missile slot.
   function Can_Fire (J : Jet; Row : Missile_Row; C : Control) return Boolean
   is (J.State = Flying
       and then C.Fire
       and then J.Remaining (C.Kind) > 0
       and then J.Cooldown = 0
       and then Has_Free_Slot (Row));

Then part of Launch's postcondition:

engine/src/adawars-simulation.ads
       --  A missile appears exactly when the firing rule allows, in a slot
       --  that was free, and nothing else in the row changes.
       and then (for all P in 1 .. W.Players =>
                   (if Can_Fire (W.Jets (P), W.Missiles (P), C (P))
                    then
                      Launch'Result.Jets (P).Fired (C (P).Kind)
                      = W.Jets (P).Fired (C (P).Kind) + 1
                      and then (for some S in Slot =>
                                  not W.Missiles (P) (S).Active
                                  and then Launch'Result.Missiles (P) (S)
                                           = Launched (W.Jets (P), C (P).Kind)
                                  and then
                                    (for all T in Slot =>
                                       (if T /= S
                                        then Launch'Result.Missiles (P) (T)
                                             = W.Missiles (P) (T))))
                    else
                      Launch'Result.Jets (P) = W.Jets (P)
                      and then Launch'Result.Missiles (P) = W.Missiles (P)))

If the rule allows it, a missile appears in a slot that was free, the jet's fired count goes up by one, and nothing else in the row changes. If not, neither the jet nor its missiles change at all. There is no other way for a missile to appear.

The whole tick

Step's contract is the summary of all of this:

engine/src/adawars-simulation.ads
     Pre  => Valid (W) and then Fits (W, C),
     Post =>
       Valid (Step'Result)
       --  A finished match never changes; a running one ticks.
       and then (if W.Result.Kind /= Running then Step'Result = W
                 else Step'Result.Now = W.Now + 1)
       and then Step'Result.Zone <= W.Zone
       --  The destroyed stay destroyed, and nothing about them changes.
       and then (for all P in 1 .. W.Players =>
                   (if W.Jets (P).State = Destroyed
                    then Step'Result.Jets (P) = W.Jets (P)))

Read it as the game's guarantees: every world is valid (so the outcome is always the rule's), a finished match is frozen, the zone never grows, and the dead stay dead. Since New_World makes a valid world and Step keeps it valid, every world in every match is valid. That is an invariant of the whole game, proved by induction over ticks.

Hiding a body on purpose

Advance is written in the body (.adb), not the spec. That is deliberate:

engine/src/adawars-simulation.ads
   --  Finish (Zone_Burn (Self_Destruct (Rearm (Drop (Launch (Detonation
   --    (Guided (Flight (W, C))), C), C)), C)))
   function Advance (W : World; C : Control_Array) return World
   with
     Pre  => Fits (W, C)
             and then W.Now < Max_Ticks
             and then Rearm_Bounded (W.Jets, Natural (W.Now)),

When proving Step, the prover sees only Advance's contract, not the nine phases unfolded into one enormous formula. Proving Advance itself is a separate job, which sees the phases, but only through their contracts. Splitting a proof into pieces with contracts between them is what keeps a large proof manageable. Each piece is small enough for the provers.

Try it

Let the zone grow. The zone is meant only ever to shrink:

engine/src/adawars-simulation.ads
   --  The zone never grows.
   function Shrunk (Zone : Zone_Radius; Now : Tick) return Zone_Radius is
     (if Now < Zone_Hold then Zone
      else Integer'Max (Zone_End, Zone - Zone_Shrink))
   with Post => Shrunk'Result <= Zone;

Get the sign wrong:

Try: engine/src/adawars-simulation.ads
-      else Integer'Max (Zone_End, Zone - Zone_Shrink))
+      else Integer'Min (Zone_Start, Zone + Zone_Shrink))
Expect: prove adawars-simulation.ads fails
high: postcondition might fail --> adawars-simulation.ads:732
e.g. when Shrunk'Result = Zone_Radius'Last

GNATprove is sure of this one (high), and its counterexample is a zone that has grown to the largest radius there is.

The type still holds: the new code keeps the zone within its range. It is the postcondition, the rule, that catches the mistake.

Recap

  • Step is a pure function from world and controls to world: the whole rule of the game, and the reason replays are exact.
  • (R with delta F => V) copies a record with some fields changed.
  • Frame conditions say what does not change. The prover needs them, because it knows only what postconditions say.
  • A postcondition can define a rule exactly: this happens if and only if that holds.
  • An invariant kept by every step holds for the whole game.
  • Bodies hidden behind contracts split a big proof into small ones.