Skip to content

1. A first package

Every jet and missile in AdaWars has a heading: the direction it points. This chapter reads the package that defines headings, Adawars.Angles. It is short, but it shows most of what an Ada unit looks like.

Specs and bodies

Ada splits a package in two:

  • the specification (.ads), which says what the package offers;
  • the body (.adb), which says how.

Code that uses a package can only see its spec. Here is the whole spec of Angles:

engine/src/adawars-angles.ads
--  Binary angles: a full turn is 2**16, so wraparound is what the type means
--  rather than a case to guard against.
--
--  Proof level: Gold. Every operation's result is fully specified.
package Adawars.Angles with Pure, SPARK_Mode is

   type Angle is mod 2**16;

   Quarter_Turn : constant Angle := 2**14;
   Half_Turn    : constant Angle := 2**15;

   --  A signed turn, at most half a turn either way.
   subtype Offset is Integer range -2**15 .. 2**15 - 1;

   --  The heading reached by turning From by By.
   function Rotate (From : Angle; By : Offset) return Angle is
     (if By >= 0 then From + Angle (By) else From - Angle (-By));

   --  The shortest turn that takes From to To.
   function Diff (To, From : Angle) return Offset
   with Post => Rotate (From, Diff'Result) = To;

   --  Turning by an offset and measuring the turn gives the offset back.
   procedure Lemma_Diff_Rotate (From : Angle; By : Offset)
   with
     Ghost,
     Global => null,
     Post   => Diff (Rotate (From, By), From) = By;

   --  How far apart two headings are, either way round.
   function Separation (A, B : Angle) return Natural is
     (abs Diff (A, B))
   with Post => Separation'Result <= 2**15;

end Adawars.Angles;

Take it a line at a time.

Comments start with -- and run to the end of the line. The style used here puts two spaces after the dashes.

package Adawars.Angles declares a package called Angles inside the package Adawars. That makes it a child package. The file name follows from the package name: adawars-angles.ads.

with Pure, SPARK_Mode attaches aspects to the package. Pure promises that the package has no state: nothing in it can change between calls, so every function's result depends only on its arguments. SPARK_Mode says the package is written in SPARK, the subset of Ada that GNATprove can prove things about. Every unit of the engine has it.

A type that cannot go out of range

engine/src/adawars-angles.ads
type Angle is mod 2**16;

This declares a new type, Angle, whose values are the whole numbers 0 to 65535. It is a modular type: arithmetic on it wraps around, so 65535 + 1 is 0. That is exactly how headings behave. A full turn is 65536 units, and turning past a full turn brings you back to where you started. Angles measured this way are called binary angles.

Most languages give you one integer type and leave you to remember that this particular integer is a heading and must be reduced modulo some number. In Ada the type says it, and there is no such thing as an out-of-range heading. The comment at the top puts it well: wraparound is what the type means, rather than a case to guard against.

A new type is a different type

Angle is not Integer. You cannot add an Angle to an Integer without saying so: Angle (By) converts By to an Angle. Mixing up two kinds of number is a compile-time error, not a bug to find later.

Constants and subtypes

engine/src/adawars-angles.ads
Quarter_Turn : constant Angle := 2**14;
Half_Turn    : constant Angle := 2**15;

These are constants of type Angle. Note := for giving a value; = is the equality test. ** is exponentiation.

engine/src/adawars-angles.ads
subtype Offset is Integer range -2**15 .. 2**15 - 1;

A subtype is a type with a constraint added. An Offset is an Integer, so the two mix freely, but its value must lie between −32768 and 32767: at most half a turn either way. If a value outside that range is ever stored in an Offset, that is an error. At run time, Ada raises Constraint_Error. In SPARK, as you will see in chapter 5, the prover must show that it never happens at all.

Natural, used later in this spec, is a predefined subtype: Integer range 0 .. Integer'Last. Likewise Positive starts at 1.

Expression functions

engine/src/adawars-angles.ads
function Rotate (From : Angle; By : Offset) return Angle is
  (if By >= 0 then From + Angle (By) else From - Angle (-By));

A function whose body is a single expression can be written like this, as an expression function, right in the spec. The parenthesised expression is the whole body. This one uses an if expression: if ... then ... else ... that produces a value, like ?: in C.

Expression functions matter a great deal for proof. Because the body is in the spec, it is also the function's specification: anyone reading the spec, including the prover, knows exactly what Rotate returns. The engine uses them everywhere for that reason.

Why not (From + By) mod 2**16?

That works for an integer type, but By can be negative and Angle has no negative values. Adding or subtracting a non-negative amount keeps every value an Angle the whole way. An earlier version used Angle'Mod (By), which also works, but the provers timed out on it. Writing code that is easy to reason about is part of writing provable code.

A function with a postcondition

engine/src/adawars-angles.ads
function Diff (To, From : Angle) return Offset
with Post => Rotate (From, Diff'Result) = To;

Diff has no body in the spec; it is in the .adb. Instead it has a postcondition, the Post aspect: a Boolean expression that must be true whenever the function returns. Diff'Result is the value being returned. (The apostrophe introduces an attribute; you will meet many, such as 'First, 'Last and 'Range.)

So the contract says: whatever turn Diff returns, turning From by it lands exactly on To. Here is how it does it, in the body:

engine/src/adawars-angles.adb
package body Adawars.Angles with SPARK_Mode is

   function Diff (To, From : Angle) return Offset is
      D : constant Angle := To - From;
   begin
      return (if D < Half_Turn then Integer (D) else Integer (D) - 2**16);
   end Diff;

   procedure Lemma_Diff_Rotate (From : Angle; By : Offset) is null;

end Adawars.Angles;

This is an ordinary function body. Declarations go between is and begin; statements go between begin and end. D is a constant local to the function. Because Angle wraps, To - From is the anticlockwise distance from From to To. If that is more than half a turn, the shorter way is clockwise, so the function returns it as a negative number.

GNATprove proves that this body meets the postcondition for every pair of angles, all 2³² of them, without running it once. Chapter 5 explains how.

A lemma

engine/src/adawars-angles.ads
procedure Lemma_Diff_Rotate (From : Angle; By : Offset)
with
  Ghost,
  Global => null,
  Post   => Diff (Rotate (From, By), From) = By;

A procedure is a subprogram that returns no value. This one does nothing at all: its body, in the .adb, is is null. It exists only for its postcondition. GNATprove proves that the postcondition holds for every From and By, and from then on that fact is available wherever the procedure is called. A procedure used like this is a lemma: a small proved fact you can cite in a larger proof.

Ghost marks it as existing only for the prover; chapter 8 is about ghost code. Global => null says it reads and writes no global variables.

Together, Diff's postcondition and this lemma say that Rotate and Diff are inverses. The flight code relies on that: it proves that a jet turns by exactly the amount its stick asks for.

Try it

Read the proof results. Prove this one unit with --report=all, which lists every check, not just the failures. Among them is the postcondition of Diff, and the range check on its result:

Expect: report adawars-angles.adb passes
info: postcondition proved --> adawars-angles.ads:21:17
info: range check proved --> adawars-angles.adb:6:66
Success: all checks proved

Each message names the file, line and column of the check: line 21 of the spec is Diff's Post, and line 6 of the body is its return, where the result must fit in an Offset.

Break the postcondition. Get the wraparound wrong in Diff's body:

Try: engine/src/adawars-angles.adb
-      return (if D < Half_Turn then Integer (D) else Integer (D) - 2**16);
+      return (if D < Half_Turn then Integer (D) else Integer (D) - 2**15);

GNATprove reports that the postcondition might fail. It also gives a counterexample after e.g.: values for which it does.

Expect: prove adawars-angles.adb fails
postcondition might fail
e.g. when

Mix the types. Leave out the conversion in Rotate, adding an Offset straight to an Angle:

Try: engine/src/adawars-angles.ads
-     (if By >= 0 then From + Angle (By) else From - Angle (-By));
+     (if By >= 0 then From + By else From - Angle (-By));

The compiler refuses before any proof is attempted. An Integer is not an Angle, and Ada will not guess which you meant.

Expect: build fails
adawars-angles.ads:17

Watch it wrap. Declare a full turn, and assert something surprising about it:

Try: engine/src/adawars-angles.ads
    Half_Turn    : constant Angle := 2**15;
+   Full_Turn    : constant Angle := 2**16;
+   pragma Assert (Full_Turn = 0);

This compiles, and the assertion is proved. Because the expected type is Angle, the ** here is Angle's own operator, and like all of Angle's arithmetic it wraps: 2¹⁶ is a full turn, which is no turn at all.

Expect: report adawars-angles.ads passes
info: assertion proved --> adawars-angles.ads:12

Recap

  • A package has a spec (what) and a body (how).
  • A modular type wraps around; a range subtype constrains a type.
  • Converting between types is explicit.
  • Expression functions are their own specification.
  • Post states what a subprogram guarantees, and 'Result names its result.
  • A lemma is a procedure that does nothing, kept for its proved postcondition.