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:
-- 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¶
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¶
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.
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¶
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¶
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:
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¶
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:
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:
- 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.
Mix the types. Leave out the conversion in Rotate, adding an Offset
straight to an Angle:
- (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.
Watch it wrap. Declare a full turn, and assert something surprising about it:
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.
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.
Poststates what a subprogram guarantees, and'Resultnames its result.- A lemma is a procedure that does nothing, kept for its proved postcondition.