Nominal/nominal_dt_alpha.ML
changeset 3229 b52e8651591f
parent 3226 780b7a2c50b6
child 3239 67370521c09c
equal deleted inserted replaced
3228:040519ec99e9 3229:b52e8651591f
   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