(* Title: HOL/MicroJava/BV/EffectMono.thy Author: Gerwin Klein Copyright 2000 Technische Universitaet Muenchen *) header {* \isaheader{Monotonicity of eff and app} *} theory EffectMono imports Effect begin lemma PrimT_PrimT: "(G \<turnstile> xb \<preceq> PrimT p) = (xb = PrimT p)" by (auto elim: widen.cases) lemma sup_loc_some [rule_format]: "∀y n. (G \<turnstile> b <=l y) --> n < length y --> y!n = OK t --> (∃t. b!n = OK t ∧ (G \<turnstile> (b!n) <=o (y!n)))" proof (induct b) case Nil show ?case by simp next case (Cons a list) show ?case proof (clarsimp simp add: list_all2_Cons1 sup_loc_def Listn.le_def lesub_def) fix z zs n assume *: "G \<turnstile> a <=o z" "list_all2 (sup_ty_opt G) list zs" "n < Suc (length list)" "(z # zs) ! n = OK t" show "(∃t. (a # list) ! n = OK t) ∧ G \<turnstile>(a # list) ! n <=o OK t" proof (cases n) case 0 with * show ?thesis by (simp add: sup_ty_opt_OK) next case Suc with Cons * show ?thesis by (simp add: sup_loc_def Listn.le_def lesub_def) qed qed qed lemma all_widen_is_sup_loc: "∀b. length a = length b --> (∀(x, y)∈set (zip a b). G \<turnstile> x \<preceq> y) = (G \<turnstile> (map OK a) <=l (map OK b))" (is "∀b. length a = length b --> ?Q a b" is "?P a") proof (induct "a") show "?P []" by simp fix l ls assume Cons: "?P ls" show "?P (l#ls)" proof (intro allI impI) fix b assume "length (l # ls) = length (b::ty list)" with Cons show "?Q (l # ls) b" by - (cases b, auto) qed qed lemma append_length_n [rule_format]: "∀n. n ≤ length x --> (∃a b. x = a@b ∧ length a = n)" proof (induct x) case Nil show ?case by simp next case (Cons l ls) show ?case proof (intro allI impI) fix n assume l: "n ≤ length (l # ls)" show "∃a b. l # ls = a @ b ∧ length a = n" proof (cases n) assume "n=0" thus ?thesis by simp next fix n' assume s: "n = Suc n'" with l have "n' ≤ length ls" by simp hence "∃a b. ls = a @ b ∧ length a = n'" by (rule Cons [rule_format]) then obtain a b where "ls = a @ b" "length a = n'" by iprover with s have "l # ls = (l#a) @ b ∧ length (l#a) = n" by simp thus ?thesis by blast qed qed qed lemma rev_append_cons: "n < length x ==> ∃a b c. x = (rev a) @ b # c ∧ length a = n" proof - assume n: "n < length x" hence "n ≤ length x" by simp hence "∃a b. x = a @ b ∧ length a = n" by (rule append_length_n) then obtain r d where x: "x = r@d" "length r = n" by iprover with n have "∃b c. d = b#c" by (simp add: neq_Nil_conv) then obtain b c where "d = b#c" by iprover with x have "x = (rev (rev r)) @ b # c ∧ length (rev r) = n" by simp thus ?thesis by blast qed lemma sup_loc_length_map: "G \<turnstile> map f a <=l map g b ==> length a = length b" proof - assume "G \<turnstile> map f a <=l map g b" hence "length (map f a) = length (map g b)" by (rule sup_loc_length) thus ?thesis by simp qed lemmas [iff] = not_Err_eq lemma app_mono: "[|G \<turnstile> s <=' s'; app i G m rT pc et s'|] ==> app i G m rT pc et s" proof - { fix s1 s2 assume G: "G \<turnstile> s2 <=s s1" assume app: "app i G m rT pc et (Some s1)" note [simp] = sup_loc_length sup_loc_length_map have "app i G m rT pc et (Some s2)" proof (cases i) case Load from G Load app have "G \<turnstile> snd s2 <=l snd s1" by (auto simp add: sup_state_conv) with G Load app show ?thesis by (cases s2) (auto simp add: sup_state_conv dest: sup_loc_some) next case Store with G app show ?thesis by (cases s2) (auto simp add: sup_loc_Cons2 sup_state_conv) next case LitPush with G app show ?thesis by (cases s2) (auto simp add: sup_state_conv) next case New with G app show ?thesis by (cases s2) (auto simp add: sup_state_conv) next case Getfield with app G show ?thesis by (cases s2) (clarsimp simp add: sup_state_Cons2, rule widen_trans) next case (Putfield vname cname) with app obtain vT oT ST LT b where s1: "s1 = (vT # oT # ST, LT)" and "field (G, cname) vname = Some (cname, b)" "is_class G cname" and oT: "G\<turnstile> oT\<preceq> (Class cname)" and vT: "G\<turnstile> vT\<preceq> b" and xc: "Ball (set (match G NullPointer pc et)) (is_class G)" by force moreover from s1 G obtain vT' oT' ST' LT' where s2: "s2 = (vT' # oT' # ST', LT')" and oT': "G\<turnstile> oT' \<preceq> oT" and vT': "G\<turnstile> vT' \<preceq> vT" by - (cases s2, simp add: sup_state_Cons2, elim exE conjE, simp) moreover from vT' vT have "G \<turnstile> vT' \<preceq> b" by (rule widen_trans) moreover from oT' oT have "G\<turnstile> oT' \<preceq> (Class cname)" by (rule widen_trans) ultimately show ?thesis by (auto simp add: Putfield xc) next case Checkcast with app G show ?thesis by (cases s2) (auto intro!: widen_RefT2 simp add: sup_state_Cons2) next case Return with app G show ?thesis by (cases s2) (auto simp add: sup_state_Cons2, rule widen_trans) next case Pop with app G show ?thesis by (cases s2) (clarsimp simp add: sup_state_Cons2) next case Dup with app G show ?thesis by (cases s2) (clarsimp simp add: sup_state_Cons2, auto dest: sup_state_length) next case Dup_x1 with app G show ?thesis by (cases s2) (clarsimp simp add: sup_state_Cons2, auto dest: sup_state_length) next case Dup_x2 with app G show ?thesis by (cases s2) (clarsimp simp add: sup_state_Cons2, auto dest: sup_state_length) next case Swap with app G show ?thesis by (cases s2) (auto simp add: sup_state_Cons2) next case IAdd with app G show ?thesis by (cases s2) (auto simp add: sup_state_Cons2 PrimT_PrimT) next case Goto with app show ?thesis by simp next case Ifcmpeq with app G show ?thesis by (cases s2) (auto simp add: sup_state_Cons2 PrimT_PrimT widen_RefT2) next case (Invoke cname mname list) with app obtain apTs X ST LT mD' rT' b' where s1: "s1 = (rev apTs @ X # ST, LT)" and l: "length apTs = length list" and c: "is_class G cname" and C: "G \<turnstile> X \<preceq> Class cname" and w: "∀(x, y) ∈ set (zip apTs list). G \<turnstile> x \<preceq> y" and m: "method (G, cname) (mname, list) = Some (mD', rT', b')" and x: "∀C ∈ set (match_any G pc et). is_class G C" by (simp del: not_None_eq, elim exE conjE) (rule that) obtain apTs' X' ST' LT' where s2: "s2 = (rev apTs' @ X' # ST', LT')" and l': "length apTs' = length list" proof - from l s1 G have "length list < length (fst s2)" by simp hence "∃a b c. (fst s2) = rev a @ b # c ∧ length a = length list" by (rule rev_append_cons [rule_format]) thus ?thesis by (cases s2) (elim exE conjE, simp, rule that) qed from l l' have "length (rev apTs') = length (rev apTs)" by simp from this s1 s2 G obtain G': "G \<turnstile> (apTs',LT') <=s (apTs,LT)" and X : "G \<turnstile> X' \<preceq> X" and "G \<turnstile> (ST',LT') <=s (ST,LT)" by (simp add: sup_state_rev_fst sup_state_append_fst sup_state_Cons1) with C have C': "G \<turnstile> X' \<preceq> Class cname" by - (rule widen_trans, auto) from G' have "G \<turnstile> map OK apTs' <=l map OK apTs" by (simp add: sup_state_conv) also from l w have "G \<turnstile> map OK apTs <=l map OK list" by (simp add: all_widen_is_sup_loc) finally have "G \<turnstile> map OK apTs' <=l map OK list" . with l' have w': "∀(x, y) ∈ set (zip apTs' list). G \<turnstile> x \<preceq> y" by (simp add: all_widen_is_sup_loc) from Invoke s2 l' w' C' m c x show ?thesis by (simp del: split_paired_Ex) blast next case Throw with app G show ?thesis by (cases s2, clarsimp simp add: sup_state_Cons2 widen_RefT2) qed } note this [simp] assume "G \<turnstile> s <=' s'" "app i G m rT pc et s'" thus ?thesis by (cases s, cases s', auto) qed lemmas [simp del] = split_paired_Ex lemma eff'_mono: "[| app i G m rT pc et (Some s2); G \<turnstile> s1 <=s s2 |] ==> G \<turnstile> eff' (i,G,s1) <=s eff' (i,G,s2)" proof (cases s1, cases s2) fix a1 b1 a2 b2 assume s: "s1 = (a1,b1)" "s2 = (a2,b2)" assume app2: "app i G m rT pc et (Some s2)" assume G: "G \<turnstile> s1 <=s s2" note [simp] = eff_def with G have "G \<turnstile> (Some s1) <=' (Some s2)" by simp from this app2 have app1: "app i G m rT pc et (Some s1)" by (rule app_mono) show ?thesis proof (cases i) case (Load n) with s app1 obtain y where y: "n < length b1" "b1 ! n = OK y" by clarsimp from Load s app2 obtain y' where y': "n < length b2" "b2 ! n = OK y'" by clarsimp from G s have "G \<turnstile> b1 <=l b2" by (simp add: sup_state_conv) with y y' have "G \<turnstile> y \<preceq> y'" by - (drule sup_loc_some, simp+) with Load G y y' s app1 app2 show ?thesis by (clarsimp simp add: sup_state_conv) next case Store with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_conv sup_loc_update) next case LitPush with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case New with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case Getfield with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case Putfield with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case Checkcast with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case (Invoke cname mname list) with s app1 obtain a X ST where s1: "s1 = (a @ X # ST, b1)" and l: "length a = length list" by (simp, elim exE conjE, simp (no_asm_simp)) from Invoke s app2 obtain a' X' ST' where s2: "s2 = (a' @ X' # ST', b2)" and l': "length a' = length list" by (simp, elim exE conjE, simp (no_asm_simp)) from l l' have lr: "length a = length a'" by simp from lr G s1 s2 have "G \<turnstile> (ST, b1) <=s (ST', b2)" by (simp add: sup_state_append_fst sup_state_Cons1) moreover obtain b1' b2' where eff': "b1' = snd (eff' (i,G,s1))" "b2' = snd (eff' (i,G,s2))" by simp from Invoke G s eff' app1 app2 obtain "b1 = b1'" "b2 = b2'" by simp ultimately have "G \<turnstile> (ST, b1') <=s (ST', b2')" by simp with Invoke G s app1 app2 eff' s1 s2 l l' show ?thesis by (clarsimp simp add: sup_state_conv) next case Return with G show ?thesis by simp next case Pop with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case Dup with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case Dup_x1 with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case Dup_x2 with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case Swap with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case IAdd with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case Goto with G s app1 app2 show ?thesis by simp next case Ifcmpeq with G s app1 app2 show ?thesis by (clarsimp simp add: sup_state_Cons1) next case Throw with G show ?thesis by simp qed qed lemmas [iff del] = not_Err_eq end