src/HOL/IMP/Live_True.thy
changeset 67406 23307fd33906
parent 67019 7a3724078363
child 68484 59793df7f853
equal deleted inserted replaced
67405:e9ab4ad7bd15 67406:23307fd33906
    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: