44 using L_While_unfold by blast |
44 using L_While_unfold by blast |
45 |
45 |
46 lemma L_While_X: "X \<subseteq> L (WHILE b DO c) X" |
46 lemma L_While_X: "X \<subseteq> L (WHILE b DO c) X" |
47 using L_While_unfold by blast |
47 using L_While_unfold by blast |
48 |
48 |
49 text{* Disable @{text "L WHILE"} equation and reason only with @{text "L WHILE"} constraints: *} |
49 text\<open>Disable @{text "L WHILE"} equation and reason only with @{text "L WHILE"} constraints:\<close> |
50 declare L.simps(5)[simp del] |
50 declare L.simps(5)[simp del] |
51 |
51 |
52 |
52 |
53 subsection "Correctness" |
53 subsection "Correctness" |
54 |
54 |
71 show ?case using t12 t23 s3t3 by auto |
71 show ?case using t12 t23 s3t3 by auto |
72 next |
72 next |
73 case (IfTrue b s c1 s' c2) |
73 case (IfTrue b s c1 s' c2) |
74 hence "s = t on vars b" and "s = t on L c1 X" by auto |
74 hence "s = t on vars b" and "s = t on L c1 X" by auto |
75 from bval_eq_if_eq_on_vars[OF this(1)] IfTrue(1) have "bval b t" by simp |
75 from bval_eq_if_eq_on_vars[OF this(1)] IfTrue(1) have "bval b t" by simp |
76 from IfTrue.IH[OF `s = t on L c1 X`] obtain t' where |
76 from IfTrue.IH[OF \<open>s = t on L c1 X\<close>] obtain t' where |
77 "(c1, t) \<Rightarrow> t'" "s' = t' on X" by auto |
77 "(c1, t) \<Rightarrow> t'" "s' = t' on X" by auto |
78 thus ?case using `bval b t` by auto |
78 thus ?case using \<open>bval b t\<close> by auto |
79 next |
79 next |
80 case (IfFalse b s c2 s' c1) |
80 case (IfFalse b s c2 s' c1) |
81 hence "s = t on vars b" "s = t on L c2 X" by auto |
81 hence "s = t on vars b" "s = t on L c2 X" by auto |
82 from bval_eq_if_eq_on_vars[OF this(1)] IfFalse(1) have "~bval b t" by simp |
82 from bval_eq_if_eq_on_vars[OF this(1)] IfFalse(1) have "~bval b t" by simp |
83 from IfFalse.IH[OF `s = t on L c2 X`] obtain t' where |
83 from IfFalse.IH[OF \<open>s = t on L c2 X\<close>] obtain t' where |
84 "(c2, t) \<Rightarrow> t'" "s' = t' on X" by auto |
84 "(c2, t) \<Rightarrow> t'" "s' = t' on X" by auto |
85 thus ?case using `~bval b t` by auto |
85 thus ?case using \<open>~bval b t\<close> by auto |
86 next |
86 next |
87 case (WhileFalse b s c) |
87 case (WhileFalse b s c) |
88 hence "~ bval b t" |
88 hence "~ bval b t" |
89 by (metis L_While_vars bval_eq_if_eq_on_vars set_mp) |
89 by (metis L_While_vars bval_eq_if_eq_on_vars set_mp) |
90 thus ?case using WhileFalse.prems L_While_X[of X b c] by auto |
90 thus ?case using WhileFalse.prems L_While_X[of X b c] by auto |
91 next |
91 next |
92 case (WhileTrue b s1 c s2 s3 X t1) |
92 case (WhileTrue b s1 c s2 s3 X t1) |
93 let ?w = "WHILE b DO c" |
93 let ?w = "WHILE b DO c" |
94 from `bval b s1` WhileTrue.prems have "bval b t1" |
94 from \<open>bval b s1\<close> WhileTrue.prems have "bval b t1" |
95 by (metis L_While_vars bval_eq_if_eq_on_vars set_mp) |
95 by (metis L_While_vars bval_eq_if_eq_on_vars set_mp) |
96 have "s1 = t1 on L c (L ?w X)" using L_While_pfp WhileTrue.prems |
96 have "s1 = t1 on L c (L ?w X)" using L_While_pfp WhileTrue.prems |
97 by (blast) |
97 by (blast) |
98 from WhileTrue.IH(1)[OF this] obtain t2 where |
98 from WhileTrue.IH(1)[OF this] obtain t2 where |
99 "(c, t1) \<Rightarrow> t2" "s2 = t2 on L ?w X" by auto |
99 "(c, t1) \<Rightarrow> t2" "s2 = t2 on L ?w X" by auto |
100 from WhileTrue.IH(2)[OF this(2)] obtain t3 where "(?w,t2) \<Rightarrow> t3" "s3 = t3 on X" |
100 from WhileTrue.IH(2)[OF this(2)] obtain t3 where "(?w,t2) \<Rightarrow> t3" "s3 = t3 on X" |
101 by auto |
101 by auto |
102 with `bval b t1` `(c, t1) \<Rightarrow> t2` show ?case by auto |
102 with \<open>bval b t1\<close> \<open>(c, t1) \<Rightarrow> t2\<close> show ?case by auto |
103 qed |
103 qed |
104 |
104 |
105 |
105 |
106 subsection "Executability" |
106 subsection "Executability" |
107 |
107 |
112 using While.IH[of "vars b \<union> rvars c \<union> X"] |
112 using While.IH[of "vars b \<union> rvars c \<union> X"] |
113 by (auto intro!: lfp_lowerbound) |
113 by (auto intro!: lfp_lowerbound) |
114 thus ?case by (simp add: L.simps(5)) |
114 thus ?case by (simp add: L.simps(5)) |
115 qed auto |
115 qed auto |
116 |
116 |
117 text{* Make @{const L} executable by replacing @{const lfp} with the @{const |
117 text\<open>Make @{const L} executable by replacing @{const lfp} with the @{const |
118 while} combinator from theory @{theory While_Combinator}. The @{const while} |
118 while} combinator from theory @{theory While_Combinator}. The @{const while} |
119 combinator obeys the recursion equation |
119 combinator obeys the recursion equation |
120 @{thm[display] While_Combinator.while_unfold[no_vars]} |
120 @{thm[display] While_Combinator.while_unfold[no_vars]} |
121 and is thus executable. *} |
121 and is thus executable.\<close> |
122 |
122 |
123 lemma L_While: fixes b c X |
123 lemma L_While: fixes b c X |
124 assumes "finite X" defines "f == \<lambda>Y. vars b \<union> X \<union> L c Y" |
124 assumes "finite X" defines "f == \<lambda>Y. vars b \<union> X \<union> L c Y" |
125 shows "L (WHILE b DO c) X = while (\<lambda>Y. f Y \<noteq> Y) f {}" (is "_ = ?r") |
125 shows "L (WHILE b DO c) X = while (\<lambda>Y. f Y \<noteq> Y) f {}" (is "_ = ?r") |
126 proof - |
126 proof - |
130 show "mono f" by(simp add: f_def mono_union_L) |
130 show "mono f" by(simp add: f_def mono_union_L) |
131 next |
131 next |
132 fix Y show "Y \<subseteq> ?V \<Longrightarrow> f Y \<subseteq> ?V" |
132 fix Y show "Y \<subseteq> ?V \<Longrightarrow> f Y \<subseteq> ?V" |
133 unfolding f_def using L_subset_vars[of c] by blast |
133 unfolding f_def using L_subset_vars[of c] by blast |
134 next |
134 next |
135 show "finite ?V" using `finite X` by simp |
135 show "finite ?V" using \<open>finite X\<close> by simp |
136 qed |
136 qed |
137 thus ?thesis by (simp add: f_def L.simps(5)) |
137 thus ?thesis by (simp add: f_def L.simps(5)) |
138 qed |
138 qed |
139 |
139 |
140 lemma L_While_let: "finite X \<Longrightarrow> L (WHILE b DO c) X = |
140 lemma L_While_let: "finite X \<Longrightarrow> L (WHILE b DO c) X = |
145 lemma L_While_set: "L (WHILE b DO c) (set xs) = |
145 lemma L_While_set: "L (WHILE b DO c) (set xs) = |
146 (let f = (\<lambda>Y. vars b \<union> set xs \<union> L c Y) |
146 (let f = (\<lambda>Y. vars b \<union> set xs \<union> L c Y) |
147 in while (\<lambda>Y. f Y \<noteq> Y) f {})" |
147 in while (\<lambda>Y. f Y \<noteq> Y) f {})" |
148 by(rule L_While_let, simp) |
148 by(rule L_While_let, simp) |
149 |
149 |
150 text{* Replace the equation for @{text "L (WHILE \<dots>)"} by the executable @{thm[source] L_While_set}: *} |
150 text\<open>Replace the equation for @{text "L (WHILE \<dots>)"} by the executable @{thm[source] L_While_set}:\<close> |
151 lemmas [code] = L.simps(1-4) L_While_set |
151 lemmas [code] = L.simps(1-4) L_While_set |
152 text{* Sorry, this syntax is odd. *} |
152 text\<open>Sorry, this syntax is odd.\<close> |
153 |
153 |
154 text{* A test: *} |
154 text\<open>A test:\<close> |
155 lemma "(let b = Less (N 0) (V ''y''); c = ''y'' ::= V ''x'';; ''x'' ::= V ''z'' |
155 lemma "(let b = Less (N 0) (V ''y''); c = ''y'' ::= V ''x'';; ''x'' ::= V ''z'' |
156 in L (WHILE b DO c) {''y''}) = {''x'', ''y'', ''z''}" |
156 in L (WHILE b DO c) {''y''}) = {''x'', ''y'', ''z''}" |
157 by eval |
157 by eval |
158 |
158 |
159 |
159 |
160 subsection "Limiting the number of iterations" |
160 subsection "Limiting the number of iterations" |
161 |
161 |
162 text{* The final parameter is the default value: *} |
162 text\<open>The final parameter is the default value:\<close> |
163 |
163 |
164 fun iter :: "('a \<Rightarrow> 'a) \<Rightarrow> nat \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'a" where |
164 fun iter :: "('a \<Rightarrow> 'a) \<Rightarrow> nat \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'a" where |
165 "iter f 0 p d = d" | |
165 "iter f 0 p d = d" | |
166 "iter f (Suc n) p d = (if f p = p then p else iter f n (f p) d)" |
166 "iter f (Suc n) p d = (if f p = p then p else iter f n (f p) d)" |
167 |
167 |
168 text{* A version of @{const L} with a bounded number of iterations (here: 2) |
168 text\<open>A version of @{const L} with a bounded number of iterations (here: 2) |
169 in the WHILE case: *} |
169 in the WHILE case:\<close> |
170 |
170 |
171 fun Lb :: "com \<Rightarrow> vname set \<Rightarrow> vname set" where |
171 fun Lb :: "com \<Rightarrow> vname set \<Rightarrow> vname set" where |
172 "Lb SKIP X = X" | |
172 "Lb SKIP X = X" | |
173 "Lb (x ::= a) X = (if x \<in> X then X - {x} \<union> vars a else X)" | |
173 "Lb (x ::= a) X = (if x \<in> X then X - {x} \<union> vars a else X)" | |
174 "Lb (c\<^sub>1;; c\<^sub>2) X = (Lb c\<^sub>1 \<circ> Lb c\<^sub>2) X" | |
174 "Lb (c\<^sub>1;; c\<^sub>2) X = (Lb c\<^sub>1 \<circ> Lb c\<^sub>2) X" | |
175 "Lb (IF b THEN c\<^sub>1 ELSE c\<^sub>2) X = vars b \<union> Lb c\<^sub>1 X \<union> Lb c\<^sub>2 X" | |
175 "Lb (IF b THEN c\<^sub>1 ELSE c\<^sub>2) X = vars b \<union> Lb c\<^sub>1 X \<union> Lb c\<^sub>2 X" | |
176 "Lb (WHILE b DO c) X = iter (\<lambda>A. vars b \<union> X \<union> Lb c A) 2 {} (vars b \<union> rvars c \<union> X)" |
176 "Lb (WHILE b DO c) X = iter (\<lambda>A. vars b \<union> X \<union> Lb c A) 2 {} (vars b \<union> rvars c \<union> X)" |
177 |
177 |
178 text{* @{const Lb} (and @{const iter}) is not monotone! *} |
178 text\<open>@{const Lb} (and @{const iter}) is not monotone!\<close> |
179 lemma "let w = WHILE Bc False DO (''x'' ::= V ''y'';; ''z'' ::= V ''x'') |
179 lemma "let w = WHILE Bc False DO (''x'' ::= V ''y'';; ''z'' ::= V ''x'') |
180 in \<not> (Lb w {''z''} \<subseteq> Lb w {''y'',''z''})" |
180 in \<not> (Lb w {''z''} \<subseteq> Lb w {''y'',''z''})" |
181 by eval |
181 by eval |
182 |
182 |
183 lemma lfp_subset_iter: |
183 lemma lfp_subset_iter: |