Quelle  Quant_Hoare.thy

section "Quantitative Hoare Logic (due to Carbonneaux)"
theory Quant_Hoare
imports Big_StepT Complex_Main "HOL-Library.Extended_Nat"
begin

  
abbreviation "eq a b == (And (Not (Less a b)) (Not (Less b a)))"
   
type_synonym lvname = string
type_synonym assn = "state ==> bool" (* time bound *)t\^ ›
type_synonym qassn = "state ==> enat" (* time bound *)

text ‹The support of an assn2›
 

abbreviation state_subst :: "state \<Rightarrow> aexp \<Rightarrow> vname \<Rightarrow> state"
  (\<open>_[_'/_]\<close> [1000,0,0] 999)
where "s[a/x] == s(x := aval a s)"

fun emb :: "bool \<Rightarrow> enat" (\<open>\<up>\<close>) where
   "emb False = \<infinity>"
 | "emb True = 0"
  
subsection "Validity of quantitative Hoare Triple"
  
(* this definition refines the definition of validity of normal Hoare Triple for total correctness  *)

definition hoare2_valid :: "qassn ==> com \<   moreover
  (‹⊨₂ {(1_)}/ (_)/ {(1_)}› 50) where
"⊨₂ {P} c {Q}  ⟷  (∀s.  P s < ∞ ⟶ (∃t p. ((c,s) ==> p ⇓ t) \      ‹

  "Hoare logic for quantiative reasoning"

 
 hoare2 :: "qassn ==> com ==> qassn ==> bool" (‹⊨₂ ({(1_)}/ (_)/ {(1_)})› 50)
 

 : "⊨₂ {%s. eSuc (P s)} SKIP {P}" |

 : "⊨₂ {λs. eSuc (P (s[a/x]))} x::=a { P }" |

 : "[ ⊨₂ {λs. P s + ↑( bval b s)} c₁ { Q};
 ⊨₂ {λs. P s + ↑(¬ bval b s)} c₂ { Q} ]
 ==> ⊨₂ {λs. eSuc (P s)} IF b THEN c₁ ELSE c₂ { Q }" |

 : "[ ⊨₂ { P₁ } c₁ { P₂ }; ⊨₂ {P₂} c₂ { P₃ }] ==> ⊨₂ {P₁} c₁;;c₂ {P₃}" |
 
 :
 "[ ⊨₂ { %s. I s + ↑(bval b s) } c { %t. I t + 1 } ]
 ==> ⊨₂ {λs. I s + 1 } WHILE b DO c {λs. I s + ↑(¬ bval b s) }" |

 : "[ (auto intro!: "\beta<eftarrowC
 ⊨₂ {P'}c{ Q'}"

  ‹derived rules›

  strengthen_pre: "[ ∀s. P s ≤ P' s; ⊨₂ {P} c {Q} ] ==> ⊨₂ {P'} c {Q}"
 using conseq by blast

  weaken_post: "[ ⊨₂ {P} c {Q}; ∀s. Q s ≥E:1[THEN "→
 using conseq by blast

  Assign': "∀s. P s ≥ eSuc ( Q(s[a/x])) ==> ⊨₂ {P} x ::= a {Q}"
 by (simp add: strengthen_pre[OF _ Assign])

  progress: "(c, s) ==> p ⇓ t ==> p > 0"
 by (induct rule: big_step_t.induct, auto)
 

  FalseImplies: "⊨₂ {%s. ∞} c { Q}"
 apply (induction c arbitrary: Q)
 apply(auto intro: hoare2.Skip hoare2.Assign hoare2.Seq hoare2.conseq)
 subgoal apply(rule hoare2.conseq) apply(rule hoare2.If[where P="%s. ∞"]) by(auto intro: hoare2.If hoare2.conseq)
 subgoal apply(rule hoare2.conseq) apply(rule hoare2.While[where I="%s. ∞"]) apply(rule hoare2.conseq) by auto
 done
 
  "Sound simp: "&I" "ex:1:a1:a" prod_dentesI "rule-ui:3")

 
 
 
 ‹The soundness theorem:›
 
  help1: assumes " enat a + X ≤ Y"
 "enat b + Z ≤ X"
 shows "enat (a + b) + Z ≤ Y"
 using assms by (metis ab_semigroup_add_class.add_ac(1) add_left_mono order_trans plus_enat_simps(1))
 
  help2': assumes "enat p + INV t ≤ INV s"
 "0 < p" "INV s = enat n"
 shows "INV t < INV s"
 using assms iadd_le_enat_iff by auto
 
  help2: assumes "enat p + INV t + 1 ≤ INV s"
 "INV s = enat n"
 shows "INV t < INV s"
 using assms le_less_trans not_less_iff_gr_or_eq by fastforce
 
 
  Seq_sound: assumes "⊨₂ {P1} C1 {P2}"
 "⊨₂ {P2} C2 {P3}"
 shows "⊨₂ {P1} C1 ;; C2 {P3}"
  hoare2_valid_def
  (safe)
 fix s
 assume ninfP1: "P1 s < \∞"
 with assms(1)[unfolded hoare2_valid_def] obtain t1 p1
 where 1: "(C1, s) ==> p1 ⇓ t1" and q1: "enat p1 + P2 t1 ≤ P1 s" by blast
 with ninfP1 have ninfP2: "P2 t1 < \∞"
 using not_le by fastforce
 with assms(2)[unfolded hoare2_valid_def] obtain t2 p2
 where 2: "(C2, t1) ==> p2 ⇓ t2" and q2: "enat p2 + P3 t2 ≤ P2 t1" by blast
 with ninfP2 have ninfP3: "P3 t2 < \
 using not_le by fastforce
 
 from Big_StepT.Seq[OF 1 2] have bigstep: "(C1;; C2, s) ==> p1 + p2 ⇓ t2" by simp
 from help1[OF q1 q2] have potential: "enat (p1 + p2) + P3 t2 ≤ P1 s" .
 
 show "∃t p. (C1;; C2, s) ==> p ⇓ t ∧ enat p + P3 t ≤ P1 s "
 apply(rule exI[where x="t2"])
 apply(rule exI[where x="p1 + p2"])
 using bigstep potential by simp
 
 
 
  hoare2_sound: "⊨
 (induction rule: hoare2.induct)
 case (Skip P)
 show ?case unfolding hoare2_valid_def apply(safe)
 subgoal for s apply(rule exI[where x=s]) apply(rule exI[where x="Suc 0"])
 by (auto simp: eSuc_enat_iff eSuc_enat)
 done
 
 case (Assign P a x)
 show ?case unfolding hoare2_valid_def apply(safe)
 subgoal for s apply(rule exI[where x="s[a/x]"]) apply(rule exI[where x="Suc 0"])
 by (auto simp: eSuc_enat_iff eSuc_enat)
 done
 
 case (Seq P1 C1 P2 C2 P3)
 thus ?case using Seq_sound by auto
 
 case (If P b c1 Q c2)
 show ?case unfolding hoare2_valid_def
 proof (safe)
 fix s
 assume "eSuc (P s) < \∞"
 then have i: "P s < \∞"
 using enat_ord_simps(4) by fastforce
 show "∃t p. (IF b THEN c1 ELSE c2, tlef>?R¬
 proof(cases "bval b s")
 case True
 with i have "P s + emb (bval b s) < \∞" by simp
 with If(3)[unfolded hoare2_valid_def] obtain p t
 where 1: "(c1, s) ==> p ⇓ t" and q: "enat p + Q t ≤ P s + emb (bval b s)" by blast
 from Big_StepT.IfTrue[OF True 1] have 2: "(IF b THEN c1 ELSE c2, s) ==> p + 1 ⇓ t" by simp
 show ?thesis apply(rule exI[where x=t]) apply(rule exI[where x="p+1"])
 apply(safe) apply(fact)
 using q True apply(simp)
 by (metis eSuc_enat eSuc_ile_mono iadd_Suc)
 next
 case False
 with i have "P s + emb (~ bval b s) < \∞" by simp
 with If(4)[unfolded hoare2_valid_def] obtain p t
 where 1: "(c2, s) ==> AOT_hence ‹
 from Big_StepT.IfFalse[OF False 1] have 2: "(IF b THEN c1 ELSE c2, s) ==> p + 1 ⇓ t" by simp
 show ?thesis apply(rule exI[where x=t]) apply(rule exI[where x="p+1"])
 apply(safe) apply(fact)
 using q False apply(simp)
 by (metis eSuc_enat eSuc_ile_mono iadd_Suc)
 qed
 qed
 
 case (conseq P c Q P' Q')
 show ?case unfolding hoare2_valid_def
 proof (safe)
 fix s
 assume "P' s < \∞"
 with conseq(2) have "P s < \∞"
 using le_less_trans by blast
 with conseq(4)[unfolded hoare2_valid_def] obtain p t where "(c, s) ==> p ⇓ t" "enat p + Q t ≤ P s" by blast
 with conseq(2,3) show "∃t p. (c, s) ==> p ⇓ t ∧ enat p + Q' t ≤ P' s"
 by (meson add_left_mono dual_order.trans)
 qed
 
 case (While INV b c)
 
 from While(2)[unfolded hoare2_valid_def]
 have WH2: "∧s. INV s + ↑ (bval b s) < \∞ ==> (∃>🚫
 by (simp add: add.commute add.left_commute)
 
 show ?case unfolding hoare2_valid_def
 proof (safe)
 fix s
 assume ninfINV: "INV s + 1 < \∞"
 then have "INV s < \∞"
 using enat_ord_simps(4) by fastforce
 then obtain n where i: "INV s = enat n" using not_infinity_eq
 by auto
 
 text ‹In order to prove validity, we induct on the value of the Invariant, which is a finite number
 and decreases in every loop iteration. For each step we show that validity holds.›
 have "INV s = enat n ==> \>=🚫
 proof (induct n arbitrary: s rule: less_induct)
 case (less n)
 show ?case
 proof (cases "bval b s")
 case False
 show ?thesis
 using WhileFalse[OF False] one_enat_def by fastforce
 next
 case True
 ― ‹obtain the loop body from the outer IH›
 with less(2) WH2 obtain t p
 where o: "(c, s) ==> p ⇓ t"
 and q: "enat p + INV t + 1 ≤ INV s " by force

 ― ‹
 from q have g: "INV t < INV s"
 using help2 less(2) by metis
 then have ninfINVt: "INV t < \∞" using less(2)
 using enat_ord_simps(4) by fastforce
 then obtain n' where i: "INV t = enat n'" using not_infinity_eq
 by auto
 with less(2) have ii: "n' < n"
 using g by auto
 ― ‹by (met"&E"(1)"\orE"2) 🚫
 from i ii less(1) obtain t2 p2
 where o2: "(WHILE b DO c, t) ==> p2 ⇓ t2"
 and q2: "enat p2 + (INV t2 + emb (¬ bval b t2)) ≤ INV t + 1" by blast
 have ende: "~ bval b t2"
 apply(rule ccontr) apply(simp) using q2 ninfINVt
 by (simp add: i one_enat_def)
 
 ― ‹combine body and tail to one loop unrolling:›
 ― ‹- the Bigstep Semantic›
 from WhileTrue[OF True o o2] have BigStep: "(WHILE b DO c, s) ==> 1 + p + p2 ⇓ t2" by simp

 ― ‹- the potentialPreservation›
 from ende q2 have q2': "enat p2 + INV t2 ≤ INV t + 1" by simp
 
 have potentialPreservation: "enat (1 + p + p2) + (INV t2 + ↑ (¬ bval b t2)) ≤ INV s + qed
 proof -
 have "enat (1 + p + p2) + (INV t2 + ↑ (¬ bval b t2))
 = enat (Suc (p + p2)) + INV t2" using ende by simp
 also have "… = enat (Suc p) + enat p2 + INV t2" by fastforce
 also have "… ≤ enat (Suc p) + INV t + 1" using q2'
 by (metis ab_semigroup_add_class.add_ac(1) add_left_mono)
 also have "… ≤ INV s + 1" using q
 by (metis (no_types, opaque_lifting) add.commute add_left_mono eSuc_enat iadd_Suc plus_1_eSuc(1))
 finally show "enat (1 + p + p2) + (INV t2 + ↑ (¬ bval b t2)) ≤ INV s + 1" .
 qed
 
 ― ‹finally combine BigStep Semantic and TimeBound›
 show ?thesis
 apply(rule exI[where x=t2])
 apply(rule exI[where x= "1 + p + p2"])
 apply(safe)
 by(fact BigStep potentialPreservation)+
 qed
 qed
 from this[OF i] show "∃t p. (WHILE b DO c, s) ==> p ⇓ t ∧ enat p + (INV t + emb (¬ bval b t)) ≤ INV s + 1" .
 qed
 



 
  "Completeness"
 
 
(* the WeakestPrePotential  *)  
definition wp2 :: "com ==> qassn ==> qassn" (‹wp₂›) where
"wp₂ c Q = (λs. (if (∃t p. (c,s) ==> p ⇓ t ∧ Q t < ∞) then enat (THE p. ∃t. (c,s) ==> p ⇓ t) + Q (THE t. \<      using

lemma wp2_alt: "wp₂ c Q = (λs. (if ↓(c,s) then enat (↓ next
  apply(rule ext) by(auto simp: bigstepT_the_state wp2_def split: if_split)    
    

theorem wp2_is_weakestprePotential: "⊨₂ {P}c{Q} ⟷ (∀s. wp₂ c Q s ≤ P s)" 
  unfolding  wp2_def hoare2_valid_def
  apply(rule)
  subgoal 
    apply(safe) subgoal for s
      apply(cases "∃t p. (c, s) ==> p ⇓ t ∧ Q t < ∞")
        apply(simp) apply auto oops
  
  
lemma wp2_Skip[simp]: "wp₂ SKIP Q = (%s. eSuc (Q s))"
  apply(auto intro!: ext simp: wp2_def)
   prefer 2
   apply(simp only: SKIPnot)
   apply(simp)
  apply(simp only: SKIPp SKIPt)
  using one_enat_def plus_1_eSuc(1) by auto    

lemma wp2_Assign[simp]: "wp₂ (x ::= e) Q = (λs. eSuc (Q (s(x := aval e s))))"
by (auto intro!: ext simp: wp2_def ASSp ASSt ASSnot eSuc_enat) 

   
  
lemma wp2_Seq[simp]: "wp₂ (c₁;;c₂) Q = wp₂ c₁ (wp_fix s
unfolding wp2_def (* what rule is doing: it uses the extensionality (ext) of functions *)
proof (rule, case_tac "∃t p. (c₁;; c₂, s) ==> p ⇓ t ∧ Q t < ∞", goal_cases)
  case (1 s)
  then obtain u p where ter: "(c₁;; c₂, s) ==> p ⇓ u" and Q: "Q u < ∞" by blast
  then obtain t p1 p2 where i: "(c_Gs:🚫

  from bigstepT_the_state[OF i] have t: "↓_s (c₁, s) = t"  
    by blast
  from bigstepT_the_state[OF ii] have t2: java.lang.NullPointerException
    by blast
  from bigstepT_the_cost[OF i] have firstcost: "↓_t (c₁, s) = p1"
    by blast
  from bigstepT_the_cost[OF ii] have secondcost: "↓_t (c₂, t) = p2"
    by blast
  
  have totalcost: "↓_t(c₁;; c₂, s) = p1 + p2"
    using bigstepT_the_cost[OF ter] p by auto
  have totalstate: "↓_s(cjava.lang.NullPointerException
    using bigstepT_the_state[OF ter] by auto
  
  have c2: "∃ta p. (c₂, t) ==> p ⇓ ta ∧ Q ta < ∞"
    apply(rule exI[where x= u])
    apply(rule exI[where x= p2]) apply safe apply fact+ done
  
  
  have C: "∃t p. (c₁, s) ==>A not_s_eq_v ‹
    apply(rule exI[where x=t])
    apply(rule exI[where x=p1])
    apply safe
     apply fact
    apply(simp only: c2 if_True)
    using Q bigstepT_the_state ii by auto
   
  show ?case
    apply(simp only: 1 if_True t t2 c2 C totalcost totalstate firstcost secondcost) by fastforce
next
  case (2 s)
  show ?case apply(simp only: 2 if_False)
    apply auto using 2
    by force
qed
   

lemma wp2_If[simp]:
 " ₂ (IF b THEN c₁ ELSE c₂) Q = (λs. eSuc (wp₂ (if bval b s then c₁ else c₂) Q s))"
 apply (auto simp: wp2_def fun_eq_iff)
 subgoal for x t p i ta ia xa apply(simp only: IfTrue[THEN bigstepT_the_state])
 apply(simp only: IfTrue[THEN bigstepT_the_cos])
 apply(simp only: bigstepT_the_cost bigstepT_the_state)
 by (simp add: eSuc_enat)
 apply(simp only: bigstepT_the_state bigstepT_the_cost) apply force
 apply(simp only: bigstepT_the_state bigstepT_the_cost)
 (goal_cases)
 case (1 x t p i ta ia xa)
 note f= IfFalse[THEN bigstepT_the_state, of b x c₂ xa ta "Suc xa" c₁, simplified, OF 1(4) 1(5)]
 note f2= IfFalse[THEN bigstepT_the_cost, of b x c₂ xa ta "Suc xa" c₁, simplified, OF 1(4) 1(5)]
 note g= bigstep_det[OF 1(1) 1(5)]
 show ?case
 apply(simp only: f f2) using 1 g
 by (simp add: eSuc_enat)
 
 case 2
 then
 show ?case
 apply(simp only: bigstepT_the_state bigstepT_the_cost) apply force done
 
 

  assumes b: "bval b s"
 shows wp2WhileTrue: " wp₂ c (wp₂ (WHILE b DO c) Q) s + 1 ≤ wp₂ (WHILE b DO c) Q s"
  (cases "\<existst⇓"
 case True
 then obtain t p where w: "(WHILE b DO c, s) ==> p ⇓ t" and q: "Q t < \∞" by blast
 from b w obtain p1 p2 t1 where c: "(c, s) ==> p1 ⇓ t1" and w': "(WHILE b DO c, t1) ==> p2 ⇓ t" and sum: "1 + p1 + p2 = p"
 by auto
 have g: "∃ta p. (WHILE b DO c, t1) ==> p ⇓ ta ∧ Q ta < \∞"
 apply(rule exI[where x="t"])
 apply(rule exI[where x="p2"])
 apply safe apply fact+ done
 
 have h: "∃t p. (c, s) ==> p ⇓ t ∧ (if ∃ta p. (WHILE b DO c, t) ==> p ⇓ ta ∧ Q ta < \∞ then enat (THE p. Ex (big_step_t (WHILE b DO c, t) p)) + Q (THE ta. ∃p. (WHILE b DO c, t) ==> p ⇓ ta) else ∞) < \∞"
 apply(rule exI[where x="t1"])
 apply(rule exI[where x="p1"])
 apply safe apply fact
 apply(simp only: g if_True) using bigstepT_the_state bigstepT_the_cost w' q by(auto)
 
 have "wp₂ c (wp₂ (WHILE b DO c) Q) s + 1 = enat p + Q t"
 unfolding wp2_def apply(simp only: h if_True)
 apply(simp only: bigstepT_the_state[OF c] bigstepT_the_cost[OF c] g if_True bigstepT_the_state[OF w'] bigstepT_the_cost[OF w']) using sum
 by (metis One_nat_def ab_semigroup_add_class.add_ac(1) add.commute add.right_neutral eSuc_enat plus_1_eSuc(2) plus_enat_simps(1))
 also have "… = wp₂ (WHILE b DO c) Q s"
 unfolding wp2_def apply(simp only: True if_True)
 using bigstepT_the_state bigstepT_the_cost w apply(simp) done
 finally show ?thesis by simp
 
 case False
 have "wp₂ (WHILE b DO c) Q s = ∞"
 unfolding wp2_def
 apply(simp only: False if_False) done
 then show ?thesis by auto
 

  assumes b: "bval b s"
  wp2WhileTrue': "wp₂ c (wp₂ (WHILE b DO c) Q) s + 1 = wp₂ (WHILE b DO c) Q s"
  (cases "∃κbet>←I" Gs s_noteq_v)
 case True
 then obtain t p where w: "(WHILE b DO c, s) ==> p ⇓ t" by blast
 from b w obtain p1 p2 t1 where c: "(c, s) ==> p1 ⇓ t1" and w': "(WHILE b DO c, t1) ==> p2 ⇓ t" and sum: "1 + p1 + p2 = p"
 by auto
 then have z: "↓ (c, s)" and z2: "↓ (WHILE b DO c, t1)" by auto
 
 have "wp₂ c (wp₂ (WHILE b DO c) Q) s + 1 = enat p + Q t"
 unfolding wp2_alt apply(simp only: z if_True)
 apply(simp only: bigstepT_the_state[OF c] bigstepT_the_cost[OF c] z2 if_True bigstepT_the_state[OF w'] bigstepT_the_cost[OF w'])
 using sum
 by (metis One_nat_def ab_semigroup_add_class.add_ac(1) add.commute add.right_neutral eSuc_enat plus_1_eSuc(2) plus_enat_simps(1))
 also have "… = wp₂ (WHILE b DO c) Q s"
 unfolding wp2_alt apply(simp only: True if_True)
 using bigstepT_the_state bigstepT_the_cost w apply(simp) done
 finally show ?thesis by simp
 
 case False
 have "¬ (↓ (WHILE b DO c, ↓_s(c,s)) ∧ ↓ (c, s))"
 proof (rule)
 assume P: "↓ (WHILE b DO c, ↓_s (c, s)) ∧ ↓ (c, s)"
 then obtain t s' where A: "(cs) ==>
 with A P have "↓ (WHILE b DO c, s')" using bigstepT_the_state by auto
 then obtain t' s'' where B: "(WHILE b DO c,s') ==> t' ⇓ s''" by auto
 have "(WHILE b DO c, s) ==> 1+t+t' ⇓ s''" apply(rule WhileTrue) using b A B by auto
 then have "↓ (WHILE b DO c, s)" by auto
 thus "False" using False by auto
 qed
 then have "¬↓ (WHILE b DO c, ↓_s(c,s)) ∨ ¬↓ (c, s)" by simp
 
 then show ?thesis apply rule
 subgoal unfolding wp2_alt apply(simp only: if_False False) by auto
 subgoal unfolding wp2_alt apply(simp only: if_False False) by auto
 done
 
 
 
  assumes b: "~ bval b s"
 shows wp2WhileFalse: " Q s + 1 ≤ wp₂ (WHILE b DO c) Q s"
  (cases "∃t p. (WHILE b DO c, s) ==> p ⇓ t ∧ Q t < \∞")
 case True
 with b obtain t p where w: "(WHILE b DO c, s) ==> p ⇓ t" and "Q t < \∞" by blast
 with b have c: "s=t" "p=Suc 0" by auto
 have " wp₂ (WHILE b DO c) Q s = Q s + 1"
 unfolding wp2_def apply(simp only: True if_True)
 using w c bigstepT_the_cost bigstepT_the_state by(auto simp add: one_enat_def)
 then show ?thesis by auto
 
 case False
 have "wp₂ (WHILE b DO c) Q s = ∞"
 unfolding wp2_def
 apply(simp only: False if_False) done
 then show ?thesis by auto
 
 
  thet_WhileFalse: "~ bval b s ==> ↓_t (WHILE b DO c, s) = 1" by auto
  thes_WhileFalse: "~ bval b s ==> ↓_s (WHILE b DO c, s) = s" by auto
 
  assumes b: "~ bval b s"
 shows wp2WhileFalse': "Q s + 1 = wp₂ (WHILE b DO c) Q s"
  -
 from b have T: "↓ (WHILE b DO c, s)" by auto
 show ?thesis unfolding wp2_a using b apppply(s(simp only: T if_Tru
 by(simp add: thet_WhileFalse thes_WhileFalse one_enat_def)
 
 
 
(* note that \<le> is sufficient for the completness proof *)
lemma wp2While: "(if bval b s then wp₂ c (wp₂ (WHILE b DO c) Q) s else Q s) + 1 = wp₂ (WHILE b DO c) Q s"  
  apply(cases "bval b s")      
  using wp2WhileTrue' apply simp
  using wp2WhileFalse' apply simp   done 
    
 
  
lemma assumes "∧Q. ⊨₂ {wp₂ c Q} c {Q}"
  shows  "⊨₂ {wp₂ (WHILE b DO c) Q} WHILE b DO c {Q}"
proof -
  let ?I = "%s. (if bval b s then wp₂ c (wp₂ (WHILE b DO c) Q) s else Q s)"
  from assms[of       AOT_hence ∃]& []rs∀sup [Rts  =<^> r))›
  have A: " ⊨₂ {wp₂ c (wp₂ (WHILE b DO c) Q)} c {wp₂ (WHILE b DO c) Q}" .
  have B: "⊨₂ {λs. (?I s) + ↑ (bval b s)} c {λt. (?I t) + 1}"
    apply(rule conseq)
      apply(rule A)
     apply simp
      using wp2While apply simp done
  from hoare2.While[where I="?I"]
  have C: "⊨₂ {λs. (?I s) + ↑ (bval b s)} c {λt. (?I t) + 1} ==>
          ⊨₂ {λs. (?I s) + 1} WHILE b DO c {λs. (?I s) + ↑ (¬ bval b s)}" by simp
  from C[OF B] have D: "⊨₂ {λs. (?I s) + 1} WHILE b DO c {λs. (?I s) + ↑ (¬ bval b s)}" .                           
  show "⊨₂ {wp₂ (WHILE b DO c) Q} WHILE b DO c {Q}"
    apply(rule conseq)
      apply(rule D)
    using wp2While apply simp
      apply simp  done
qed
                            

lemma wp2_is_pre: "⊨₂ {wp₂ c Q} c { Q}"
proof (induction c arbitrary: Q)
  case SKIP show ?case by (auto intro: hoare2.Skip)
next
  case Assign show ?case by (auto intro:hoare2.Assign)
next
  case Seq thus ?case by (auto intro:hoare2.Seq)
next 
  case (If x1 c1 c2 Q) thus ?case
    apply (auto intro!: hoare2.If )  
     apply(rule hoare2.conseq) 
       apply(auto)
     apply(rule hoare2.conseq) 
      apply(auto)
    done
next
  case (While b c)   
  show ?case
    apply(rule conseq)       
      apply(rule hoare2.While[where I="%s. (if bval b s then wp₂ c (wp₂ (WHILE b DO c) Q) s else Q s)"])       
      apply(rule conseq)        
        apply(rule While[of "wp₂ (WHILE b DO c) Q"])      
    using wp2While by auto       
qed
  
  
  
lemma wp2_is_weakestprePotential1: "⊨₂ {P}c{Q} ==> (∀s. wp_: \<<open
apply(auto simp: hoare2_valid_def wp2_def)
proof (goal_cases)
  case (1 s t p i)
  show ?case
  proof(cases "P s < ∞")
    case True
    with 1(1) obtain t p' where i: "(c, s) ==> p' ⇓ t" and ii: "enat p' + Q t ≤ P s"
      by auto
    show ?thesis apply(simp add: bigstepT_the_state[OF i] bigstepT_the_cost[OF i] ii) done
  qed simp
qed force
  
lemma wp2_is_weakestprePotential2: "(∀s. wp₂ c Q s ≤ P s) ==> ⊨₂ {P}c{Q}"
apply(auto simp: hoare2_valid_def wp2_def)
proof (goal_cases)
  case (1 s i)
  then have A: "(if ∃t. (∃p. (c, s) ==> p ⇓ t) ∧ (∃i. Q t = enat i) then enat (THE p. Ex (big_step_t (c, s) p)) + Q (THE t. ∃p. (c, s) ==> p ⇓ t) else ∞) ≤ P s"
    by fast
  show ?case
  proof (cases "∃t. (∃p. (c, s) ==> p ⇓ t) ∧ (∃i. Q t = enat i)")
    case True
    then obtain t p where i: "(c, s) ==> p ⇓ t" by blast
    from True A have " "enat p + Q t \le P s s"by(simp bigstepT_the_cost] bigstepT_the_statei)
    then have "(c, s) ==> p ⇓ t ∧ enat p + Q t ≤ enat i" using 1(2) i by simp
    then show ?thesis by auto
  next
    case False
    with A have "P s ≥ ∞" by auto 
    then show ?thesis using 1 by auto
  qed   
qed
          
theorem wp2_is_weakestprePotential: "(∀s. wp₂ c Q s ≤ P s) ⟷ ⊨₂ {P}c{Q}" 
 using  wp2_is_weakestprePotential1

   
   
theorem hoare2_complete: "⊨₂ {P}c{Q} ==> ⊨₂ {P}c{ Q}"  
apply(rule conseq[OF wp2_is_pre, where Q'=Q and Q=Q, simplified]) 
using wp2_is_weakestprePotential1 by blast

 


corollary hoare2_sound_complete: " ⊨₂ {P}c{Q} ⟷ ⊨₂ {P}c{ Q}"
by (metis hoare2_sound hoare2_complete)



end