Theory PHoare

(*  Title:       Inductive definition of Hoare logic
    Author:      Tobias Nipkow, 2001/2006
    Maintainer:  Tobias Nipkow

theory PHoare imports PLang begin

subsection‹Hoare logic for partial correctness›

text‹Taking auxiliary variables seriously means that assertions must
now depend on them as well as on the state. Initially we do not fix
the type of auxiliary variables but parameterize the type of
assertions with a type variable @{typ 'a}:›

type_synonym 'a assn = "'a  state  bool"

The second major change is the need to reason about Hoare
triples in a context: proofs about recursive procedures are conducted
by induction where we assume that all @{term CALL}s satisfy the given
pre/postconditions and have to show that the body does as well. The
assumption is stored in a context, which is a set of Hoare triples:›

type_synonym 'a cntxt = "('a assn × com × 'a assn)set"

text‹\noindent In the presence of only a single procedure the context will
always be empty or a singleton set. With multiple procedures, larger
sets can arise.

Now that we have contexts, validity becomes more complicated. Ordinary
validity (w.r.t.\ partial correctness) is still what it used to be,
except that we have to take auxiliary variables into account as well:

 valid :: "'a assn  com  'a assn  bool" (" {(1_)}/ (_)/ {(1_)}" 50) where
     " {P}c{Q}  (s t. s -c t  (z. P z s  Q z t))"

text‹\noindent Auxiliary variables are always denoted by @{term z}.

Validity of a context and validity of a Hoare triple in a context are defined
as follows:›

 valids :: "'a cntxt  bool" ("|⊨ _" 50) where
  [simp]: "|⊨ C  ((P,c,Q)  C.  {P}c{Q})"

 cvalid :: "'a cntxt  'a assn  com  'a assn  bool" ("_ / {(1_)}/ (_)/ {(1_)}" 50) where
  "C  {P}c{Q}  |⊨ C   {P}c{Q}"

text‹\noindent Note that @{prop"{}  {P}c{Q}"} is equivalent to
@{prop" {P}c{Q}"}.

Unfortunately, this is not the end of it. As we have two
semantics, -c→› and -c-n→›, we also need a second notion
of validity parameterized with the recursion depth @{term n}:›

 nvalid :: "nat  'a assn  com  'a assn  bool" ("_ {(1_)}/ (_)/ {(1_)}" 50) where
  "n {P}c{Q}  (s t. s -c-n t  (z. P z s  Q z t))"

 nvalids :: "nat  'a cntxt  bool" ("|⊨'__/ _" 50) where
  "|⊨_n C  ((P,c,Q)  C. n {P}c{Q})"

 cnvalid :: "'a cntxt  nat  'a assn  com  'a assn  bool" ("_ _/ {(1_)}/ (_)/ {(1_)}" 50) where
  "C n {P}c{Q}  |⊨_n C  n {P}c{Q}"

text‹Finally we come to the proof system for deriving triples in a context:›

  hoare :: "'a cntxt  'a assn  com  'a assn  bool" ("_ / ({(1_)}/ (_)/ {(1_)})" 50)
   (*<*)Do:(*>*)"C  {λz s. t  f s . P z t} Do f {P}"

 | (*<*)Semi:(*>*)" C  {P}c1{Q}; C  {Q}c2{R}   C  {P} c1;c2 {R}"

 | (*<*)If:(*>*)" C  {λz s. P z s  b s}c1{Q};  C  {λz s. P z s  ¬b s}c2{Q}  
    C  {P} IF b THEN c1 ELSE c2 {Q}"

 | (*<*)While:(*>*)"C  {λz s. P z s  b s} c {P}
    C  {P} WHILE b DO c {λz s. P z s  ¬b s}"

 | (*<*)Conseq:(*>*)" C  {P'}c{Q'};  s t. (z. P' z s  Q' z t)  (z. P z s  Q z t) 
    C  {P}c{Q}"

 | (*<*)Call:(*>*)"{(P,CALL,Q)}  {P}body{Q}  {}  {P} CALL {Q}"

 | (*<*)Asm:(*>*)"{(P,CALL,Q)}  {P} CALL {Q}"
 | (*<*)Local:(*>*) " s'. C  {λz s. P z s'  s = f s'} c {λz t. Q z (g s' t)}  
        C  {P} LOCAL f;c;g {Q}"

abbreviation hoare1 :: "'a cntxt  'a assn × com × 'a assn  bool" ("_  _") where
  "C  x  C  {fst x}fst (snd x){snd (snd x)}"

text‹\noindent The first four rules are familiar, except for their adaptation
to auxiliary variables. The @{term CALL} rule embodies induction and
has already been motivated above. Note that it is only applicable if
the context is empty. This shows that we never need nested induction.
For the same reason the assumption rule (the last rule) is stated with
just a singleton context.

The rule of consequence is explained in the accompanying paper.

lemma strengthen_pre:
 " z s. P' z s  P z s; C {P}c{Q}    C {P'}c{Q}"
by(rule hoare.Conseq, assumption, blast)

lemmas valid_defs = valid_def valids_def cvalid_def
                    nvalid_def nvalids_def cnvalid_def

theorem hoare_sound: "C  {P}c{Q}    C  {P}c{Q}"
txt‹\noindent requires a generalization: @{prop"n. C n
{P}c{Q}"} is proved instead, from which the actual theorem follows
directly via lemma @{thm[source]exec_iff_execn} in \S\ref{sec:proc1-lang}.
The generalization
is proved by induction on @{term c}. The reason for the generalization
is that soundness of the @{term CALL} rule is proved by induction on the
maximal call depth, i.e.\ @{term n}.›
apply(subgoal_tac "n. C n {P}c{Q}")
apply(unfold valid_defs exec_iff_execn)
 apply fast
apply(erule hoare.induct)
        apply simp
       apply fast
      apply simp
     apply clarify
     apply(drule while_rule)
       prefer 3
       apply (assumption, assumption)
     apply fast
    apply fast
   prefer 2
   apply simp
 apply(rule allI, rule impI)
 apply(induct_tac n)
  apply blast
 apply clarify
 apply (simp(no_asm_use))
 apply blast
apply auto

The completeness proof employs the notion of a \emph{most general triple} (or
\emph{most general formula}):›

  MGT :: "com  state assn × com × state assn" where
  "MGT c = (λz s. z = s, c, λz t. z -c t)"

declare MGT_def[simp]

text‹\noindent Note that the type of @{term z} has been identified with
@{typ state}.  This means that for every state variable there is an auxiliary
variable, which is simply there to record the value of the program variables
before execution of a command. This is exactly what, for example, VDM offers
by allowing you to refer to the pre-value of a variable in a
postcondition. The intuition behind @{term"MGT c"} is
that it completely describes the operational behaviour of @{term c}.  It is
easy to see that, in the presence of the new consequence rule,
\mbox{@{prop"{}  MGT c"}} implies completeness:›

lemma MGT_implies_complete:
 "{}  MGT c    {}  {P}c{Q}    {}  {P}c{Q::state assn}"
apply(simp add: MGT_def)
apply (erule hoare.Conseq)
apply(simp add: valid_defs)

text‹In order to discharge @{prop"{}  MGT c"} one proves›

lemma MGT_lemma: "C  MGT CALL    C  MGT c"
apply (simp)
apply(induct_tac c)
      apply (rule strengthen_pre[OF _ hoare.Do])
      apply blast
     apply(blast intro:hoare.Semi hoare.Conseq)
    apply(rule hoare.If)
    apply(erule hoare.Conseq)
     apply simp
    apply(erule hoare.Conseq)
    apply simp
   prefer 2
   apply simp
 apply(rename_tac b c)
 apply(rule hoare.Conseq)
  apply(rule_tac P = "λz s. (z,s)  ({(s,t). b s  s -c t})^*"
        in hoare.While)
  apply(erule hoare.Conseq)
  apply(blast intro:rtrancl_into_rtrancl)
 apply clarsimp
 apply(rename_tac s t)
 apply(erule_tac x = s in allE)
 apply clarsimp
 apply(erule converse_rtrancl_induct)
  apply simp
 apply(fast elim:exec.WhileTrue)
apply(fastforce intro: hoare.Local elim!: hoare.Conseq)

text‹\noindent The proof is by induction on @{term c}. In the @{term
While}-case it is easy to show that @{term"λz t. (z,t)  ({(s,t). b
s  s -c t})^*"} is invariant. The precondition \mbox{@{term[source]"λz s. z=s"}}
establishes the invariant and a reflexive transitive closure
induction shows that the invariant conjoined with @{prop"¬b t"}
implies the postcondition \mbox{@{term"λz t. z -WHILE b DO c t"}}. The
remaining cases are trivial.

Using the @{thm[source]MGT_lemma} (together with the CALL› and the
assumption rule) one can easily derive›

lemma MGT_CALL: "{}  MGT CALL"
apply(simp add: MGT_def)
apply (rule hoare.Call)
apply (rule hoare.Conseq[OF MGT_lemma[simplified], OF hoare.Asm])
apply (fast intro:exec.intros)

text‹\noindent Using the @{thm[source]MGT_lemma} once more we obtain
@{prop"{}  MGT c"} and thus by @{thm[source]MGT_implies_complete}

theorem "{}  {P}c{Q}    {}  {P}c{Q::state assn}"
apply(erule MGT_implies_complete[OF MGT_lemma[OF MGT_CALL]])