Hoare Logic

6. Hoare2: Hoare Logic, Part II🔗

Note to developers (before next release)

BCP 23,25: There are a lot of questions about the flow of this material. Needs a deep look. In particular:

  • One feels that it takes a rather circuitous route to get to formal decorated programs -- there might be a way to just go straight there. More importantly, it isn't very clear to me that the version of decorated programs that we wound up with is really the right one -- why spend all this time writing annotations that we then say are unnecessary? Seems like we could define decorated programs with a lighter annotation burden (as in the exercise at the end) and just add optional annotations when we want to, to make particular examples clearer.

  • The rigidity of the Hoare rules as stated in the last chapter is also annoying here at many points. Building the rules of consequence into all the other rules might make a lot of things smoother. Would be a big change (also to Hoare.v), but definitely worth a try.

And related...

Note to developers (Michael Clarkson @clarksmr, before next release, 2020)

Here are a bunch of improvements I wanted to make but didn't have time to get to. Maybe next time if no one else gets to them first.

    1. Weakest preconditions show up in this chapter as completely optional, then are revisited (and required) in HoareAsLogic. Consider moving the entire treatment to that chapter. (BCP 23: Yes, we should do that!)

    1. It seems a shame that the SparseAnnotations section is not visible in the full version, but only in a solution. It's fantastic! It would be great to show it off. (BCP 25: Yes! Indeed, perhaps it should even replace the current treatment!)

Note to developers

HIDE: Some useful theorems about Imp are not being redefined for the modified versions of Imp. We should either re-prove them or add hints (or exercises!) about this. BCP 20: Which ones???

In Hoare, we defined Hoare Logic's proof rules and proved them sound. In this chapter, we put those rules to work: verifying Imp programs by formalizing the informal proof sketches we call decorated programs.

Such proofs require specifications, i.e., the pre- and post-conditions that explain what programs are supposed to do. Let's play with writing specifications.

Quiz

Write down a Hoare-triple specification for the following program:

X := 2;
Y := X + X
Show solution
{{True}} c {{X = 2 ∧ Y = 4}}
Quiz

Write down a (useful) specification for the following program:

X := X + 1;
Y := X + 1
Show solution
∀ m, {{ X=m }} c {{ X = m+1 ∧ Y = m+2 }}

This is more interesting than {{ True }} c {{ Y > X }}.

Quiz

Write down a (useful) specification for the following program:

if X ≤ Y then
  skip
else
  Z := X;
  X := Y;
  Y := Z
end
Show solution

One obvious spec is {{True}} c {{X≤Y}}, but this loses the fact that the final values are either the same as the initial or else swapped, so then a spec with parameters seems preferable. There's also a question about whether to say something about Z in the postcondition.

Quiz

Write down a (useful) specification for the following program:

X := m;
Y := X + X
Show solution
{{True}} c {{X = m ∧ Y = 2 * m}}
Quiz

Write down a (useful) specification for the following program:

X := m;
Z := 0;
while X ≠ 0 do
  X := X - 2;
  Z := Z + 1
end
Show solution
{{True}} c {{X = 0 ∧ Z = (m + 1) / 2}}

Here / is natural-number division: the loop subtracts 2 from X each time around, so it runs ⌈m / 2⌉ times whether m is even or odd, thanks to truncated subtraction turning the odd case's last 1 into 0 rather than going negative.

6.1. Decorated Programs🔗

The beauty of Hoare Logic is that it is syntax directed: the structure of proofs exactly follows the structure of programs.

We can record the essential ideas of a Hoare-logic proof — omitting low-level calculational details — by "decorating" a program with appropriate assertions on each of its commands.

Such a decorated program carries within itself an argument for its own correctness.

For example, consider the program:

X := m;
Z := p;
while X ≠ 0 do
  Z := Z - 1;
  X := X - 1
end

Here is one possible specification for this program, in the form of a Hoare triple:

{{ True }}
X := m;
Z := p;
while X ≠ 0 do
  Z := Z - 1;
  X := X - 1
end
{{ Z = p - m }}

(Note the parameters m and p, which stand for fixed-but-arbitrary numbers. Formally, they are simply Lean variables of type Nat.)

Here is a decorated version of this program, embodying a proof of this specification:

{{ True }} ↠
{{ m = m }}
  X := m
                     {{ X = m }} ↠
                     {{ X = m ∧ p = p }};
  Z := p;
                     {{ X = m ∧ Z = p }} ↠
                     {{ Z - X = p - m }}
  while X ≠ 0 do
                     {{ Z - X = p - m ∧ X ≠ 0 }} ↠
                     {{ (Z - 1) - (X - 1) = p - m }}
    Z := Z - 1
                     {{ Z - (X - 1) = p - m }};
    X := X - 1
                     {{ Z - X = p - m }}
  end
{{ Z - X = p - m ∧ ¬ (X ≠ 0) }} ↠
{{ Z = p - m }}

Concretely, a decorated program consists of the program's text interleaved with assertions (sometimes multiple assertions separated by ↠).

A decorated program can be viewed as a compact representation of a proof in Hoare Logic: the assertions surrounding each command specify the Hoare triple to be proved for that part of the program using one of the Hoare Logic rules, and the structure of the program itself shows how to assemble all these individual steps into a proof for the whole program.

Our goal is to verify such decorated programs "mostly automatically." But, before we can verify anything, we need to be able to find a proof for a given specification, and for this we need to discover the right assertions. This can be done in an almost mechanical way, with the exception of finding loop invariants. In the remainder of this section, we explain in detail how to construct decorations for several short programs, all of which are loop free or have simple loop invariants. We'll return to finding more interesting loop invariants later in the chapter.

6.1.1. Example: Swapping🔗

Consider the following program, which swaps the values of two variables using addition and subtraction, instead of by assigning to a temporary variable.

X := X + Y;
Y := X - Y;
X := X - Y

We can give a proof, in the form of decorations, that this program is correct — i.e., it really swaps X and Y — as follows.

(1)    {{ X = m ∧ Y = n }} ↠
(2)    {{ (X + Y) - ((X + Y) - Y) = n ∧ (X + Y) - Y = m }}
         X := X + Y
(3)                     {{ X - (X - Y) = n ∧ X - Y = m }};
         Y := X - Y
(4)                     {{ X - Y = n ∧ Y = m }};
         X := X - Y
(5)    {{ X = n ∧ Y = m }}

The decorations can be constructed as follows:

  • We begin with the undecorated program (the unnumbered lines).

  • We add the specification — i.e., the outer precondition (1) and postcondition (5). In the precondition, we use parameters m and n to remember the initial values of variables X and Y so that we can refer to them in the postcondition (5).

  • We work backwards, mechanically, starting from (5) and proceeding until we get to (2). At each step, we obtain the precondition of the assignment from its postcondition by substituting the assigned variable with the right-hand-side of the assignment. For instance, we obtain (4) by substituting X with X - Y in (5), and we obtain (3) by substituting Y with X - Y in (4).

  • Finally, we verify that (1) logically implies (2) — i.e., that the step from (1) to (2) is a valid use of the law of consequence — by doing a bit of high-school algebra.

Note to developers

HIDE: BCP 21: This side comment seems too technical:

  • (Note that we are working with natural numbers rather than fixed-width machine integers, so we don't need to worry about the possibility of arithmetic overflow anywhere in this argument. This makes life quite a bit simpler!)

HIDE: A quick / optional exercise using just assignment here would be good.

6.1.2. Example: Simple Conditionals🔗

Here is a simple decorated program using conditionals:

(1)   {{ True }}
        if X ≤ Y then
(2)                    {{ True ∧ X ≤ Y }} ↠
(3)                    {{ (Y - X) + X = Y ∨ (Y - X) + Y = X }}
          Z := Y - X
(4)                    {{ Z + X = Y ∨ Z + Y = X }}
        else
(5)                    {{ True ∧ ¬(X ≤ Y) }} ↠
(6)                    {{ (X - Y) + X = Y ∨ (X - Y) + Y = X }}
          Z := X - Y
(7)                    {{ Z + X = Y ∨ Z + Y = X }}
        end
(8)   {{ Z + X = Y ∨ Z + Y = X }}

These decorations can be constructed as follows:

  • We start with the outer precondition (1) and postcondition (8).

  • Following the format dictated by the hoare_if rule, we copy the postcondition (8) to (4) and (7). We conjoin the precondition (1) with the guard of the conditional to obtain (2). We conjoin (1) with the negated guard of the conditional to obtain (5).

  • In order to use the assignment rule and obtain (3), we substitute Z by Y - X in (4). To obtain (6) we substitute Z by X - Y in (7).

  • Finally, we verify that (2) implies (3) and (5) implies (6). Both of these implications crucially depend on the ordering of X and Y obtained from the guard. For instance, knowing that X ≤ Y ensures that subtracting X from Y and then adding back X produces Y, as required by the first disjunct of (3). Similarly, knowing that ¬ (X ≤ Y) ensures that subtracting Y from X and then adding back Y produces X, as needed by the second disjunct of (6). Note that n - m + m = n does not hold for arbitrary natural numbers n and m (for example, [3 - 5 + 5 = 5]).

Exercise★★(if_minus_plus_reloaded) (Optional, Manually graded)

N.b.: Although this exercise is marked optional, it is an excellent warm-up for the (non-optional) if_minus_plus_correct exercise below!

Fill in valid decorations for the following program:

{{ True }}
  if X ≤ Y then
            {{                         }} ↠
            {{                         }}
    Z := Y - X
            {{                         }}
  else
            {{                         }} ↠
            {{                         }}
    Y := X + Z
            {{                         }}
  end
{{ Y = X + Z }}

Briefly justify each use of ↠.

{{ True }}
  if X ≤ Y then
       {{ True ∧ X ≤ Y }} ↠
       {{ Y = X + (Y - X) }}
    Z := Y - X
       {{ Y = X + Z }}
  else
       {{ True ∧ ¬(X ≤ Y) }} ↠
       {{ X + Z = X + Z }}
    Y := X + Z
       {{ Y = X + Z }}
  end
{{ Y = X + Z }}

The second use of consequence is trivial, while the first crucially depends on the X ≤ Y condition, which ensures that subtracting X from Y and then adding back X produces Y.

6.1.3. Example: Reduce to Zero🔗

Here is a while loop that is so simple that True suffices as a loop invariant.

(1)    {{ True }}
         while X ≠ 0 do
(2)                  {{ True ∧ X ≠ 0 }} ↠
(3)                  {{ True }}
           X := X - 1
(4)                  {{ True }}
         end
(5)    {{ True ∧ ¬(X ≠ 0) }} ↠
(6)    {{ X = 0 }}

The decorations can be constructed as follows:

  • Start with the outer precondition (1) and postcondition (6).

  • Following the format dictated by the hoare_while rule, we copy (1) to (4). We conjoin (1) with the guard to obtain (2). We also conjoin (1) with the negation of the guard to obtain (5).

  • Because the final postcondition (6) does not syntactically match (5), we add an implication between them.

  • Using the assignment rule with assertion (4), we trivially substitute and obtain assertion (3).

  • We add the implication between (2) and (3).

Finally we check that the implications do hold; both are trivial.

6.1.4. Example: Division🔗

Let's do one more example of simple reasoning about a loop.

The following Imp program calculates the integer quotient and remainder of parameters m and n.

X := m;
Y := 0;
while n ≤ X do
  X := X - n;
  Y := Y + 1
end;

If we replace m and n by concrete numbers and execute the program, it will terminate with the variable X set to the remainder when m is divided by n and Y set to the quotient.

In order to give a specification to this program we need to remember that dividing m by n produces a remainder X and a quotient Y such that n * Y + X = m ∧ X < n.

It turns out that we get lucky with this program and don't have to think very hard about the loop invariant: the loop invariant is just the first conjunct, n * Y + X = m, and we can use this to decorate the program.

 (1)  {{ True }} ↠
 (2)  {{ n * 0 + m = m }}
        X := m;
 (3)                     {{ n * 0 + X = m }}
        Y := 0;
 (4)                     {{ n * Y + X = m }}
        while n ≤ X do
 (5)                     {{ n * Y + X = m ∧ n ≤ X }} ↠
 (6)                     {{ n * (Y + 1) + (X - n) = m }}
          X := X - n;
 (7)                     {{ n * (Y + 1) + X = m }}
          Y := Y + 1
 (8)                     {{ n * Y + X = m }}
        end
 (9)  {{ n * Y + X = m ∧ ¬ (n ≤ X) }} ↠
(10)  {{ n * Y + X = m ∧ X < n }}

Assertions (4), (5), (8), and (9) are derived mechanically from the loop invariant and the loop's guard. Assertions (8), (7), and (6) are derived using the assignment rule going backwards from (8) to (6). Assertions (4), (3), and (2) are again backwards applications of the assignment rule.

Now that we've decorated the program it only remains to check that the uses of the consequence rule are correct — i.e., that (1) implies (2), that (5) implies (6), and that (9) implies (10). This is indeed the case:

  • (1) ↠ (2): trivial, by algebra.

  • (5) ↠ (6): because n ≤ X, we are guaranteed that the subtraction in (6) does not get zero-truncated. We can therefore rewrite (6) as n * Y + n + X - n and cancel the ns, which results in the left conjunct of (5).

  • (9) ↠ (10): if ¬ (n ≤ X) then X < n. That's straightforward from high-school algebra. So, we have a valid decorated program.

6.1.5. From Decorated Programs to Formal Proofs🔗

From an informal proof in the form of a decorated program, it is "easy in principle" to read off a formal proof using the Lean theorems corresponding to the Hoare Logic rules, but these proofs can be a bit long and fiddly.

Note that we do not unfold the definition of ValidHoareTriple anywhere in this proof: the point of the game we're playing now is to use the Hoare rules as a self-contained logic for reasoning about programs.

For example...

def reduceToZero : Com := imp { while (X ≠ 0) { X := X - 1 } } theorem reduce_to_zero_correct' : {{ True }} reduceToZero {{ X = 0 }} := ⊢ {{True}} ~reduceToZero {{X = 0}} -- First put the postcondition into the form expected by -- the while rule. ⊢ {{True}} ~reduceToZero {{?Q'}}⊢ ?Q' ↠ {{X = 0}}⊢ Assertion -- We use the fact that after the `while` loop, -- the loops condition must not hold. ⊢ {{True}} ~reduceToZero {{?Q'}} ⊢ {{True ∧ bexp {X ≠ 0} }} X := X - 1 {{True}} -- Trivial postcondition: we just need to prove `True` ⊢ {{True ∧ bexp {X ≠ 0} }} X := X - 1 {{True}} ⊢ ∀ (st : State), True; All goals completed! 🐙 -- Our precondition that `X ≠ 0` cannot hold is -- exactly what we need to prove `X = 0`. ⊢ {{True ∧ ¬bexp {X ≠ 0} }} ↠ {{X = 0}} ⊢ {{X = 0}} ↠ {{X = 0}} st✝:Stateh:st✝["X"] = 0⊢ st✝[X] = 0; All goals completed! 🐙

In Hoare we introduced a series of tactics named assertion_auto to automate proofs involving assertions.

The following declaration introduces a more sophisticated tactic that will help with proving assertions throughout the rest of this chapter. You don't need to understand the details, but briefly: it introduces the available hypotheses, simplifies assertions, maps, and arithmetic expressions, and then asks lia to solve linear arithmetic goals. What's left after verify_assertion does its work should be just the "interesting parts" of the proof (which, if we're lucky, will be nothing at all!).

macro "verify_assertion" : tactic => `(tactic| assertion_auto)

This makes it pretty easy to verify reduce_to_zero:

theorem reduce_to_zero_correct''' : {{ True }} reduceToZero {{ X = 0 }} := ⊢ {{True}} ~reduceToZero {{X = 0}} ⊢ {{True}} ~reduceToZero {{?Q'}}⊢ ?Q' ↠ {{X = 0}}⊢ Assertion ⊢ {{True ∧ bexp {X ≠ 0} }} X := X - 1 {{True}}⊢ {{True ∧ ¬bexp {X ≠ 0} }} ↠ {{X = 0}} all_goals All goals completed! 🐙

This example shows that it is conceptually straightforward to read off the main elements of a formal proof from a decorated program. Indeed, the process is so straightforward that it can be automated, as we will see next.

6.2. Formal Decorated Programs🔗

Our informal conventions for decorated programs amount to a way of "displaying" Hoare triples, in which commands are annotated with enough embedded assertions that checking the validity of a triple is reduced to simple logical and algebraic calculations showing that some assertions imply others.

In this section, we show that this presentation style can be made completely formal — and indeed that checking the validity of decorated programs can be largely automated.

6.2.1. Syntax🔗

The first thing we need to do is to formalize a variant of the syntax of Imp commands that includes embedded assertions, which we'll call "decorations." We call the new commands decorated commands, or dcoms.

The choice of exactly where to put assertions in the definition of dcom is a bit subtle. The simplest thing to do would be to annotate every dcom with a precondition and postcondition — something like this...

namespace DComFirstTry inductive DCom where | skip (pre : Assertion) | seq (pre : Assertion) (first : DCom) (middle : Assertion) (second : DCom) (post : Assertion) | asgn (x : Ident) (a : Aexp) (post : Assertion) | cond (pre : Assertion) (b : Bexp) (thenPre : Assertion) (thenBranch : DCom) (elsePre : Assertion) (elseBranch : DCom) (post : Assertion) | whileDo (pre : Assertion) (b : Bexp) (bodyPre : Assertion) (body : DCom) (bodyPost : Assertion) (post : Assertion) | strengthenPre (pre : Assertion) (body : DCom) | weakenPost (body : DCom) (post : Assertion) end DComFirstTry

But this would result in very verbose decorated programs with a lot of repeated annotations: a simple program like skip;skip would be decorated like this,

{{p}} ({{p}} skip {{p}}) ; ({{p}} skip {{p}}) {{p}}

with pre- and post-conditions around each skip, plus identical pre- and post-conditions on the semicolon!

In other words, we don't want both preconditions and postconditions on each command, because a sequence of two commands would contain redundant decorations — the postcondition of the first likely being the same as the precondition of the second.

Instead, our formal syntax of decorated commands will omit preconditions whenever possible and embed just postconditions.

The skip command skip is decorated only with its postcondition.

skip {{ q }}

The precondition will be provided by somebody else. We carry the same assumption through the other syntactic forms: each decorated command is assumed to carry its own postcondition within itself but take its precondition from its context in which it is used.

Sequences d₁ ; d₂ need no additional decorations. Why? Because inside d₂ there will be a postcondition, which also serves as the postcondition of d₁;d₂. Similarly, inside d₁ there will also be a postcondition, which additionally serves as the precondition for d₂.

An assignment X := a is decorated only with its postcondition:

X := a {{ q }}

A conditional if b then d₁ else d₂ is decorated with a postcondition for the entire statement, as well as preconditions for each branch:

if b then {{ p₁ }} d₁ else {{ p₂ }} d₂ end {{ q }}
Note to developers (Benjamin Pierce @bcpierce00, before next release, 2025)

Maybe we need a note here about why we don't just calculate p₁ and p₂ later, once we know the precondition of the whole loop. Indeed, we could (and perhaps should, as discussed elsewhere), but we are doing something simpler for the moment.

A loop while (b) {d} is decorated with its final postcondition plus a precondition for the body:

while (b) {{ p }} { d } {{ q }}

The postcondition embedded in d serves as the loop invariant.

Implications ↠ can be added as decorations either for a precondition...

↠ {{ p }} d

...or for a postcondition:

d ↠ {{ q }}

The former is waiting for another precondition to be supplied by the context; the latter relies on the postcondition already embedded in d.

Putting this all together gives us the formal syntax of decorated commands:

inductive DCom where | skip (post : Assertion) | seq (first second : DCom) | asgn (x : Ident) (a : Aexp) (post : Assertion) | cond (b : Bexp) (thenPre : Assertion) (thenBranch : DCom) (elsePre : Assertion) (elseBranch : DCom) (post : Assertion) | whileDo (b : Bexp) (bodyPre : Assertion) (body : DCom) (post : Assertion) | pre (pre : Assertion) (body : DCom) | post (body : DCom) (post : Assertion)

Lean keeps decorated-command notation in its own syntax category, dcom, so it can coexist with the ordinary Imp command syntax.

Notation encoding: decorated commandsdeclare_syntax_cat dcom syntax:max "(" dcom ")" : dcom syntax:max "skip" " {{" term "}}" : dcom syntax:max ident " := " imp_aexp " {{" term "}}" : dcom syntax:20 dcom:21 ";" ppDedent(ppLine dcom:20) : dcom syntax:max "if " "(" imp_bexp ")" ppHardSpace "then" ppLine "{{" term "}}" ppLine dcom ppDedent(ppLine "else") ppLine "{{" term "}}" ppLine dcom ppDedent(ppLine "end") ppLine "{{" term "}}" : dcom syntax:max "while " "(" imp_bexp ")" ppHardSpace "do" ppLine "{{" term "}}" ppLine dcom ppDedent(ppLine "end") ppLine "{{" term "}}" : dcom syntax:5 "↠" " {{" term "}}" ppLine dcom:0 : dcom syntax:5 dcom:6 ppLine "↠" " {{" term "}}" : dcom syntax:min "dcom" ppHardSpace "{" ppLine dcom ppDedent(ppLine "}") : term macro_rules | `(dcom { $s }) => do let stx ← match s with | `(dcom| ($body:dcom)) => `(dcom { $body }) | `(dcom| skip {{ $q }}) => `(DCom.skip ({{ $q }})) | `(dcom| $x:ident := $a:imp_aexp {{ $q }}) => `(DCom.asgn $x (aexp { $a }) ({{ $q }})) | `(dcom| $d₁:dcom; $d₂:dcom) => `(DCom.seq (dcom { $d₁ }) (dcom { $d₂ })) | `(dcom| if ($b:imp_bexp) then {{ $p₁ }} $d₁:dcom else {{ $p₂ }} $d₂:dcom end {{ $q }}) => `(DCom.cond (bexp { $b }) ({{ $p₁ }}) (dcom { $d₁ }) ({{ $p₂ }}) (dcom { $d₂ }) ({{ $q }})) | `(dcom| while ($b:imp_bexp) do {{ $p }} $body:dcom end {{ $q }}) => `(DCom.whileDo (bexp { $b }) ({{ $p }}) (dcom { $body }) ({{ $q }})) | `(dcom| ↠ {{ $p }} $body:dcom) => `(DCom.pre ({{ $p }}) (dcom { $body })) | `(dcom| $body:dcom ↠ {{ $q }}) => `(DCom.post (dcom { $body }) ({{ $q }})) | _ => Lean.Macro.throwUnsupported return Imp.Elab.withSourceInfoOf s stx namespace DCom.Delab open Lean PrettyPrinter Delaborator SubExpr Parenthesizer Imp.Elab Imp.Delab @[category_parenthesizer dcom] def dcom.parenthesizer : CategoryParenthesizer := fun prec => do maybeParenthesize `dcom false wrapParens prec <| parenthesizeCategoryCore `dcom prec where wrapParens (stx : Syntax) : Syntax := Unhygienic.run do let stxInfo := SourceInfo.fromRef stx let stx := stx.setInfo .none let pstx ← `(dcom| ($(⟨stx⟩))) return pstx.raw.setInfo stxInfo def getAssnBody (stx : Term) : Term := withSourceInfoOf (canonical := false) stx <| Unhygienic.run do match stx with | `({{ $p }}) => return p | _ => return stx private def getDCom? (stx : Term) : Option (TSyntax `dcom) := match stx with | `(dcom { $d:dcom }) => some <| withSourceInfoOf (canonical := false) stx d | _ => none @[app_unexpander DCom.skip] def unexpandSkip : Unexpander | `($_ $q) => `(dcom { skip {{ $(getAssnBody q) }} }) | _ => throw () @[app_unexpander DCom.asgn] def unexpandAsgn : Unexpander | `($_ $x:ident $a $q) => `(dcom { $x:ident := $(getAexp a) {{ $(getAssnBody q) }} }) | _ => throw () @[app_unexpander DCom.seq] def unexpandSeq : Unexpander | `($_ $first $second) => do let some first := getDCom? first | throw () let some second := getDCom? second | throw () `(dcom { $first; $second }) | _ => throw () @[app_unexpander DCom.cond] def unexpandCond : Unexpander | `($_ $b $thenPre $thenBranch $elsePre $elseBranch $post) => do let some thenBranch := getDCom? thenBranch | throw () let some elseBranch := getDCom? elseBranch | throw () `(dcom { if ($(getBexp b)) then {{ $(getAssnBody thenPre) }} $thenBranch else {{ $(getAssnBody elsePre) }} $elseBranch end {{ $(getAssnBody post) }} }) | _ => throw () @[app_unexpander DCom.whileDo] def unexpandWhileDo : Unexpander | `($_ $b $bodyPre $body $post) => do let some body := getDCom? body | throw () `(dcom { while ($(getBexp b)) do {{ $(getAssnBody bodyPre) }} $body end {{ $(getAssnBody post) }} }) | _ => throw () @[app_unexpander DCom.pre] def unexpandPre : Unexpander | `($_ $pre $body) => do let some body := getDCom? body | throw () `(dcom { ↠ {{ $(getAssnBody pre) }} $body }) | _ => throw () @[app_unexpander DCom.post] def unexpandPost : Unexpander | `($_ $body $post) => do let some body := getDCom? body | throw () `(dcom { $body ↠ {{ $(getAssnBody post) }} }) | _ => throw () end DCom.Delab
example : DCom := dcom { skip {{ True }} } example : DCom := dcom { while (true) do {{ True }} skip {{ True }} end {{ True }} }

To inspect the fully elaborated term behind this notation, put set_option pp.all true in before a #check or #print command.

To provide the initial precondition that goes at the very top of a decorated program, we introduce a new type decorated:

structure Decorated where pre : Assertion body : DCom

An example decorated program that decrements X to 0:

def decWhile : Decorated where pre := ({{ True }}) body := dcom { while (X ≠ 0) do {{ True ∧ ¬ X = 0 }} X := X - 1 {{ True }} end {{ True ∧ X = 0 }} ↠ {{ X = 0 }} }

It is easy to go from a dcom to a com by erasing all annotations.

def DCom.erase (d : DCom) : Com := match d with | .skip _ => .skip | .seq d₁ d₂ => .seq d₁.erase d₂.erase | .asgn x a _ => .asgn x a | .cond b _ d₁ _ d₂ _ => .cond b d₁.erase d₂.erase | .whileDo b _ body _ => .whileDo b body.erase | .pre _ body => body.erase | .post body _ => body.erase def Decorated.erase (dec : Decorated) : Com := dec.body.erase example : decWhile.erase = (imp { while (X ≠ 0) { X := X - 1 } }) := ⊢ decWhile.erase = imp {while (X ≠ 0) {X := X - 1} } All goals completed! 🐙

Aside: In the DCom.erase function we do not use dcom { ... } syntax in the pattern match. This is because dcom syntax is implemented with elab_rules, which provides no way to extend patterns, but provides more helpful error messages than does macro_rules, which we used to implement the imp syntax. In a definition, you can use either constructors directly or the decorated-command notation.

It is also straightforward to extract the precondition and postcondition from a decorated program.

@[simp] def Decorated.precondition (dec : Decorated) : Assertion := dec.pre

Notice the @[simp] annotation we added here.

This directs Lean to generate an equational lemma of the same form as the characterizing lemmas we've been writing by hand, such as validHoareTriple_def and Assertion.subst_apply in the Hoare chapter, and add it to the simp set. We can see the added equation by printing it.

equations: @[backward_defeq] theorem Decorated.precondition.eq_1 : ∀ (dec : Decorated), dec.precondition = dec.pre#print equations Decorated.precondition
equations:
@[backward_defeq] theorem Decorated.precondition.eq_1 : ∀ (dec : Decorated), dec.precondition = dec.pre

We'll add @[simp] annotations on the following definitions, too.

@[simp] def DCom.postcondition (d : DCom) : Assertion := match d with | .skip q => q | .seq _ d₂ => d₂.postcondition | .asgn _ _ q => q | .cond _ _ _ _ _ q => q | .whileDo _ _ _ q => q | .pre _ body => body.postcondition | .post _ q => q @[simp] def Decorated.postcondition (dec : Decorated) : Assertion := dec.body.postcondition example : decWhile.precondition = {{ True }} := ⊢ decWhile.precondition = {{True}} st:State⊢ decWhile.precondition st = True All goals completed! 🐙 example : decWhile.postcondition = {{ X = 0 }} := ⊢ decWhile.postcondition = {{X = 0}} st:State⊢ decWhile.postcondition st = (st[X] = 0) All goals completed! 🐙

6.2.2. Extracting Verification Conditions🔗

Now that we have defined what a decorated program is, we can express what it means for a particular decorated program to be correct, as a valid Hoare Triple:

def Decorated.OuterTripleValid (dec : Decorated) : Prop := ValidHoareTriple dec.precondition dec.erase dec.postcondition

For example, here is this definition unfolded for decWhile:

example : decWhile.OuterTripleValid = {{ True }} while (X ≠ 0) { X := X - 1 } {{ X = 0 }} := ⊢ decWhile.OuterTripleValid = {{True}} while (X ≠ 0) {X := X - 1} {{X = 0}} All goals completed! 🐙

The outer Hoare triple of a decorated program is just a Prop; thus, to show that it is valid, we need to produce a proof of this proposition.

We will do this by extracting "proof obligations" from the decorations sprinkled throughout the program.

These obligations are often called verification conditions, because they are the facts that must be verified to see that the decorations are locally consistent and thus constitute a proof of validity of the outer triple.

The function DCom.VerificationConditions takes a decorated command d together with a precondition p and returns a proposition that, if it can be proved, implies that the triple

{{p}} d.erase {{d.postcondition}}

is valid.

It does this by walking over d and generating a big conjunction that includes

  • local consistency checks for each form of command, plus

  • uses of ↠ to bridge the gap between the assertions found inside a decorated command and the assertions imposed by the external precondition; these uses correspond to applications of the consequence rule.

6.2.2.1. Local consistency🔗

The skip command skip {{q}} is locally consistent with respect to a precondition p if p ↠ q.

The sequential composition d₁ and d₂ is locally consistent with respect to p if

  1. d₁ is locally consistent with respect to p

  2. d₂ is locally consistent with respect to the postcondition of d₁.

An assignment X := a {{q}} is locally consistent with respect to a precondition p if p ↠ q [X ↦ a].

A conditional if b then {{p₁}} d₁ else {{p₂}} d₂ end {{q}} is locally consistent with respect to precondition p if

  1. p ∧ b ↠ p₁

  2. p ∧ ¬ b ↠ p₂

  3. d₁ is locally consistent with respect to p₁

  4. d₂ is locally consistent with respect to p₂

  5. d₁.postcondition ↠ q

  6. d₂.postcondition ↠ q

A loop while (b) {{{q}} d} {{r}} is locally consistent with respect to precondition p if:

  1. p ↠ d.postcondition

  2. d.postcondition ∧ b ↠ q

  3. d.postcondition ∧ ¬ b ↠ r

  4. d is locally consistent with respect to q

A command with an extra assertion at the beginning, ↠ {{q}} d is locally consistent with respect to a precondition p if:

  1. p ↠ q

  2. d is locally consistent with respect to q

A command with an extra assertion at the end d ↠ {{q}} is locally consistent with respect to a precondition p if:

  1. d is locally consistent with respect to p

  2. d.postcondition ↠ q

6.2.2.2. Verification Condition Generation🔗

With all this in mind, we can write a verification condition generator that takes a decorated command and reads off a proposition saying that all its decorations are locally consistent.

Formally, since a decorated command is "waiting for its precondition" the main VC generator takes a dcom plus a given precondition as arguments.

Note to developers

HIDE: There was some discussion in 2016 about whether the VC generator should should use equivalence or implication in a few places. I (BCP) believe Phil (Wadler) changed some instances of the former to the latter.

@[simp] def DCom.VerificationConditions (p : Assertion) (d : DCom) : Prop := match d with | .skip q => p ↠ q | .seq d₁ d₂ => d₁.VerificationConditions p ∧ d₂.VerificationConditions d₁.postcondition | .asgn x a q => p ↠ {{ q [x ↦ a] }} | .cond b p₁ d₁ p₂ d₂ q => ({{ p ∧ b }} ↠ p₁) ∧ ({{ p ∧ ¬ b }} ↠ p₂) ∧ (d₁.postcondition ↠ q) ∧ (d₂.postcondition ↠ q) ∧ d₁.VerificationConditions p₁ ∧ d₂.VerificationConditions p₂ | .whileDo b bodyPre body q => -- The body's postcondition is both the loop invariant -- and the precondition for the first iteration. (p ↠ body.postcondition) ∧ ({{ body.postcondition ∧ b }} ↠ bodyPre) ∧ ({{ body.postcondition ∧ ¬ b }} ↠ q) ∧ body.VerificationConditions bodyPre | .pre p' body => (p ↠ p') ∧ body.VerificationConditions p' | .post body q => body.VerificationConditions p ∧ (body.postcondition ↠ q)

The following key theorem states that DCom.VerificationConditions does its job correctly. Not surprisingly, each of the Hoare Logic rules plays a critical role at some point in the proof.

theorem verification_correct (d : DCom) (p : Assertion) (hvc : d.VerificationConditions p) : ValidHoareTriple p d.erase d.postcondition := d:DComp:Assertionhvc:DCom.VerificationConditions p d⊢ ValidHoareTriple p d.erase d.postcondition induction d generalizing p with body:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhvc:DCom.VerificationConditions p body ∧ (body.postcondition ↠ q)⊢ ValidHoareTriple p body.erase q -- Note that we need to escape `skip` as `«skip»`, -- as it is a reserved word under Hoare2's `dcom` syntax. q:Assertionp:Assertionhvc:p ↠ q⊢ ValidHoareTriple p (imp {«skip»}) q q:Assertionp:Assertionhvc:p ↠ q⊢ {{?«skip».P'}} «skip» {{q}}q:Assertionp:Assertionhvc:p ↠ q⊢ p ↠ ?«skip».P'q:Assertionp:Assertionhvc:p ↠ q⊢ Assertion q:Assertionp:Assertionhvc:p ↠ q⊢ {{?«skip».P'}} «skip» {{q}} All goals completed! 🐙 q:Assertionp:Assertionhvc:p ↠ q⊢ p ↠ q All goals completed! 🐙 d₁:DComd₂:DComih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionhvc:DCom.VerificationConditions p d₁ ∧ DCom.VerificationConditions d₁.postcondition d₂⊢ ValidHoareTriple p (imp {~d₁.erase; ~d₂.erase}) d₂.postcondition d₁:DComd₂:DComih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionh₁:DCom.VerificationConditions p d₁h₂:DCom.VerificationConditions d₁.postcondition d₂⊢ ValidHoareTriple p (imp {~d₁.erase; ~d₂.erase}) d₂.postcondition d₁:DComd₂:DComih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionh₁:DCom.VerificationConditions p d₁h₂:DCom.VerificationConditions d₁.postcondition d₂⊢ {{?seq.Q}} ~d₂.erase {{fun st => d₂.postcondition st}}d₁:DComd₂:DComih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionh₁:DCom.VerificationConditions p d₁h₂:DCom.VerificationConditions d₁.postcondition d₂⊢ {{p}} ~d₁.erase {{?seq.Q}}d₁:DComd₂:DComih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionh₁:DCom.VerificationConditions p d₁h₂:DCom.VerificationConditions d₁.postcondition d₂⊢ Assertion d₁:DComd₂:DComih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionh₁:DCom.VerificationConditions p d₁h₂:DCom.VerificationConditions d₁.postcondition d₂⊢ {{?seq.Q}} ~d₂.erase {{fun st => d₂.postcondition st}} d₁:DComd₂:DComih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionh₁:DCom.VerificationConditions p d₁h₂:DCom.VerificationConditions d₁.postcondition d₂⊢ DCom.VerificationConditions ({{?seq.Q}}) d₂; All goals completed! 🐙 d₁:DComd₂:DComih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionh₁:DCom.VerificationConditions p d₁h₂:DCom.VerificationConditions d₁.postcondition d₂⊢ {{p}} ~d₁.erase {{fun st => d₁.postcondition st}} d₁:DComd₂:DComih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionh₁:DCom.VerificationConditions p d₁h₂:DCom.VerificationConditions d₁.postcondition d₂⊢ DCom.VerificationConditions ({{p}}) d₁; All goals completed! 🐙 x:Identa:Aexpq:Assertionp:Assertionhvc:p ↠ {{q [x ↦ a]}}⊢ ValidHoareTriple p (imp {x := a}) q x:Identa:Aexpq:Assertionp:Assertionhvc:p ↠ {{q [x ↦ a]}}⊢ {{?asgn.P'}} x := a {{q}}x:Identa:Aexpq:Assertionp:Assertionhvc:p ↠ {{q [x ↦ a]}}⊢ p ↠ ?asgn.P'x:Identa:Aexpq:Assertionp:Assertionhvc:p ↠ {{q [x ↦ a]}}⊢ Assertion x:Identa:Aexpq:Assertionp:Assertionhvc:p ↠ {{q [x ↦ a]}}⊢ {{?asgn.P'}} x := a {{q}} All goals completed! 🐙 x:Identa:Aexpq:Assertionp:Assertionhvc:p ↠ {{q [x ↦ a]}}⊢ p ↠ q [x ↦ a] All goals completed! 🐙 b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionhvc:({{p ∧ b}} ↠ p₁) ∧ ({{p ∧ ¬b}} ↠ p₂) ∧ (d₁.postcondition ↠ q) ∧ (d₂.postcondition ↠ q) ∧ DCom.VerificationConditions p₁ d₁ ∧ DCom.VerificationConditions p₂ d₂⊢ ValidHoareTriple p (imp {if (b) {~d₁.erase} else {~d₂.erase} }) q b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:∀ (p : Assertion), DCom.VerificationConditions p d₁ → ValidHoareTriple p d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ ValidHoareTriple p (imp {if (b) {~d₁.erase} else {~d₂.erase} }) q b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:∀ (p : Assertion), DCom.VerificationConditions p d₂ → ValidHoareTriple p d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ ValidHoareTriple p (imp {if (b) {~d₁.erase} else {~d₂.erase} }) q b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ ValidHoareTriple p (imp {if (b) {~d₁.erase} else {~d₂.erase} }) q b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{p ∧ b}} ~d₁.erase {{q}}b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{p ∧ ¬b}} ~d₂.erase {{q}} b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{p ∧ b}} ~d₁.erase {{q}} b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{?cond.htrue.P'}} ~d₁.erase {{?cond.htrue.Q'}}b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{p ∧ b}} ↠ ?cond.htrue.P'b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ ?cond.htrue.Q' ↠ qb:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ Assertionb:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ Assertion b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{?cond.htrue.P'}} ~d₁.erase {{?cond.htrue.Q'}} All goals completed! 🐙 b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{p ∧ b}} ↠ p₁ All goals completed! 🐙 b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ d₁.postcondition ↠ q All goals completed! 🐙 b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{p ∧ ¬b}} ~d₂.erase {{q}} b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{?cond.hfalse.P'}} ~d₂.erase {{?cond.hfalse.Q'}}b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{p ∧ ¬b}} ↠ ?cond.hfalse.P'b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ ?cond.hfalse.Q' ↠ qb:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ Assertionb:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ Assertion b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{?cond.hfalse.P'}} ~d₂.erase {{?cond.hfalse.Q'}} All goals completed! 🐙 b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ {{p ∧ ¬b}} ↠ p₂ All goals completed! 🐙 b:Bexpp₁:Assertiond₁:DComp₂:Assertiond₂:DComq:Assertionih₁:ValidHoareTriple p₁ d₁.erase d₁.postconditionih₂:ValidHoareTriple p₂ d₂.erase d₂.postconditionp:Assertionhpre₁:{{p ∧ b}} ↠ p₁hpre₂:{{p ∧ ¬b}} ↠ p₂hd₁:d₁.postcondition ↠ qhd₂:d₂.postcondition ↠ qhthen:DCom.VerificationConditions p₁ d₁helse:DCom.VerificationConditions p₂ d₂⊢ d₂.postcondition ↠ q All goals completed! 🐙 b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhvc:(p ↠ body.postcondition) ∧ ({{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPre) ∧ ({{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ q) ∧ DCom.VerificationConditions bodyPre body⊢ ValidHoareTriple p (imp {while (b) {~body.erase} }) q b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ ValidHoareTriple p (imp {while (b) {~body.erase} }) q b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ {{?whileDo.P'}} while (b) {~body.erase} {{?whileDo.Q'}}b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ p ↠ ?whileDo.P'b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ ?whileDo.Q' ↠ qb:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ Assertionb:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ Assertion b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ {{?whileDo.P'}} while (b) {~body.erase} {{?whileDo.Q'}} b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ {{?whileDo.P' ∧ b}} ~body.erase {{?whileDo.P'}} b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ {{?whileDo.htriple.P'}} ~body.erase {{?whileDo.P'}}b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ {{?whileDo.P' ∧ b}} ↠ ?whileDo.htriple.P'b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ Assertion b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ {{?whileDo.htriple.P'}} ~body.erase {{?whileDo.P'}} b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ DCom.VerificationConditions ({{?whileDo.htriple.P'}}) body; All goals completed! 🐙 b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ {{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPre All goals completed! 🐙 b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ p ↠ body.postcondition All goals completed! 🐙 b:BexpbodyPre:Assertionbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhpre:p ↠ body.postconditionhbody:{{fun st => body.postcondition st ∧ Bexp.eval st b = true}} ↠ bodyPrehpost:{{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ qhd:DCom.VerificationConditions bodyPre body⊢ {{fun st => body.postcondition st ∧ ¬Bexp.eval st b = true}} ↠ q All goals completed! 🐙 p':Assertionbody:DComih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhvc:(p ↠ p') ∧ DCom.VerificationConditions p' body⊢ ValidHoareTriple p body.erase body.postcondition p':Assertionbody:DComih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhp:p ↠ p'hd:DCom.VerificationConditions p' body⊢ ValidHoareTriple p body.erase body.postcondition p':Assertionbody:DComih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhp:p ↠ p'hd:DCom.VerificationConditions p' body⊢ {{?pre.P'}} ~body.erase {{fun st => body.postcondition st}}p':Assertionbody:DComih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhp:p ↠ p'hd:DCom.VerificationConditions p' body⊢ p ↠ ?pre.P'p':Assertionbody:DComih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhp:p ↠ p'hd:DCom.VerificationConditions p' body⊢ Assertion p':Assertionbody:DComih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhp:p ↠ p'hd:DCom.VerificationConditions p' body⊢ {{?pre.P'}} ~body.erase {{fun st => body.postcondition st}} p':Assertionbody:DComih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhp:p ↠ p'hd:DCom.VerificationConditions p' body⊢ DCom.VerificationConditions ({{?pre.P'}}) body; All goals completed! 🐙 p':Assertionbody:DComih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhp:p ↠ p'hd:DCom.VerificationConditions p' body⊢ p ↠ p' All goals completed! 🐙 body:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhvc:DCom.VerificationConditions p body ∧ (body.postcondition ↠ q)⊢ ValidHoareTriple p body.erase q body:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhd:DCom.VerificationConditions p bodyhq:body.postcondition ↠ q⊢ ValidHoareTriple p body.erase q body:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhd:DCom.VerificationConditions p bodyhq:body.postcondition ↠ q⊢ {{p}} ~body.erase {{?post.Q'}}body:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhd:DCom.VerificationConditions p bodyhq:body.postcondition ↠ q⊢ ?post.Q' ↠ qbody:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhd:DCom.VerificationConditions p bodyhq:body.postcondition ↠ q⊢ Assertion body:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhd:DCom.VerificationConditions p bodyhq:body.postcondition ↠ q⊢ {{p}} ~body.erase {{?post.Q'}} body:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhd:DCom.VerificationConditions p bodyhq:body.postcondition ↠ q⊢ DCom.VerificationConditions ({{p}}) body; All goals completed! 🐙 body:DComq:Assertionih:∀ (p : Assertion), DCom.VerificationConditions p body → ValidHoareTriple p body.erase body.postconditionp:Assertionhd:DCom.VerificationConditions p bodyhq:body.postcondition ↠ q⊢ body.postcondition ↠ q All goals completed! 🐙

Now that all the pieces are in place, we can define what it means to verify an entire program.

@[simp] def Decorated.VerificationConditions (dec : Decorated) : Prop := dec.body.VerificationConditions dec.pre

And this brings us to the main theorem of this section:

theorem verification_conditions_correct (dec : Decorated) (hvc : dec.VerificationConditions) : dec.OuterTripleValid := dec:Decoratedhvc:dec.VerificationConditions⊢ dec.OuterTripleValid All goals completed! 🐙

6.2.3. More Automation🔗

The propositions generated by DCom.VerificationConditions are fairly big and contain many conjuncts that are essentially trivial.

example : decWhile.VerificationConditions := unsolved goals ⊢ (({{True}} ↠ {{True}}) ∧ ({{True ∧ bexp {X ≠ 0} }} ↠ {{True ∧ ¬X = 0}}) ∧ ({{True ∧ ¬bexp {X ≠ 0} }} ↠ {{True ∧ X = 0}}) ∧ ({{True ∧ ¬X = 0}} ↠ {{True [X ↦ X - 1]}})) ∧ ({{True ∧ X = 0}} ↠ {{X = 0}})⊢ decWhile.VerificationConditions ⊢ DCom.VerificationConditions { pre := {{True}}, body := dcom { while (X ≠ 0) do {{True ∧ ¬X = 0}} X := X - 1 {{True}} end {{True ∧ X = 0}} ↠ {{X = 0}} } }.pre { pre := {{True}}, body := dcom { while (X ≠ 0) do {{True ∧ ¬X = 0}} X := X - 1 {{True}} end {{True ∧ X = 0}} ↠ {{X = 0}} } }.body ⊢ (({{True}} ↠ {{True}}) ∧ ({{True ∧ bexp {X ≠ 0} }} ↠ {{True ∧ ¬X = 0}}) ∧ ({{True ∧ ¬bexp {X ≠ 0} }} ↠ {{True ∧ X = 0}}) ∧ ({{True ∧ ¬X = 0}} ↠ {{True [X ↦ X - 1]}})) ∧ ({{True ∧ X = 0}} ↠ {{X = 0}})

Fortunately, our verify_assertion tactic can generally take care of most (or sometimes, all) of them.

example : decWhile.VerificationConditions := ⊢ decWhile.VerificationConditions ⊢ { pre := {{True}}, body := dcom { while (X ≠ 0) do {{True ∧ ¬X = 0}} X := X - 1 {{True}} end {{True ∧ X = 0}} ↠ {{X = 0}} } }.VerificationConditions All goals completed! 🐙

We develop another tactic, verify, to automate the overall process of verification. It uses verification_conditions_correct to extract the verification conditions, and the logic of verify_assertion to verify them as much as it can.

We enhance this logic with four low-level simplification lemmas, defined next, to make the process a little smoother. In particular, these lemmas translate the Bexp.eval equations introduced by conditional and loop guards into inequalities on the underlying arithmetic expressions. This makes them visible to lia for further simplification. For these lemmas to have maximum effect, the tactic removes Bexp.eval_le and Bexp.eval_gt, since these could rewrite Bexp.eval expressions in a way that would cause the four simplification lemmas not to match.

theorem Bexp.eval_le_true {st : State} {a₁ a₂ : Aexp} : (Bexp.le a₁ a₂).eval st = true ↔ a₁.eval st ≤ a₂.eval st := st:Statea₁:Aexpa₂:Aexp⊢ eval st (bexp {a₁ ≤ a₂}) = true ↔ Aexp.eval st a₁ ≤ Aexp.eval st a₂ All goals completed! 🐙 theorem Bexp.eval_le_false {st : State} {a₁ a₂ : Aexp} : (Bexp.le a₁ a₂).eval st = false ↔ ¬ a₁.eval st ≤ a₂.eval st := st:Statea₁:Aexpa₂:Aexp⊢ eval st (bexp {a₁ ≤ a₂}) = false ↔ ¬Aexp.eval st a₁ ≤ Aexp.eval st a₂ All goals completed! 🐙 theorem Bexp.eval_gt_true {st : State} {a₁ a₂ : Aexp} : (Bexp.gt a₁ a₂).eval st = true ↔ a₁.eval st > a₂.eval st := st:Statea₁:Aexpa₂:Aexp⊢ eval st (bexp {a₁ > a₂}) = true ↔ Aexp.eval st a₁ > Aexp.eval st a₂ All goals completed! 🐙 theorem Bexp.eval_gt_false {st : State} {a₁ a₂ : Aexp} : (Bexp.gt a₁ a₂).eval st = false ↔ ¬ a₁.eval st > a₂.eval st := st:Statea₁:Aexpa₂:Aexp⊢ eval st (bexp {a₁ > a₂}) = false ↔ ¬Aexp.eval st a₁ > Aexp.eval st a₂ All goals completed! 🐙 macro "verify" : tactic => `(tactic| (apply verification_conditions_correct; simp +decide [-Bexp.eval_le, -Bexp.eval_gt, Bexp.eval_le_true, Bexp.eval_le_false, Bexp.eval_gt_true, Bexp.eval_gt_false, assertImplies_def, assertIff_def, validHoareTriple_def, Assertion.subst_def]; all_goals and_intros; all_goals try lia))

Here's the final, formal proof that decWhile is correct.

theorem dec_while_correct : decWhile.OuterTripleValid := ⊢ decWhile.OuterTripleValid ⊢ { pre := {{True}}, body := dcom { while (X ≠ 0) do {{True ∧ ¬X = 0}} X := X - 1 {{True}} end {{True ∧ X = 0}} ↠ {{X = 0}} } }.OuterTripleValid All goals completed! 🐙

Similarly, here is the formal decorated program for the "swapping by adding and subtracting" example that we saw earlier.

def swapDec (m n : Nat) : Decorated where pre := ({{ X = m ∧ Y = n }}) body := dcom { ↠ {{ (X + Y) - ((X + Y) - Y) = n ∧ (X + Y) - Y = m }} X := X + Y {{ X - (X - Y) = n ∧ X - Y = m }}; Y := X - Y {{ X - Y = n ∧ Y = m }}; X := X - Y {{ X = n ∧ Y = m }} } theorem swap_correct (m n : Nat) : (swapDec m n).OuterTripleValid := m:Natn:Nat⊢ (swapDec m n).OuterTripleValid m:Natn:Nat⊢ { pre := {{X = m ∧ Y = n}}, body := dcom { ↠ {{X + Y - (X + Y - Y) = n ∧ X + Y - Y = m}} X := X + Y {{X - (X - Y) = n ∧ X - Y = m}}; Y := X - Y {{X - Y = n ∧ Y = m}}; X := X - Y {{X = n ∧ Y = m}} } }.OuterTripleValid All goals completed! 🐙

And here is the formal decorated version of the "positive difference" program from earlier:

def positiveDifferenceDec : Decorated where pre := ({{ True }}) body := dcom { if (X ≤ Y) then {{ True ∧ X ≤ Y }} ↠ {{ (Y - X) + X = Y ∨ (Y - X) + Y = X }} Z := Y - X {{ Z + X = Y ∨ Z + Y = X }} else {{ True ∧ ¬ X ≤ Y }} ↠ {{ (X - Y) + X = Y ∨ (X - Y) + Y = X }} Z := X - Y {{ Z + X = Y ∨ Z + Y = X }} end {{ Z + X = Y ∨ Z + Y = X }} } theorem positive_difference_correct : positiveDifferenceDec.OuterTripleValid := ⊢ positiveDifferenceDec.OuterTripleValid ⊢ { pre := {{True}}, body := dcom { if (X ≤ Y) then {{True ∧ X ≤ Y}} ↠ {{Y - X + X = Y ∨ Y - X + Y = X}} Z := Y - X {{Z + X = Y ∨ Z + Y = X}} else {{True ∧ ¬X ≤ Y}} ↠ {{X - Y + X = Y ∨ X - Y + Y = X}} Z := X - Y {{Z + X = Y ∨ Z + Y = X}} end {{Z + X = Y ∨ Z + Y = X}} } }.OuterTripleValid All goals completed! 🐙
Exercise★★(if_minus_plus_correct)

Here is a skeleton of the formal decorated version of the if_minus_plus program that we saw earlier. Replace all occurrences of sorry with appropriate assertions and fill in the proof (which should be just as straightforward as in the examples above).

def ifMinusPlusDec : Decorated where pre := ({{ True }}) body := dcom { if (X ≤ Y) then {{ solution!({{ True ∧ X ≤ Y }}) }} ↠ {{ solution!({{ Y = X + (Y - X) }}) }} Z := Y - X {{ solution!({{ Y = X + Z }}) }} else {{ solution!({{ True ∧ ¬ X ≤ Y }}) }} ↠ {{ solution!({{ X + Z = X + Z }}) }} Y := X + Z {{ solution!({{ Y = X + Z }}) }} end {{ Y = X + Z }} } theorem if_minus_plus_correct : ifMinusPlusDec.OuterTripleValid := ⊢ ifMinusPlusDec.OuterTripleValid solution! ⊢ { pre := {{True}}, body := dcom { if (X ≤ Y) then {{True ∧ X ≤ Y}} ↠ {{Y = X + (Y - X)}} Z := Y - X {{Y = X + Z}} else {{True ∧ ¬X ≤ Y}} ↠ {{True}} Y := X + Z {{Y = X + Z}} end {{Y = X + Z}} } }.OuterTripleValid All goals completed! 🐙
Exercise★★(div_mod_outer_triple_valid) (Optional)

Fill in appropriate assertions for the division program from above.

def divModDec (a b : Nat) : Decorated where pre := ({{ True }}) body := dcom { ↠ {{ solution!({{ b * 0 + a = a }}) }} X := ~(Aexp.num a) {{ solution!({{ b * 0 + X = a }}) }}; Y := 0 {{ solution!({{ b * Y + X = a }}) }}; while (~(Aexp.num b) ≤ X) do {{ solution!({{ b * Y + X = a ∧ b ≤ X }}) }} ↠ {{ solution!({{ b * (Y + 1) + (X - b) = a }}) }} X := X - ~(Aexp.num b) {{ solution!({{ b * (Y + 1) + X = a }}) }}; Y := Y + 1 {{ solution!({{ b * Y + X = a }}) }} end {{ solution!({{ b * Y + X = a ∧ ¬ b ≤ X }}) }} ↠ {{ solution!({{ b * Y + X = a ∧ X < b }}) }} } theorem div_mod_outer_triple_valid (a b : Nat) : (divModDec a b).OuterTripleValid := a:Natb:Nat⊢ (divModDec a b).OuterTripleValid solution! a:Natb:Nat⊢ { pre := {{True}}, body := dcom { ↠ {{b * 0 + a = a}} X := ~(Aexp.num a) {{b * 0 + X = a}}; Y := 0 {{b * Y + X = a}}; while (~(Aexp.num b) ≤ X) do {{b * Y + X = a ∧ b ≤ X}} ↠ {{b * (Y + 1) + (X - b) = a}} X := X - ~(Aexp.num b) {{b * (Y + 1) + X = a}}; Y := Y + 1 {{b * Y + X = a}} end {{b * Y + X = a ∧ ¬b ≤ X}} ↠ {{b * Y + X = a ∧ X < b}} } }.OuterTripleValid All goals completed! 🐙

6.3. Finding Loop Invariants🔗

Once the outermost precondition and postcondition are chosen, the only creative part of a verifying program using Hoare Logic is finding the right loop invariants. The reason this is difficult is the same as the reason that inductive mathematical proofs are:

  • Strengthening a loop invariant means that you have a stronger assumption to work with when trying to establish the postcondition of the loop body, but it also means that the loop body's postcondition is harder to prove.

  • Similarly, strengthening an induction hypothesis means that you have a stronger assumption to work with when trying to complete the induction step of the proof, but it also means that the statement being proved inductively is harder to prove.

This section explains how to approach the challenge of finding loop invariants through a series of examples and exercises.

6.3.1. Example: Slow Subtraction🔗

The following program subtracts the value of X from the value of Y by repeatedly decrementing both X and Y. We want to verify its correctness with respect to the pre- and postconditions shown:

{{ X = m ∧ Y = n }}
  while X ≠ 0 do
    Y := Y - 1;
    X := X - 1
  end
{{ Y = n - m }}

To verify this program, we need to find an invariant Inv for the loop. As a first step we can leave Inv as an unknown and build a skeleton for the proof by applying the rules for local consistency, working from the end of the program to the beginning, as usual, and without doing any thinking at all yet.

This leads to the following skeleton:

(1)    {{ X = m ∧ Y = n }}  ↠                  (a)
(2)    {{ Inv }}
         while X ≠ 0 do
(3)              {{ Inv ∧ X ≠ 0 }}  ↠          (c)
(4)              {{ Inv [X ↦ X-1] [Y ↦ Y-1] }}
           Y := Y - 1;
(5)              {{ Inv [X ↦ X-1] }}
           X := X - 1
(6)              {{ Inv }}
         end
(7)    {{ Inv ∧ ¬ (X ≠ 0) }}  ↠                (b)
(8)    {{ Y = n - m }}

Examining this skeleton, we can see that any valid Inv will have to respect three conditions:

  • (a) it must be weak enough to be implied by the loop's precondition, i.e., (1) must imply (2);

  • (b) it must be strong enough to imply the program's postcondition, i.e., (7) must imply (8);

  • (c) it must be preserved by a single iteration of the loop, assuming that the loop guard also evaluates to true, i.e., (3) must imply (4).

These conditions are actually independent of the particular program and specification we are considering: every loop invariant has to satisfy them.

One way to find a loop invariant that simultaneously satisfies these three conditions is by using an iterative process: start with a "candidate" invariant (e.g., a guess or a heuristic choice) and check the three conditions above; if any of the checks fails, try to use the information that we get from the failure to produce another — hopefully better — candidate invariant, and repeat.

For instance, in the reduce-to-zero example above, we saw that, for a very simple loop, choosing True as a loop invariant did the job. Maybe it will work here too. To find out, let's try instantiating Inv with True in the skeleton above and see what we get...

(1)    {{ X = m ∧ Y = n }} ↠                   (a - OK)
(2)    {{ True }}
         while X ≠ 0 do
(3)                   {{ True ∧ X ≠ 0 }} ↠     (c - OK)
(4)                   {{ True }}
           Y := Y - 1;
(5)                   {{ True }}
           X := X - 1
(6)                   {{ True }}
         end
(7)    {{ True ∧ ¬(X ≠ 0) }} ↠                 (b - WRONG!)
(8)    {{ Y = n - m }}

While conditions (a) and (c) are trivially satisfied, (b) is wrong: it is not the case that True ∧ X = 0 (7) implies Y = n - m (8). In fact, the two assertions are completely unrelated, so it is very easy to find a counterexample to the implication (say, Y = X = m = 0 and n = 1).

If we want (b) to hold, we need to strengthen the loop invariant so that it implies the postcondition (8). One simple way to do this is to let the loop invariant be the postcondition. So let's return to our skeleton, instantiate Inv with Y = n - m, and try checking conditions (a) to (c) again.

(1)    {{ X = m ∧ Y = n }} ↠                       (a - WRONG!)
(2)    {{ Y = n - m }}
         while X ≠ 0 do
(3)                     {{ Y = n - m ∧ X ≠ 0 }} ↠  (c - WRONG!)
(4)                     {{ Y - 1 = n - m }}
           Y := Y - 1;
(5)                     {{ Y = n - m }}
           X := X - 1
(6)                     {{ Y = n - m }}
         end
(7)    {{ Y = n - m ∧ ¬(X ≠ 0) }} ↠                (b - OK)
(8)    {{ Y = n - m }}

This time, condition (b) holds trivially, but (a) and (c) are broken. Condition (a) requires that (1) X = m ∧ Y = n implies (2) Y = n - m. If we substitute Y by n we have to show that n = n - m for arbitrary m and n, which is not the case (for instance, when m = n = 1). Condition (c) requires that n - m - 1 = n - m, which fails, for instance, for n = 1 and m = 0. So, although Y = n - m holds at the end of the loop, it does not hold from the start, and it doesn't hold on each iteration; it is not a correct loop invariant.

This failure is not very surprising: the variable Y changes during the loop, while m and n are constant, so the assertion we chose didn't have much chance of being a loop invariant!

To do better, we need to generalize (7) to some statement that is equivalent to (8) when X is 0, since this will be the case when the loop terminates, and that "fills the gap" in some appropriate way when X is nonzero. Looking at how the loop works, we can observe that X and Y are decremented together until X reaches 0. So, if X = 2 and Y = 5 initially, after one iteration of the loop we obtain X = 1 and Y = 4; after two iterations X = 0 and Y = 3; and then the loop stops. Notice that the difference between Y and X stays constant between iterations: initially, Y = n and X = m, and the difference is always n - m. So let's try instantiating Inv in the skeleton above with Y - X = n - m.

(1)    {{ X = m ∧ Y = n }} ↠                           (a - OK)
(2)    {{ Y - X = n - m }}
         while X ≠ 0 do
(3)                    {{ Y - X = n - m ∧ X ≠ 0 }} ↠   (c - OK)
(4)                    {{ (Y - 1) - (X - 1) = n - m }}
           Y := Y - 1;
(5)                    {{ Y - (X - 1) = n - m }}
           X := X - 1
(6)                    {{ Y - X = n - m }}
         end
(7)    {{ Y - X = n - m ∧ ¬(X ≠ 0) }} ↠                (b - OK)
(8)    {{ Y = n - m }}

Success! Conditions (a), (b) and (c) all hold now. (To verify (c), we need to check that, under the assumption that X ≠ 0, we have Y - X = (Y - 1) - (X - 1); this holds for all natural numbers X and Y.)

Here is the final version of the decorated program:

def subtractSlowlyDec (m n : Nat) : Decorated where pre := ({{ X = m ∧ Y = n }}) body := dcom { ↠ {{ Y - X = n - m }} while (X ≠ 0) do {{ Y - X = n - m ∧ ¬ X = 0 }} ↠ {{ (Y - 1) - (X - 1) = n - m }} Y := Y - 1 {{ Y - (X - 1) = n - m }}; X := X - 1 {{ Y - X = n - m }} end {{ Y - X = n - m ∧ X = 0 }} ↠ {{ Y = n - m }} } theorem subtract_slowly_outer_triple_valid (m n : Nat) : (subtractSlowlyDec m n).OuterTripleValid := m:Natn:Nat⊢ (subtractSlowlyDec m n).OuterTripleValid m:Natn:Nat⊢ { pre := {{X = m ∧ Y = n}}, body := dcom { ↠ {{Y - X = n - m}} while (X ≠ 0) do {{Y - X = n - m ∧ ¬X = 0}} ↠ {{Y - 1 - (X - 1) = n - m}} Y := Y - 1 {{Y - (X - 1) = n - m}}; X := X - 1 {{Y - X = n - m}} end {{Y - X = n - m ∧ X = 0}} ↠ {{Y = n - m}} } }.OuterTripleValid All goals completed! 🐙

6.3.2. Exercise: Slow Assignment🔗

Exercise★★(slow_assignment)

A roundabout way of assigning a number currently stored in X to the variable Y is to start Y at 0, then decrement X until it hits 0, incrementing Y at each step. Here is a program that implements this idea. Fill in decorations and prove the decorated program correct. (The proof should be very simple.)

def slowAssignmentDec (m : Nat) : Decorated where pre := ({{ X = m }}) body := dcom { Y := 0 {{ solution!({{ X = m ∧ Y = 0 }}) }}; (↠ {{ solution!({{ Y + X = m }}) }} while (X ≠ 0) do {{ solution!({{ Y + X = m ∧ ¬ X = 0 }}) }} ↠ {{ solution!({{ Y + (X - 1) + 1 = m }}) }} X := X - 1 {{ solution!({{ Y + X + 1 = m }}) }}; (↠ {{ solution!({{ Y + X + 1 = m }}) }} Y := Y + 1 {{ solution!({{ Y + X = m }}) }}) end {{ solution!({{ Y + X = m ∧ X = 0 }}) }} ↠ {{ Y = m }}) } theorem slow_assignment (m : Nat) : (slowAssignmentDec m).OuterTripleValid := m:Nat⊢ (slowAssignmentDec m).OuterTripleValid solution! m:Nat⊢ { pre := {{X = m}}, body := dcom { Y := 0 {{X = m ∧ Y = 0}}; (↠ {{Y + X = m}} while (X ≠ 0) do {{Y + X = m ∧ ¬X = 0}} ↠ {{Y + (X - 1) + 1 = m}} X := X - 1 {{Y + X + 1 = m}}; (↠ {{Y + X + 1 = m}} Y := Y + 1 {{Y + X = m}}) end {{Y + X = m ∧ X = 0}} ↠ {{Y = m}}) } }.OuterTripleValid All goals completed! 🐙

6.3.3. Example: Parity🔗

Here is a cute way of computing the parity of a value initially stored in X, due to Daniel Cristofani.

{{ X = m }}
  while 2 ≤ X do
    X := X - 2
  end
{{ X = parity m }}

The parity function used in the specification is defined in Lean as follows:

def parity : Nat → Nat | 0 => 0 | 1 => 1 | Nat.succ (Nat.succ n) => parity n

The postcondition does not hold at the beginning of the loop, since m = parity m does not hold for an arbitrary m, so we cannot hope to use that as a loop invariant. To find a loop invariant that works, let's think a bit about what this loop does. On each iteration it decrements X by 2, which preserves the parity of X. So the parity of X does not change, i.e., it is invariant. The initial value of X is m, so the parity of X is always equal to the parity of m. Using parity X = parity m as an invariant we obtain the following decorated program:

{{ X = m }} ↠                                       (a - OK)
{{ parity X = parity m }}
  while 2 ≤ X do
               {{ parity X = parity m ∧ 2 ≤ X }} ↠  (c - OK)
               {{ parity (X-2) = parity m }}
    X := X - 2
               {{ parity X = parity m }}
  end
{{ parity X = parity m ∧ ¬(2 ≤ X) }} ↠              (b - OK)
{{ X = parity m }}

With this loop invariant, conditions (a), (b), and (c) are all satisfied. For verifying (b), we observe that, when X < 2, we have parity X = X (we can easily see this in the definition of parity). For verifying (c), we observe that, when 2 ≤ X, we have parity X = parity (X-2).

Note to developers
HIDE: A more complexly phrased loop invariant for the same program
[[
        {{ X = m }} ↠                       (a - OK)
        {{ ev X <-> ev m }}
      while 2 ≤ X do
          {{ ev X <-> ev m ∧ 2 ≤ X }} ↠     (c - OK)
          {{ ev (X-2) <-> ev m }}
        X := X - 2
          {{ ev X <-> ev m }}
      end
        {{ (ev X <-> ev m) ∧ ~(2 ≤ X) }} ↠  (b - OK)
        {{ X=0 <-> ev m }}
]]
HIDE: find_parity'_dec; more complicated phrasing of invariant
there is very little resemblance between the invariant and the
postcondition -- the implication is also non-obvious, and the
X ≤ m condition makes the invariant more complicated
[[
 {{ X = m }} ↠
 {{ X ≤ m ∧ ev (m - X) }}
while 2 ≤ X do
   {{ X ≤ m ∧ ev (m - X) ∧ 2 ≤ X }} ↠
   {{ X - 2 ≤ m ∧ ev (m - (X - 2)) }}
 X := X - 2
   {{ X ≤ m ∧ ev (m - X) }}
end
 {{ X ≤ m ∧ ev (m - X) ∧ ~(2 ≤ X) }} ↠
 {{ X=0 <-> ev m }}
]]
Exercise★★★(parity) (Optional)

Translate the above informal decorated program into a formal one and prove it correct.

Hint: There are actually several possible loop invariants that all lead to good proofs; one that leads to a particularly simple proof is parity X = parity m. Ordinary Lean functions can be applied directly to Imp variables inside assertions, so this can be written as {{ parity X = parity m }}.

def parityDec (m : Nat) : Decorated where pre := ({{ X = m }}) body := let inv : Assertion := solution!(fun st => parity st[X] = parity m) let guardedInv : Assertion := solution!(fun st => parity st[X] = parity m ∧ 2 ≤ st[X]) let bodyPre : Assertion := solution!(fun st => parity (st[X] - 2) = parity m) let exit : Assertion := solution!(fun st => parity st[X] = parity m ∧ ¬ 2 ≤ st[X]) let post : Assertion := fun st => st[X] = parity m dcom { ↠ {{ inv }} while (2 ≤ X) do {{ guardedInv }} ↠ {{ bodyPre }} X := X - 2 {{ inv }} end {{ exit }} ↠ {{ post }} }

If you use the suggested loop invariant, you may find the following two lemmas helpful.

theorem parity_ge_2 (x : Nat) (h : 2 ≤ x) : parity (x - 2) = parity x := x:Nath:2 ≤ x⊢ parity (x - 2) = parity x cases x with h:2 ≤ 0⊢ parity (0 - 2) = parity 0 All goals completed! 🐙 x:Nath:2 ≤ x + 1⊢ parity (x + 1 - 2) = parity (x + 1) cases x with h:2 ≤ 0 + 1⊢ parity (0 + 1 - 2) = parity (0 + 1) All goals completed! 🐙 x:Nath:2 ≤ x + 1 + 1⊢ parity (x + 1 + 1 - 2) = parity (x + 1 + 1) -- Both sides compute to `parity x`. All goals completed! 🐙 theorem parity_lt_2 (x : Nat) (h : ¬ 2 ≤ x) : parity x = x := x:Nath:¬2 ≤ x⊢ parity x = x cases x with h:¬2 ≤ 0⊢ parity 0 = 0 All goals completed! 🐙 x:Nath:¬2 ≤ x + 1⊢ parity (x + 1) = x + 1 cases x with h:¬2 ≤ 0 + 1⊢ parity (0 + 1) = 0 + 1 All goals completed! 🐙 x:Nath:¬2 ≤ x + 1 + 1⊢ parity (x + 1 + 1) = x + 1 + 1 All goals completed! 🐙 theorem parity_outer_triple_valid (m : Nat) : (parityDec m).OuterTripleValid := m:Nat⊢ (parityDec m).OuterTripleValid solution! m:Nat⊢ { pre := {{X = m}}, body := dcom { ↠ {{parity X = parity m}} while (2 ≤ X) do {{parity X = parity m ∧ 2 ≤ X}} ↠ {{parity (X - 2) = parity m}} X := X - 2 {{parity X = parity m}} end {{parity X = parity m ∧ ¬2 ≤ X}} ↠ {{X = parity m}} } }.OuterTripleValid m:Nat⊢ ∀ (st : State), parity st[X] = parity m → 2 ≤ st[X] → parity (st[X] - 2) = parity mm:Nat⊢ ∀ (st : State), parity st[X] = parity m → st[X] < 2 → st[X] = parity m m:Nat⊢ ∀ (st : State), parity st[X] = parity m → 2 ≤ st[X] → parity (st[X] - 2) = parity m -- loop invariant preserved m:Natst:Stateh:parity st[X] = parity mhle:2 ≤ st[X]⊢ parity (st[X] - 2) = parity m m:Natst:Stateh:parity st[X] = parity mhle:2 ≤ st[X]⊢ parity (st[X] - 2) = parity st[X] m:Natst:Stateh:parity st[X] = parity mhle:2 ≤ st[X]⊢ 2 ≤ st[X] All goals completed! 🐙 m:Nat⊢ ∀ (st : State), parity st[X] = parity m → st[X] < 2 → st[X] = parity m -- loop invariant strong enough m:Natst:Stateh:parity st[X] = parity mhlt:st[X] < 2⊢ st[X] = parity m m:Natst:Stateh:parity st[X] = parity mhlt:st[X] < 2⊢ st[X] = parity st[X] m:Natst:Stateh:parity st[X] = parity mhlt:st[X] < 2⊢ parity st[X] = st[X] m:Natst:Stateh:parity st[X] = parity mhlt:st[X] < 2⊢ ¬2 ≤ st[X] All goals completed! 🐙 /- Here is another loop invariant — arguably a more natural one — which sadly leads to a rather long proof. -/ inductive Even : Nat → Prop where | zero : Even 0 | addTwo {n : Nat} : Even n → Even (Nat.succ (Nat.succ n)) def findParityDec (m : Nat) : Decorated where pre := ({{ X = m }}) body := let inv : Assertion := fun st => st[X] ≤ m ∧ Even (m - st[X]) let guardedInv : Assertion := fun st => (st[X] ≤ m ∧ Even (m - st[X])) ∧ 2 ≤ st[X] let bodyPre : Assertion := fun st => st[X] - 2 ≤ m ∧ Even (m - (st[X] - 2)) let exit : Assertion := fun st => (st[X] ≤ m ∧ Even (m - st[X])) ∧ st[X] < 2 let post : Assertion := fun st => st[X] = 0 ↔ Even m dcom { ↠ {{ inv }} while (2 ≤ X) do {{ guardedInv }} ↠ {{ bodyPre }} X := X - 2 {{ inv }} end {{ exit }} ↠ {{ post }} } -- The proof will want a few useful (but not terribly interesting) -- helper lemmas: theorem l1 (m n p : Nat) (h₁ : p ≤ n) (h₂ : n ≤ m) : m - (n - p) = m - n + p := m:Natn:Natp:Nath₁:p ≤ nh₂:n ≤ m⊢ m - (n - p) = m - n + p All goals completed! 🐙 theorem l2 (m : Nat) (h : Even m) : Even (m + 2) := m:Nath:Even m⊢ Even (m + 2) m:Nath:Even m⊢ Even m All goals completed! 🐙 theorem Even.not_add_one {n : Nat} (h : Even n) : ¬ Even (n + 1) := n:Nath:Even n⊢ ¬Even (n + 1) induction n with h:Even 0⊢ ¬Even (0 + 1) h:Even 0h₂:Even (0 + 1)⊢ False All goals completed! 🐙 n:Natih:Even n → ¬Even (n + 1)h:Even (n + 1)⊢ ¬Even (n + 1 + 1) n:Natih:Even n → ¬Even (n + 1)h:Even (n + 1)h₂:Even (n + 1 + 1)⊢ False n:Natih:Even n → ¬Even (n + 1)h:Even (n + 1)h₂:Even (n + 1 + 1)⊢ Even nn:Natih:Even n → ¬Even (n + 1)h:Even (n + 1)h₂:Even (n + 1 + 1)⊢ Even (n + 1) n:Natih:Even n → ¬Even (n + 1)h:Even (n + 1)h₂:Even (n + 1 + 1)⊢ Even n inversion h₂ with n:Natih:Even n → ¬Even (n + 1)h:Even (n + 1)h':Even n⊢ Even n All goals completed! 🐙 n:Natih:Even n → ¬Even (n + 1)h:Even (n + 1)h₂:Even (n + 1 + 1)⊢ Even (n + 1) All goals completed! 🐙 theorem l3 (m : Nat) (h : 1 ≤ m) (h₁ : Even m) (h₂ : Even (m - 1)) : False := m:Nath:1 ≤ mh₁:Even mh₂:Even (m - 1)⊢ False m:Nath:1 ≤ mh₁:Even mh₂:Even (m - 1 + 2)⊢ False m:Nath:1 ≤ mh₁:Even mh₂:Even (m - 1 + 2)g:m - 1 + 2 = m + 1⊢ False m:Nath:1 ≤ mh₁:Even mh₂:Even (m + 1)g:m - 1 + 2 = m + 1⊢ False m:Nath:1 ≤ mh₂:Even (m + 1)g:m - 1 + 2 = m + 1h₁:¬Even (m + 1)⊢ False m:Nath:1 ≤ mh₂:Even (m + 1)g:m - 1 + 2 = m + 1h₁:¬Even (m + 1)⊢ Even (m + 1) All goals completed! 🐙 theorem find_parity_correct (m : Nat) : (findParityDec m).OuterTripleValid := m:Nat⊢ (findParityDec m).OuterTripleValid m:Nat⊢ { pre := {{X = m}}, body := dcom { ↠ {{X ≤ m ∧ Even (m - X)}} while (2 ≤ X) do {{(X ≤ m ∧ Even (m - X)) ∧ 2 ≤ X}} ↠ {{X - 2 ≤ m ∧ Even (m - (X - 2))}} X := X - 2 {{X ≤ m ∧ Even (m - X)}} end {{(X ≤ m ∧ Even (m - X)) ∧ X < 2}} ↠ {{X = 0 ↔ Even m}} } }.OuterTripleValid m:Nat⊢ ∀ (st : State), st[X] = m → st[X] ≤ m ∧ Even (m - st[X])m:Nat⊢ ∀ (st : State), st[X] ≤ m → Even (m - st[X]) → 2 ≤ st[X] → st[X] ≤ m + 2 ∧ Even (m - (st[X] - 2))m:Nat⊢ ∀ (st : State), st[X] ≤ m → Even (m - st[X]) → st[X] < 2 → (st[X] = 0 ↔ Even m) m:Nat⊢ ∀ (st : State), st[X] = m → st[X] ≤ m ∧ Even (m - st[X]) -- loop invariant holds initially m:Natst:Stateh:st[X] = m⊢ st[X] ≤ m ∧ Even (m - st[X]) m:Natst:Stateh:st[X] = m⊢ m ≤ m ∧ Even 0 m:Natst:Stateh:st[X] = m⊢ m ≤ mm:Natst:Stateh:st[X] = m⊢ Even 0 m:Natst:Stateh:st[X] = m⊢ m ≤ m All goals completed! 🐙 m:Natst:Stateh:st[X] = m⊢ Even 0 All goals completed! 🐙 m:Nat⊢ ∀ (st : State), st[X] ≤ m → Even (m - st[X]) → 2 ≤ st[X] → st[X] ≤ m + 2 ∧ Even (m - (st[X] - 2)) -- loop invariant preserved m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ st[X] ≤ m + 2 ∧ Even (m - (st[X] - 2)) m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ st[X] ≤ m + 2m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ Even (m - (st[X] - 2)) m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ st[X] ≤ m + 2 All goals completed! 🐙 m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ Even (m - (st[X] - 2)) m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ Even (m - st[X] + 2)m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ 2 ≤ st[X]m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ st[X] ≤ m m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ Even (m - st[X] + 2) m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ Even (m - st[X]) All goals completed! 🐙 m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ 2 ≤ st[X] All goals completed! 🐙 m:Natst:Statehle:st[X] ≤ mheven:Even (m - st[X])hge:2 ≤ st[X]⊢ st[X] ≤ m All goals completed! 🐙 m:Nat⊢ ∀ (st : State), st[X] ≤ m → Even (m - st[X]) → st[X] < 2 → (st[X] = 0 ↔ Even m) m:Natst:State⊢ st[X] ≤ m → Even (m - st[X]) → st[X] < 2 → (st[X] = 0 ↔ Even m) m:Natst:Statex:Nat⊢ x ≤ m → Even (m - x) → x < 2 → (x = 0 ↔ Even m) m:Natst:Statex:Nathle:x ≤ mheven:Even (m - x)hlt:x < 2⊢ x = 0 ↔ Even m m:Natst:Statex:Nathle:x ≤ mheven:Even (m - x)hlt:x < 2⊢ x = 0 → Even mm:Natst:Statex:Nathle:x ≤ mheven:Even (m - x)hlt:x < 2⊢ Even m → x = 0 m:Natst:Statex:Nathle:x ≤ mheven:Even (m - x)hlt:x < 2⊢ x = 0 → Even m -- loop invariant strong enough to imply conclusion -- (→ direction) m:Natst:Statex:Nathle:x ≤ mheven:Even (m - x)hlt:x < 2hx:x = 0⊢ Even m m:Natst:Statex:Nathle:x ≤ mheven:Even mhlt:x < 2hx:x = 0⊢ Even m All goals completed! 🐙 m:Natst:Statex:Nathle:x ≤ mheven:Even (m - x)hlt:x < 2⊢ Even m → x = 0 -- loop invariant strong enough to imply conclusion -- (← direction) m:Natst:Statex:Nathle:x ≤ mheven:Even (m - x)hlt:x < 2hm:Even m⊢ x = 0 -- At loop exit, X can only be 0 or 1. cases x with m:Natst:Statehm:Even mhle:0 ≤ mheven:Even (m - 0)hlt:0 < 2⊢ 0 = 0 All goals completed! 🐙 m:Natst:Statehm:Even mx:Nathle:x + 1 ≤ mheven:Even (m - (x + 1))hlt:x + 1 < 2⊢ x + 1 = 0 cases x with m:Natst:Statehm:Even mhle:0 + 1 ≤ mheven:Even (m - (0 + 1))hlt:0 + 1 < 2⊢ 0 + 1 = 0 m:Natst:Statehm:Even mhle:0 + 1 ≤ mheven:Even (m - (0 + 1))hlt:0 + 1 < 2⊢ False m:Natst:Statehm:Even mhle:0 + 1 ≤ mheven:Even (m - (0 + 1))hlt:0 + 1 < 2⊢ 1 ≤ mm:Natst:Statehm:Even mhle:0 + 1 ≤ mheven:Even (m - (0 + 1))hlt:0 + 1 < 2⊢ Even mm:Natst:Statehm:Even mhle:0 + 1 ≤ mheven:Even (m - (0 + 1))hlt:0 + 1 < 2⊢ Even (m - 1) m:Natst:Statehm:Even mhle:0 + 1 ≤ mheven:Even (m - (0 + 1))hlt:0 + 1 < 2⊢ 1 ≤ m All goals completed! 🐙 m:Natst:Statehm:Even mhle:0 + 1 ≤ mheven:Even (m - (0 + 1))hlt:0 + 1 < 2⊢ Even m All goals completed! 🐙 m:Natst:Statehm:Even mhle:0 + 1 ≤ mheven:Even (m - (0 + 1))hlt:0 + 1 < 2⊢ Even (m - 1) All goals completed! 🐙 m:Natst:Statehm:Even mx:Nathle:x + 1 + 1 ≤ mheven:Even (m - (x + 1 + 1))hlt:x + 1 + 1 < 2⊢ x + 1 + 1 = 0 All goals completed! 🐙 /- Here is a more intuitive way of writing the loop invariant. -/ def findParityDec' (m : Nat) : Decorated where pre := ({{ X = m }}) body := let inv : Assertion := fun st => Even st[X] ↔ Even m let guardedInv : Assertion := fun st => (Even st[X] ↔ Even m) ∧ 2 ≤ st[X] let bodyPre : Assertion := fun st => Even (st[X] - 2) ↔ Even m let exit : Assertion := fun st => (Even st[X] ↔ Even m) ∧ ¬ 2 ≤ st[X] let post : Assertion := fun st => st[X] = 0 ↔ Even m dcom { ↠ {{ inv }} while (2 ≤ X) do {{ guardedInv }} ↠ {{ bodyPre }} X := X - 2 {{ inv }} end {{ exit }} ↠ {{ post }} } theorem Even.sub_two_iff {n : Nat} (h : 2 ≤ n) : Even (n - 2) ↔ Even n := n:Nath:2 ≤ n⊢ Even (n - 2) ↔ Even n cases n with h:2 ≤ 0⊢ Even (0 - 2) ↔ Even 0 h:2 ≤ 0⊢ Even (0 - 2) → Even 0h:2 ≤ 0⊢ Even 0 → Even (0 - 2) h:2 ≤ 0⊢ Even (0 - 2) → Even 0 h:2 ≤ 0a✝:Even (0 - 2)⊢ Even 0 All goals completed! 🐙 h:2 ≤ 0⊢ Even 0 → Even (0 - 2) h:2 ≤ 0a✝:Even 0⊢ Even (0 - 2) All goals completed! 🐙 n:Nath:2 ≤ n + 1⊢ Even (n + 1 - 2) ↔ Even (n + 1) cases n with h:2 ≤ 0 + 1⊢ Even (0 + 1 - 2) ↔ Even (0 + 1) h:2 ≤ 0 + 1⊢ False All goals completed! 🐙 n:Nath:2 ≤ n + 1 + 1⊢ Even (n + 1 + 1 - 2) ↔ Even (n + 1 + 1) n:Nath:2 ≤ n + 1 + 1⊢ Even n ↔ Even (n + 1 + 1) n:Nath:2 ≤ n + 1 + 1⊢ Even n → Even (n + 1 + 1)n:Nath:2 ≤ n + 1 + 1⊢ Even (n + 1 + 1) → Even n n:Nath:2 ≤ n + 1 + 1⊢ Even n → Even (n + 1 + 1) n:Nath:2 ≤ n + 1 + 1h':Even n⊢ Even (n + 1 + 1) n:Nath:2 ≤ n + 1 + 1h':Even n⊢ Even n All goals completed! 🐙 n:Nath:2 ≤ n + 1 + 1⊢ Even (n + 1 + 1) → Even n n:Nath:2 ≤ n + 1 + 1h':Even (n + 1 + 1)⊢ Even n inversion h' with n:Nath:2 ≤ n + 1 + 1h'':Even n⊢ Even n All goals completed! 🐙 theorem find_parity_correct' (m : Nat) : (findParityDec' m).OuterTripleValid := m:Nat⊢ (findParityDec' m).OuterTripleValid m:Nat⊢ { pre := {{X = m}}, body := dcom { ↠ {{Even X ↔ Even m}} while (2 ≤ X) do {{(Even X ↔ Even m) ∧ 2 ≤ X}} ↠ {{Even (X - 2) ↔ Even m}} X := X - 2 {{Even X ↔ Even m}} end {{(Even X ↔ Even m) ∧ ¬2 ≤ X}} ↠ {{X = 0 ↔ Even m}} } }.OuterTripleValid m:Nat⊢ ∀ (st : State), (Even st[X] ↔ Even m) → 2 ≤ st[X] → (Even (st[X] - 2) ↔ Even m)m:Nat⊢ ∀ (st : State), (Even st[X] ↔ Even m) → st[X] < 2 → (st[X] = 0 ↔ Even m) m:Nat⊢ ∀ (st : State), (Even st[X] ↔ Even m) → 2 ≤ st[X] → (Even (st[X] - 2) ↔ Even m) -- loop invariant preserved m:Natst:Stateh:Even st[X] ↔ Even mhle:2 ≤ st[X]⊢ Even (st[X] - 2) ↔ Even m m:Natst:Stateh:Even st[X] ↔ Even mhle:2 ≤ st[X]⊢ Even st[X] ↔ Even mm:Natst:Stateh:Even st[X] ↔ Even mhle:2 ≤ st[X]⊢ 2 ≤ st[X] m:Natst:Stateh:Even st[X] ↔ Even mhle:2 ≤ st[X]⊢ Even st[X] ↔ Even m All goals completed! 🐙 m:Natst:Stateh:Even st[X] ↔ Even mhle:2 ≤ st[X]⊢ 2 ≤ st[X] All goals completed! 🐙 m:Nat⊢ ∀ (st : State), (Even st[X] ↔ Even m) → st[X] < 2 → (st[X] = 0 ↔ Even m) m:Natst:State⊢ (Even st[X] ↔ Even m) → st[X] < 2 → (st[X] = 0 ↔ Even m) m:Natst:Statex:Nat⊢ (Even x ↔ Even m) → x < 2 → (x = 0 ↔ Even m) m:Natst:Statex:Nath:Even x ↔ Even mhlt:x < 2⊢ x = 0 ↔ Even m m:Natst:Statex:Nath:Even x ↔ Even mhlt:x < 2⊢ x = 0 → Even mm:Natst:Statex:Nath:Even x ↔ Even mhlt:x < 2⊢ Even m → x = 0 m:Natst:Statex:Nath:Even x ↔ Even mhlt:x < 2⊢ x = 0 → Even m -- loop invariant strong enough to imply conclusion -- (→ direction) m:Natst:Statex:Nath:Even x ↔ Even mhlt:x < 2hx:x = 0⊢ Even m m:Natst:Statex:Nath:Even 0 ↔ Even mhlt:x < 2hx:x = 0⊢ Even m m:Natst:Statex:Nath:Even 0 ↔ Even mhlt:x < 2hx:x = 0⊢ Even 0 All goals completed! 🐙 m:Natst:Statex:Nath:Even x ↔ Even mhlt:x < 2⊢ Even m → x = 0 -- loop invariant strong enough to imply conclusion -- (← direction) m:Natst:Statex:Nath:Even x ↔ Even mhlt:x < 2hm:Even m⊢ x = 0 -- At loop exit, X can only be 0 or 1. cases x with m:Natst:Statehm:Even mh:Even 0 ↔ Even mhlt:0 < 2⊢ 0 = 0 All goals completed! 🐙 m:Natst:Statehm:Even mx:Nath:Even (x + 1) ↔ Even mhlt:x + 1 < 2⊢ x + 1 = 0 cases x with m:Natst:Statehm:Even mh:Even (0 + 1) ↔ Even mhlt:0 + 1 < 2⊢ 0 + 1 = 0 m:Natst:Stateh:Even (0 + 1) ↔ Even mhlt:0 + 1 < 2hm:Even (0 + 1)⊢ 0 + 1 = 0 All goals completed! 🐙 m:Natst:Statehm:Even mx:Nath:Even (x + 1 + 1) ↔ Even mhlt:x + 1 + 1 < 2⊢ x + 1 + 1 = 0 All goals completed! 🐙 /- Finally, just for fun, here is an old-style non-decorated-program proof. -/ theorem parity_correct (m : Nat) : {{ X = m }} while (2 ≤ X) { X := X - 2 } {{ fun st => st[X] = parity m }} := m:Nat⊢ {{X = m}} while (2 ≤ X) {X := X - 2} {{X = parity m}} m:Nat⊢ {{?P'}} while (2 ≤ X) {X := X - 2} {{?Q'}}m:Nat⊢ {{X = m}} ↠ ?P'm:Nat⊢ ?Q' ↠ {{X = parity m}}m:Nat⊢ Assertionm:Nat⊢ Assertion m:Nat⊢ {{?P'}} while (2 ≤ X) {X := X - 2} {{?Q'}} -- loop invariant preserved by loop m:Nat⊢ {{parity X = parity m ∧ bexp {2 ≤ X} }} X := X - 2 {{parity X = parity m}} m:Nat⊢ {{?htriple.P'}} X := X - 2 {{parity X = parity m}}m:Nat⊢ {{parity X = parity m ∧ bexp {2 ≤ X} }} ↠ ?htriple.P'm:Nat⊢ Assertion m:Nat⊢ {{?htriple.P'}} X := X - 2 {{parity X = parity m}} All goals completed! 🐙 m:Nat⊢ {{parity X = parity m ∧ bexp {2 ≤ X} }} ↠ (parity X = parity m) [X ↦ X - 2] m:Nat⊢ ∀ (st : State), parity st[X] = parity m → 2 ≤ st["X"] → parity (st["X"] - 2) = parity m m:Natst:Stateh:parity st[X] = parity mhle:2 ≤ st["X"]⊢ parity (st["X"] - 2) = parity m m:Natst:Stateh:parity st[X] = parity mhle:2 ≤ st["X"]⊢ parity (st["X"] - 2) = parity st[X] m:Natst:Stateh:parity st[X] = parity mhle:2 ≤ st["X"]⊢ 2 ≤ st["X"] All goals completed! 🐙 m:Nat⊢ {{X = m}} ↠ {{parity X = parity m}} -- loop invariant holds initially m:Nat⊢ ∀ (st : State), st[X] = m → parity st[X] = parity m m:Natst:Stateh:st[X] = m⊢ parity st[X] = parity m All goals completed! 🐙 m:Nat⊢ {{parity X = parity m ∧ ¬bexp {2 ≤ X} }} ↠ {{X = parity m}} -- loop invariant holds at the end m:Nat⊢ ∀ (st : State), parity st[X] = parity m → st["X"] < 2 → st[X] = parity m m:Natst:Stateh:parity st[X] = parity mhlt:st["X"] < 2⊢ st[X] = parity m m:Natst:Stateh:parity st[X] = parity mhlt:st["X"] < 2⊢ st[X] = parity st[X] m:Natst:Stateh:parity st[X] = parity mhlt:st["X"] < 2⊢ parity st[X] = st[X] m:Natst:Stateh:parity st[X] = parity mhlt:st["X"] < 2⊢ ¬2 ≤ st[X] All goals completed! 🐙

6.3.4. Example: Finding Square Roots🔗

The following program computes the integer square root of X by naive iteration:

{{ X=m }}
  Z := 0;
  while (Z+1)*(Z+1) ≤ X do
    Z := Z+1
  end
{{ Z*Z≤m ∧ m<(Z+1)*(Z+1) }}

As we did before, we can try to use the postcondition as a candidate loop invariant, obtaining the following decorated program:

(1)  {{ X=m }} ↠                (a - second conjunct of (2) WRONG!)
(2)  {{ 0*0 ≤ m ∧ m<(0+1)*(0+1) }}
        Z := 0
(3)            {{ Z*Z ≤ m ∧ m<(Z+1)*(Z+1) }};
        while (Z+1)*(Z+1) ≤ X do
(4)            {{ Z*Z≤m ∧ m<(Z+1)*(Z+1)
                         ∧ (Z+1)*(Z+1)≤X }} ↠          (c - WRONG!)
(5)            {{ (Z+1)*(Z+1)≤m ∧ m<((Z+1)+1)*((Z+1)+1) }}
          Z := Z+1
(6)            {{ Z*Z≤m ∧ m<(Z+1)*(Z+1) }}
        end
(7)  {{ Z*Z≤m ∧ m<(Z+1)*(Z+1) ∧ ¬((Z+1)*(Z+1)≤X) }} ↠      (b - OK)
(8)  {{ Z*Z≤m ∧ m<(Z+1)*(Z+1) }}

This didn't work very well: conditions (a) and (c) both failed. Looking at condition (c), we see that the second conjunct of (4) is almost the same as the first conjunct of (5), except that (4) mentions X while (5) mentions m. But note that X is never assigned in this program, so we should always have X=m. We didn't propagate this information from (1) into the loop invariant, but we could!

Also, we don't need the second conjunct of (8), since we can obtain it from the negation of the guard — the third conjunct in (7) — again under the assumption that X=m. This allows us to simplify a bit.

So we now try X=m ∧ Z*Z ≤ m as the loop invariant:

{{ X=m }} ↠                                       (a - OK)
{{ X=m ∧ 0*0 ≤ m }}
  Z := 0
             {{ X=m ∧ Z*Z ≤ m }};
  while (Z+1)*(Z+1) ≤ X do
             {{ X=m ∧ Z*Z≤m ∧ (Z+1)*(Z+1)≤X }} ↠  (c - OK)
             {{ X=m ∧ (Z+1)*(Z+1)≤m }}
    Z := Z + 1
             {{ X=m ∧ Z*Z≤m }}
  end
{{ X=m ∧ Z*Z≤m ∧ ¬((Z+1)*(Z+1)≤X) }} ↠            (b - OK)
{{ Z*Z≤m ∧ m<(Z+1)*(Z+1) }}

This works, since conditions (a), (b), and (c) are now all rather trivially satisfied.

Very often, when a variable is used in a loop in a read-only fashion (i.e., it is referred to by the program or by the specification, and it is not changed by the loop), it is necessary to record the fact that it doesn't change in the loop invariant.

Exercise★★★(sqrt) (Optional)

Translate the above informal decorated program into a formal one and prove it correct.

Hint: The loop invariant here must ensure that Z*Z is consistently less than or equal to X.

def sqrtDec (m : Nat) : Decorated where pre := ({{ X = m }}) body := dcom { ↠ {{ solution!({{ X = m ∧ 0 * 0 ≤ m }}) }} Z := 0 {{ solution!({{ X = m ∧ Z * Z ≤ m }}) }}; while ((Z + 1) * (Z + 1) ≤ X) do {{ solution!({{ (X = m ∧ Z * Z ≤ m) ∧ (Z + 1) * (Z + 1) ≤ X }}) }} ↠ {{ solution!({{ X = m ∧ (Z + 1) * (Z + 1) ≤ m }}) }} Z := Z + 1 {{ solution!({{ X = m ∧ Z * Z ≤ m }}) }} end {{ solution!({{ (X = m ∧ Z * Z ≤ m) ∧ ¬ (Z + 1) * (Z + 1) ≤ X }}) }} ↠ {{ Z * Z ≤ m ∧ m < (Z + 1) * (Z + 1) }} } theorem sqrt_correct (m : Nat) : (sqrtDec m).OuterTripleValid := m:Nat⊢ (sqrtDec m).OuterTripleValid solution! m:Nat⊢ { pre := {{X = m}}, body := dcom { ↠ {{X = m ∧ 0 * 0 ≤ m}} Z := 0 {{X = m ∧ Z * Z ≤ m}}; while ((Z + 1) * (Z + 1) ≤ X) do {{(X = m ∧ Z * Z ≤ m) ∧ (Z + 1) * (Z + 1) ≤ X}} ↠ {{X = m ∧ (Z + 1) * (Z + 1) ≤ m}} Z := Z + 1 {{X = m ∧ Z * Z ≤ m}} end {{(X = m ∧ Z * Z ≤ m) ∧ ¬(Z + 1) * (Z + 1) ≤ X}} ↠ {{Z * Z ≤ m ∧ m < (Z + 1) * (Z + 1)}} } }.OuterTripleValid All goals completed! 🐙

6.3.5. Example: Squaring🔗

Note to developers

HIDE: CH: it might make sense to show all the variants for future exercise builders, together with some hints on how to write programs that are easier to verify

Here is a program that squares X by repeated addition:

{{ X = m }}
  Y := 0;
  Z := 0;
  while Y ≠ X  do
    Z := Z + X;
    Y := Y + 1
  end
{{ Z = m*m }}

The first thing to note is that the loop reads X but doesn't change its value. As we saw in the previous example, it can be a good idea in such cases to add X = m to the loop invariant. The other thing that we know is often useful in the loop invariant is the postcondition, so let's add that too, leading to the candidate loop invariant Z = m*m ∧ X = m.

{{ X = m }} ↠                                    (a - WRONG)
{{ 0 = m*m ∧ X = m }}
  Y := 0
               {{ 0 = m*m ∧ X = m }};
  Z := 0
               {{ Z = m*m ∧ X = m }};
  while Y ≠ X do
               {{ Z = m*m ∧ X = m ∧ Y ≠ X }} ↠   (c - WRONG)
               {{ Z+X = m*m ∧ X = m }}
    Z := Z + X
               {{ Z = m*m ∧ X = m }};
    Y := Y + 1
               {{ Z = m*m ∧ X = m }}
  end
{{ Z = m*m ∧ X = m ∧ ¬(Y ≠ X) }} ↠               (b - OK)
{{ Z = m*m }}

Conditions (a) and (c) fail because of the Z = m*m part. While Z starts at 0 and works itself up to m*m, we can't expect Z to be m*m from the start. If we look at how Z progresses in the loop, after the 1st iteration Z = m, after the 2nd iteration Z = 2*m, and at the end Z = m*m. Since the variable Y tracks how many times we go through the loop, this leads us to derive a new loop invariant candidate: Z = Y*m ∧ X = m.

{{ X = m }} ↠                                     (a - OK)
{{ 0 = 0*m ∧ X = m }}
  Y := 0
                {{ 0 = Y*m ∧ X = m }};
  Z := 0
                {{ Z = Y*m ∧ X = m }};
  while Y ≠ X do
                {{ Z = Y*m ∧ X = m ∧ Y ≠ X }} ↠   (c - OK)
                {{ Z+X = (Y+1)*m ∧ X = m }}
    Z := Z + X
                {{ Z = (Y+1)*m ∧ X = m }};
    Y := Y + 1
                {{ Z = Y*m ∧ X = m }}
  end
{{ Z = Y*m ∧ X = m ∧ ¬(Y ≠ X) }} ↠                (b - OK)
{{ Z = m*m }}

This new loop invariant makes the proof go through: all three conditions are easy to check.

It is worth comparing the postcondition Z = m*m and the Z = Y*m conjunct of the loop invariant. It is often the case that one has to replace parameters with variables — or with expressions involving both variables and parameters, like m - Y — when going from postconditions to loop invariants.

Note to developers
HIDE: the more complicated version from 2012's class

Here is a program that squares X by repeated addition:
[[
  X := n;
  Y := X;
  Z := 0;
  while Y ≠ 0 do
    Z := Z + X;
    Y := Y - 1
  end
]]

  Bob's simpler loop invariant for squaring [square_dec]:
  (a very similar invariant given as solution in 2011 final; exercise 3)

[[
  {{ True }}
  X := n;
  {{ X = n }}
  Y := X;
  {{ X = n ∧ Y = n }}
  Z := 0;
  {{ X = n ∧ Y = n ∧ Z = 0}} ↠
  {{ Z + X * Y = n * n }}
  while Y ≠ 0 do
    {{ Z + X * Y = n * n ∧ (Y ≠ 0)}} ↠
    {{ Z + X + X * (Y - 1) = n * n }}
    Z := Z + X;
    {{ Z + X * (Y - 1) = n * n }}
    Y := Y - 1
    {{ Z + X * Y = n * n }}
  end
  {{ Z + X * Y = n * n ∧ ~(Y ≠ 0)}} ↠
  {{ Z = n * n }}
]]

The other loop invariant [square_dec']:
[[
  {{ True }}
  X := n;
  {{ X = n }}
  Y := X;
  {{ X = n ∧ Y = n }}
  Z := 0;
  {{ X = n ∧ Y = n ∧ Z = 0}} ↠
  {{ Z = X * (X - Y) ∧ X = n ∧ Y ≤ X }}
  while Y ≠ 0 do
    {{ Z = X * (X - Y) ∧ X = n ∧ Y ≤ X ∧ (Y ≠ 0)}} ↠
    {{ Z + X = X * (X - (Y - 1)) ∧ X = n ∧ (Y - 1) ≤ X }}
    Z := Z + X;
    {{ Z = X * (X - (Y - 1)) ∧ X = n ∧ (Y - 1) ≤ X }}
    Y := Y - 1
    {{ Z = X * (X - Y) ∧ X = n ∧ Y ≤ X }}
  end
  {{ Z = X * (X - Y) ∧ X = n ∧ Y ≤ X ∧ ~(Y ≠ 0)}} ↠
  {{ Z = n * n }}
]]

6.3.6. Exercise: Factorial🔗

Note to developers (before next release)

Move this later? Might be harder than some of the others.

Exercise★★★★(factorial_correct) (Advanced)

Recall that n! denotes the factorial of n (i.e., n! = 1*2*...*n). We can define the factorial function recursively in Lean as follows:

def fact : Nat → Nat | 0 => 1 | Nat.succ n => Nat.succ n * fact n 120#eval fact 5

First, write the Imp program factorial that calculates the factorial of the number initially stored in the variable X and puts it in the variable Y.

Using your definition factorial and slowAssignmentDec as a guide, write a formal decorated program factorialDec that implements the factorial function. Ordinary Lean functions such as fact can be applied directly to Imp variables inside assertions.

Fill in the blanks and finish the proof of correctness. Bear in mind that we are working with natural numbers, for which both division and subtraction can behave differently than with real numbers. Excluding both operations from your loop invariant is advisable!

Then state a theorem named factorial_correct that says factorialDec is correct, and prove the theorem. If all goes well, verify will leave you with just two subgoals, each of which requires establishing some mathematical property of fact, rather than proving anything about your program.

Hint: if those two subgoals become tedious to prove, give some thought to how you could restate your assertions such that the mathematical operations are more amenable to manipulation in Lean. For example, recall that 1 + ... is easier to work with than ... + 1.

def factorialDec (m : Nat) : Decorated := solution!({ pre := ({{ X = m }}) body := dcom { ↠ {{ 1 * fact X = fact m }} Y := 1 {{ Y * fact X = fact m }}; while (X ≠ 0) do {{ Y * fact X = fact m ∧ ¬ X = 0 }} ↠ {{ (Y * X) * fact (X - 1) = fact m }} Y := Y * X {{ Y * fact (X - 1) = fact m }}; X := X - 1 {{ Y * fact X = fact m }} end {{ Y * fact X = fact m ∧ X = 0 }} ↠ {{ Y = fact m }} } }) theorem fact_sub_one (m : Nat) (h : m ≠ 0) : m * fact (m - 1) = fact m := m:Nath:m ≠ 0⊢ m * fact (m - 1) = fact m solution! cases m with h:0 ≠ 0⊢ 0 * fact (0 - 1) = fact 0 All goals completed! 🐙 m:Nath:m + 1 ≠ 0⊢ (m + 1) * fact (m + 1 - 1) = fact (m + 1) -- Both sides compute to `(m + 1) * fact m`. All goals completed! 🐙 theorem factorial_correct (m : Nat) : (factorialDec m).OuterTripleValid := m:Nat⊢ (factorialDec m).OuterTripleValid solution! m:Nat⊢ { pre := {{X = m}}, body := dcom { ↠ {{1 * fact X = fact m}} Y := 1 {{Y * fact X = fact m}}; while (X ≠ 0) do {{Y * fact X = fact m ∧ ¬X = 0}} ↠ {{Y * X * fact (X - 1) = fact m}} Y := Y * X {{Y * fact (X - 1) = fact m}}; X := X - 1 {{Y * fact X = fact m}} end {{Y * fact X = fact m ∧ X = 0}} ↠ {{Y = fact m}} } }.OuterTripleValid m:Nat⊢ ∀ (st : State), st[Y] * fact st[X] = fact m → ¬st[X] = 0 → st[Y] * st[X] * fact (st[X] - 1) = fact mm:Nat⊢ ∀ (st : State), st[Y] * fact st[X] = fact m → st[X] = 0 → st[Y] = fact m m:Nat⊢ ∀ (st : State), st[Y] * fact st[X] = fact m → ¬st[X] = 0 → st[Y] * st[X] * fact (st[X] - 1) = fact m m:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st[X] = 0⊢ st[Y] * st[X] * fact (st[X] - 1) = fact m m:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st[X] = 0⊢ st[Y] * fact st[X] = fact mm:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st[X] = 0⊢ st[X] ≠ 0 m:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st[X] = 0⊢ st[Y] * fact st[X] = fact m All goals completed! 🐙 m:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st[X] = 0⊢ st[X] ≠ 0 All goals completed! 🐙 m:Nat⊢ ∀ (st : State), st[Y] * fact st[X] = fact m → st[X] = 0 → st[Y] = fact m m:Natst:Stateh:st[Y] * fact st[X] = fact mhx:st[X] = 0⊢ st[Y] = fact m m:Natst:Stateh:st[Y] * fact 0 = fact mhx:st[X] = 0⊢ st[Y] = fact m m:Natst:Stateh:st[Y] * 1 = fact mhx:st[X] = 0⊢ st[Y] = fact m All goals completed! 🐙
Note to developers
HIDE: LY: I saw one submission for [factorial_dec] use a program
like that instead of the one already given by the informal
exercise. I accepted it because the exercise does not require to
reuse the given program, and we did not strictly define what it
means to "implement" factorial in Imp.  This other one "implements"
factorial in the same way two_loops_dec "implements" the sum (a + b
+ c).

6.3.7. Exercise: Minimum🔗

Exercise★★★(minimum_correct) (Advanced)

Fill in decorations for the following program and prove them correct. As with factorial, be careful about mathematical reasoning involving natural numbers, especially subtraction.

Lean functions can be applied directly inside assertions. For example, the minimum of a and b can be written Nat.min a b.

def minimumDec (a b : Nat) : Decorated where pre := ({{ True }}) body := dcom { ↠ {{ solution!({{ 0 + Nat.min a b = Nat.min a b }}) }} X := ~(Aexp.num a) {{ solution!({{ 0 + Nat.min X b = Nat.min a b }}) }}; Y := ~(Aexp.num b) {{ solution!({{ 0 + Nat.min X Y = Nat.min a b }}) }}; Z := 0 {{ solution!({{ Z + Nat.min X Y = Nat.min a b }}) }}; while (X ≠ 0 ∧ Y ≠ 0) do {{ solution!({{ Z + Nat.min X Y = Nat.min a b ∧ (¬ X = 0 ∧ ¬ Y = 0) }}) }} ↠ {{ solution!({{ Z + 1 + Nat.min (X - 1) (Y - 1) = Nat.min a b }}) }} X := X - 1 {{ solution!({{ Z + 1 + Nat.min X (Y - 1) = Nat.min a b }}) }}; Y := Y - 1 {{ solution!({{ Z + 1 + Nat.min X Y = Nat.min a b }}) }}; Z := Z + 1 {{ solution!({{ Z + Nat.min X Y = Nat.min a b }}) }} end {{ solution!({{ Z + Nat.min X Y = Nat.min a b ∧ ¬ (¬ X = 0 ∧ ¬ Y = 0) }}) }} ↠ {{ Z = Nat.min a b }} } theorem minimum_correct (a b : Nat) : (minimumDec a b).OuterTripleValid := a:Natb:Nat⊢ (minimumDec a b).OuterTripleValid solution! a:Natb:Nat⊢ { pre := {{True}}, body := dcom { ↠ {{0 + a.min b = a.min b}} X := ~(Aexp.num a) {{0 + (Nat.min X) b = a.min b}}; Y := ~(Aexp.num b) {{0 + (Nat.min X) Y = a.min b}}; Z := 0 {{Z + (Nat.min X) Y = a.min b}}; while (X ≠ 0 ∧ Y ≠ 0) do {{Z + (Nat.min X) Y = a.min b ∧ ¬X = 0 ∧ ¬Y = 0}} ↠ {{Z + 1 + (Nat.min (X - 1)) (Y - 1) = a.min b}} X := X - 1 {{Z + 1 + (Nat.min X) (Y - 1) = a.min b}}; Y := Y - 1 {{Z + 1 + (Nat.min X) Y = a.min b}}; Z := Z + 1 {{Z + (Nat.min X) Y = a.min b}} end {{Z + (Nat.min X) Y = a.min b ∧ ¬(¬X = 0 ∧ ¬Y = 0)}} ↠ {{Z = a.min b}} } }.OuterTripleValid All goals completed! 🐙

6.3.8. Exercise: Two Loops🔗

Note to developers

HIDE: Taken from midterm 2, 2012

Exercise★★★(two_loops)

Here is a pretty inefficient way of adding 3 numbers:

X := 0;
Y := 0;
Z := c;
while X ≠ a do
  X := X + 1;
  Z := Z + 1
end;
while Y ≠ b do
  Y := Y + 1;
  Z := Z + 1
end

Show that it does what it should by completing the following decorated program.

def twoLoopsDec (a b c : Nat) : Decorated where pre := ({{ True }}) body := dcom { ↠ {{ solution!({{ c = 0 + c ∧ 0 = 0 }}) }} X := 0 {{ solution!({{ c = X + c ∧ 0 = 0 }}) }}; Y := 0 {{ solution!({{ c = X + c ∧ Y = 0 }}) }}; Z := ~(Aexp.num c) {{ solution!({{ Z = X + c ∧ Y = 0 }}) }}; (while (X ≠ ~(Aexp.num a)) do {{ solution!({{ (Z = X + c ∧ Y = 0) ∧ ¬ X = a }}) }} ↠ {{ solution!({{ Z + 1 = X + 1 + c ∧ Y = 0 }}) }} X := X + 1 {{ solution!({{ Z + 1 = X + c ∧ Y = 0 }}) }}; Z := Z + 1 {{ solution!({{ Z = X + c ∧ Y = 0 }}) }} end {{ solution!({{ (Z = X + c ∧ Y = 0) ∧ X = a }}) }} ↠ {{ solution!({{ Z = a + Y + c }}) }}); while (Y ≠ ~(Aexp.num b)) do {{ solution!({{ Z = a + Y + c ∧ ¬ Y = b }}) }} ↠ {{ solution!({{ Z + 1 = a + Y + 1 + c }}) }} Y := Y + 1 {{ solution!({{ Z + 1 = a + Y + c }}) }}; Z := Z + 1 {{ solution!({{ Z = a + Y + c }}) }} end {{ solution!({{ Z = a + Y + c ∧ Y = b }}) }} ↠ {{ Z = a + b + c }} } theorem two_loops (a b c : Nat) : (twoLoopsDec a b c).OuterTripleValid := a:Natb:Natc:Nat⊢ (twoLoopsDec a b c).OuterTripleValid solution! a:Natb:Natc:Nat⊢ { pre := {{True}}, body := dcom { ↠ {{c = 0 + c ∧ True}} X := 0 {{c = X + c ∧ True}}; Y := 0 {{c = X + c ∧ Y = 0}}; Z := ~(Aexp.num c) {{Z = X + c ∧ Y = 0}}; (while (X ≠ ~(Aexp.num a)) do {{(Z = X + c ∧ Y = 0) ∧ ¬X = a}} ↠ {{Z + 1 = X + 1 + c ∧ Y = 0}} X := X + 1 {{Z + 1 = X + c ∧ Y = 0}}; Z := Z + 1 {{Z = X + c ∧ Y = 0}} end {{(Z = X + c ∧ Y = 0) ∧ X = a}} ↠ {{Z = a + Y + c}}); while (Y ≠ ~(Aexp.num b)) do {{Z = a + Y + c ∧ ¬Y = b}} ↠ {{Z + 1 = a + Y + 1 + c}} Y := Y + 1 {{Z + 1 = a + Y + c}}; Z := Z + 1 {{Z = a + Y + c}} end {{Z = a + Y + c ∧ Y = b}} ↠ {{Z = a + b + c}} } }.OuterTripleValid All goals completed! 🐙
Solution:
[[
    {{ True }} ↠
    {{ c = 0 + c ∧ 0 = 0 }}
  X := 0;
    {{ c = X + c ∧ 0 = 0 }}
  Y := 0;
    {{ c = X + c ∧ Y = 0 }}
  Z := c;
    {{ Z = X + c ∧ Y = 0 }}
  while X ≠ a do
      {{ Z = X + c ∧ Y = 0 ∧ X ≠ a }} ↠
      {{ Z + 1 = X + 1 + c ∧ Y = 0 }}
    X := X + 1;
      {{ Z + 1 = X + c ∧ Y = 0 }}
    Z := Z + 1
      {{ Z = X + c ∧ Y = 0 }}
  end;
    {{ Z = X + c ∧ Y = 0 ∧ ¬(X ≠ a) }} ↠
    {{ Z = a + Y + c }}
  while Y ≠ b do
      {{ Z = a + Y + c ∧ Y ≠ b }} ↠
      {{ Z + 1 = a + Y + 1 + c }}
    Y := Y + 1;
      {{ Z + 1 = a + Y + c }}
    Z := Z + 1
      {{ Z = a + Y + c }}
  end
    {{ Z = a + Y + c ∧ (Y ≠ b) }} ↠
    {{ Z = a + b + c }}
]]

Another solution follows.  It doesn't require carrying an additional
[Y = 0] conjunct through the first loop, but instead carries an
additional [ + Y] term through it.

[[
      {{ True }} ↠
        {{ c = 0 + 0 + c }}
    X := 0;
        {{ c = X + 0 + c }}
    Y := 0;
        {{ c = X + Y + c }}
    Z := c;
        {{ Z = X + Y + c }}
    while X ≠ a do
        {{ Z = X + Y + c ∧ X ≠ a }} ↠
        {{ Z + 1 = (X + 1) + Y + c }}
      X := X + 1;
        {{ Z + 1 = X + Y + c }}
      Z := Z + 1
        {{ Z = X + Y + c }}
    end;
      {{ Z = X + Y + c ∧ ¬(X ≠ a) }} ↠
      {{ Z = a + Y + c }}
    while Y ≠ b do
        {{ Z = a + Y + c ∧ (Y ≠ b) }} ↠
        {{ Z + 1 = a + (Y + 1) + c }}
      Y := Y + 1;
        {{ Z + 1 = a + Y + c }}
      Z := Z + 1
        {{ Z = a + Y + c }}
    end
      {{ Z = a + Y + c ∧ ¬(Y ≠ b) }} ↠
      {{ Z = a + b + c }}
]]

6.3.9. Exercise: Power Series🔗

Exercise★★★★(dpow2) (Optional)

Here is a program that computes the series: 1 + 2 + 2^2 + ... + 2^m = 2^(m+1) - 1

X := 0;
Y := 1;
Z := 1;
while X ≠ m do
  Z := 2 * Z;
  Y := Y + Z;
  X := X + 1
end

Turn this into a decorated program and prove it correct.

def pow2 : Nat → Nat | 0 => 1 | Nat.succ n => 2 * pow2 n def dpow2Dec (n : Nat) : Decorated where pre := ({{ True }}) body := dcom { ↠ {{ solution!({{ 1 = pow2 (0 + 1) - 1 ∧ 1 = pow2 0 }}) }} X := 0 {{ solution!({{ 1 = pow2 (X + 1) - 1 ∧ 1 = pow2 X }}) }}; Y := 1 {{ solution!({{ Y = pow2 (X + 1) - 1 ∧ 1 = pow2 X }}) }}; Z := 1 {{ solution!({{ Y = pow2 (X + 1) - 1 ∧ Z = pow2 X }}) }}; while (X ≠ ~(Aexp.num n)) do {{ solution!({{ (Y = pow2 (X + 1) - 1 ∧ Z = pow2 X) ∧ ¬ X = n }}) }} ↠ {{ solution!({{ Y + 2 * Z = pow2 (X + 2) - 1 ∧ 2 * Z = pow2 (X + 1) }}) }} Z := 2 * Z {{ solution!({{ Y + Z = pow2 (X + 2) - 1 ∧ Z = pow2 (X + 1) }}) }}; Y := Y + Z {{ solution!({{ Y = pow2 (X + 2) - 1 ∧ Z = pow2 (X + 1) }}) }}; X := X + 1 {{ solution!({{ Y = pow2 (X + 1) - 1 ∧ Z = pow2 X }}) }} end {{ solution!({{ (Y = pow2 (X + 1) - 1 ∧ Z = pow2 X) ∧ X = n }}) }} ↠ {{ Y = pow2 (n + 1) - 1 }} }

Some lemmas that you may find useful...

theorem pow2_add_one (n : Nat) : pow2 (n + 1) = pow2 n + pow2 n := n:Nat⊢ pow2 (n + 1) = pow2 n + pow2 n n:Nat⊢ 2 * pow2 n = pow2 n + pow2 n All goals completed! 🐙 theorem one_le_pow2 (n : Nat) : 1 ≤ pow2 n := n:Nat⊢ 1 ≤ pow2 n induction n with ⊢ 1 ≤ pow2 0 All goals completed! 🐙 n:Natih:1 ≤ pow2 n⊢ 1 ≤ pow2 (n + 1) n:Natih:1 ≤ pow2 n⊢ 1 ≤ 2 * pow2 n All goals completed! 🐙

The main correctness theorem:

theorem dpow2_down_correct (n : Nat) : (dpow2Dec n).OuterTripleValid := n:Nat⊢ (dpow2Dec n).OuterTripleValid solution! n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1⊢ (dpow2Dec n).OuterTripleValid n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1⊢ { pre := {{True}}, body := dcom { ↠ {{1 = pow2 (0 + 1) - 1 ∧ 1 = pow2 0}} X := 0 {{1 = pow2 (X + 1) - 1 ∧ 1 = pow2 X}}; Y := 1 {{Y = pow2 (X + 1) - 1 ∧ 1 = pow2 X}}; Z := 1 {{Y = pow2 (X + 1) - 1 ∧ Z = pow2 X}}; while (X ≠ ~(Aexp.num n)) do {{(Y = pow2 (X + 1) - 1 ∧ Z = pow2 X) ∧ ¬X = n}} ↠ {{Y + 2 * Z = pow2 (X + 2) - 1 ∧ 2 * Z = pow2 (X + 1)}} Z := 2 * Z {{Y + Z = pow2 (X + 2) - 1 ∧ Z = pow2 (X + 1)}}; Y := Y + Z {{Y = pow2 (X + 2) - 1 ∧ Z = pow2 (X + 1)}}; X := X + 1 {{Y = pow2 (X + 1) - 1 ∧ Z = pow2 X}} end {{(Y = pow2 (X + 1) - 1 ∧ Z = pow2 X) ∧ X = n}} ↠ {{Y = pow2 (n + 1) - 1}} } }.OuterTripleValid n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1⊢ ∀ (st : State), st[Y] = pow2 (st[X] + 1) - 1 → st[Z] = pow2 st[X] → ¬st[X] = n → st[Y] + 2 * st[Z] = pow2 (st[X] + 2) - 1 ∧ 2 * st[Z] = pow2 (st[X] + 1) n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1⊢ ∀ (st : State), st[Y] = pow2 (st[X] + 1) - 1 → st[Z] = pow2 st[X] → ¬st[X] = n → st[Y] + 2 * st[Z] = pow2 (st[X] + 2) - 1 ∧ 2 * st[Z] = pow2 (st[X] + 1) n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1st:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st[X] = n⊢ st[Y] + 2 * st[Z] = pow2 (st[X] + 2) - 1 ∧ 2 * st[Z] = pow2 (st[X] + 1) n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1st:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st[X] = n⊢ pow2 (st[X] + 1) - 1 + 2 * pow2 st[X] = pow2 (st[X] + 2) - 1 ∧ 2 * pow2 st[X] = pow2 (st[X] + 1) n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1st:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st[X] = n⊢ pow2 (st[X] + 1) - 1 + 2 * pow2 st[X] = pow2 (st[X] + 2) - 1n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1st:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st[X] = n⊢ 2 * pow2 st[X] = pow2 (st[X] + 1) n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1st:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st[X] = n⊢ pow2 (st[X] + 1) - 1 + 2 * pow2 st[X] = pow2 (st[X] + 2) - 1 -- 1 n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1st:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st[X] = n⊢ pow2 (st[X] + 1) - 1 + 2 * pow2 st[X] = pow2 (st[X] + 1 + 1) - 1 repeat n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1st:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st[X] = n⊢ pow2 st[X] + pow2 st[X] - 1 + 2 * pow2 st[X] = pow2 st[X] + pow2 st[X] + (pow2 st[X] + pow2 st[X]) - 1 All goals completed! 🐙 n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1st:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st[X] = n⊢ 2 * pow2 st[X] = pow2 (st[X] + 1) -- 2 n:Natadd_2_1:∀ (n : Nat), n + 2 = n + 1 + 1st:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st[X] = n⊢ 2 * pow2 st[X] = pow2 st[X] + pow2 st[X] All goals completed! 🐙
Note to developers
HIDE: Another (very) good exercise from 09-mid₂ -- just needs typeset

The notion of weakest precondition has a natural dual : given a
precondition and a command, we can ask what is the strongest
postcondition of the command with respect to the
precondition. Formally, we can define it like this:

q is the strongest postcondition of c for p if:

(a) {{p}} c {{q}}, and

(b) if Q′ is an assertion such that {{p}}c{{Q′}},
    then q st implies Q′ st, for all states st.

q is the strongest (most difficult to satisfy) assertion that is
guaranteed to hold after c if p holds before. For example, the
strongest postcondition of the command skip with respect to the
precondition Y = 1 is Y = 1. Similarly, the postcondition in...

         {{ Y = y }}
           if Y = 0 then X := 0 else Y := Y * 2
         {{ (Y = y = X = 0) ∨ (Y = 2*y ∧ y ≠ 0) }}

...is the strongest one.

Complete each of the following Hoare triples with the strongest
postcondition for the given command and precondition.

(a) {{ Y = 1 }} X := Y + 1 {{ ? }}
(b) {{ True }} X := 5 {{ ? }}
(c) {{ True }} skip {{ ? }}
(d) {{ True }} while true do skip {{ ? }}
(e) {{ X = x ∧ Y = y }}
    while X ≠ 0 do
      Y := Y + 2;
      X := X - 1
    end
    {{ ? }}
Exercise★★(fib_eqn) (Advanced, Optional)

The Fibonacci function is characterized by the equations

fib 0 = 1
fib 1 = 1
fib (n + 2) = fib (n + 1) + fib n

This recurrence can be defined structurally in Lean as follows:

def fib : Nat → Nat | 0 => 1 | Nat.succ 0 => 1 | Nat.succ (Nat.succ n) => fib (Nat.succ n) + fib n

Prove that fib satisfies the following equation. You will need this as a lemma in the next exercise.

theorem fib_eqn (n : Nat) (h : n > 0) : fib n + fib (Nat.pred n) = fib (1 + n) := n:Nath:n > 0⊢ fib n + fib n.pred = fib (1 + n) solution! cases n with h:0 > 0⊢ fib 0 + fib (Nat.pred 0) = fib (1 + 0) All goals completed! 🐙 k:Nath:k + 1 > 0⊢ fib (k + 1) + fib (k + 1).pred = fib (1 + (k + 1)) k:Nath:k + 1 > 0⊢ fib (k + 1) + fib (k + 1).pred = fib (k + 1 + 1) -- Both sides compute to `fib (k + 1) + fib k`. All goals completed! 🐙
Exercise★★★★(fib) (Advanced, Optional)

The following Imp program leaves the value of fib n in the variable Y when it terminates:

X := 1;
Y := 1;
Z := 1;
while X ≠ 1 + n do
  T := Z;
  Z := Z + Y;
  Y := T;
  X := 1 + X
end

Fill in the following definition of dfib and prove that it satisfies this specification:

{{ True }} dfib {{ Y = fib n }}

Ordinary Lean function application can be used in the assertions. If all goes well, your proof will be very brief.

def T : Ident := "T" def dfib (n : Nat) : Decorated where pre := ({{ True }}) body := let init : Assertion := solution!(fun _ => 1 = fib 0 ∧ 1 = fib (Nat.pred 0) ∧ 1 > 0) let afterX : Assertion := solution!(fun st => 1 = fib st[X] ∧ 1 = fib (Nat.pred st[X]) ∧ st[X] > 0) let afterY : Assertion := solution!(fun st => 1 = fib st[X] ∧ st[Y] = fib (Nat.pred st[X]) ∧ st[X] > 0) let inv : Assertion := solution!(fun st => st[Z] = fib st[X] ∧ st[Y] = fib (Nat.pred st[X]) ∧ st[X] > 0) let guardedInv : Assertion := solution!(fun st => st[Z] = fib st[X] ∧ st[Y] = fib (Nat.pred st[X]) ∧ st[X] > 0 ∧ st[X] ≠ 1 + n) let bodyPre : Assertion := solution!(fun st => st[Z] + st[Y] = fib (1 + st[X]) ∧ st[Z] = fib (Nat.pred (1 + st[X])) ∧ 1 + st[X] > 0) let afterT : Assertion := solution!(fun st => st[Z] + st[Y] = fib (1 + st[X]) ∧ st[T] = fib (Nat.pred (1 + st[X])) ∧ 1 + st[X] > 0) let afterZ : Assertion := solution!(fun st => st[Z] = fib (1 + st[X]) ∧ st[T] = fib (Nat.pred (1 + st[X])) ∧ 1 + st[X] > 0) let afterYBody : Assertion := solution!(fun st => st[Z] = fib (1 + st[X]) ∧ st[Y] = fib (Nat.pred (1 + st[X])) ∧ 1 + st[X] > 0) let exit : Assertion := solution!(fun st => st[Z] = fib st[X] ∧ st[Y] = fib (Nat.pred st[X]) ∧ st[X] > 0 ∧ st[X] = 1 + n) dcom { ↠ {{ init }} X := 1 {{ afterX }}; Y := 1 {{ afterY }}; Z := 1 {{ inv }}; while (X ≠ ~(Aexp.num (1 + n))) do {{ guardedInv }} ↠ {{ bodyPre }} T := Z {{ afterT }}; Z := Z + Y {{ afterZ }}; Y := T {{ afterYBody }}; X := 1 + X {{ inv }} end {{ exit }} ↠ {{ Y = fib n }} } theorem dfib_correct (n : Nat) : (dfib n).OuterTripleValid := n:Nat⊢ (dfib n).OuterTripleValid solution! n:Nat⊢ { pre := {{True}}, body := DCom.pre ({{1 = fib 0 ∧ 1 = fib (Nat.pred 0) ∧ 1 > 0}}) ((dcom { X := 1 {{1 = fib X ∧ 1 = fib (Nat.pred X) ∧ X > 0}} }.seq (dcom { Y := 1 {{1 = fib X ∧ Y = fib (Nat.pred X) ∧ X > 0}} }.seq (dcom { Z := 1 {{Z = fib X ∧ Y = fib (Nat.pred X) ∧ X > 0}} }.seq (DCom.whileDo (bexp {X ≠ ~(Aexp.num (1 + n))}) ({{Z = fib X ∧ Y = fib (Nat.pred X) ∧ X > 0 ∧ X ≠ 1 + n}}) (DCom.pre ({{Z + Y = fib (1 + X) ∧ Z = fib (Nat.pred (1 + X)) ∧ 1 + X > 0}}) ((DCom.asgn "T" (aexp {Z}) ({{Z + Y = fib (1 + X) ∧ T = fib (Nat.pred (1 + X)) ∧ 1 + X > 0}})).seq (dcom { Z := Z + Y {{Z = fib (1 + X) ∧ T = fib (Nat.pred (1 + X)) ∧ 1 + X > 0}}; Y := T {{Z = fib (1 + X) ∧ Y = fib (Nat.pred (1 + X)) ∧ 1 + X > 0}}; X := 1 + X {{Z = fib X ∧ Y = fib (Nat.pred X) ∧ X > 0}} }))) ({{Z = fib X ∧ Y = fib (Nat.pred X) ∧ X > 0 ∧ X = 1 + n}}))))).post ({{Y = fib n}})) }.OuterTripleValid n:Nat⊢ ∀ (st : State), st[Z] = fib st[X] → st[Y] = fib (st[X] - 1) → 0 < st[X] → ¬st[X] = 1 + n → st[Z] + st[Y] = fib (1 + st[X]) ∧ st[Z] = fib st[X] ∧ 0 < 1 + st[X]n:Nat⊢ ∀ (st : State), st[Z] = fib st[X] → st[Y] = fib (st[X] - 1) → 0 < st[X] → st[X] = 1 + n → st[Y] = fib n n:Nat⊢ ∀ (st : State), st[Z] = fib st[X] → st[Y] = fib (st[X] - 1) → 0 < st[X] → ¬st[X] = 1 + n → st[Z] + st[Y] = fib (1 + st[X]) ∧ st[Z] = fib st[X] ∧ 0 < 1 + st[X] n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st[X] = 1 + n⊢ st[Z] + st[Y] = fib (1 + st[X]) ∧ st[Z] = fib st[X] ∧ 0 < 1 + st[X] n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st[X] = 1 + n⊢ fib st[X] + fib (st[X] - 1) = fib (1 + st[X]) ∧ fib st[X] = fib st[X] ∧ 0 < 1 + st[X] n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st[X] = 1 + n⊢ fib st[X] + fib (st[X] - 1) = fib (1 + st[X])n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st[X] = 1 + n⊢ fib st[X] = fib st[X] ∧ 0 < 1 + st[X] n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st[X] = 1 + n⊢ fib st[X] + fib (st[X] - 1) = fib (1 + st[X]) n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st[X] = 1 + n⊢ st[X] > 0 All goals completed! 🐙 n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st[X] = 1 + n⊢ fib st[X] = fib st[X] ∧ 0 < 1 + st[X] All goals completed! 🐙 n:Nat⊢ ∀ (st : State), st[Z] = fib st[X] → st[Y] = fib (st[X] - 1) → 0 < st[X] → st[X] = 1 + n → st[Y] = fib n n:Natst:Statea✝¹:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)a✝:0 < st[X]hx:st[X] = 1 + n⊢ st[Y] = fib n n:Natst:Statea✝¹:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)a✝:0 < st[X]hx:st[X] = 1 + n⊢ fib (1 + n - 1) = fib n All goals completed! 🐙
Note to developers (Benjamin Pierce @bcpierce00, before next release, 2021)

This exercise should really be expanded into its own whole section. Moreover, there is a proposal to make the decorations in Hoare look more like the decorations earlier in the present chapter. All three should be aligned.

Exercise★★★★★(improve_dcom) (Advanced, Optional)

The formal decorated programs defined above are intended to look as similar as possible to the informal ones defined earlier. If we drop this requirement, we can eliminate almost all annotations, just requiring final postconditions and loop invariants to be provided explicitly. Do this — i.e., define a new version of DCom with as few annotations as possible and adapt the rest of the formal development leading up to the verification_correct theorem.

namespace SparseAnnotations /- (This solution also allows optional post-condition assertions at any point, since these are quite useful in practice when debugging the results of automated VC solvers.) -/ inductive DCom where | skip | seq (first second : DCom) | asgn (x : Ident) (a : Aexp) | cond (b : Bexp) (thenBranch elseBranch : DCom) | whileDo (b : Bexp) (invariant : Assertion) (body : DCom) | assert (assertion : Assertion) structure Decorated where pre : Assertion body : DCom post : Assertion declare_syntax_cat sparse_dcom syntax:max "(" sparse_dcom ")" : sparse_dcom syntax:max "skip" : sparse_dcom syntax:max ident " := " imp_aexp : sparse_dcom syntax:20 sparse_dcom:21 ";" ppDedent(ppLine sparse_dcom:20) : sparse_dcom syntax:max "if " "(" imp_bexp ")" ppHardSpace "then" ppLine sparse_dcom ppDedent(ppLine ppDedent("else")) ppLine sparse_dcom ppDedent(ppLine ppDedent("end")) : sparse_dcom syntax:max "while " "(" imp_bexp ")" ppHardSpace "do" ppLine "{{" term "}}" ppLine sparse_dcom ppDedent(ppLine ppDedent("end")) : sparse_dcom syntax:max "assert" " {{" term "}}" : sparse_dcom syntax:min "sdcom" ppHardSpace "{" ppLine sparse_dcom ppDedent(ppLine "}") : term macro_rules | `(sdcom { $s }) => do let stx ← match s with | `(sparse_dcom| ($body:sparse_dcom)) => `(sdcom { $body }) | `(sparse_dcom| skip) => `(DCom.skip) | `(sparse_dcom| $x:ident := $a:imp_aexp) => `(DCom.asgn $x (aexp { $a })) | `(sparse_dcom| $d₁:sparse_dcom; $d₂:sparse_dcom) => `(DCom.seq (sdcom { $d₁ }) (sdcom { $d₂ })) | `(sparse_dcom| if ($b:imp_bexp) then $d₁:sparse_dcom else $d₂:sparse_dcom end) => `(DCom.cond (bexp { $b }) (sdcom { $d₁ }) (sdcom { $d₂ })) | `(sparse_dcom| while ($b:imp_bexp) do {{ $inv }} $body:sparse_dcom end) => `(DCom.whileDo (bexp { $b }) ({{ $inv }}) (sdcom { $body })) | `(sparse_dcom| assert {{ $p }}) => `(DCom.assert ({{ $p }})) | _ => Lean.Macro.throwUnsupported return Imp.Elab.withSourceInfoOf s stx namespace DCom.Delab open Lean PrettyPrinter Delaborator SubExpr Parenthesizer Imp.Elab Imp.Delab @[category_parenthesizer sparse_dcom] def sparse_dcom.parenthesizer : CategoryParenthesizer := fun prec => do maybeParenthesize `sparse_dcom false wrapParens prec <| parenthesizeCategoryCore `sparse_dcom prec where wrapParens (stx : Syntax) : Syntax := Unhygienic.run do let stxInfo := SourceInfo.fromRef stx let stx := stx.setInfo .none let pstx ← `(sparse_dcom| ($(⟨stx⟩))) return pstx.raw.setInfo stxInfo private def getDCom? (stx : Term) : Option (TSyntax `sparse_dcom) := match stx with | `(sdcom { $d:sparse_dcom }) => some <| withSourceInfoOf (canonical := false) stx d | _ => none @[app_delab SparseAnnotations.DCom.skip] def delabSkip : Delab := whenPPOption getPPNotation do `(sdcom { skip }) @[app_unexpander SparseAnnotations.DCom.asgn] def unexpandAsgn : Unexpander | `($_ $x:ident $a) => `(sdcom { $x:ident := $(getAexp a) }) | _ => throw () @[app_unexpander SparseAnnotations.DCom.seq] def unexpandSeq : Unexpander | `($_ $first $second) => do let some first := getDCom? first | throw () let some second := getDCom? second | throw () `(sdcom { $first; $second }) | _ => throw () @[app_unexpander SparseAnnotations.DCom.cond] def unexpandCond : Unexpander | `($_ $b $thenBranch $elseBranch) => do let some thenBranch := getDCom? thenBranch | throw () let some elseBranch := getDCom? elseBranch | throw () `(sdcom { if ($(getBexp b)) then $thenBranch else $elseBranch end }) | _ => throw () @[app_unexpander SparseAnnotations.DCom.whileDo] def unexpandWhileDo : Unexpander | `($_ $b $invariant $body) => do let some body := getDCom? body | throw () `(sdcom { while ($(getBexp b)) do {{ $(_root_.DCom.Delab.getAssnBody invariant) }} $body end }) | _ => throw () @[app_unexpander SparseAnnotations.DCom.assert] def unexpandAssert : Unexpander | `($_ $assertion) => `(sdcom { assert {{ $(_root_.DCom.Delab.getAssnBody assertion) }} }) | _ => throw () end DCom.Delab /- Here's how our decorated programs look now: -/ def decWhile : Decorated where pre := ({{ True }}) body := sdcom { while (X ≠ 0) do {{ True }} X := X - 1 end } post := ({{ X = 0 }}) /- It is easy to go from a `DCom` to a `Com` by erasing all annotations. -/ def DCom.erase (d : DCom) : Com := match d with | .skip => .skip | .seq d₁ d₂ => .seq d₁.erase d₂.erase | .asgn x a => .asgn x a | .cond b d₁ d₂ => .cond b d₁.erase d₂.erase | .whileDo b _ body => .whileDo b body.erase | .assert _ => .skip /- We can express what it means for a decorated program to be correct as follows: -/ def Decorated.OuterTripleValid (dec : Decorated) : Prop := ValidHoareTriple dec.pre dec.body.erase dec.post theorem Decorated.outerTripleValid_def {dec : Decorated} : dec.OuterTripleValid ↔ ValidHoareTriple dec.pre dec.body.erase dec.post := dec:Decorated⊢ dec.OuterTripleValid ↔ ValidHoareTriple dec.pre dec.body.erase dec.post All goals completed! 🐙 /- This VC generator is derived from Mike Gordon, "Background reading on Hoare Logic," https://www.cl.cam.ac.uk/archive/mjcg/HL/Notes/Notes.pdf -/ @[simp] def DCom.awp (post : Assertion) (d : DCom) : Assertion := match d with | .skip => post | .seq d₁ d₂ => d₁.awp (d₂.awp post) | .asgn x a => {{ post [x ↦ a] }} | .cond b d₁ d₂ => fun st => (b.eval st = true ∧ d₁.awp post st) ∨ (b.eval st = false ∧ d₂.awp post st) | .whileDo _ invariant _ => invariant | .assert assertion => fun st => assertion st ∧ post st @[simp] def DCom.VerificationConditions (post : Assertion) (d : DCom) : Prop := match d with | .seq d₁ d₂ => d₁.VerificationConditions (d₂.awp post) ∧ d₂.VerificationConditions post | .cond _ d₁ d₂ => d₁.VerificationConditions post ∧ d₂.VerificationConditions post | .whileDo b invariant body => (∀ st, invariant st ∧ b.eval st ≠ true → post st) ∧ (∀ st, invariant st ∧ b.eval st = true → body.awp invariant st) ∧ body.VerificationConditions invariant | _ => True -- `validHoareTriple_def` for `ValidHoareTriple` written -- directly rather than with `{{ P }} c {{ Q }}` notation. theorem validHoareTriple_def' {P : Assertion} {c : Com} {Q : Assertion} : ValidHoareTriple P c Q ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' := P:Assertionc:ComQ:Assertion⊢ ValidHoareTriple P c Q ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' All goals completed! 🐙 theorem vc_correct (d : DCom) (post : Assertion) (hvc : d.VerificationConditions post) : ValidHoareTriple (d.awp post) d.erase post := d:DCompost:Assertionhvc:DCom.VerificationConditions post d⊢ ValidHoareTriple (DCom.awp post d) d.erase post induction d generalizing post with a:Assertionpost:Assertionhvc:True⊢ ValidHoareTriple ({{a ∧ post}}) (imp {«skip»}) post post:Assertionhvc:True⊢ ValidHoareTriple post (imp {«skip»}) post All goals completed! 🐙 d₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionhvc:DCom.VerificationConditions (DCom.awp post d₂) d₁ ∧ DCom.VerificationConditions post d₂⊢ ValidHoareTriple (DCom.awp (DCom.awp post d₂) d₁) (imp {~d₁.erase; ~d₂.erase}) post d₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionh₁:DCom.VerificationConditions (DCom.awp post d₂) d₁h₂:DCom.VerificationConditions post d₂⊢ ValidHoareTriple (DCom.awp (DCom.awp post d₂) d₁) (imp {~d₁.erase; ~d₂.erase}) post d₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionh₁:DCom.VerificationConditions (DCom.awp post d₂) d₁h₂:DCom.VerificationConditions post d₂⊢ {{?seq.Q}} ~d₂.erase {{post}}d₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionh₁:DCom.VerificationConditions (DCom.awp post d₂) d₁h₂:DCom.VerificationConditions post d₂⊢ {{fun st => DCom.awp (DCom.awp post d₂) d₁ st}} ~d₁.erase {{?seq.Q}}d₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionh₁:DCom.VerificationConditions (DCom.awp post d₂) d₁h₂:DCom.VerificationConditions post d₂⊢ Assertion d₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionh₁:DCom.VerificationConditions (DCom.awp post d₂) d₁h₂:DCom.VerificationConditions post d₂⊢ {{?seq.Q}} ~d₂.erase {{post}} d₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionh₁:DCom.VerificationConditions (DCom.awp post d₂) d₁h₂:DCom.VerificationConditions post d₂⊢ DCom.VerificationConditions ({{post}}) d₂; All goals completed! 🐙 d₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionh₁:DCom.VerificationConditions (DCom.awp post d₂) d₁h₂:DCom.VerificationConditions post d₂⊢ {{fun st => DCom.awp (DCom.awp post d₂) d₁ st}} ~d₁.erase {{fun st => DCom.awp ({{post}}) d₂ st}} d₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionh₁:DCom.VerificationConditions (DCom.awp post d₂) d₁h₂:DCom.VerificationConditions post d₂⊢ DCom.VerificationConditions (DCom.awp post d₂) d₁; All goals completed! 🐙 x:Identa:Aexppost:Assertionhvc:True⊢ ValidHoareTriple ({{post [x ↦ a]}}) (imp {x := a}) post All goals completed! 🐙 b:Bexpd₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionhvc:DCom.VerificationConditions post d₁ ∧ DCom.VerificationConditions post d₂⊢ ValidHoareTriple (fun st => Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) (imp {if (b) {~d₁.erase} else {~d₂.erase} }) post b:Bexpd₁:DComd₂:DComih₁:∀ (post : Assertion), DCom.VerificationConditions post d₁ → ValidHoareTriple (DCom.awp post d₁) d₁.erase postih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionhthen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ ValidHoareTriple (fun st => Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) (imp {if (b) {~d₁.erase} else {~d₂.erase} }) post b:Bexpd₁:DComd₂:DComih₂:∀ (post : Assertion), DCom.VerificationConditions post d₂ → ValidHoareTriple (DCom.awp post d₂) d₂.erase postpost:Assertionih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ ValidHoareTriple (fun st => Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) (imp {if (b) {~d₁.erase} else {~d₂.erase} }) post b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ ValidHoareTriple (fun st => Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) (imp {if (b) {~d₁.erase} else {~d₂.erase} }) post b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{fun st => (Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) ∧ Bexp.eval st b = true}} ~d₁.erase {{post}}b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{fun st => (Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) ∧ ¬Bexp.eval st b = true}} ~d₂.erase {{post}} b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{fun st => (Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) ∧ Bexp.eval st b = true}} ~d₁.erase {{post}} b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{?cond.htrue.P'}} ~d₁.erase {{post}}b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{fun st => (Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) ∧ Bexp.eval st b = true}} ↠ ?cond.htrue.P'b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ Assertion b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{?cond.htrue.P'}} ~d₁.erase {{post}} All goals completed! 🐙 b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{fun st => (Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) ∧ Bexp.eval st b = true}} ↠ DCom.awp post d₁ All goals completed! 🐙 b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{fun st => (Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) ∧ ¬Bexp.eval st b = true}} ~d₂.erase {{post}} b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{?cond.hfalse.P'}} ~d₂.erase {{post}}b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{fun st => (Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) ∧ ¬Bexp.eval st b = true}} ↠ ?cond.hfalse.P'b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ Assertion b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{?cond.hfalse.P'}} ~d₂.erase {{post}} All goals completed! 🐙 b:Bexpd₁:DComd₂:DCompost:Assertionih₂:ValidHoareTriple (DCom.awp post d₂) d₂.erase postih₁:ValidHoareTriple (DCom.awp post d₁) d₁.erase posththen:DCom.VerificationConditions post d₁helse:DCom.VerificationConditions post d₂⊢ {{fun st => (Bexp.eval st b = true ∧ DCom.awp post d₁ st ∨ Bexp.eval st b = false ∧ DCom.awp post d₂ st) ∧ ¬Bexp.eval st b = true}} ↠ DCom.awp post d₂ All goals completed! 🐙 b:Bexpinv:Assertionbody:DComih:∀ (post : Assertion), DCom.VerificationConditions post body → ValidHoareTriple (DCom.awp post body) body.erase postpost:Assertionhvc:(∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post st) ∧ (∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body st) ∧ DCom.VerificationConditions inv body⊢ ValidHoareTriple inv (imp {while (b) {~body.erase} }) post b:Bexpinv:Assertionbody:DComih:∀ (post : Assertion), DCom.VerificationConditions post body → ValidHoareTriple (DCom.awp post body) body.erase postpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ ValidHoareTriple inv (imp {while (b) {~body.erase} }) post b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ ValidHoareTriple inv (imp {while (b) {~body.erase} }) post b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ {{inv}} while (b) {~body.erase} {{?whileDo.Q'}}b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ ?whileDo.Q' ↠ postb:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ Assertion b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ {{inv}} while (b) {~body.erase} {{?whileDo.Q'}} b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ {{inv ∧ b}} ~body.erase {{inv}} b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ {{?whileDo.hhoare.P'}} ~body.erase {{inv}}b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ {{inv ∧ b}} ↠ ?whileDo.hhoare.P'b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ Assertion b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ {{?whileDo.hhoare.P'}} ~body.erase {{inv}} All goals completed! 🐙 b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ {{inv ∧ b}} ↠ DCom.awp inv body b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ ∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body st b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv bodyst:Stateh:inv st ∧ Bexp.eval st b = true⊢ DCom.awp inv body st b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv bodyst:Stateh:inv st ∧ Bexp.eval st b = true⊢ inv st ∧ Bexp.eval st b = true All goals completed! 🐙 b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ {{inv ∧ ¬b}} ↠ post b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv body⊢ ∀ (st : State), inv st ∧ ¬Bexp.eval st b = true → post st b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv bodyst:Stateh:inv st ∧ ¬Bexp.eval st b = true⊢ post st b:Bexpinv:Assertionbody:DComih:ValidHoareTriple (DCom.awp inv body) body.erase invpost:Assertionh₁:∀ (st : State), inv st ∧ Bexp.eval st b ≠ true → post sth₂:∀ (st : State), inv st ∧ Bexp.eval st b = true → DCom.awp inv body sth₃:DCom.VerificationConditions inv bodyst:Stateh:inv st ∧ ¬Bexp.eval st b = true⊢ inv st ∧ Bexp.eval st b ≠ true All goals completed! 🐙 a:Assertionpost:Assertionhvc:True⊢ ValidHoareTriple ({{a ∧ post}}) (imp {«skip»}) post a:Assertionpost:Assertionhvc:True⊢ ∀ {st st' : State}, (st =[ «skip» ]=> st') → a st ∧ post st → post st' a:Assertionpost:Assertionhvc:Truest:Statest':Stateheval:st =[ «skip» ]=> st'hpre:a st ∧ post st⊢ post st' a:Assertionpost:Assertionhvc:Truest:Statehpre:a st ∧ post st⊢ post st a:Assertionpost:Assertionhvc:Truest:Stateleft✝:a sthq:post st⊢ post st All goals completed! 🐙 @[simp] def Decorated.VerificationConditions (dec : Decorated) : Prop := (dec.pre ↠ dec.body.awp dec.post) ∧ dec.body.VerificationConditions dec.post theorem verification_correct (dec : Decorated) (hvc : dec.VerificationConditions) : dec.OuterTripleValid := dec:Decoratedhvc:dec.VerificationConditions⊢ dec.OuterTripleValid dec:Decoratedhpre:dec.pre ↠ DCom.awp dec.post dec.bodyhd:DCom.VerificationConditions dec.post dec.body⊢ dec.OuterTripleValid dec:Decoratedhpre:dec.pre ↠ DCom.awp dec.post dec.bodyhd:DCom.VerificationConditions dec.post dec.body⊢ ValidHoareTriple dec.pre dec.body.erase dec.post dec:Decoratedhpre:dec.pre ↠ DCom.awp dec.post dec.bodyhd:DCom.VerificationConditions dec.post dec.body⊢ {{?P'}} ~dec.body.erase {{fun st => dec.post st}}dec:Decoratedhpre:dec.pre ↠ DCom.awp dec.post dec.bodyhd:DCom.VerificationConditions dec.post dec.body⊢ dec.pre ↠ ?P'dec:Decoratedhpre:dec.pre ↠ DCom.awp dec.post dec.bodyhd:DCom.VerificationConditions dec.post dec.body⊢ Assertion dec:Decoratedhpre:dec.pre ↠ DCom.awp dec.post dec.bodyhd:DCom.VerificationConditions dec.post dec.body⊢ {{?P'}} ~dec.body.erase {{fun st => dec.post st}} dec:Decoratedhpre:dec.pre ↠ DCom.awp dec.post dec.bodyhd:DCom.VerificationConditions dec.post dec.body⊢ DCom.VerificationConditions (fun st => dec.post st) dec.body All goals completed! 🐙 dec:Decoratedhpre:dec.pre ↠ DCom.awp dec.post dec.bodyhd:DCom.VerificationConditions dec.post dec.body⊢ dec.pre ↠ DCom.awp (fun st => dec.post st) dec.body All goals completed! 🐙 -- We redefine `verify` for this section's `verification_correct`, -- again leaving any conjunct `lia` cannot prove open as a separate goal. scoped macro_rules | `(tactic| verify) => `(tactic| (apply verification_correct; simp +decide [-Bexp.eval_le, -Bexp.eval_gt, Bexp.eval_le_true, Bexp.eval_le_false, Bexp.eval_gt_true, Bexp.eval_gt_false, assertImplies_def, assertIff_def, validHoareTriple_def, Assertion.subst_def]; all_goals and_intros; all_goals try lia)) /- Let's redo all the examples to date. -/ theorem dec_while_correct : decWhile.OuterTripleValid := ⊢ decWhile.OuterTripleValid ⊢ { pre := {{True}}, body := sdcom { while (X ≠ 0) do {{True}} X := X - 1 end }, post := {{X = 0}} }.OuterTripleValid All goals completed! 🐙 def swapDec (m n : Nat) : Decorated where pre := ({{ X = m ∧ Y = n }}) body := sdcom { X := X + Y; Y := X - Y; X := X - Y } post := ({{ X = n ∧ Y = m }}) theorem swap_correct (m n : Nat) : (swapDec m n).OuterTripleValid := m:Natn:Nat⊢ (swapDec m n).OuterTripleValid m:Natn:Nat⊢ { pre := {{X = m ∧ Y = n}}, body := sdcom { X := X + Y; Y := X - Y; X := X - Y }, post := {{X = n ∧ Y = m}} }.OuterTripleValid All goals completed! 🐙 def ifMinusDec : Decorated where pre := ({{ True }}) body := sdcom { if (X ≤ Y) then Z := Y - X else Z := X - Y end } post := ({{ Z + X = Y ∨ Z + Y = X }}) theorem if_minus_correct : ifMinusDec.OuterTripleValid := ⊢ ifMinusDec.OuterTripleValid ⊢ { pre := {{True}}, body := sdcom { if (X ≤ Y) then Z := Y - X else Z := X - Y end }, post := {{Z + X = Y ∨ Z + Y = X}} }.OuterTripleValid All goals completed! 🐙 def ifMinusPlusDec : Decorated where pre := ({{ True }}) body := sdcom { if (X ≤ Y) then Z := Y - X else Y := X + Z end } post := ({{ Y = X + Z }}) theorem if_minus_plus_correct : ifMinusPlusDec.OuterTripleValid := ⊢ ifMinusPlusDec.OuterTripleValid ⊢ { pre := {{True}}, body := sdcom { if (X ≤ Y) then Z := Y - X else Y := X + Z end }, post := {{Y = X + Z}} }.OuterTripleValid All goals completed! 🐙 def divModDec (a b : Nat) : Decorated where pre := ({{ True }}) body := sdcom { X := ~(Aexp.num a); Y := 0; while (~(Aexp.num b) ≤ X) do {{ b * Y + X = a }} X := X - ~(Aexp.num b); Y := Y + 1 end } post := ({{ b * Y + X = a ∧ X < b }}) theorem div_mod_outer_triple_valid (a b : Nat) : (divModDec a b).OuterTripleValid := a:Natb:Nat⊢ (divModDec a b).OuterTripleValid a:Natb:Nat⊢ { pre := {{True}}, body := sdcom { X := ~(Aexp.num a); Y := 0; while (~(Aexp.num b) ≤ X) do {{b * Y + X = a}} X := X - ~(Aexp.num b); Y := Y + 1 end }, post := {{b * Y + X = a ∧ X < b}} }.OuterTripleValid All goals completed! 🐙 def parityDec (m : Nat) : Decorated where pre := ({{ X = m }}) body := sdcom { while (2 ≤ X) do {{ parity X = parity m }} X := X - 2 end } post := ({{ X = parity m }}) theorem parity_outer_triple_valid (m : Nat) : (parityDec m).OuterTripleValid := m:Nat⊢ (parityDec m).OuterTripleValid m:Nat⊢ { pre := {{X = m}}, body := sdcom { while (2 ≤ X) do {{parity X = parity m}} X := X - 2 end }, post := {{X = parity m}} }.OuterTripleValid m:Nat⊢ ∀ (st : State), parity st[X] = parity m → st["X"] < 2 → st[X] = parity mm:Nat⊢ ∀ (st : State), parity st[X] = parity m → 2 ≤ st["X"] → parity (st["X"] - 2) = parity m m:Nat⊢ ∀ (st : State), parity st[X] = parity m → st["X"] < 2 → st[X] = parity m m:Natst:Stateh:parity st[X] = parity mhlt:st["X"] < 2⊢ st[X] = parity m m:Natst:Stateh:parity st[X] = parity mhlt:st["X"] < 2⊢ ¬2 ≤ st[X] All goals completed! 🐙 m:Nat⊢ ∀ (st : State), parity st[X] = parity m → 2 ≤ st["X"] → parity (st["X"] - 2) = parity m m:Natst:Stateh:parity st[X] = parity mhle:2 ≤ st["X"]⊢ parity (st["X"] - 2) = parity m m:Natst:Stateh:parity st[X] = parity mhle:2 ≤ st["X"]⊢ 2 ≤ st["X"] All goals completed! 🐙 def sqrtDec (m : Nat) : Decorated where pre := ({{ X = m }}) body := sdcom { Z := 0; while ((Z + 1) * (Z + 1) ≤ X) do {{ X = m ∧ Z * Z ≤ m }} Z := Z + 1 end } post := ({{ Z * Z ≤ m ∧ m < (Z + 1) * (Z + 1) }}) theorem sqrt_correct (m : Nat) : (sqrtDec m).OuterTripleValid := m:Nat⊢ (sqrtDec m).OuterTripleValid m:Nat⊢ { pre := {{X = m}}, body := sdcom { Z := 0; while ((Z + 1) * (Z + 1) ≤ X) do {{X = m ∧ Z * Z ≤ m}} Z := Z + 1 end }, post := {{Z * Z ≤ m ∧ m < (Z + 1) * (Z + 1)}} }.OuterTripleValid All goals completed! 🐙 def squareDec (m : Nat) : Decorated where pre := ({{ X = m }}) body := sdcom { Y := X; Z := 0; while (Y ≠ 0) do {{ Z + X * Y = m * m }} Z := Z + X; Y := Y - 1 end } post := ({{ Z = m * m }}) theorem square_outer_triple_valid (m : Nat) : (squareDec m).OuterTripleValid := m:Nat⊢ (squareDec m).OuterTripleValid m:Nat⊢ { pre := {{X = m}}, body := sdcom { Y := X; Z := 0; while (Y ≠ 0) do {{Z + X * Y = m * m}} Z := Z + X; Y := Y - 1 end }, post := {{Z = m * m}} }.OuterTripleValid m:Nat⊢ ∀ (st : State), st[Z] + st[X] * st[Y] = m * m → ¬st["Y"] = 0 → st["Z"] + st["X"] + st[X] * (st["Y"] - 1) = m * m -- loop invariant preserved m:Natst:Stateh:st[Z] + st[X] * st[Y] = m * mhy:¬st["Y"] = 0⊢ st["Z"] + st["X"] + st[X] * (st["Y"] - 1) = m * m m:Natst:Statey:Nath:st[Z] + st[X] * y = m * mhy:¬y = 0⊢ st["Z"] + st["X"] + st[X] * (y - 1) = m * m cases y with m:Natst:Stateh:st[Z] + st[X] * 0 = m * mhy:¬0 = 0⊢ st["Z"] + st["X"] + st[X] * (0 - 1) = m * m All goals completed! 🐙 m:Natst:Statey:Nath:st[Z] + st[X] * (y + 1) = m * mhy:¬y + 1 = 0⊢ st["Z"] + st["X"] + st[X] * (y + 1 - 1) = m * m m:Natst:Statey:Nath:st[Z] + st[X] * (y + 1) = m * mhy:¬y + 1 = 0⊢ st["Z"] + st["X"] + st[X] * y = m * m m:Natst:Statey:Nath:st[Z] + (st[X] * y + st[X]) = m * mhy:¬y + 1 = 0⊢ st["Z"] + st["X"] + st[X] * y = m * m All goals completed! 🐙 def squareDec' (n : Nat) : Decorated where pre := ({{ True }}) body := sdcom { X := ~(Aexp.num n); Y := X; Z := 0; while (Y ≠ 0) do {{ Z = X * (X - Y) ∧ X = n ∧ Y ≤ X }} Z := Z + X; Y := Y - 1 end } post := ({{ Z = n * n }}) theorem square_dec'_correct (n : Nat) : (squareDec' n).OuterTripleValid := n:Nat⊢ (squareDec' n).OuterTripleValid n:Nat⊢ { pre := {{True}}, body := sdcom { X := ~(Aexp.num n); Y := X; Z := 0; while (Y ≠ 0) do {{Z = X * (X - Y) ∧ X = n ∧ Y ≤ X}} Z := Z + X; Y := Y - 1 end }, post := {{Z = n * n}} }.OuterTripleValid n:Nat⊢ ∀ (st : State), st[Z] = st[X] * (st[X] - st[Y]) → st[X] = n → st[Y] ≤ st[X] → st["Y"] = 0 → st[Z] = n * nn:Nat⊢ ∀ (st : State), st[Z] = st[X] * (st[X] - st[Y]) → st[X] = n → st[Y] ≤ st[X] → ¬st["Y"] = 0 → st["Z"] + st["X"] = st[X] * (st[X] - (st["Y"] - 1)) ∧ st[X] = n ∧ st["Y"] ≤ st[X] + 1 n:Nat⊢ ∀ (st : State), st[Z] = st[X] * (st[X] - st[Y]) → st[X] = n → st[Y] ≤ st[X] → st["Y"] = 0 → st[Z] = n * n n:Natst:Statehz:st[Z] = st[X] * (st[X] - st[Y])hx:st[X] = na✝:st[Y] ≤ st[X]hy:st["Y"] = 0⊢ st[Z] = n * n All goals completed! 🐙 n:Nat⊢ ∀ (st : State), st[Z] = st[X] * (st[X] - st[Y]) → st[X] = n → st[Y] ≤ st[X] → ¬st["Y"] = 0 → st["Z"] + st["X"] = st[X] * (st[X] - (st["Y"] - 1)) ∧ st[X] = n ∧ st["Y"] ≤ st[X] + 1 -- loop invariant preserved n:Natst:Statehz:st[Z] = st[X] * (st[X] - st[Y])hx:st[X] = nhle:st[Y] ≤ st[X]hy:¬st["Y"] = 0⊢ st["Z"] + st["X"] = st[X] * (st[X] - (st["Y"] - 1)) ∧ st[X] = n ∧ st["Y"] ≤ st[X] + 1 n:Natst:Statehz:st[Z] = st[X] * (st[X] - st[Y])hx:st[X] = nhle:st[Y] ≤ st[X]hy:¬st["Y"] = 0⊢ st["Z"] + st["X"] = st[X] * (st[X] - (st["Y"] - 1))n:Natst:Statehz:st[Z] = st[X] * (st[X] - st[Y])hx:st[X] = nhle:st[Y] ≤ st[X]hy:¬st["Y"] = 0⊢ st[X] = n ∧ st["Y"] ≤ st[X] + 1 n:Natst:Statehz:st[Z] = st[X] * (st[X] - st[Y])hx:st[X] = nhle:st[Y] ≤ st[X]hy:¬st["Y"] = 0⊢ st["Z"] + st["X"] = st[X] * (st[X] - (st["Y"] - 1)) n:Natst:Statehz:st[Z] = st[X] * (st[X] - st[Y])hx:st[X] = nhle:st[Y] ≤ st[X]hy:¬st["Y"] = 0⊢ st[X] * st[X] - st[X] * st[Y] + st["X"] = st[X] * st[X] - (st[X] * st["Y"] - st[X]) n:Natst:Statehz:st[Z] = st[X] * (st[X] - st[Y])hx:st[X] = nhle:st[Y] ≤ st[X]hy:¬st["Y"] = 0hxy:st[X] * st[Y] ≤ st[X] * st[X]⊢ st[X] * st[X] - st[X] * st[Y] + st["X"] = st[X] * st[X] - (st[X] * st["Y"] - st[X]) n:Natst:Statehz:st[Z] = st[X] * (st[X] - st[Y])hx:st[X] = nhle:st[Y] ≤ st[X]hy:¬st["Y"] = 0hxy:st[X] * st[Y] ≤ st[X] * st[X]hx':st[X] ≤ st[X] * st[Y]⊢ st[X] * st[X] - st[X] * st[Y] + st["X"] = st[X] * st[X] - (st[X] * st["Y"] - st[X]) All goals completed! 🐙 n:Natst:Statehz:st[Z] = st[X] * (st[X] - st[Y])hx:st[X] = nhle:st[Y] ≤ st[X]hy:¬st["Y"] = 0⊢ st[X] = n ∧ st["Y"] ≤ st[X] + 1 All goals completed! 🐙 def squareSimplerDec (m : Nat) : Decorated where pre := ({{ X = m }}) body := sdcom { Y := 0; Z := 0; while (Y ≠ X) do {{ Z = Y * m ∧ X = m }} Z := Z + X; Y := Y + 1 end } post := ({{ Z = m * m }}) theorem square_simpler_outer_triple_valid (m : Nat) : (squareSimplerDec m).OuterTripleValid := m:Nat⊢ (squareSimplerDec m).OuterTripleValid m:Nat⊢ { pre := {{X = m}}, body := sdcom { Y := 0; Z := 0; while (Y ≠ X) do {{Z = Y * m ∧ X = m}} Z := Z + X; Y := Y + 1 end }, post := {{Z = m * m}} }.OuterTripleValid All goals completed! 🐙 def twoLoopsDec (a b c : Nat) : Decorated where pre := ({{ True }}) body := sdcom { X := 0; Y := 0; Z := ~(Aexp.num c); (while (X ≠ ~(Aexp.num a)) do {{ Z = X + c ∧ Y = 0 }} X := X + 1; Z := Z + 1 end); while (Y ≠ ~(Aexp.num b)) do {{ Z = a + Y + c }} Y := Y + 1; Z := Z + 1 end } post := ({{ Z = a + b + c }}) theorem two_loops_correct (a b c : Nat) : (twoLoopsDec a b c).OuterTripleValid := a:Natb:Natc:Nat⊢ (twoLoopsDec a b c).OuterTripleValid a:Natb:Natc:Nat⊢ { pre := {{True}}, body := sdcom { X := 0; Y := 0; Z := ~(Aexp.num c); while (X ≠ ~(Aexp.num a)) do {{Z = X + c ∧ Y = 0}} X := X + 1; Z := Z + 1 end; while (Y ≠ ~(Aexp.num b)) do {{Z = a + Y + c}} Y := Y + 1; Z := Z + 1 end }, post := {{Z = a + b + c}} }.OuterTripleValid All goals completed! 🐙 def subtractSlowlyDec (m p : Nat) : Decorated where pre := ({{ X = m ∧ Z = p }}) body := sdcom { while (X ≠ 0) do {{ Z - X = p - m }} Z := Z - 1; X := X - 1 end } post := ({{ Z = p - m }}) theorem subtract_slowly_correct (m p : Nat) : (subtractSlowlyDec m p).OuterTripleValid := m:Natp:Nat⊢ (subtractSlowlyDec m p).OuterTripleValid m:Natp:Nat⊢ { pre := {{X = m ∧ Z = p}}, body := sdcom { while (X ≠ 0) do {{Z - X = p - m}} Z := Z - 1; X := X - 1 end }, post := {{Z = p - m}} }.OuterTripleValid All goals completed! 🐙 def dpow2Down (n : Nat) : Decorated where pre := ({{ True }}) body := sdcom { X := 0; Y := 1; Z := 1; while (X ≠ ~(Aexp.num n)) do {{ Y = pow2 (X + 1) - 1 ∧ Z = pow2 X }} Z := 2 * Z; Y := Y + Z; X := X + 1 end } post := ({{ Y = pow2 (n + 1) - 1 }}) theorem dpow2_down_correct (n : Nat) : (dpow2Down n).OuterTripleValid := n:Nat⊢ (dpow2Down n).OuterTripleValid n:Nat⊢ { pre := {{True}}, body := sdcom { X := 0; Y := 1; Z := 1; while (X ≠ ~(Aexp.num n)) do {{Y = pow2 (X + 1) - 1 ∧ Z = pow2 X}} Z := 2 * Z; Y := Y + Z; X := X + 1 end }, post := {{Y = pow2 (n + 1) - 1}} }.OuterTripleValid n:Nat⊢ ∀ (st : State), st[Y] = pow2 (st[X] + 1) - 1 → st[Z] = pow2 st[X] → ¬st["X"] = n → st["Y"] + 2 * st["Z"] = pow2 (st["X"] + 1 + 1) - 1 ∧ 2 * st["Z"] = pow2 (st["X"] + 1) n:Natst:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st["X"] = n⊢ st["Y"] + 2 * st["Z"] = pow2 (st["X"] + 1 + 1) - 1 ∧ 2 * st["Z"] = pow2 (st["X"] + 1) n:Natst:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st["X"] = n⊢ pow2 (st[X] + 1) - 1 + 2 * pow2 st[X] = pow2 (st["X"] + 1 + 1) - 1 ∧ 2 * pow2 st[X] = pow2 (st["X"] + 1) n:Natst:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st["X"] = n⊢ pow2 (st[X] + 1) - 1 + 2 * pow2 st[X] = pow2 (st["X"] + 1 + 1) - 1n:Natst:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st["X"] = n⊢ 2 * pow2 st[X] = pow2 (st["X"] + 1) n:Natst:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st["X"] = n⊢ pow2 (st[X] + 1) - 1 + 2 * pow2 st[X] = pow2 (st["X"] + 1 + 1) - 1 n:Natst:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st["X"] = n⊢ pow2 st[X] + pow2 st[X] - 1 + 2 * pow2 st[X] = pow2 st["X"] + pow2 st["X"] + (pow2 st["X"] + pow2 st["X"]) - 1 All goals completed! 🐙 n:Natst:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st["X"] = n⊢ 2 * pow2 st[X] = pow2 (st["X"] + 1) n:Natst:Statehy:st[Y] = pow2 (st[X] + 1) - 1hz:st[Z] = pow2 st[X]a✝:¬st["X"] = n⊢ 2 * pow2 st[X] = pow2 st["X"] + pow2 st["X"] All goals completed! 🐙 def factorialDec (m : Nat) : Decorated where pre := ({{ X = m }}) body := sdcom { Y := 1; while (X ≠ 0) do {{ Y * fact X = fact m }} Y := Y * X; X := X - 1 end } post := ({{ Y = fact m }}) theorem factorial_outer_triple_valid (m : Nat) : (factorialDec m).OuterTripleValid := m:Nat⊢ (factorialDec m).OuterTripleValid m:Nat⊢ { pre := {{X = m}}, body := sdcom { Y := 1; while (X ≠ 0) do {{Y * fact X = fact m}} Y := Y * X; X := X - 1 end }, post := {{Y = fact m}} }.OuterTripleValid m:Nat⊢ ∀ (st : State), st[Y] * fact st[X] = fact m → st["X"] = 0 → st[Y] = fact mm:Nat⊢ ∀ (st : State), st[Y] * fact st[X] = fact m → ¬st["X"] = 0 → st["Y"] * st["X"] * fact (st["X"] - 1) = fact m m:Nat⊢ ∀ (st : State), st[Y] * fact st[X] = fact m → st["X"] = 0 → st[Y] = fact m m:Natst:Stateh:st[Y] * fact st[X] = fact mhx:st["X"] = 0⊢ st[Y] = fact m m:Natst:Stateh:st[Y] * fact 0 = fact mhx:st["X"] = 0⊢ st[Y] = fact m m:Natst:Stateh:st[Y] * 1 = fact mhx:st["X"] = 0⊢ st[Y] = fact m All goals completed! 🐙 m:Nat⊢ ∀ (st : State), st[Y] * fact st[X] = fact m → ¬st["X"] = 0 → st["Y"] * st["X"] * fact (st["X"] - 1) = fact m m:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st["X"] = 0⊢ st["Y"] * st["X"] * fact (st["X"] - 1) = fact m m:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st["X"] = 0⊢ st["Y"] * fact st["X"] = fact mm:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st["X"] = 0⊢ st["X"] ≠ 0 m:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st["X"] = 0⊢ st["Y"] * fact st["X"] = fact m All goals completed! 🐙 m:Natst:Stateh:st[Y] * fact st[X] = fact mhne:¬st["X"] = 0⊢ st["X"] ≠ 0 All goals completed! 🐙 def T : Ident := "T" def dfib (n : Nat) : Decorated where pre := ({{ True }}) body := sdcom { X := 1; Y := 1; Z := 1; while (X ≠ ~(Aexp.num (1 + n))) do {{ Z = fib X ∧ Y = fib (Nat.pred X) ∧ X > 0 }} T := Z; Z := Z + Y; Y := T; X := 1 + X end } post := ({{ Y = fib n }}) theorem dfib_correct (n : Nat) : (dfib n).OuterTripleValid := n:Nat⊢ (dfib n).OuterTripleValid n:Nat⊢ { pre := {{True}}, body := sdcom { X := 1 }.seq (sdcom { Y := 1 }.seq (sdcom { Z := 1 }.seq (DCom.whileDo (bexp {X ≠ ~(Aexp.num (1 + n))}) ({{Z = fib X ∧ Y = fib (Nat.pred X) ∧ X > 0}}) ((DCom.asgn "T" (aexp {Z})).seq (sdcom { Z := Z + Y; Y := T; X := 1 + X }))))), post := {{Y = fib n}} }.OuterTripleValid n:Nat⊢ ∀ (st : State), st[Z] = fib st[X] → st[Y] = fib (st[X] - 1) → 0 < st[X] → st["X"] = 1 + n → st[Y] = fib nn:Nat⊢ ∀ (st : State), st[Z] = fib st[X] → st[Y] = fib (st[X] - 1) → 0 < st[X] → ¬st["X"] = 1 + n → st["Z"] + st["Y"] = fib (1 + st["X"]) ∧ st["Z"] = fib st["X"] ∧ 0 < 1 + st["X"] n:Nat⊢ ∀ (st : State), st[Z] = fib st[X] → st[Y] = fib (st[X] - 1) → 0 < st[X] → st["X"] = 1 + n → st[Y] = fib n n:Natst:Statea✝¹:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)a✝:0 < st[X]hx:st["X"] = 1 + n⊢ st[Y] = fib n n:Natst:Statea✝¹:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)a✝:0 < st[X]hx:st["X"] = 1 + n⊢ fib (1 + n - 1) = fib n All goals completed! 🐙 n:Nat⊢ ∀ (st : State), st[Z] = fib st[X] → st[Y] = fib (st[X] - 1) → 0 < st[X] → ¬st["X"] = 1 + n → st["Z"] + st["Y"] = fib (1 + st["X"]) ∧ st["Z"] = fib st["X"] ∧ 0 < 1 + st["X"] n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st["X"] = 1 + n⊢ st["Z"] + st["Y"] = fib (1 + st["X"]) ∧ st["Z"] = fib st["X"] ∧ 0 < 1 + st["X"] n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st["X"] = 1 + n⊢ fib st[X] + fib (st[X] - 1) = fib (1 + st["X"]) ∧ fib st[X] = fib st["X"] ∧ 0 < 1 + st["X"] n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st["X"] = 1 + n⊢ fib st[X] + fib (st[X] - 1) = fib (1 + st["X"])n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st["X"] = 1 + n⊢ fib st[X] = fib st["X"] ∧ 0 < 1 + st["X"] n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st["X"] = 1 + n⊢ fib st[X] + fib (st[X] - 1) = fib (1 + st["X"]) n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st["X"] = 1 + n⊢ st[X] > 0 All goals completed! 🐙 n:Natst:Statehz:st[Z] = fib st[X]hy:st[Y] = fib (st[X] - 1)hx:0 < st[X]a✝:¬st["X"] = 1 + n⊢ fib st[X] = fib st["X"] ∧ 0 < 1 + st["X"] All goals completed! 🐙 end SparseAnnotations

6.4. Weakest Preconditions🔗

Note to developers

HIDE: BCP 21: We talked about moving this stuff to the HoareAsLogic chapter to lighten this chapter, but it fits awkwardly there, so I'm leaving it here. It's optional anyway. We might consider assigning one of the exercises as advanced-only though.

Some preconditions are more interesting than others. For example, the Hoare triple

{{ False }}  X := Y + 1  {{ X ≤ 5 }}

is not very interesting: although it is perfectly valid, it tells us nothing useful. Since the precondition isn't satisfied by any state, it doesn't describe any situations where we can use the command X := Y + 1 to achieve the postcondition X ≤ 5.

By contrast,

{{ Y ≤ 4 ∧ Z = 0 }}  X := Y + 1 {{ X ≤ 5 }}

has a useful precondition: it tells us that, if we can somehow create a situation in which we know that Y ≤ 4 ∧ Z = 0, then running this command will produce a state satisfying the postcondition. However, this precondition is not as useful as it could be, because the Z = 0 clause in the precondition actually has nothing to do with the postcondition X ≤ 5.

The most useful precondition for this command is this one:

{{ Y ≤ 4 }}  X := Y + 1  {{ X ≤ 5 }}

The assertion Y ≤ 4 is called the weakest precondition of X := Y + 1 with respect to the postcondition X ≤ 5.

Assertion Y ≤ 4 is a weakest precondition of command X := Y + 1 with respect to postcondition X ≤ 5. Think of weakest here as meaning "easiest to satisfy": a weakest precondition is one that as many states as possible can satisfy.

p is a weakest precondition of command c for postcondition q if

  • p is a precondition, that is, {{p}} c {{q}}; and

  • p is at least as weak as all other preconditions, that is, if {{p'}} c {{q}} then p' ↠ p.

Note that weakest preconditions need not be unique. For example, Y ≤ 4 was a weakest precondition above, but so are the logically equivalent assertions Y < 5, Y ≤ 2 * 2, etc. It is easy to show that any two weakest preconditions p and p' of a command c with respect to postcondition q are logically equivalent; that is, p ↞↠ p'.

def IsWp (p : Assertion) (c : Com) (q : Assertion) : Prop := ValidHoareTriple p c q ∧ ∀ p' : Assertion, {{ p' }} c {{ q }} → p' ↠ p theorem isWp_def {p : Assertion} {c : Com} {q : Assertion} : IsWp p c q ↔ ValidHoareTriple p c q ∧ ∀ p' : Assertion, {{ p' }} c {{ q }} → p' ↠ p := p:Assertionc:Comq:Assertion⊢ IsWp p c q ↔ ValidHoareTriple p c q ∧ ∀ (p' : Assertion), {{p'}} ~c {{q}} → p' ↠ p All goals completed! 🐙
Quiz

What are weakest preconditions of the following commands for the following postconditions?

  1. {{ ? }} skip {{ X = 5 }}

  2. {{ ? }} X := Y + Z {{ X = 5 }}

  3. {{ ? }} X := Y {{ X = Y }}

  4. {{ ? }}
    if X = 0 then Y := Z + 1 else Y := W + 2 end
    {{ Y = 5 }}
    
  5. {{ ? }} X := 5 {{ X = 0 }}

  6. {{ ? }}
    while (true) {X := 0}
    {{ X = 0 }}
    
Show solution
  1. X = 5

  2. Y + Z = 5

  3. True

  4. (X = 0 ∧ Z = 4) ∨ (X ≠ 0 ∧ W = 3)

  5. False

  6. True

Exercise★★★(is_wp) (Advanced, Optional)

Prove formally, using the definition of ValidHoareTriple, that Y ≤ 4 is indeed a weakest precondition of X := Y + 1 with respect to postcondition X ≤ 5.

theorem is_wp_example : IsWp ({{ Y ≤ 4 }}) (imp {X := Y + 1}) ({{ X ≤ 5 }}) := ⊢ IsWp ({{Y ≤ 4}}) (imp {X := Y + 1}) ({{X ≤ 5}}) solution! ⊢ ValidHoareTriple ({{Y ≤ 4}}) (imp {X := Y + 1}) ({{X ≤ 5}}) ∧ ∀ (p' : Assertion), {{p'}} X := Y + 1 {{X ≤ 5}} → p' ↠ {{Y ≤ 4}} ⊢ ValidHoareTriple ({{Y ≤ 4}}) (imp {X := Y + 1}) ({{X ≤ 5}})⊢ ∀ (p' : Assertion), {{p'}} X := Y + 1 {{X ≤ 5}} → p' ↠ {{Y ≤ 4}} ⊢ ValidHoareTriple ({{Y ≤ 4}}) (imp {X := Y + 1}) ({{X ≤ 5}}) -- precondition ⊢ {{?left.P'}} X := Y + 1 {{X ≤ 5}}⊢ {{Y ≤ 4}} ↠ ?left.P'⊢ Assertion ⊢ {{?left.P'}} X := Y + 1 {{X ≤ 5}} All goals completed! 🐙 ⊢ {{Y ≤ 4}} ↠ (X ≤ 5) [X ↦ Y + 1] All goals completed! 🐙 ⊢ ∀ (p' : Assertion), {{p'}} X := Y + 1 {{X ≤ 5}} → p' ↠ {{Y ≤ 4}} -- weakest precondition p':Assertionhtriple:{{p'}} X := Y + 1 {{X ≤ 5}}⊢ p' ↠ {{Y ≤ 4}} p':Assertionhtriple:∀ {st st' : State}, (st =[ X := Y + 1 ]=> st') → p' st → st'[X] ≤ 5⊢ p' ↠ {{Y ≤ 4}} p':Assertionhtriple:∀ {st st' : State}, (st =[ X := Y + 1 ]=> st') → p' st → st'[X] ≤ 5⊢ ∀ (st : State), p' st → st[Y] ≤ 4 p':Assertionhtriple:∀ {st st' : State}, (st =[ X := Y + 1 ]=> st') → p' st → st'[X] ≤ 5st:Statehp':p' st⊢ st[Y] ≤ 4 p':Assertionhtriple:∀ {st st' : State}, (st =[ X := Y + 1 ]=> st') → p' st → st'[X] ≤ 5st:Statehp':p' sthst:st =[ X := Y + 1 ]=> X →ₜ st[Y] + 1 ; st⊢ st[Y] ≤ 4 p':Assertionst:Statehtriple:(X →ₜ st[Y] + 1 ; st)[X] ≤ 5hp':p' sthst:st =[ X := Y + 1 ]=> X →ₜ st[Y] + 1 ; st⊢ st[Y] ≤ 4 p':Assertionst:Statehtriple:(X →ₜ st[Y] + 1 ; st)[X] ≤ 5hp':p' sthst:st =[ X := Y + 1 ]=> X →ₜ st[Y] + 1 ; st⊢ st[Y] ≤ 4 p':Assertionst:Statehp':p' sthst:st =[ X := Y + 1 ]=> X →ₜ st[Y] + 1 ; sthtriple:st[Y] ≤ 4⊢ st[Y] ≤ 4 All goals completed! 🐙
Exercise★★(hoare_asgn_weakest) (Advanced, Optional)

Show that the precondition in the rule hoare_asgn is in fact the weakest precondition.

theorem hoare_asgn_weakest (q : Assertion) (x : Ident) (a : Aexp) : IsWp ({{ q [x ↦ a] }}) (imp {x := a}) q := q:Assertionx:Identa:Aexp⊢ IsWp ({{q [x ↦ a]}}) (imp {x := a}) q solution! q:Assertionx:Identa:Aexp⊢ ValidHoareTriple ({{q [x ↦ a]}}) (imp {x := a}) q ∧ ∀ (p' : Assertion), {{p'}} x := a {{q}} → p' ↠ {{q [x ↦ a]}} q:Assertionx:Identa:Aexp⊢ ValidHoareTriple ({{q [x ↦ a]}}) (imp {x := a}) qq:Assertionx:Identa:Aexp⊢ ∀ (p' : Assertion), {{p'}} x := a {{q}} → p' ↠ {{q [x ↦ a]}} q:Assertionx:Identa:Aexp⊢ ValidHoareTriple ({{q [x ↦ a]}}) (imp {x := a}) q All goals completed! 🐙 q:Assertionx:Identa:Aexp⊢ ∀ (p' : Assertion), {{p'}} x := a {{q}} → p' ↠ {{q [x ↦ a]}} q:Assertionx:Identa:Aexpp:AssertionhP:{{p}} x := a {{q}}⊢ p ↠ {{q [x ↦ a]}} q:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'⊢ p ↠ {{q [x ↦ a]}} q:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'⊢ ∀ (st : State), p st → q [x ↦ a] st q:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'st:Statehst:p st⊢ q [x ↦ a] st q:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'st:Statehst:p st⊢ q (x →ₜ Aexp.eval st a ; st) q:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'st:Statehst:p st⊢ ?right.st =[ x := a ]=> x →ₜ Aexp.eval st a ; stq:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'st:Statehst:p st⊢ p ?right.stq:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'st:Statehst:p st⊢ State q:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'st:Statehst:p st⊢ ?right.st =[ x := a ]=> x →ₜ Aexp.eval st a ; st q:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'st:Statehst:p st⊢ Aexp.eval st a = Aexp.eval st a All goals completed! 🐙 q:Assertionx:Identa:Aexpp:AssertionhP:∀ {st st' : State}, (st =[ x := a ]=> st') → p st → q st'st:Statehst:p st⊢ p st All goals completed! 🐙
Exercise★★(hoare_havoc_weakest) (Advanced, Optional)

Show that your havoc_pre function from the himp_hoare exercise in the Hoare chapter returns a weakest precondition.

namespace HimpHoare2 open HimpHoare theorem validHoareTriple_def' {P : Assertion} {c : HimpHoare.Com} {Q : Assertion} : HimpHoare.ValidHoareTriple P c Q ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' := P:Assertionc:HimpHoare.ComQ:Assertion⊢ HimpHoare.ValidHoareTriple P c Q ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' All goals completed! 🐙 theorem hoare_havoc_weakest (p q : Assertion) (x : Ident) (h : ValidHoareTriple p (Com.havoc x) q) : p ↠ havoc_pre x q := p:Assertionq:Assertionx:Identh:HimpHoare.ValidHoareTriple p (imp {havoc x}) q⊢ p ↠ havoc_pre x q solution! p:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'⊢ p ↠ havoc_pre x q p:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'⊢ ∀ (st : State), p st → havoc_pre x q st p:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'st:Statehp:p st⊢ havoc_pre x q st p:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'st:Statehp:p st⊢ ∀ (n : Nat), ({{q [x ↦ ~(Aexp.num n)]}}) st p:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'st:Statehp:p stn:Nat⊢ q [x ↦ ~(Aexp.num n)] st p:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'st:Statehp:p stn:Nat⊢ q (x →ₜ n ; st) p:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'st:Statehp:p stn:Nat⊢ ?st =[ havoc x ]=> x →ₜ n ; stp:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'st:Statehp:p stn:Nat⊢ p ?stp:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'st:Statehp:p stn:Nat⊢ State p:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'st:Statehp:p stn:Nat⊢ ?st =[ havoc x ]=> x →ₜ n ; st All goals completed! 🐙 p:Assertionq:Assertionx:Identh:∀ {st st' : State}, (st =[ havoc x ]=> st') → p st → q st'st:Statehp:p stn:Nat⊢ p st All goals completed! 🐙 end HimpHoare2
Source revision: 4432bd0, committed 2026-10-24 18:24 UTC