64 show ?case using t12 t23 s3t3 by auto |
64 show ?case using t12 t23 s3t3 by auto |
65 next |
65 next |
66 case (IfTrue b s c1 s' c2) |
66 case (IfTrue b s c1 s' c2) |
67 hence "s = t on vars b" "s = t on L c1 X" by auto |
67 hence "s = t on vars b" "s = t on L c1 X" by auto |
68 from bval_eq_if_eq_on_vars[OF this(1)] IfTrue(1) have "bval b t" by simp |
68 from bval_eq_if_eq_on_vars[OF this(1)] IfTrue(1) have "bval b t" by simp |
69 from IfTrue(3)[OF `s = t on L c1 X`] obtain t' where |
69 from IfTrue.IH[OF `s = t on L c1 X`] obtain t' where |
70 "(c1, t) \<Rightarrow> t'" "s' = t' on X" by auto |
70 "(c1, t) \<Rightarrow> t'" "s' = t' on X" by auto |
71 thus ?case using `bval b t` by auto |
71 thus ?case using `bval b t` by auto |
72 next |
72 next |
73 case (IfFalse b s c2 s' c1) |
73 case (IfFalse b s c2 s' c1) |
74 hence "s = t on vars b" "s = t on L c2 X" by auto |
74 hence "s = t on vars b" "s = t on L c2 X" by auto |
75 from bval_eq_if_eq_on_vars[OF this(1)] IfFalse(1) have "~bval b t" by simp |
75 from bval_eq_if_eq_on_vars[OF this(1)] IfFalse(1) have "~bval b t" by simp |
76 from IfFalse(3)[OF `s = t on L c2 X`] obtain t' where |
76 from IfFalse.IH[OF `s = t on L c2 X`] obtain t' where |
77 "(c2, t) \<Rightarrow> t'" "s' = t' on X" by auto |
77 "(c2, t) \<Rightarrow> t'" "s' = t' on X" by auto |
78 thus ?case using `~bval b t` by auto |
78 thus ?case using `~bval b t` by auto |
79 next |
79 next |
80 case (WhileFalse b s c) |
80 case (WhileFalse b s c) |
81 hence "~ bval b t" by (auto simp: ball_Un) (metis bval_eq_if_eq_on_vars) |
81 hence "~ bval b t" by (auto simp: ball_Un) (metis bval_eq_if_eq_on_vars) |
98 subsection "Program Optimization" |
98 subsection "Program Optimization" |
99 |
99 |
100 text{* Burying assignments to dead variables: *} |
100 text{* Burying assignments to dead variables: *} |
101 fun bury :: "com \<Rightarrow> vname set \<Rightarrow> com" where |
101 fun bury :: "com \<Rightarrow> vname set \<Rightarrow> com" where |
102 "bury SKIP X = SKIP" | |
102 "bury SKIP X = SKIP" | |
103 "bury (x ::= a) X = (if x:X then x::= a else SKIP)" | |
103 "bury (x ::= a) X = (if x \<in> X then x ::= a else SKIP)" | |
104 "bury (c\<^isub>1; c\<^isub>2) X = (bury c\<^isub>1 (L c\<^isub>2 X); bury c\<^isub>2 X)" | |
104 "bury (c\<^isub>1; c\<^isub>2) X = (bury c\<^isub>1 (L c\<^isub>2 X); bury c\<^isub>2 X)" | |
105 "bury (IF b THEN c\<^isub>1 ELSE c\<^isub>2) X = IF b THEN bury c\<^isub>1 X ELSE bury c\<^isub>2 X" | |
105 "bury (IF b THEN c\<^isub>1 ELSE c\<^isub>2) X = IF b THEN bury c\<^isub>1 X ELSE bury c\<^isub>2 X" | |
106 "bury (WHILE b DO c) X = WHILE b DO bury c (vars b \<union> X \<union> L c X)" |
106 "bury (WHILE b DO c) X = WHILE b DO bury c (vars b \<union> X \<union> L c X)" |
107 |
107 |
108 text{* We could prove the analogous lemma to @{thm[source]L_sound}, and the |
108 text{* We could prove the analogous lemma to @{thm[source]L_sound}, and the |
128 show ?case using t12 t23 s3t3 by auto |
128 show ?case using t12 t23 s3t3 by auto |
129 next |
129 next |
130 case (IfTrue b s c1 s' c2) |
130 case (IfTrue b s c1 s' c2) |
131 hence "s = t on vars b" "s = t on L c1 X" by auto |
131 hence "s = t on vars b" "s = t on L c1 X" by auto |
132 from bval_eq_if_eq_on_vars[OF this(1)] IfTrue(1) have "bval b t" by simp |
132 from bval_eq_if_eq_on_vars[OF this(1)] IfTrue(1) have "bval b t" by simp |
133 from IfTrue(3)[OF `s = t on L c1 X`] obtain t' where |
133 from IfTrue.IH[OF `s = t on L c1 X`] obtain t' where |
134 "(bury c1 X, t) \<Rightarrow> t'" "s' =t' on X" by auto |
134 "(bury c1 X, t) \<Rightarrow> t'" "s' =t' on X" by auto |
135 thus ?case using `bval b t` by auto |
135 thus ?case using `bval b t` by auto |
136 next |
136 next |
137 case (IfFalse b s c2 s' c1) |
137 case (IfFalse b s c2 s' c1) |
138 hence "s = t on vars b" "s = t on L c2 X" by auto |
138 hence "s = t on vars b" "s = t on L c2 X" by auto |
139 from bval_eq_if_eq_on_vars[OF this(1)] IfFalse(1) have "~bval b t" by simp |
139 from bval_eq_if_eq_on_vars[OF this(1)] IfFalse(1) have "~bval b t" by simp |
140 from IfFalse(3)[OF `s = t on L c2 X`] obtain t' where |
140 from IfFalse.IH[OF `s = t on L c2 X`] obtain t' where |
141 "(bury c2 X, t) \<Rightarrow> t'" "s' = t' on X" by auto |
141 "(bury c2 X, t) \<Rightarrow> t'" "s' = t' on X" by auto |
142 thus ?case using `~bval b t` by auto |
142 thus ?case using `~bval b t` by auto |
143 next |
143 next |
144 case (WhileFalse b s c) |
144 case (WhileFalse b s c) |
145 hence "~ bval b t" by (auto simp: ball_Un) (metis bval_eq_if_eq_on_vars) |
145 hence "~ bval b t" by (auto simp: ball_Un) (metis bval_eq_if_eq_on_vars) |