Theory Equiv

(*  Title:      ZF/IMP/Equiv.thy
    Author:     Heiko Loetzbeyer and Robert Sandner, TU München
*)

section ‹Equivalence›

theory Equiv imports Denotation Com begin

lemma aexp_iff [rule_format]:
  "⟦a ∈ aexp; sigma: loc -> nat⟧ 
    ⟹ ∀n. ⟨a,sigma⟩ -a-> n ⟷ A(a,sigma) = n"
  apply (erule aexp.induct)
     apply (force intro!: evala.intros)+
  done

declare aexp_iff [THEN iffD1, simp]
        aexp_iff [THEN iffD2, intro!]

inductive_cases [elim!]:
  "⟨true,sigma⟩ -b-> x"
  "⟨false,sigma⟩ -b-> x"
  "<ROp(f,a0,a1),sigma> -b-> x"
  "<noti(b),sigma> -b-> x"
  "<b0 andi b1,sigma> -b-> x"
  "<b0 ori b1,sigma> -b-> x"


lemma bexp_iff [rule_format]:
  "⟦b ∈ bexp; sigma: loc -> nat⟧ 
    ⟹ ∀w. ⟨b,sigma⟩ -b-> w ⟷ B(b,sigma) = w"
  apply (erule bexp.induct) 
  apply (auto intro!: evalb.intros)
  done

declare bexp_iff [THEN iffD1, simp]
        bexp_iff [THEN iffD2, intro!]

lemma com1: "⟨c,sigma⟩ -c-> sigma' ⟹ <sigma,sigma'> ∈ C(c)"
  apply (erule evalc.induct)
        apply (simp_all (no_asm_simp))
     txt ‹‹assign››
     apply (simp add: update_type)
    txt ‹‹comp››
    apply fast
   txt ‹‹while››
   apply (erule Gamma_bnd_mono [THEN lfp_unfold, THEN ssubst, OF C_subset])
   apply (simp add: Gamma_def)
  txt ‹recursive case of ‹while››
  apply (erule Gamma_bnd_mono [THEN lfp_unfold, THEN ssubst, OF C_subset])
  apply (auto simp add: Gamma_def)
  done

declare B_type [intro!] A_type [intro!]
declare evalc.intros [intro]


lemma com2 [rule_format]: "c ∈ com ⟹ ∀x ∈ C(c). <c,fst(x)> -c-> snd(x)"
  apply (erule com.induct)
      txt ‹‹skip››
      apply force
     txt ‹‹assign››
     apply force
    txt ‹‹comp››
    apply force
   txt ‹‹while››
   apply safe
   apply simp_all
   apply (frule Gamma_bnd_mono [OF C_subset], erule Fixedpt.induct, assumption)
     unfolding Gamma_def
   apply force
  txt ‹‹if››
  apply auto
  done


subsection ‹Main theorem›

theorem com_equivalence:
    "c ∈ com ⟹ C(c) = {io ∈ (loc->nat) × (loc->nat). <c,fst(io)> -c-> snd(io)}"
  by (force intro: C_subset [THEN subsetD] elim: com2 dest: com1)

end