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
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: AssertionsnamespaceAssertionopenLeanElabTermMetaImp.Elabscopedsyntax:max"assn("ident"; "term")":termscopedsyntax:lead"{{"term"}}":term-- `: Assertion` guards that the resulting type is `State → Prop`.macro_rules|`({{$t}})=>`((funst:_root_.State=>assn(st;$t):Assertion))macro_rules|`(assn($st;$t))=>doletresult←matchtwith|`(($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*)=>doletmutresult:=fforarginargsdoresult←`($resultassn($st;$arg))pureresult|_=>Macro.throwUnsupportedreturnwithSourceInfoOftresultelab_rules:term|`(assn($st;$t:term))=>dolett←elabTermtnoneletty←whnf(←inferTypet)tryPostponeIfMVartyletst←elabTermstnonematch_exprtywith|String=>mkAppM``_root_.MyGetElem.getElem#[st,t]|Aexp=>mkAppM``Aexp.eval#[st,t]|Bexp=>mkAppM``Bexp.eval#[st,t]|_=>matchtywith|.forallE_domainbody_=>ifbody.isProp&&(←isDefEqdomain(mkConst``_root_.State))thenpure<|mkApptstelsepuret|_=>puret
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?
endAssertionopenscopedAssertion
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.
namespaceAssertion.DelabopenLeanPrettyPrinterDelaboratorSubExprImp.ElabImp.DelabprivatedefgetAssn(stx:Term):Term:=withSourceInfoOf(canonical:=false)stx<|Unhygienic.rundomatchstxwith|`({{$P}})=>returnP|_=>returnstx/-- 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. -/partialdefdelabBody(stId:FVarId):DelabMTerm:=dolete←getExprif!e.containsFVarstIdthendelabelsematch_exprewith|MyGetElem.getElem____stk=>guard(st==.fvarstId)iflet.lit(.strVals):=kthen`($(mkIdent(Name.mkSimples)):ident)elsewithAppArgdelab|Aexp.evalst_=>guard(st==.fvarstId)withAppArgdelab|HAdd.hAdd______=>`($(←withAppFn<|withAppArg(delabBodystId))+$(←withAppArg(delabBodystId)))|HSub.hSub______=>`($(←withAppFn<|withAppArg(delabBodystId))-$(←withAppArg(delabBodystId)))|HMul.hMul______=>`($(←withAppFn<|withAppArg(delabBodystId))*$(←withAppArg(delabBodystId)))|Eq_lr=>-- `Bexp.eval st b = true` is the threaded form of a bare-- boolean `b`ifr.isConstOf``Bool.true&&l.isAppOfArity``Bexp.eval2&&l.appFn!.appArg!==.fvarstIdthenwithAppFn<|withAppArg<|withAppArgdelabelse`($(←withAppFn<|withAppArg(delabBodystId))=$(←withAppArg(delabBodystId)))|Ne___=>`($(←withAppFn<|withAppArg(delabBodystId))≠$(←withAppArg(delabBodystId)))|LE.le____=>`($(←withAppFn<|withAppArg(delabBodystId))≤$(←withAppArg(delabBodystId)))|LT.lt____=>`($(←withAppFn<|withAppArg(delabBodystId))<$(←withAppArg(delabBodystId)))|GE.ge____=>`($(←withAppFn<|withAppArg(delabBodystId))≥$(←withAppArg(delabBodystId)))|GT.gt____=>`($(←withAppFn<|withAppArg(delabBodystId))>$(←withAppArg(delabBodystId)))|And__=>`($(←withAppFn<|withAppArg(delabBodystId))∧$(←withAppArg(delabBodystId)))|Or__=>`($(←withAppFn<|withAppArg(delabBodystId))∨$(←withAppArg(delabBodystId)))|Iff__=>`($(←withAppFn<|withAppArg(delabBodystId))↔$(←withAppArg(delabBodystId)))|Not_=>`(¬$(←withAppArg(delabBodystId)))|_=>ife.isArrowthen`($(←withBindingDomain(delabBodystId))→$(←withBindingBody`h(delabBodystId)))elseiflet.appfv:=ethenifv==.fvarstId&&!f.containsFVarstIdthen-- 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 printingletfty←Meta.whnfR(←Meta.inferTypef)guard<|fty.isArrow&&fty.bindingBody!.isPropguard<|←Meta.isDefEqfty.bindingDomain!(mkConst``_root_.State)iff.isLambdathen-- 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!.instantiate1v)0(delabBodystId)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 formguard<|f.isFVar||f.isConst||f.isMVar||f.isAppOf`Assertion.substwithAppFndelabelse`($(←withAppFn(delabBodystId))$(←withAppArg(delabBodystId)))elsefailure/-- 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. -/partialdefdelabAssn:DelabMTerm:=dolete←getExprife.isLambdathenlete:=e.updateLambdaE!e.bindingDomain!e.bindingBody!.headBetadescende0do(withBindingBody'`st(pure·.fvarId!)funstId=>delabBodystId)<|>Delaborator.delabelsedelab/-- Print an assertion-position argument: a state lambda gets the
`{{ … }}` notation; any other term (a named assertion, a substitution)
already reads well bare. -/defdelabAssnArg(i:Nat):DelabMTerm:=doif(←withNaryArgigetExpr).isLambdathen`({{$(←withNaryArgidelabAssn)}})elsewithNaryArgiDelaborator.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. -/@[delablam]defdelabAssertion:Delab:=whenPPOptiongetPPNotationdolete←getExprguard<|e.isLambda&&e.bindingDomain!.isConstOf``_root_.StateletP←withBindingBody'`st(pure·.fvarId!)funstId=>doguard(←Meta.inferType(←getExpr)).isPropdelabBodystId`({{$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. -/@[delabapp.Exists]defdelabExistsState:Delab:=whenPPOptiongetPPNotationdolete←getExprguard<|e.isAppOfArity``Exists2letlam:=e.appArg!guard<|lam.isLambda&&lam.bindingDomain!.isConstOf``_root_.StatewithAppArg<|withBindingBodyUnusedNamefunx=>doletx:TSyntax`ident:=⟨x⟩letbody←delab`(∃$x:ident,$body)endAssertion.Delab
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
If command c terminates starting in an arbitrary state it produces a
state where the value of X is equal to 5.
Starting in a state where the value of X is m, if c terminates the
value of X is equal to m+5.
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.
c doesn't terminate on any starting state.
If c terminates then Y contains as a value the factorial of the
initial value of X.
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}}
We overload the {{ P }} c {{ Q }} notation across
command types with a typeclass, the same way the Equiv typeclass of
Equiv overloads ≃:
classHasTriple(α:Type)whereTriple:Assertion→α→Assertion→Propinstance:HasTripleComwhereTriple:=ValidHoareTripleNotation: Hoare triplesnamespaceHasTriple/-- Hoare triple: `{{ P }} c {{ Q }}` with `imp_com` command syntax -/scopedsyntax:lead"{{"term"}} "imp_com:min" {{"term"}}":termscopedmacro_rules|`({{$P}}$c:imp_com{{$Q}})=>``(HasTriple.Triple({{$P}})(imp{$c})({{$Q}}))endHasTriple
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.
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.
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 }}
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:
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 substitutionnamespaceAssertion/-- 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). -/scopedsyntax:max(priority:=high)term:arg" ["ident" ↦ "imp_aexp"]":termmacro_rules|`(assn($st;$P[$x↦$a:imp_aexp]))=>matchPwith|`($_:ident)=>``(Assertion.subst$x(aexp{$a})$P$st)|_=>``(Assertion.subst$x(aexp{$a})({{$P}})$st)endAssertionnamespaceAssertion.DelabopenLeanPrettyPrinterDelaboratorSubExprImp.ElabImp.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_unexpanderAssertion.subst]defunexpandSubst:Unexpander|`($_$x$a$P)=>doletx←matchxwith|`($x:ident)=>purex|`($s:str)=>pure(mkObjectIdentFroms.raws.getString)|_=>throw()matchgetAssnPwith|`($P:ident)=>`($P:ident[$x:ident↦$(getAexpa):imp_aexp])|P=>`(($P)[$x:ident↦$(getAexpa):imp_aexp])|_=>throw()endAssertion.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.
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.
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}}
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.
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).
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.
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.
We can also leave a metavariable for P' in hoare_asgn_example1,
which we did earlier as an example of using the consequence rule:
theoremhoare_asgn_example1':{{True}}X:=1{{X=1}}:=by⊢ {{True}}X:=1{{X=1}}applyhoare_consequence_prehhoare⊢ {{?P'}}X:=1{{X=1}}himp⊢ {{True}}↠?P'P'⊢ Assertion·hhoare⊢ {{?P'}}X:=1{{X=1}}-- The goal is `{{?P'}} X := 1 {{X = 1}}`exacthoare_asgnAll goals completed! 🐙-- assigns `{{ (X = 1) [X ↦ 1] }}` to `?P'`, closing `case P'`·himp⊢ {{True}}↠(X=1)[X↦1]introst_himpst:Statea✝:True⊢ (X=1)[X↦1]st-- Since `↠` is an implication, we can just use `intro` directly.simpAll goals completed! 🐙
The final bullet of that proof also looks like a candidate for
automation.
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.
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.
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.
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.
theoremhoare_asgn_example3(a:Aexp)(n:Nat):{{a=n}}X:=a;skip{{X=n}}:=bya:Aexpn:Nat⊢ {{a=n}}X:=a;skip{{X=n}}applyhoare_seqh₁a:Aexpn:Nat⊢ {{?Q}}skip{{X=n}}h₂a:Aexpn:Nat⊢ {{a=n}}X:=a{{?Q}}Qa:Aexpn:Nat⊢ Assertion·h₁a:Aexpn:Nat⊢ {{?Q}}skip{{X=n}}-- right part of seqexacthoare_skipAll goals completed! 🐙·h₂a:Aexpn:Nat⊢ {{a=n}}X:=a{{X=n}}-- left part of seqapplyhoare_consequence_preh₂.hhoarea:Aexpn:Nat⊢ {{?h₂.P'}}X:=a{{X=n}}h₂.himpa:Aexpn:Nat⊢ {{a=n}}↠?h₂.P'h₂.P'a:Aexpn:Nat⊢ Assertion·h₂.hhoarea:Aexpn:Nat⊢ {{?h₂.P'}}X:=a{{X=n}}exacthoare_asgnAll goals completed! 🐙·h₂.himpa:Aexpn:Nat⊢ {{a=n}}↠(X=n)[X↦a]assertion_autoAll 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.
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 Bexpb 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.
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}}
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.
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).
-------------------------- (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.