equal
deleted
inserted
replaced
16 by(cases bv)(auto intro: small_step.IfTrue small_step.IfFalse) |
16 by(cases bv)(auto intro: small_step.IfTrue small_step.IfFalse) |
17 qed (fastforce intro: small_step.intros)+ |
17 qed (fastforce intro: small_step.intros)+ |
18 |
18 |
19 lemma D_mono: "D A c M \<Longrightarrow> A \<subseteq> A' \<Longrightarrow> EX M'. D A' c M' & M <= M'" |
19 lemma D_mono: "D A c M \<Longrightarrow> A \<subseteq> A' \<Longrightarrow> EX M'. D A' c M' & M <= M'" |
20 proof (induction c arbitrary: A A' M) |
20 proof (induction c arbitrary: A A' M) |
21 case Semi thus ?case by auto (metis D.intros(3)) |
21 case Seq thus ?case by auto (metis D.intros(3)) |
22 next |
22 next |
23 case (If b c1 c2) |
23 case (If b c1 c2) |
24 then obtain M1 M2 where "vars b \<subseteq> A" "D A c1 M1" "D A c2 M2" "M = M1 \<inter> M2" |
24 then obtain M1 M2 where "vars b \<subseteq> A" "D A c1 M1" "D A c2 M2" "M = M1 \<inter> M2" |
25 by auto |
25 by auto |
26 with If.IH `A \<subseteq> A'` obtain M1' M2' |
26 with If.IH `A \<subseteq> A'` obtain M1' M2' |
38 case (While b c s) |
38 case (While b c s) |
39 then obtain A' where "vars b \<subseteq> dom s" "A = dom s" "D (dom s) c A'" by blast |
39 then obtain A' where "vars b \<subseteq> dom s" "A = dom s" "D (dom s) c A'" by blast |
40 moreover |
40 moreover |
41 then obtain A'' where "D A' c A''" by (metis D_incr D_mono) |
41 then obtain A'' where "D A' c A''" by (metis D_incr D_mono) |
42 ultimately have "D (dom s) (IF b THEN c; WHILE b DO c ELSE SKIP) (dom s)" |
42 ultimately have "D (dom s) (IF b THEN c; WHILE b DO c ELSE SKIP) (dom s)" |
43 by (metis D.If[OF `vars b \<subseteq> dom s` D.Semi[OF `D (dom s) c A'` D.While[OF _ `D A' c A''`]] D.Skip] D_incr Int_absorb1 subset_trans) |
43 by (metis D.If[OF `vars b \<subseteq> dom s` D.Seq[OF `D (dom s) c A'` D.While[OF _ `D A' c A''`]] D.Skip] D_incr Int_absorb1 subset_trans) |
44 thus ?case by (metis D_incr `A = dom s`) |
44 thus ?case by (metis D_incr `A = dom s`) |
45 next |
45 next |
46 case Semi2 thus ?case by auto (metis D_mono D.intros(3)) |
46 case Seq2 thus ?case by auto (metis D_mono D.intros(3)) |
47 qed (auto intro: D.intros) |
47 qed (auto intro: D.intros) |
48 |
48 |
49 theorem D_sound: |
49 theorem D_sound: |
50 "(c,s) \<rightarrow>* (c',s') \<Longrightarrow> D (dom s) c A' \<Longrightarrow> c' \<noteq> SKIP |
50 "(c,s) \<rightarrow>* (c',s') \<Longrightarrow> D (dom s) c A' \<Longrightarrow> c' \<noteq> SKIP |
51 \<Longrightarrow> \<exists>cs''. (c',s') \<rightarrow> cs''" |
51 \<Longrightarrow> \<exists>cs''. (c',s') \<rightarrow> cs''" |