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); |