58 by (REPEAT (ares_tac prems 1)); |
58 by (REPEAT (ares_tac prems 1)); |
59 qed "Term_induct2"; |
59 qed "Term_induct2"; |
60 |
60 |
61 (*** Structural Induction on the abstract type 'a term ***) |
61 (*** Structural Induction on the abstract type 'a term ***) |
62 |
62 |
63 val list_all_ss = map_ss addsimps [list_all_Nil, list_all_Cons]; |
|
64 |
|
65 val Rep_term_in_sexp = |
63 val Rep_term_in_sexp = |
66 Rep_term RS (range_Leaf_subset_sexp RS term_subset_sexp RS subsetD); |
64 Rep_term RS (range_Leaf_subset_sexp RS term_subset_sexp RS subsetD); |
67 |
65 |
68 (*Induction for the abstract type 'a term*) |
66 (*Induction for the abstract type 'a term*) |
69 val prems = goalw Term.thy [App_def,Rep_Tlist_def,Abs_Tlist_def] |
67 val prems = goalw Term.thy [App_def,Rep_Tlist_def,Abs_Tlist_def] |
87 by (stac Abs_map_CONS 2); |
85 by (stac Abs_map_CONS 2); |
88 by (etac conjunct1 2); |
86 by (etac conjunct1 2); |
89 by (etac rev_subsetD 2); |
87 by (etac rev_subsetD 2); |
90 by (rtac list_subset_sexp 2); |
88 by (rtac list_subset_sexp 2); |
91 by (fast_tac set_cs 2); |
89 by (fast_tac set_cs 2); |
92 by (ALLGOALS (asm_simp_tac list_all_ss)); |
90 by (ALLGOALS Asm_simp_tac); |
93 qed "term_induct"; |
91 qed "term_induct"; |
94 |
92 |
95 (*Induction for the abstract type 'a term*) |
93 (*Induction for the abstract type 'a term*) |
96 val prems = goal Term.thy |
94 val prems = goal Term.thy |
97 "[| !!x. R(App x Nil); \ |
95 "[| !!x. R(App x Nil); \ |
98 \ !!x t ts. R(App x ts) ==> R(App x (t#ts)) \ |
96 \ !!x t ts. R(App x ts) ==> R(App x (t#ts)) \ |
99 \ |] ==> R(t)"; |
97 \ |] ==> R(t)"; |
100 by (rtac term_induct 1); (*types force good instantiation*) |
98 by (rtac term_induct 1); (*types force good instantiation*) |
101 by (etac rev_mp 1); |
99 by (etac rev_mp 1); |
102 by (rtac list_induct 1); (*types force good instantiation*) |
100 by (rtac list_induct2 1); (*types force good instantiation*) |
103 by (ALLGOALS (asm_simp_tac (list_all_ss addsimps prems))); |
101 by (ALLGOALS (asm_simp_tac (!simpset addsimps prems))); |
104 qed "term_induct2"; |
102 qed "term_induct2"; |
105 |
103 |
106 (*Perform induction on xs. *) |
104 (*Perform induction on xs. *) |
107 fun term_ind2_tac a i = |
105 fun term_ind2_tac a i = |
108 EVERY [res_inst_tac [("t",a)] term_induct2 i, |
106 EVERY [res_inst_tac [("t",a)] term_induct2 i, |
121 "N: list(term(A)) ==> \ |
119 "N: list(term(A)) ==> \ |
122 \ !M. (N,M): pred_sexp^+ --> \ |
120 \ !M. (N,M): pred_sexp^+ --> \ |
123 \ Abs_map (cut h (pred_sexp^+) M) N = \ |
121 \ Abs_map (cut h (pred_sexp^+) M) N = \ |
124 \ Abs_map h N"; |
122 \ Abs_map h N"; |
125 by (rtac (prem RS list.induct) 1); |
123 by (rtac (prem RS list.induct) 1); |
126 by (simp_tac list_all_ss 1); |
124 by (Simp_tac 1); |
127 by (strip_tac 1); |
125 by (strip_tac 1); |
128 by (etac (pred_sexp_CONS_D RS conjE) 1); |
126 by (etac (pred_sexp_CONS_D RS conjE) 1); |
129 by (asm_simp_tac (list_all_ss addsimps [trancl_pred_sexpD1, cut_apply]) 1); |
127 by (asm_simp_tac (!simpset addsimps [trancl_pred_sexpD1]) 1); |
130 qed "Abs_map_lemma"; |
128 qed "Abs_map_lemma"; |
131 |
129 |
132 val [prem1,prem2,A_subset_sexp] = goal Term.thy |
130 val [prem1,prem2,A_subset_sexp] = goal Term.thy |
133 "[| M: sexp; N: list(term(A)); A<=sexp |] ==> \ |
131 "[| M: sexp; N: list(term(A)); A<=sexp |] ==> \ |
134 \ Term_rec (M$N) d = d M N (Abs_map (%Z. Term_rec Z d) N)"; |
132 \ Term_rec (M$N) d = d M N (Abs_map (%Z. Term_rec Z d) N)"; |
135 by (rtac (Term_rec_unfold RS trans) 1); |
133 by (rtac (Term_rec_unfold RS trans) 1); |
136 by (simp_tac (HOL_ss addsimps |
134 by (simp_tac (HOL_ss addsimps |
137 [Split, |
135 [Split, |
138 prem2 RS Abs_map_lemma RS spec RS mp, pred_sexpI2 RS r_into_trancl, |
136 prem2 RS Abs_map_lemma RS spec RS mp, pred_sexpI2 RS r_into_trancl, |
139 prem1, prem2 RS rev_subsetD, list_subset_sexp, |
137 prem1, prem2 RS rev_subsetD, list_subset_sexp, |
140 term_subset_sexp, A_subset_sexp])1); |
138 term_subset_sexp, A_subset_sexp]) 1); |
141 qed "Term_rec"; |
139 qed "Term_rec"; |
142 |
140 |
143 (*** term_rec -- by Term_rec ***) |
141 (*** term_rec -- by Term_rec ***) |
144 |
142 |
145 local |
143 local |
148 val Rep_Tlist = Rep_term RS Rep_map_type1; |
146 val Rep_Tlist = Rep_term RS Rep_map_type1; |
149 val Rep_Term_rec = range_Leaf_subset_sexp RSN (2,Rep_Tlist RSN(2,Term_rec)); |
147 val Rep_Term_rec = range_Leaf_subset_sexp RSN (2,Rep_Tlist RSN(2,Term_rec)); |
150 |
148 |
151 (*Now avoids conditional rewriting with the premise N: list(term(A)), |
149 (*Now avoids conditional rewriting with the premise N: list(term(A)), |
152 since A will be uninstantiated and will cause rewriting to fail. *) |
150 since A will be uninstantiated and will cause rewriting to fail. *) |
153 val term_rec_ss = HOL_ss |
151 val term_rec_ss = HOL_ss |
154 addsimps [Rep_Tlist RS (rangeI RS term.APP_I RS Abs_term_inverse), |
152 addsimps [Rep_Tlist RS (rangeI RS term.APP_I RS Abs_term_inverse), |
155 Rep_term_in_sexp, Rep_Term_rec, Rep_term_inverse, |
153 Rep_term_in_sexp, Rep_Term_rec, Rep_term_inverse, inj_Leaf, |
156 inj_Leaf, Inv_f_f, |
154 Inv_f_f, Abs_Rep_map, map_ident2, sexp.LeafI] |
157 Abs_Rep_map, map_ident, sexp.LeafI] |
|
158 in |
155 in |
159 |
156 |
160 val term_rec = prove_goalw Term.thy |
157 val term_rec = prove_goalw Term.thy |
161 [term_rec_def, App_def, Rep_Tlist_def, Abs_Tlist_def] |
158 [term_rec_def, App_def, Rep_Tlist_def, Abs_Tlist_def] |
162 "term_rec (App f ts) d = d f ts (map (%t. term_rec t d) ts)" |
159 "term_rec (App f ts) d = d f ts (map (%t. term_rec t d) ts)" |