2. Types that mean something¶
The first line of verification in Ada is not a proof tool. It is the type system. This chapter reads the arena's geometry and the game's constants, and shows how much of the game's rulebook is just types.
Numbers with units¶
The arena is a square, 6 km on a side. Positions are measured in sixteenths of a metre, so that slow movements are not lost to rounding:
-- Position units per metre.
Sub : constant := 16;
Arena_Metres : constant := 6_000;
Arena_Size : constant := Arena_Metres * Sub;
type Coord is range 0 .. Arena_Size;
type Point is record
X, Y : Coord;
end record;
Centre : constant Point := (Arena_Size / 2, Arena_Size / 2);
Sub : constant := 16 has no type. It is a named number: a value known
at compile time, usable with any integer type. Underscores in numeric
literals, as in 6_000, are just for reading.
type Coord is range 0 .. Arena_Size declares a new integer type whose
values are 0 to 96000. Like Angle, it is distinct from Integer. Unlike
Angle, it does not wrap: a Coord outside its range is an error.
So a position cannot leave the arena. Nothing has to check for it, because
no Coord outside the arena exists.
Point is a record, a structure with named fields. Centre is built
with an aggregate, (Arena_Size / 2, Arena_Size / 2), which lists the
fields' values in order. You can name them too: (X => 0, Y => 0).
Keeping values in range¶
If a value cannot go out of range, what happens when a jet flies into the
wall? The code has to bring it back in range before it becomes a Coord:
-- A coordinate pulled back inside the arena.
function Clamp (V : Integer) return Coord is
(Coord (Integer'Max (0, Integer'Min (Arena_Size, V))));
The calculation is done in Integer, which has room for values beyond the
arena. Integer'Max and Integer'Min are attributes of the type that pick
the larger and smaller of two values. Only then is the result converted to
Coord. The conversion Coord (...) is checked: if the value were out of
range it would fail. GNATprove proves that it never does, because the
clamped value is always between 0 and Arena_Size.
Here is where it is used, to move a point:
-- The furthest anything moves in one tick, in position units.
Max_Step : constant := 400;
subtype Step_Length is Natural range 0 .. Max_Step;
...
-- Where P ends up after travelling Distance along Heading. Movement
-- stops at the arena's walls.
function Move (P : Point; Heading : Angle; Distance : Step_Length)
return Point
is ((X => Clamp (Integer (P.X) + Along (Distance, Cos (Heading))),
Y => Clamp (Integer (P.Y) + Along (Distance, Sin (Heading)))))
with
Post =>
abs (Integer (Move'Result.X) - Integer (P.X)) <= Distance
and then abs (Integer (Move'Result.Y) - Integer (P.Y)) <= Distance;
Notice Step_Length: anything that moves is limited to 400 units a tick, and
that limit is part of Move's parameter type. A caller cannot pass a longer
step.
The postcondition says that a move never goes further than its distance
along either axis. and then is Ada's short-circuit "and": the right side is
only evaluated if the left side is true. (Plain and evaluates both.) The
engine uses and then throughout, because the right side is often only
meaningful when the left side holds.
No floating point¶
Cos (Heading) above is not the floating-point cosine. The engine uses no
floating point at all. Floating-point results can differ between machines,
and the engine must give identical results everywhere, so that a match can be
replayed exactly from its inputs.
Instead, trigonometry is done in fixed point: a fraction is stored as a whole number of 1/16384ths.
One : constant := 2**14;
-- A value in [-1, 1], scaled by One.
type Ratio is range -One .. One;
function Sin (A : Angle) return Ratio;
function Cos (A : Angle) return Ratio is (Sin (A + Quarter_Turn));
A Ratio is between −1 and 1, scaled by 16384. Its type says so: no sine can
come out larger than one. Cos is defined from Sin by turning a quarter
turn, and because Angle wraps, there are no special cases.
Sine itself reads a table of 257 values covering a quarter turn:
-- The table entry at or below A's position within its quadrant.
function Within (A : Angle) return Index is
(Natural (A mod Quarter_Turn) / Step);
function Sin (A : Angle) return Ratio is
(case A / Quarter_Turn is
when 0 => Quarter_Sine (Within (A)),
when 1 => Quarter_Sine (Steps - Within (A)),
when 2 => -Quarter_Sine (Within (A)),
when others => -Quarter_Sine (Steps - Within (A)));
This is a case expression. A / Quarter_Turn is the quadrant, 0 to 3,
and each branch reflects the table into its quadrant. The compiler insists
that a case covers every possible value. when others covers the rest.
These declarations are in the private part of the spec, after the word
private. Code outside the package cannot see them, but the prover can.
The rulebook as types¶
Adawars.Rules holds every constant in the game. Read it as a rulebook:
Tick_Rate : constant := 30;
-- A match is drawn if it lasts this long.
Max_Ticks : constant := Tick_Rate * 60 * 8;
type Tick is range 0 .. Max_Ticks;
Max_Players : constant := 8;
subtype Player_Count is Positive range 2 .. Max_Players;
subtype Player_Id is Positive range 1 .. Max_Players;
A match has two to eight players, and a player is numbered 1 to 8. A
Player_Id of 9 cannot exist, so there is no "invalid player" case anywhere
in the engine.
Min_Speed : constant := 64;
Max_Speed : constant := 160;
Acceleration : constant := 2;
-- Throttle reaches Max_Speed; only a boost goes faster.
Boost_Speed : constant := 360;
subtype Airspeed is Step_Length range Min_Speed .. Boost_Speed;
subtype Cruise_Speed is Airspeed range Min_Speed .. Max_Speed;
Subtypes can be built from subtypes. Airspeed is a Step_Length, so an
airspeed is a valid distance for Move without any check. A jet that is
not boosting flies at a Cruise_Speed, which is a narrower range again.
type Throttle_Level is range 0 .. 100;
type Turn_Command is range -100 .. 100;
These two are what a player sends each tick: how much throttle, and how hard to turn. They are separate types, so a turn cannot be passed where a throttle is expected, even though both are small integers.
Enumerations and tables¶
An enumeration type lists its values by name. Here is the weapons table, an array indexed by the enumeration:
Weapons : constant array (Weapon) of Weapon_Spec :=
[Dumbfire =>
(Speed => 267, Turn => 0, Fuel => 120, Arming => 10,
Damage => 20, Seeker => Blind, Loadout => 12, Rearm => 45),
-- 30 degrees either side, out to 2 km.
Heat_Seeker =>
(Speed => 224, Turn => 728, Fuel => 180, Arming => 15,
Damage => 35, Seeker => (Reach => 2_000, Half_Cone => 5_461),
Loadout => 4, Rearm => 300)];
array (Weapon) of Weapon_Spec has exactly one element per weapon, so
Weapons (Heat_Seeker).Speed is always valid. If someone adds a third
weapon, every aggregate like this one stops compiling until it says what the
new weapon does. Square brackets are the Ada 2022 notation for array
aggregates.
Each field of Weapon_Spec has its own range:
type Weapon_Spec is record
Speed : Step_Length;
Turn : Turn_Rate;
-- Ticks of flight.
Fuel : Positive range 1 .. Max_Fuel;
...
Damage : Hull_Points;
Seeker : Sensor;
Loadout : Natural range 0 .. Max_Loadout;
...
end record;
A missile with zero fuel, or one faster than anything can move in a tick, cannot even be described.
A rule as a proof¶
One rule in this file is not a type. A boost has to outrun every missile, for the whole boost. That is a relationship between constants, stated as a lemma:
procedure Lemma_Boost_Outruns_Missiles
with
Ghost,
Global => null,
Post => (for all K in Weapon => Boost_Speed > Weapons (K).Speed);
for all K in Weapon => ... is a quantified expression: true if the
condition holds for every weapon. (for some is true if it holds for at
least one.) If anyone retunes a missile to be faster than a boost, this proof
fails, and the build with it.
Try it¶
Retune the boost. Slow the boost below the dumbfire's 267:
The lemma's postcondition now fails, and GNATprove names the weapon that breaks it:
postcondition might fail, cannot prove Boost_Speed > Weapons (K).Speed
e.g. when K = Dumbfire
Make an impossible weapon. Give the dumbfire no fuel:
- (Speed => 267, Turn => 0, Fuel => 120, Arming => 10,
+ (Speed => 267, Turn => 0, Fuel => 0, Arming => 10,
Fuel is Positive range 1 .. Max_Fuel, so this value cannot exist. Since
the value is known at compile time, this is not even left to the provers:
GNATprove's front end, which is the compiler's, rejects the program outright.
error: value not in range of subtype of "Standard.Integer"
Constraint_Error would have been raised at run time
Look for the missing check. Search the engine for a test of whether a player number is between 1 and 8. There isn't one. Why not?
Recap¶
type T is range A .. Bmakes a new integer type; values outside it cannot exist.- Subtypes narrow a type and mix freely with it.
- Named numbers are typeless compile-time constants.
- Records group fields; aggregates build values, by position or by name.
- An array indexed by an enumeration has exactly one element per value.
casemust cover every value;and thenshort-circuits.- Quantified expressions (
for all,for some) state facts about every element.