69 (*Lemma: map works correctly on the underlying list of terms*) |
69 (*Lemma: map works correctly on the underlying list of terms*) |
70 val [major,ordi] = goal list.thy |
70 val [major,ordi] = goal list.thy |
71 "[| l: list(A); Ord(i) |] ==> \ |
71 "[| l: list(A); Ord(i) |] ==> \ |
72 \ rank(l)<i --> map(%z. (lam x:Vset(i).h(x)) ` z, l) = map(h,l)"; |
72 \ rank(l)<i --> map(%z. (lam x:Vset(i).h(x)) ` z, l) = map(h,l)"; |
73 by (rtac (major RS list.induct) 1); |
73 by (rtac (major RS list.induct) 1); |
74 by (simp_tac list_ss 1); |
74 by (Simp_tac 1); |
75 by (rtac impI 1); |
75 by (rtac impI 1); |
76 by (forward_tac [rank_Cons1 RS lt_trans] 1); |
76 by (forward_tac [rank_Cons1 RS lt_trans] 1); |
77 by (dtac (rank_Cons2 RS lt_trans) 1); |
77 by (dtac (rank_Cons2 RS lt_trans) 1); |
78 by (asm_simp_tac (list_ss addsimps [ordi, VsetI]) 1); |
78 by (asm_simp_tac (!simpset addsimps [ordi, VsetI]) 1); |
79 qed "map_lemma"; |
79 qed "map_lemma"; |
80 |
80 |
81 (*Typing premise is necessary to invoke map_lemma*) |
81 (*Typing premise is necessary to invoke map_lemma*) |
82 val [prem] = goal Term.thy |
82 val [prem] = goal Term.thy |
83 "ts: list(A) ==> \ |
83 "ts: list(A) ==> \ |
84 \ term_rec(Apply(a,ts), d) = d(a, ts, map (%z. term_rec(z,d), ts))"; |
84 \ term_rec(Apply(a,ts), d) = d(a, ts, map (%z. term_rec(z,d), ts))"; |
85 by (rtac (term_rec_def RS def_Vrec RS trans) 1); |
85 by (rtac (term_rec_def RS def_Vrec RS trans) 1); |
86 by (rewrite_goals_tac term.con_defs); |
86 by (rewrite_goals_tac term.con_defs); |
87 val term_rec_ss = ZF_ss addsimps [Ord_rank, rank_pair2, prem RS map_lemma]; |
87 by (simp_tac (!simpset addsimps [Ord_rank, rank_pair2, prem RS map_lemma]) 1);; |
88 by (simp_tac term_rec_ss 1); |
|
89 qed "term_rec"; |
88 qed "term_rec"; |
90 |
89 |
91 (*Slightly odd typing condition on r in the second premise!*) |
90 (*Slightly odd typing condition on r in the second premise!*) |
92 val major::prems = goal Term.thy |
91 val major::prems = goal Term.thy |
93 "[| t: term(A); \ |
92 "[| t: term(A); \ |
170 val term_typechecks = |
169 val term_typechecks = |
171 [term.Apply_I, term_map_type, term_map_type2, term_size_type, |
170 [term.Apply_I, term_map_type, term_map_type2, term_size_type, |
172 reflect_type, preorder_type]; |
171 reflect_type, preorder_type]; |
173 |
172 |
174 (*map_type2 and term_map_type2 instantiate variables*) |
173 (*map_type2 and term_map_type2 instantiate variables*) |
175 val term_ss = list_ss |
174 simpset := !simpset |
176 addsimps [term_rec, term_map, term_size, reflect, preorder] |
175 addsimps [term_rec, term_map, term_size, reflect, preorder] |
177 setsolver type_auto_tac (list_typechecks@term_typechecks); |
176 setsolver type_auto_tac (list_typechecks@term_typechecks); |
178 |
177 |
179 |
178 |
180 (** theorems about term_map **) |
179 (** theorems about term_map **) |
181 |
180 |
182 goal Term.thy "!!t A. t: term(A) ==> term_map(%u.u, t) = t"; |
181 goal Term.thy "!!t A. t: term(A) ==> term_map(%u.u, t) = t"; |
183 by (etac term_induct_eqn 1); |
182 by (etac term_induct_eqn 1); |
184 by (asm_simp_tac (term_ss addsimps [map_ident]) 1); |
183 by (asm_simp_tac (!simpset addsimps [map_ident]) 1); |
185 qed "term_map_ident"; |
184 qed "term_map_ident"; |
186 |
185 |
187 goal Term.thy |
186 goal Term.thy |
188 "!!t A. t: term(A) ==> term_map(f, term_map(g,t)) = term_map(%u.f(g(u)), t)"; |
187 "!!t A. t: term(A) ==> term_map(f, term_map(g,t)) = term_map(%u.f(g(u)), t)"; |
189 by (etac term_induct_eqn 1); |
188 by (etac term_induct_eqn 1); |
190 by (asm_simp_tac (term_ss addsimps [map_compose]) 1); |
189 by (asm_simp_tac (!simpset addsimps [map_compose]) 1); |
191 qed "term_map_compose"; |
190 qed "term_map_compose"; |
192 |
191 |
193 goal Term.thy |
192 goal Term.thy |
194 "!!t A. t: term(A) ==> term_map(f, reflect(t)) = reflect(term_map(f,t))"; |
193 "!!t A. t: term(A) ==> term_map(f, reflect(t)) = reflect(term_map(f,t))"; |
195 by (etac term_induct_eqn 1); |
194 by (etac term_induct_eqn 1); |
196 by (asm_simp_tac (term_ss addsimps [rev_map_distrib RS sym, map_compose]) 1); |
195 by (asm_simp_tac (!simpset addsimps [rev_map_distrib RS sym, map_compose]) 1); |
197 qed "term_map_reflect"; |
196 qed "term_map_reflect"; |
198 |
197 |
199 |
198 |
200 (** theorems about term_size **) |
199 (** theorems about term_size **) |
201 |
200 |
202 goal Term.thy |
201 goal Term.thy |
203 "!!t A. t: term(A) ==> term_size(term_map(f,t)) = term_size(t)"; |
202 "!!t A. t: term(A) ==> term_size(term_map(f,t)) = term_size(t)"; |
204 by (etac term_induct_eqn 1); |
203 by (etac term_induct_eqn 1); |
205 by (asm_simp_tac (term_ss addsimps [map_compose]) 1); |
204 by (asm_simp_tac (!simpset addsimps [map_compose]) 1); |
206 qed "term_size_term_map"; |
205 qed "term_size_term_map"; |
207 |
206 |
208 goal Term.thy "!!t A. t: term(A) ==> term_size(reflect(t)) = term_size(t)"; |
207 goal Term.thy "!!t A. t: term(A) ==> term_size(reflect(t)) = term_size(t)"; |
209 by (etac term_induct_eqn 1); |
208 by (etac term_induct_eqn 1); |
210 by (asm_simp_tac (term_ss addsimps [rev_map_distrib RS sym, map_compose, |
209 by (asm_simp_tac (!simpset addsimps [rev_map_distrib RS sym, map_compose, |
211 list_add_rev]) 1); |
210 list_add_rev]) 1); |
212 qed "term_size_reflect"; |
211 qed "term_size_reflect"; |
213 |
212 |
214 goal Term.thy "!!t A. t: term(A) ==> term_size(t) = length(preorder(t))"; |
213 goal Term.thy "!!t A. t: term(A) ==> term_size(t) = length(preorder(t))"; |
215 by (etac term_induct_eqn 1); |
214 by (etac term_induct_eqn 1); |
216 by (asm_simp_tac (term_ss addsimps [length_flat, map_compose]) 1); |
215 by (asm_simp_tac (!simpset addsimps [length_flat, map_compose]) 1); |
217 qed "term_size_length"; |
216 qed "term_size_length"; |
218 |
217 |
219 |
218 |
220 (** theorems about reflect **) |
219 (** theorems about reflect **) |
221 |
220 |
222 goal Term.thy "!!t A. t: term(A) ==> reflect(reflect(t)) = t"; |
221 goal Term.thy "!!t A. t: term(A) ==> reflect(reflect(t)) = t"; |
223 by (etac term_induct_eqn 1); |
222 by (etac term_induct_eqn 1); |
224 by (asm_simp_tac (term_ss addsimps [rev_map_distrib, map_compose, |
223 by (asm_simp_tac (!simpset addsimps [rev_map_distrib, map_compose, |
225 map_ident, rev_rev_ident]) 1); |
224 map_ident, rev_rev_ident]) 1); |
226 qed "reflect_reflect_ident"; |
225 qed "reflect_reflect_ident"; |
227 |
226 |
228 |
227 |
229 (** theorems about preorder **) |
228 (** theorems about preorder **) |
230 |
229 |
231 goal Term.thy |
230 goal Term.thy |
232 "!!t A. t: term(A) ==> preorder(term_map(f,t)) = map(f, preorder(t))"; |
231 "!!t A. t: term(A) ==> preorder(term_map(f,t)) = map(f, preorder(t))"; |
233 by (etac term_induct_eqn 1); |
232 by (etac term_induct_eqn 1); |
234 by (asm_simp_tac (term_ss addsimps [map_compose, map_flat]) 1); |
233 by (asm_simp_tac (!simpset addsimps [map_compose, map_flat]) 1); |
235 qed "preorder_term_map"; |
234 qed "preorder_term_map"; |
236 |
235 |
237 (** preorder(reflect(t)) = rev(postorder(t)) **) |
236 (** preorder(reflect(t)) = rev(postorder(t)) **) |
238 |
237 |
239 writeln"Reached end of file."; |
238 writeln"Reached end of file."; |