14 by (fast_tac (claset() addSIs (map rew intrs) addEs [rew elim]) 1) |
14 by (fast_tac (claset() addSIs (map rew intrs) addEs [rew elim]) 1) |
15 end; |
15 end; |
16 qed "term_unfold"; |
16 qed "term_unfold"; |
17 |
17 |
18 (*Induction on term(A) followed by induction on List *) |
18 (*Induction on term(A) followed by induction on List *) |
19 val major::prems = goal Term.thy |
19 val major::prems = Goal |
20 "[| t: term(A); \ |
20 "[| t: term(A); \ |
21 \ !!x. [| x: A |] ==> P(Apply(x,Nil)); \ |
21 \ !!x. [| x: A |] ==> P(Apply(x,Nil)); \ |
22 \ !!x z zs. [| x: A; z: term(A); zs: list(term(A)); P(Apply(x,zs)) \ |
22 \ !!x z zs. [| x: A; z: term(A); zs: list(term(A)); P(Apply(x,zs)) \ |
23 \ |] ==> P(Apply(x, Cons(z,zs))) \ |
23 \ |] ==> P(Apply(x, Cons(z,zs))) \ |
24 \ |] ==> P(t)"; |
24 \ |] ==> P(t)"; |
27 by (etac CollectE 2); |
27 by (etac CollectE 2); |
28 by (REPEAT (ares_tac (prems@[list_CollectD]) 1)); |
28 by (REPEAT (ares_tac (prems@[list_CollectD]) 1)); |
29 qed "term_induct2"; |
29 qed "term_induct2"; |
30 |
30 |
31 (*Induction on term(A) to prove an equation*) |
31 (*Induction on term(A) to prove an equation*) |
32 val major::prems = goal Term.thy |
32 val major::prems = Goal |
33 "[| t: term(A); \ |
33 "[| t: term(A); \ |
34 \ !!x zs. [| x: A; zs: list(term(A)); map(f,zs) = map(g,zs) |] ==> \ |
34 \ !!x zs. [| x: A; zs: list(term(A)); map(f,zs) = map(g,zs) |] ==> \ |
35 \ f(Apply(x,zs)) = g(Apply(x,zs)) \ |
35 \ f(Apply(x,zs)) = g(Apply(x,zs)) \ |
36 \ |] ==> f(t)=g(t)"; |
36 \ |] ==> f(t)=g(t)"; |
37 by (rtac (major RS term.induct) 1); |
37 by (rtac (major RS term.induct) 1); |
64 |
64 |
65 |
65 |
66 (*** term_rec -- by Vset recursion ***) |
66 (*** term_rec -- by Vset recursion ***) |
67 |
67 |
68 (*Lemma: map works correctly on the underlying list of terms*) |
68 (*Lemma: map works correctly on the underlying list of terms*) |
69 val [major,ordi] = goal list.thy |
69 Goal "[| l: list(A); Ord(i) |] ==> \ |
70 "[| l: list(A); Ord(i) |] ==> \ |
70 \ rank(l)<i --> map(%z. (lam x:Vset(i).h(x)) ` z, l) = map(h,l)"; |
71 \ rank(l)<i --> map(%z. (lam x:Vset(i).h(x)) ` z, l) = map(h,l)"; |
71 by (etac list.induct 1); |
72 by (rtac (major RS list.induct) 1); |
|
73 by (Simp_tac 1); |
72 by (Simp_tac 1); |
74 by (rtac impI 1); |
73 by (rtac impI 1); |
75 by (forward_tac [rank_Cons1 RS lt_trans] 1); |
74 by (subgoal_tac "rank(a)<i & rank(l) < i" 1); |
76 by (dtac (rank_Cons2 RS lt_trans) 1); |
75 by (asm_simp_tac (simpset() addsimps [VsetI]) 1); |
77 by (asm_simp_tac (simpset() addsimps [ordi, VsetI]) 1); |
76 by (full_simp_tac (simpset() addsimps list.con_defs) 1); |
|
77 by (blast_tac (claset() addDs (rank_rls RL [lt_trans])) 1); |
78 qed "map_lemma"; |
78 qed "map_lemma"; |
79 |
79 |
80 (*Typing premise is necessary to invoke map_lemma*) |
80 (*Typing premise is necessary to invoke map_lemma*) |
81 val [prem] = goal Term.thy |
81 Goal "ts: list(A) ==> \ |
82 "ts: list(A) ==> \ |
82 \ term_rec(Apply(a,ts), d) = d(a, ts, map (%z. term_rec(z,d), ts))"; |
83 \ term_rec(Apply(a,ts), d) = d(a, ts, map (%z. term_rec(z,d), ts))"; |
|
84 by (rtac (term_rec_def RS def_Vrec RS trans) 1); |
83 by (rtac (term_rec_def RS def_Vrec RS trans) 1); |
85 by (rewrite_goals_tac term.con_defs); |
84 by (rewrite_goals_tac term.con_defs); |
86 by (simp_tac (simpset() addsimps [Ord_rank, rank_pair2, prem RS map_lemma]) 1);; |
85 by (asm_simp_tac (simpset() addsimps [Ord_rank, rank_pair2, map_lemma]) 1);; |
87 qed "term_rec"; |
86 qed "term_rec"; |
88 |
87 |
89 (*Slightly odd typing condition on r in the second premise!*) |
88 (*Slightly odd typing condition on r in the second premise!*) |
90 val major::prems = goal Term.thy |
89 val major::prems = Goal |
91 "[| t: term(A); \ |
90 "[| t: term(A); \ |
92 \ !!x zs r. [| x: A; zs: list(term(A)); \ |
91 \ !!x zs r. [| x: A; zs: list(term(A)); \ |
93 \ r: list(UN t:term(A). C(t)) |] \ |
92 \ r: list(UN t:term(A). C(t)) |] \ |
94 \ ==> d(x, zs, r): C(Apply(x,zs)) \ |
93 \ ==> d(x, zs, r): C(Apply(x,zs)) \ |
95 \ |] ==> term_rec(t,d) : C(t)"; |
94 \ |] ==> term_rec(t,d) : C(t)"; |
101 by (ALLGOALS (asm_simp_tac (simpset() addsimps [term_rec]))); |
100 by (ALLGOALS (asm_simp_tac (simpset() addsimps [term_rec]))); |
102 by (etac CollectE 1); |
101 by (etac CollectE 1); |
103 by (REPEAT (ares_tac [list.Cons_I, UN_I] 1)); |
102 by (REPEAT (ares_tac [list.Cons_I, UN_I] 1)); |
104 qed "term_rec_type"; |
103 qed "term_rec_type"; |
105 |
104 |
106 val [rew,tslist] = goal Term.thy |
105 val [rew,tslist] = Goal |
107 "[| !!t. j(t)==term_rec(t,d); ts: list(A) |] ==> \ |
106 "[| !!t. j(t)==term_rec(t,d); ts: list(A) |] ==> \ |
108 \ j(Apply(a,ts)) = d(a, ts, map(%Z. j(Z), ts))"; |
107 \ j(Apply(a,ts)) = d(a, ts, map(%Z. j(Z), ts))"; |
109 by (rewtac rew); |
108 by (rewtac rew); |
110 by (rtac (tslist RS term_rec) 1); |
109 by (rtac (tslist RS term_rec) 1); |
111 qed "def_term_rec"; |
110 qed "def_term_rec"; |
112 |
111 |
113 val prems = goal Term.thy |
112 val prems = Goal |
114 "[| t: term(A); \ |
113 "[| t: term(A); \ |
115 \ !!x zs r. [| x: A; zs: list(term(A)); r: list(C) |] \ |
114 \ !!x zs r. [| x: A; zs: list(term(A)); r: list(C) |] \ |
116 \ ==> d(x, zs, r): C \ |
115 \ ==> d(x, zs, r): C \ |
117 \ |] ==> term_rec(t,d) : C"; |
116 \ |] ==> term_rec(t,d) : C"; |
118 by (REPEAT (ares_tac (term_rec_type::prems) 1)); |
117 by (REPEAT (ares_tac (term_rec_type::prems) 1)); |
122 |
121 |
123 (** term_map **) |
122 (** term_map **) |
124 |
123 |
125 bind_thm ("term_map", (term_map_def RS def_term_rec)); |
124 bind_thm ("term_map", (term_map_def RS def_term_rec)); |
126 |
125 |
127 val prems = goalw Term.thy [term_map_def] |
126 val prems = Goalw [term_map_def] |
128 "[| t: term(A); !!x. x: A ==> f(x): B |] ==> term_map(f,t) : term(B)"; |
127 "[| t: term(A); !!x. x: A ==> f(x): B |] ==> term_map(f,t) : term(B)"; |
129 by (REPEAT (ares_tac ([term_rec_simple_type, term.Apply_I] @ prems) 1)); |
128 by (REPEAT (ares_tac ([term_rec_simple_type, term.Apply_I] @ prems) 1)); |
130 qed "term_map_type"; |
129 qed "term_map_type"; |
131 |
130 |
132 val [major] = goal Term.thy |
131 Goal "t: term(A) ==> term_map(f,t) : term({f(u). u:A})"; |
133 "t: term(A) ==> term_map(f,t) : term({f(u). u:A})"; |
132 by (etac term_map_type 1); |
134 by (rtac (major RS term_map_type) 1); |
|
135 by (etac RepFunI 1); |
133 by (etac RepFunI 1); |
136 qed "term_map_type2"; |
134 qed "term_map_type2"; |
137 |
135 |
138 |
136 |
139 (** term_size **) |
137 (** term_size **) |