src/ZF/ex/Term.ML
changeset 2469 b50b8c0eec01
parent 2034 5079fdf938dd
child 2493 bdeb5024353a
equal deleted inserted replaced
2468:428efffe8599 2469:b50b8c0eec01
    50 
    50 
    51 (*Easily provable by induction also*)
    51 (*Easily provable by induction also*)
    52 goalw Term.thy (term.defs@term.con_defs) "term(univ(A)) <= univ(A)";
    52 goalw Term.thy (term.defs@term.con_defs) "term(univ(A)) <= univ(A)";
    53 by (rtac lfp_lowerbound 1);
    53 by (rtac lfp_lowerbound 1);
    54 by (rtac (A_subset_univ RS univ_mono) 2);
    54 by (rtac (A_subset_univ RS univ_mono) 2);
    55 by (safe_tac ZF_cs);
    55 by (safe_tac (!claset));
    56 by (REPEAT (ares_tac [Pair_in_univ, list_univ RS subsetD] 1));
    56 by (REPEAT (ares_tac [Pair_in_univ, list_univ RS subsetD] 1));
    57 qed "term_univ";
    57 qed "term_univ";
    58 
    58 
    59 val term_subset_univ = 
    59 val term_subset_univ = 
    60     term_mono RS (term_univ RSN (2,subset_trans)) |> standard;
    60     term_mono RS (term_univ RSN (2,subset_trans)) |> standard;
    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);                                     \
    98 by (rtac (major RS term.induct) 1);
    97 by (rtac (major RS term.induct) 1);
    99 by (forward_tac [list_CollectD] 1);
    98 by (forward_tac [list_CollectD] 1);
   100 by (stac term_rec 1);
    99 by (stac term_rec 1);
   101 by (REPEAT (ares_tac prems 1));
   100 by (REPEAT (ares_tac prems 1));
   102 by (etac list.induct 1);
   101 by (etac list.induct 1);
   103 by (ALLGOALS (asm_simp_tac (list_ss addsimps [term_rec])));
   102 by (ALLGOALS (asm_simp_tac (!simpset addsimps [term_rec])));
   104 by (etac CollectE 1);
   103 by (etac CollectE 1);
   105 by (REPEAT (ares_tac [list.Cons_I, UN_I] 1));
   104 by (REPEAT (ares_tac [list.Cons_I, UN_I] 1));
   106 qed "term_rec_type";
   105 qed "term_rec_type";
   107 
   106 
   108 val [rew,tslist] = goal Term.thy
   107 val [rew,tslist] = goal Term.thy
   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.";