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 |