change to simpler, more extensible continuity simproc
authorhuffman
Wed Jan 14 17:11:29 2009 -0800 (2009-01-14)
changeset 295309905b660612b
parent 29485 ec072307c69b
child 29531 2eb29775b0b6
change to simpler, more extensible continuity simproc

define attribute [cont2cont] for continuity rules;
new continuity simproc just applies cont2cont rules repeatedly;
split theory Product_Cpo from Cprod, so Cfun can import Product_Cpo;
add lemma cont2cont_LAM', which is suitable as a cont2cont rule.
src/HOLCF/Cfun.thy
src/HOLCF/Cont.thy
src/HOLCF/Cprod.thy
src/HOLCF/Fixrec.thy
src/HOLCF/HOLCF.thy
src/HOLCF/IsaMakefile
src/HOLCF/Ssum.thy
src/HOLCF/Up.thy
src/HOLCF/ex/Stream.thy
     1.1 --- a/src/HOLCF/Cfun.thy	Wed Jan 14 13:47:14 2009 -0800
     1.2 +++ b/src/HOLCF/Cfun.thy	Wed Jan 14 17:11:29 2009 -0800
     1.3 @@ -7,8 +7,7 @@
     1.4  header {* The type of continuous functions *}
     1.5  
     1.6  theory Cfun
     1.7 -imports Pcpodef Ffun
     1.8 -uses ("Tools/cont_proc.ML")
     1.9 +imports Pcpodef Product_Cpo
    1.10  begin
    1.11  
    1.12  defaultsort cpo
    1.13 @@ -301,7 +300,7 @@
    1.14  
    1.15  text {* cont2cont lemma for @{term Rep_CFun} *}
    1.16  
    1.17 -lemma cont2cont_Rep_CFun:
    1.18 +lemma cont2cont_Rep_CFun [cont2cont]:
    1.19    assumes f: "cont (\<lambda>x. f x)"
    1.20    assumes t: "cont (\<lambda>x. t x)"
    1.21    shows "cont (\<lambda>x. (f x)\<cdot>(t x))"
    1.22 @@ -321,6 +320,11 @@
    1.23  
    1.24  text {* cont2cont Lemma for @{term "%x. LAM y. f x y"} *}
    1.25  
    1.26 +text {*
    1.27 +  Not suitable as a cont2cont rule, because on nested lambdas
    1.28 +  it causes exponential blow-up in the number of subgoals.
    1.29 +*}
    1.30 +
    1.31  lemma cont2cont_LAM:
    1.32    assumes f1: "\<And>x. cont (\<lambda>y. f x y)"
    1.33    assumes f2: "\<And>y. cont (\<lambda>x. f x y)"
    1.34 @@ -331,17 +335,40 @@
    1.35    from f2 show "cont f" by (rule cont2cont_lambda)
    1.36  qed
    1.37  
    1.38 -text {* continuity simplification procedure *}
    1.39 +text {*
    1.40 +  This version does work as a cont2cont rule, since it
    1.41 +  has only a single subgoal.
    1.42 +*}
    1.43 +
    1.44 +lemma cont2cont_LAM' [cont2cont]:
    1.45 +  fixes f :: "'a::cpo \<Rightarrow> 'b::cpo \<Rightarrow> 'c::cpo"
    1.46 +  assumes f: "cont (\<lambda>p. f (fst p) (snd p))"
    1.47 +  shows "cont (\<lambda>x. \<Lambda> y. f x y)"
    1.48 +proof (rule cont2cont_LAM)
    1.49 +  fix x :: 'a
    1.50 +  have "cont (\<lambda>y. (x, y))"
    1.51 +    by (rule cont_pair2)
    1.52 +  with f have "cont (\<lambda>y. f (fst (x, y)) (snd (x, y)))"
    1.53 +    by (rule cont2cont_app3)
    1.54 +  thus "cont (\<lambda>y. f x y)"
    1.55 +    by (simp only: fst_conv snd_conv)
    1.56 +next
    1.57 +  fix y :: 'b
    1.58 +  have "cont (\<lambda>x. (x, y))"
    1.59 +    by (rule cont_pair1)
    1.60 +  with f have "cont (\<lambda>x. f (fst (x, y)) (snd (x, y)))"
    1.61 +    by (rule cont2cont_app3)
    1.62 +  thus "cont (\<lambda>x. f x y)"
    1.63 +    by (simp only: fst_conv snd_conv)
    1.64 +qed
    1.65 +
    1.66 +lemma cont2cont_LAM_discrete [cont2cont]:
    1.67 +  "(\<And>y::'a::discrete_cpo. cont (\<lambda>x. f x y)) \<Longrightarrow> cont (\<lambda>x. \<Lambda> y. f x y)"
    1.68 +by (simp add: cont2cont_LAM)
    1.69  
    1.70  lemmas cont_lemmas1 =
    1.71    cont_const cont_id cont_Rep_CFun2 cont2cont_Rep_CFun cont2cont_LAM
    1.72  
    1.73 -use "Tools/cont_proc.ML";
    1.74 -setup ContProc.setup;
    1.75 -
    1.76 -(*val cont_tac = (fn i => (resolve_tac cont_lemmas i));*)
    1.77 -(*val cont_tacR = (fn i => (REPEAT (cont_tac i)));*)
    1.78 -
    1.79  subsection {* Miscellaneous *}
    1.80  
    1.81  text {* Monotonicity of @{term Abs_CFun} *}
    1.82 @@ -530,7 +557,8 @@
    1.83    monocontlub2cont [OF monofun_strictify2 contlub_strictify2, standard]
    1.84  
    1.85  lemma strictify_conv_if: "strictify\<cdot>f\<cdot>x = (if x = \<bottom> then \<bottom> else f\<cdot>x)"
    1.86 -by (unfold strictify_def, simp add: cont_strictify1 cont_strictify2)
    1.87 +  unfolding strictify_def
    1.88 +  by (simp add: cont_strictify1 cont_strictify2 cont2cont_LAM)
    1.89  
    1.90  lemma strictify1 [simp]: "strictify\<cdot>f\<cdot>\<bottom> = \<bottom>"
    1.91  by (simp add: strictify_conv_if)
     2.1 --- a/src/HOLCF/Cont.thy	Wed Jan 14 13:47:14 2009 -0800
     2.2 +++ b/src/HOLCF/Cont.thy	Wed Jan 14 17:11:29 2009 -0800
     2.3 @@ -135,18 +135,50 @@
     2.4  apply (erule cpo_lubI)
     2.5  done
     2.6  
     2.7 +subsection {* Continuity simproc *}
     2.8 +
     2.9 +ML {*
    2.10 +structure Cont2ContData = NamedThmsFun
    2.11 +  ( val name = "cont2cont" val description = "continuity intro rule" )
    2.12 +*}
    2.13 +
    2.14 +setup {* Cont2ContData.setup *}
    2.15 +
    2.16 +text {*
    2.17 +  Given the term @{term "cont f"}, the procedure tries to construct the
    2.18 +  theorem @{term "cont f == True"}. If this theorem cannot be completely
    2.19 +  solved by the introduction rules, then the procedure returns a
    2.20 +  conditional rewrite rule with the unsolved subgoals as premises.
    2.21 +*}
    2.22 +
    2.23 +setup {*
    2.24 +let
    2.25 +  fun solve_cont thy ss t =
    2.26 +    let
    2.27 +      val tr = instantiate' [] [SOME (cterm_of thy t)] Eq_TrueI;
    2.28 +      val rules = Cont2ContData.get (Simplifier.the_context ss);
    2.29 +      val tac = REPEAT_ALL_NEW (resolve_tac rules);
    2.30 +    in Option.map fst (Seq.pull (tac 1 tr)) end
    2.31 +
    2.32 +  val proc =
    2.33 +    Simplifier.simproc @{theory} "cont_proc" ["cont f"] solve_cont;
    2.34 +in
    2.35 +  Simplifier.map_simpset (fn ss => ss addsimprocs [proc])
    2.36 +end
    2.37 +*}
    2.38 +
    2.39  subsection {* Continuity of basic functions *}
    2.40  
    2.41  text {* The identity function is continuous *}
    2.42  
    2.43 -lemma cont_id: "cont (\<lambda>x. x)"
    2.44 +lemma cont_id [cont2cont]: "cont (\<lambda>x. x)"
    2.45  apply (rule contI)
    2.46  apply (erule cpo_lubI)
    2.47  done
    2.48  
    2.49  text {* constant functions are continuous *}
    2.50  
    2.51 -lemma cont_const: "cont (\<lambda>x. c)"
    2.52 +lemma cont_const [cont2cont]: "cont (\<lambda>x. c)"
    2.53  apply (rule contI)
    2.54  apply (rule lub_const)
    2.55  done
     3.1 --- a/src/HOLCF/Cprod.thy	Wed Jan 14 13:47:14 2009 -0800
     3.2 +++ b/src/HOLCF/Cprod.thy	Wed Jan 14 17:11:29 2009 -0800
     3.3 @@ -12,23 +12,6 @@
     3.4  
     3.5  subsection {* Type @{typ unit} is a pcpo *}
     3.6  
     3.7 -instantiation unit :: sq_ord
     3.8 -begin
     3.9 -
    3.10 -definition
    3.11 -  less_unit_def [simp]: "x \<sqsubseteq> (y::unit) \<equiv> True"
    3.12 -
    3.13 -instance ..
    3.14 -end
    3.15 -
    3.16 -instance unit :: discrete_cpo
    3.17 -by intro_classes simp
    3.18 -
    3.19 -instance unit :: finite_po ..
    3.20 -
    3.21 -instance unit :: pcpo
    3.22 -by intro_classes simp
    3.23 -
    3.24  definition
    3.25    unit_when :: "'a \<rightarrow> unit \<rightarrow> 'a" where
    3.26    "unit_when = (\<Lambda> a _. a)"
    3.27 @@ -39,165 +22,6 @@
    3.28  lemma unit_when [simp]: "unit_when\<cdot>a\<cdot>u = a"
    3.29  by (simp add: unit_when_def)
    3.30  
    3.31 -
    3.32 -subsection {* Product type is a partial order *}
    3.33 -
    3.34 -instantiation "*" :: (sq_ord, sq_ord) sq_ord
    3.35 -begin
    3.36 -
    3.37 -definition
    3.38 -  less_cprod_def: "(op \<sqsubseteq>) \<equiv> \<lambda>p1 p2. (fst p1 \<sqsubseteq> fst p2 \<and> snd p1 \<sqsubseteq> snd p2)"
    3.39 -
    3.40 -instance ..
    3.41 -end
    3.42 -
    3.43 -instance "*" :: (po, po) po
    3.44 -proof
    3.45 -  fix x :: "'a \<times> 'b"
    3.46 -  show "x \<sqsubseteq> x"
    3.47 -    unfolding less_cprod_def by simp
    3.48 -next
    3.49 -  fix x y :: "'a \<times> 'b"
    3.50 -  assume "x \<sqsubseteq> y" "y \<sqsubseteq> x" thus "x = y"
    3.51 -    unfolding less_cprod_def Pair_fst_snd_eq
    3.52 -    by (fast intro: antisym_less)
    3.53 -next
    3.54 -  fix x y z :: "'a \<times> 'b"
    3.55 -  assume "x \<sqsubseteq> y" "y \<sqsubseteq> z" thus "x \<sqsubseteq> z"
    3.56 -    unfolding less_cprod_def
    3.57 -    by (fast intro: trans_less)
    3.58 -qed
    3.59 -
    3.60 -subsection {* Monotonicity of @{text "(_,_)"}, @{term fst}, @{term snd} *}
    3.61 -
    3.62 -lemma prod_lessI: "\<lbrakk>fst p \<sqsubseteq> fst q; snd p \<sqsubseteq> snd q\<rbrakk> \<Longrightarrow> p \<sqsubseteq> q"
    3.63 -unfolding less_cprod_def by simp
    3.64 -
    3.65 -lemma Pair_less_iff [simp]: "(a, b) \<sqsubseteq> (c, d) = (a \<sqsubseteq> c \<and> b \<sqsubseteq> d)"
    3.66 -unfolding less_cprod_def by simp
    3.67 -
    3.68 -text {* Pair @{text "(_,_)"}  is monotone in both arguments *}
    3.69 -
    3.70 -lemma monofun_pair1: "monofun (\<lambda>x. (x, y))"
    3.71 -by (simp add: monofun_def)
    3.72 -
    3.73 -lemma monofun_pair2: "monofun (\<lambda>y. (x, y))"
    3.74 -by (simp add: monofun_def)
    3.75 -
    3.76 -lemma monofun_pair:
    3.77 -  "\<lbrakk>x1 \<sqsubseteq> x2; y1 \<sqsubseteq> y2\<rbrakk> \<Longrightarrow> (x1, y1) \<sqsubseteq> (x2, y2)"
    3.78 -by simp
    3.79 -
    3.80 -text {* @{term fst} and @{term snd} are monotone *}
    3.81 -
    3.82 -lemma monofun_fst: "monofun fst"
    3.83 -by (simp add: monofun_def less_cprod_def)
    3.84 -
    3.85 -lemma monofun_snd: "monofun snd"
    3.86 -by (simp add: monofun_def less_cprod_def)
    3.87 -
    3.88 -subsection {* Product type is a cpo *}
    3.89 -
    3.90 -lemma is_lub_Pair:
    3.91 -  "\<lbrakk>range X <<| x; range Y <<| y\<rbrakk> \<Longrightarrow> range (\<lambda>i. (X i, Y i)) <<| (x, y)"
    3.92 -apply (rule is_lubI [OF ub_rangeI])
    3.93 -apply (simp add: less_cprod_def is_ub_lub)
    3.94 -apply (frule ub2ub_monofun [OF monofun_fst])
    3.95 -apply (drule ub2ub_monofun [OF monofun_snd])
    3.96 -apply (simp add: less_cprod_def is_lub_lub)
    3.97 -done
    3.98 -
    3.99 -lemma lub_cprod:
   3.100 -  fixes S :: "nat \<Rightarrow> ('a::cpo \<times> 'b::cpo)"
   3.101 -  assumes S: "chain S"
   3.102 -  shows "range S <<| (\<Squnion>i. fst (S i), \<Squnion>i. snd (S i))"
   3.103 -proof -
   3.104 -  have "chain (\<lambda>i. fst (S i))"
   3.105 -    using monofun_fst S by (rule ch2ch_monofun)
   3.106 -  hence 1: "range (\<lambda>i. fst (S i)) <<| (\<Squnion>i. fst (S i))"
   3.107 -    by (rule cpo_lubI)
   3.108 -  have "chain (\<lambda>i. snd (S i))"
   3.109 -    using monofun_snd S by (rule ch2ch_monofun)
   3.110 -  hence 2: "range (\<lambda>i. snd (S i)) <<| (\<Squnion>i. snd (S i))"
   3.111 -    by (rule cpo_lubI)
   3.112 -  show "range S <<| (\<Squnion>i. fst (S i), \<Squnion>i. snd (S i))"
   3.113 -    using is_lub_Pair [OF 1 2] by simp
   3.114 -qed
   3.115 -
   3.116 -lemma thelub_cprod:
   3.117 -  "chain (S::nat \<Rightarrow> 'a::cpo \<times> 'b::cpo)
   3.118 -    \<Longrightarrow> (\<Squnion>i. S i) = (\<Squnion>i. fst (S i), \<Squnion>i. snd (S i))"
   3.119 -by (rule lub_cprod [THEN thelubI])
   3.120 -
   3.121 -instance "*" :: (cpo, cpo) cpo
   3.122 -proof
   3.123 -  fix S :: "nat \<Rightarrow> ('a \<times> 'b)"
   3.124 -  assume "chain S"
   3.125 -  hence "range S <<| (\<Squnion>i. fst (S i), \<Squnion>i. snd (S i))"
   3.126 -    by (rule lub_cprod)
   3.127 -  thus "\<exists>x. range S <<| x" ..
   3.128 -qed
   3.129 -
   3.130 -instance "*" :: (finite_po, finite_po) finite_po ..
   3.131 -
   3.132 -instance "*" :: (discrete_cpo, discrete_cpo) discrete_cpo
   3.133 -proof
   3.134 -  fix x y :: "'a \<times> 'b"
   3.135 -  show "x \<sqsubseteq> y \<longleftrightarrow> x = y"
   3.136 -    unfolding less_cprod_def Pair_fst_snd_eq
   3.137 -    by simp
   3.138 -qed
   3.139 -
   3.140 -subsection {* Product type is pointed *}
   3.141 -
   3.142 -lemma minimal_cprod: "(\<bottom>, \<bottom>) \<sqsubseteq> p"
   3.143 -by (simp add: less_cprod_def)
   3.144 -
   3.145 -instance "*" :: (pcpo, pcpo) pcpo
   3.146 -by intro_classes (fast intro: minimal_cprod)
   3.147 -
   3.148 -lemma inst_cprod_pcpo: "\<bottom> = (\<bottom>, \<bottom>)"
   3.149 -by (rule minimal_cprod [THEN UU_I, symmetric])
   3.150 -
   3.151 -
   3.152 -subsection {* Continuity of @{text "(_,_)"}, @{term fst}, @{term snd} *}
   3.153 -
   3.154 -lemma cont_pair1: "cont (\<lambda>x. (x, y))"
   3.155 -apply (rule contI)
   3.156 -apply (rule is_lub_Pair)
   3.157 -apply (erule cpo_lubI)
   3.158 -apply (rule lub_const)
   3.159 -done
   3.160 -
   3.161 -lemma cont_pair2: "cont (\<lambda>y. (x, y))"
   3.162 -apply (rule contI)
   3.163 -apply (rule is_lub_Pair)
   3.164 -apply (rule lub_const)
   3.165 -apply (erule cpo_lubI)
   3.166 -done
   3.167 -
   3.168 -lemma contlub_fst: "contlub fst"
   3.169 -apply (rule contlubI)
   3.170 -apply (simp add: thelub_cprod)
   3.171 -done
   3.172 -
   3.173 -lemma contlub_snd: "contlub snd"
   3.174 -apply (rule contlubI)
   3.175 -apply (simp add: thelub_cprod)
   3.176 -done
   3.177 -
   3.178 -lemma cont_fst: "cont fst"
   3.179 -apply (rule monocontlub2cont)
   3.180 -apply (rule monofun_fst)
   3.181 -apply (rule contlub_fst)
   3.182 -done
   3.183 -
   3.184 -lemma cont_snd: "cont snd"
   3.185 -apply (rule monocontlub2cont)
   3.186 -apply (rule monofun_snd)
   3.187 -apply (rule contlub_snd)
   3.188 -done
   3.189 -
   3.190  subsection {* Continuous versions of constants *}
   3.191  
   3.192  definition
     4.1 --- a/src/HOLCF/Fixrec.thy	Wed Jan 14 13:47:14 2009 -0800
     4.2 +++ b/src/HOLCF/Fixrec.thy	Wed Jan 14 17:11:29 2009 -0800
     4.3 @@ -55,6 +55,7 @@
     4.4    "maybe_when\<cdot>f\<cdot>r\<cdot>fail = f"
     4.5    "maybe_when\<cdot>f\<cdot>r\<cdot>(return\<cdot>x) = r\<cdot>x"
     4.6  by (simp_all add: return_def fail_def maybe_when_def cont_Rep_maybe
     4.7 +                  cont2cont_LAM
     4.8                    cont_Abs_maybe Abs_maybe_inverse Rep_maybe_strict)
     4.9  
    4.10  translations
     5.1 --- a/src/HOLCF/HOLCF.thy	Wed Jan 14 13:47:14 2009 -0800
     5.2 +++ b/src/HOLCF/HOLCF.thy	Wed Jan 14 17:11:29 2009 -0800
     5.3 @@ -10,6 +10,7 @@
     5.4  uses
     5.5    "holcf_logic.ML"
     5.6    "Tools/cont_consts.ML"
     5.7 +  "Tools/cont_proc.ML"
     5.8    "Tools/domain/domain_library.ML"
     5.9    "Tools/domain/domain_syntax.ML"
    5.10    "Tools/domain/domain_axioms.ML"
     6.1 --- a/src/HOLCF/IsaMakefile	Wed Jan 14 13:47:14 2009 -0800
     6.2 +++ b/src/HOLCF/IsaMakefile	Wed Jan 14 17:11:29 2009 -0800
     6.3 @@ -1,5 +1,3 @@
     6.4 -#
     6.5 -# $Id$
     6.6  #
     6.7  # IsaMakefile for HOLCF
     6.8  #
     6.9 @@ -54,6 +52,7 @@
    6.10    Pcpodef.thy \
    6.11    Pcpo.thy \
    6.12    Porder.thy \
    6.13 +  Product_Cpo.thy \
    6.14    Sprod.thy \
    6.15    Ssum.thy \
    6.16    Tr.thy \
     7.1 --- a/src/HOLCF/Ssum.thy	Wed Jan 14 13:47:14 2009 -0800
     7.2 +++ b/src/HOLCF/Ssum.thy	Wed Jan 14 17:11:29 2009 -0800
     7.3 @@ -188,7 +188,7 @@
     7.4  
     7.5  lemma beta_sscase:
     7.6    "sscase\<cdot>f\<cdot>g\<cdot>s = (\<Lambda><t, x, y>. If t then f\<cdot>x else g\<cdot>y fi)\<cdot>(Rep_Ssum s)"
     7.7 -unfolding sscase_def by (simp add: cont_Rep_Ssum)
     7.8 +unfolding sscase_def by (simp add: cont_Rep_Ssum cont2cont_LAM)
     7.9  
    7.10  lemma sscase1 [simp]: "sscase\<cdot>f\<cdot>g\<cdot>\<bottom> = \<bottom>"
    7.11  unfolding beta_sscase by (simp add: Rep_Ssum_strict)
     8.1 --- a/src/HOLCF/Up.thy	Wed Jan 14 13:47:14 2009 -0800
     8.2 +++ b/src/HOLCF/Up.thy	Wed Jan 14 17:11:29 2009 -0800
     8.3 @@ -282,10 +282,10 @@
     8.4  text {* properties of fup *}
     8.5  
     8.6  lemma fup1 [simp]: "fup\<cdot>f\<cdot>\<bottom> = \<bottom>"
     8.7 -by (simp add: fup_def cont_Ifup1 cont_Ifup2 inst_up_pcpo)
     8.8 +by (simp add: fup_def cont_Ifup1 cont_Ifup2 inst_up_pcpo cont2cont_LAM)
     8.9  
    8.10  lemma fup2 [simp]: "fup\<cdot>f\<cdot>(up\<cdot>x) = f\<cdot>x"
    8.11 -by (simp add: up_def fup_def cont_Iup cont_Ifup1 cont_Ifup2)
    8.12 +by (simp add: up_def fup_def cont_Iup cont_Ifup1 cont_Ifup2 cont2cont_LAM)
    8.13  
    8.14  lemma fup3 [simp]: "fup\<cdot>up\<cdot>x = x"
    8.15  by (cases x, simp_all)
     9.1 --- a/src/HOLCF/ex/Stream.thy	Wed Jan 14 13:47:14 2009 -0800
     9.2 +++ b/src/HOLCF/ex/Stream.thy	Wed Jan 14 17:11:29 2009 -0800
     9.3 @@ -521,7 +521,7 @@
     9.4  section "smap"
     9.5  
     9.6  lemma smap_unfold: "smap = (\<Lambda> f t. case t of x&&xs \<Rightarrow> f$x && smap$f$xs)"
     9.7 -by (insert smap_def [THEN eq_reflection, THEN fix_eq2], auto)
     9.8 +by (insert smap_def [where 'a='a and 'b='b, THEN eq_reflection, THEN fix_eq2], auto)
     9.9  
    9.10  lemma smap_empty [simp]: "smap\<cdot>f\<cdot>\<bottom> = \<bottom>"
    9.11  by (subst smap_unfold, simp)
    9.12 @@ -540,7 +540,7 @@
    9.13  lemma sfilter_unfold:
    9.14   "sfilter = (\<Lambda> p s. case s of x && xs \<Rightarrow>
    9.15    If p\<cdot>x then x && sfilter\<cdot>p\<cdot>xs else sfilter\<cdot>p\<cdot>xs fi)"
    9.16 -by (insert sfilter_def [THEN eq_reflection, THEN fix_eq2], auto)
    9.17 +by (insert sfilter_def [where 'a='a, THEN eq_reflection, THEN fix_eq2], auto)
    9.18  
    9.19  lemma strict_sfilter: "sfilter\<cdot>\<bottom> = \<bottom>"
    9.20  apply (rule ext_cfun)