Skip to content

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:

engine/src/adawars-angles.ads
   --  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;
engine/src/adawars-angles.adb
   procedure Lemma_Diff_Rotate (From : Angle; By : Offset) is null;

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:

engine/src/adawars-simulation.adb
   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:

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

engine/src/adawars-trig-table_facts.ads
   --  The sine table rises.
   procedure Rising_Step (I : Natural)
   with
     Global => null,
     Pre    => I < Steps,
     Post   => Quarter_Sine (I) <= Quarter_Sine (I + 1);
engine/src/adawars-trig-table_facts.adb
   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:

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

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

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

Expect: prove adawars-trig.adb fails
postcondition might fail --> adawars-trig.ads:61

Now try the same with the rising chain:

Try: engine/src/adawars-trig.adb
       for K in Within (A) .. Within (B) - 1 loop
-         Table_Facts.Rising_Step (K);
          pragma Loop_Invariant
Expect: prove adawars-trig.adb passes

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:

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

engine/src/adawars-simulation-lemmas.adb
   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

engine/src/adawars-simulation-lemmas.ads
pragma Assertion_Policy (Ghost => Ignore);

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_Equal provides it.
  • Assertion_Policy (Ghost => Ignore) leaves ghost code out of the build.