src/ZF/ex/LList.ML
changeset 782 200a16083201
parent 760 f0200e91b272
child 1461 6bcb44e4d6e5
equal deleted inserted replaced
781:9ab8873bf9b3 782:200a16083201
    18 goal LList.thy "llist(A) = {0} <+> (A <*> llist(A))";
    18 goal LList.thy "llist(A) = {0} <+> (A <*> llist(A))";
    19 let open llist;  val rew = rewrite_rule con_defs in  
    19 let open llist;  val rew = rewrite_rule con_defs in  
    20 by (fast_tac (qsum_cs addSIs (equalityI :: map rew intrs)
    20 by (fast_tac (qsum_cs addSIs (equalityI :: map rew intrs)
    21                       addEs [rew elim]) 1)
    21                       addEs [rew elim]) 1)
    22 end;
    22 end;
    23 val llist_unfold = result();
    23 qed "llist_unfold";
    24 
    24 
    25 (*** Lemmas to justify using "llist" in other recursive type definitions ***)
    25 (*** Lemmas to justify using "llist" in other recursive type definitions ***)
    26 
    26 
    27 goalw LList.thy llist.defs "!!A B. A<=B ==> llist(A) <= llist(B)";
    27 goalw LList.thy llist.defs "!!A B. A<=B ==> llist(A) <= llist(B)";
    28 by (rtac gfp_mono 1);
    28 by (rtac gfp_mono 1);
    29 by (REPEAT (rtac llist.bnd_mono 1));
    29 by (REPEAT (rtac llist.bnd_mono 1));
    30 by (REPEAT (ares_tac (quniv_mono::basic_monos) 1));
    30 by (REPEAT (ares_tac (quniv_mono::basic_monos) 1));
    31 val llist_mono = result();
    31 qed "llist_mono";
    32 
    32 
    33 (** Closure of quniv(A) under llist -- why so complex?  Its a gfp... **)
    33 (** Closure of quniv(A) under llist -- why so complex?  Its a gfp... **)
    34 
    34 
    35 val quniv_cs = subset_cs addSIs [QPair_Int_Vset_subset_UN RS subset_trans, 
    35 val quniv_cs = subset_cs addSIs [QPair_Int_Vset_subset_UN RS subset_trans, 
    36 				 QPair_subset_univ,
    36 				 QPair_subset_univ,
    48 (*LNil case*)
    48 (*LNil case*)
    49 by (fast_tac quniv_cs 1);
    49 by (fast_tac quniv_cs 1);
    50 (*LCons case*)
    50 (*LCons case*)
    51 by (safe_tac quniv_cs);
    51 by (safe_tac quniv_cs);
    52 by (ALLGOALS (fast_tac (quniv_cs addSEs [Ord_trans, make_elim bspec])));
    52 by (ALLGOALS (fast_tac (quniv_cs addSEs [Ord_trans, make_elim bspec])));
    53 val llist_quniv_lemma = result();
    53 qed "llist_quniv_lemma";
    54 
    54 
    55 goal LList.thy "llist(quniv(A)) <= quniv(A)";
    55 goal LList.thy "llist(quniv(A)) <= quniv(A)";
    56 by (rtac (qunivI RS subsetI) 1);
    56 by (rtac (qunivI RS subsetI) 1);
    57 by (rtac Int_Vset_subset 1);
    57 by (rtac Int_Vset_subset 1);
    58 by (REPEAT (ares_tac [llist_quniv_lemma RS bspec] 1));
    58 by (REPEAT (ares_tac [llist_quniv_lemma RS bspec] 1));
    59 val llist_quniv = result();
    59 qed "llist_quniv";
    60 
    60 
    61 val llist_subset_quniv = standard
    61 bind_thm ("llist_subset_quniv",
    62     (llist_mono RS (llist_quniv RSN (2,subset_trans)));
    62     (llist_mono RS (llist_quniv RSN (2,subset_trans))));
    63 
    63 
    64 
    64 
    65 (*** Lazy List Equality: lleq ***)
    65 (*** Lazy List Equality: lleq ***)
    66 
    66 
    67 val lleq_cs = subset_cs
    67 val lleq_cs = subset_cs
    75 by (REPEAT (resolve_tac [allI, impI] 1));
    75 by (REPEAT (resolve_tac [allI, impI] 1));
    76 by (etac lleq.elim 1);
    76 by (etac lleq.elim 1);
    77 by (rewrite_goals_tac (QInr_def::llist.con_defs));
    77 by (rewrite_goals_tac (QInr_def::llist.con_defs));
    78 by (safe_tac lleq_cs);
    78 by (safe_tac lleq_cs);
    79 by (fast_tac (subset_cs addSEs [Ord_trans, make_elim bspec]) 1);
    79 by (fast_tac (subset_cs addSEs [Ord_trans, make_elim bspec]) 1);
    80 val lleq_Int_Vset_subset_lemma = result();
    80 qed "lleq_Int_Vset_subset_lemma";
    81 
    81 
    82 val lleq_Int_Vset_subset = standard
    82 bind_thm ("lleq_Int_Vset_subset",
    83 	(lleq_Int_Vset_subset_lemma RS spec RS spec RS mp);
    83 	(lleq_Int_Vset_subset_lemma RS spec RS spec RS mp));
    84 
    84 
    85 
    85 
    86 (*lleq(A) is a symmetric relation because qconverse(lleq(A)) is a fixedpoint*)
    86 (*lleq(A) is a symmetric relation because qconverse(lleq(A)) is a fixedpoint*)
    87 val [prem] = goal LList.thy "<l,l'> : lleq(A) ==> <l',l> : lleq(A)";
    87 val [prem] = goal LList.thy "<l,l'> : lleq(A) ==> <l',l> : lleq(A)";
    88 by (rtac (prem RS converseI RS lleq.coinduct) 1);
    88 by (rtac (prem RS converseI RS lleq.coinduct) 1);
    89 by (rtac (lleq.dom_subset RS converse_type) 1);
    89 by (rtac (lleq.dom_subset RS converse_type) 1);
    90 by (safe_tac converse_cs);
    90 by (safe_tac converse_cs);
    91 by (etac lleq.elim 1);
    91 by (etac lleq.elim 1);
    92 by (ALLGOALS (fast_tac qconverse_cs));
    92 by (ALLGOALS (fast_tac qconverse_cs));
    93 val lleq_symmetric = result();
    93 qed "lleq_symmetric";
    94 
    94 
    95 goal LList.thy "!!l l'. <l,l'> : lleq(A) ==> l=l'";
    95 goal LList.thy "!!l l'. <l,l'> : lleq(A) ==> l=l'";
    96 by (rtac equalityI 1);
    96 by (rtac equalityI 1);
    97 by (REPEAT (ares_tac [lleq_Int_Vset_subset RS Int_Vset_subset] 1
    97 by (REPEAT (ares_tac [lleq_Int_Vset_subset RS Int_Vset_subset] 1
    98      ORELSE etac lleq_symmetric 1));
    98      ORELSE etac lleq_symmetric 1));
    99 val lleq_implies_equal = result();
    99 qed "lleq_implies_equal";
   100 
   100 
   101 val [eqprem,lprem] = goal LList.thy
   101 val [eqprem,lprem] = goal LList.thy
   102     "[| l=l';  l: llist(A) |] ==> <l,l'> : lleq(A)";
   102     "[| l=l';  l: llist(A) |] ==> <l,l'> : lleq(A)";
   103 by (res_inst_tac [("X", "{<l,l>. l: llist(A)}")] lleq.coinduct 1);
   103 by (res_inst_tac [("X", "{<l,l>. l: llist(A)}")] lleq.coinduct 1);
   104 by (rtac (lprem RS RepFunI RS (eqprem RS subst)) 1);
   104 by (rtac (lprem RS RepFunI RS (eqprem RS subst)) 1);
   105 by (safe_tac qpair_cs);
   105 by (safe_tac qpair_cs);
   106 by (etac llist.elim 1);
   106 by (etac llist.elim 1);
   107 by (ALLGOALS (fast_tac pair_cs));
   107 by (ALLGOALS (fast_tac pair_cs));
   108 val equal_llist_implies_leq = result();
   108 qed "equal_llist_implies_leq";
   109 
   109 
   110 
   110 
   111 (*** Lazy List Functions ***)
   111 (*** Lazy List Functions ***)
   112 
   112 
   113 (*Examples of coinduction for type-checking and to prove llist equations*)
   113 (*Examples of coinduction for type-checking and to prove llist equations*)
   117 goalw LList.thy llist.con_defs "bnd_mono(univ(a), %l. LCons(a,l))";
   117 goalw LList.thy llist.con_defs "bnd_mono(univ(a), %l. LCons(a,l))";
   118 by (rtac bnd_monoI 1);
   118 by (rtac bnd_monoI 1);
   119 by (REPEAT (ares_tac [subset_refl, QInr_mono, QPair_mono] 2));
   119 by (REPEAT (ares_tac [subset_refl, QInr_mono, QPair_mono] 2));
   120 by (REPEAT (ares_tac [subset_refl, A_subset_univ, 
   120 by (REPEAT (ares_tac [subset_refl, A_subset_univ, 
   121 		      QInr_subset_univ, QPair_subset_univ] 1));
   121 		      QInr_subset_univ, QPair_subset_univ] 1));
   122 val lconst_fun_bnd_mono = result();
   122 qed "lconst_fun_bnd_mono";
   123 
   123 
   124 (* lconst(a) = LCons(a,lconst(a)) *)
   124 (* lconst(a) = LCons(a,lconst(a)) *)
   125 val lconst = standard 
   125 bind_thm ("lconst",
   126     ([lconst_def, lconst_fun_bnd_mono] MRS def_lfp_Tarski);
   126     ([lconst_def, lconst_fun_bnd_mono] MRS def_lfp_Tarski));
   127 
   127 
   128 val lconst_subset = lconst_def RS def_lfp_subset;
   128 val lconst_subset = lconst_def RS def_lfp_subset;
   129 
   129 
   130 val member_subset_Union_eclose = standard (arg_into_eclose RS Union_upper);
   130 bind_thm ("member_subset_Union_eclose", (arg_into_eclose RS Union_upper));
   131 
   131 
   132 goal LList.thy "!!a A. a : A ==> lconst(a) : quniv(A)";
   132 goal LList.thy "!!a A. a : A ==> lconst(a) : quniv(A)";
   133 by (rtac (lconst_subset RS subset_trans RS qunivI) 1);
   133 by (rtac (lconst_subset RS subset_trans RS qunivI) 1);
   134 by (etac (arg_into_eclose RS eclose_subset RS univ_mono) 1);
   134 by (etac (arg_into_eclose RS eclose_subset RS univ_mono) 1);
   135 val lconst_in_quniv = result();
   135 qed "lconst_in_quniv";
   136 
   136 
   137 goal LList.thy "!!a A. a:A ==> lconst(a): llist(A)";
   137 goal LList.thy "!!a A. a:A ==> lconst(a): llist(A)";
   138 by (rtac (singletonI RS llist.coinduct) 1);
   138 by (rtac (singletonI RS llist.coinduct) 1);
   139 by (etac (lconst_in_quniv RS singleton_subsetI) 1);
   139 by (etac (lconst_in_quniv RS singleton_subsetI) 1);
   140 by (fast_tac (ZF_cs addSIs [lconst]) 1);
   140 by (fast_tac (ZF_cs addSIs [lconst]) 1);
   141 val lconst_type = result();
   141 qed "lconst_type";
   142 
   142 
   143 (*** flip --- equations merely assumed; certain consequences proved ***)
   143 (*** flip --- equations merely assumed; certain consequences proved ***)
   144 
   144 
   145 val flip_ss = ZF_ss addsimps [flip_LNil, flip_LCons, not_type];
   145 val flip_ss = ZF_ss addsimps [flip_LNil, flip_LCons, not_type];
   146 
   146 
   147 goal QUniv.thy "!!b. b:bool ==> b Int X <= univ(eclose(A))";
   147 goal QUniv.thy "!!b. b:bool ==> b Int X <= univ(eclose(A))";
   148 by (fast_tac (quniv_cs addSEs [boolE]) 1);
   148 by (fast_tac (quniv_cs addSEs [boolE]) 1);
   149 val bool_Int_subset_univ = result();
   149 qed "bool_Int_subset_univ";
   150 
   150 
   151 val flip_cs = quniv_cs addSIs [not_type]
   151 val flip_cs = quniv_cs addSIs [not_type]
   152                        addIs  [bool_Int_subset_univ];
   152                        addIs  [bool_Int_subset_univ];
   153 
   153 
   154 (*Reasoning borrowed from lleq.ML; a similar proof works for all
   154 (*Reasoning borrowed from lleq.ML; a similar proof works for all
   165 (*LNil case*)
   165 (*LNil case*)
   166 by (fast_tac flip_cs 1);
   166 by (fast_tac flip_cs 1);
   167 (*LCons case*)
   167 (*LCons case*)
   168 by (safe_tac flip_cs);
   168 by (safe_tac flip_cs);
   169 by (ALLGOALS (fast_tac (flip_cs addSEs [Ord_trans, make_elim bspec])));
   169 by (ALLGOALS (fast_tac (flip_cs addSEs [Ord_trans, make_elim bspec])));
   170 val flip_llist_quniv_lemma = result();
   170 qed "flip_llist_quniv_lemma";
   171 
   171 
   172 goal LList.thy "!!l. l: llist(bool) ==> flip(l) : quniv(bool)";
   172 goal LList.thy "!!l. l: llist(bool) ==> flip(l) : quniv(bool)";
   173 by (rtac (flip_llist_quniv_lemma RS bspec RS Int_Vset_subset RS qunivI) 1);
   173 by (rtac (flip_llist_quniv_lemma RS bspec RS Int_Vset_subset RS qunivI) 1);
   174 by (REPEAT (assume_tac 1));
   174 by (REPEAT (assume_tac 1));
   175 val flip_in_quniv = result();
   175 qed "flip_in_quniv";
   176 
   176 
   177 val [prem] = goal LList.thy "l : llist(bool) ==> flip(l): llist(bool)";
   177 val [prem] = goal LList.thy "l : llist(bool) ==> flip(l): llist(bool)";
   178 by (res_inst_tac [("X", "{flip(l) . l:llist(bool)}")]
   178 by (res_inst_tac [("X", "{flip(l) . l:llist(bool)}")]
   179        llist.coinduct 1);
   179        llist.coinduct 1);
   180 by (rtac (prem RS RepFunI) 1);
   180 by (rtac (prem RS RepFunI) 1);
   195 by (etac RepFunE 1);
   195 by (etac RepFunE 1);
   196 by (etac llist.elim 1);
   196 by (etac llist.elim 1);
   197 by (asm_simp_tac flip_ss 1);
   197 by (asm_simp_tac flip_ss 1);
   198 by (asm_simp_tac (flip_ss addsimps [flip_type, not_not]) 1);
   198 by (asm_simp_tac (flip_ss addsimps [flip_type, not_not]) 1);
   199 by (fast_tac (ZF_cs addSIs [not_type]) 1);
   199 by (fast_tac (ZF_cs addSIs [not_type]) 1);
   200 val flip_flip = result();
   200 qed "flip_flip";