36 datatype ind_scheme = IndScheme of |
36 datatype ind_scheme = IndScheme of |
37 {T: typ, (* sum of products *) |
37 {T: typ, (* sum of products *) |
38 branches: scheme_branch list, |
38 branches: scheme_branch list, |
39 cases: scheme_case list} |
39 cases: scheme_case list} |
40 |
40 |
41 val ind_atomize = Raw_Simplifier.rewrite true @{thms induct_atomize} |
41 fun ind_atomize ctxt = Raw_Simplifier.rewrite ctxt true @{thms induct_atomize} |
42 val ind_rulify = Raw_Simplifier.rewrite true @{thms induct_rulify} |
42 fun ind_rulify ctxt = Raw_Simplifier.rewrite ctxt true @{thms induct_rulify} |
43 |
43 |
44 fun meta thm = thm RS eq_reflection |
44 fun meta thm = thm RS eq_reflection |
45 |
45 |
46 val sum_prod_conv = Raw_Simplifier.rewrite true |
46 fun sum_prod_conv ctxt = Raw_Simplifier.rewrite ctxt true |
47 (map meta (@{thm split_conv} :: @{thms sum.cases})) |
47 (map meta (@{thm split_conv} :: @{thms sum.cases})) |
48 |
48 |
49 fun term_conv thy cv t = |
49 fun term_conv thy cv t = |
50 cv (cterm_of thy t) |
50 cv (cterm_of thy t) |
51 |> prop_of |> Logic.dest_equals |> snd |
51 |> prop_of |> Logic.dest_equals |> snd |
185 in |
185 in |
186 map f cases |
186 map f cases |
187 end |
187 end |
188 |
188 |
189 |
189 |
190 fun mk_ind_goal thy branches = |
190 fun mk_ind_goal ctxt branches = |
191 let |
191 let |
|
192 val thy = Proof_Context.theory_of ctxt |
|
193 |
192 fun brnch (SchemeBranch { P, xs, ws, Cs, ... }) = |
194 fun brnch (SchemeBranch { P, xs, ws, Cs, ... }) = |
193 HOLogic.mk_Trueprop (list_comb (P, map Free xs)) |
195 HOLogic.mk_Trueprop (list_comb (P, map Free xs)) |
194 |> fold_rev (curry Logic.mk_implies) Cs |
196 |> fold_rev (curry Logic.mk_implies) Cs |
195 |> fold_rev (Logic.all o Free) ws |
197 |> fold_rev (Logic.all o Free) ws |
196 |> term_conv thy ind_atomize |
198 |> term_conv thy (ind_atomize ctxt) |
197 |> Object_Logic.drop_judgment thy |
199 |> Object_Logic.drop_judgment thy |
198 |> HOLogic.tupled_lambda (foldr1 HOLogic.mk_prod (map Free xs)) |
200 |> HOLogic.tupled_lambda (foldr1 HOLogic.mk_prod (map Free xs)) |
199 in |
201 in |
200 SumTree.mk_sumcases HOLogic.boolT (map brnch branches) |
202 SumTree.mk_sumcases HOLogic.boolT (map brnch branches) |
201 end |
203 end |
202 |
204 |
203 fun mk_induct_rule ctxt R x complete_thms wf_thm ineqss |
205 fun mk_induct_rule ctxt R x complete_thms wf_thm ineqss |
204 (IndScheme {T, cases=scases, branches}) = |
206 (IndScheme {T, cases=scases, branches}) = |
205 let |
207 let |
|
208 val thy = Proof_Context.theory_of ctxt |
|
209 val cert = cterm_of thy |
|
210 |
206 val n = length branches |
211 val n = length branches |
207 val scases_idx = map_index I scases |
212 val scases_idx = map_index I scases |
208 |
213 |
209 fun inject i ts = |
214 fun inject i ts = |
210 SumTree.mk_inj T n (i + 1) (foldr1 HOLogic.mk_prod ts) |
215 SumTree.mk_inj T n (i + 1) (foldr1 HOLogic.mk_prod ts) |
211 val P_of = nth (map (fn (SchemeBranch { P, ... }) => P) branches) |
216 val P_of = nth (map (fn (SchemeBranch { P, ... }) => P) branches) |
212 |
217 |
213 val thy = Proof_Context.theory_of ctxt |
218 val P_comp = mk_ind_goal ctxt branches |
214 val cert = cterm_of thy |
|
215 |
|
216 val P_comp = mk_ind_goal thy branches |
|
217 |
219 |
218 (* Inductive Hypothesis: !!z. (z,x):R ==> P z *) |
220 (* Inductive Hypothesis: !!z. (z,x):R ==> P z *) |
219 val ihyp = Logic.all_const T $ Abs ("z", T, |
221 val ihyp = Logic.all_const T $ Abs ("z", T, |
220 Logic.mk_implies |
222 Logic.mk_implies |
221 (HOLogic.mk_Trueprop ( |
223 (HOLogic.mk_Trueprop ( |
268 |> import |
270 |> import |
269 in |
271 in |
270 sih |
272 sih |
271 |> Thm.forall_elim (cert (inject idx rcargs)) |
273 |> Thm.forall_elim (cert (inject idx rcargs)) |
272 |> Thm.elim_implies (import ineq) (* Psum rcargs *) |
274 |> Thm.elim_implies (import ineq) (* Psum rcargs *) |
273 |> Conv.fconv_rule sum_prod_conv |
275 |> Conv.fconv_rule (sum_prod_conv ctxt) |
274 |> Conv.fconv_rule ind_rulify |
276 |> Conv.fconv_rule (ind_rulify ctxt) |
275 |> (fn th => th COMP ipres) (* P rs *) |
277 |> (fn th => th COMP ipres) (* P rs *) |
276 |> fold_rev (Thm.implies_intr o cprop_of) cGas |
278 |> fold_rev (Thm.implies_intr o cprop_of) cGas |
277 |> fold_rev Thm.forall_intr cGvs |
279 |> fold_rev Thm.forall_intr cGvs |
278 end |
280 end |
279 |
281 |
310 |> fold_rev (Thm.implies_intr o cprop_of) C_hyps |
312 |> fold_rev (Thm.implies_intr o cprop_of) C_hyps |
311 |> fold_rev (Thm.forall_intr o cert o Free) ws |
313 |> fold_rev (Thm.forall_intr o cert o Free) ws |
312 |
314 |
313 val Pxs = cert (HOLogic.mk_Trueprop (P_comp $ x)) |
315 val Pxs = cert (HOLogic.mk_Trueprop (P_comp $ x)) |
314 |> Goal.init |
316 |> Goal.init |
315 |> (Simplifier.rewrite_goals_tac (map meta (branch_hyp :: @{thm split_conv} :: @{thms sum.cases})) |
317 |> (Simplifier.rewrite_goals_tac ctxt |
316 THEN CONVERSION ind_rulify 1) |
318 (map meta (branch_hyp :: @{thm split_conv} :: @{thms sum.cases})) |
|
319 THEN CONVERSION (ind_rulify ctxt) 1) |
317 |> Seq.hd |
320 |> Seq.hd |
318 |> Thm.elim_implies (Conv.fconv_rule Drule.beta_eta_conversion bstep) |
321 |> Thm.elim_implies (Conv.fconv_rule Drule.beta_eta_conversion bstep) |
319 |> Goal.finish ctxt |
322 |> Goal.finish ctxt |
320 |> Thm.implies_intr (cprop_of branch_hyp) |
323 |> Thm.implies_intr (cprop_of branch_hyp) |
321 |> fold_rev (Thm.forall_intr o cert) fxs |
324 |> fold_rev (Thm.forall_intr o cert) fxs |
373 |> cert |
376 |> cert |
374 in |
377 in |
375 indthm |
378 indthm |
376 |> Drule.instantiate' [] [SOME inst] |
379 |> Drule.instantiate' [] [SOME inst] |
377 |> simplify (put_simpset SumTree.sumcase_split_ss ctxt'') |
380 |> simplify (put_simpset SumTree.sumcase_split_ss ctxt'') |
378 |> Conv.fconv_rule ind_rulify |
381 |> Conv.fconv_rule (ind_rulify ctxt'') |
379 end |
382 end |
380 |
383 |
381 val res = Conjunction.intr_balanced (map_index project branches) |
384 val res = Conjunction.intr_balanced (map_index project branches) |
382 |> fold_rev Thm.implies_intr (map cprop_of newgoals @ steps) |
385 |> fold_rev Thm.implies_intr (map cprop_of newgoals @ steps) |
383 |> Drule.generalize ([], [Rn]) |
386 |> Drule.generalize ([], [Rn]) |