56 |
56 |
57 (* defines the quotient types *) |
57 (* defines the quotient types *) |
58 fun define_qtypes qtys_descr alpha_tys alpha_trms alpha_equivp_thms lthy = |
58 fun define_qtypes qtys_descr alpha_tys alpha_trms alpha_equivp_thms lthy = |
59 let |
59 let |
60 val qty_args1 = map2 (fn ty => fn trm => (ty, trm, false)) alpha_tys alpha_trms |
60 val qty_args1 = map2 (fn ty => fn trm => (ty, trm, false)) alpha_tys alpha_trms |
61 val qty_args2 = map2 (fn descr => fn args1 => (descr, args1, (NONE, false, NONE))) qtys_descr qty_args1 |
61 val qty_args2 = map2 (fn descr => fn args1 => (descr, args1, (NONE, NONE))) qtys_descr qty_args1 |
62 val qty_args3 = qty_args2 ~~ alpha_equivp_thms |
62 val qty_args3 = qty_args2 ~~ alpha_equivp_thms |
63 in |
63 in |
64 fold_map Quotient_Type.add_quotient_type qty_args3 lthy |
64 fold_map Quotient_Type.add_quotient_type qty_args3 lthy |
65 end |
65 end |
66 |
66 |
111 |
111 |
112 val lifted_perm_laws = |
112 val lifted_perm_laws = |
113 map (Quotient_Tacs.lifted lthy3 qtys []) raw_perm_laws' |
113 map (Quotient_Tacs.lifted lthy3 qtys []) raw_perm_laws' |
114 |> Variable.exportT lthy3 lthy2 |
114 |> Variable.exportT lthy3 lthy2 |
115 |
115 |
116 fun tac _ = |
116 fun tac ctxt = |
117 Class.intro_classes_tac [] THEN |
117 Class.intro_classes_tac ctxt [] THEN |
118 (ALLGOALS (resolve_tac lifted_perm_laws)) |
118 (ALLGOALS (resolve_tac ctxt lifted_perm_laws)) |
119 in |
119 in |
120 lthy2 |
120 lthy2 |
121 |> Class.prove_instantiation_exit tac |
121 |> Class.prove_instantiation_exit tac |
122 |> Named_Target.theory_init |
122 |> Named_Target.theory_init |
123 end |
123 end |
124 |
124 |
125 |
125 |
126 (* defines the size functions and proves size-class *) |
126 (* defines the size functions and proves size-class *) |
127 fun define_qsizes qtys qfull_ty_names tvs size_specs lthy = |
127 fun define_qsizes qtys qfull_ty_names tvs size_specs lthy = |
128 let |
128 let |
129 val tac = K (Class.intro_classes_tac []) |
129 fun tac ctxt = Class.intro_classes_tac ctxt [] |
130 in |
130 in |
131 lthy |
131 lthy |
132 |> Local_Theory.exit_global |
132 |> Local_Theory.exit_global |
133 |> Class.instantiation (qfull_ty_names, tvs, @{sort size}) |
133 |> Class.instantiation (qfull_ty_names, tvs, @{sort size}) |
134 |> snd o (define_qconsts qtys size_specs) |
134 |> snd o (define_qconsts qtys size_specs) |
155 |
155 |
156 fun unraw_vars_thm thm = |
156 fun unraw_vars_thm thm = |
157 let |
157 let |
158 fun unraw_var_str ((s, i), T) = ((unraw_str s, i), T) |
158 fun unraw_var_str ((s, i), T) = ((unraw_str s, i), T) |
159 |
159 |
160 val vars = Term.add_vars (prop_of thm) [] |
160 val vars = Term.add_vars (Thm.prop_of thm) [] |
161 val vars' = map (Var o unraw_var_str) vars |
161 val vars' = map (Var o unraw_var_str) vars |
162 in |
162 in |
163 Thm.certify_instantiate ([], (vars ~~ vars')) thm |
163 Thm.certify_instantiate ([], (vars ~~ vars')) thm |
164 end |
164 end |
165 |
165 |
227 |> foldr1 (HOLogic.mk_conj) |
227 |> foldr1 (HOLogic.mk_conj) |
228 |> HOLogic.mk_Trueprop |
228 |> HOLogic.mk_Trueprop |
229 |
229 |
230 val tac = |
230 val tac = |
231 EVERY' [ rtac @{thm supports_finite}, |
231 EVERY' [ rtac @{thm supports_finite}, |
232 resolve_tac qsupports_thms, |
232 resolve_tac ctxt' qsupports_thms, |
233 asm_simp_tac (put_simpset HOL_ss ctxt' |
233 asm_simp_tac (put_simpset HOL_ss ctxt' |
234 addsimps @{thms finite_supp supp_Pair finite_Un}) ] |
234 addsimps @{thms finite_supp supp_Pair finite_Un}) ] |
235 in |
235 in |
236 Goal.prove ctxt' [] [] goals |
236 Goal.prove ctxt' [] [] goals |
237 (K (HEADGOAL (rtac qinduct THEN_ALL_NEW tac))) |
237 (K (HEADGOAL (rtac qinduct THEN_ALL_NEW tac))) |
238 |> singleton (Proof_Context.export ctxt' ctxt) |
238 |> singleton (Proof_Context.export ctxt' ctxt) |
239 |> Datatype_Aux.split_conj_thm |
239 |> Old_Datatype_Aux.split_conj_thm |
240 |> map zero_var_indexes |
240 |> map zero_var_indexes |
241 end |
241 end |
242 |
242 |
243 |
243 |
244 (* finite supp instances *) |
244 (* finite supp instances *) |
248 val lthy1 = |
248 val lthy1 = |
249 lthy |
249 lthy |
250 |> Local_Theory.exit_global |
250 |> Local_Theory.exit_global |
251 |> Class.instantiation (qfull_ty_names, tvs, @{sort fs}) |
251 |> Class.instantiation (qfull_ty_names, tvs, @{sort fs}) |
252 |
252 |
253 fun tac _ = |
253 fun tac ctxt = |
254 Class.intro_classes_tac [] THEN |
254 Class.intro_classes_tac ctxt [] THEN |
255 (ALLGOALS (resolve_tac qfsupp_thms)) |
255 (ALLGOALS (resolve_tac ctxt qfsupp_thms)) |
256 in |
256 in |
257 lthy1 |
257 lthy1 |
258 |> Class.prove_instantiation_exit tac |
258 |> Class.prove_instantiation_exit tac |
259 |> Named_Target.theory_init |
259 |> Named_Target.theory_init |
260 end |
260 end |
301 | _ => raise TERM ("mk_bn_supp_abs_tac", [trm])) |
301 | _ => raise TERM ("mk_bn_supp_abs_tac", [trm])) |
302 |
302 |
303 |
303 |
304 val thms1 = @{thms supp_Pair supp_eqvt[symmetric] Un_assoc conj_assoc} |
304 val thms1 = @{thms supp_Pair supp_eqvt[symmetric] Un_assoc conj_assoc} |
305 val thms2 = @{thms de_Morgan_conj Collect_disj_eq finite_Un} |
305 val thms2 = @{thms de_Morgan_conj Collect_disj_eq finite_Un} |
306 val thms3 = @{thms alphas prod_alpha_def prod_fv.simps rel_prod_def permute_prod_def |
306 val thms3 = @{thms alphas prod_alpha_def prod_fv.simps rel_prod_conv permute_prod_def |
307 prod.rec prod.case prod.inject not_True_eq_False empty_def[symmetric] finite.emptyI} |
307 prod.rec prod.case prod.inject not_True_eq_False empty_def[symmetric] finite.emptyI} |
308 |
308 |
309 fun prove_fv_supp qtys qtrms fvs fv_bns alpha_bns fv_simps eq_iffs perm_simps |
309 fun prove_fv_supp qtys qtrms fvs fv_bns alpha_bns fv_simps eq_iffs perm_simps |
310 fv_bn_eqvts qinduct bclausess ctxt = |
310 fv_bn_eqvts qinduct bclausess ctxt = |
311 let |
311 let |
434 Const (@{const_name "Abs_set"}, _) => true |
434 Const (@{const_name "Abs_set"}, _) => true |
435 | Const (@{const_name "Abs_lst"}, _) => true |
435 | Const (@{const_name "Abs_lst"}, _) => true |
436 | Const (@{const_name "Abs_res"}, _) => true |
436 | Const (@{const_name "Abs_res"}, _) => true |
437 | _ => false |
437 | _ => false |
438 in |
438 in |
439 thm |> prop_of |
439 thm |> Thm.prop_of |
440 |> HOLogic.dest_Trueprop |
440 |> HOLogic.dest_Trueprop |
441 |> HOLogic.dest_eq |
441 |> HOLogic.dest_eq |
442 |> fst |
442 |> fst |
443 |> is_abs |
443 |> is_abs |
444 end |
444 end |
536 @ @{thms fresh_star_Un fresh_star_Pair fresh_star_list fresh_star_singleton fresh_star_fset |
536 @ @{thms fresh_star_Un fresh_star_Pair fresh_star_list fresh_star_singleton fresh_star_fset |
537 fresh_star_set} |
537 fresh_star_set} |
538 |
538 |
539 val tac1 = |
539 val tac1 = |
540 if rec_flag |
540 if rec_flag |
541 then resolve_tac @{thms Abs_rename_set' Abs_rename_res' Abs_rename_lst'} |
541 then resolve_tac ctxt @{thms Abs_rename_set' Abs_rename_res' Abs_rename_lst'} |
542 else resolve_tac @{thms Abs_rename_set Abs_rename_res Abs_rename_lst} |
542 else resolve_tac ctxt @{thms Abs_rename_set Abs_rename_res Abs_rename_lst} |
543 |
543 |
544 val tac2 = |
544 val tac2 = |
545 EVERY' [simp_tac (put_simpset HOL_basic_ss ctxt addsimps ss), |
545 EVERY' [simp_tac (put_simpset HOL_basic_ss ctxt addsimps ss), |
546 TRY o simp_tac (put_simpset HOL_ss ctxt)] |
546 TRY o simp_tac (put_simpset HOL_ss ctxt)] |
547 in |
547 in |
557 fun case_tac ctxt c bn_finite_thms eq_iff_thms bn_eqvt permute_bns perm_bn_alphas |
557 fun case_tac ctxt c bn_finite_thms eq_iff_thms bn_eqvt permute_bns perm_bn_alphas |
558 prems bclausess qexhaust_thm = |
558 prems bclausess qexhaust_thm = |
559 let |
559 let |
560 fun aux_tac prem bclauses = |
560 fun aux_tac prem bclauses = |
561 case (get_all_binders bclauses) of |
561 case (get_all_binders bclauses) of |
562 [] => EVERY' [rtac prem, atac] |
562 [] => EVERY' [rtac prem, assume_tac ctxt] |
563 | binders => Subgoal.SUBPROOF (fn {params, prems, concl, context = ctxt, ...} => |
563 | binders => Subgoal.SUBPROOF (fn {params, prems, concl, context = ctxt, ...} => |
564 let |
564 let |
565 val parms = map (term_of o snd) params |
565 val parms = map (Thm.term_of o snd) params |
566 val fthm = fresh_thm ctxt c parms binders bn_finite_thms |
566 val fthm = fresh_thm ctxt c parms binders bn_finite_thms |
567 |
567 |
568 val ss = @{thms fresh_star_Pair union_eqvt fresh_star_Un} |
568 val ss = @{thms fresh_star_Pair union_eqvt fresh_star_Un} |
569 val (([(_, fperm)], fprops), ctxt') = Obtain.result |
569 val (([(_, fperm)], fprops), ctxt') = Obtain.result |
570 (fn ctxt' => EVERY1 [etac exE, |
570 (fn ctxt' => EVERY1 [etac exE, |
571 full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps ss), |
571 full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps ss), |
572 REPEAT o (etac @{thm conjE})]) [fthm] ctxt |
572 REPEAT o (etac @{thm conjE})]) [fthm] ctxt |
573 |
573 |
574 val abs_eq_thms = flat |
574 val abs_eq_thms = flat |
575 (map (abs_eq_thm ctxt' fprops (term_of fperm) parms bn_eqvt permute_bns) bclauses) |
575 (map (abs_eq_thm ctxt' fprops (Thm.term_of fperm) parms bn_eqvt permute_bns) bclauses) |
576 |
576 |
577 val ((_, eqs), ctxt'') = Obtain.result |
577 val ((_, eqs), ctxt'') = Obtain.result |
578 (fn ctxt'' => EVERY1 |
578 (fn ctxt'' => EVERY1 |
579 [ REPEAT o (etac @{thm exE}), |
579 [ REPEAT o (etac @{thm exE}), |
580 REPEAT o (etac @{thm conjE}), |
580 REPEAT o (etac @{thm conjE}), |
590 |
590 |
591 (* for freshness conditions *) |
591 (* for freshness conditions *) |
592 val tac1 = SOLVED' (EVERY' |
592 val tac1 = SOLVED' (EVERY' |
593 [ simp_tac (put_simpset HOL_basic_ss ctxt'' addsimps peqs), |
593 [ simp_tac (put_simpset HOL_basic_ss ctxt'' addsimps peqs), |
594 rewrite_goal_tac ctxt'' (@{thms fresh_star_Un[THEN eq_reflection]}), |
594 rewrite_goal_tac ctxt'' (@{thms fresh_star_Un[THEN eq_reflection]}), |
595 conj_tac (DETERM o resolve_tac fprops') ]) |
595 conj_tac (DETERM o resolve_tac ctxt'' fprops') ]) |
596 |
596 |
597 (* for equalities between constructors *) |
597 (* for equalities between constructors *) |
598 val tac2 = SOLVED' (EVERY' |
598 val tac2 = SOLVED' (EVERY' |
599 [ rtac (@{thm ssubst} OF prems), |
599 [ rtac (@{thm ssubst} OF prems), |
600 rewrite_goal_tac ctxt'' (map safe_mk_equiv eq_iff_thms), |
600 rewrite_goal_tac ctxt'' (map safe_mk_equiv eq_iff_thms), |
601 rewrite_goal_tac ctxt'' (map safe_mk_equiv abs_eqs), |
601 rewrite_goal_tac ctxt'' (map safe_mk_equiv abs_eqs), |
602 conj_tac (DETERM o resolve_tac (@{thms refl} @ perm_bn_alphas)) ]) |
602 conj_tac (DETERM o resolve_tac ctxt'' (@{thms refl} @ perm_bn_alphas)) ]) |
603 |
603 |
604 (* proves goal "P" *) |
604 (* proves goal "P" *) |
605 val side_thm = Goal.prove ctxt'' [] [] (term_of concl) |
605 val side_thm = Goal.prove ctxt'' [] [] (Thm.term_of concl) |
606 (K (EVERY1 [ rtac prem, RANGE [tac1, tac2] ])) |
606 (K (EVERY1 [ rtac prem, RANGE [tac1, tac2] ])) |
607 |> singleton (Proof_Context.export ctxt'' ctxt) |
607 |> singleton (Proof_Context.export ctxt'' ctxt) |
608 in |
608 in |
609 rtac side_thm 1 |
609 rtac side_thm 1 |
610 end) ctxt |
610 end) ctxt |
620 |
620 |
621 val ([c, a], lthy'') = Variable.variant_fixes ["c", "'a"] lthy' |
621 val ([c, a], lthy'') = Variable.variant_fixes ["c", "'a"] lthy' |
622 val c = Free (c, TFree (a, @{sort fs})) |
622 val c = Free (c, TFree (a, @{sort fs})) |
623 |
623 |
624 val (ecases, main_concls) = exhausts' (* ecases are of the form (params, prems, concl) *) |
624 val (ecases, main_concls) = exhausts' (* ecases are of the form (params, prems, concl) *) |
625 |> map prop_of |
625 |> map Thm.prop_of |
626 |> map Logic.strip_horn |
626 |> map Logic.strip_horn |
627 |> split_list |
627 |> split_list |
628 |
628 |
629 val ecases' = (map o map) strip_full_horn ecases |
629 val ecases' = (map o map) strip_full_horn ecases |
630 |
630 |
705 val ([c_name, a], lthy'') = Variable.variant_fixes ["c", "'a"] lthy' |
705 val ([c_name, a], lthy'') = Variable.variant_fixes ["c", "'a"] lthy' |
706 val c_ty = TFree (a, @{sort fs}) |
706 val c_ty = TFree (a, @{sort fs}) |
707 val c = Free (c_name, c_ty) |
707 val c = Free (c_name, c_ty) |
708 |
708 |
709 val (prems, concl) = induct' |
709 val (prems, concl) = induct' |
710 |> prop_of |
710 |> Thm.prop_of |
711 |> Logic.strip_horn |
711 |> Logic.strip_horn |
712 |
712 |
713 val concls = concl |
713 val concls = concl |
714 |> HOLogic.dest_Trueprop |
714 |> HOLogic.dest_Trueprop |
715 |> HOLogic.dest_conj |
715 |> HOLogic.dest_conj |
719 val prems' = prems |
719 val prems' = prems |
720 |> map strip_full_horn |
720 |> map strip_full_horn |
721 |> map2 (prep_prem lthy'' c c_name c_ty) (flat bclausesss) |
721 |> map2 (prep_prem lthy'' c c_name c_ty) (flat bclausesss) |
722 |
722 |
723 fun pat_tac ctxt thm = |
723 fun pat_tac ctxt thm = |
724 Subgoal.FOCUS (fn {params, context, ...} => |
724 Subgoal.FOCUS (fn {params, context = ctxt', ...} => |
725 let |
725 let |
726 val thy = Proof_Context.theory_of context |
726 val ty_parms = map (fn (_, ct) => (fastype_of (Thm.term_of ct), ct)) params |
727 val ty_parms = map (fn (_, ct) => (fastype_of (term_of ct), ct)) params |
727 val vs = Term.add_vars (Thm.prop_of thm) [] |
728 val vs = Term.add_vars (prop_of thm) [] |
|
729 val vs_tys = map (Type.legacy_freeze_type o snd) vs |
728 val vs_tys = map (Type.legacy_freeze_type o snd) vs |
730 val vs_ctrms = map (cterm_of thy o Var) vs |
729 val vs_ctrms = map (Thm.cterm_of ctxt' o Var) vs |
731 val assigns = map (lookup ty_parms) vs_tys |
730 val assigns = map (lookup ty_parms) vs_tys |
732 |
731 |
733 val thm' = cterm_instantiate (vs_ctrms ~~ assigns) thm |
732 val thm' = cterm_instantiate (vs_ctrms ~~ assigns) thm |
734 in |
733 in |
735 rtac thm' 1 |
734 rtac thm' 1 |
737 THEN_ALL_NEW asm_full_simp_tac (put_simpset HOL_basic_ss ctxt) |
736 THEN_ALL_NEW asm_full_simp_tac (put_simpset HOL_basic_ss ctxt) |
738 |
737 |
739 fun size_simp_tac ctxt = |
738 fun size_simp_tac ctxt = |
740 simp_tac (put_simpset size_ss ctxt addsimps (@{thms comp_def snd_conv} @ size_thms)) |
739 simp_tac (put_simpset size_ss ctxt addsimps (@{thms comp_def snd_conv} @ size_thms)) |
741 in |
740 in |
742 Goal.prove_multi lthy'' [] prems' concls |
741 Goal.prove_common lthy'' NONE [] prems' concls |
743 (fn {prems, context = ctxt} => |
742 (fn {prems, context = ctxt} => |
744 Induction_Schema.induction_schema_tac ctxt prems |
743 Induction_Schema.induction_schema_tac ctxt prems |
745 THEN RANGE (map (pat_tac ctxt) exhausts) 1 |
744 THEN RANGE (map (pat_tac ctxt) exhausts) 1 |
746 THEN prove_termination_ind ctxt 1 |
745 THEN prove_termination_ind ctxt 1 |
747 THEN ALLGOALS (size_simp_tac ctxt)) |
746 THEN ALLGOALS (size_simp_tac ctxt)) |