src/HOL/ex/Term.ML
changeset 1266 3ae9fe3c0f68
parent 972 e61b058d58d2
child 1465 5d7a7e439cec
equal deleted inserted replaced
1265:6ef9a9893fd6 1266:3ae9fe3c0f68
    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)"