equal
deleted
inserted
replaced
461 |
461 |
462 val exi_zero = @{lemma "P (0::perm) ==> (? x. P x)" by auto} |
462 val exi_zero = @{lemma "P (0::perm) ==> (? x. P x)" by auto} |
463 |
463 |
464 fun cases_tac intros ctxt = |
464 fun cases_tac intros ctxt = |
465 let |
465 let |
466 val prod_simps = @{thms split_conv prod_alpha_def prod_rel_def} |
466 val prod_simps = @{thms split_conv prod_alpha_def rel_prod_def} |
467 |
467 |
468 val unbound_tac = REPEAT o (etac @{thm conjE}) THEN' atac |
468 val unbound_tac = REPEAT o (etac @{thm conjE}) THEN' atac |
469 |
469 |
470 val bound_tac = |
470 val bound_tac = |
471 EVERY' [ rtac exi_zero, |
471 EVERY' [ rtac exi_zero, |
502 let |
502 let |
503 val prems' = map (transform_prem1 context pred_names) prems |
503 val prems' = map (transform_prem1 context pred_names) prems |
504 in |
504 in |
505 resolve_tac prems' 1 |
505 resolve_tac prems' 1 |
506 end) ctxt |
506 end) ctxt |
507 val prod_simps = @{thms split_conv permute_prod.simps prod_alpha_def prod_rel_def alphas} |
507 val prod_simps = @{thms split_conv permute_prod.simps prod_alpha_def rel_prod_def alphas} |
508 in |
508 in |
509 EVERY' |
509 EVERY' |
510 [ etac exi_neg, |
510 [ etac exi_neg, |
511 resolve_tac @{thms alpha_sym_eqvt}, |
511 resolve_tac @{thms alpha_sym_eqvt}, |
512 asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps prod_simps), |
512 asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps prod_simps), |
554 HEADGOAL (rtac exi_inst) |
554 HEADGOAL (rtac exi_inst) |
555 end) |
555 end) |
556 |
556 |
557 fun non_trivial_cases_tac pred_names intros alpha_eqvt ctxt = |
557 fun non_trivial_cases_tac pred_names intros alpha_eqvt ctxt = |
558 let |
558 let |
559 val prod_simps = @{thms split_conv alphas permute_prod.simps prod_alpha_def prod_rel_def} |
559 val prod_simps = @{thms split_conv alphas permute_prod.simps prod_alpha_def rel_prod_def} |
560 in |
560 in |
561 resolve_tac intros |
561 resolve_tac intros |
562 THEN_ALL_NEW (asm_simp_tac (put_simpset HOL_basic_ss ctxt) THEN' |
562 THEN_ALL_NEW (asm_simp_tac (put_simpset HOL_basic_ss ctxt) THEN' |
563 TRY o EVERY' (* if binders are present *) |
563 TRY o EVERY' (* if binders are present *) |
564 [ etac @{thm exE}, |
564 [ etac @{thm exE}, |
568 atac, |
568 atac, |
569 aatac pred_names ctxt, |
569 aatac pred_names ctxt, |
570 eqvt_tac ctxt (eqvt_relaxed_config addpres alpha_eqvt) THEN' rtac @{thm refl}, |
570 eqvt_tac ctxt (eqvt_relaxed_config addpres alpha_eqvt) THEN' rtac @{thm refl}, |
571 asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps prod_simps) ]) |
571 asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps prod_simps) ]) |
572 end |
572 end |
573 |
573 |
574 fun prove_trans_tac alpha_result raw_dt_thms alpha_eqvt ctxt = |
574 fun prove_trans_tac alpha_result raw_dt_thms alpha_eqvt ctxt = |
575 let |
575 let |
576 val AlphaResult {alpha_names, alpha_bn_names, alpha_intros, alpha_cases, ...} = alpha_result |
576 val AlphaResult {alpha_names, alpha_bn_names, alpha_intros, alpha_cases, ...} = alpha_result |
577 val alpha_names = alpha_names @ alpha_bn_names |
577 val alpha_names = alpha_names @ alpha_bn_names |
578 |
578 |
683 val prop1 = map (fn t => (lookup ty_assoc (arg_ty t), fn (x, y) => mk_eq' t x y)) fvs |
683 val prop1 = map (fn t => (lookup ty_assoc (arg_ty t), fn (x, y) => mk_eq' t x y)) fvs |
684 val prop2 = map (fn t => (lookup ty_assoc (arg_ty t), fn (x, y) => mk_eq' t x y)) (bns @ fv_bns) |
684 val prop2 = map (fn t => (lookup ty_assoc (arg_ty t), fn (x, y) => mk_eq' t x y)) (bns @ fv_bns) |
685 val prop3 = map2 (fn t1 => fn t2 => (t1, fn (x, y) => mk_eq' t2 x y)) alpha_bn_trms fv_bns |
685 val prop3 = map2 (fn t1 => fn t2 => (t1, fn (x, y) => mk_eq' t2 x y)) alpha_bn_trms fv_bns |
686 |
686 |
687 val simpset = |
687 val simpset = |
688 put_simpset HOL_ss ctxt addsimps (simps @ @{thms alphas prod_fv.simps set.simps append.simps} |
688 put_simpset HOL_ss ctxt addsimps (simps @ @{thms alphas prod_fv.simps set_simps append.simps} |
689 @ @{thms Un_assoc Un_insert_left Un_empty_right Un_empty_left}) |
689 @ @{thms Un_assoc Un_insert_left Un_empty_right Un_empty_left}) |
690 in |
690 in |
691 alpha_prove (alpha_trms @ alpha_bn_trms) (prop1 @ prop2 @ prop3) alpha_raw_induct |
691 alpha_prove (alpha_trms @ alpha_bn_trms) (prop1 @ prop2 @ prop3) alpha_raw_induct |
692 (K (asm_full_simp_tac simpset)) ctxt |
692 (K (asm_full_simp_tac simpset)) ctxt |
693 end |
693 end |
704 (HOLogic.size_const ty $ x, HOLogic.size_const ty $ y) |
704 (HOLogic.size_const ty $ x, HOLogic.size_const ty $ y) |
705 |
705 |
706 val props = (alpha_trms @ alpha_bn_trms) ~~ (map mk_prop (alpha_tys @ alpha_bn_tys)) |
706 val props = (alpha_trms @ alpha_bn_trms) ~~ (map mk_prop (alpha_tys @ alpha_bn_tys)) |
707 |
707 |
708 val simpset = |
708 val simpset = |
709 put_simpset HOL_ss ctxt addsimps (simps @ @{thms alphas prod_alpha_def prod_rel_def |
709 put_simpset HOL_ss ctxt addsimps (simps @ @{thms alphas prod_alpha_def rel_prod_def |
710 permute_prod_def prod.cases prod.recs}) |
710 permute_prod_def prod.case prod.rec}) |
711 |
711 |
712 val tac = (TRY o REPEAT o etac @{thm exE}) THEN' asm_full_simp_tac simpset |
712 val tac = (TRY o REPEAT o etac @{thm exE}) THEN' asm_full_simp_tac simpset |
713 in |
713 in |
714 alpha_prove (alpha_trms @ alpha_bn_trms) props alpha_raw_induct (K tac) ctxt |
714 alpha_prove (alpha_trms @ alpha_bn_trms) props alpha_raw_induct (K tac) ctxt |
715 end |
715 end |
717 |
717 |
718 (* respectfulness for constructors *) |
718 (* respectfulness for constructors *) |
719 |
719 |
720 fun raw_constr_rsp_tac ctxt alpha_intros simps = |
720 fun raw_constr_rsp_tac ctxt alpha_intros simps = |
721 let |
721 let |
722 val pre_simpset = put_simpset HOL_ss ctxt addsimps @{thms fun_rel_def} |
722 val pre_simpset = put_simpset HOL_ss ctxt addsimps @{thms rel_fun_def} |
723 val post_simpset = put_simpset HOL_ss ctxt addsimps @{thms alphas prod_alpha_def prod_rel_def |
723 val post_simpset = put_simpset HOL_ss ctxt addsimps @{thms alphas prod_alpha_def rel_prod_def |
724 prod_fv.simps fresh_star_zero permute_zero prod.cases} @ simps |
724 prod_fv.simps fresh_star_zero permute_zero prod.case} @ simps |
725 in |
725 in |
726 asm_full_simp_tac pre_simpset |
726 asm_full_simp_tac pre_simpset |
727 THEN' REPEAT o (resolve_tac @{thms allI impI}) |
727 THEN' REPEAT o (resolve_tac @{thms allI impI}) |
728 THEN' resolve_tac alpha_intros |
728 THEN' resolve_tac alpha_intros |
729 THEN_ALL_NEW (TRY o (rtac exi_zero) THEN' asm_full_simp_tac post_simpset) |
729 THEN_ALL_NEW (TRY o (rtac exi_zero) THEN' asm_full_simp_tac post_simpset) |
736 fun lookup ty = |
736 fun lookup ty = |
737 case AList.lookup (op=) (alpha_tys ~~ alpha_trms) ty of |
737 case AList.lookup (op=) (alpha_tys ~~ alpha_trms) ty of |
738 NONE => HOLogic.eq_const ty |
738 NONE => HOLogic.eq_const ty |
739 | SOME alpha => alpha |
739 | SOME alpha => alpha |
740 |
740 |
741 fun fun_rel_app (t1, t2) = |
741 fun rel_fun_app (t1, t2) = |
742 Const (@{const_name "fun_rel"}, dummyT) $ t1 $ t2 |
742 Const (@{const_name "rel_fun"}, dummyT) $ t1 $ t2 |
743 |
743 |
744 fun prep_goal trm = |
744 fun prep_goal trm = |
745 trm |
745 trm |
746 |> strip_type o fastype_of |
746 |> strip_type o fastype_of |
747 |> (fn (tys, ty) => tys @ [ty]) |
747 |> (fn (tys, ty) => tys @ [ty]) |
748 |> map lookup |
748 |> map lookup |
749 |> foldr1 fun_rel_app |
749 |> foldr1 rel_fun_app |
750 |> (fn t => t $ trm $ trm) |
750 |> (fn t => t $ trm $ trm) |
751 |> Syntax.check_term ctxt |
751 |> Syntax.check_term ctxt |
752 |> HOLogic.mk_Trueprop |
752 |> HOLogic.mk_Trueprop |
753 in |
753 in |
754 map (fn constrs => |
754 map (fn constrs => |
760 |
760 |
761 (* rsp lemmas for alpha_bn relations *) |
761 (* rsp lemmas for alpha_bn relations *) |
762 |
762 |
763 val rsp_equivp = |
763 val rsp_equivp = |
764 @{lemma "[|equivp Q; !!x y. R x y ==> Q x y|] ==> (R ===> R ===> op =) Q Q" |
764 @{lemma "[|equivp Q; !!x y. R x y ==> Q x y|] ==> (R ===> R ===> op =) Q Q" |
765 by (simp only: fun_rel_def equivp_def, metis)} |
765 by (simp only: rel_fun_def equivp_def, metis)} |
766 |
766 |
767 |
767 |
768 (* we have to reorder the alpha_bn_imps theorems in order |
768 (* we have to reorder the alpha_bn_imps theorems in order |
769 to be in order with alpha_bn_trms *) |
769 to be in order with alpha_bn_trms *) |
770 fun raw_alpha_bn_rsp alpha_result alpha_bn_equivp alpha_bn_imps = |
770 fun raw_alpha_bn_rsp alpha_result alpha_bn_equivp alpha_bn_imps = |
789 |
789 |
790 |
790 |
791 (* rsp for permute_bn functions *) |
791 (* rsp for permute_bn functions *) |
792 |
792 |
793 val perm_bn_rsp = @{lemma "(!x y p. R x y --> R (f p x) (f p y)) ==> (op= ===> R ===> R) f f" |
793 val perm_bn_rsp = @{lemma "(!x y p. R x y --> R (f p x) (f p y)) ==> (op= ===> R ===> R) f f" |
794 by (simp add: fun_rel_def)} |
794 by (simp add: rel_fun_def)} |
795 |
795 |
796 fun raw_prove_perm_bn_tac alpha_result simps ctxt = |
796 fun raw_prove_perm_bn_tac alpha_result simps ctxt = |
797 SUBPROOF (fn {prems, context, ...} => |
797 SUBPROOF (fn {prems, context, ...} => |
798 let |
798 let |
799 val AlphaResult {alpha_names, alpha_bn_names, alpha_intros, ...} = alpha_result |
799 val AlphaResult {alpha_names, alpha_bn_names, alpha_intros, ...} = alpha_result |
817 alpha_result |
817 alpha_result |
818 |
818 |
819 val perm_bn_ty = range_type o range_type o fastype_of |
819 val perm_bn_ty = range_type o range_type o fastype_of |
820 val ty_assoc = (alpha_tys @ alpha_bn_tys) ~~ (alpha_trms @ alpha_bn_trms) |
820 val ty_assoc = (alpha_tys @ alpha_bn_tys) ~~ (alpha_trms @ alpha_bn_trms) |
821 |
821 |
822 val ([p], ctxt') = Variable.variant_fixes ["p"] ctxt |
822 val ([p], ctxt') = Variable.variant_fixes ["p"] ctxt |
823 val p = Free (p, @{typ perm}) |
823 val p = Free (p, @{typ perm}) |
824 |
824 |
825 fun mk_prop t = |
825 fun mk_prop t = |
826 let |
826 let |
827 val alpha_trm = lookup ty_assoc (perm_bn_ty t) |
827 val alpha_trm = lookup ty_assoc (perm_bn_ty t) |
842 |
842 |
843 |
843 |
844 (* transformation of the natural rsp-lemmas into standard form *) |
844 (* transformation of the natural rsp-lemmas into standard form *) |
845 |
845 |
846 val fun_rsp = @{lemma |
846 val fun_rsp = @{lemma |
847 "(!x y. R x y --> f x = f y) ==> (R ===> (op =)) f f" by (simp add: fun_rel_def)} |
847 "(!x y. R x y --> f x = f y) ==> (R ===> (op =)) f f" by (simp add: rel_fun_def)} |
848 |
848 |
849 fun mk_funs_rsp ctxt thm = |
849 fun mk_funs_rsp ctxt thm = |
850 thm |
850 thm |
851 |> atomize ctxt |
851 |> atomize ctxt |
852 |> single |
852 |> single |
853 |> curry (op OF) fun_rsp |
853 |> curry (op OF) fun_rsp |
854 |
854 |
855 |
855 |
856 val permute_rsp = @{lemma |
856 val permute_rsp = @{lemma |
857 "(!x y p. R x y --> R (permute p x) (permute p y)) |
857 "(!x y p. R x y --> R (permute p x) (permute p y)) |
858 ==> ((op =) ===> R ===> R) permute permute" by (simp add: fun_rel_def)} |
858 ==> ((op =) ===> R ===> R) permute permute" by (simp add: rel_fun_def)} |
859 |
859 |
860 fun mk_alpha_permute_rsp ctxt thm = |
860 fun mk_alpha_permute_rsp ctxt thm = |
861 thm |
861 thm |
862 |> atomize ctxt |
862 |> atomize ctxt |
863 |> single |
863 |> single |