Note to developers (Benjamin Pierce @bcpierce00, before next release, 2025)
There is an excellent and fairly polished problem
on a Hoare Logic for a little assembly language in the materials
for the 2025 CIS 5000 final exam at Penn. We should turn it into an
exercise in this chapter!
Note to developers (Benjamin Pierce @bcpierce00, before next release, 2021)
Any chance we could move the (awkwardly placed)
weakest precondition discussion to this chapter instead?
The terse version of the chapter needs serious
work — it has gotten quite ragged after a bunch of reorganization
of the chapter over the past couple years. BCP 23: Did some work
on it. Bit better now. But the notation issues make everything a
bit heavy.
Note to developers
HIDE: What about typesetting multi-line triples as
{{ P }}
c
{{ Q }}
instead of
{{ P }}
c
{{ Q }}
when we print them?
Note to developers (Mike Hicks @mwhicks1, 2026)
The terse version of this chapter is not sufficiently terse, IMO.
Too much explanation in the text itself. When going through this
in class I found myself scrolling through a lot of the text that
is shown to get to the good parts.
In the Imp and Equiv chapters, we built up the
mathematical machinery for talking about Imp programs precisely — an
evaluation relation giving their operational semantics, and a notion of
behavioral equivalence for judging when two programs do the same thing.
We now turn to a different kind of question: whether a single program
behaves the way we intend.
Our goal in this chapter is to develop the tools for simple program
verification: using the precise definition of Imp to prove, formally,
that particular programs satisfy particular specifications of their
behavior. We'll develop a reasoning system called Floyd-Hoare Logic —
usually shortened to Hoare Logic — that equips each syntactic
construct of Imp with a generic "proof rule," so that the structure of a
correctness proof mirrors the structure of the program it is about.
First developed in the 1960s, Hoare Logic remains the basis of a
multitude of tools used in academia and industry to specify and verify
real software systems.
Hoare Logic combines two beautiful ideas: a natural way of writing down
specifications of programs, and a structured proof technique for
proving that programs are correct with respect to such specifications —
where by "structured" we mean that the structure of proofs directly
mirrors the structure of the programs that they are about.
This way of writing assertions can be a little bit heavy,
for two reasons: (1) every single assertion that we ever write is
going to begin with fun st => ; and (2) this state st is the
only one that we ever use to look up variables in assertions (we
will almost never need to talk about two different memory states at the
same time). For discussing examples informally, we'll adopt some
simplifying conventions: we'll drop the initial fun st =>, and
we'll write just X to mean st[X]. Thus, instead of writing
fun st => st[X] = m
we'll write just
{{ X = m }}.
Here the "doubly curly" braces {{ and }} delimit
the scope of an assertion. We'll see more examples below.
This example also illustrates a convention that we'll use
throughout the Hoare Logic chapters: in informal assertions,
capital letters like X, Y, and Z are Imp variables, while
lowercase letters like x, y, m, and n are ordinary Lean
variables. This is why, when translating from
informal to formal, we replace X with st[X] but leave m
alone.
The convention described above can be implemented with a little
syntax magic, much as we did with the imp { … } notation in
Imp. This new notation automatically lifts Aexps,
numbers, and Props into Assertions when they appear between the
{{ _ }} brackets.
There is no need to understand the details of how these notations
work, so we have tucked them away in a collapsible block below.
Notation: 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. Thus, {{ f e1 ... en }} stands for
fun st => f (e1 st) ... (en st).
Occasionally it is simpler to write an assertion directly as a Lean
function. A fun st => … can be placed inside the assertion notation
without an escape marker, and so can the name of an assertion.
For example, {{ fun st => ∀ x, st[x] = 0 }} indicates an assertion that
every variable maps to 0 in the given state.
(An assertion obtained by applying a function to arguments, say
f x y, must be written as fun st => f x y st, since the notation would
otherwise interpret x and y in the current state. We will see an
example in the havoc exercise at the end of the chapter.)
Notation encoding: printing assertions back
As in the Imp chapter, the assertion notation
above is input only: Lean reads {{ X ≤ 5 }} but still prints the
underlying function by default. The delaborators below close the loop
for plain assertions: a state lambda whose body Lean can rebuild is
printed back in {{ … }} notation, and an assertion Lean cannot
rebuild falls back to the raw fun st => … form, which is exactly
this notation's escape syntax, so what you see is always valid input.
Each time a new notation involving assertions appears below
(implication, Hoare triples, substitution), a small delaborator
defined next to it will extend this printing to cover it. As before,
there is no need to understand the details.
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
(The scoped keyword tells Lean that this notation is not global but is
available only where the Assertion namespace is open, as it is
throughout this chapter.)
To type ↠ in VS Code, we can write \rr-.
We'll also want the "iff" variant of implication between
assertions:
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.
Exercise★(triples) (Optional)
Paraphrase the following in English.
1) {{True}} c {{X = 5}}
2) ∀ m, {{X = m}} c {{X = m + 5}}
3) {{X ≤ Y}} c {{Y ≤ X}}
4) {{True}} c {{False}}
5) ∀ m,
{{X = m}}
c
{{Y = realFact m}}
6) ∀ m,
{{X = m}}
c
{{(Z * Z) ≤ m ∧ ¬ ((Z + 1) * (Z + 1) ≤ m)}}
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}}
(A) Yes
(B) No
Show solution
Yes: the loop never terminates.
Exercise★(valid_triples) (Optional)
Which of the following Hoare triples are valid — i.e., the
claimed relation between P, c, and Q is true?
1) {{True}} X := 5 {{X = 5}}
2) {{X = 2}} X := X + 1 {{X = 3}}
3) {{True}} X := 5; Y := 0 {{X = 5}}
4) {{X = 2 ∧ X = 3}} X := 5 {{X = 0}}
5) {{True}} skip {{False}}
6) {{False}} skip {{True}}
7) {{True}} while true do skip end {{False}}
8) {{X = 0}}
while X = 0 do X := X + 1 end
{{X = 1}}
9) {{X = 1}}
while X ≠ 0 do X := X + 1 end
{{X = 100}}
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.
The goal of Hoare logic is to provide a compositional
method for proving the validity of specific Hoare triples. That
is, we want the structure of a program's correctness proof to
mirror the structure of the program itself. To this end, in the
sections below, we'll introduce a rule for reasoning about each of
the different syntactic forms of commands in Imp — one for
assignment, one for sequencing, one for conditionals, etc. — plus
a couple of "structural" rules for gluing things together. We
will then be able to prove programs correct using these proof
rules, without ever unfolding the definition of ValidHoareTriple.
The presentation of Hoare logic in this chapter could be
described as model-theoretic: the proof rules for each of the
syntactic forms are presented as theorems about the evaluation
behavior of programs, justified according to ValidHoareTriple.
Another way of presenting Hoare logic is to define a completely
separate proof system — a set of axioms and inference rules as
part of an inductive proposition — and then say that a
proof of a Hoare triple is a valid derivation in that logic.
Then we would prove this logic sound in the sense that all proofs
in that logic (its derivations) have a corresponding (Lean) proof
of ValidHoareTriple. This approach could be
described as proof theoretic. Since the most natural proof of soundness
would be via the model-theoretic approach, we present that
approach and leave a proof theoretic presentation (and discussion
of its potential advantages) to a future development.
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 }}
Note that, in the formal rule hoare_seq, the premises are
given in backwards order (c₂ before c₁). This matches the
natural flow of information in many of the situations where we'll
use the rule, since the natural way to construct a Hoare-logic
proof is to begin at the end of the program (with the final
postcondition) and push postconditions backwards through commands
until we reach the beginning.
The rule for assignment is the most fundamental of the Hoare
logic proof rules. Here's how it works.
Consider this incomplete Hoare triple:
{{ ??? }} X := Y {{ X = 1 }}
We want to assign Y to X and finish in a state where X is 1.
What could the precondition be?
One possibility is Y = 1, because if Y is already 1 then
assigning it to X causes X to be 1. That leads to a valid
Hoare triple:
{{ Y = 1 }} X := Y {{ X = 1 }}
It may seem as though coming up with that precondition must have
taken some clever thought. But there is a mechanical way we could
have done it: if we take the postcondition X = 1 and in it
replace X with Y — that is, replace the left-hand side of the
assignment statement with the right-hand side — we get the
precondition, Y = 1.
That same idea works in more complicated cases. For
example:
{{ ??? }} X := X + Y {{ X = 1 }}
If we replace the X in X = 1 with X + Y, we get X + Y = 1.
That again leads to a valid Hoare triple:
{{ X + Y = 1 }} X := X + Y {{ X = 1 }}
Why does this technique work? The postcondition identifies some
property P that we want to hold of the variable X being
assigned. In this case, P is "equals 1". To complete the
triple and make it valid, we need to identify a precondition that
guarantees that property will hold of X. Such a precondition
must ensure that the same property holds of whatever is being
assigned toX. So, in the example, we need "equals 1" to
hold of X + Y. That's exactly what the technique guarantees.
In general, the postcondition could be some arbitrary assertion
Q, and the right-hand side of the assignment could be some
arbitrary arithmetic expression a:
{{ ??? }} X := a {{ Q }}
The precondition would then be Q, but with any occurrences of
X in it replaced by a.
Let's introduce a notation for this idea of replacing occurrences:
Define Q [X ↦ a] to mean "Q where a is substituted in
place of X".
This yields the Hoare logic rule for assignment:
{{ Q [X ↦ a] }} X := a {{ Q }}
One way of reading this rule is: If you want statement X := a
to terminate in a state that satisfies assertion Q, then it
suffices to start in a state that also satisfies Q, except
where a is substituted for every occurrence of X.
To many people, this rule seems "backwards" at first, because
it proceeds from the postcondition to the precondition. Actually
it makes good sense to go in this direction: the postcondition is
often what is more important, because it characterizes what will be
true after running the code.
Nonetheless, it's also possible to formulate a "forward" assignment
rule. We'll do that later in some exercises.
Here are some valid instances of the assignment rule:
{{ (X ≤ 5) [X ↦ X + 1] }} (that is, X + 1 ≤ 5)
X := X + 1
{{ X ≤ 5 }}
{{ (X = 3) [X ↦ 3] }} (that is, 3 = 3)
X := 3
{{ X = 3 }}
{{ (0 ≤ X ∧ X ≤ 5) [X ↦ 3] }} (that is, 0 ≤ 3 ∧ 3 ≤ 5)
X := 3
{{ 0 ≤ X ∧ X ≤ 5 }}
To formalize the rule, we must first formalize the idea of
"substituting an expression for an Imp variable in an assertion",
which we refer to as assertion substitution, or Assertion.subst.
Intuitively, given a proposition P, a variable X, and an
arithmetic expression a, we want to derive another proposition
P' that is just the same as P except that P' should mention
a wherever P mentions X.
This operation is related to the idea of substituting Imp
expressions for Imp variables that we saw in Equiv
(Aexp.subst and friends). The difference is that, here,
P is an arbitrary Lean assertion, so we can't directly
"edit" its text.
However, we can achieve the same effect by evaluating P in an
updated state, defined as follows:
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.
To see how this works in more detail, let's calculate what happens with
a couple of examples. First, suppose P' is (X ≤ 5) [X ↦ 3] —
that is, more formally, P' is the Lean expression
fun st =>
(fun st' => st'[X] ≤ 5)
(X →ₜ Aexp.eval st 3 ; st),
which simplifies to
fun st =>
(fun st' => st'[X] ≤ 5)
(X →ₜ 3 ; st)
and further simplifies to
fun st =>
((X →ₜ 3 ; st)[X]) ≤ 5
and finally to
fun st =>
3 ≤ 5.
That is, P' is the assertion that 3 is less than or equal to
5 (as expected).
For a more interesting example, suppose P' is (X ≤ 5) [X ↦
X + 1]. Formally, P' is the Lean expression
fun st =>
(fun st' => st'[X] ≤ 5)
(X →ₜ Aexp.eval st (aexp { X + 1 }) ; st),
which simplifies to
fun st =>
(X →ₜ Aexp.eval st (aexp { X + 1 }) ; st)[X] ≤ 5
and further simplifies to
fun st =>
(Aexp.eval st (aexp { X + 1 })) ≤ 5.
That is, P' is the assertion that X + 1 is at most 5.
Of course, we'd probably prefer to work with this simpler triple:
{{X < 4}} X := X + 1 {{X < 5}}
We will see how to do so in the next section.
Several proofs below use the facts about total-map updates
proved in the Typeclasses chapter — TotalMap.update_eq,
TotalMap.update_neq, TotalMap.update_shadow,
TotalMap.update_same, and TotalMap.update_permute. Make
sure you understand their statements.
Complete these Hoare triples by providing an appropriate
precondition using exists, then prove them with apply
hoare_asgn. If you find that tactic doesn't suffice, double check
that you have completed the triple properly.
The assignment rule looks backward to almost everyone the first
time they see it. If it still seems puzzling to you, it may help
to think a little about alternative "forward" rules. Here is a
seemingly natural one:
----------------------------- (hoare_asgn_wrong)
{{ True }} X := a {{ X = a }}
Give a counterexample showing that this rule is incorrect and use
it to complete the proof below, showing that it is really a
counterexample. (Hint: The rule universally quantifies over the
arithmetic expression a, so your counterexample needs to
exhibit an a for which the rule doesn't work.)
If a itself mentions X, then the value of a may be different
in the final state because of this update. For example, if a is
X + 1, then setting X to a certainly does not achieve the
postcondition X = X + 1! The underlying problem is that the
state in which the postcondition will be checked is different than
the state in which a was evaluated when it was assigned to X.
Exercise★★★(hoare_asgn_fwd) (Advanced, Optional)
By using a parameterm (a Lean number) to remember the
original value of X we can define a Hoare rule for assignment
that does, intuitively, "work forwards" rather than backwards.
------------------------------------------ (hoare_asgn_fwd)
{{ P ∧ X = m }}
X := a
{{ fun st => P (X →ₜ m ; st) ∧ st[X] = a.eval (X →ₜ m ; st) }}
Note that we need to write out the postcondition in "desugared"
form, because it needs to talk about two different states: we use
the original value of X to reconstruct the state st' before the
assignment took place. (Also note that this rule is more complicated
than hoare_asgn!)
Prove that this rule is correct.
Note to developers
HIDE: BCP 21: Could we make the precondition use compact
notation, at least?
HIDE: SAZ 2024 - this version of the syntax does let
us use the compact notation for the precondition, but it
comes at the cost of having to "escape" the function in
the postcondition.
Another way to define a forward rule for assignment is to
existentially quantify over the previous value of the assigned
variable. Prove that it is correct.
------------------------------------ (hoare_asgn_fwd_exists)
{{ P }}
X := a
{{ fun st => ∃ m, P (X →ₜ m ; st) ∧
st[X] = a.eval (X →ₜ m ; st) }}
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).
The proof of hoare_consequence_pre, repeated below, looks
like an opportune place for automation, because all it does
is rewrite with the characterizing lemmas, intro, and
apply. (It uses exact, too, but that's just
application of a hypothesis.)
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.
By now it might be apparent that the entire proof could be
automated by a more ambitious tactic that also knew about the Hoare
rules themselves. We won't build one in this chapter, so that we
can get a better understanding of when and how the Hoare rules are
used. In the next chapter, Hoare2, we'll dive deeper into
automating entire proofs of Hoare triples.
The other example of using consequence that we did earlier,
assertion_sub_example2, requires a little more work to automate.
simp simplifies the assertion implication in the final bullet,
but cannot finish it: the leftover goal is arithmetic, so it needs
lia.
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.
Exercise★★(hoare_asgn_examples_2)
Prove these triples. Try to make your proof scripts nicely
automated by following the examples above.
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.
Exercise★★(hoare_asgn_example4)
Translate this "decorated program" into a formal proof:
{{ True }} ↠
{{ 1 = 1 }}
X := 1
{{ X = 1 }} ↠
{{ X = 1 ∧ 2 = 2 }};
Y := 2
{{ X = 1 ∧ Y = 2 }}
We've started you off by providing a use of hoare_seq that
explicitly identifies X = 1 as the intermediate assertion.
theoremhoare_asgn_example4:{{True}}X:=1;Y:=2{{X=1∧Y=2}}:=by⊢ {{True}}X:=1;Y:=2{{X=1∧Y=2}}applyhoare_seq(Q:={{X=1}})h₁⊢ {{X=1}}Y:=2{{X=1∧Y=2}}h₂⊢ {{True}}X:=1{{X=1}}·h₁⊢ {{X=1}}Y:=2{{X=1∧Y=2}}-- right part of seqsolution!applyhoare_consequence_preh₁.hhoare⊢ {{?h₁.P'}}Y:=2{{X=1∧Y=2}}h₁.himp⊢ {{X=1}}↠?h₁.P'h₁.P'⊢ Assertion·h₁.hhoare⊢ {{?h₁.P'}}Y:=2{{X=1∧Y=2}}exacthoare_asgnAll goals completed! 🐙·h₁.himp⊢ {{X=1}}↠(X=1∧Y=2)[Y↦2]assertion_autoAll goals completed! 🐙·h₂⊢ {{True}}X:=1{{X=1}}-- left part of seqsolution!applyhoare_consequence_preh₂.hhoare⊢ {{?h₂.P'}}X:=1{{X=1}}h₂.himp⊢ {{True}}↠?h₂.P'h₂.P'⊢ Assertion·h₂.hhoare⊢ {{?h₂.P'}}X:=1{{X=1}}exacthoare_asgnAll goals completed! 🐙·h₂.himp⊢ {{True}}↠(X=1)[X↦1]assertion_autoAll goals completed! 🐙
Exercise★★★(swap_exercise) (Manually graded)
Write an Imp program c that swaps the values of X and Y and
show that it satisfies the following specification:
{{X ≤ Y}} c {{Y ≤ X}}
Your proof should not need to use rw [validHoareTriple_def].
Hints:
Remember that Imp commands need to be enclosed in imp { … }
brackets.
Remember that the assignment rule works best when it's
applied "back to front," from the postcondition to the
precondition. So your proof will want to start at the end
and work back to the beginning of your program.
Remember that apply is your friend.
Note to developers
HIDE: CH: Here goes:
[[
{{ X ≤ Y }}
Z := X
{{ Z ≤ Y }};
X := Y
{{ Z ≤ X }};
Y := Z
{{ Y ≤ X }}
]]
The _only_ catch is that one needs to do it backwards, since that's
how the hoare_asgn rule is defined.
Maybe move this decorated program to the decorated programs
section, since it's a good warm-up exercise.
is not a valid Hoare triple for some choices of a and n.
Conceptual hint: Invent a particular a and n for which the
triple is invalid, then use those to complete the proof.
Technical hint: Hypothesis h below begins ∀ a n, ....
You'll want to instantiate that with the particular a and n
you've invented. You can do that with have and apply, but
you may remember (from the Tactics chapter of Logical Foundations)
that Lean offers an even easier tactic: specialize. If you write
specialize h your_a your_n
the hypothesis will be instantiated on your_a and your_n.
Having chosen your a and n, proceed as follows:
Use the (assumed) validity of the given hoare triple to derive
a state st' in which Y has some value y1
Use the evaluation rules (EvalR.seq and EvalR.asgn) to show
that Y has a different value y2 in the same final state st'
Since y1 and y2 are both equal to st'[Y], they are equal
to each other. But we chose them to be different, so this is a
contradiction, which finishes the proof.
What sort of rule do we want for reasoning about conditional
commands?
Certainly, if the same assertion Q holds after executing
either of the branches, then it holds after the whole conditional.
So we might be tempted to write:
{{P}} c₁ {{Q}}
{{P}} c₂ {{Q}}
--------------------------------
{{P}} if b then c₁ else c₂ {{Q}}
However, this is rather weak. For example, using this rule,
we cannot show
{{ True }}
if X = 0
then Y := 2
else Y := X + 1
end
{{ X ≤ Y }}
since the rule doesn't tell us enough about the state in which the
assignments take place in the "then" and "else" branches.
Fortunately, we can say something more precise. In the
"then" branch, we know that the boolean expression b evaluates to
true, and in the "else" branch, we know it evaluates to false.
Making this information available in the premises of the rule gives
us more information to work with when reasoning about the behavior
of c₁ and c₂ (i.e., the reasons why they establish the
postcondition Q).
{{P ∧ b}} c₁ {{Q}}
{{P ∧ ¬ b}} c₂ {{Q}}
------------------------------------ (hoare_if)
{{P}} if b then c₁ else c₂ end {{Q}}
To interpret this rule formally, we need to do a little work.
Strictly speaking, the assertion we've written, P ∧ b, is the
conjunction of an assertion and a boolean expression — i.e., it
doesn't typecheck. To fix this, we need a way of formally
"lifting" any Bexpb to an assertion. Inside the {{ }}
brackets, a boolean expression b stands for the assertion "the
boolean expression b evaluates to true (in the given state),"
that is, fun st => b.eval st = true.
Note to developers (Niklas Halonen @xhalo32)
I have removed bassertion as it's an unnecessary abstraction and only
adds overhead for the reader.
Now we can formalize the Hoare proof rule for conditionals
and prove it correct.
We can even shorten it a little bit more. Recall that wherever Lean expects a term of
some type, we may write (by <tactics>) in its place: the tactics run
immediately, and the proof they produce is spliced in as that term. Here we
use it to supply hoare_consequence_pre's second argument, the
implication P ↠ P', directly at the call site, instead of apply-ing
hoare_consequence_pre and discharging that goal afterward with a
separate bullet.
Prove the theorem below using hoare_if. Do not unfold
ValidHoareTriple (i.e., do not use validHoareTriple_def). The
assertion_auto tactic defined above may be useful.
HIDE: Question from 2012, Midterm 2. One-sided conditionals.
In this exercise we consider extending Imp with "one-sided
conditionals" of the form if1 (b) { c }. Here b is a boolean
expression, and c is a command. If b evaluates to true, then
command c is evaluated. If b evaluates to false, then
if1 (b) { c } does nothing.
We recommend that you complete this exercise before attempting the
ones that follow, as it should help solidify your understanding of
the material.
The first step is to extend the syntax of commands and introduce
the usual notations. (We've done this for you, in a separate
namespace to prevent polluting the global name space. The scoped
notations below are active only inside namespace If1.)
The delaborators are re-instantiated the same way: the Imp printer is
parameterized over the namespace of the command constructors, so the
extended printer is that printer at If1.Com plus one case for if1.
The following unit tests should be provable simply by applying your
new rules (plus rfl for the boolean side conditions) if you have
defined them correctly.
Now we have to repeat the definition of Hoare triples, so that it
uses the updated Com type. The {{ P }} c {{ Q }} notation
itself is generic: it only needs a new HasTriple instance.
Invent a Hoare logic proof rule for if1. State and prove a
theorem named hoare_if1 that shows the validity of your rule.
Use hoare_if as a guide. Try to invent a rule that is
complete, meaning it can be used to prove the correctness of as
many one-sided conditionals as possible. Also try to keep your
rule compositional, meaning that any Imp command that appears
in a premise should syntactically be a part of the command
in the conclusion.
Hint: if you encounter difficulty getting Lean to parse part of
your rule as an assertion, try wrapping it in the {{ … }} brackets
(and in parentheses, when it is an argument of ↠). For example, if
you want P ∧ ¬ b to be read as an assertion, write it as
({{ P ∧ ¬ b }}).
Use your if1 rule to prove the following (valid) Hoare triple.
Hint: assertion_auto will once again get you most but not all
the way to a completely automated proof. You can finish manually,
or tweak the tactic further.
Hint: If you see a message about failing to unify commands from the
top-level Com with commands from this namespace, it probably means
you are using a definition or theorem (e.g., hoare_skip) from
above this exercise without re-proving it for the new version of
Imp with if1.
The Hoare rule for while loops is based on the idea of a
command invariant (or just invariant): an assertion whose
truth is guaranteed after executing a command, assuming it is true
before.
That is, an assertion P is a command invariant of c if
{{P}} c {{P}}
holds. Note that the command invariant might temporarily become
false in the middle of executing c, but by the end of c it
must be restored.
As a first attempt at a while rule, we could try:
{{P}} c {{P}}
---------------------------
{{P}} while b do c end {{P}}
This rule is valid: if P is a command invariant of c, as the
premise requires, then, no matter how many times the loop body
executes, P is going to be true when the loop finally finishes.
But the rule also omits two crucial pieces of information. First,
the loop terminates when b becomes false. So we can strengthen
the postcondition in the conclusion:
{{P}} c {{P}}
---------------------------------
{{P}} while b do c end {{P ∧ ¬b}}
Second, the loop body will be executed only if b is true. So we
can also strengthen the precondition in the premise:
{{P ∧ b}} c {{P}}
--------------------------------- (hoare_while)
{{P}} while b do c end {{P ∧ ¬b}}
That is the Hoare while rule. Note how it combines
aspects of skip and conditionals:
If the loop body executes zero times, the rule is like skip in
that the precondition survives to become (part of) the
postcondition.
Like a conditional, we can assume guard b holds on entry to
the subcommand.
Note to developers (Benjamin Pierce @bcpierce00, before next release, 2021)
This definition / discussion could be clearer.
Note to developers (Benjamin Pierce @bcpierce00, before next release, 2023)
Maja says: The wording of "we will never enter the
loop" could definitely be improved. As is, it suggests a situation
where the loop condition itself can never be satisfied. I suspect that
a previous draft included a discussion that explicitly placed {{ P }}
before the while, perhaps along the lines of "a loop invariant P of
[while b do c end] is also an invariant of [while b do c end]" (which
is, FWIW, a (somewhat obtuse) way of stating a weaker variant of
hoare_while, without the ¬b in the postcondition). Combined with the
fact that it is supposed to justify a somewhat surprising and
unexpected fact — [X = 0] is not what I would intuitively consider an
invariant of this loop — this sentence ends up being quite confusing.
I only understood it when I came back to find this excerpt.
We call P a loop invariant of while b do c end if
{{P ∧ b}} c {{P}}
is a valid Hoare triple.
This means that P will be true at the end of the loop body
whenever the loop body executes. If P contradicts b, this
holds trivially since the precondition is false.
For instance, X = 0 is a loop invariant of
while X = 2 do X := 1 end
since the program will never enter the loop.
Quiz
Is the assertion
Y = 0
a loop invariant of the following?
while X < 100 do X := X + 1 end
(A) Yes
(B) No
Show solution
Yes.
Quiz
Is the assertion
X = 0
a loop invariant of the following?
while X < 100 do X := X + 1 end
(A) Yes
(B) No
Show solution
No.
Quiz
Is the assertion
X < Y
a loop invariant of the following?
while true do X := X + 1; Y := Y + 1 end
(A) Yes
(B) No
Show solution
Yes.
Quiz
Is the assertion
X = Y + Z
a loop invariant of the following?
while Y > 10 do Y := Y - 1; Z := Z + 1 end
(A) Yes
(B) No
Show solution
Yes.
Note to developers (before next release)
This last quiz should be turned into a discussion in the
text, at least in the full version — indeed, maybe all these
should be turned into a long discussion of what it means to be a
loop invariant — I think that would be pretty helpful.
The program
while Y > 10 do Y := Y - 1; Z := Z + 1 end
admits an interesting loop invariant:
X = Y + Z
Note that this doesn't contradict the loop guard but neither
is it a command invariant of
Y := Y - 1; Z := Z + 1
since, if X = 5,
Y = 0 and Z = 5, running the command will set Y + Z to 6. The
loop guard Y > 10 guarantees that this will not be the case.
We will see many such loop invariants in the following chapter.
Note to developers (Benjamin Pierce @bcpierce00, before next release, 2021)
What is this example doing here?? Needs some text.
HIDE: CJC: Maybe also a good place to talk about the structure of
our logic - that we've set up the hoare_* lemmas and they are all
the reasoning about Hoare triples that they should have to use (in
both formal or informal proofs)? Probably should talk about this
somewhere or else we'll get back lots of proofs that unfold
ValidHoareTriple and reason at a low level everywhere.
BCP 21: I think we do this now?
Quiz
Is the assertion
X > 0
a loop invariant of the following?
while X = 0 do X := X - 1 end
(A) Yes
(B) No
Show solution
According to how we defined the term, the answer should be Yes! The
reason is that a loop invariant is defined as a P that, together with
the fact that the guard is true, implies P.
Quiz
Is the assertion
X < 100
a loop invariant of the following?
while X < 100 do X := X + 1 end
(A) Yes
(B) No
Show solution
No.
Quiz
Is the assertion
X > 10
a loop invariant of the following?
while X > 10 do X := X + 1 end
(A) Yes
(B) No
Show solution
Yes.
If the loop never terminates, any postcondition will work.
Of course, this result is not surprising if we remember that
the definition of ValidHoareTriple asserts that the postcondition
must hold only when the command terminates. If the command
doesn't terminate, we can prove anything we like about the
post-condition.
Hoare rules that specify what happens if commands terminate,
without proving that they do, are said to describe a logic of
partial correctness. It is also possible to give Hoare rules
for total correctness, which additionally specifies that
commands must terminate. Total correctness is out of the scope of
this textbook.
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).
In this exercise, we'll add a new command to our language of
commands: repeat { c } until (b). You will write the
evaluation rule for repeat and add a new Hoare rule to the
language for programs involving it.
repeat behaves like while, except that the loop guard is
checked after each execution of the body, with the loop
repeating as long as the guard stays false. Because of this,
the body will always execute at least once.
We also need to extend the imp { } notation to parse the new repeat
command.
Notation encoding: commands, macro rules/-- Repeat loop -/scopedsyntax"repeat"ppHardSpace"{"ppLineimp_comppDedent(ppLine"}")" until ""("imp_bexp")":imp_comopenLeaninscopedmacro_rules|`(imp{$x:ident})=>ifx.getId==`skipthen`(Com.skip)elsepurex|`(imp{$c1;$c2})=>`(Com.seq(imp{$c1})(imp{$c2}))|`(imp{$x:ident:=$a})=>`(Com.asgn$x(aexp{$a}))|`(imp{if($b){$c1}else{$c2}})=>`(Com.cond(bexp{$b})(imp{$c1})(imp{$c2}))|`(imp{while($b){$c}})=>`(Com.whileDo(bexp{$b})(imp{$c}))|`(imp{repeat{$c}until($b)})=>`(Com.repeatUntil(imp{$c})(bexp{$b}))|`(imp{~$c})=>purecnamespaceDelabopenLeanPrettyPrinterImp.Delab@[app_unexpanderCom.repeatUntil]privatedefCom.unexpandRepeatUntil:Unexpander|`($_$c$b)=>`(imp{repeat{$(getImpc)}until($(getBexpb))})|_=>throw()attribute[app_unexpanderCom.skip]unexpandComSkipattribute[app_unexpanderCom.asgn]unexpandComAsgnattribute[app_unexpanderCom.seq]unexpandComSeqattribute[app_unexpanderCom.cond]unexpandComCondattribute[app_unexpanderCom.whileDo]unexpandComWhileDoendDelab
Add new rules for repeat to Com.EvalR below. You can use the rules
for while as a guide, but remember that the body of a repeat
should always execute at least once, and that the loop ends when
the guard becomes true.
Now state and prove a theorem, hoare_repeat, that expresses an
appropriate proof rule for repeat commands. Use hoare_while
as a model, and try to make your rule as precise as possible.
For full credit, make sure (informally) that your rule can be used
to prove the following valid Hoare triple:
{{ X > 0 }}
repeat {
Y := X;
X := X - 1
} until (X = 0)
{{ X = 0 ∧ Y > 0 }}
/- Although it was not required by the exercise, we can show formally
that `hoare_repeat` can handle this litmus test: -/
def ex2Repeat : Com :=
imp {
repeat {
Y := X;
X := X - 1
} until (X = 0)
}
/- Before we can show anything about this program we need to repeat
the proofs of some more Hoare rules from above (remember we're in
a separate namespace, with a different definition of commands). -/
theorem hoare_asgn {Q : Assertion} {x : Ident} {a : Aexp} :
{{Q [x ↦ a]}} x := a {{ Q }} := by
rw [validHoareTriple_def]
intro st st' heval hQ
rw [Assertion.subst_apply] at hQ
inversion heval with
| asgn n h =>
subst h
exact hQ
theorem hoare_consequence {P P' Q Q' : Assertion} {c : Com}
(hht : {{ P' }} c {{ Q' }}) (hPP' : P ↠ P') (hQ'Q : Q' ↠ Q) :
{{ P }} c {{ Q }} := by
rw [validHoareTriple_def] at hht ⊢
intro st st' hc hP
apply_rules
theorem hoare_consequence_pre {P P' Q : Assertion} {c : Com}
(hhoare : {{ P' }} c {{ Q }}) (himp : P ↠ P') :
{{ P }} c {{ Q }} := by
rw [validHoareTriple_def] at hhoare ⊢
intro st st' hc hP
apply_rules
theorem hoare_seq {P Q R : Assertion} {c₁ c₂ : Com}
(h₁ : {{ Q }} c₂ {{R}}) (h₂ : {{ P }} c₁ {{ Q }}) :
{{ P }} c₁; c₂ {{R}} := by
rw [validHoareTriple_def] at h₁ h₂ ⊢
intro st st' heval hpre
inversion heval with
| seq _ hc₁ hc₂ =>
apply_rules/- Now we are ready to show `ex2Repeat` correct using
`hoare_repeat`. -/
theorem ex2Repeat_hoare_repeat :
{{ X > 0 }}
ex2Repeat
{{ X = 0 ∧ Y > 0 }} := by
rw [ex2Repeat]
apply hoare_consequence
· apply hoare_repeat (Q := {{ Y > 0 }})
· exact hoare_seq hoare_asgn hoare_asgn
· apply hoare_seq hoare_asgn
apply hoare_consequence_pre hoare_asgn
assertion_auto
· -- body of repeat if exiting right away
assertion_auto
· -- final postcondition
assertion_auto
/- A sound but less precise variant of the `hoare_repeat` rule looks
like this: -/theorem hoare_repeat' {P : Assertion} {b : Bexp} {c : Com}
(h : {{ P }} c {{ P }}) :
{{ P }} repeat { c } until (b) {{ P ∧ b }} := by
rw [validHoareTriple_def] at h ⊢
intro st st' heval hpre
generalize heq : (imp { repeat { c } until (b) }) = cmd at heval
induction heval with
| repeatEnd hc hb _ =>
injection heq with hceq hbeq
subst hceq hbeq
exact ⟨h hc hpre, hb⟩
| repeatLoop hc hb hloop ih₁ ih₂ =>
injection heq with hceq hbeq
subst hceq hbeq
apply ih₂ (h hc hpre)
rfl
| skip | asgn | seq | ifTrue | ifFalse | whileFalse | whileTrue =>
contradiction
/- First, let's show that `hoare_repeat'` is implied by
`hoare_repeat`. -/
theorem hoare_repeat_implies_hoare_repeat'
(hoare_repeat : ∀ (P Q : Assertion) (b : Bexp) (c : Com),
({{ P }} c {{ Q }}) →
({{ Q ∧ ¬ b }} c {{ Q }}) →
{{ P }} repeat { c } until (b) {{ Q ∧ b }}) :
∀ (P : Assertion) (b : Bexp) (c : Com),
({{ P }} c {{ P }}) →
{{ P }} repeat { c } until (b) {{ P ∧ b }} := by
intro P b c h
apply hoare_repeat <;> try assumption
apply hoare_consequence_pre
· exact h
· intro st ⟨hp, _⟩
exact hp/- However, we can't prove `ex2Repeat` correct using `hoare_repeat'`,
even with a stronger initial precondition on `Y`. Here is a first
failed proof attempt. -/
/-- warning: declaration uses `sorry` -/
#guard_msgs in
example :
{{ X > 0 ∧ Y > 0}}
ex2Repeat
{{ X = 0 ∧ Y > 0}} := by
apply hoare_consequence
· apply hoare_repeat' (P := {{ Y > 0 }})
apply hoare_seq hoare_asgn
apply hoare_consequence_pre hoare_asgn
intro st hy
simp
-- loop invariant too weak on its own,
-- we need the value of the previous guard
sorry
· -- initial precondition
intro st ⟨_, hy⟩
exact hy
-- this only works with an additional Y > 0 precondition
· -- final postcondition
assertion_auto
/- Here is a second failed attempt trying stronger loop invariant, but
it is too strong. -/
/-- warning: declaration uses `sorry` -/
#guard_msgs in
example :
{{ X > 0 ∧ Y > 0}}
ex2Repeat
{{ X = 0 ∧ Y > 0}} := by
apply hoare_consequence
· apply hoare_repeat' (P := {{ X > 0 ∧ Y > 0 }})
apply hoare_seq hoare_asgn
apply hoare_consequence_pre hoare_asgn
intro st ⟨hx, hy⟩
simp
-- loop invariant too strong
sorry
· -- initial precondition
intro st hp
exact hp
· -- final postcondition
assertion_auto
end RepeatExercise
So far, we've introduced Hoare Logic as a tool for reasoning about
Imp programs.
The rules of Hoare Logic are:
-------------------------- (hoare_asgn)
{{Q [X ↦ a]}} X := a {{Q}}
-------------------- (hoare_skip)
{{ P }} skip {{ P }}
{{ P }} c₁ {{ Q }}
{{ Q }} c₂ {{ R }}
---------------------- (hoare_seq)
{{ P }} c₁; c₂ {{ R }}
{{P ∧ b}} c₁ {{Q}}
{{P ∧ ¬ b}} c₂ {{Q}}
------------------------------------ (hoare_if)
{{P}} if b then c₁ else c₂ end {{Q}}
{{P ∧ b}} c {{P}}
----------------------------------- (hoare_while)
{{P}} while b do c end {{P ∧ ¬ b}}
{{P'}} c {{Q'}}
P ↠ P'
Q' ↠ Q
----------------------------- (hoare_consequence)
{{P}} c {{Q}}
Our main task in this chapter has been to define the rules of
Hoare logic, and prove that the definitions are sound. Having
done so, we can go on and work within Hoare logic to prove that
particular programs satisfy particular Hoare triples. In the next
chapter, we'll see how Hoare logic can be used to prove that
more interesting programs satisfy interesting specifications of
their behavior.
Crucially, we will do so without ever again unfolding the
definition of Hoare triples (via validHoareTriple_def) — i.e.,
we will take the rules of Hoare logic as a closed world for reasoning
about programs.
We also need to extend the imp { } notation to parse the new havoc
command, and to print it back.
Notation encoding: commands, macro rules/-- Havoc: set a variable to a nondeterministically chosen number
(`havoc x;`). As with `skip`, the word `havoc` is not reserved: the
production accepts any identifier and the macro below rejects
everything except `havoc`. -/scopedsyntaxidentident:imp_comopenLeaninscopedmacro_rules|`(imp{$x:ident})=>ifx.getId==`skipthen`(Com.skip)elsepurex|`(imp{$c1;$c2})=>`(Com.seq(imp{$c1})(imp{$c2}))|`(imp{$x:ident:=$a})=>`(Com.asgn$x(aexp{$a}))|`(imp{if($b){$c1}else{$c2}})=>`(Com.cond(bexp{$b})(imp{$c1})(imp{$c2}))|`(imp{while($b){$c}})=>`(Com.whileDo(bexp{$b})(imp{$c}))|`(imp{$h:ident$x:ident})=>ifh.getId==`havocthen`(Com.havoc$x)elseMacro.throwErrorAths!"expected 'havoc', got '{h.getId}'"|`(imp{~$c})=>purecnamespaceDelabopenLeanPrettyPrinterImp.Delab@[app_unexpanderCom.havoc]privatedefCom.unexpandHavoc:Unexpander|`($_$x:ident)=>`(imp{$(mkIdent`havoc):ident$x:ident})|_=>throw()attribute[app_unexpanderCom.skip]unexpandComSkipattribute[app_unexpanderCom.asgn]unexpandComAsgnattribute[app_unexpanderCom.seq]unexpandComSeqattribute[app_unexpanderCom.cond]unexpandComCondattribute[app_unexpanderCom.whileDo]unexpandComWhileDoendDelabinductiveCom.EvalR:Com→State→State→Propwhere|skip{st:State}:EvalR(imp{skip})stst|asgn{st:State}{a:Aexp}{n:Nat}{x:Ident}(h:a.evalst=n):EvalR(imp{x:=a})st(x→ₜn;st)|seq{c₁c₂:Com}{stst'st'':State}(h₁:EvalRc₁stst')(h₂:EvalRc₂st'st''):EvalR(imp{c₁;c₂})stst''|ifTrue{stst':State}{b:Bexp}{c₁c₂:Com}(hb:b.evalst=true)(hc:EvalRc₁stst'):EvalR(imp{if(b){c₁}else{c₂}})stst'|ifFalse{stst':State}{b:Bexp}{c₁c₂:Com}(hb:b.evalst=false)(hc:EvalRc₂stst'):EvalR(imp{if(b){c₁}else{c₂}})stst'|whileFalse{b:Bexp}{st:State}{c:Com}(hb:b.evalst=false):EvalR(imp{while(b){c}})stst|whileTrue{stst'st'':State}{b:Bexp}{c:Com}(hb:b.evalst=true)(hc:EvalRcstst')(hloop:Com.EvalR(imp{while(b){c}})st'st''):EvalR(imp{while(b){c}})stst''|havoc{st:State}{x:Ident}{n:Nat}:EvalR(imp{havocx})st(x→ₜn;st)instance:HasEvalComStateStatewhereEval:=Com.EvalR@[simp]theoremCom.evalR_eq{c:Com}{stst':State}:EvalRcstst'↔st=[c]=>st':=byc:Comst:Statest':State⊢ c.EvalRstst'↔st=[c]=>st'rflAll goals completed! 🐙attribute[app_delabCom.EvalR]HasEval.Delab.delabEvalR
The definition of Hoare triples is exactly as before.
Note to developers (Benjamin Pierce @bcpierce00, before next release, 2021)
This exercise turns out to be quite hard — a lot
of people get stuck. We should make it advanced the next time
through. BCP 23: Made it advanced. Can we also explain it better?
Complete the Hoare rule for havoc commands below by defining
havoc_pre, and prove that the resulting rule is correct.
Complete the following proof without changing any of the provided
commands. If you find that it can't be completed, your definition of
havoc_pre is probably too strong. Find a way to relax it so that
havoc_post can be proved.
Hint: the assertion_auto tactic we've built won't help you here.
You need to proceed manually.
Note to developers (before next release)
This exercise is kind of weird. Should probably be
optional.
In this exercise, we will extend Imp with two commands, assert
and assume. Both commands are ways to indicate that a certain
assertion should hold any time this part of the program is
reached. However they differ as follows:
If an assert statement fails, it causes the program to go into
an error state and exit.
If an assume statement fails, the program fails to evaluate at
all. In other words, the program gets stuck and has no final
state.
We also need to extend the imp { } notation to parse the new assert
and assume commands.
Notation encoding: commands, macro rules/-- Assert / assume (`assert (b);`, `assume (b);`). As with `skip`,
the words `assert` and `assume` are not reserved: the production
accepts any identifier and the macro below rejects everything else. -/scopedsyntaxident" ("imp_bexp")":imp_comopenLeaninscopedmacro_rules|`(imp{$x:ident})=>ifx.getId==`skipthen`(Com.skip)elsepurex|`(imp{$h:ident($b)})=>ifh.getId==`assertthen`(Com.assert(bexp{$b}))elseifh.getId==`assumethen`(Com.assume(bexp{$b}))elseMacro.throwErrorAths!"expected 'assert' or 'assume', got '{h.getId}'"|`(imp{$c1;$c2})=>`(Com.seq(imp{$c1})(imp{$c2}))|`(imp{$x:ident:=$a})=>`(Com.asgn$x(aexp{$a}))|`(imp{if($b){$c1}else{$c2}})=>`(Com.cond(bexp{$b})(imp{$c1})(imp{$c2}))|`(imp{while($b){$c}})=>`(Com.whileDo(bexp{$b})(imp{$c}))|`(imp{~$c})=>purecnamespaceDelabopenLeanPrettyPrinterImp.Delab@[app_unexpanderCom.assert]privatedefCom.unexpandAssert:Unexpander|`($_$b)=>`(imp{$(mkIdent`assert):ident($(getBexpb))})|_=>throw()@[app_unexpanderCom.assume]privatedefCom.unexpandAssume:Unexpander|`($_$b)=>`(imp{$(mkIdent`assume):ident($(getBexpb))})|_=>throw()attribute[app_unexpanderCom.skip]unexpandComSkipattribute[app_unexpanderCom.asgn]unexpandComAsgnattribute[app_unexpanderCom.seq]unexpandComSeqattribute[app_unexpanderCom.cond]unexpandComCondattribute[app_unexpanderCom.whileDo]unexpandComWhileDoendDelab
To define the behavior of assert and assume, we need to add
notation for an error, which indicates that an assertion has
failed. We modify the Com.EvalR relation, therefore, so that
it relates a start state to either an end state or to error.
The Result type indicates the end value of a program,
either a state or an error:
We redefine Hoare triples: Now, {{ P }} c {{ Q }} means that,
whenever c is started in a state satisfying P, and terminates
with result r, then r is not an error and the state of r
satisfies Q.
To test your understanding of this modification, give an example
precondition and postcondition that are satisfied by the assume
statement but not by the assert statement.
Finally, state Hoare rules for assert and assume and use them
to prove a simple program correct. Name your rules hoare_assert
and hoare_assume.
Note to developers
HIDE: Equivalently, we could make the postcondition Q ∧ b or the
precondition Q → b ... (for hoare_assert). Likewise, for
hoare_assume, we could make the postcondition Q ∧ b.