Nominal/nominal_dt_quot.ML
changeset 3239 67370521c09c
parent 3229 b52e8651591f
child 3243 c4f31f1564b7
equal deleted inserted replaced
3238:b2e1a7b83e05 3239:67370521c09c
    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))