src/ZF/indrule.ML
changeset 4352 7ac9f3e8a97d
parent 3939 83f908ed3c04
child 4804 02b7c759159b
equal deleted inserted replaced
4351:36b28f78ed1b 4352:7ac9f3e8a97d
    42    ind_alist = [(rec_tm1,pred1),...]  -- associates predicates with rec ops
    42    ind_alist = [(rec_tm1,pred1),...]  -- associates predicates with rec ops
    43    prem is a premise of an intr rule*)
    43    prem is a premise of an intr rule*)
    44 fun add_induct_prem ind_alist (prem as Const("Trueprop",_) $ 
    44 fun add_induct_prem ind_alist (prem as Const("Trueprop",_) $ 
    45                  (Const("op :",_)$t$X), iprems) =
    45                  (Const("op :",_)$t$X), iprems) =
    46      (case gen_assoc (op aconv) (ind_alist, X) of
    46      (case gen_assoc (op aconv) (ind_alist, X) of
    47           Some pred => prem :: Ind_Syntax.mk_tprop (pred $ t) :: iprems
    47           Some pred => prem :: FOLogic.mk_Trueprop (pred $ t) :: iprems
    48         | None => (*possibly membership in M(rec_tm), for M monotone*)
    48         | None => (*possibly membership in M(rec_tm), for M monotone*)
    49             let fun mk_sb (rec_tm,pred) = 
    49             let fun mk_sb (rec_tm,pred) = 
    50                         (rec_tm, Ind_Syntax.Collect_const$rec_tm$pred)
    50                         (rec_tm, Ind_Syntax.Collect_const$rec_tm$pred)
    51             in  subst_free (map mk_sb ind_alist) prem :: iprems  end)
    51             in  subst_free (map mk_sb ind_alist) prem :: iprems  end)
    52   | add_induct_prem ind_alist (prem,iprems) = prem :: iprems;
    52   | add_induct_prem ind_alist (prem,iprems) = prem :: iprems;
    56   let val quantfrees = map dest_Free (term_frees intr \\ rec_params)
    56   let val quantfrees = map dest_Free (term_frees intr \\ rec_params)
    57       val iprems = foldr (add_induct_prem ind_alist)
    57       val iprems = foldr (add_induct_prem ind_alist)
    58                          (Logic.strip_imp_prems intr,[])
    58                          (Logic.strip_imp_prems intr,[])
    59       val (t,X) = Ind_Syntax.rule_concl intr
    59       val (t,X) = Ind_Syntax.rule_concl intr
    60       val (Some pred) = gen_assoc (op aconv) (ind_alist, X)
    60       val (Some pred) = gen_assoc (op aconv) (ind_alist, X)
    61       val concl = Ind_Syntax.mk_tprop (pred $ t)
    61       val concl = FOLogic.mk_Trueprop (pred $ t)
    62   in list_all_free (quantfrees, Logic.list_implies (iprems,concl)) end
    62   in list_all_free (quantfrees, Logic.list_implies (iprems,concl)) end
    63   handle Bind => error"Recursion term not found in conclusion";
    63   handle Bind => error"Recursion term not found in conclusion";
    64 
    64 
    65 (*Reduces backtracking by delivering the correct premise to each goal.
    65 (*Reduces backtracking by delivering the correct premise to each goal.
    66   Intro rules with extra Vars in premises still cause some backtracking *)
    66   Intro rules with extra Vars in premises still cause some backtracking *)
    67 fun ind_tac [] 0 = all_tac
    67 fun ind_tac [] 0 = all_tac
    68   | ind_tac(prem::prems) i = 
    68   | ind_tac(prem::prems) i = 
    69         DEPTH_SOLVE_1 (ares_tac [prem, refl] i) THEN
    69         DEPTH_SOLVE_1 (ares_tac [prem, refl] i) THEN
    70         ind_tac prems (i-1);
    70         ind_tac prems (i-1);
    71 
    71 
    72 val pred = Free(pred_name, Ind_Syntax.iT --> Ind_Syntax.oT);
    72 val pred = Free(pred_name, Ind_Syntax.iT --> FOLogic.oT);
    73 
    73 
    74 val ind_prems = map (induct_prem (map (rpair pred) Inductive.rec_tms)) 
    74 val ind_prems = map (induct_prem (map (rpair pred) Inductive.rec_tms)) 
    75                     Inductive.intr_tms;
    75                     Inductive.intr_tms;
    76 
    76 
    77 (*Debugging code...
    77 (*Debugging code...
    90 
    90 
    91 val quant_induct = 
    91 val quant_induct = 
    92     prove_goalw_cterm part_rec_defs 
    92     prove_goalw_cterm part_rec_defs 
    93       (cterm_of sign 
    93       (cterm_of sign 
    94        (Logic.list_implies (ind_prems, 
    94        (Logic.list_implies (ind_prems, 
    95                 Ind_Syntax.mk_tprop (Ind_Syntax.mk_all_imp(big_rec_tm,pred)))))
    95                 FOLogic.mk_Trueprop (Ind_Syntax.mk_all_imp(big_rec_tm,pred)))))
    96       (fn prems =>
    96       (fn prems =>
    97        [rtac (impI RS allI) 1,
    97        [rtac (impI RS allI) 1,
    98         DETERM (etac Intr_elim.raw_induct 1),
    98         DETERM (etac Intr_elim.raw_induct 1),
    99         (*Push Part inside Collect*)
    99         (*Push Part inside Collect*)
   100         full_simp_tac (min_ss addsimps [Part_Collect]) 1,
   100         full_simp_tac (min_ss addsimps [Part_Collect]) 1,
   118   a summand 'domt' was also an argument, but this required the domain of
   118   a summand 'domt' was also an argument, but this required the domain of
   119   mutual recursion to invariably be a disjoint sum.*)
   119   mutual recursion to invariably be a disjoint sum.*)
   120 fun mk_predpair rec_tm = 
   120 fun mk_predpair rec_tm = 
   121   let val rec_name = (#1 o dest_Const o head_of) rec_tm
   121   let val rec_name = (#1 o dest_Const o head_of) rec_tm
   122       val pfree = Free(pred_name ^ "_" ^ Sign.base_name rec_name,
   122       val pfree = Free(pred_name ^ "_" ^ Sign.base_name rec_name,
   123                        elem_factors ---> Ind_Syntax.oT)
   123                        elem_factors ---> FOLogic.oT)
   124       val qconcl = 
   124       val qconcl = 
   125         foldr Ind_Syntax.mk_all 
   125         foldr FOLogic.mk_all
   126           (elem_frees, 
   126           (elem_frees, 
   127            Ind_Syntax.imp $ 
   127            FOLogic.imp $ 
   128            (Ind_Syntax.mem_const $ elem_tuple $ rec_tm)
   128            (Ind_Syntax.mem_const $ elem_tuple $ rec_tm)
   129                  $ (list_comb (pfree, elem_frees)))
   129                  $ (list_comb (pfree, elem_frees)))
   130   in  (CP.ap_split elem_type Ind_Syntax.oT pfree, 
   130   in  (CP.ap_split elem_type FOLogic.oT pfree, 
   131        qconcl)  
   131        qconcl)  
   132   end;
   132   end;
   133 
   133 
   134 val (preds,qconcls) = split_list (map mk_predpair Inductive.rec_tms);
   134 val (preds,qconcls) = split_list (map mk_predpair Inductive.rec_tms);
   135 
   135 
   136 (*Used to form simultaneous induction lemma*)
   136 (*Used to form simultaneous induction lemma*)
   137 fun mk_rec_imp (rec_tm,pred) = 
   137 fun mk_rec_imp (rec_tm,pred) = 
   138     Ind_Syntax.imp $ (Ind_Syntax.mem_const $ Bound 0 $ rec_tm) $ 
   138     FOLogic.imp $ (Ind_Syntax.mem_const $ Bound 0 $ rec_tm) $ 
   139                      (pred $ Bound 0);
   139                      (pred $ Bound 0);
   140 
   140 
   141 (*To instantiate the main induction rule*)
   141 (*To instantiate the main induction rule*)
   142 val induct_concl = 
   142 val induct_concl = 
   143     Ind_Syntax.mk_tprop
   143     FOLogic.mk_Trueprop
   144       (Ind_Syntax.mk_all_imp
   144       (Ind_Syntax.mk_all_imp
   145        (big_rec_tm,
   145        (big_rec_tm,
   146         Abs("z", Ind_Syntax.iT, 
   146         Abs("z", Ind_Syntax.iT, 
   147             fold_bal (app Ind_Syntax.conj) 
   147             fold_bal (app FOLogic.conj) 
   148             (ListPair.map mk_rec_imp (Inductive.rec_tms,preds)))))
   148             (ListPair.map mk_rec_imp (Inductive.rec_tms,preds)))))
   149 and mutual_induct_concl =
   149 and mutual_induct_concl =
   150  Ind_Syntax.mk_tprop(fold_bal (app Ind_Syntax.conj) qconcls);
   150  FOLogic.mk_Trueprop(fold_bal (app FOLogic.conj) qconcls);
   151 
   151 
   152 val lemma_tac = FIRST' [eresolve_tac [asm_rl, conjE, PartE, mp],
   152 val lemma_tac = FIRST' [eresolve_tac [asm_rl, conjE, PartE, mp],
   153                         resolve_tac [allI, impI, conjI, Part_eqI],
   153                         resolve_tac [allI, impI, conjI, Part_eqI],
   154                         dresolve_tac [spec, mp, Pr.fsplitD]];
   154                         dresolve_tac [spec, mp, Pr.fsplitD]];
   155 
   155 
   239 val Const ("Trueprop", _) $ (pred_var $ _) = concl_of induct0
   239 val Const ("Trueprop", _) $ (pred_var $ _) = concl_of induct0
   240 
   240 
   241 in
   241 in
   242   struct
   242   struct
   243   (*strip quantifier*)
   243   (*strip quantifier*)
   244   val induct = CP.split_rule_var(pred_var, elem_type-->Ind_Syntax.oT, induct0) 
   244   val induct = CP.split_rule_var(pred_var, elem_type-->FOLogic.oT, induct0) 
   245                |> standard;
   245                |> standard;
   246 
   246 
   247   (*Just "True" unless there's true mutual recursion.  This saves storage.*)
   247   (*Just "True" unless there's true mutual recursion.  This saves storage.*)
   248   val mutual_induct = CP.remove_split mutual_induct_fsplit
   248   val mutual_induct = CP.remove_split mutual_induct_fsplit
   249   end
   249   end