8. Ghost code and lemmas¶
Sometimes the provers cannot prove something unaided, however true it is. They need a hint: an intermediate fact, a case split, a step of reasoning. Ghost code is how you give them one. It is code that exists for the prover only, and does nothing in the running program.
Lemmas, again¶
You met a lemma in chapter 1:
-- 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;
A lemma is a procedure whose postcondition is the fact. Proving the procedure proves the fact, for every possible argument. Calling the procedure makes the fact available, for the arguments given, at the point of the call.
Here is where it is called, flying a jet:
function Flown_Jet (J : Jet; C : Control) return Jet is
Heading : constant Angle := Rotate (J.Heading, Stick_Turn (C.Turn));
Speed : constant Airspeed := Flown_Speed (J, C);
begin
Lemma_Diff_Rotate (J.Heading, Stick_Turn (C.Turn));
Flown_Jet's postcondition promises that the jet turns by exactly what the
stick asks:
-- It turns exactly as the stick asks, ...
and then Diff (Flown_Jet'Result.Heading, J.Heading)
= Stick_Turn (C.Turn)
That is precisely the lemma's fact, for this heading and this turn. Proving it directly, inside the larger context of flying a jet, is harder for the provers than proving it once, alone, and citing it.
Why Flown_Jet has an ordinary body
An expression function cannot contain a procedure call, so it cannot cite
a lemma. That is why Flown_Jet has a body with statements, and why its
postcondition restates its whole definition: callers get the same
knowledge an expression function would have given them.
The Ghost aspect¶
Ghost marks an entity as existing only for verification. The compiler
checks that ghost code never affects the real program: a ghost procedure can
read normal variables, but normal code cannot read ghost ones. So deleting
all ghost code never changes what the program does, and the build can leave
it out.
Facts about tables¶
Provers are poor at facts about a constant array at an unknown index. Ask
them whether the sine table rises, Quarter_Sine (I) <= Quarter_Sine (I + 1)
for every I, and they see a constant array and a symbolic I, and may
well give up. For harder facts, as the exercise below shows, they certainly
do.
The engine's answer is to generate one fact per index, with a script
(engine/tools/trig_tables.py):
-- The sine table rises.
procedure Rising_Step (I : Natural)
with
Global => null,
Pre => I < Steps,
Post => Quarter_Sine (I) <= Quarter_Sine (I + 1);
procedure Rising_Step (I : Natural) is
begin
case I is
when 0 => null;
when 1 => null;
when 2 => null;
...
end Rising_Step;
Each branch does nothing, but within each branch I is a literal, so the
postcondition is concrete arithmetic on two known numbers. The provers can
do that.
Then a ghost loop chains the steps together to prove that sine rises between any two angles in the first quarter:
for K in Within (A) .. Within (B) - 1 loop
Table_Facts.Rising_Step (K);
pragma Loop_Invariant
(Quarter_Sine (Within (A)) <= Quarter_Sine (K + 1));
end loop;
The loop does nothing at run time. It is a proof by induction, written as a loop: each iteration cites one step, and the invariant accumulates them.
Try it: drop a citation¶
The other table fact says that every heading is a unit vector: mirrored
entries of the sine table, squared and added, come to one (within
rounding). Lemma_Unit_Circle cites it for one angle:
-- Sine and cosine of the same angle read mirrored table entries.
procedure Lemma_Unit_Circle (A : Angle) is
begin
Table_Facts.Unit_Pair (Within (A));
pragma Assert (Within (A + Quarter_Turn) = Within (A));
end Lemma_Unit_Circle;
Take the citation out:
begin
- Table_Facts.Unit_Pair (Within (A));
pragma Assert (Within (A + Quarter_Turn) = Within (A));
Without the fact for that one index, the provers face squares of table entries at an unknown index, and cannot prove the postcondition:
Now try the same with the rising chain:
for K in Within (A) .. Within (B) - 1 loop
- Table_Facts.Rising_Step (K);
pragma Loop_Invariant
It still proves. Comparing two neighbouring entries is simple enough that the current provers manage it without the hint. The citation stays in the engine anyway: it costs nothing at run time, and a proof that depends on how clever a prover happens to be can break when the prover changes. The unit-circle fact, with its squares, is beyond them without help.
Logical equality¶
Here is a fact that should be easy. The controls of a jet that is already
destroyed should make no difference to the tick. Step replaces them with
Idle (that is what Masked does), so stating the lemma looks simple:
-- The controls of destroyed jets make no difference.
procedure Dead_Controls_Ignored (W : World; C : Control_Array)
with
Global => null,
Pre => Valid (W) and then Fits (W, C),
Post => Step (W, C) = Step (W, Masked (W, C));
The argument is that masking twice is the same as masking once. The provers
can show that element by element. But for arrays, Ada's = is a function
like any other. Knowing that two arrays are = does not let the prover
substitute one for the other inside a call to Step. It needs the arrays to
be the same value, in its own logic.
SPARK provides for this. A function annotated Logical_Equal is the
prover's equality:
function Same (X, Y : Control_Array) return Boolean
with
Import,
Global => null,
Annotate => (GNATprove, Logical_Equal);
procedure Dead_Controls_Ignored (W : World; C : Control_Array) is
M : constant Control_Array := Masked (W, C);
begin
-- Masking is idempotent, so Step sees the same controls either way.
pragma Assert (for all P in C'Range => Masked (W, M) (P) = M (P));
pragma Assert (Masked (W, M) = M);
pragma Assert (Same (Masked (W, M), M));
end Dead_Controls_Ignored;
The assertions walk the prover there one step at a time: element by element,
then array =, then logical equality. From the last, substitution is
allowed, and the postcondition follows.
Same is Imported: it has no body, because it could not have one that
means what the annotation says. So this package must never generate code.
Both its files begin with
which tells the compiler to leave out all ghost code. The whole package is ghost, so nothing is compiled at all.
Assertions as stepping stones¶
Plain pragma Assert is ghost code of a kind too: it is a fact proved at one
point and usable after it. The longest proof in the engine, chapter 11's
codec, is a sequence of assertions, each one a step the provers can manage
from the one before.
Recap¶
- A lemma is a ghost procedure whose postcondition is the fact; calling it cites the fact.
- Ghost code is for the prover only, and can never change what the program does.
- Facts about constant tables are proved one index at a time, then chained with a ghost loop.
=on arrays is not the prover's equality;Logical_Equalprovides it.Assertion_Policy (Ghost => Ignore)leaves ghost code out of the build.