Skip to content

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:

engine/src/adawars-geometry.ads
   --  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:

engine/src/adawars-geometry.ads
   --  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:

engine/src/adawars-geometry.ads
   --  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.

engine/src/adawars-trig.ads
   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:

engine/src/adawars-trig.ads
   --  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:

engine/src/adawars-rules.ads
   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.

engine/src/adawars-rules.ads
   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.

engine/src/adawars-rules.ads
   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

engine/src/adawars-rules.ads
   type Weapon is (Dumbfire, Heat_Seeker);

An enumeration type lists its values by name. Here is the weapons table, an array indexed by the enumeration:

engine/src/adawars-rules.ads
   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:

engine/src/adawars-rules.ads
   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:

engine/src/adawars-rules.ads
   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:

Try: engine/src/adawars-rules.ads
-   Boost_Speed : constant := 360;
+   Boost_Speed : constant := 250;

The lemma's postcondition now fails, and GNATprove names the weapon that breaks it:

Expect: prove adawars-rules.adb fails
postcondition might fail, cannot prove Boost_Speed > Weapons (K).Speed
e.g. when K = Dumbfire

Make an impossible weapon. Give the dumbfire no fuel:

Try: engine/src/adawars-rules.ads
-        (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.

Expect: prove adawars-rules.adb fails
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 .. B makes 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.
  • case must cover every value; and then short-circuits.
  • Quantified expressions (for all, for some) state facts about every element.