src/HOLCF/Cfun2.ML
changeset 5291 5706f0ef1d43
parent 4721 c8a8482a8124
child 9245 428385c4bc50
equal deleted inserted replaced
5290:b755c7240348 5291:5706f0ef1d43
     7 *)
     7 *)
     8 
     8 
     9 open Cfun2;
     9 open Cfun2;
    10 
    10 
    11 (* for compatibility with old HOLCF-Version *)
    11 (* for compatibility with old HOLCF-Version *)
    12 qed_goal "inst_cfun_po" thy "(op <<)=(%f1 f2. fapp f1 << fapp f2)"
    12 qed_goal "inst_cfun_po" thy "(op <<)=(%f1 f2. Rep_CFun f1 << Rep_CFun f2)"
    13  (fn prems => 
    13  (fn prems => 
    14         [
    14         [
    15 	(fold_goals_tac [less_cfun_def]),
    15 	(fold_goals_tac [less_cfun_def]),
    16 	(rtac refl 1)
    16 	(rtac refl 1)
    17         ]);
    17         ]);
    18 
    18 
    19 (* ------------------------------------------------------------------------ *)
    19 (* ------------------------------------------------------------------------ *)
    20 (* access to less_cfun in class po                                          *)
    20 (* access to less_cfun in class po                                          *)
    21 (* ------------------------------------------------------------------------ *)
    21 (* ------------------------------------------------------------------------ *)
    22 
    22 
    23 qed_goal "less_cfun" thy "( f1 << f2 ) = (fapp(f1) << fapp(f2))"
    23 qed_goal "less_cfun" thy "( f1 << f2 ) = (Rep_CFun(f1) << Rep_CFun(f2))"
    24 (fn prems =>
    24 (fn prems =>
    25         [
    25         [
    26         (simp_tac (simpset() addsimps [inst_cfun_po]) 1)
    26         (simp_tac (simpset() addsimps [inst_cfun_po]) 1)
    27         ]);
    27         ]);
    28 
    28 
    29 (* ------------------------------------------------------------------------ *)
    29 (* ------------------------------------------------------------------------ *)
    30 (* Type 'a ->'b  is pointed                                                 *)
    30 (* Type 'a ->'b  is pointed                                                 *)
    31 (* ------------------------------------------------------------------------ *)
    31 (* ------------------------------------------------------------------------ *)
    32 
    32 
    33 qed_goal "minimal_cfun" thy "fabs(% x. UU) << f"
    33 qed_goal "minimal_cfun" thy "Abs_CFun(% x. UU) << f"
    34 (fn prems =>
    34 (fn prems =>
    35         [
    35         [
    36         (stac less_cfun 1),
    36         (stac less_cfun 1),
    37         (stac Abs_Cfun_inverse2 1),
    37         (stac Abs_Cfun_inverse2 1),
    38         (rtac cont_const 1),
    38         (rtac cont_const 1),
    42 bind_thm ("UU_cfun_def",minimal_cfun RS minimal2UU RS sym);
    42 bind_thm ("UU_cfun_def",minimal_cfun RS minimal2UU RS sym);
    43 
    43 
    44 qed_goal "least_cfun" thy "? x::'a->'b::pcpo.!y. x<<y"
    44 qed_goal "least_cfun" thy "? x::'a->'b::pcpo.!y. x<<y"
    45 (fn prems =>
    45 (fn prems =>
    46         [
    46         [
    47         (res_inst_tac [("x","fabs(% x. UU)")] exI 1),
    47         (res_inst_tac [("x","Abs_CFun(% x. UU)")] exI 1),
    48         (rtac (minimal_cfun RS allI) 1)
    48         (rtac (minimal_cfun RS allI) 1)
    49         ]);
    49         ]);
    50 
    50 
    51 (* ------------------------------------------------------------------------ *)
    51 (* ------------------------------------------------------------------------ *)
    52 (* fapp yields continuous functions in 'a => 'b                             *)
    52 (* Rep_CFun yields continuous functions in 'a => 'b                             *)
    53 (* this is continuity of fapp in its 'second' argument                      *)
    53 (* this is continuity of Rep_CFun in its 'second' argument                      *)
    54 (* cont_fapp2 ==> monofun_fapp2 & contlub_fapp2                            *)
    54 (* cont_Rep_CFun2 ==> monofun_Rep_CFun2 & contlub_Rep_CFun2                            *)
    55 (* ------------------------------------------------------------------------ *)
    55 (* ------------------------------------------------------------------------ *)
    56 
    56 
    57 qed_goal "cont_fapp2" thy "cont(fapp(fo))"
    57 qed_goal "cont_Rep_CFun2" thy "cont(Rep_CFun(fo))"
    58 (fn prems =>
    58 (fn prems =>
    59         [
    59         [
    60         (res_inst_tac [("P","cont")] CollectD 1),
    60         (res_inst_tac [("P","cont")] CollectD 1),
    61         (fold_goals_tac [CFun_def]),
    61         (fold_goals_tac [CFun_def]),
    62         (rtac Rep_Cfun 1)
    62         (rtac Rep_Cfun 1)
    63         ]);
    63         ]);
    64 
    64 
    65 bind_thm ("monofun_fapp2", cont_fapp2 RS cont2mono);
    65 bind_thm ("monofun_Rep_CFun2", cont_Rep_CFun2 RS cont2mono);
    66 (* monofun(fapp(?fo1)) *)
    66 (* monofun(Rep_CFun(?fo1)) *)
    67 
    67 
    68 
    68 
    69 bind_thm ("contlub_fapp2", cont_fapp2 RS cont2contlub);
    69 bind_thm ("contlub_Rep_CFun2", cont_Rep_CFun2 RS cont2contlub);
    70 (* contlub(fapp(?fo1)) *)
    70 (* contlub(Rep_CFun(?fo1)) *)
    71 
    71 
    72 (* ------------------------------------------------------------------------ *)
    72 (* ------------------------------------------------------------------------ *)
    73 (* expanded thms cont_fapp2, contlub_fapp2                                 *)
    73 (* expanded thms cont_Rep_CFun2, contlub_Rep_CFun2                                 *)
    74 (* looks nice with mixfix syntac                                            *)
    74 (* looks nice with mixfix syntac                                            *)
    75 (* ------------------------------------------------------------------------ *)
    75 (* ------------------------------------------------------------------------ *)
    76 
    76 
    77 bind_thm ("cont_cfun_arg", (cont_fapp2 RS contE RS spec RS mp));
    77 bind_thm ("cont_cfun_arg", (cont_Rep_CFun2 RS contE RS spec RS mp));
    78 (* chain(?x1) ==> range (%i. ?fo3`(?x1 i)) <<| ?fo3`(lub (range ?x1))    *)
    78 (* chain(?x1) ==> range (%i. ?fo3`(?x1 i)) <<| ?fo3`(lub (range ?x1))    *)
    79  
    79  
    80 bind_thm ("contlub_cfun_arg", (contlub_fapp2 RS contlubE RS spec RS mp));
    80 bind_thm ("contlub_cfun_arg", (contlub_Rep_CFun2 RS contlubE RS spec RS mp));
    81 (* chain(?x1) ==> ?fo4`(lub (range ?x1)) = lub (range (%i. ?fo4`(?x1 i))) *)
    81 (* chain(?x1) ==> ?fo4`(lub (range ?x1)) = lub (range (%i. ?fo4`(?x1 i))) *)
    82 
    82 
    83 
    83 
    84 (* ------------------------------------------------------------------------ *)
    84 (* ------------------------------------------------------------------------ *)
    85 (* fapp is monotone in its 'first' argument                                 *)
    85 (* Rep_CFun is monotone in its 'first' argument                                 *)
    86 (* ------------------------------------------------------------------------ *)
    86 (* ------------------------------------------------------------------------ *)
    87 
    87 
    88 qed_goalw "monofun_fapp1" thy [monofun] "monofun(fapp)"
    88 qed_goalw "monofun_Rep_CFun1" thy [monofun] "monofun(Rep_CFun)"
    89 (fn prems =>
    89 (fn prems =>
    90         [
    90         [
    91         (strip_tac 1),
    91         (strip_tac 1),
    92         (etac (less_cfun RS subst) 1)
    92         (etac (less_cfun RS subst) 1)
    93         ]);
    93         ]);
    94 
    94 
    95 
    95 
    96 (* ------------------------------------------------------------------------ *)
    96 (* ------------------------------------------------------------------------ *)
    97 (* monotonicity of application fapp in mixfix syntax [_]_                   *)
    97 (* monotonicity of application Rep_CFun in mixfix syntax [_]_                   *)
    98 (* ------------------------------------------------------------------------ *)
    98 (* ------------------------------------------------------------------------ *)
    99 
    99 
   100 qed_goal "monofun_cfun_fun" thy  "f1 << f2 ==> f1`x << f2`x"
   100 qed_goal "monofun_cfun_fun" thy  "f1 << f2 ==> f1`x << f2`x"
   101 (fn prems =>
   101 (fn prems =>
   102         [
   102         [
   103         (cut_facts_tac prems 1),
   103         (cut_facts_tac prems 1),
   104         (res_inst_tac [("x","x")] spec 1),
   104         (res_inst_tac [("x","x")] spec 1),
   105         (rtac (less_fun RS subst) 1),
   105         (rtac (less_fun RS subst) 1),
   106         (etac (monofun_fapp1 RS monofunE RS spec RS spec RS mp) 1)
   106         (etac (monofun_Rep_CFun1 RS monofunE RS spec RS spec RS mp) 1)
   107         ]);
   107         ]);
   108 
   108 
   109 
   109 
   110 bind_thm ("monofun_cfun_arg", monofun_fapp2 RS monofunE RS spec RS spec RS mp);
   110 bind_thm ("monofun_cfun_arg", monofun_Rep_CFun2 RS monofunE RS spec RS spec RS mp);
   111 (* ?x2 << ?x1 ==> ?fo5`?x2 << ?fo5`?x1                                      *)
   111 (* ?x2 << ?x1 ==> ?fo5`?x2 << ?fo5`?x1                                      *)
   112 
   112 
   113 (* ------------------------------------------------------------------------ *)
   113 (* ------------------------------------------------------------------------ *)
   114 (* monotonicity of fapp in both arguments in mixfix syntax [_]_             *)
   114 (* monotonicity of Rep_CFun in both arguments in mixfix syntax [_]_             *)
   115 (* ------------------------------------------------------------------------ *)
   115 (* ------------------------------------------------------------------------ *)
   116 
   116 
   117 qed_goal "monofun_cfun" thy
   117 qed_goal "monofun_cfun" thy
   118         "[|f1<<f2;x1<<x2|] ==> f1`x1 << f2`x2"
   118         "[|f1<<f2;x1<<x2|] ==> f1`x1 << f2`x2"
   119 (fn prems =>
   119 (fn prems =>
   135 (* ------------------------------------------------------------------------ *)
   135 (* ------------------------------------------------------------------------ *)
   136 (* ch2ch - rules for the type 'a -> 'b                                      *)
   136 (* ch2ch - rules for the type 'a -> 'b                                      *)
   137 (* use MF2 lemmas from Cont.ML                                              *)
   137 (* use MF2 lemmas from Cont.ML                                              *)
   138 (* ------------------------------------------------------------------------ *)
   138 (* ------------------------------------------------------------------------ *)
   139 
   139 
   140 qed_goal "ch2ch_fappR" thy 
   140 qed_goal "ch2ch_Rep_CFunR" thy 
   141  "chain(Y) ==> chain(%i. f`(Y i))"
   141  "chain(Y) ==> chain(%i. f`(Y i))"
   142 (fn prems =>
   142 (fn prems =>
   143         [
   143         [
   144         (cut_facts_tac prems 1),
   144         (cut_facts_tac prems 1),
   145         (etac (monofun_fapp2 RS ch2ch_MF2R) 1)
   145         (etac (monofun_Rep_CFun2 RS ch2ch_MF2R) 1)
   146         ]);
   146         ]);
   147 
   147 
   148 
   148 
   149 bind_thm ("ch2ch_fappL", monofun_fapp1 RS ch2ch_MF2L);
   149 bind_thm ("ch2ch_Rep_CFunL", monofun_Rep_CFun1 RS ch2ch_MF2L);
   150 (* chain(?F) ==> chain (%i. ?F i`?x)                                  *)
   150 (* chain(?F) ==> chain (%i. ?F i`?x)                                  *)
   151 
   151 
   152 
   152 
   153 (* ------------------------------------------------------------------------ *)
   153 (* ------------------------------------------------------------------------ *)
   154 (*  the lub of a chain of continous functions is monotone                   *)
   154 (*  the lub of a chain of continous functions is monotone                   *)
   159         "chain(F) ==> monofun(% x. lub(range(% j.(F j)`x)))"
   159         "chain(F) ==> monofun(% x. lub(range(% j.(F j)`x)))"
   160 (fn prems =>
   160 (fn prems =>
   161         [
   161         [
   162         (cut_facts_tac prems 1),
   162         (cut_facts_tac prems 1),
   163         (rtac lub_MF2_mono 1),
   163         (rtac lub_MF2_mono 1),
   164         (rtac monofun_fapp1 1),
   164         (rtac monofun_Rep_CFun1 1),
   165         (rtac (monofun_fapp2 RS allI) 1),
   165         (rtac (monofun_Rep_CFun2 RS allI) 1),
   166         (atac 1)
   166         (atac 1)
   167         ]);
   167         ]);
   168 
   168 
   169 (* ------------------------------------------------------------------------ *)
   169 (* ------------------------------------------------------------------------ *)
   170 (* a lemma about the exchange of lubs for type 'a -> 'b                     *)
   170 (* a lemma about the exchange of lubs for type 'a -> 'b                     *)
   177 \               lub(range(%i. lub(range(%j. F(j)`(Y i)))))"
   177 \               lub(range(%i. lub(range(%j. F(j)`(Y i)))))"
   178 (fn prems =>
   178 (fn prems =>
   179         [
   179         [
   180         (cut_facts_tac prems 1),
   180         (cut_facts_tac prems 1),
   181         (rtac ex_lubMF2 1),
   181         (rtac ex_lubMF2 1),
   182         (rtac monofun_fapp1 1),
   182         (rtac monofun_Rep_CFun1 1),
   183         (rtac (monofun_fapp2 RS allI) 1),
   183         (rtac (monofun_Rep_CFun2 RS allI) 1),
   184         (atac 1),
   184         (atac 1),
   185         (atac 1)
   185         (atac 1)
   186         ]);
   186         ]);
   187 
   187 
   188 (* ------------------------------------------------------------------------ *)
   188 (* ------------------------------------------------------------------------ *)
   219         (rtac allI 1),
   219         (rtac allI 1),
   220         (stac less_cfun 1),
   220         (stac less_cfun 1),
   221         (stac Abs_Cfun_inverse2 1),
   221         (stac Abs_Cfun_inverse2 1),
   222         (etac cont_lubcfun 1),
   222         (etac cont_lubcfun 1),
   223         (rtac (lub_fun RS is_lubE RS conjunct1 RS ub_rangeE RS spec) 1),
   223         (rtac (lub_fun RS is_lubE RS conjunct1 RS ub_rangeE RS spec) 1),
   224         (etac (monofun_fapp1 RS ch2ch_monofun) 1),
   224         (etac (monofun_Rep_CFun1 RS ch2ch_monofun) 1),
   225         (strip_tac 1),
   225         (strip_tac 1),
   226         (stac less_cfun 1),
   226         (stac less_cfun 1),
   227         (stac Abs_Cfun_inverse2 1),
   227         (stac Abs_Cfun_inverse2 1),
   228         (etac cont_lubcfun 1),
   228         (etac cont_lubcfun 1),
   229         (rtac (lub_fun RS is_lubE RS conjunct2 RS spec RS mp) 1),
   229         (rtac (lub_fun RS is_lubE RS conjunct2 RS spec RS mp) 1),
   230         (etac (monofun_fapp1 RS ch2ch_monofun) 1),
   230         (etac (monofun_Rep_CFun1 RS ch2ch_monofun) 1),
   231         (etac (monofun_fapp1 RS ub2ub_monofun) 1)
   231         (etac (monofun_Rep_CFun1 RS ub2ub_monofun) 1)
   232         ]);
   232         ]);
   233 
   233 
   234 bind_thm ("thelub_cfun", lub_cfun RS thelubI);
   234 bind_thm ("thelub_cfun", lub_cfun RS thelubI);
   235 (* 
   235 (* 
   236 chain(?CCF1) ==>  lub (range ?CCF1) = (LAM x. lub (range (%i. ?CCF1 i`x)))
   236 chain(?CCF1) ==>  lub (range ?CCF1) = (LAM x. lub (range (%i. ?CCF1 i`x)))
   253 qed_goal "ext_cfun" Cfun1.thy "(!!x. f`x = g`x) ==> f = g"
   253 qed_goal "ext_cfun" Cfun1.thy "(!!x. f`x = g`x) ==> f = g"
   254  (fn prems =>
   254  (fn prems =>
   255         [
   255         [
   256         (res_inst_tac [("t","f")] (Rep_Cfun_inverse RS subst) 1),
   256         (res_inst_tac [("t","f")] (Rep_Cfun_inverse RS subst) 1),
   257         (res_inst_tac [("t","g")] (Rep_Cfun_inverse RS subst) 1),
   257         (res_inst_tac [("t","g")] (Rep_Cfun_inverse RS subst) 1),
   258         (res_inst_tac [("f","fabs")] arg_cong 1),
   258         (res_inst_tac [("f","Abs_CFun")] arg_cong 1),
   259         (rtac ext 1),
   259         (rtac ext 1),
   260         (resolve_tac prems 1)
   260         (resolve_tac prems 1)
   261         ]);
   261         ]);
   262 
   262 
   263 (* ------------------------------------------------------------------------ *)
   263 (* ------------------------------------------------------------------------ *)
   264 (* Monotonicity of fabs                                                     *)
   264 (* Monotonicity of Abs_CFun                                                     *)
   265 (* ------------------------------------------------------------------------ *)
   265 (* ------------------------------------------------------------------------ *)
   266 
   266 
   267 qed_goal "semi_monofun_fabs" thy 
   267 qed_goal "semi_monofun_Abs_CFun" thy 
   268         "[|cont(f);cont(g);f<<g|]==>fabs(f)<<fabs(g)"
   268         "[|cont(f);cont(g);f<<g|]==>Abs_CFun(f)<<Abs_CFun(g)"
   269  (fn prems =>
   269  (fn prems =>
   270         [
   270         [
   271         (rtac (less_cfun RS iffD2) 1),
   271         (rtac (less_cfun RS iffD2) 1),
   272         (stac Abs_Cfun_inverse2 1),
   272         (stac Abs_Cfun_inverse2 1),
   273         (resolve_tac prems 1),
   273         (resolve_tac prems 1),
   283 qed_goal "less_cfun2" thy "(!!x. f`x << g`x) ==> f << g"
   283 qed_goal "less_cfun2" thy "(!!x. f`x << g`x) ==> f << g"
   284  (fn prems =>
   284  (fn prems =>
   285         [
   285         [
   286         (res_inst_tac [("t","f")] (Rep_Cfun_inverse RS subst) 1),
   286         (res_inst_tac [("t","f")] (Rep_Cfun_inverse RS subst) 1),
   287         (res_inst_tac [("t","g")] (Rep_Cfun_inverse RS subst) 1),
   287         (res_inst_tac [("t","g")] (Rep_Cfun_inverse RS subst) 1),
   288         (rtac semi_monofun_fabs 1),
   288         (rtac semi_monofun_Abs_CFun 1),
   289         (rtac cont_fapp2 1),
   289         (rtac cont_Rep_CFun2 1),
   290         (rtac cont_fapp2 1),
   290         (rtac cont_Rep_CFun2 1),
   291         (rtac (less_fun RS iffD2) 1),
   291         (rtac (less_fun RS iffD2) 1),
   292         (rtac allI 1),
   292         (rtac allI 1),
   293         (resolve_tac prems 1)
   293         (resolve_tac prems 1)
   294         ]);
   294         ]);
   295 
   295