114 using While.IH[of "vars b \<union> rvars c \<union> X"] |
114 using While.IH[of "vars b \<union> rvars c \<union> X"] |
115 by (auto intro!: lfp_lowerbound) |
115 by (auto intro!: lfp_lowerbound) |
116 thus ?case by (simp add: L.simps(5)) |
116 thus ?case by (simp add: L.simps(5)) |
117 qed auto |
117 qed auto |
118 |
118 |
119 text\<open>Make @{const L} executable by replacing @{const lfp} with the @{const |
119 text\<open>Make \<^const>\<open>L\<close> executable by replacing \<^const>\<open>lfp\<close> with the \<^const>\<open>while\<close> combinator from theory \<^theory>\<open>HOL-Library.While_Combinator\<close>. The \<^const>\<open>while\<close> |
120 while} combinator from theory @{theory "HOL-Library.While_Combinator"}. The @{const while} |
|
121 combinator obeys the recursion equation |
120 combinator obeys the recursion equation |
122 @{thm[display] While_Combinator.while_unfold[no_vars]} |
121 @{thm[display] While_Combinator.while_unfold[no_vars]} |
123 and is thus executable.\<close> |
122 and is thus executable.\<close> |
124 |
123 |
125 lemma L_While: fixes b c X |
124 lemma L_While: fixes b c X |
165 |
164 |
166 fun iter :: "('a \<Rightarrow> 'a) \<Rightarrow> nat \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'a" where |
165 fun iter :: "('a \<Rightarrow> 'a) \<Rightarrow> nat \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'a" where |
167 "iter f 0 p d = d" | |
166 "iter f 0 p d = d" | |
168 "iter f (Suc n) p d = (if f p = p then p else iter f n (f p) d)" |
167 "iter f (Suc n) p d = (if f p = p then p else iter f n (f p) d)" |
169 |
168 |
170 text\<open>A version of @{const L} with a bounded number of iterations (here: 2) |
169 text\<open>A version of \<^const>\<open>L\<close> with a bounded number of iterations (here: 2) |
171 in the WHILE case:\<close> |
170 in the WHILE case:\<close> |
172 |
171 |
173 fun Lb :: "com \<Rightarrow> vname set \<Rightarrow> vname set" where |
172 fun Lb :: "com \<Rightarrow> vname set \<Rightarrow> vname set" where |
174 "Lb SKIP X = X" | |
173 "Lb SKIP X = X" | |
175 "Lb (x ::= a) X = (if x \<in> X then X - {x} \<union> vars a else X)" | |
174 "Lb (x ::= a) X = (if x \<in> X then X - {x} \<union> vars a else X)" | |
176 "Lb (c\<^sub>1;; c\<^sub>2) X = (Lb c\<^sub>1 \<circ> Lb c\<^sub>2) X" | |
175 "Lb (c\<^sub>1;; c\<^sub>2) X = (Lb c\<^sub>1 \<circ> Lb c\<^sub>2) X" | |
177 "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 (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" | |
178 "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 "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)" |
179 |
178 |
180 text\<open>@{const Lb} (and @{const iter}) is not monotone!\<close> |
179 text\<open>\<^const>\<open>Lb\<close> (and \<^const>\<open>iter\<close>) is not monotone!\<close> |
181 lemma "let w = WHILE Bc False DO (''x'' ::= V ''y'';; ''z'' ::= V ''x'') |
180 lemma "let w = WHILE Bc False DO (''x'' ::= V ''y'';; ''z'' ::= V ''x'') |
182 in \<not> (Lb w {''z''} \<subseteq> Lb w {''y'',''z''})" |
181 in \<not> (Lb w {''z''} \<subseteq> Lb w {''y'',''z''})" |
183 by eval |
182 by eval |
184 |
183 |
185 lemma lfp_subset_iter: |
184 lemma lfp_subset_iter: |