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:
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:
-- 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:
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:
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:
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:
-- 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:
-- 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:
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:
-- 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:
-- 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:
- else Integer'Max (Zone_End, Zone - Zone_Shrink))
+ else Integer'Min (Zone_Start, Zone + Zone_Shrink))
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¶
Stepis 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.