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|_=>puretendAssertionopenscopedAssertion
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)}}
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
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:
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.)
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!)
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}}
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.
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:
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.
theoremdeclaration uses `sorry`hoare_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 seqsorryAll goals completed! 🐙·h₂⊢ {{True}}X:=1{{X=1}}-- left part of seqsorryAll 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.
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.
Now we can formalize the Hoare proof rule for conditionals
and prove it correct.
We can even shorten it a little bit more. Wherever Lean expects a term of
some type, we may write (by <tactics>) in its place: the tactics run
immediately, and the proof they produce is spliced in as that term. Here we
use it to supply hoare_consequence_pre's second argument, the
implication P ↠ P', directly at the call site, instead of apply-ing
hoare_consequence_pre and discharging that goal afterward with a
separate bullet.
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.
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 }}).
-- FILL IN HERE
For example (hoare_if1_good) your rule should be strong
enough to show the following Hoare triple is valid:
{{ X + Y = Z }}
if1 (Y ≠ 0) {
X := X + Y
}
{{ X = Z }}
Before the next exercise, we need to restate the Hoare rules of
consequence (for preconditions) and assignment for the new Com
type.
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.
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.
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.
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.
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.
-- FILL IN HERE
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 }}
-- FILL IN HERE-- FILL IN HERE-- FILL IN HERE-- FILL IN HERE-- FILL IN HEREendRepeatExercise
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.
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.
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.