Hoare Logic

5. Hoare: Hoare Logic, Part I🔗

Note to developers (Benjamin Pierce @bcpierce00, before next release, 2025)

There is an excellent and fairly polished problem on a Hoare Logic for a little assembly language in the materials for the 2025 CIS 5000 final exam at Penn. We should turn it into an exercise in this chapter!

Note to developers (Benjamin Pierce @bcpierce00, before next release, 2021)

Any chance we could move the (awkwardly placed) weakest precondition discussion to this chapter instead?

The terse version of the chapter needs serious work — it has gotten quite ragged after a bunch of reorganization of the chapter over the past couple years. BCP 23: Did some work on it. Bit better now. But the notation issues make everything a bit heavy.

Note to developers
HIDE: What about typesetting multi-line triples as
{{ P }}
   c
{{ Q }}
instead of
  {{ P }}
c
  {{ Q }}
when we print them?
Note to developers (Mike Hicks @mwhicks1, 2026)

The terse version of this chapter is not sufficiently terse, IMO. Too much explanation in the text itself. When going through this in class I found myself scrolling through a lot of the text that is shown to get to the good parts.

In the Imp and Equiv chapters, we built up the mathematical machinery for talking about Imp programs precisely — an evaluation relation giving their operational semantics, and a notion of behavioral equivalence for judging when two programs do the same thing. We now turn to a different kind of question: whether a single program behaves the way we intend.

Our goal in this chapter is to develop the tools for simple program verification: using the precise definition of Imp to prove, formally, that particular programs satisfy particular specifications of their behavior. We'll develop a reasoning system called Floyd-Hoare Logic — usually shortened to Hoare Logic — that equips each syntactic construct of Imp with a generic "proof rule," so that the structure of a correctness proof mirrors the structure of the program it is about. First developed in the 1960s, Hoare Logic remains the basis of a multitude of tools used in academia and industry to specify and verify real software systems.

Hoare Logic combines two beautiful ideas: a natural way of writing down specifications of programs, and a structured proof technique for proving that programs are correct with respect to such specifications — where by "structured" we mean that the structure of proofs directly mirrors the structure of the programs that they are about.

5.1. Assertions🔗

An assertion is a logical claim about the state of a program's memory — formally, a predicate of States.

open scoped Com MyGetElem KVPair open Com abbrev Assertion := State → Prop

For example,

  • fun st => st[X] = 3 holds for states st in which the value of X is 3,

  • fun st => True holds for all states, and

  • fun st => False holds for no states.

Quiz

Paraphrase the following assertions in English (i.e., say which states satisfy them)

(A) fun st => st[X] ≤ st[Y]

(B) fun st => st[X] = 3 ∨ st[X] ≤ st[Y]

(C) fun st => st[Z] * st[Z] ≤ st[X] ∧ ¬ ((st[Z] + 1) * (st[Z] + 1) ≤ st[X])

Exercise★(assertions) (Optional)

Paraphrase the following assertions in English (or your favorite natural language).

namespace ExAssertions def assertion1 : Assertion := fun st => st[X] ≤ st[Y] def assertion2 : Assertion := fun st => st[X] = 3 ∨ st[X] ≤ st[Y] def assertion3 : Assertion := fun st => st[Z] * st[Z] ≤ st[X] ∧ ¬ ((st[Z] + 1) * (st[Z] + 1) ≤ st[X]) def assertion4 : Assertion := fun st => st[Z] = max st[X] st[Y]
  1. The value of X is less than or equal to the value of Y.

  2. The value of X is 3 or is less than or equal to the value of Y.

  3. The value of Z is the integer square root of X.

  4. The value of Z is the greater of the values of X and Y.

end ExAssertions

5.1.1. Notations for Assertions🔗

This way of writing assertions can be a little bit heavy, for two reasons: (1) every single assertion that we ever write is going to begin with fun st => ; and (2) this state st is the only one that we ever use to look up variables in assertions (we will almost never need to talk about two different memory states at the same time). For discussing examples informally, we'll adopt some simplifying conventions: we'll drop the initial fun st =>, and we'll write just X to mean st[X]. Thus, instead of writing

fun st => st[X] = m

we'll write just

{{ X = m }}.

Here the "doubly curly" braces {{ and }} delimit the scope of an assertion. We'll see more examples below.

This example also illustrates a convention that we'll use throughout the Hoare Logic chapters: in informal assertions, capital letters like X, Y, and Z are Imp variables, while lowercase letters like x, y, m, and n are ordinary Lean variables. This is why, when translating from informal to formal, we replace X with st[X] but leave m alone.

The convention described above can be implemented with a little syntax magic, much as we did with the imp { … } notation in Imp. This new notation automatically lifts Aexps, numbers, and Props into Assertions when they appear between the {{ _ }} brackets.

There is no need to understand the details of how these notations work, so we have tucked them away in a collapsible block below.

Notation: Assertionsnamespace Assertion open Lean Elab Term Meta Imp.Elab scoped syntax:max "assn(" ident "; " term ")" : term scoped syntax:lead "{{" term "}}" : term -- `: Assertion` guards that the resulting type is `State → Prop`. macro_rules | `({{ $t }}) => `((fun st : _root_.State => assn(st; $t) : Assertion)) macro_rules | `(assn($st; $t)) => do let result ← match t with | `(($P)) => ``((assn($st; $P))) | `($l = $r) => ``(assn($st; $l) = assn($st; $r)) | `($l + $r) => ``(assn($st; $l) + assn($st; $r)) | `($l - $r) => ``(assn($st; $l) - assn($st; $r)) | `($l * $r) => ``(assn($st; $l) * assn($st; $r)) | `($l ≤ $r) => ``(assn($st; $l) ≤ assn($st; $r)) | `($l < $r) => ``(assn($st; $l) < assn($st; $r)) | `($l ≥ $r) => ``(assn($st; $l) ≥ assn($st; $r)) | `($l > $r) => ``(assn($st; $l) > assn($st; $r)) | `($l ∧ $r) => ``(assn($st; $l) ∧ assn($st; $r)) | `($l ∨ $r) => ``(assn($st; $l) ∨ assn($st; $r)) | `($l → $r) => ``(assn($st; $l) → assn($st; $r)) | `($l ↔ $r) => ``(assn($st; $l) ↔ assn($st; $r)) | `(¬ $p) => ``(¬ assn($st; $p)) | `($f $args*) => do let mut result := f for arg in args do result ← `($result assn($st; $arg)) pure result | _ => Macro.throwUnsupported return withSourceInfoOf t result elab_rules : term | `(assn($st; $t:term)) => do let t ← elabTerm t none let ty ← whnf (← inferType t) tryPostponeIfMVar ty let st ← elabTerm st none match_expr ty with | String => mkAppM ``_root_.MyGetElem.getElem #[st, t] | Aexp => mkAppM ``Aexp.eval #[st, t] | Bexp => mkAppM ``Bexp.eval #[st, t] | _ => match ty with | .forallE _ domain body _ => if body.isProp && (← isDefEq domain (mkConst ``_root_.State)) then pure <| mkApp t st else pure t | _ => pure t
Note to developers (Niklas Halonen @xhalo32)

Mention (don't explain macro hygiene though) why

#check {{ st[X] = st[Y] }}

doesn't work, but instead one should write

#check {{ fun st => st[X] = st[Y] }}

And mention that when inside the brackets, one sees in the infoview

st✝ : State

but outside the brackets, one sees fun st => st[X] = st[X] : State → Prop

Also: should we introduce the terminology "pure" for embedding propositions into assertions that are constant functions?

end Assertion open scoped Assertion

Function applications inside assertions automatically interpret their arguments in the current state. Thus, {{ f e1 ... en }} stands for fun st => f (e1 st) ... (en st).

Occasionally it is simpler to write an assertion directly as a Lean function. A fun st => … can be placed inside the assertion notation without an escape marker, and so can the name of an assertion.

For example, {{ fun st => ∀ x, st[x] = 0 }} indicates an assertion that every variable maps to 0 in the given state.

(An assertion obtained by applying a function to arguments, say f x y, must be written as fun st => f x y st, since the notation would otherwise interpret x and y in the current state. We will see an example in the havoc exercise at the end of the chapter.)

Notation encoding: printing assertions back

As in the Imp chapter, the assertion notation above is input only: Lean reads {{ X ≤ 5 }} but still prints the underlying function by default. The delaborators below close the loop for plain assertions: a state lambda whose body Lean can rebuild is printed back in {{ … }} notation, and an assertion Lean cannot rebuild falls back to the raw fun st => … form, which is exactly this notation's escape syntax, so what you see is always valid input. Each time a new notation involving assertions appears below (implication, Hoare triples, substitution), a small delaborator defined next to it will extend this printing to cover it. As before, there is no need to understand the details.

namespace Assertion.Delab open Lean PrettyPrinter Delaborator SubExpr Imp.Elab Imp.Delab private def getAssn (stx : Term) : Term := withSourceInfoOf (canonical := false) stx <| Unhygienic.run do match stx with | `({{ $P }}) => return P | _ => return stx /-- Rebuild the surface form of an assertion body, undoing the state threading the `assn` elaborator performs: `st[X]` prints as `X`, `Aexp.eval st a` as `a`, `Bexp.eval st b = true` as `b`, an applied assertion `P st` as `P`, and a subterm that does not mention the state prints as itself. -/ partial def delabBody (stId : FVarId) : DelabM Term := do let e ← getExpr if !e.containsFVar stId then delab else match_expr e with | MyGetElem.getElem _ _ _ _ st k => guard (st == .fvar stId) if let .lit (.strVal s) := k then `($(mkIdent (Name.mkSimple s)):ident) else withAppArg delab | Aexp.eval st _ => guard (st == .fvar stId) withAppArg delab | HAdd.hAdd _ _ _ _ _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) + $(← withAppArg (delabBody stId))) | HSub.hSub _ _ _ _ _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) - $(← withAppArg (delabBody stId))) | HMul.hMul _ _ _ _ _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) * $(← withAppArg (delabBody stId))) | Eq _ l r => -- `Bexp.eval st b = true` is the threaded form of a bare -- boolean `b` if r.isConstOf ``Bool.true && l.isAppOfArity ``Bexp.eval 2 && l.appFn!.appArg! == .fvar stId then withAppFn <| withAppArg <| withAppArg delab else `($(← withAppFn <| withAppArg (delabBody stId)) = $(← withAppArg (delabBody stId))) | Ne _ _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) ≠ $(← withAppArg (delabBody stId))) | LE.le _ _ _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) ≤ $(← withAppArg (delabBody stId))) | LT.lt _ _ _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) < $(← withAppArg (delabBody stId))) | GE.ge _ _ _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) ≥ $(← withAppArg (delabBody stId))) | GT.gt _ _ _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) > $(← withAppArg (delabBody stId))) | And _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) ∧ $(← withAppArg (delabBody stId))) | Or _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) ∨ $(← withAppArg (delabBody stId))) | Iff _ _ => `($(← withAppFn <| withAppArg (delabBody stId)) ↔ $(← withAppArg (delabBody stId))) | Not _ => `(¬ $(← withAppArg (delabBody stId))) | _ => if e.isArrow then `($(← withBindingDomain (delabBody stId)) → $(← withBindingBody `h (delabBody stId))) else if let .app f v := e then if v == .fvar stId && !f.containsFVar stId then -- an applied assertion `P st` (or an applied escape -- lambda); the state applied to anything else (say -- `Result.normal st`) is not an assertion, so the whole -- lambda falls back to raw printing let fty ← Meta.whnfR (← Meta.inferType f) guard <| fty.isArrow && fty.bindingBody!.isProp guard <| ← Meta.isDefEq fty.bindingDomain! (mkConst ``_root_.State) if f.isLambda then -- an applied escape lambda `(fun st' => …) st`, which is -- what substituting a concrete assertion for a variable -- leaves behind: print its body with `st` in place of -- `st'` descend (f.bindingBody!.instantiate1 v) 0 (delabBody stId) else -- only a name or a substitution reads back the same -- inside the braces: any other applied term (say -- `havoc_pre x Q st`) would have the state threaded -- through its arguments, so it keeps the escape form guard <| f.isFVar || f.isConst || f.isMVar || f.isAppOf `Assertion.subst withAppFn delab else `($(← withAppFn (delabBody stId)) $(← withAppArg (delabBody stId))) else failure /-- Print an `Assertion`-valued term as it appears inside `{{ … }}`: a state lambda is un-threaded; a term the printer cannot rebuild falls back to the lambda itself, which is exactly this notation's escape form. An applied lambda at the head of the body, `fun st => (fun st' => …) st`, is reduced first so that the escape form stays a single lambda. -/ partial def delabAssn : DelabM Term := do let e ← getExpr if e.isLambda then let e := e.updateLambdaE! e.bindingDomain! e.bindingBody!.headBeta descend e 0 do (withBindingBody' `st (pure ·.fvarId!) fun stId => delabBody stId) <|> Delaborator.delab else delab /-- Print an assertion-position argument: a state lambda gets the `{{ … }}` notation; any other term (a named assertion, a substitution) already reads well bare. -/ def delabAssnArg (i : Nat) : DelabM Term := do if (← withNaryArg i getExpr).isLambda then `({{ $(← withNaryArg i delabAssn) }}) else withNaryArg i Delaborator.delab /-- Print a bare assertion lambda in `{{ … }}` notation. Keyed on lambdas at large, so the guards bail out cheaply unless the binder is a `State` and the body is a proposition the printer can rebuild. -/ @[delab lam] def delabAssertion : Delab := whenPPOption getPPNotation do let e ← getExpr guard <| e.isLambda && e.bindingDomain!.isConstOf ``_root_.State let P ← withBindingBody' `st (pure ·.fvarId!) fun stId => do guard (← Meta.inferType (← getExpr)).isProp delabBody stId `({{ $P }}) /-- An existential over states, `∃ st, …`, is printed as a binder rather than as `Exists {{ … }}`: its body is a state lambda, but not an assertion. -/ @[delab app.Exists] def delabExistsState : Delab := whenPPOption getPPNotation do let e ← getExpr guard <| e.isAppOfArity ``Exists 2 let lam := e.appArg! guard <| lam.isLambda && lam.bindingDomain!.isConstOf ``_root_.State withAppArg <| withBindingBodyUnusedName fun x => do let x : TSyntax `ident := ⟨x⟩ let body ← delab `(∃ $x:ident, $body) end Assertion.Delab

5.1.2. Example Assertions🔗

Here are some example assertions that take advantage of this new notation.

namespace ExamplePrettyAssertions def assertion1 : Assertion := {{ X = 3 }} def assertion2 : Assertion := {{ True }} def assertion3 : Assertion := {{ False }} def assertion4 : Assertion := {{ True ∨ False }} def assertion5 : Assertion := {{ X ≤ Y }} def assertion6 : Assertion := {{ X = 3 ∨ X ≤ Y }} def assertion7 : Assertion := {{ Z = max X Y }} def assertion8 : Assertion := {{ Z * Z ≤ X ∧ ¬ (((Z + 1) * (Z + 1)) ≤ X) }} def assertion9 : Assertion := {{ Nat.add X Y > max Y X }} def ExamplePrettyAssertions.assertion8 : Assertion := {{Z * Z ≤ X ∧ ¬(Z + 1) * (Z + 1) ≤ X}}#print assertion8
def ExamplePrettyAssertions.assertion8 : Assertion :=
{{Z * Z ≤ X ∧ ¬(Z + 1) * (Z + 1) ≤ X}}
end ExamplePrettyAssertions

5.1.3. Assertion Implication🔗

Given two assertions P and Q, we say that P implies Q, written P ↠ Q, if, whenever P holds in some state st, Q also holds.

def AssertImplies (P Q : Assertion) : Prop := ∀ st : State, P st → Q st

Note that the notation for assertion implication is analogous to the "usual" Lean implication →.

namespace Assertion scoped notation:26 P:27 " ↠ " Q:27 => AssertImplies P Q end Assertion theorem assertImplies_def {P Q : Assertion} : P ↠ Q ↔ ∀ st : State, P st → Q st := P:AssertionQ:Assertion⊢ P ↠ Q ↔ ∀ (st : State), P st → Q st All goals completed! 🐙

(The scoped keyword tells Lean that this notation is not global but is available only where the Assertion namespace is open, as it is throughout this chapter.)

To type ↠ in VS Code, we can write \rr-.

We'll also want the "iff" variant of implication between assertions:

def AssertIff (P Q : Assertion) : Prop := (P ↠ Q) ∧ (Q ↠ P) namespace Assertion scoped notation:26 P:27 " ↞↠ " Q:27 => AssertIff P Q end Assertion theorem assertIff_def {P Q : Assertion} : P ↞↠ Q ↔ (P ↠ Q) ∧ (Q ↠ P) := P:AssertionQ:Assertion⊢ P ↞↠ Q ↔ (P ↠ Q) ∧ (Q ↠ P) All goals completed! 🐙

To type ↞↠ in VS Code, we can write \llrr or \ll-\rr-.

Notation encoding: printing implications back

The matching delaborators print implications and equivalences between assertions back in ↠ and ↞↠ notation.

namespace Assertion.Delab open Lean PrettyPrinter Delaborator SubExpr @[delab app.AssertImplies] def delabAssertImplies : Delab := whenPPOption getPPNotation do guard <| (← getExpr).isAppOfArity ``AssertImplies 2 `($(← delabAssnArg 0) ↠ $(← delabAssnArg 1)) @[delab app.AssertIff] def delabAssertIff : Delab := whenPPOption getPPNotation do guard <| (← getExpr).isAppOfArity ``AssertIff 2 `($(← delabAssnArg 0) ↞↠ $(← delabAssnArg 1)) end Assertion.Delab

5.2. Hoare Triples, Informally🔗

A Hoare triple is a claim about the state before and after executing a command. A common notation for Hoare triples, and the one we use in this book, is

{{P}} c {{Q}}

meaning:

  • If command c begins execution in a state satisfying assertion P,

  • and if c eventually terminates in some final state,

  • then that final state will satisfy the assertion Q.

Assertion P is called the precondition of the triple, and Q is the postcondition.

For example,

  • The Hoare triple

    {{X = 0}} X := X + 1 {{X = 1}}
    

    states that command X := X + 1 will transform a state in which X = 0 to a state in which X = 1.

  • On the other hand,

    ∀ m, {{X = m}} X := X + 1 {{X = m + 1}}
    

    is a proposition stating that the Hoare triple {{X = m}} X := X + 1 {{X = m + 1}} is valid for any choice of m. Note that m in the two assertions is a reference to the Lean variable m, which is bound outside the Hoare triple.

Quiz

Paraphrase the following in English.

1) {{True}} c {{X = 5}}

2) ∀ m, {{X = m}} c {{X = m + 5}}

3) {{X ≤ Y}} c {{Y ≤ X}}

4) {{True}} c {{False}}

5) ∀ m,
     {{X = m}}
     c
     {{Y = realFact m}}

6) ∀ m,
     {{X = m}}
     c
     {{(Z * Z) ≤ m ∧ ¬ ((Z + 1) * (Z + 1) ≤ m)}}
Show solution
  1. If command c terminates starting in an arbitrary state it produces a state where the value of X is equal to 5.

  2. Starting in a state where the value of X is m, if c terminates the value of X is equal to m+5.

  3. Starting in a state where the value of X is less than or equal to the value of Y, if c terminates then the value of Y is less than or equal to the value of X.

  4. c doesn't terminate on any starting state.

  5. If c terminates then Y contains as a value the factorial of the initial value of X.

  6. If c terminates starting in a state in which the value of X is equal to m, then Z contains the integer square root of the initial value of X.

Exercise★(triples) (Optional)

Paraphrase the following in English.

1) {{True}} c {{X = 5}}

2) ∀ m, {{X = m}} c {{X = m + 5}}

3) {{X ≤ Y}} c {{Y ≤ X}}

4) {{True}} c {{False}}

5) ∀ m,
     {{X = m}}
     c
     {{Y = realFact m}}

6) ∀ m,
     {{X = m}}
     c
     {{(Z * Z) ≤ m ∧ ¬ ((Z + 1) * (Z + 1) ≤ m)}}
  1. If command c terminates starting in an arbitrary state it produces a state where the value of X is equal to 5.

  2. Starting in a state where the value of X is m, if c terminates the value of X is equal to m+5.

  3. Starting in a state where the value of X is less than or equal to the value of Y, if c terminates then the value of Y is less than or equal to the value of X.

  4. c doesn't terminate on any starting state.

  5. If c terminates then Y contains as a value the factorial of the initial value of X.

  6. If c terminates starting in a state in which the value of X is equal to m, then Z contains the integer square root of the initial value of X.

Quiz

Is the following Hoare triple valid — i.e., is the claimed relation between P, c, and Q true?

{{True}} X := 5 {{X = 5}}

(A) Yes

(B) No

Show solution

Yes.

Quiz

What about this one?

{{X = 2}} X := X + 1 {{X = 3}}

(A) Yes

(B) No

Show solution

Yes.

Quiz

What about this one?

{{True}} X := 5; Y := 0 {{X = 5}}

(A) Yes

(B) No

Show solution

Yes.

Quiz

What about this one?

{{X = 2 ∧ X = 3}} X := 5 {{X = 0}}

(A) Yes

(B) No

Show solution

Yes: the precondition is never satisfied.

Quiz

What about this one?

{{True}} skip {{False}}

(A) Yes

(B) No

Show solution

No.

Quiz

What about this one?

{{False}} skip {{True}}

(A) Yes

(B) No

Show solution

Yes.

Quiz

What about this one?

{{True}} while true do skip end {{False}}

(A) Yes

(B) No

Show solution

Yes: the loop never terminates.

Quiz

This one?

{{X = 0}}
  while X = 0 do X := X + 1 end
{{X = 1}}

(A) Yes

(B) No

Show solution

Yes.

Quiz

This one?

{{X = 1}}
  while X ≠ 0 do X := X + 1 end
{{X = 100}}

(A) Yes

(B) No

Show solution

Yes: the loop never terminates.

Exercise★(valid_triples) (Optional)

Which of the following Hoare triples are valid — i.e., the claimed relation between P, c, and Q is true?

1) {{True}} X := 5 {{X = 5}}

2) {{X = 2}} X := X + 1 {{X = 3}}

3) {{True}} X := 5; Y := 0 {{X = 5}}

4) {{X = 2 ∧ X = 3}} X := 5 {{X = 0}}

5) {{True}} skip {{False}}

6) {{False}} skip {{True}}

7) {{True}} while true do skip end {{False}}

8) {{X = 0}}
    while X = 0 do X := X + 1 end
  {{X = 1}}

9) {{X = 1}}
    while X ≠ 0 do X := X + 1 end
  {{X = 100}}

All are valid except the 5th.

5.3. Hoare Triples, Formally🔗

We formalize valid Hoare triples in Lean as follows:

open scoped HasEval def ValidHoareTriple (P : Assertion) (c : Com) (Q : Assertion) : Prop := ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'

We overload the {{ P }} c {{ Q }} notation across command types with a typeclass, the same way the Equiv typeclass of Equiv overloads ≃:

class HasTriple (α : Type) where Triple : Assertion → α → Assertion → Prop instance : HasTriple Com where Triple := ValidHoareTriple
Notation: Hoare triplesnamespace HasTriple /-- Hoare triple: `{{ P }} c {{ Q }}` with `imp_com` command syntax -/ scoped syntax:lead "{{" term "}} " imp_com:min " {{" term "}}" : term scoped macro_rules | `({{ $P }} $c:imp_com {{ $Q }}) => ``(HasTriple.Triple ({{ $P }}) (imp { $c }) ({{ $Q }})) end HasTriple
Note to developers (Niklas Halonen @xhalo32)

Something strange is going on in theorem if_example, using apply hoare_consequence_pre followed by · exact hoare_asgn works, but refine hoare_consequence_pre hoare_asgn ?_ or apply hoare_consequence_pre hoare_asgn don't. The only solution I found was to mark ValidHoareTriple irreducible.

It has to do something with apply and refine looking inside the implication in ∀ {st st'}, ...

We make ValidHoareTriple irreducible for technical reasons. In your proofs, if you need to prove the validity of a Hoare triple, you should use validHoareTriple_def with rw or simp.

open scoped HasTriple theorem validHoareTriple_def {P : Assertion} {c : Com} {Q : Assertion} : {{ P }} c {{ Q }} ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' := P:Assertionc:ComQ:Assertion⊢ HasTriple.Triple ({{P}}) c ({{Q}}) ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' All goals completed! 🐙 attribute [irreducible] ValidHoareTriple
Notation encoding: printing triples back

The delaborator is agnostic to the command type: it prints the command with whatever printer is registered for its constructors and splices the result into the triple, so a language-extension chapter only has to register a printer for its own Com.

Note to developers (Niklas Halonen @xhalo32)

Can we use an unexpander for this? Something like

@[app_unexpander HasTriple.Triple]
def unexpandTriple : Lean.PrettyPrinter.Unexpander
  | `($_ ({{ $P }}) (imp { $c }) ({{ $Q }})) => ``({{ $P }} $c {{ $Q }})
  | _ => throw ()
namespace HasTriple.Delab open Lean PrettyPrinter Delaborator SubExpr Assertion.Delab Imp.Delab @[delab app.HasTriple.Triple] def delabTriple : Delab := whenPPOption getPPNotation do guard <| (← getExpr).isAppOfArity ``HasTriple.Triple 5 let P ← withNaryArg 2 delabAssn let c ← withNaryArg 3 delab let Q ← withNaryArg 4 delabAssn match c with | `(imp { $c:imp_com }) => ``({{ $P }} $c:imp_com {{ $Q }}) | c => ``({{ $P }} ~$c {{ $Q }}) end HasTriple.Delab namespace HasEval.Delab open Lean PrettyPrinter Delaborator SubExpr Imp.Delab def delabEvalR : Delab := whenPPOption getPPNotation do guard <| (← getExpr).getAppNumArgs == 3 let c ← withNaryArg 0 delab let st ← withNaryArg 1 delab let st' ← withNaryArg 2 delab match c with | `(imp { $c:imp_com }) => ``($st =[ $c ]=> $st') | c => ``($st =[ ~$c ]=> $st') attribute [app_delab Com.EvalR] delabEvalR end HasEval.Delab
Exercise★(hoare_post_true)

Prove that if Q holds in every state, then any triple with Q as its postcondition is valid.

theorem hoare_post_true {P Q : Assertion} {c : Com} (h : ∀ st : State, Q st) : {{ P }} c {{ Q }} := P:AssertionQ:Assertionc:Comh:∀ (st : State), Q st⊢ {{P}} ~c {{Q}} solution! P:AssertionQ:Assertionc:Comh:∀ (st : State), Q st⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionQ:Assertionc:Comh:∀ (st : State), Q stst:Statest':Statehc:st =[ c ]=> st'hpre:P st⊢ Q st' All goals completed! 🐙
Exercise★(hoare_pre_false) (Optional)

Prove that if P holds in no state, then any triple with P as its precondition is valid.

theorem hoare_pre_false {P Q : Assertion} {c : Com} (h : ∀ st : State, ¬ (P st)) : {{ P }} c {{ Q }} := P:AssertionQ:Assertionc:Comh:∀ (st : State), ¬P st⊢ {{P}} ~c {{Q}} solution! P:AssertionQ:Assertionc:Comh:∀ (st : State), ¬P st⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionQ:Assertionc:Comh:∀ (st : State), ¬P stst:Statest':Statehc:st =[ c ]=> st'hpre:P st⊢ Q st' P:AssertionQ:Assertionc:Comst:Stateh:¬P stst':Statehc:st =[ c ]=> st'hpre:P st⊢ Q st' All goals completed! 🐙

5.4. Proof Rules🔗

The goal of Hoare logic is to provide a compositional method for proving the validity of specific Hoare triples. That is, we want the structure of a program's correctness proof to mirror the structure of the program itself. To this end, in the sections below, we'll introduce a rule for reasoning about each of the different syntactic forms of commands in Imp — one for assignment, one for sequencing, one for conditionals, etc. — plus a couple of "structural" rules for gluing things together. We will then be able to prove programs correct using these proof rules, without ever unfolding the definition of ValidHoareTriple.

The presentation of Hoare logic in this chapter could be described as model-theoretic: the proof rules for each of the syntactic forms are presented as theorems about the evaluation behavior of programs, justified according to ValidHoareTriple. Another way of presenting Hoare logic is to define a completely separate proof system — a set of axioms and inference rules as part of an inductive proposition — and then say that a proof of a Hoare triple is a valid derivation in that logic. Then we would prove this logic sound in the sense that all proofs in that logic (its derivations) have a corresponding (Lean) proof of ValidHoareTriple. This approach could be described as proof theoretic. Since the most natural proof of soundness would be via the model-theoretic approach, we present that approach and leave a proof theoretic presentation (and discussion of its potential advantages) to a future development.

5.4.1. Skip🔗

Since skip doesn't change the state, it preserves any assertion P:

--------------------  (hoare_skip)
{{ P }} skip {{ P }}
theorem hoare_skip {P : Assertion} : {{ P }} skip {{ P }} := P:Assertion⊢ {{P}} skip {{P}} P:Assertion⊢ ∀ {st st' : State}, (st =[ skip ]=> st') → P st → P st' P:Assertionst:Statest':Stateh:st =[ skip ]=> st'hpre:P st⊢ P st' P:Assertionst:Statehpre:P st⊢ P st All goals completed! 🐙

5.4.2. Sequencing🔗

If command c₁ takes any state where P holds to a state where Q holds, and if c₂ takes any state where Q holds to one where R holds, then doing c₁ followed by c₂ will take any state where P holds to one where R holds:

  {{ P }} c₁ {{ Q }}
  {{ Q }} c₂ {{ R }}
----------------------  (hoare_seq)
{{ P }} c₁; c₂ {{ R }}
theorem hoare_seq {P Q R : Assertion} {c₁ c₂ : Com} (h₁ : {{ Q }} c₂ {{ R }}) (h₂ : {{ P }} c₁ {{ Q }}) : {{ P }} c₁; c₂ {{ R }} := P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:{{Q}} ~c₂ {{R}}h₂:{{P}} ~c₁ {{Q}}⊢ {{P}} c₁; c₂ {{R}} P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:{{Q}} ~c₂ {{R}}h₂:{{P}} ~c₁ {{Q}}⊢ ∀ {st st' : State}, (st =[ c₁; c₂ ]=> st') → P st → R st' P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:{{Q}} ~c₂ {{R}}h₂:{{P}} ~c₁ {{Q}}st:Statest':Stateheval:st =[ c₁; c₂ ]=> st'hpre:P st⊢ R st' inversion heval with P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:{{Q}} ~c₂ {{R}}h₂:{{P}} ~c₁ {{Q}}st:Statest':Statehpre:P stst'✝:Statehc₁:st =[ ~c₁ ]=> st'✝hc₂:st'✝ =[ ~c₂ ]=> st'⊢ R st' P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st st' : State}, (st =[ c₂ ]=> st') → Q st → R st'h₂:∀ {st st' : State}, (st =[ c₁ ]=> st') → P st → Q st'st:Statest':Statehpre:P stst'✝:Statehc₁:st =[ ~c₁ ]=> st'✝hc₂:st'✝ =[ ~c₂ ]=> st'⊢ R st' -- We now "string together" each piece of information to conclude. All goals completed! 🐙

Note that, in the formal rule hoare_seq, the premises are given in backwards order (c₂ before c₁). This matches the natural flow of information in many of the situations where we'll use the rule, since the natural way to construct a Hoare-logic proof is to begin at the end of the program (with the final postcondition) and push postconditions backwards through commands until we reach the beginning.

5.4.3. Assignment🔗

The rule for assignment is the most fundamental of the Hoare logic proof rules. Here's how it works.

Consider this incomplete Hoare triple:

{{ ??? }}  X := Y  {{ X = 1 }}

We want to assign Y to X and finish in a state where X is 1. What could the precondition be?

One possibility is Y = 1, because if Y is already 1 then assigning it to X causes X to be 1. That leads to a valid Hoare triple:

{{ Y = 1 }}  X := Y  {{ X = 1 }}

It may seem as though coming up with that precondition must have taken some clever thought. But there is a mechanical way we could have done it: if we take the postcondition X = 1 and in it replace X with Y — that is, replace the left-hand side of the assignment statement with the right-hand side — we get the precondition, Y = 1.

That same idea works in more complicated cases. For example:

{{ ??? }}  X := X + Y  {{ X = 1 }}

If we replace the X in X = 1 with X + Y, we get X + Y = 1. That again leads to a valid Hoare triple:

{{ X + Y = 1 }}  X := X + Y  {{ X = 1 }}

Why does this technique work? The postcondition identifies some property P that we want to hold of the variable X being assigned. In this case, P is "equals 1". To complete the triple and make it valid, we need to identify a precondition that guarantees that property will hold of X. Such a precondition must ensure that the same property holds of whatever is being assigned to X. So, in the example, we need "equals 1" to hold of X + Y. That's exactly what the technique guarantees.

In general, the postcondition could be some arbitrary assertion Q, and the right-hand side of the assignment could be some arbitrary arithmetic expression a:

{{ ??? }}  X := a  {{ Q }}

The precondition would then be Q, but with any occurrences of X in it replaced by a.

Let's introduce a notation for this idea of replacing occurrences: Define Q [X ↦ a] to mean "Q where a is substituted in place of X".

This yields the Hoare logic rule for assignment:

{{ Q [X ↦ a] }}  X := a  {{ Q }}

One way of reading this rule is: If you want statement X := a to terminate in a state that satisfies assertion Q, then it suffices to start in a state that also satisfies Q, except where a is substituted for every occurrence of X.

To many people, this rule seems "backwards" at first, because it proceeds from the postcondition to the precondition. Actually it makes good sense to go in this direction: the postcondition is often what is more important, because it characterizes what will be true after running the code.

Nonetheless, it's also possible to formulate a "forward" assignment rule. We'll do that later in some exercises.

Here are some valid instances of the assignment rule:

{{ (X ≤ 5) [X ↦ X + 1] }}        (that is, X + 1 ≤ 5)
  X := X + 1
{{ X ≤ 5 }}

{{ (X = 3) [X ↦ 3] }}            (that is, 3 = 3)
  X := 3
{{ X = 3 }}

{{ (0 ≤ X ∧ X ≤ 5) [X ↦ 3] }}    (that is, 0 ≤ 3 ∧ 3 ≤ 5)
  X := 3
{{ 0 ≤ X ∧ X ≤ 5 }}

To formalize the rule, we must first formalize the idea of "substituting an expression for an Imp variable in an assertion", which we refer to as assertion substitution, or Assertion.subst.

Intuitively, given a proposition P, a variable X, and an arithmetic expression a, we want to derive another proposition P' that is just the same as P except that P' should mention a wherever P mentions X.

This operation is related to the idea of substituting Imp expressions for Imp variables that we saw in Equiv (Aexp.subst and friends). The difference is that, here, P is an arbitrary Lean assertion, so we can't directly "edit" its text.

However, we can achieve the same effect by evaluating P in an updated state, defined as follows:

namespace Assertion def subst (x : Ident) (a : Aexp) (P : Assertion) : Assertion := fun (st : State) => P (x →ₜ a.eval st ; st) theorem subst_def {x : Ident} {a : Aexp} {P : Assertion} : Assertion.subst x a P = fun (st : State) => P (x →ₜ a.eval st ; st) := x:Identa:AexpP:Assertion⊢ subst x a P = fun st => P (x →ₜ Aexp.eval st a ; st) All goals completed! 🐙 @[simp] theorem subst_apply {x : Ident} {a : Aexp} {P : Assertion} {st : State} : Assertion.subst x a P st ↔ P (x →ₜ a.eval st ; st) := x:Identa:AexpP:Assertionst:State⊢ subst x a P st ↔ P (x →ₜ Aexp.eval st a ; st) All goals completed! 🐙 end Assertion
Note to developers (before next release)

This concrete syntax is hard to read in comments because of all the square brackets. Something like P with X ↦ a would be much better. I guess the same will apply to the lambda-calculus chapters... BCP 25: I still think this is a good idea, and I had a quick go at implementing it, but did not succeed yet.

Note to developers (One An @meluge, before next release)

Introduce a notation typeclass for this (e.g. HasSubst)

We write assertion substitution with the notation P [X ↦ a], implemented the same {{ }}-plus-typeclass way as the notations above.

Notation: Assertion substitutionnamespace Assertion /-- Assertion substitution, written inside the braces: `{{ (P) [X ↦ a] }}`. The substituted assertion is re-read with the same notation, so Imp variables in it mean state lookups as usual; a named assertion is passed through directly. The high priority keeps `P [X ↦ a]` from being read as `P` applied to a one-element list of `KVPair`s (the `{X ↦ 1}` state notation is open chapter-wide). -/ scoped syntax:max (priority := high) term:arg " [" ident " ↦ " imp_aexp "]" : term macro_rules | `(assn($st; $P [$x ↦ $a:imp_aexp])) => match P with | `($_:ident) => ``(Assertion.subst $x (aexp { $a }) $P $st) | _ => ``(Assertion.subst $x (aexp { $a }) ({{ $P }}) $st) end Assertion namespace Assertion.Delab open Lean PrettyPrinter Delaborator SubExpr Imp.Elab Imp.Delab /-- Print an `Assertion.subst` back in `P [x ↦ a]` notation. Emits the bare inside-the-braces form: the generic application case of `delabBody` picks it up inside an assertion body, and the enclosing printer supplies the single pair of braces. -/ @[app_unexpander Assertion.subst] def unexpandSubst : Unexpander | `($_ $x $a $P) => do let x ← match x with | `($x:ident) => pure x | `($s:str) => pure (mkObjectIdentFrom s.raw s.getString) | _ => throw () match getAssn P with | `($P:ident) => `($P:ident [$x:ident ↦ $(getAexp a):imp_aexp]) | P => `(($P) [$x:ident ↦ $(getAexp a):imp_aexp]) | _ => throw () end Assertion.Delab

This notation allows us to write this operation as:

P [ X ↦ a ]

That is, P [X ↦ a] stands for an assertion — let's call it P' — that behaves just like P except that, wherever P looks up the variable X in the current state, P' instead uses the value of the expression a.

To see how this works in more detail, let's calculate what happens with a couple of examples. First, suppose P' is (X ≤ 5) [X ↦ 3] — that is, more formally, P' is the Lean expression

fun st =>
  (fun st' => st'[X] ≤ 5)
  (X →ₜ Aexp.eval st 3 ; st),

which simplifies to

fun st =>
  (fun st' => st'[X] ≤ 5)
  (X →ₜ 3 ; st)

and further simplifies to

fun st =>
  ((X →ₜ 3 ; st)[X]) ≤ 5

and finally to

fun st =>
  3 ≤ 5.

That is, P' is the assertion that 3 is less than or equal to 5 (as expected).

For a more interesting example, suppose P' is (X ≤ 5) [X ↦ X + 1]. Formally, P' is the Lean expression

fun st =>
  (fun st' => st'[X] ≤ 5)
  (X →ₜ Aexp.eval st (aexp { X + 1 }) ; st),

which simplifies to

fun st =>
  (X →ₜ Aexp.eval st (aexp { X + 1 }) ; st)[X] ≤ 5

and further simplifies to

fun st =>
  (Aexp.eval st (aexp { X + 1 })) ≤ 5.

That is, P' is the assertion that X + 1 is at most 5.

Some examples of using substitution:

{{(X ≤ 10) [X ↦ 2 * X]}} : State → Prop#check {{ (X ≤ 10) [X ↦ 2 * X] }} ∀ (st : State), ({{(X ≤ 10) [X ↦ 2 * X]}}) st : Prop#check (∀ st, ({{ (X ≤ 10) [X ↦ 2 * X] }}) st) -- Written explicitly: {{(X ≤ 10) [X ↦ 2 * X]}} : State → Prop#check (fun st => Assertion.subst X (aexp { 2 * X }) ({{ X ≤ 10 }}) st)
{{(X ≤ 10) [X ↦ 2 * X]}} : State → Prop
∀ (st : State), ({{(X ≤ 10) [X ↦ 2 * X]}}) st : Prop
{{(X ≤ 10) [X ↦ 2 * X]}} : State → Prop

We can demonstrate formally that we have captured the intuitive meaning of "assertion substitution" by proving some example logical equivalences:

namespace ExampleAssertionSub example : {{ (X ≤ 5) [X ↦ 3] }} ↞↠ {{ 3 ≤ 5 }} := ⊢ {{(X ≤ 5) [X ↦ 3]}} ↞↠ {{3 ≤ 5}} ⊢ ({{(X ≤ 5) [X ↦ 3]}} ↠ {{3 ≤ 5}}) ∧ ({{3 ≤ 5}} ↠ {{(X ≤ 5) [X ↦ 3]}}) ⊢ {{(X ≤ 5) [X ↦ 3]}} ↠ {{3 ≤ 5}}⊢ {{3 ≤ 5}} ↠ {{(X ≤ 5) [X ↦ 3]}} ⊢ {{(X ≤ 5) [X ↦ 3]}} ↠ {{3 ≤ 5}} ⊢ ∀ (st : State), (X ≤ 5) [X ↦ 3] st → 3 ≤ 5 st:Statea✝:(X ≤ 5) [X ↦ 3] st⊢ 3 ≤ 5 All goals completed! 🐙 ⊢ {{3 ≤ 5}} ↠ {{(X ≤ 5) [X ↦ 3]}} ⊢ ∀ (st : State), 3 ≤ 5 → (X ≤ 5) [X ↦ 3] st st:Statea✝:3 ≤ 5⊢ (X ≤ 5) [X ↦ 3] st All goals completed! 🐙 example : {{ (X ≤ 5) [X ↦ X + 1] }} ↞↠ {{ (X + 1) ≤ 5 }} := ⊢ {{(X ≤ 5) [X ↦ X + 1]}} ↞↠ {{X + 1 ≤ 5}} ⊢ ({{(X ≤ 5) [X ↦ X + 1]}} ↠ {{X + 1 ≤ 5}}) ∧ ({{X + 1 ≤ 5}} ↠ {{(X ≤ 5) [X ↦ X + 1]}}) ⊢ {{(X ≤ 5) [X ↦ X + 1]}} ↠ {{X + 1 ≤ 5}}⊢ {{X + 1 ≤ 5}} ↠ {{(X ≤ 5) [X ↦ X + 1]}} ⊢ {{(X ≤ 5) [X ↦ X + 1]}} ↠ {{X + 1 ≤ 5}} ⊢ ∀ (st : State), (X ≤ 5) [X ↦ X + 1] st → st[X] + 1 ≤ 5 st:State⊢ (X ≤ 5) [X ↦ X + 1] st → st[X] + 1 ≤ 5 All goals completed! 🐙 ⊢ {{X + 1 ≤ 5}} ↠ {{(X ≤ 5) [X ↦ X + 1]}} ⊢ ∀ (st : State), st[X] + 1 ≤ 5 → (X ≤ 5) [X ↦ X + 1] st st:State⊢ st[X] + 1 ≤ 5 → (X ≤ 5) [X ↦ X + 1] st All goals completed! 🐙 end ExampleAssertionSub

Most of the simp calls rely on Assertion.subst_apply and TotalMap.update_eq, plus some Aexp characterizing lemmas like Aexp.eval_num.

Now, using the substitution operation we've just defined, we can give the precise proof rule for assignment:

-------------------------- (hoare_asgn)
{{Q [X ↦ a]}} X := a {{Q}}

We can prove formally that this rule is indeed valid.

theorem hoare_asgn {Q : Assertion} {x : Ident} {a : Aexp} : {{ Q [x ↦ a] }} x := a {{ Q }} := Q:Assertionx:Identa:Aexp⊢ {{Q [x ↦ a]}} x := a {{Q}} Q:Assertionx:Identa:Aexp⊢ ∀ {st st' : State}, (st =[ x := a ]=> st') → Q [x ↦ a] st → Q st' Q:Assertionx:Identa:Aexpst:Statest':Stateheval:st =[ x := a ]=> st'hQ:Q [x ↦ a] st⊢ Q st' inversion heval with Q:Assertionx:Identa:Aexpst:StatehQ:Q [x ↦ a] stn:Nath:Aexp.eval st a = n⊢ Q (x →ₜ n ; st) Q:Assertionx:Identa:Aexpst:StatehQ:Q [x ↦ a] st⊢ Q (x →ₜ Aexp.eval st a ; st) Q:Assertionx:Identa:Aexpst:StatehQ:Q (x →ₜ Aexp.eval st a ; st)⊢ Q (x →ₜ Aexp.eval st a ; st) All goals completed! 🐙

Here's a first formal proof of a Hoare triple using this rule.

theorem assertion_sub_example : {{ (X < 5) [X ↦ X + 1] }} X := X + 1 {{ X < 5 }} := ⊢ {{(X < 5) [X ↦ X + 1]}} X := X + 1 {{X < 5}} All goals completed! 🐙

Of course, we'd probably prefer to work with this simpler triple:

{{X < 4}} X := X + 1 {{X < 5}}

We will see how to do so in the next section.

Several proofs below use the facts about total-map updates proved in the Typeclasses chapter — TotalMap.update_eq, TotalMap.update_neq, TotalMap.update_shadow, TotalMap.update_same, and TotalMap.update_permute. Make sure you understand their statements.

Complete these Hoare triples by providing an appropriate precondition using exists, then prove them with apply hoare_asgn. If you find that tactic doesn't suffice, double check that you have completed the triple properly.

Exercise★★(hoare_asgn_examples1) (Optional)
theorem hoare_asgn_examples1 : ∃ P : Assertion, {{ P }} X := 2 * X {{ X ≤ 10 }} := ⊢ ∃ P, {{P}} X := 2 * X {{X ≤ 10}} solution! ⊢ {{(X ≤ 10) [X ↦ 2 * X]}} X := 2 * X {{X ≤ 10}} All goals completed! 🐙
Exercise★★(hoare_asgn_examples2) (Optional)
theorem hoare_asgn_examples2 : ∃ P : Assertion, {{ P }} X := 3 {{ 0 ≤ X ∧ X ≤ 5 }} := ⊢ ∃ P, {{P}} X := 3 {{0 ≤ X ∧ X ≤ 5}} solution! ⊢ {{(0 ≤ X ∧ X ≤ 5) [X ↦ 3]}} X := 3 {{0 ≤ X ∧ X ≤ 5}} All goals completed! 🐙
Exercise★★(hoare_asgn_wrong)

The assignment rule looks backward to almost everyone the first time they see it. If it still seems puzzling to you, it may help to think a little about alternative "forward" rules. Here is a seemingly natural one:

----------------------------- (hoare_asgn_wrong)
{{ True }} X := a {{ X = a }}

Give a counterexample showing that this rule is incorrect and use it to complete the proof below, showing that it is really a counterexample. (Hint: The rule universally quantifies over the arithmetic expression a, so your counterexample needs to exhibit an a for which the rule doesn't work.)

theorem hoare_asgn_wrong : ∃ a : Aexp, ¬ {{ True }} X := a {{ X = a }} := ⊢ ∃ a, ¬{{True}} X := a {{X = a}} solution! ⊢ ¬{{True}} X := X + 1 {{X = aexp {X + 1} }} hc:{{True}} X := X + 1 {{X = aexp {X + 1} }}⊢ False hc:∀ {st st' : State}, (st =[ X := X + 1 ]=> st') → True → st'[X] = Aexp.eval st' (aexp {X + 1})⊢ False hc:∀ {st st' : State}, (st =[ X := X + 1 ]=> st') → True → st'[X] = Aexp.eval st' (aexp {X + 1})h:{X ↦ 1}[X] = Aexp.eval {X ↦ 1} (aexp {X + 1})⊢ False All goals completed! 🐙

If a itself mentions X, then the value of a may be different in the final state because of this update. For example, if a is X + 1, then setting X to a certainly does not achieve the postcondition X = X + 1! The underlying problem is that the state in which the postcondition will be checked is different than the state in which a was evaluated when it was assigned to X.

Exercise★★★(hoare_asgn_fwd) (Advanced, Optional)

By using a parameter m (a Lean number) to remember the original value of X we can define a Hoare rule for assignment that does, intuitively, "work forwards" rather than backwards.

------------------------------------------ (hoare_asgn_fwd)
{{ P ∧ X = m }}
  X := a
{{ fun st => P (X →ₜ m ; st) ∧ st[X] = a.eval (X →ₜ m ; st) }}

Note that we need to write out the postcondition in "desugared" form, because it needs to talk about two different states: we use the original value of X to reconstruct the state st' before the assignment took place. (Also note that this rule is more complicated than hoare_asgn!)

Prove that this rule is correct.

Note to developers

HIDE: BCP 21: Could we make the precondition use compact notation, at least?

HIDE: SAZ 2024 - this version of the syntax does let us use the compact notation for the precondition, but it comes at the cost of having to "escape" the function in the postcondition.

theorem hoare_asgn_fwd {m : Nat} {a : Aexp} {P : Assertion} : {{ P ∧ X = m }} X := a {{ fun st => P (X →ₜ m ; st) ∧ st[X] = a.eval (X →ₜ m ; st) }} := m:Nata:AexpP:Assertion⊢ {{P ∧ X = m}} X := a {{fun st => P (X →ₜ m ; st) ∧ st[X] = Aexp.eval (X →ₜ m ; st) a}} solution! m:Nata:AexpP:Assertion⊢ ∀ {st st' : State}, (st =[ X := a ]=> st') → P st ∧ st[X] = m → P (X →ₜ m ; st') ∧ st'[X] = Aexp.eval (X →ₜ m ; st') a m:Nata:AexpP:Assertionst:Statest':Stateheval:st =[ X := a ]=> st'hp:P sthx:st[X] = m⊢ P (X →ₜ m ; st') ∧ st'[X] = Aexp.eval (X →ₜ m ; st') a inversion heval with m:Nata:AexpP:Assertionst:Statehp:P sthx:st[X] = mn:Nath:Aexp.eval st a = n⊢ P (X →ₜ m ; "X" →ₜ n ; st) ∧ ("X" →ₜ n ; st)[X] = Aexp.eval (X →ₜ m ; "X" →ₜ n ; st) a a:AexpP:Assertionst:Statehp:P st⊢ P (X →ₜ st[X] ; "X" →ₜ Aexp.eval st a ; st) ∧ ("X" →ₜ Aexp.eval st a ; st)[X] = Aexp.eval (X →ₜ st[X] ; "X" →ₜ Aexp.eval st a ; st) a a:AexpP:Assertionst:Statehp:P st⊢ P st ∧ Aexp.eval st a = Aexp.eval st a All goals completed! 🐙
Exercise★★(hoare_asgn_fwd_exists) (Advanced, Optional)

Another way to define a forward rule for assignment is to existentially quantify over the previous value of the assigned variable. Prove that it is correct.

------------------------------------ (hoare_asgn_fwd_exists)
{{ P }}
  X := a
{{ fun st => ∃ m, P (X →ₜ m ; st) ∧
                st[X] = a.eval (X →ₜ m ; st) }}
theorem hoare_asgn_fwd_exists {a : Aexp} {P : Assertion} : {{ P }} X := a {{ fun st => ∃ m, P (X →ₜ m ; st) ∧ st[X] = a.eval (X →ₜ m ; st) }} := a:AexpP:Assertion⊢ {{P}} X := a {{fun st => ∃ m, P (X →ₜ m ; st) ∧ st[X] = Aexp.eval (X →ₜ m ; st) a}} solution! a:AexpP:Assertion⊢ ∀ {st st' : State}, (st =[ X := a ]=> st') → P st → ∃ m, P (X →ₜ m ; st') ∧ st'[X] = Aexp.eval (X →ₜ m ; st') a a:AexpP:Assertionst:Statest':Stateheval:st =[ X := a ]=> st'hpre:P st⊢ ∃ m, P (X →ₜ m ; st') ∧ st'[X] = Aexp.eval (X →ₜ m ; st') a inversion heval with a:AexpP:Assertionst:Statehpre:P stn:Nath:Aexp.eval st a = n⊢ ∃ m, P (X →ₜ m ; "X" →ₜ n ; st) ∧ ("X" →ₜ n ; st)[X] = Aexp.eval (X →ₜ m ; "X" →ₜ n ; st) a a:AexpP:Assertionst:Statehpre:P st⊢ ∃ m, P (X →ₜ m ; "X" →ₜ Aexp.eval st a ; st) ∧ ("X" →ₜ Aexp.eval st a ; st)[X] = Aexp.eval (X →ₜ m ; "X" →ₜ Aexp.eval st a ; st) a a:AexpP:Assertionst:Statehpre:P st⊢ P (X →ₜ st[X] ; "X" →ₜ Aexp.eval st a ; st) ∧ ("X" →ₜ Aexp.eval st a ; st)[X] = Aexp.eval (X →ₜ st[X] ; "X" →ₜ Aexp.eval st a ; st) a a:AexpP:Assertionst:Statehpre:P st⊢ P st ∧ Aexp.eval st a = Aexp.eval st a All goals completed! 🐙

5.4.4. Consequence🔗

Sometimes the preconditions and postconditions we get from the Hoare rules won't quite be the ones we want in the particular situation at hand — they may be logically equivalent but have a different syntactic form that fails to unify with the goal we are trying to prove, or they actually may be logically weaker (for preconditions) or stronger (for postconditions) than what we need.

For instance,

{{(X = 3) [X ↦ 3]}} X := 3 {{X = 3}},

follows directly from the assignment rule, but

{{True}} X := 3 {{X = 3}}

does not. This triple is valid, but it is not an instance of hoare_asgn because True and (X = 3) [X ↦ 3] are not syntactically equal assertions.

However, they are logically equivalent, so if one triple is valid, then the other must certainly be as well. We can capture this observation with the following rule:

{{P'}} c {{Q}}
    P ↞↠ P'
--------------
{{P}} c {{Q}}

Taking this line of thought a bit further, we can see that strengthening the precondition or weakening the postcondition of a valid triple always produces another valid triple. This observation is captured by two Rules of Consequence.

{{P'}} c {{Q}}
    P ↠ P'
--------------   (hoare_consequence_pre)
{{P}} c {{Q}}

{{P}} c {{Q'}}
   Q' ↠ Q
--------------   (hoare_consequence_post)
{{P}} c {{Q}}

Here are the formal versions:

theorem hoare_consequence_pre {P P' Q : Assertion} {c : Com} (hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') : {{ P }} c {{ Q }} := P:AssertionP':AssertionQ:Assertionc:Comhhoare:{{P'}} ~c {{Q}}himp:P ↠ P'⊢ {{P}} ~c {{Q}} P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'st:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'st:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ P' st P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:∀ (st : State), P st → P' stst:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ P' st All goals completed! 🐙 theorem hoare_consequence_post {P Q Q' : Assertion} {c : Com} (hhoare : {{ P }} c {{ Q' }}) (himp : Q' ↠ Q) : {{ P }} c {{ Q }} := P:AssertionQ:AssertionQ':Assertionc:Comhhoare:{{P}} ~c {{Q'}}himp:Q' ↠ Q⊢ {{P}} ~c {{Q}} P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q' st'himp:Q' ↠ Q⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q' st'himp:Q' ↠ Qst:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q st' P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q' st'himp:∀ (st : State), Q' st → Q stst:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q st' P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q' st'himp:∀ (st : State), Q' st → Q stst:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q' st' All goals completed! 🐙

For example, we can use the first consequence rule like this:

{{ True }} ↠
{{ (X = 1) [X ↦ 1] }}
  X := 1
{{ X = 1 }}

Or, formally...

theorem hoare_asgn_example1 : {{True}} X := 1 {{X = 1}} := ⊢ {{True}} X := 1 {{X = 1}} workinclass! ⊢ {{(X = 1) [X ↦ 1]}} X := 1 {{X = 1}}⊢ {{True}} ↠ {{(X = 1) [X ↦ 1]}} ⊢ {{(X = 1) [X ↦ 1]}} X := 1 {{X = 1}} All goals completed! 🐙 ⊢ {{True}} ↠ {{(X = 1) [X ↦ 1]}} ⊢ ∀ (st : State), True → (X = 1) [X ↦ 1] st st:Statea✝:True⊢ (X = 1) [X ↦ 1] st All goals completed! 🐙

We can also use it to prove the example mentioned earlier.

{{ X < 4 }} ↠
{{ (X < 5)[X ↦ X + 1] }}
  X := X + 1
{{ X < 5 }}

Or, formally ...

theorem assertion_sub_example2 : {{X < 4}} X := X + 1 {{X < 5}} := ⊢ {{X < 4}} X := X + 1 {{X < 5}} workinclass! ⊢ {{(X < 5) [X ↦ X + 1]}} X := X + 1 {{X < 5}}⊢ {{X < 4}} ↠ {{(X < 5) [X ↦ X + 1]}} ⊢ {{(X < 5) [X ↦ X + 1]}} X := X + 1 {{X < 5}} All goals completed! 🐙 ⊢ {{X < 4}} ↠ {{(X < 5) [X ↦ X + 1]}} ⊢ ∀ (st : State), st[X] < 4 → (X < 5) [X ↦ X + 1] st ⊢ ∀ (st : State), st[X] < 4 → st["X"] + 1 < 5 All goals completed! 🐙

Finally, here is a combined rule of consequence that allows us to vary both the precondition and the postcondition.

{{P'}} c {{Q'}}
     P ↠ P'
    Q' ↠ Q
---------------   (hoare_consequence)
 {{P}} c {{Q}}
Note to developers (Niklas Halonen @xhalo32)

In the following proof, (P' := P') is not necessary, however it avoids having a metavariable in the first goal. Another option is to just write exact hoare_consequence_pre (hoare_consequence_post htriple hpost) hpre.

theorem hoare_consequence {P P' Q Q' : Assertion} {c : Com} (htriple : {{ P' }} c {{ Q' }}) (hpre : P ↠ P') (hpost : Q' ↠ Q) : {{ P }} c {{ Q }} := P:AssertionP':AssertionQ:AssertionQ':Assertionc:Comhtriple:{{P'}} ~c {{Q'}}hpre:P ↠ P'hpost:Q' ↠ Q⊢ {{P}} ~c {{Q}} P:AssertionP':AssertionQ:AssertionQ':Assertionc:Comhtriple:{{P'}} ~c {{Q'}}hpre:P ↠ P'hpost:Q' ↠ Q⊢ {{P'}} ~c {{Q}}P:AssertionP':AssertionQ:AssertionQ':Assertionc:Comhtriple:{{P'}} ~c {{Q'}}hpre:P ↠ P'hpost:Q' ↠ Q⊢ P ↠ P' P:AssertionP':AssertionQ:AssertionQ':Assertionc:Comhtriple:{{P'}} ~c {{Q'}}hpre:P ↠ P'hpost:Q' ↠ Q⊢ {{P'}} ~c {{Q}} All goals completed! 🐙 P:AssertionP':AssertionQ:AssertionQ':Assertionc:Comhtriple:{{P'}} ~c {{Q'}}hpre:P ↠ P'hpost:Q' ↠ Q⊢ P ↠ P' All goals completed! 🐙

5.4.5. Automation🔗

Many of the proofs we have done so far with Hoare triples can be streamlined using the automation techniques that we introduced in the Automation chapter of Logical Foundations.

Recall that simp rewrites with any lemmas we pass it. The definitions whose meaning we keep needing to expose in this chapter — ValidHoareTriple, AssertImplies, and Assertion.subst — each come with a characterizing lemma (validHoareTriple_def, assertImplies_def, Assertion.subst_def) restating the definition as an equation. Passing these lemmas to simp replaces the defined notions by their meanings wherever they appear. We'll do that explicitly below (and shortly package the recipe up as a tactic of our own).

The proof of hoare_consequence_pre, repeated below, looks like an opportune place for automation, because all it does is rewrite with the characterizing lemmas, intro, and apply. (It uses exact, too, but that's just application of a hypothesis.)

theorem hoare_consequence_pre {P P' Q : Assertion} {c : Com} (hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') : {{ P }} c {{ Q }} := P:AssertionP':AssertionQ:Assertionc:Comhhoare:{{P'}} ~c {{Q}}himp:P ↠ P'⊢ {{P}} ~c {{Q}} P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'st:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'st:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ P' st P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:∀ (st : State), P st → P' stst:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ P' st All goals completed! 🐙

Since AssertImplies is not marked irreducible, and assertImplies_def is a proof by definitional equality, we can skip the rw [assertImplies_def] at himp and use P ↠ P' like an implication directly.

Note to developers (Niklas Halonen @xhalo32)

This needs a better explanation of when it's okay to use definitions without using their characterizing lemmas.

theorem hoare_consequence_pre' {P P' Q : Assertion} {c : Com} (hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') : {{ P }} c {{ Q }} := P:AssertionP':AssertionQ:Assertionc:Comhhoare:{{P'}} ~c {{Q}}himp:P ↠ P'⊢ {{P}} ~c {{Q}} P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'st:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'st:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ P' st All goals completed! 🐙

From now on, we will not usually rewrite assertImplies_def explicitly.

Since, after the rw and intro, the remaining steps just apply hypotheses to the goal (and each other), the remaining proof can be compressed into a single tactic: apply_rules. Besides local hypotheses, apply_rules also tries rfl and trivial automatically, and apply_rules [l₁, l₂, …] additionally tries the given lemmas.

theorem hoare_consequence_pre'' {P P' Q : Assertion} {c : Com} (hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') : {{ P }} c {{ Q }} := P:AssertionP':AssertionQ:Assertionc:Comhhoare:{{P'}} ~c {{Q}}himp:P ↠ P'⊢ {{P}} ~c {{Q}} P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'st:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q st' All goals completed! 🐙

The same trick works for hoare_consequence_post.

theorem hoare_consequence_post' {P Q Q' : Assertion} {c : Com} (hhoare : {{ P }} c {{ Q' }}) (himp : Q' ↠ Q) : {{ P }} c {{ Q }} := P:AssertionQ:AssertionQ':Assertionc:Comhhoare:{{P}} ~c {{Q'}}himp:Q' ↠ Q⊢ {{P}} ~c {{Q}} P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q' st'himp:Q' ↠ Q⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q' st'himp:Q' ↠ Qst:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q st' All goals completed! 🐙

We can also leave a metavariable for P' in hoare_asgn_example1, which we did earlier as an example of using the consequence rule:

theorem hoare_asgn_example1' : {{True}} X := 1 {{X = 1}} := ⊢ {{True}} X := 1 {{X = 1}} ⊢ {{?P'}} X := 1 {{X = 1}}⊢ {{True}} ↠ ?P'⊢ Assertion ⊢ {{?P'}} X := 1 {{X = 1}} -- The goal is `{{?P'}} X := 1 {{X = 1}}` All goals completed! 🐙 -- assigns `{{ (X = 1) [X ↦ 1] }}` to `?P'`, closing `case P'` ⊢ {{True}} ↠ (X = 1) [X ↦ 1] st:Statea✝:True⊢ (X = 1) [X ↦ 1] st -- Since `↠` is an implication, we can just use `intro` directly. All goals completed! 🐙

The final bullet of that proof also looks like a candidate for automation.

theorem hoare_asgn_example1'' : {{True}} X := 1 {{X = 1}} := ⊢ {{True}} X := 1 {{X = 1}} ⊢ {{?P'}} X := 1 {{X = 1}}⊢ {{True}} ↠ ?P'⊢ Assertion ⊢ {{?P'}} X := 1 {{X = 1}} All goals completed! 🐙 ⊢ {{True}} ↠ (X = 1) [X ↦ 1] All goals completed! 🐙

Now we have quite a nice proof script: it simply identifies the Hoare rules that need to be used and leaves the remaining low-level details up to Lean to figure out.

By now it might be apparent that the entire proof could be automated by a more ambitious tactic that also knew about the Hoare rules themselves. We won't build one in this chapter, so that we can get a better understanding of when and how the Hoare rules are used. In the next chapter, Hoare2, we'll dive deeper into automating entire proofs of Hoare triples.

The other example of using consequence that we did earlier, assertion_sub_example2, requires a little more work to automate. simp simplifies the assertion implication in the final bullet, but cannot finish it: the leftover goal is arithmetic, so it needs lia.

theorem assertion_sub_example2' : {{X < 4}} X := X + 1 {{X < 5}} := ⊢ {{X < 4}} X := X + 1 {{X < 5}} ⊢ {{?P'}} X := X + 1 {{X < 5}}⊢ {{X < 4}} ↠ ?P'⊢ Assertion ⊢ {{?P'}} X := X + 1 {{X < 5}} All goals completed! 🐙 ⊢ {{X < 4}} ↠ (X < 5) [X ↦ X + 1] ⊢ ∀ (st : State), st[X] < 4 → st["X"] + 1 < 5 -- an arithmetic goal remains All goals completed! 🐙

Let's introduce our own tactic to handle both that bullet and the bullet from example 1. A macro declaration gives a name to a canned sequence of tactics:

Note to developers (Niklas Halonen @xhalo32)

It's unfortunate that simp on its own wouldn't reduce X == Y to false, since X, Y, Z, W are plain defs in Imp; assertion_auto relies on +decide for this. Note that Ident is an abbrev. Making it an implicit_reducible def breaks lia for some reason and doesn't resolve the issue.

@[implicit_reducible]
def Ident := String
deriving BEq, ReflBEq, LawfulBEq, DecidableEq
macro "assertion_auto" : tactic => `(tactic| focus (simp +decide [assertImplies_def, assertIff_def, validHoareTriple_def, Assertion.subst_def] at * <;> lia)) theorem assertion_sub_example2'' : {{X < 4}} X := X + 1 {{X < 5}} := ⊢ {{X < 4}} X := X + 1 {{X < 5}} ⊢ {{?P'}} X := X + 1 {{X < 5}}⊢ {{X < 4}} ↠ ?P'⊢ Assertion ⊢ {{?P'}} X := X + 1 {{X < 5}} All goals completed! 🐙 ⊢ {{X < 4}} ↠ (X < 5) [X ↦ X + 1] All goals completed! 🐙 theorem hoare_asgn_example1''' : {{True}} X := 1 {{X = 1}} := ⊢ {{True}} X := 1 {{X = 1}} ⊢ {{?P'}} X := 1 {{X = 1}}⊢ {{True}} ↠ ?P'⊢ Assertion ⊢ {{?P'}} X := 1 {{X = 1}} All goals completed! 🐙 ⊢ {{True}} ↠ (X = 1) [X ↦ 1] All goals completed! 🐙

Again, we have quite a nice proof script. All the low-level details of proofs about assertions have been taken care of automatically. Of course, assertion_auto isn't able to prove everything we could possibly want to know about assertions — there's no magic here! But it's pretty good.

Exercise★★(hoare_asgn_examples_2)

Prove these triples. Try to make your proof scripts nicely automated by following the examples above.

theorem assertion_sub_ex1' : {{ X ≤ 5 }} X := 2 * X {{ X ≤ 10 }} := ⊢ {{X ≤ 5}} X := 2 * X {{X ≤ 10}} solution! ⊢ {{?P'}} X := 2 * X {{X ≤ 10}}⊢ {{X ≤ 5}} ↠ ?P'⊢ Assertion ⊢ {{?P'}} X := 2 * X {{X ≤ 10}} All goals completed! 🐙 ⊢ {{X ≤ 5}} ↠ (X ≤ 10) [X ↦ 2 * X] All goals completed! 🐙 theorem assertion_sub_ex2' : {{ 0 ≤ 3 ∧ 3 ≤ 5 }} X := 3 {{ 0 ≤ X ∧ X ≤ 5 }} := ⊢ {{0 ≤ 3 ∧ 3 ≤ 5}} X := 3 {{0 ≤ X ∧ X ≤ 5}} solution! ⊢ {{?P'}} X := 3 {{0 ≤ X ∧ X ≤ 5}}⊢ {{0 ≤ 3 ∧ 3 ≤ 5}} ↠ ?P'⊢ Assertion ⊢ {{?P'}} X := 3 {{0 ≤ X ∧ X ≤ 5}} All goals completed! 🐙 ⊢ {{0 ≤ 3 ∧ 3 ≤ 5}} ↠ (0 ≤ X ∧ X ≤ 5) [X ↦ 3] All goals completed! 🐙

5.4.6. Sequencing + Assignment🔗

Here's an example of a program involving both sequencing and assignment. Note the use of hoare_seq in conjunction with hoare_consequence_pre and apply's metavariables.

theorem hoare_asgn_example3 (a : Aexp) (n : Nat) : {{a = n}} X := a; skip {{X = n}} := a:Aexpn:Nat⊢ {{a = n}} X := a; skip {{X = n}} a:Aexpn:Nat⊢ {{?Q}} skip {{X = n}}a:Aexpn:Nat⊢ {{a = n}} X := a {{?Q}}a:Aexpn:Nat⊢ Assertion a:Aexpn:Nat⊢ {{?Q}} skip {{X = n}} -- right part of seq All goals completed! 🐙 a:Aexpn:Nat⊢ {{a = n}} X := a {{X = n}} -- left part of seq a:Aexpn:Nat⊢ {{?h₂.P'}} X := a {{X = n}}a:Aexpn:Nat⊢ {{a = n}} ↠ ?h₂.P'a:Aexpn:Nat⊢ Assertion a:Aexpn:Nat⊢ {{?h₂.P'}} X := a {{X = n}} All goals completed! 🐙 a:Aexpn:Nat⊢ {{a = n}} ↠ (X = n) [X ↦ a] All goals completed! 🐙

Informally, a nice way of displaying a proof using the sequencing rule is as a "decorated program" where the intermediate assertion Q is written between c₁ and c₂:

         {{ a = n }}
X := a
         {{ X = n }};    <--- decoration for Q
skip
         {{ X = n }}

We'll come back to the idea of decorated programs in much more detail in the next chapter.

Exercise★★(hoare_asgn_example4)

Translate this "decorated program" into a formal proof:

               {{ True }} ↠
               {{ 1 = 1 }}
X := 1
               {{ X = 1 }} ↠
               {{ X = 1 ∧ 2 = 2 }};
Y := 2
               {{ X = 1 ∧ Y = 2 }}

Note the use of "↠" decorations, each marking a use of hoare_consequence_pre.

We've started you off by providing a use of hoare_seq that explicitly identifies X = 1 as the intermediate assertion.

theorem hoare_asgn_example4 : {{ True }} X := 1; Y := 2 {{ X = 1 ∧ Y = 2 }} := ⊢ {{True}} X := 1; Y := 2 {{X = 1 ∧ Y = 2}} ⊢ {{X = 1}} Y := 2 {{X = 1 ∧ Y = 2}}⊢ {{True}} X := 1 {{X = 1}} ⊢ {{X = 1}} Y := 2 {{X = 1 ∧ Y = 2}} -- right part of seq solution! ⊢ {{?h₁.P'}} Y := 2 {{X = 1 ∧ Y = 2}}⊢ {{X = 1}} ↠ ?h₁.P'⊢ Assertion ⊢ {{?h₁.P'}} Y := 2 {{X = 1 ∧ Y = 2}} All goals completed! 🐙 ⊢ {{X = 1}} ↠ (X = 1 ∧ Y = 2) [Y ↦ 2] All goals completed! 🐙 ⊢ {{True}} X := 1 {{X = 1}} -- left part of seq solution! ⊢ {{?h₂.P'}} X := 1 {{X = 1}}⊢ {{True}} ↠ ?h₂.P'⊢ Assertion ⊢ {{?h₂.P'}} X := 1 {{X = 1}} All goals completed! 🐙 ⊢ {{True}} ↠ (X = 1) [X ↦ 1] All goals completed! 🐙
Exercise★★★(swap_exercise) (Manually graded)

Write an Imp program c that swaps the values of X and Y and show that it satisfies the following specification:

{{X ≤ Y}} c {{Y ≤ X}}

Your proof should not need to use rw [validHoareTriple_def].

Hints:

  • Remember that Imp commands need to be enclosed in imp { … } brackets.

  • Remember that the assignment rule works best when it's applied "back to front," from the postcondition to the precondition. So your proof will want to start at the end and work back to the beginning of your program.

  • Remember that apply is your friend.

Note to developers
HIDE: CH: Here goes:
[[
  {{ X ≤ Y }}
    Z := X
            {{ Z ≤ Y }};
    X := Y
            {{ Z ≤ X }};
    Y := Z
  {{ Y ≤ X }}
]]
   The _only_ catch is that one needs to do it backwards, since that's
   how the hoare_asgn rule is defined.
   Maybe move this decorated program to the decorated programs
   section, since it's a good warm-up exercise.
def swapProgram : Com := solution!(imp { Z := X; X := Y; Y := Z }) theorem swap_exercise : {{X ≤ Y}} swapProgram {{Y ≤ X}} := ⊢ {{X ≤ Y}} ~swapProgram {{Y ≤ X}} solution! ⊢ {{X ≤ Y}} Z := X; X := Y; Y := Z {{Y ≤ X}} ⊢ {{?Q}} X := Y; Y := Z {{Y ≤ X}}⊢ {{X ≤ Y}} Z := X {{?Q}}⊢ Assertion ⊢ {{?Q}} X := Y; Y := Z {{Y ≤ X}} ⊢ {{?h₁.Q}} Y := Z {{Y ≤ X}}⊢ {{?Q✝}} X := Y {{?h₁.Q}}⊢ Assertion ⊢ {{?h₁.Q}} Y := Z {{Y ≤ X}} All goals completed! 🐙 ⊢ {{?Q✝}} X := Y {{(Y ≤ X) [Y ↦ Z]}} All goals completed! 🐙 ⊢ {{X ≤ Y}} Z := X {{((Y ≤ X) [Y ↦ Z]) [X ↦ Y]}} ⊢ {{?h₂.P'}} Z := X {{((Y ≤ X) [Y ↦ Z]) [X ↦ Y]}}⊢ {{X ≤ Y}} ↠ ?h₂.P'⊢ Assertion ⊢ {{?h₂.P'}} Z := X {{((Y ≤ X) [Y ↦ Z]) [X ↦ Y]}} All goals completed! 🐙 ⊢ {{X ≤ Y}} ↠ (((Y ≤ X) [Y ↦ Z]) [X ↦ Y]) [Z ↦ X] All goals completed! 🐙
Exercise★★★★(invalid_triple) (Advanced)

Show that

{{ a = n }} X := 3; Y := a {{ Y = n }}

is not a valid Hoare triple for some choices of a and n.

Conceptual hint: Invent a particular a and n for which the triple is invalid, then use those to complete the proof.

Technical hint: Hypothesis h below begins ∀ a n, .... You'll want to instantiate that with the particular a and n you've invented. You can do that with have and apply, but you may remember (from the Tactics chapter of Logical Foundations) that Lean offers an even easier tactic: specialize. If you write

specialize h your_a your_n

the hypothesis will be instantiated on your_a and your_n.

Having chosen your a and n, proceed as follows:

  • Use the (assumed) validity of the given hoare triple to derive a state st' in which Y has some value y1

  • Use the evaluation rules (EvalR.seq and EvalR.asgn) to show that Y has a different value y2 in the same final state st'

  • Since y1 and y2 are both equal to st'[Y], they are equal to each other. But we chose them to be different, so this is a contradiction, which finishes the proof.

theorem invalid_triple : ¬ ∀ (a : Aexp) (n : Nat), {{ a = n }} X := 3; Y := a {{ Y = n }} := ⊢ ¬∀ (a : Aexp) (n : Nat), {{a = n}} X := 3; Y := a {{Y = n}} h:∀ (a : Aexp) (n : Nat), {{a = n}} X := 3; Y := a {{Y = n}}⊢ False h:∀ (a : Aexp) (n : Nat) {st st' : State}, (st =[ X := 3; Y := a ]=> st') → Aexp.eval st a = n → st'[Y] = n⊢ False solution! h:∀ (a : Aexp) (n : Nat) {st st' : State}, (st =[ X := 3; Y := a ]=> st') → Aexp.eval st a = n → st'[Y] = n⊢ {X ↦ 2} =[ X := 3; Y := X ]=> {Y ↦ 3, X ↦ 3, X ↦ 2}h:Aexp.eval {X ↦ 2} (aexp {X}) = 2 → {Y ↦ 3, X ↦ 3, X ↦ 2}[Y] = 2⊢ False h:∀ (a : Aexp) (n : Nat) {st st' : State}, (st =[ X := 3; Y := a ]=> st') → Aexp.eval st a = n → st'[Y] = n⊢ {X ↦ 2} =[ X := 3; Y := X ]=> {Y ↦ 3, X ↦ 3, X ↦ 2} h:∀ (a : Aexp) (n : Nat) {st st' : State}, (st =[ X := 3; Y := a ]=> st') → Aexp.eval st a = n → st'[Y] = n⊢ {X ↦ 2} =[ X := 3 ]=> ?st'h:∀ (a : Aexp) (n : Nat) {st st' : State}, (st =[ X := 3; Y := a ]=> st') → Aexp.eval st a = n → st'[Y] = n⊢ ?st' =[ Y := X ]=> {Y ↦ 3, X ↦ 3, X ↦ 2}h:∀ (a : Aexp) (n : Nat) {st st' : State}, (st =[ X := 3; Y := a ]=> st') → Aexp.eval st a = n → st'[Y] = n⊢ State h:∀ (a : Aexp) (n : Nat) {st st' : State}, (st =[ X := 3; Y := a ]=> st') → Aexp.eval st a = n → st'[Y] = n⊢ {X ↦ 2} =[ X := 3 ]=> ?st' All goals completed! 🐙 h:∀ (a : Aexp) (n : Nat) {st st' : State}, (st =[ X := 3; Y := a ]=> st') → Aexp.eval st a = n → st'[Y] = n⊢ ("X" →ₜ Aexp.eval {X ↦ 2} (aexp {3}) ; {X ↦ 2}) =[ Y := X ]=> {Y ↦ 3, X ↦ 3, X ↦ 2} All goals completed! 🐙 All goals completed! 🐙

5.4.7. Conditionals🔗

What sort of rule do we want for reasoning about conditional commands?

Certainly, if the same assertion Q holds after executing either of the branches, then it holds after the whole conditional. So we might be tempted to write:

        {{P}} c₁ {{Q}}
        {{P}} c₂ {{Q}}
--------------------------------
{{P}} if b then c₁ else c₂ {{Q}}

However, this is rather weak. For example, using this rule, we cannot show

{{ True }}
  if X = 0
    then Y := 2
    else Y := X + 1
  end
{{ X ≤ Y }}

since the rule doesn't tell us enough about the state in which the assignments take place in the "then" and "else" branches.

Fortunately, we can say something more precise. In the "then" branch, we know that the boolean expression b evaluates to true, and in the "else" branch, we know it evaluates to false. Making this information available in the premises of the rule gives us more information to work with when reasoning about the behavior of c₁ and c₂ (i.e., the reasons why they establish the postcondition Q).

        {{P ∧   b}} c₁ {{Q}}
        {{P ∧ ¬ b}} c₂ {{Q}}
------------------------------------  (hoare_if)
{{P}} if b then c₁ else c₂ end {{Q}}

To interpret this rule formally, we need to do a little work. Strictly speaking, the assertion we've written, P ∧ b, is the conjunction of an assertion and a boolean expression — i.e., it doesn't typecheck. To fix this, we need a way of formally "lifting" any Bexp b to an assertion. Inside the {{ }} brackets, a boolean expression b stands for the assertion "the boolean expression b evaluates to true (in the given state)," that is, fun st => b.eval st = true.

Note to developers (Niklas Halonen @xhalo32)

I have removed bassertion as it's an unnecessary abstraction and only adds overhead for the reader.

Now we can formalize the Hoare proof rule for conditionals and prove it correct.

theorem hoare_if {P Q : Assertion} {b : Bexp} {c₁ c₂ : Com} (htrue : {{ P ∧ b }} c₁ {{ Q }}) (hfalse : {{ P ∧ ¬ b }} c₂ {{ Q }}) : {{ P }} if (b) { c₁ } else { c₂ } {{ Q }} := P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:{{P ∧ b}} ~c₁ {{Q}}hfalse:{{P ∧ ¬b}} ~c₂ {{Q}}⊢ {{P}} if (b) {c₁} else {c₂} {{Q}} P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st st' : State}, (st =[ c₁ ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:∀ {st st' : State}, (st =[ c₂ ]=> st') → P st ∧ ¬Bexp.eval st b = true → Q st'⊢ ∀ {st st' : State}, (st =[ if (b) {c₁} else {c₂} ]=> st') → P st → Q st' P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st st' : State}, (st =[ c₁ ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:∀ {st st' : State}, (st =[ c₂ ]=> st') → P st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Stateheval:st =[ if (b) {c₁} else {c₂} ]=> st'hpre:P st⊢ Q st' inversion heval with P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st st' : State}, (st =[ c₁ ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:∀ {st st' : State}, (st =[ c₂ ]=> st') → P st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statehpre:P sthb:Bexp.eval st b = truehc:st =[ ~c₁ ]=> st'⊢ Q st' All goals completed! 🐙 P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st st' : State}, (st =[ c₁ ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:∀ {st st' : State}, (st =[ c₂ ]=> st') → P st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statehpre:P sthb:Bexp.eval st b = falsehc:st =[ ~c₂ ]=> st'⊢ Q st' P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st st' : State}, (st =[ c₁ ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:∀ {st st' : State}, (st =[ c₂ ]=> st') → P st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statehpre:P sthb:¬Bexp.eval st b = truehc:st =[ ~c₂ ]=> st'⊢ Q st' All goals completed! 🐙

5.4.7.1. Example🔗

Here is a formal proof that the program we used to motivate the rule satisfies the specification we wanted.

theorem if_example : {{True}} if (X = 0) { Y := 2 } else { Y := X + 1 } {{X ≤ Y}} := ⊢ {{True}} if (X = 0) {Y := 2} else {Y := X + 1} {{X ≤ Y}} ⊢ {{True ∧ bexp {X = 0} }} Y := 2 {{X ≤ Y}}⊢ {{True ∧ ¬bexp {X = 0} }} Y := X + 1 {{X ≤ Y}} ⊢ {{True ∧ bexp {X = 0} }} Y := 2 {{X ≤ Y}} -- Then ⊢ {{?htrue.P'}} Y := 2 {{X ≤ Y}}⊢ {{True ∧ bexp {X = 0} }} ↠ ?htrue.P'⊢ Assertion ⊢ {{?htrue.P'}} Y := 2 {{X ≤ Y}} All goals completed! 🐙 ⊢ {{True ∧ bexp {X = 0} }} ↠ (X ≤ Y) [Y ↦ 2] All goals completed! 🐙 ⊢ {{True ∧ ¬bexp {X = 0} }} Y := X + 1 {{X ≤ Y}} -- Else ⊢ {{?hfalse.P'}} Y := X + 1 {{X ≤ Y}}⊢ {{True ∧ ¬bexp {X = 0} }} ↠ ?hfalse.P'⊢ Assertion ⊢ {{?hfalse.P'}} Y := X + 1 {{X ≤ Y}} All goals completed! 🐙 ⊢ {{True ∧ ¬bexp {X = 0} }} ↠ (X ≤ Y) [Y ↦ X + 1] All goals completed! 🐙

We can even shorten it a little bit more. Wherever Lean expects a term of some type, we may write (by <tactics>) in its place: the tactics run immediately, and the proof they produce is spliced in as that term. Here we use it to supply hoare_consequence_pre's second argument, the implication P ↠ P', directly at the call site, instead of apply-ing hoare_consequence_pre and discharging that goal afterward with a separate bullet.

theorem if_example' : {{True}} if (X = 0) { Y := 2 } else { Y := X + 1 } {{X ≤ Y}} := ⊢ {{True}} if (X = 0) {Y := 2} else {Y := X + 1} {{X ≤ Y}} ⊢ {{True ∧ bexp {X = 0} }} Y := 2 {{X ≤ Y}}⊢ {{True ∧ ¬bexp {X = 0} }} Y := X + 1 {{X ≤ Y}} ⊢ {{True ∧ bexp {X = 0} }} Y := 2 {{X ≤ Y}}⊢ {{True ∧ ¬bexp {X = 0} }} Y := X + 1 {{X ≤ Y}} apply hoare_consequence_pre hoare_asgn (⊢ {{True ∧ ¬bexp {X = 0} }} ↠ (X ≤ Y) [Y ↦ X + 1] All goals completed! 🐙)
Exercise★★(if_minus_plus)

Prove the theorem below using hoare_if. Do not unfold ValidHoareTriple (i.e., do not use validHoareTriple_def). The assertion_auto tactic defined above may be useful.

theorem if_minus_plus : {{True}} if (X ≤ Y) { Z := Y - X } else { Y := X + Z } {{Y = X + Z}} := ⊢ {{True}} if (X ≤ Y) {Z := Y - X} else {Y := X + Z} {{Y = X + Z}} solution! ⊢ {{True ∧ bexp {X ≤ Y} }} Z := Y - X {{Y = X + Z}}⊢ {{True ∧ ¬bexp {X ≤ Y} }} Y := X + Z {{Y = X + Z}} ⊢ {{True ∧ bexp {X ≤ Y} }} Z := Y - X {{Y = X + Z}}⊢ {{True ∧ ¬bexp {X ≤ Y} }} Y := X + Z {{Y = X + Z}} apply hoare_consequence_pre hoare_asgn (⊢ {{True ∧ ¬bexp {X ≤ Y} }} ↠ (Y = X + Z) [Y ↦ X + Z] All goals completed! 🐙)

5.4.7.2. Exercise: One-sided conditionals🔗

Note to developers

HIDE: Question from 2012, Midterm 2. One-sided conditionals.

In this exercise we consider extending Imp with "one-sided conditionals" of the form if1 (b) { c }. Here b is a boolean expression, and c is a command. If b evaluates to true, then command c is evaluated. If b evaluates to false, then if1 (b) { c } does nothing.

We recommend that you complete this exercise before attempting the ones that follow, as it should help solidify your understanding of the material.

The first step is to extend the syntax of commands and introduce the usual notations. (We've done this for you, in a separate namespace to prevent polluting the global name space. The scoped notations below are active only inside namespace If1.)

namespace If1 inductive Com : Type where | skip : Com | asgn : Ident → Aexp → Com | seq : Com → Com → Com | cond : Bexp → Com → Com → Com | whileDo : Bexp → Com → Com | if1 : Bexp → Com → Com

We also need to extend the imp { } notation to parse the new if1 command.

Notation encoding: commands, macro rules/-- One-sided conditional -/ scoped syntax "if1 " "(" imp_bexp ")" ppHardSpace "{" imp_com "}" : imp_com namespace Com open Lean Imp.Elab scoped macro_rules | `(imp { $s }) => do let stx ← match s with | `(imp_com| skip) => ``(Com.skip) | `(imp_com| $x:ident) => ``(($x : Com)) | `(imp_com| $c₁ ; $c₂) => ``(Com.seq (imp {$c₁}) (imp {$c₂})) | `(imp_com| $x:ident := $a) => ``(Com.asgn $x (aexp {$a})) | `(imp_com| if ($b) {$c₁} else {$c₂}) => ``(Com.cond (bexp {$b}) (imp {$c₁}) (imp {$c₂})) | `(imp_com| while ($b) {$c}) => ``(Com.whileDo (bexp {$b}) (imp {$c})) | `(imp_com| if1 ($b) {$c}) => ``(Com.if1 (bexp {$b}) (imp {$c})) | `(imp_com| ~$c) => `(($c : Com)) | _ => Macro.throwUnsupported return withSourceInfoOf s stx end Com open scoped Com

The delaborators are re-instantiated the same way: the Imp printer is parameterized over the namespace of the command constructors, so the extended printer is that printer at If1.Com plus one case for if1.

namespace Delab open Lean PrettyPrinter Imp.Delab @[app_unexpander Com.if1] private def Com.unexpandIf1 : Unexpander | `($_ $b $c) => `(imp { if1 ($(getBexp b)) { $(getImp c) } }) | _ => throw () attribute [app_unexpander Com.skip] unexpandComSkip attribute [app_unexpander Com.asgn] unexpandComAsgn attribute [app_unexpander Com.seq] unexpandComSeq attribute [app_unexpander Com.cond] unexpandComCond attribute [app_unexpander Com.whileDo] unexpandComWhileDo end Delab
Exercise★★(if1_ceval)

Add two new evaluation rules to relation Com.EvalR, below, for if1. Let the rules for if guide you.

inductive Com.EvalR : Com → State → State → Prop where | skip {st : State} : EvalR (imp {skip}) st st | asgn {st : State} {a : Aexp} {n : Nat} {x : Ident} (h : a.eval st = n) : EvalR (imp {x := a}) st (x →ₜ n ; st) | seq {c₁ c₂ : Com} {st st' st'' : State} (h₁ : EvalR c₁ st st') (h₂ : EvalR c₂ st' st'') : EvalR (imp {c₁; c₂}) st st'' | ifTrue {st st' : State} {b : Bexp} {c₁ c₂ : Com} (hb : b.eval st = true) (hc : EvalR c₁ st st') : EvalR (imp {if (b) {c₁} else {c₂} }) st st' | ifFalse {st st' : State} {b : Bexp} {c₁ c₂ : Com} (hb : b.eval st = false) (hc : EvalR c₂ st st') : EvalR (imp {if (b) {c₁} else {c₂} }) st st' | whileFalse {b : Bexp} {st : State} {c : Com} (hb : b.eval st = false) : EvalR (imp {while (b) {c} }) st st | whileTrue {st st' st'' : State} {b : Bexp} {c : Com} (hb : b.eval st = true) (hc : EvalR c st st') (hloop : Com.EvalR (imp {while (b) {c} }) st' st'') : EvalR (imp {while (b) {c} }) st st'' | if1True {st st' : State} {b : Bexp} {c : Com} (hb : b.eval st = true) (hc : EvalR c st st') : EvalR (imp {if1 (b) {c} }) st st' | if1False {st : State} {b : Bexp} {c : Com} (hb : b.eval st = false) : EvalR (imp {if1 (b) {c} }) st st instance : HasEval Com State State where Eval := Com.EvalR @[simp] theorem Com.evalR_eq {c : Com} {st st' : State} : EvalR c st st' ↔ st =[ c ]=> st' := c:Comst:Statest':State⊢ c.EvalR st st' ↔ st =[ c ]=> st' All goals completed! 🐙 attribute [app_delab Com.EvalR] HasEval.Delab.delabEvalR

The following unit tests should be provable simply by applying your new rules (plus rfl for the boolean side conditions) if you have defined them correctly.

theorem if1true_test : ∅ =[ if1 (X = 0) { X := 1 } ]=> {X ↦ 1} := ⊢ ∅ =[ if1 (X = 0) {X := 1} ]=> {X ↦ 1} solution! ⊢ Bexp.eval ∅ (bexp {X = 0}) = true⊢ ∅ =[ X := 1 ]=> {X ↦ 1} ⊢ Bexp.eval ∅ (bexp {X = 0}) = true All goals completed! 🐙 ⊢ ∅ =[ X := 1 ]=> {X ↦ 1} ⊢ Aexp.eval ∅ (aexp {1}) = (X ↦ 1).value ⊢ Aexp.eval ∅ (aexp {1}) = (X ↦ 1).value All goals completed! 🐙 theorem if1false_test : {X ↦ 2} =[ if1 (X = 0) { X := 1 } ]=> {X ↦ 2} := ⊢ {X ↦ 2} =[ if1 (X = 0) {X := 1} ]=> {X ↦ 2} solution! ⊢ Bexp.eval {X ↦ 2} (bexp {X = 0}) = false ⊢ Bexp.eval {X ↦ 2} (bexp {X = 0}) = false All goals completed! 🐙

Now we have to repeat the definition of Hoare triples, so that it uses the updated Com type. The {{ P }} c {{ Q }} notation itself is generic: it only needs a new HasTriple instance.

def ValidHoareTriple (P : Assertion) (c : Com) (Q : Assertion) : Prop := ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' instance : HasTriple Com where Triple := ValidHoareTriple theorem validHoareTriple_def {P : Assertion} {c : Com} {Q : Assertion} : {{ P }} c {{ Q }} ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' := P:Assertionc:ComQ:Assertion⊢ {{P}} ~c {{Q}} ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' All goals completed! 🐙 attribute [irreducible] ValidHoareTriple
Exercise★★(hoare_if1) (Manually graded)

Invent a Hoare logic proof rule for if1. State and prove a theorem named hoare_if1 that shows the validity of your rule. Use hoare_if as a guide. Try to invent a rule that is complete, meaning it can be used to prove the correctness of as many one-sided conditionals as possible. Also try to keep your rule compositional, meaning that any Imp command that appears in a premise should syntactically be a part of the command in the conclusion.

Hint: if you encounter difficulty getting Lean to parse part of your rule as an assertion, try wrapping it in the {{ … }} brackets (and in parentheses, when it is an argument of ↠). For example, if you want P ∧ ¬ b to be read as an assertion, write it as ({{ P ∧ ¬ b }}).

theorem hoare_if1 {b : Bexp} {c : Com} {P Q : Assertion} (htrue : {{ P ∧ b }} c {{ Q }}) (hfalse : ({{ P ∧ ¬ b }}) ↠ Q) : {{ P }} if1 (b) { c } {{ Q }} := b:Bexpc:ComP:AssertionQ:Assertionhtrue:{{P ∧ b}} ~c {{Q}}hfalse:{{P ∧ ¬b}} ↠ Q⊢ {{P}} if1 (b) {c} {{Q}} b:Bexpc:ComP:AssertionQ:Assertionhtrue:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:{{P ∧ ¬b}} ↠ Q⊢ ∀ {st st' : State}, (st =[ if1 (b) {c} ]=> st') → P st → Q st' b:Bexpc:ComP:AssertionQ:Assertionhtrue:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:{{P ∧ ¬b}} ↠ Qst:Statest':Stateheval:st =[ if1 (b) {c} ]=> st'hpre:P st⊢ Q st' inversion heval with b:Bexpc:ComP:AssertionQ:Assertionhtrue:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:{{P ∧ ¬b}} ↠ Qst:Statest':Statehpre:P sthb:Bexp.eval st b = truehc:st =[ ~c ]=> st'⊢ Q st' All goals completed! 🐙 b:Bexpc:ComP:AssertionQ:Assertionhtrue:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:{{P ∧ ¬b}} ↠ Qst:Statehpre:P sthb:Bexp.eval st b = false⊢ Q st b:Bexpc:ComP:AssertionQ:Assertionhtrue:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → Q st'hfalse:{{P ∧ ¬b}} ↠ Qst:Statehpre:P sthb:Bexp.eval st b = false⊢ P st ∧ ¬Bexp.eval st b = true All goals completed! 🐙

For example (hoare_if1_good) your rule should be strong enough to show the following Hoare triple is valid:

{{ X + Y = Z }}
if1 (Y ≠ 0) {
  X := X + Y
}
{{ X = Z }}

Before the next exercise, we need to restate the Hoare rules of consequence (for preconditions) and assignment for the new Com type.

theorem hoare_consequence_pre {P P' Q : Assertion} {c : Com} (hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') : {{ P }} c {{ Q }} := P:AssertionP':AssertionQ:Assertionc:Comhhoare:{{P'}} ~c {{Q}}himp:P ↠ P'⊢ {{P}} ~c {{Q}} P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'st:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q st' All goals completed! 🐙 theorem hoare_asgn {Q : Assertion} {x : Ident} {a : Aexp} : {{Q [x ↦ a]}} x := a {{ Q }} := Q:Assertionx:Identa:Aexp⊢ {{Q [x ↦ a]}} x := a {{Q}} Q:Assertionx:Identa:Aexp⊢ ∀ {st st' : State}, (st =[ x := a ]=> st') → Q [x ↦ a] st → Q st' Q:Assertionx:Identa:Aexpst:Statest':Stateheval:st =[ x := a ]=> st'hQ:Q [x ↦ a] st⊢ Q st' Q:Assertionx:Identa:Aexpst:Statest':Stateheval:st =[ x := a ]=> st'hQ:Q (x →ₜ Aexp.eval st a ; st)⊢ Q st' inversion heval with Q:Assertionx:Identa:Aexpst:StatehQ:Q (x →ₜ Aexp.eval st a ; st)n:Nath:Aexp.eval st a = n⊢ Q (x →ₜ n ; st) Q:Assertionx:Identa:Aexpst:StatehQ:Q (x →ₜ Aexp.eval st a ; st)⊢ Q (x →ₜ Aexp.eval st a ; st) All goals completed! 🐙
Exercise★★(hoare_if1_good)

Use your if1 rule to prove the following (valid) Hoare triple.

Hint: assertion_auto will once again get you most but not all the way to a completely automated proof. You can finish manually, or tweak the tactic further.

Hint: If you see a message about failing to unify commands from the top-level Com with commands from this namespace, it probably means you are using a definition or theorem (e.g., hoare_skip) from above this exercise without re-proving it for the new version of Imp with if1.

theorem hoare_if1_good : {{ X + Y = Z }} if1 (Y ≠ 0) { X := X + Y } {{ X = Z }} := ⊢ {{X + Y = Z}} if1 (Y ≠ 0) {X := X + Y} {{X = Z}} solution! ⊢ {{X + Y = Z ∧ bexp {Y ≠ 0} }} X := X + Y {{X = Z}}⊢ {{X + Y = Z ∧ ¬bexp {Y ≠ 0} }} ↠ {{X = Z}} ⊢ {{X + Y = Z ∧ bexp {Y ≠ 0} }} X := X + Y {{X = Z}} ⊢ {{?htrue.P'}} X := X + Y {{X = Z}}⊢ {{X + Y = Z ∧ bexp {Y ≠ 0} }} ↠ ?htrue.P'⊢ Assertion ⊢ {{?htrue.P'}} X := X + Y {{X = Z}} All goals completed! 🐙 ⊢ {{X + Y = Z ∧ bexp {Y ≠ 0} }} ↠ (X = Z) [X ↦ X + Y] All goals completed! 🐙 ⊢ {{X + Y = Z ∧ ¬bexp {Y ≠ 0} }} ↠ {{X = Z}} All goals completed! 🐙
end If1

5.4.8. While Loops🔗

The Hoare rule for while loops is based on the idea of a command invariant (or just invariant): an assertion whose truth is guaranteed after executing a command, assuming it is true before.

That is, an assertion P is a command invariant of c if

{{P}} c {{P}}

holds. Note that the command invariant might temporarily become false in the middle of executing c, but by the end of c it must be restored.

As a first attempt at a while rule, we could try:

       {{P}} c {{P}}
---------------------------
{{P}} while b do c end {{P}}

This rule is valid: if P is a command invariant of c, as the premise requires, then, no matter how many times the loop body executes, P is going to be true when the loop finally finishes.

But the rule also omits two crucial pieces of information. First, the loop terminates when b becomes false. So we can strengthen the postcondition in the conclusion:

          {{P}} c {{P}}
---------------------------------
{{P}} while b do c end {{P ∧ ¬b}}

Second, the loop body will be executed only if b is true. So we can also strengthen the precondition in the premise:

        {{P ∧ b}} c {{P}}
--------------------------------- (hoare_while)
{{P}} while b do c end {{P ∧ ¬b}}

That is the Hoare while rule. Note how it combines aspects of skip and conditionals:

  • If the loop body executes zero times, the rule is like skip in that the precondition survives to become (part of) the postcondition.

  • Like a conditional, we can assume guard b holds on entry to the subcommand.

theorem hoare_while {P : Assertion} {b : Bexp} {c : Com} (hhoare : {{P ∧ b}} c {{ P }}) : {{ P }} while (b) { c } {{P ∧ ¬ b}} := P:Assertionb:Bexpc:Comhhoare:{{P ∧ b}} ~c {{P}}⊢ {{P}} while (b) {c} {{P ∧ ¬b}} P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'⊢ ∀ {st st' : State}, (st =[ while (b) {c} ]=> st') → P st → P st' ∧ ¬Bexp.eval st' b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Stateheval:st =[ while (b) {c} ]=> st'hpre:P st⊢ P st' ∧ ¬Bexp.eval st' b = true /- We proceed by induction on `heval`, because, in the "keep looping" case, its hypotheses talk about the whole loop instead of just `c`. We begin by generalizing over an arbitrary command, together with an equation remembering that the command is the original loop. The cases for commands other than `while` are dismissed because their equations are contradictory. -/ P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statehpre:P stcmd:Comheq:imp {while (b) {c} } = cmdheval:st =[ cmd ]=> st'⊢ P st' ∧ ¬Bexp.eval st' b = true induction heval with P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comb✝:Bexpst✝:Statec✝:Comhb:Bexp.eval st✝ b✝ = falsehpre:P st✝heq:imp {while (b) {c} } = imp {while (b✝) {c✝} }⊢ P st✝ ∧ ¬Bexp.eval st✝ b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comb✝:Bexpst✝:Statec✝:Comhb:Bexp.eval st✝ b✝ = falsehpre:P st✝hbeq:b = b✝hceq:c = c✝⊢ P st✝ ∧ ¬Bexp.eval st✝ b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statehpre:P st✝hb:Bexp.eval st✝ b = false⊢ P st✝ ∧ ¬Bexp.eval st✝ b = true exact ⟨hpre, P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statehpre:P st✝hb:Bexp.eval st✝ b = false⊢ ¬Bexp.eval st✝ b = true All goals completed! 🐙⟩ P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:Stateb✝:Bexpc✝:Comhb:Bexp.eval st✝ b✝ = truehc:st✝ =[ ~c✝ ]=> st'✝hloop:st'✝ =[ while (b✝) {c✝} ]=> st''✝ih₁:P st✝ → imp {while (b) {c} } = c✝ → P st'✝ ∧ ¬Bexp.eval st'✝ b = trueih₂:P st'✝ → imp {while (b) {c} } = imp {while (b✝) {c✝} } → P st''✝ ∧ ¬Bexp.eval st''✝ b = truehpre:P st✝heq:imp {while (b) {c} } = imp {while (b✝) {c✝} }⊢ P st''✝ ∧ ¬Bexp.eval st''✝ b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:Stateb✝:Bexpc✝:Comhb:Bexp.eval st✝ b✝ = truehc:st✝ =[ ~c✝ ]=> st'✝hloop:st'✝ =[ while (b✝) {c✝} ]=> st''✝ih₁:P st✝ → imp {while (b) {c} } = c✝ → P st'✝ ∧ ¬Bexp.eval st'✝ b = trueih₂:P st'✝ → imp {while (b) {c} } = imp {while (b✝) {c✝} } → P st''✝ ∧ ¬Bexp.eval st''✝ b = truehpre:P st✝hbeq:b = b✝hceq:c = c✝⊢ P st''✝ ∧ ¬Bexp.eval st''✝ b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:Statehpre:P st✝hb:Bexp.eval st✝ b = truehc:st✝ =[ ~c ]=> st'✝ih₁:P st✝ → imp {while (b) {c} } = c → P st'✝ ∧ ¬Bexp.eval st'✝ b = truehloop:st'✝ =[ while (b) {c} ]=> st''✝ih₂:P st'✝ → imp {while (b) {c} } = imp {while (b) {c} } → P st''✝ ∧ ¬Bexp.eval st''✝ b = true⊢ P st''✝ ∧ ¬Bexp.eval st''✝ b = true All goals completed! 🐙 P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statehpre:P st✝heq:imp {while (b) {c} } = imp {skip}⊢ P st✝ ∧ ¬Bexp.eval st✝ b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statea✝:Aexpn✝:Natx✝:Identh✝:Aexp.eval st✝ a✝ = n✝hpre:P st✝heq:imp {while (b) {c} } = imp {x✝ := a✝}⊢ P (x✝ →ₜ n✝ ; st✝) ∧ ¬Bexp.eval (x✝ →ₜ n✝ ; st✝) b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comc₁✝:Comc₂✝:Comst✝:Statest'✝:Statest''✝:Stateh₁✝:st✝ =[ ~c₁✝ ]=> st'✝h₂✝:st'✝ =[ ~c₂✝ ]=> st''✝h₁_ih✝:P st✝ → imp {while (b) {c} } = c₁✝ → P st'✝ ∧ ¬Bexp.eval st'✝ b = trueh₂_ih✝:P st'✝ → imp {while (b) {c} } = c₂✝ → P st''✝ ∧ ¬Bexp.eval st''✝ b = truehpre:P st✝heq:imp {while (b) {c} } = imp {c₁✝; c₂✝}⊢ P st''✝ ∧ ¬Bexp.eval st''✝ b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = truehc✝:st✝ =[ ~c₁✝ ]=> st'✝hc_ih✝:P st✝ → imp {while (b) {c} } = c₁✝ → P st'✝ ∧ ¬Bexp.eval st'✝ b = truehpre:P st✝heq:imp {while (b) {c} } = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ P st'✝ ∧ ¬Bexp.eval st'✝ b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = falsehc✝:st✝ =[ ~c₂✝ ]=> st'✝hc_ih✝:P st✝ → imp {while (b) {c} } = c₂✝ → P st'✝ ∧ ¬Bexp.eval st'✝ b = truehpre:P st✝heq:imp {while (b) {c} } = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ P st'✝ ∧ ¬Bexp.eval st'✝ b = true P:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = falsehc✝:st✝ =[ ~c₂✝ ]=> st'✝hc_ih✝:P st✝ → imp {while (b) {c} } = c₂✝ → P st'✝ ∧ ¬Bexp.eval st'✝ b = truehpre:P st✝heq:imp {while (b) {c} } = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ P st'✝ ∧ ¬Bexp.eval st'✝ b = trueP:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = truehc✝:st✝ =[ ~c₁✝ ]=> st'✝hc_ih✝:P st✝ → imp {while (b) {c} } = c₁✝ → P st'✝ ∧ ¬Bexp.eval st'✝ b = truehpre:P st✝heq:imp {while (b) {c} } = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ P st'✝ ∧ ¬Bexp.eval st'✝ b = trueP:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comc₁✝:Comc₂✝:Comst✝:Statest'✝:Statest''✝:Stateh₁✝:st✝ =[ ~c₁✝ ]=> st'✝h₂✝:st'✝ =[ ~c₂✝ ]=> st''✝h₁_ih✝:P st✝ → imp {while (b) {c} } = c₁✝ → P st'✝ ∧ ¬Bexp.eval st'✝ b = trueh₂_ih✝:P st'✝ → imp {while (b) {c} } = c₂✝ → P st''✝ ∧ ¬Bexp.eval st''✝ b = truehpre:P st✝heq:imp {while (b) {c} } = imp {c₁✝; c₂✝}⊢ P st''✝ ∧ ¬Bexp.eval st''✝ b = trueP:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statea✝:Aexpn✝:Natx✝:Identh✝:Aexp.eval st✝ a✝ = n✝hpre:P st✝heq:imp {while (b) {c} } = imp {x✝ := a✝}⊢ P (x✝ →ₜ n✝ ; st✝) ∧ ¬Bexp.eval (x✝ →ₜ n✝ ; st✝) b = trueP:Assertionb:Bexpc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P st ∧ Bexp.eval st b = true → P st'st:Statest':Statecmd:Comst✝:Statehpre:P st✝heq:imp {while (b) {c} } = imp {skip}⊢ P st✝ ∧ ¬Bexp.eval st✝ b = true All goals completed! 🐙
Note to developers (Benjamin Pierce @bcpierce00, before next release, 2021)

This definition / discussion could be clearer.

Note to developers (Benjamin Pierce @bcpierce00, before next release, 2023)
Maja says: The wording of "we will never enter the
loop" could definitely be improved. As is, it suggests a situation
where the loop condition itself can never be satisfied. I suspect that
a previous draft included a discussion that explicitly placed {{ P }}
before the while, perhaps along the lines of "a loop invariant P of
[while b do c end] is also an invariant of [while b do c end]" (which
is, FWIW, a (somewhat obtuse) way of stating a weaker variant of
hoare_while, without the ¬b in the postcondition). Combined with the
fact that it is supposed to justify a somewhat surprising and
unexpected fact — [X = 0] is not what I would intuitively consider an
invariant of this loop — this sentence ends up being quite confusing.
I only understood it when I came back to find this excerpt.

We call P a loop invariant of while b do c end if

{{P ∧ b}} c {{P}}

is a valid Hoare triple.

This means that P will be true at the end of the loop body whenever the loop body executes. If P contradicts b, this holds trivially since the precondition is false.

For instance, X = 0 is a loop invariant of

while X = 2 do X := 1 end

since the program will never enter the loop.

Quiz

Is the assertion

Y = 0

a loop invariant of the following?

while X < 100 do X := X + 1 end

(A) Yes

(B) No

Show solution

Yes.

Quiz

Is the assertion

X = 0

a loop invariant of the following?

while X < 100 do X := X + 1 end

(A) Yes

(B) No

Show solution

No.

Quiz

Is the assertion

X < Y

a loop invariant of the following?

while true do X := X + 1; Y := Y + 1 end

(A) Yes

(B) No

Show solution

Yes.

Quiz

Is the assertion

X = Y + Z

a loop invariant of the following?

while Y > 10 do Y := Y - 1; Z := Z + 1 end

(A) Yes

(B) No

Show solution

Yes.

Note to developers (before next release)

This last quiz should be turned into a discussion in the text, at least in the full version — indeed, maybe all these should be turned into a long discussion of what it means to be a loop invariant — I think that would be pretty helpful.

The program

while Y > 10 do Y := Y - 1; Z := Z + 1 end

admits an interesting loop invariant:

X = Y + Z

Note that this doesn't contradict the loop guard but neither is it a command invariant of

Y := Y - 1; Z := Z + 1

since, if X = 5, Y = 0 and Z = 5, running the command will set Y + Z to 6. The loop guard Y > 10 guarantees that this will not be the case. We will see many such loop invariants in the following chapter.

Note to developers (Benjamin Pierce @bcpierce00, before next release, 2021)

What is this example doing here?? Needs some text.

theorem while_example : {{X ≤ 3}} while (X ≤ 2) { X := X + 1 } {{X = 3}} := ⊢ {{X ≤ 3}} while (X ≤ 2) {X := X + 1} {{X = 3}} ⊢ {{X ≤ 3}} while (X ≤ 2) {X := X + 1} {{?Q'}}⊢ ?Q' ↠ {{X = 3}}⊢ Assertion ⊢ {{X ≤ 3}} while (X ≤ 2) {X := X + 1} {{?Q'}} ⊢ {{X ≤ 3 ∧ bexp {X ≤ 2} }} X := X + 1 {{X ≤ 3}} ⊢ {{?hhoare.P'}} X := X + 1 {{X ≤ 3}}⊢ {{X ≤ 3 ∧ bexp {X ≤ 2} }} ↠ ?hhoare.P'⊢ Assertion ⊢ {{?hhoare.P'}} X := X + 1 {{X ≤ 3}} All goals completed! 🐙 ⊢ {{X ≤ 3 ∧ bexp {X ≤ 2} }} ↠ (X ≤ 3) [X ↦ X + 1] All goals completed! 🐙 ⊢ {{X ≤ 3 ∧ ¬bexp {X ≤ 2} }} ↠ {{X = 3}} All goals completed! 🐙
Note to developers
HIDE: CJC: Maybe also a good place to talk about the structure of
our logic - that we've set up the hoare_* lemmas and they are all
the reasoning about Hoare triples that they should have to use (in
both formal or informal proofs)?  Probably should talk about this
somewhere or else we'll get back lots of proofs that unfold
ValidHoareTriple and reason at a low level everywhere.

BCP 21: I think we do this now?
Quiz

Is the assertion

X > 0

a loop invariant of the following?

while X = 0 do X := X - 1 end

(A) Yes

(B) No

Show solution

According to how we defined the term, the answer should be Yes! The reason is that a loop invariant is defined as a P that, together with the fact that the guard is true, implies P.

Quiz

Is the assertion

X < 100

a loop invariant of the following?

while X < 100 do X := X + 1 end

(A) Yes

(B) No

Show solution

No.

Quiz

Is the assertion

X > 10

a loop invariant of the following?

while X > 10 do X := X + 1 end

(A) Yes

(B) No

Show solution

Yes.

If the loop never terminates, any postcondition will work.

theorem always_loop_hoare (Q : Assertion) : {{True}} while (true) { skip } {{ Q }} := Q:Assertion⊢ {{True}} while (true) {skip} {{Q}} Q:Assertion⊢ {{True}} while (true) {skip} {{?Q'}}Q:Assertion⊢ ?Q' ↠ QQ:Assertion⊢ Assertion Q:Assertion⊢ {{True}} while (true) {skip} {{?Q'}} Q:Assertion⊢ {{True ∧ bexp {true} }} skip {{True}} Q:Assertion⊢ ∀ (st : State), True Q:Assertionst:State⊢ True All goals completed! 🐙 Q:Assertion⊢ {{True ∧ ¬bexp {true} }} ↠ Q Q:Assertionst:Stateleft✝:Truehguard:¬Bexp.eval st (bexp {true}) = true⊢ Q st All goals completed! 🐙

Of course, this result is not surprising if we remember that the definition of ValidHoareTriple asserts that the postcondition must hold only when the command terminates. If the command doesn't terminate, we can prove anything we like about the post-condition.

Hoare rules that specify what happens if commands terminate, without proving that they do, are said to describe a logic of partial correctness. It is also possible to give Hoare rules for total correctness, which additionally specifies that commands must terminate. Total correctness is out of the scope of this textbook.

5.4.8.1. Exercise: repeat🔗

Note to developers

HIDE: I (BCP) think I see a much simpler way to do the 'for' stuff. Instead of for x from a to b do c define for x downfrom a do c that steps from a down to 0. This will be much simpler to specify, though still an interesting challenge. (CJC: This still seemed hard to me, but I'm deleting it for now to get things looking right)

HIDE: Coming up with the precise rule for REPEAT is tricky, and so is proving formally that the precise rule passes the litmus test (at this point we only ask them to convince themselves informally there).

Exercise★★★★(hoare_repeat) (Advanced, Optional, Manually graded)

In this exercise, we'll add a new command to our language of commands: repeat { c } until (b). You will write the evaluation rule for repeat and add a new Hoare rule to the language for programs involving it.

namespace RepeatExercise inductive Com : Type where | skip : Com | asgn : Ident → Aexp → Com | seq : Com → Com → Com | cond : Bexp → Com → Com → Com | whileDo : Bexp → Com → Com | repeatUntil : Com → Bexp → Com

repeat behaves like while, except that the loop guard is checked after each execution of the body, with the loop repeating as long as the guard stays false. Because of this, the body will always execute at least once.

We also need to extend the imp { } notation to parse the new repeat command.

Notation encoding: commands, macro rules/-- Repeat loop -/ scoped syntax "repeat" ppHardSpace "{" ppLine imp_com ppDedent(ppLine "}") " until " "(" imp_bexp ")" : imp_com open Lean in scoped macro_rules | `(imp { $x:ident }) => if x.getId == `skip then `(Com.skip) else pure x | `(imp { $c1; $c2 }) => `(Com.seq (imp {$c1}) (imp {$c2})) | `(imp { $x:ident := $a }) => `(Com.asgn $x (aexp {$a})) | `(imp { if ($b) {$c1} else {$c2} }) => `(Com.cond (bexp {$b}) (imp {$c1}) (imp {$c2})) | `(imp { while ($b) {$c} }) => `(Com.whileDo (bexp {$b}) (imp {$c})) | `(imp { repeat {$c} until ($b) }) => `(Com.repeatUntil (imp {$c}) (bexp {$b})) | `(imp { ~$c }) => pure c namespace Delab open Lean PrettyPrinter Imp.Delab @[app_unexpander Com.repeatUntil] private def Com.unexpandRepeatUntil : Unexpander | `($_ $c $b) => `(imp { repeat { $(getImp c) } until ($(getBexp b)) }) | _ => throw () attribute [app_unexpander Com.skip] unexpandComSkip attribute [app_unexpander Com.asgn] unexpandComAsgn attribute [app_unexpander Com.seq] unexpandComSeq attribute [app_unexpander Com.cond] unexpandComCond attribute [app_unexpander Com.whileDo] unexpandComWhileDo end Delab

Add new rules for repeat to Com.EvalR below. You can use the rules for while as a guide, but remember that the body of a repeat should always execute at least once, and that the loop ends when the guard becomes true.

inductive Com.EvalR : Com → State → State → Prop where | skip {st : State} : EvalR (imp {skip}) st st | asgn {st : State} {a : Aexp} {n : Nat} {x : Ident} (h : a.eval st = n) : EvalR (imp {x := a}) st (x →ₜ n ; st) | seq {c₁ c₂ : Com} {st st' st'' : State} (h₁ : EvalR c₁ st st') (h₂ : EvalR c₂ st' st'') : EvalR (imp {c₁; c₂}) st st'' | ifTrue {st st' : State} {b : Bexp} {c₁ c₂ : Com} (hb : b.eval st = true) (hc : EvalR c₁ st st') : EvalR (imp {if (b) {c₁} else {c₂} }) st st' | ifFalse {st st' : State} {b : Bexp} {c₁ c₂ : Com} (hb : b.eval st = false) (hc : EvalR c₂ st st') : EvalR (imp {if (b) {c₁} else {c₂} }) st st' | whileFalse {b : Bexp} {st : State} {c : Com} (hb : b.eval st = false) : EvalR (imp {while (b) {c} }) st st | whileTrue {st st' st'' : State} {b : Bexp} {c : Com} (hb : b.eval st = true) (hc : EvalR c st st') (hloop : Com.EvalR (imp {while (b) {c} }) st' st'') : EvalR (imp {while (b) {c} }) st st'' | repeatEnd {st st' : State} {b : Bexp} {c : Com} (hc : EvalR c st st') (hb : b.eval st' = true) : EvalR (imp {repeat {c} until (b) }) st st' | repeatLoop {st st' st'' : State} {b : Bexp} {c : Com} (hc : EvalR c st st') (hb : b.eval st' = false) (hloop : EvalR (imp {repeat {c} until (b) }) st' st'') : EvalR (imp {repeat {c} until (b) }) st st'' instance : HasEval Com State State where Eval := Com.EvalR @[simp] theorem Com.evalR_eq {c : Com} {st st' : State} : EvalR c st st' ↔ st =[ c ]=> st' := c:Comst:Statest':State⊢ c.EvalR st st' ↔ st =[ c ]=> st' All goals completed! 🐙 attribute [app_delab Com.EvalR] HasEval.Delab.delabEvalR

A couple of definitions from above, copied here so they use the new Com.EvalR.

def ValidHoareTriple (P : Assertion) (c : Com) (Q : Assertion) : Prop := ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' instance : HasTriple Com where Triple := ValidHoareTriple theorem validHoareTriple_def {P : Assertion} {c : Com} {Q : Assertion} : {{ P }} c {{ Q }} ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' := P:Assertionc:ComQ:Assertion⊢ {{P}} ~c {{Q}} ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' All goals completed! 🐙 attribute [irreducible] ValidHoareTriple

To make sure you've got the evaluation rules for repeat right, prove that ex1Repeat evaluates correctly.

def ex1Repeat : Com := imp { repeat { X := 1; Y := Y + 1 } until (X = 1) } theorem ex1Repeat_works : ∅ =[ ex1Repeat ]=> {Y ↦ 1, X ↦ 1} := ⊢ ∅ =[ ex1Repeat ]=> {Y ↦ 1, X ↦ 1} solution! ⊢ ∅ =[ X := 1; Y := Y + 1 ]=> {Y ↦ 1, X ↦ 1}⊢ Bexp.eval {Y ↦ 1, X ↦ 1} (bexp {X = 1}) = true ⊢ ∅ =[ X := 1; Y := Y + 1 ]=> {Y ↦ 1, X ↦ 1} ⊢ ∅ =[ X := 1 ]=> ?hc.st'⊢ ?hc.st' =[ Y := Y + 1 ]=> {Y ↦ 1, X ↦ 1}⊢ State ⊢ ∅ =[ X := 1 ]=> ?hc.st' All goals completed! 🐙 ⊢ (X →ₜ Aexp.eval ∅ (aexp {1})) =[ Y := Y + 1 ]=> {Y ↦ 1, X ↦ 1} All goals completed! 🐙 ⊢ Bexp.eval {Y ↦ 1, X ↦ 1} (bexp {X = 1}) = true All goals completed! 🐙

Now state and prove a theorem, hoare_repeat, that expresses an appropriate proof rule for repeat commands. Use hoare_while as a model, and try to make your rule as precise as possible.

/- Here is a very precise version of `hoare_repeat`. -/ theorem hoare_repeat {P Q : Assertion} {b : Bexp} {c : Com} (h₁ : {{ P }} c {{ Q }}) (h₂ : {{ Q ∧ ¬ b }} c {{ Q }}) : {{ P }} repeat { c } until (b) {{ Q ∧ b }} := P:AssertionQ:Assertionb:Bexpc:Comh₁:{{P}} ~c {{Q}}h₂:{{Q ∧ ¬b}} ~c {{Q}}⊢ {{P}} repeat { c } until (b) {{Q ∧ b}} P:AssertionQ:Assertionb:Bexpc:Comh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'h₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'⊢ ∀ {st st' : State}, (st =[ repeat { c } until (b) ]=> st') → P st → Q st' ∧ Bexp.eval st' b = true P:AssertionQ:Assertionb:Bexpc:Comh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'h₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Stateheval:st =[ repeat { c } until (b) ]=> st'hpre:P st⊢ Q st' ∧ Bexp.eval st' b = true P:AssertionQ:Assertionb:Bexpc:Comh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'h₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statehpre:P stcmd:Comheq:imp {repeat { c } until (b)} = cmdheval:st =[ cmd ]=> st'⊢ Q st' ∧ Bexp.eval st' b = true induction heval generalizing P with Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc✝:Comhc:st✝ =[ ~c✝ ]=> st'✝hb:Bexp.eval st'✝ b✝ = truehc_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {repeat { c✝ } until (b✝)}⊢ Q st'✝ ∧ Bexp.eval st'✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc✝:Comhc:st✝ =[ ~c✝ ]=> st'✝hb:Bexp.eval st'✝ b✝ = truehc_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝hceq:c = c✝hbeq:b = b✝⊢ Q st'✝ ∧ Bexp.eval st'✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:StateP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝hc:st✝ =[ ~c ]=> st'✝hc_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c → Q st'✝ ∧ Bexp.eval st'✝ b = truehb:Bexp.eval st'✝ b = true⊢ Q st'✝ ∧ Bexp.eval st'✝ b = true All goals completed! 🐙 Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:Stateb✝:Bexpc✝:Comhc:st✝ =[ ~c✝ ]=> st'✝hb:Bexp.eval st'✝ b✝ = falsehloop:st'✝ =[ repeat { c✝ } until (b✝) ]=> st''✝ih₁:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueih₂:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {repeat { c✝ } until (b✝)} → Q st''✝ ∧ Bexp.eval st''✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {repeat { c✝ } until (b✝)}⊢ Q st''✝ ∧ Bexp.eval st''✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:Stateb✝:Bexpc✝:Comhc:st✝ =[ ~c✝ ]=> st'✝hb:Bexp.eval st'✝ b✝ = falsehloop:st'✝ =[ repeat { c✝ } until (b✝) ]=> st''✝ih₁:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueih₂:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {repeat { c✝ } until (b✝)} → Q st''✝ ∧ Bexp.eval st''✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝hceq:c = c✝hbeq:b = b✝⊢ Q st''✝ ∧ Bexp.eval st''✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:StateP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝hc:st✝ =[ ~c ]=> st'✝ih₁:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c → Q st'✝ ∧ Bexp.eval st'✝ b = truehb:Bexp.eval st'✝ b = falsehloop:st'✝ =[ repeat { c } until (b) ]=> st''✝ih₂:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {repeat { c } until (b)} → Q st''✝ ∧ Bexp.eval st''✝ b = true⊢ Q st''✝ ∧ Bexp.eval st''✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:StateP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝hc:st✝ =[ ~c ]=> st'✝ih₁:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c → Q st'✝ ∧ Bexp.eval st'✝ b = truehb:Bexp.eval st'✝ b = falsehloop:st'✝ =[ repeat { c } until (b) ]=> st''✝ih₂:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {repeat { c } until (b)} → Q st''✝ ∧ Bexp.eval st''✝ b = true⊢ Q st'✝ ∧ ¬Bexp.eval st'✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:StateP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝hc:st✝ =[ ~c ]=> st'✝ih₁:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c → Q st'✝ ∧ Bexp.eval st'✝ b = truehb:Bexp.eval st'✝ b = falsehloop:st'✝ =[ repeat { c } until (b) ]=> st''✝ih₂:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {repeat { c } until (b)} → Q st''✝ ∧ Bexp.eval st''✝ b = true⊢ Q st'✝Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:StateP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝hc:st✝ =[ ~c ]=> st'✝ih₁:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c → Q st'✝ ∧ Bexp.eval st'✝ b = truehb:Bexp.eval st'✝ b = falsehloop:st'✝ =[ repeat { c } until (b) ]=> st''✝ih₂:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {repeat { c } until (b)} → Q st''✝ ∧ Bexp.eval st''✝ b = true⊢ ¬Bexp.eval st'✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:StateP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝hc:st✝ =[ ~c ]=> st'✝ih₁:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c → Q st'✝ ∧ Bexp.eval st'✝ b = truehb:Bexp.eval st'✝ b = falsehloop:st'✝ =[ repeat { c } until (b) ]=> st''✝ih₂:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {repeat { c } until (b)} → Q st''✝ ∧ Bexp.eval st''✝ b = true⊢ Q st'✝ All goals completed! 🐙 Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:StateP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝hc:st✝ =[ ~c ]=> st'✝ih₁:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c → Q st'✝ ∧ Bexp.eval st'✝ b = truehb:Bexp.eval st'✝ b = falsehloop:st'✝ =[ repeat { c } until (b) ]=> st''✝ih₂:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {repeat { c } until (b)} → Q st''✝ ∧ Bexp.eval st''✝ b = true⊢ ¬Bexp.eval st'✝ b = true All goals completed! 🐙 Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:StateP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {skip}⊢ Q st✝ ∧ Bexp.eval st✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statea✝:Aexpn✝:Natx✝:Identh✝:Aexp.eval st✝ a✝ = n✝P:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {x✝ := a✝}⊢ Q (x✝ →ₜ n✝ ; st✝) ∧ Bexp.eval (x✝ →ₜ n✝ ; st✝) b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comc₁✝:Comc₂✝:Comst✝:Statest'✝:Statest''✝:Stateh₁✝:st✝ =[ ~c₁✝ ]=> st'✝h₂✝:st'✝ =[ ~c₂✝ ]=> st''✝h₁_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c₁✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueh₂_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = c₂✝ → Q st''✝ ∧ Bexp.eval st''✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {c₁✝; c₂✝}⊢ Q st''✝ ∧ Bexp.eval st''✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = truehc✝:st✝ =[ ~c₁✝ ]=> st'✝hc_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c₁✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ Q st'✝ ∧ Bexp.eval st'✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = falsehc✝:st✝ =[ ~c₂✝ ]=> st'✝hc_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c₂✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ Q st'✝ ∧ Bexp.eval st'✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comb✝:Bexpst✝:Statec✝:Comhb✝:Bexp.eval st✝ b✝ = falseP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {while (b✝) {c✝} }⊢ Q st✝ ∧ Bexp.eval st✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:Stateb✝:Bexpc✝:Comhb✝:Bexp.eval st✝ b✝ = truehc✝:st✝ =[ ~c✝ ]=> st'✝hloop✝:st'✝ =[ while (b✝) {c✝} ]=> st''✝hc_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c✝ → Q st'✝ ∧ Bexp.eval st'✝ b = truehloop_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {while (b✝) {c✝} } → Q st''✝ ∧ Bexp.eval st''✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {while (b✝) {c✝} }⊢ Q st''✝ ∧ Bexp.eval st''✝ b = true Q:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Statest''✝:Stateb✝:Bexpc✝:Comhb✝:Bexp.eval st✝ b✝ = truehc✝:st✝ =[ ~c✝ ]=> st'✝hloop✝:st'✝ =[ while (b✝) {c✝} ]=> st''✝hc_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c✝ → Q st'✝ ∧ Bexp.eval st'✝ b = truehloop_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = imp {while (b✝) {c✝} } → Q st''✝ ∧ Bexp.eval st''✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {while (b✝) {c✝} }⊢ Q st''✝ ∧ Bexp.eval st''✝ b = trueQ:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comb✝:Bexpst✝:Statec✝:Comhb✝:Bexp.eval st✝ b✝ = falseP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {while (b✝) {c✝} }⊢ Q st✝ ∧ Bexp.eval st✝ b = trueQ:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = falsehc✝:st✝ =[ ~c₂✝ ]=> st'✝hc_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c₂✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ Q st'✝ ∧ Bexp.eval st'✝ b = trueQ:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statest'✝:Stateb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = truehc✝:st✝ =[ ~c₁✝ ]=> st'✝hc_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c₁✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ Q st'✝ ∧ Bexp.eval st'✝ b = trueQ:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comc₁✝:Comc₂✝:Comst✝:Statest'✝:Statest''✝:Stateh₁✝:st✝ =[ ~c₁✝ ]=> st'✝h₂✝:st'✝ =[ ~c₂✝ ]=> st''✝h₁_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st✝ → imp {repeat { c } until (b)} = c₁✝ → Q st'✝ ∧ Bexp.eval st'✝ b = trueh₂_ih✝:∀ {P : Assertion}, (∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st') → P st'✝ → imp {repeat { c } until (b)} = c₂✝ → Q st''✝ ∧ Bexp.eval st''✝ b = trueP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {c₁✝; c₂✝}⊢ Q st''✝ ∧ Bexp.eval st''✝ b = trueQ:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:Statea✝:Aexpn✝:Natx✝:Identh✝:Aexp.eval st✝ a✝ = n✝P:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {x✝ := a✝}⊢ Q (x✝ →ₜ n✝ ; st✝) ∧ Bexp.eval (x✝ →ₜ n✝ ; st✝) b = trueQ:Assertionb:Bexpc:Comh₂:∀ {st st' : State}, (st =[ c ]=> st') → Q st ∧ ¬Bexp.eval st b = true → Q st'st:Statest':Statecmd:Comst✝:StateP:Assertionh₁:∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st'hpre:P st✝heq:imp {repeat { c } until (b)} = imp {skip}⊢ Q st✝ ∧ Bexp.eval st✝ b = true All goals completed! 🐙

For full credit, make sure (informally) that your rule can be used to prove the following valid Hoare triple:

{{ X > 0 }}
repeat {
  Y := X;
  X := X - 1
} until (X = 0)
{{ X = 0 ∧ Y > 0 }}
/- Although it was not required by the exercise, we can show formally that `hoare_repeat` can handle this litmus test: -/ def ex2Repeat : Com := imp { repeat { Y := X; X := X - 1 } until (X = 0) } /- Before we can show anything about this program we need to repeat the proofs of some more Hoare rules from above (remember we're in a separate namespace, with a different definition of commands). -/ theorem hoare_asgn {Q : Assertion} {x : Ident} {a : Aexp} : {{Q [x ↦ a]}} x := a {{ Q }} := by rw [validHoareTriple_def] intro st st' heval hQ rw [Assertion.subst_apply] at hQ inversion heval with | asgn n h => subst h exact hQ theorem hoare_consequence {P P' Q Q' : Assertion} {c : Com} (hht : {{ P' }} c {{ Q' }}) (hPP' : P ↠ P') (hQ'Q : Q' ↠ Q) : {{ P }} c {{ Q }} := by rw [validHoareTriple_def] at hht ⊢ intro st st' hc hP apply_rules theorem hoare_consequence_pre {P P' Q : Assertion} {c : Com} (hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') : {{ P }} c {{ Q }} := by rw [validHoareTriple_def] at hhoare ⊢ intro st st' hc hP apply_rules theorem hoare_seq {P Q R : Assertion} {c₁ c₂ : Com} (h₁ : {{ Q }} c₂ {{R}}) (h₂ : {{ P }} c₁ {{ Q }}) : {{ P }} c₁; c₂ {{R}} := by rw [validHoareTriple_def] at h₁ h₂ ⊢ intro st st' heval hpre inversion heval with | seq _ hc₁ hc₂ => apply_rules/- Now we are ready to show `ex2Repeat` correct using `hoare_repeat`. -/ theorem ex2Repeat_hoare_repeat : {{ X > 0 }} ex2Repeat {{ X = 0 ∧ Y > 0 }} := by rw [ex2Repeat] apply hoare_consequence · apply hoare_repeat (Q := {{ Y > 0 }}) · exact hoare_seq hoare_asgn hoare_asgn · apply hoare_seq hoare_asgn apply hoare_consequence_pre hoare_asgn assertion_auto · -- body of repeat if exiting right away assertion_auto · -- final postcondition assertion_auto /- A sound but less precise variant of the `hoare_repeat` rule looks like this: -/theorem hoare_repeat' {P : Assertion} {b : Bexp} {c : Com} (h : {{ P }} c {{ P }}) : {{ P }} repeat { c } until (b) {{ P ∧ b }} := by rw [validHoareTriple_def] at h ⊢ intro st st' heval hpre generalize heq : (imp { repeat { c } until (b) }) = cmd at heval induction heval with | repeatEnd hc hb _ => injection heq with hceq hbeq subst hceq hbeq exact ⟨h hc hpre, hb⟩ | repeatLoop hc hb hloop ih₁ ih₂ => injection heq with hceq hbeq subst hceq hbeq exact ih₂ (h hc hpre) rfl | skip | asgn | seq | ifTrue | ifFalse | whileFalse | whileTrue => contradiction /- First, let's show that `hoare_repeat'` is implied by `hoare_repeat`. -/ theorem hoare_repeat_implies_hoare_repeat' (hoare_repeat : ∀ (P Q : Assertion) (b : Bexp) (c : Com), ({{ P }} c {{ Q }}) → ({{ Q ∧ ¬ b }} c {{ Q }}) → {{ P }} repeat { c } until (b) {{ Q ∧ b }}) : ∀ (P : Assertion) (b : Bexp) (c : Com), ({{ P }} c {{ P }}) → {{ P }} repeat { c } until (b) {{ P ∧ b }} := by intro P b c h apply hoare_repeat <;> try assumption apply hoare_consequence_pre · exact h · intro st ⟨hp, _⟩ exact hp/- However, we can't prove `ex2Repeat` correct using `hoare_repeat'`, even with a stronger initial precondition on `Y`. Here is a first failed proof attempt. -/ /-- warning: declaration uses `sorry` -/ #guard_msgs in example : {{ X > 0 ∧ Y > 0}} ex2Repeat {{ X = 0 ∧ Y > 0}} := by apply hoare_consequence · apply hoare_repeat' (P := {{ Y > 0 }}) apply hoare_seq hoare_asgn apply hoare_consequence_pre hoare_asgn intro st hy simp -- loop invariant too weak on its own, -- we need the value of the previous guard sorry · -- initial precondition intro st ⟨_, hy⟩ exact hy -- this only works with an additional Y > 0 precondition · -- final postcondition assertion_auto /- Here is a second failed attempt trying stronger loop invariant, but it is too strong. -/ /-- warning: declaration uses `sorry` -/ #guard_msgs in example : {{ X > 0 ∧ Y > 0}} ex2Repeat {{ X = 0 ∧ Y > 0}} := by apply hoare_consequence · apply hoare_repeat' (P := {{ X > 0 ∧ Y > 0 }}) apply hoare_seq hoare_asgn apply hoare_consequence_pre hoare_asgn intro st ⟨hx, hy⟩ simp -- loop invariant too strong sorry · -- initial precondition intro st hp exact hp · -- final postcondition assertion_auto end RepeatExercise

5.5. Summary🔗

So far, we've introduced Hoare Logic as a tool for reasoning about Imp programs.

The rules of Hoare Logic are:

     --------------------------          (hoare_asgn)
     {{Q [X ↦ a]}} X := a {{Q}}

        --------------------             (hoare_skip)
        {{ P }} skip {{ P }}

         {{ P }} c₁ {{ Q }}
         {{ Q }} c₂ {{ R }}
        ----------------------            (hoare_seq)
        {{ P }} c₁; c₂ {{ R }}

        {{P ∧   b}} c₁ {{Q}}
        {{P ∧ ¬ b}} c₂ {{Q}}
------------------------------------       (hoare_if)
{{P}} if b then c₁ else c₂ end {{Q}}

         {{P ∧ b}} c {{P}}
 -----------------------------------    (hoare_while)
 {{P}} while b do c end {{P ∧ ¬ b}}

          {{P'}} c {{Q'}}
             P ↠ P'
             Q' ↠ Q
   -----------------------------  (hoare_consequence)
          {{P}} c {{Q}}

Our main task in this chapter has been to define the rules of Hoare logic, and prove that the definitions are sound. Having done so, we can go on and work within Hoare logic to prove that particular programs satisfy particular Hoare triples. In the next chapter, we'll see how Hoare logic can be used to prove that more interesting programs satisfy interesting specifications of their behavior.

Crucially, we will do so without ever again unfolding the definition of Hoare triples (via validHoareTriple_def) — i.e., we will take the rules of Hoare logic as a closed world for reasoning about programs.

5.6. Additional Exercises🔗

5.6.1. Havoc🔗

In this exercise, we will derive proof rules for a havoc command, which is similar to the nondeterministic any expression from the Imp chapter.

First, we enclose this work in a separate namespace, and recall the syntax and big-step semantics of Himp commands from the Equiv chapter.

namespace HimpHoare inductive Com : Type where | skip : Com | asgn : Ident → Aexp → Com | seq : Com → Com → Com | cond : Bexp → Com → Com → Com | whileDo : Bexp → Com → Com | havoc : Ident → Com

We also need to extend the imp { } notation to parse the new havoc command, and to print it back.

Notation encoding: commands, macro rules/-- Havoc: set a variable to a nondeterministically chosen number (`havoc x;`). As with `skip`, the word `havoc` is not reserved: the production accepts any identifier and the macro below rejects everything except `havoc`. -/ scoped syntax ident ident : imp_com open Lean in scoped macro_rules | `(imp { $x:ident }) => if x.getId == `skip then `(Com.skip) else pure x | `(imp { $c1; $c2 }) => `(Com.seq (imp {$c1}) (imp {$c2})) | `(imp { $x:ident := $a }) => `(Com.asgn $x (aexp {$a})) | `(imp { if ($b) {$c1} else {$c2} }) => `(Com.cond (bexp {$b}) (imp {$c1}) (imp {$c2})) | `(imp { while ($b) {$c} }) => `(Com.whileDo (bexp {$b}) (imp {$c})) | `(imp { $h:ident $x:ident }) => if h.getId == `havoc then `(Com.havoc $x) else Macro.throwErrorAt h s!"expected 'havoc', got '{h.getId}'" | `(imp { ~$c }) => pure c namespace Delab open Lean PrettyPrinter Imp.Delab @[app_unexpander Com.havoc] private def Com.unexpandHavoc : Unexpander | `($_ $x:ident) => `(imp { $(mkIdent `havoc):ident $x:ident }) | _ => throw () attribute [app_unexpander Com.skip] unexpandComSkip attribute [app_unexpander Com.asgn] unexpandComAsgn attribute [app_unexpander Com.seq] unexpandComSeq attribute [app_unexpander Com.cond] unexpandComCond attribute [app_unexpander Com.whileDo] unexpandComWhileDo end Delab
inductive Com.EvalR : Com → State → State → Prop where | skip {st : State} : EvalR (imp {skip}) st st | asgn {st : State} {a : Aexp} {n : Nat} {x : Ident} (h : a.eval st = n) : EvalR (imp {x := a}) st (x →ₜ n ; st) | seq {c₁ c₂ : Com} {st st' st'' : State} (h₁ : EvalR c₁ st st') (h₂ : EvalR c₂ st' st'') : EvalR (imp {c₁; c₂}) st st'' | ifTrue {st st' : State} {b : Bexp} {c₁ c₂ : Com} (hb : b.eval st = true) (hc : EvalR c₁ st st') : EvalR (imp {if (b) {c₁} else {c₂} }) st st' | ifFalse {st st' : State} {b : Bexp} {c₁ c₂ : Com} (hb : b.eval st = false) (hc : EvalR c₂ st st') : EvalR (imp {if (b) {c₁} else {c₂} }) st st' | whileFalse {b : Bexp} {st : State} {c : Com} (hb : b.eval st = false) : EvalR (imp {while (b) {c} }) st st | whileTrue {st st' st'' : State} {b : Bexp} {c : Com} (hb : b.eval st = true) (hc : EvalR c st st') (hloop : Com.EvalR (imp {while (b) {c} }) st' st'') : EvalR (imp {while (b) {c} }) st st'' | havoc {st : State} {x : Ident} {n : Nat} : EvalR (imp {havoc x}) st (x →ₜ n ; st) instance : HasEval Com State State where Eval := Com.EvalR @[simp] theorem Com.evalR_eq {c : Com} {st st' : State} : EvalR c st st' ↔ st =[ c ]=> st' := c:Comst:Statest':State⊢ c.EvalR st st' ↔ st =[ c ]=> st' All goals completed! 🐙 attribute [app_delab Com.EvalR] HasEval.Delab.delabEvalR

The definition of Hoare triples is exactly as before.

def ValidHoareTriple (P : Assertion) (c : Com) (Q : Assertion) : Prop := ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' instance : HasTriple Com where Triple := ValidHoareTriple theorem validHoareTriple_def {P : Assertion} {c : Com} {Q : Assertion} : {{ P }} c {{ Q }} ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' := P:Assertionc:ComQ:Assertion⊢ {{P}} ~c {{Q}} ↔ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' All goals completed! 🐙 attribute [irreducible] ValidHoareTriple

And the precondition consequence rule is exactly as before.

theorem hoare_consequence_pre {P P' Q : Assertion} {c : Com} (hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') : {{ P }} c {{ Q }} := P:AssertionP':AssertionQ:Assertionc:Comhhoare:{{P'}} ~c {{Q}}himp:P ↠ P'⊢ {{P}} ~c {{Q}} P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'⊢ ∀ {st st' : State}, (st =[ c ]=> st') → P st → Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st st' : State}, (st =[ c ]=> st') → P' st → Q st'himp:P ↠ P'st:Statest':Stateheval:st =[ c ]=> st'hpre:P st⊢ Q st' All goals completed! 🐙
Exercise★★★(hoare_havoc) (Advanced)
Note to developers (Benjamin Pierce @bcpierce00, before next release, 2021)

This exercise turns out to be quite hard — a lot of people get stuck. We should make it advanced the next time through. BCP 23: Made it advanced. Can we also explain it better?

Complete the Hoare rule for havoc commands below by defining havoc_pre, and prove that the resulting rule is correct.

def havoc_pre (x : Ident) (Q : Assertion) (st : State) : Prop := solution!(∀ (n : Nat), ({{ Q [x ↦ ~(.num n)] }}) st) theorem hoare_havoc {Q : Assertion} {x : Ident} : {{ fun st => havoc_pre x Q st }} havoc x {{ Q }} := Q:Assertionx:Ident⊢ {{fun st => havoc_pre x Q st}} havoc x {{Q}} solution! Q:Assertionx:Ident⊢ ∀ {st st' : State}, (st =[ havoc x ]=> st') → havoc_pre x Q st → Q st' Q:Assertionx:Identst:Statest':Stateheval:st =[ havoc x ]=> st'hpre:havoc_pre x Q st⊢ Q st' Q:Assertionx:Identst:Statest':Stateheval:st =[ havoc x ]=> st'hpre:∀ (n : Nat), ({{Q [x ↦ ~(Aexp.num n)]}}) st⊢ Q st' inversion heval with Q:Assertionx:Identst:Statehpre:∀ (n : Nat), ({{Q [x ↦ ~(Aexp.num n)]}}) stn:Nat⊢ Q (x →ₜ n ; st) Q:Assertionx:Identst:Staten:Nathpre:Q [x ↦ ~(Aexp.num n)] st⊢ Q (x →ₜ n ; st) Q:Assertionx:Identst:Staten:Nathpre:Q (x →ₜ n ; st)⊢ Q (x →ₜ n ; st) All goals completed! 🐙
Exercise★★★(havoc_post) (Advanced)

Complete the following proof without changing any of the provided commands. If you find that it can't be completed, your definition of havoc_pre is probably too strong. Find a way to relax it so that havoc_post can be proved.

Hint: the assertion_auto tactic we've built won't help you here. You need to proceed manually.

Note to developers (before next release)

This exercise is kind of weird. Should probably be optional.

theorem havoc_post {P : Assertion} {x : Ident} : {{ P }} havoc x {{ fun st => ∃ (n : Nat), ({{ P [x ↦ ~(.num n)] }}) st }} := P:Assertionx:Ident⊢ {{P}} havoc x {{fun st => ∃ n, ({{P [x ↦ ~(Aexp.num n)]}}) st}} P:Assertionx:Ident⊢ {{?P'}} havoc x {{fun st => ∃ n, ({{P [x ↦ ~(Aexp.num n)]}}) st}}P:Assertionx:Ident⊢ P ↠ ?P'P:Assertionx:Ident⊢ Assertion P:Assertionx:Ident⊢ {{?P'}} havoc x {{fun st => ∃ n, ({{P [x ↦ ~(Aexp.num n)]}}) st}} All goals completed! 🐙 P:Assertionx:Ident⊢ P ↠ {{fun st => havoc_pre x (fun st => ∃ n, ({{P [x ↦ ~(Aexp.num n)]}}) st) st}} solution! P:Assertionx:Identst:Statehpre:P stn:Nat⊢ (fun st => ∃ n, ({{P [x ↦ ~(Aexp.num n)]}}) st) [x ↦ ~(Aexp.num n)] st P:Assertionx:Identst:Statehpre:P stn:Nat⊢ ∃ n, P (x →ₜ n ; st) P:Assertionx:Identst:Statehpre:P stn:Nat⊢ P (x →ₜ st[x] ; st) P:Assertionx:Identst:Statehpre:P stn:Nat⊢ P st All goals completed! 🐙
end HimpHoare

5.6.2. Assert and Assume🔗

Exercise★★★★(assert_vs_assume)

In this exercise, we will extend Imp with two commands, assert and assume. Both commands are ways to indicate that a certain assertion should hold any time this part of the program is reached. However they differ as follows:

  • If an assert statement fails, it causes the program to go into an error state and exit.

  • If an assume statement fails, the program fails to evaluate at all. In other words, the program gets stuck and has no final state.

The new set of commands is:

namespace HoareAssertAssume inductive Com : Type where | skip : Com | asgn : Ident → Aexp → Com | seq : Com → Com → Com | cond : Bexp → Com → Com → Com | whileDo : Bexp → Com → Com | assert : Bexp → Com | assume : Bexp → Com

We also need to extend the imp { } notation to parse the new assert and assume commands.

Notation encoding: commands, macro rules/-- Assert / assume (`assert (b);`, `assume (b);`). As with `skip`, the words `assert` and `assume` are not reserved: the production accepts any identifier and the macro below rejects everything else. -/ scoped syntax ident " (" imp_bexp ")" : imp_com open Lean in scoped macro_rules | `(imp { $x:ident }) => if x.getId == `skip then `(Com.skip) else pure x | `(imp { $h:ident ($b) }) => if h.getId == `assert then `(Com.assert (bexp {$b})) else if h.getId == `assume then `(Com.assume (bexp {$b})) else Macro.throwErrorAt h s!"expected 'assert' or 'assume', got '{h.getId}'" | `(imp { $c1; $c2 }) => `(Com.seq (imp {$c1}) (imp {$c2})) | `(imp { $x:ident := $a }) => `(Com.asgn $x (aexp {$a})) | `(imp { if ($b) {$c1} else {$c2} }) => `(Com.cond (bexp {$b}) (imp {$c1}) (imp {$c2})) | `(imp { while ($b) {$c} }) => `(Com.whileDo (bexp {$b}) (imp {$c})) | `(imp { ~$c }) => pure c namespace Delab open Lean PrettyPrinter Imp.Delab @[app_unexpander Com.assert] private def Com.unexpandAssert : Unexpander | `($_ $b) => `(imp { $(mkIdent `assert):ident ($(getBexp b)) }) | _ => throw () @[app_unexpander Com.assume] private def Com.unexpandAssume : Unexpander | `($_ $b) => `(imp { $(mkIdent `assume):ident ($(getBexp b)) }) | _ => throw () attribute [app_unexpander Com.skip] unexpandComSkip attribute [app_unexpander Com.asgn] unexpandComAsgn attribute [app_unexpander Com.seq] unexpandComSeq attribute [app_unexpander Com.cond] unexpandComCond attribute [app_unexpander Com.whileDo] unexpandComWhileDo end Delab

To define the behavior of assert and assume, we need to add notation for an error, which indicates that an assertion has failed. We modify the Com.EvalR relation, therefore, so that it relates a start state to either an end state or to error. The Result type indicates the end value of a program, either a state or an error:

inductive Result : Type where | normal (st : State) : Result | error : Result

Now we are ready to give you the evaluation relation for the new language.

inductive Com.EvalR : Com → State → Result → Prop where /- Old rules, several modified -/ | skip {st : State} : EvalR (imp {skip}) st (.normal st) | asgn {st : State} {a : Aexp} {n : Nat} {x : Ident} (h : a.eval st = n) : EvalR (imp {x := a}) st (.normal (x →ₜ n ; st)) | seqNormal {c₁ c₂ : Com} {st st' : State} {r : Result} (h₁ : EvalR c₁ st (.normal st')) (h₂ : EvalR c₂ st' r) : EvalR (imp {c₁; c₂}) st r | seqError {c₁ c₂ : Com} {st : State} (h : EvalR c₁ st .error) : EvalR (imp {c₁; c₂}) st .error | ifTrue {st : State} {r : Result} {b : Bexp} {c₁ c₂ : Com} (hb : b.eval st = true) (hc : EvalR c₁ st r) : EvalR (imp {if (b) {c₁} else {c₂} }) st r | ifFalse {st : State} {r : Result} {b : Bexp} {c₁ c₂ : Com} (hb : b.eval st = false) (hc : EvalR c₂ st r) : EvalR (imp {if (b) {c₁} else {c₂} }) st r | whileFalse {b : Bexp} {st : State} {c : Com} (hb : b.eval st = false) : EvalR (imp {while (b) {c} }) st (.normal st) | whileTrueNormal {st st' : State} {r : Result} {b : Bexp} {c : Com} (hb : b.eval st = true) (hc : EvalR c st (.normal st')) (hloop : EvalR (imp {while (b) {c} }) st' r) : EvalR (imp {while (b) {c} }) st r | whileTrueError {st : State} {b : Bexp} {c : Com} (hb : b.eval st = true) (hc : EvalR c st .error) : EvalR (imp {while (b) {c} }) st .error /- Rules for Assert and Assume -/ | assertTrue {st : State} {b : Bexp} (hb : b.eval st = true) : EvalR (imp {assert (b)}) st (.normal st) | assertFalse {st : State} {b : Bexp} (hb : b.eval st = false) : EvalR (imp {assert (b)}) st .error | assume {st : State} {b : Bexp} (hb : b.eval st = true) : EvalR (imp {assume (b)}) st (.normal st) instance : HasEval Com State Result where Eval := Com.EvalR @[simp] theorem Com.evalR_eq {c : Com} {st : State} {res : Result} : EvalR c st res ↔ st =[ c ]=> res := c:Comst:Stateres:Result⊢ c.EvalR st res ↔ st =[ c ]=> res All goals completed! 🐙 attribute [app_delab Com.EvalR] HasEval.Delab.delabEvalR

We redefine Hoare triples: Now, {{ P }} c {{ Q }} means that, whenever c is started in a state satisfying P, and terminates with result r, then r is not an error and the state of r satisfies Q.

def ValidHoareTriple (P : Assertion) (c : Com) (Q : Assertion) : Prop := ∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st → ∃ st' : State, r = Result.normal st' ∧ Q st' instance : HasTriple Com where Triple := ValidHoareTriple theorem validHoareTriple_def {P : Assertion} {c : Com} {Q : Assertion} : {{ P }} c {{ Q }} ↔ ∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st → ∃ st' : State, r = Result.normal st' ∧ Q st' := P:Assertionc:ComQ:Assertion⊢ {{P}} ~c {{Q}} ↔ ∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st' All goals completed! 🐙 attribute [irreducible] ValidHoareTriple

To test your understanding of this modification, give an example precondition and postcondition that are satisfied by the assume statement but not by the assert statement.

theorem assert_assume_differ : ∃ (P : Assertion) (b : Bexp) (Q : Assertion), ({{ P }} assume (b) {{ Q }}) ∧ ¬ ({{ P }} assert (b) {{ Q }}) := ⊢ ∃ P b Q, {{P}} assume (b) {{Q}} ∧ ¬{{P}} assert (b) {{Q}} solution! ⊢ {{True}} assume (false) {{False}} ∧ ¬{{True}} assert (false) {{False}} ⊢ {{True}} assume (false) {{False}}⊢ ¬{{True}} assert (false) {{False}} ⊢ {{True}} assume (false) {{False}} ⊢ ∀ {st : State} {r : Result}, (st =[ assume (false) ]=> r) → True → ∃ st', r = Result.normal st' ∧ False st:Stater:Resultheval:st =[ assume (false) ]=> ra✝:True⊢ ∃ st', r = Result.normal st' ∧ False inversion heval with st:Statea✝:Truehb:Bexp.eval st (bexp {false}) = true⊢ ∃ st', Result.normal st = Result.normal st' ∧ False All goals completed! 🐙 ⊢ ¬{{True}} assert (false) {{False}} hC:{{True}} assert (false) {{False}}⊢ False hC:∀ {st : State} {r : Result}, (st =[ assert (false) ]=> r) → True → ∃ st', r = Result.normal st' ∧ False⊢ False hC:∀ {st : State} {r : Result}, (st =[ assert (false) ]=> r) → True → ∃ st', r = Result.normal st' ∧ Falseh:∅ =[ assert (false) ]=> Result.error⊢ False hC:∀ {st : State} {r : Result}, (st =[ assert (false) ]=> r) → True → ∃ st', r = Result.normal st' ∧ Falseh:∅ =[ assert (false) ]=> Result.errorst':Stateh₁:Result.error = Result.normal st'h₂:False⊢ False All goals completed! 🐙

Then prove that any triple for an assert also works when assert is replaced by assume.

theorem assert_implies_assume {P : Assertion} {b : Bexp} {Q : Assertion} (hhoare : {{ P }} assert (b) {{ Q }}) : {{ P }} assume (b) {{ Q }} := P:Assertionb:BexpQ:Assertionhhoare:{{P}} assert (b) {{Q}}⊢ {{P}} assume (b) {{Q}} solution! P:Assertionb:BexpQ:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ assert (b) ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'⊢ ∀ {st : State} {r : Result}, (st =[ assume (b) ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st' P:Assertionb:BexpQ:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ assert (b) ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Stater:Resultheval:st =[ assume (b) ]=> rhpre:P st⊢ ∃ st', r = Result.normal st' ∧ Q st' inversion heval with P:Assertionb:BexpQ:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ assert (b) ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Statehpre:P sthb:Bexp.eval st b = true⊢ ∃ st', Result.normal st = Result.normal st' ∧ Q st' P:Assertionb:BexpQ:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ assert (b) ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Statehpre:P sthb:Bexp.eval st b = true⊢ Result.normal st = Result.normal st ∧ Q st P:Assertionb:BexpQ:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ assert (b) ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Statehpre:P sthb:Bexp.eval st b = trueh:st =[ assert (b) ]=> Result.normal st⊢ Result.normal st = Result.normal st ∧ Q st P:Assertionb:BexpQ:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ assert (b) ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Statehpre:P sthb:Bexp.eval st b = trueh:st =[ assert (b) ]=> Result.normal stst':Stateh₁:Result.normal st = Result.normal st'h₂:Q st'⊢ Result.normal st = Result.normal st ∧ Q st P:Assertionb:BexpQ:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ assert (b) ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Statehpre:P sthb:Bexp.eval st b = trueh:st =[ assert (b) ]=> Result.normal stst':Stateh₂:Q st'hsteq:st = st'⊢ Result.normal st = Result.normal st ∧ Q st P:Assertionb:BexpQ:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ assert (b) ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Statehpre:P sthb:Bexp.eval st b = trueh:st =[ assert (b) ]=> Result.normal sth₂:Q st⊢ Result.normal st = Result.normal st ∧ Q st All goals completed! 🐙

Next, here are proofs for the old Hoare rules adapted to the new semantics. You don't need to do anything with these.

theorem hoare_asgn {Q : Assertion} {x : Ident} {a : Aexp} : {{Q [x ↦ a]}} x := a {{ Q }} := Q:Assertionx:Identa:Aexp⊢ {{Q [x ↦ a]}} x := a {{Q}} Q:Assertionx:Identa:Aexp⊢ ∀ {st : State} {r : Result}, (st =[ x := a ]=> r) → Q [x ↦ a] st → ∃ st', r = Result.normal st' ∧ Q st' Q:Assertionx:Identa:Aexpst:Stater:Resultheval:st =[ x := a ]=> rhQ:Q [x ↦ a] st⊢ ∃ st', r = Result.normal st' ∧ Q st' Q:Assertionx:Identa:Aexpst:Stater:Resultheval:st =[ x := a ]=> rhQ:Q (x →ₜ Aexp.eval st a ; st)⊢ ∃ st', r = Result.normal st' ∧ Q st' inversion heval with Q:Assertionx:Identa:Aexpst:StatehQ:Q (x →ₜ Aexp.eval st a ; st)n:Nath:Aexp.eval st a = n⊢ ∃ st', Result.normal (x →ₜ n ; st) = Result.normal st' ∧ Q st' Q:Assertionx:Identa:Aexpst:StatehQ:Q (x →ₜ Aexp.eval st a ; st)n:Nath:Aexp.eval st a = n⊢ Result.normal (x →ₜ n ; st) = Result.normal (x →ₜ n ; st) ∧ Q (x →ₜ n ; st) Q:Assertionx:Identa:Aexpst:StatehQ:Q (x →ₜ Aexp.eval st a ; st)⊢ Result.normal (x →ₜ Aexp.eval st a ; st) = Result.normal (x →ₜ Aexp.eval st a ; st) ∧ Q (x →ₜ Aexp.eval st a ; st) All goals completed! 🐙 theorem hoare_consequence_pre {P P' Q : Assertion} {c : Com} (hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') : {{ P }} c {{ Q }} := P:AssertionP':AssertionQ:Assertionc:Comhhoare:{{P'}} ~c {{Q}}himp:P ↠ P'⊢ {{P}} ~c {{Q}} P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P' st → ∃ st', r = Result.normal st' ∧ Q st'himp:P ↠ P'⊢ ∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st' P:AssertionP':AssertionQ:Assertionc:Comhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P' st → ∃ st', r = Result.normal st' ∧ Q st'himp:P ↠ P'st:Stater:Resulthc:st =[ c ]=> rhpre:P st⊢ ∃ st', r = Result.normal st' ∧ Q st' All goals completed! 🐙 theorem hoare_consequence_post {P Q Q' : Assertion} {c : Com} (hhoare : {{ P }} c {{ Q' }}) (himp : Q' ↠ Q) : {{ P }} c {{ Q }} := P:AssertionQ:AssertionQ':Assertionc:Comhhoare:{{P}} ~c {{Q'}}himp:Q' ↠ Q⊢ {{P}} ~c {{Q}} P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q' st'himp:Q' ↠ Q⊢ ∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st' P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q' st'himp:Q' ↠ Qst:Stater:Resulthc:st =[ c ]=> rhpre:P st⊢ ∃ st', r = Result.normal st' ∧ Q st' P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q' st'himp:Q' ↠ Qst:Stater:Resulthc:st =[ c ]=> rhpre:P stst':Statehr:r = Result.normal st'hQ':Q' st'⊢ ∃ st', r = Result.normal st' ∧ Q st' P:AssertionQ:AssertionQ':Assertionc:Comhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q' st'himp:Q' ↠ Qst:Stater:Resulthc:st =[ c ]=> rhpre:P stst':Statehr:r = Result.normal st'hQ':Q' st'⊢ r = Result.normal st' ∧ Q st' All goals completed! 🐙 theorem hoare_seq {P Q R : Assertion} {c₁ c₂ : Com} (h₁ : {{ Q }} c₂ {{R}}) (h₂ : {{ P }} c₁ {{ Q }}) : {{ P }} c₁; c₂ {{R}} := P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:{{Q}} ~c₂ {{R}}h₂:{{P}} ~c₁ {{Q}}⊢ {{P}} c₁; c₂ {{R}} P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'h₂:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'⊢ ∀ {st : State} {r : Result}, (st =[ c₁; c₂ ]=> r) → P st → ∃ st', r = Result.normal st' ∧ R st' P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'h₂:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Stater:Resultheval:st =[ c₁; c₂ ]=> rhpre:P st⊢ ∃ st', r = Result.normal st' ∧ R st' inversion heval with P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'h₂:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Stater:Resulthpre:P stst'✝:Statehc₁:st =[ ~c₁ ]=> Result.normal st'✝hc₂:st'✝ =[ ~c₂ ]=> r⊢ ∃ st', r = Result.normal st' ∧ R st' P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'h₂:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Stater:Resulthpre:P stst'✝:Statehc₁:st =[ ~c₁ ]=> Result.normal st'✝hc₂:st'✝ =[ ~c₂ ]=> r⊢ Q st'✝ P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'st:Stater:Resulthpre:P stst'✝:Stateh₂:∃ st', Result.normal st'✝ = Result.normal st' ∧ Q st'hc₁:st =[ ~c₁ ]=> Result.normal st'✝hc₂:st'✝ =[ ~c₂ ]=> r⊢ Q st'✝ P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'st:Stater:Resulthpre:P stst'✝:Statehc₁:st =[ ~c₁ ]=> Result.normal st'✝hc₂:st'✝ =[ ~c₂ ]=> rst'':Stateheq:Result.normal st'✝ = Result.normal st''hQ:Q st''⊢ Q st'✝ P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'st:Stater:Resulthpre:P stst'✝:Statehc₁:st =[ ~c₁ ]=> Result.normal st'✝hc₂:st'✝ =[ ~c₂ ]=> rst'':StatehQ:Q st''e:st'✝ = st''⊢ Q st'✝ P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'st:Stater:Resulthpre:P stst'✝:Statehc₁:st =[ ~c₁ ]=> Result.normal st'✝hc₂:st'✝ =[ ~c₂ ]=> rhQ:Q st'✝⊢ Q st'✝ All goals completed! 🐙 P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'h₂:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st'st:Statehpre:P sthc₁:st =[ ~c₁ ]=> Result.error⊢ ∃ st', Result.error = Result.normal st' ∧ R st' -- Find contradictory assumption P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'h₂:∃ st', Result.error = Result.normal st' ∧ Q st'st:Statehpre:P sthc₁:st =[ ~c₁ ]=> Result.error⊢ ∃ st', Result.error = Result.normal st' ∧ R st' P:AssertionQ:AssertionR:Assertionc₁:Comc₂:Comh₁:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → Q st → ∃ st', r = Result.normal st' ∧ R st'st:Statehpre:P sthc₁:st =[ ~c₁ ]=> Result.errorst':StatehC:Result.error = Result.normal st'right✝:Q st'⊢ ∃ st', Result.error = Result.normal st' ∧ R st' All goals completed! 🐙

Here are the other proof rules (sanity check)

theorem hoare_skip {P : Assertion} : {{ P }} skip {{ P }} := P:Assertion⊢ {{P}} skip {{P}} P:Assertion⊢ ∀ {st : State} {r : Result}, (st =[ skip ]=> r) → P st → ∃ st', r = Result.normal st' ∧ P st' P:Assertionst:Stater:Resulth:st =[ skip ]=> rhpre:P st⊢ ∃ st', r = Result.normal st' ∧ P st' P:Assertionst:Statehpre:P st⊢ ∃ st', Result.normal st = Result.normal st' ∧ P st' All goals completed! 🐙 theorem hoare_if {P Q : Assertion} {b : Bexp} {c₁ c₂ : Com} (htrue : {{ P ∧ b}} c₁ {{ Q }}) (hfalse : {{ P ∧ ¬ b}} c₂ {{ Q }}) : {{ P }} if (b) { c₁ } else { c₂ } {{ Q }} := P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:{{P ∧ b}} ~c₁ {{Q}}hfalse:{{P ∧ ¬b}} ~c₂ {{Q}}⊢ {{P}} if (b) {c₁} else {c₂} {{Q}} P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'hfalse:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → P st ∧ ¬Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'⊢ ∀ {st : State} {r : Result}, (st =[ if (b) {c₁} else {c₂} ]=> r) → P st → ∃ st', r = Result.normal st' ∧ Q st' P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'hfalse:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → P st ∧ ¬Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'st:Stater:Resultheval:st =[ if (b) {c₁} else {c₂} ]=> rhpre:P st⊢ ∃ st', r = Result.normal st' ∧ Q st' inversion heval with P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'hfalse:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → P st ∧ ¬Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'st:Stater:Resulthpre:P sthb:Bexp.eval st b = truehc:st =[ ~c₁ ]=> r⊢ ∃ st', r = Result.normal st' ∧ Q st' -- b is true; `htrue` needs a proof of `P st ∧ b.eval st = true`, -- which `apply_rules` builds from `hpre` and `hb` via `And.intro` -- (conjunction-introduction isn't one of its automatic defaults) All goals completed! 🐙 P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'hfalse:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → P st ∧ ¬Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'st:Stater:Resulthpre:P sthb:Bexp.eval st b = falsehc:st =[ ~c₂ ]=> r⊢ ∃ st', r = Result.normal st' ∧ Q st' -- b is false P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'hfalse:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → P st ∧ ¬Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'st:Stater:Resulthpre:P sthb:Bexp.eval st b = falsehc:st =[ ~c₂ ]=> r⊢ P st ∧ ¬Bexp.eval st b = true exact ⟨hpre, P:AssertionQ:Assertionb:Bexpc₁:Comc₂:Comhtrue:∀ {st : State} {r : Result}, (st =[ c₁ ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'hfalse:∀ {st : State} {r : Result}, (st =[ c₂ ]=> r) → P st ∧ ¬Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st'st:Stater:Resulthpre:P sthb:Bexp.eval st b = falsehc:st =[ ~c₂ ]=> r⊢ ¬Bexp.eval st b = true All goals completed! 🐙⟩ theorem hoare_while {P : Assertion} {b : Bexp} {c : Com} (hhoare : {{P ∧ b}} c {{ P }}) : {{ P }} while (b) { c } {{ P ∧ ¬ b}} := P:Assertionb:Bexpc:Comhhoare:{{P ∧ b}} ~c {{P}}⊢ {{P}} while (b) {c} {{P ∧ ¬b}} P:Assertionb:Bexpc:Comhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'⊢ ∀ {st : State} {r : Result}, (st =[ while (b) {c} ]=> r) → P st → ∃ st', r = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true P:Assertionb:Bexpc:Comhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'st:Stater:Resultheval:st =[ while (b) {c} ]=> rhpre:P st⊢ ∃ st', r = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true P:Assertionb:Bexpc:Comhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'st:Stater:Resulthpre:P stcmd:Comheq:imp {while (b) {c} } = cmdheval:st =[ cmd ]=> r⊢ ∃ st', r = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true induction heval generalizing P with b:Bexpc:Comst:Stater:Resultcmd:Comb✝:Bexpst✝:Statec✝:Comhb:Bexp.eval st✝ b✝ = falseP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {while (b✝) {c✝} }⊢ ∃ st', Result.normal st✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comb✝:Bexpst✝:Statec✝:Comhb:Bexp.eval st✝ b✝ = falseP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hbeq:b = b✝hceq:c = c✝⊢ ∃ st', Result.normal st✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:StateP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hb:Bexp.eval st✝ b = false⊢ ∃ st', Result.normal st✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true exact ⟨_, rfl, hpre, b:Bexpc:Comst:Stater:Resultcmd:Comst✝:StateP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hb:Bexp.eval st✝ b = false⊢ ¬Bexp.eval st✝ b = true All goals completed! 🐙⟩ b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Statest'✝:Stater✝:Resultb✝:Bexpc✝:Comhb:Bexp.eval st✝ b✝ = truehc:st✝ =[ ~c✝ ]=> Result.normal st'✝hloop:st'✝ =[ while (b✝) {c✝} ]=> r✝ih₁:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c✝ → ∃ st', Result.normal st'✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueih₂:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st'✝ → imp {while (b) {c} } = imp {while (b✝) {c✝} } → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {while (b✝) {c✝} }⊢ ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Statest'✝:Stater✝:Resultb✝:Bexpc✝:Comhb:Bexp.eval st✝ b✝ = truehc:st✝ =[ ~c✝ ]=> Result.normal st'✝hloop:st'✝ =[ while (b✝) {c✝} ]=> r✝ih₁:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c✝ → ∃ st', Result.normal st'✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueih₂:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st'✝ → imp {while (b) {c} } = imp {while (b✝) {c✝} } → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hbeq:b = b✝hceq:c = c✝⊢ ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Statest'✝:Stater✝:ResultP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hb:Bexp.eval st✝ b = truehc:st✝ =[ ~c ]=> Result.normal st'✝ih₁:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c → ∃ st', Result.normal st'✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = truehloop:st'✝ =[ while (b) {c} ]=> r✝ih₂:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st'✝ → imp {while (b) {c} } = imp {while (b) {c} } → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true⊢ ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Statest'✝:Stater✝:ResultP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hb:Bexp.eval st✝ b = truehc:st✝ =[ ~c ]=> Result.normal st'✝ih₁:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c → ∃ st', Result.normal st'✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = truehloop:st'✝ =[ while (b) {c} ]=> r✝ih₂:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st'✝ → imp {while (b) {c} } = imp {while (b) {c} } → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true⊢ P st'✝ b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Statest'✝:Stater✝:ResultP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hb:Bexp.eval st✝ b = truehc:st✝ =[ ~c ]=> Result.normal st'✝ih₁:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c → ∃ st', Result.normal st'✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = truehloop:st'✝ =[ while (b) {c} ]=> r✝ih₂:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st'✝ → imp {while (b) {c} } = imp {while (b) {c} } → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trues₁:Stateheq₁:Result.normal st'✝ = Result.normal s₁hs₁:P s₁⊢ P st'✝ b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Statest'✝:Stater✝:ResultP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hb:Bexp.eval st✝ b = truehc:st✝ =[ ~c ]=> Result.normal st'✝ih₁:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c → ∃ st', Result.normal st'✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = truehloop:st'✝ =[ while (b) {c} ]=> r✝ih₂:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st'✝ → imp {while (b) {c} } = imp {while (b) {c} } → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trues₁:Statehs₁:P s₁he:st'✝ = s₁⊢ P st'✝ b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Statest'✝:Stater✝:ResultP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hb:Bexp.eval st✝ b = truehc:st✝ =[ ~c ]=> Result.normal st'✝ih₁:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c → ∃ st', Result.normal st'✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = truehloop:st'✝ =[ while (b) {c} ]=> r✝ih₂:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st'✝ → imp {while (b) {c} } = imp {while (b) {c} } → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = truehs₁:P st'✝⊢ P st'✝ All goals completed! 🐙 b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stateb✝:Bexpc✝:Comhb:Bexp.eval st✝ b✝ = truehc:st✝ =[ ~c✝ ]=> Result.errorhc_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c✝ → ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {while (b✝) {c✝} }⊢ ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stateb✝:Bexpc✝:Comhb:Bexp.eval st✝ b✝ = truehc:st✝ =[ ~c✝ ]=> Result.errorhc_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c✝ → ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hbeq:b = b✝hceq:c = c✝⊢ ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:StateP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hb:Bexp.eval st✝ b = truehc:st✝ =[ ~c ]=> Result.errorhc_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c → ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true⊢ ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:StateP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝hb:Bexp.eval st✝ b = truehc:st✝ =[ ~c ]=> Result.errorhc_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c → ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trues₁:Stateheq₁:Result.error = Result.normal s₁hs₁:P s₁⊢ ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true All goals completed! 🐙 b:Bexpc:Comst:Stater:Resultcmd:Comst✝:StateP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {skip}⊢ ∃ st', Result.normal st✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Statea✝:Aexpn✝:Natx✝:Identh✝:Aexp.eval st✝ a✝ = n✝P:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {x✝ := a✝}⊢ ∃ st', Result.normal (x✝ →ₜ n✝ ; st✝) = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comc₁✝:Comc₂✝:Comst✝:Statest'✝:Stater✝:Resulth₁✝:st✝ =[ ~c₁✝ ]=> Result.normal st'✝h₂✝:st'✝ =[ ~c₂✝ ]=> r✝h₁_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c₁✝ → ∃ st', Result.normal st'✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueh₂_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st'✝ → imp {while (b) {c} } = c₂✝ → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {c₁✝; c₂✝}⊢ ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comc₁✝:Comc₂✝:Comst✝:Stateh✝:st✝ =[ ~c₁✝ ]=> Result.errorh_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c₁✝ → ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {c₁✝; c₂✝}⊢ ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stater✝:Resultb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = truehc✝:st✝ =[ ~c₁✝ ]=> r✝hc_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c₁✝ → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stater✝:Resultb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = falsehc✝:st✝ =[ ~c₂✝ ]=> r✝hc_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c₂✝ → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stateb✝:Bexphb✝:Bexp.eval st✝ b✝ = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {assert (b✝)}⊢ ∃ st', Result.normal st✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stateb✝:Bexphb✝:Bexp.eval st✝ b✝ = falseP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {assert (b✝)}⊢ ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stateb✝:Bexphb✝:Bexp.eval st✝ b✝ = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {assume (b✝)}⊢ ∃ st', Result.normal st✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true b:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stateb✝:Bexphb✝:Bexp.eval st✝ b✝ = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {assume (b✝)}⊢ ∃ st', Result.normal st✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueb:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stateb✝:Bexphb✝:Bexp.eval st✝ b✝ = falseP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {assert (b✝)}⊢ ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueb:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stateb✝:Bexphb✝:Bexp.eval st✝ b✝ = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {assert (b✝)}⊢ ∃ st', Result.normal st✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueb:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stater✝:Resultb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = falsehc✝:st✝ =[ ~c₂✝ ]=> r✝hc_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c₂✝ → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueb:Bexpc:Comst:Stater:Resultcmd:Comst✝:Stater✝:Resultb✝:Bexpc₁✝:Comc₂✝:Comhb✝:Bexp.eval st✝ b✝ = truehc✝:st✝ =[ ~c₁✝ ]=> r✝hc_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c₁✝ → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {if (b✝) {c₁✝} else {c₂✝} }⊢ ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueb:Bexpc:Comst:Stater:Resultcmd:Comc₁✝:Comc₂✝:Comst✝:Stateh✝:st✝ =[ ~c₁✝ ]=> Result.errorh_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c₁✝ → ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {c₁✝; c₂✝}⊢ ∃ st', Result.error = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueb:Bexpc:Comst:Stater:Resultcmd:Comc₁✝:Comc₂✝:Comst✝:Statest'✝:Stater✝:Resulth₁✝:st✝ =[ ~c₁✝ ]=> Result.normal st'✝h₂✝:st'✝ =[ ~c₂✝ ]=> r✝h₁_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st✝ → imp {while (b) {c} } = c₁✝ → ∃ st', Result.normal st'✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueh₂_ih✝:∀ {P : Assertion}, (∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st') → P st'✝ → imp {while (b) {c} } = c₂✝ → ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {c₁✝; c₂✝}⊢ ∃ st', r✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueb:Bexpc:Comst:Stater:Resultcmd:Comst✝:Statea✝:Aexpn✝:Natx✝:Identh✝:Aexp.eval st✝ a✝ = n✝P:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {x✝ := a✝}⊢ ∃ st', Result.normal (x✝ →ₜ n✝ ; st✝) = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = trueb:Bexpc:Comst:Stater:Resultcmd:Comst✝:StateP:Assertionhhoare:∀ {st : State} {r : Result}, (st =[ c ]=> r) → P st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ P st'hpre:P st✝heq:imp {while (b) {c} } = imp {skip}⊢ ∃ st', Result.normal st✝ = Result.normal st' ∧ P st' ∧ ¬Bexp.eval st' b = true All goals completed! 🐙

Finally, state Hoare rules for assert and assume and use them to prove a simple program correct. Name your rules hoare_assert and hoare_assume.

Note to developers

HIDE: Equivalently, we could make the postcondition Q ∧ b or the precondition Q → b ... (for hoare_assert). Likewise, for hoare_assume, we could make the postcondition Q ∧ b.

theorem hoare_assert {Q : Assertion} {b : Bexp} : {{Q ∧ b}} assert (b) {{ Q }} := Q:Assertionb:Bexp⊢ {{Q ∧ b}} assert (b) {{Q}} Q:Assertionb:Bexp⊢ ∀ {st : State} {r : Result}, (st =[ assert (b) ]=> r) → Q st ∧ Bexp.eval st b = true → ∃ st', r = Result.normal st' ∧ Q st' Q:Assertionb:Bexpst:Stater:Resultheval:st =[ assert (b) ]=> rhpre:Q st ∧ Bexp.eval st b = true⊢ ∃ st', r = Result.normal st' ∧ Q st' Q:Assertionb:Bexpst:Stater:Resultheval:st =[ assert (b) ]=> rhst:Q sthb:Bexp.eval st b = true⊢ ∃ st', r = Result.normal st' ∧ Q st' Q:Assertionb:Bexpst:Stater:Resultheval:st =[ assert (b) ]=> rhst:Q sthb:Bexp.eval st b = true⊢ r = Result.normal st ∧ Q st inversion heval with Q:Assertionb:Bexpst:Statehst:Q sthb:Bexp.eval st b = truehb':Bexp.eval st b = true⊢ Result.normal st = Result.normal st ∧ Q st All goals completed! 🐙 Q:Assertionb:Bexpst:Statehst:Q sthb:Bexp.eval st b = truehb':Bexp.eval st b = false⊢ Result.error = Result.normal st ∧ Q st All goals completed! 🐙 /- Stating this in a backwards-direction friendly way. -/ theorem hoare_assume {Q : Assertion} {b : Bexp} : {{ b → Q }} assume (b) {{ Q }} := Q:Assertionb:Bexp⊢ {{b → Q}} assume (b) {{Q}} Q:Assertionb:Bexp⊢ ∀ {st : State} {r : Result}, (st =[ assume (b) ]=> r) → (Bexp.eval st b = true → Q st) → ∃ st', r = Result.normal st' ∧ Q st' Q:Assertionb:Bexpst:Stater:Resultheval:st =[ assume (b) ]=> rhpre:Bexp.eval st b = true → Q st⊢ ∃ st', r = Result.normal st' ∧ Q st' Q:Assertionb:Bexpst:Stater:Resultheval:st =[ assume (b) ]=> rhpre:Bexp.eval st b = true → Q st⊢ r = Result.normal st ∧ Q st inversion heval with Q:Assertionb:Bexpst:Statehpre:Bexp.eval st b = true → Q sthb:Bexp.eval st b = true⊢ Result.normal st = Result.normal st ∧ Q st All goals completed! 🐙

Use your rules to prove the following triple.

theorem assert_assume_example : {{True}} assume (X = 1); X := X + 1; assert (X = 2) {{True}} := ⊢ {{True}} assume (X = 1); X := X + 1; assert (X = 2) {{True}} solution! ⊢ {{?P'}} assume (X = 1); X := X + 1; assert (X = 2) {{True}}⊢ {{True}} ↠ ?P'⊢ Assertion ⊢ {{?P'}} assume (X = 1); X := X + 1; assert (X = 2) {{True}} ⊢ {{?hhoare.Q}} X := X + 1; assert (X = 2) {{True}}⊢ {{?P'}} assume (X = 1) {{?hhoare.Q}}⊢ Assertion ⊢ {{?hhoare.Q}} X := X + 1; assert (X = 2) {{True}} ⊢ {{?hhoare.h₁.Q}} assert (X = 2) {{True}}⊢ {{?hhoare.Q}} X := X + 1 {{?hhoare.h₁.Q}}⊢ Assertion ⊢ {{?hhoare.h₁.Q}} assert (X = 2) {{True}} All goals completed! 🐙 ⊢ {{?hhoare.Q}} X := X + 1 {{True ∧ bexp {X = 2} }} All goals completed! 🐙 ⊢ {{?P'}} assume (X = 1) {{(True ∧ bexp {X = 2}) [X ↦ X + 1]}} All goals completed! 🐙 ⊢ {{True}} ↠ {{bexp {X = 1} → (True ∧ bexp {X = 2}) [X ↦ X + 1]}} All goals completed! 🐙 end HoareAssertAssume
Source revision: 0519b34, committed 2026-11-20 16:53 UTC