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.

Now we consider a systematic method for proving that Imp programs do what we intend them to do. We develop:

  • a natural notation for program specifications and

  • a compositional proof technique for program correctness, called Hoare logic

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])

5.1.1. Notations for Assertions🔗

We'll use Lean's notation features to make assertions look as much like informal math as possible.

For example, instead of writing

fun st => st[X] = m

we'll usually write just

{{ X = m }}

Here, the {{ A }} brackets delimit the scope of the assertion notation.

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:

{{ f e1 ... en }} stands for (fun st => f (e1 st) ... (en st)).

We can place a raw Lean function directly inside assertion notation:

For example: {{ fun st => ∀ x, st[x] = 0 }}

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🔗

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! 🐙

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! 🐙
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.

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.

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 declaration uses `sorry`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}} 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 declaration uses `sorry`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}} All goals completed! 🐙

5.4. Proof Rules🔗

We want to be able to prove Hoare triples formally.

Here's our plan:

  • introduce one "proof rule" for each Imp syntactic form

  • plus a couple of "structural rules" that help glue proofs together

  • prove these rules correct in terms of the definition of ValidHoareTriple

  • prove programs correct using these proof rules, without ever unfolding the definition of ValidHoareTriple

  • we state the rules as theorems, rather than as a separate inductive proof system

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! 🐙

5.4.3. Assignment🔗

How can we complete this triple?

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

One natural possibility is:

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

The precondition is just the postcondition, but with X replaced by Y.

How about this one?

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

Replace X with X + Y:

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

This works because "equals 1" holding of X is guaranteed by the property "equals 1" holding of whatever is being assigned to X.

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.

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.

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.

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 declaration uses `sorry`hoare_asgn_example1 : {{True}} X := 1 {{X = 1}} := ⊢ {{True}} X := 1 {{X = 1}} 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 declaration uses `sorry`assertion_sub_example2 : {{X < 4}} X := X + 1 {{X < 5}} := ⊢ {{X < 4}} X := X + 1 {{X < 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).

Here's a good candidate for automation:

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.

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.

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.

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.

Better:

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

To make this formal, we need a way of formally "lifting" any Bexp b to an assertion.

Inside {{ }}, a boolean expression b stands for the assertion "the boolean expression b evaluates to 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🔗

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! 🐙 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! 🐙)

5.4.7.2. Exercise: One-sided conditionals🔗

Note to developers

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

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.

The Hoare while rule combines the idea of a command invariant with information about when guard b does or does not hold.

        {{P ∧ b}} c {{P}}
--------------------------------- (hoare_while)
{{P}} while b do c end {{P ∧ ¬b}}
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.

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

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

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.

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).

5.5. Summary🔗

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🔗

5.6.2. Assert and Assume🔗

Source revision: 4432bd0, committed 2026-10-24 18:24 UTC