src/HOL/IMP/Live_True.thy
changeset 69597 ff784d5a5bfb
parent 69505 cc2d676d5395
child 69712 dc85b5b3a532
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
   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: