Nominal/nominal_dt_quot.ML
changeset 3218 89158f401b07
parent 3210 024d07886de8
child 3226 780b7a2c50b6
equal deleted inserted replaced
3217:d67a6a48f1c7 3218:89158f401b07
   190     |> HOLogic.mk_Trueprop
   190     |> HOLogic.mk_Trueprop
   191   end
   191   end
   192 
   192 
   193 fun supports_tac ctxt perm_simps =
   193 fun supports_tac ctxt perm_simps =
   194   let
   194   let
   195     val ss1 = HOL_basic_ss addsimps @{thms supports_def fresh_def[symmetric]}
   195     val simpset1 =
   196     val ss2 = HOL_ss addsimps @{thms swap_fresh_fresh fresh_Pair}
   196       put_simpset HOL_basic_ss ctxt addsimps @{thms supports_def fresh_def[symmetric]}
   197   in
   197     val simpset2 =
   198     EVERY' [ simp_tac ss1,
   198       put_simpset HOL_ss ctxt addsimps @{thms swap_fresh_fresh fresh_Pair}
       
   199   in
       
   200     EVERY' [ simp_tac simpset1,
   199              eqvt_tac ctxt (eqvt_strict_config addpres perm_simps),
   201              eqvt_tac ctxt (eqvt_strict_config addpres perm_simps),
   200              simp_tac ss2 ]
   202              simp_tac simpset2 ]
   201   end
   203   end
   202 
   204 
   203 fun prove_supports_single ctxt perm_simps qtrm =
   205 fun prove_supports_single ctxt perm_simps qtrm =
   204   let
   206   let
   205     val goal = mk_supports_goal ctxt qtrm 
   207     val goal = mk_supports_goal ctxt qtrm 
   226       |> HOLogic.mk_Trueprop
   228       |> HOLogic.mk_Trueprop
   227 
   229 
   228     val tac = 
   230     val tac = 
   229       EVERY' [ rtac @{thm supports_finite},
   231       EVERY' [ rtac @{thm supports_finite},
   230                resolve_tac qsupports_thms,
   232                resolve_tac qsupports_thms,
   231                asm_simp_tac (HOL_ss addsimps @{thms finite_supp supp_Pair finite_Un}) ]
   233                asm_simp_tac (put_simpset HOL_ss ctxt
       
   234                 addsimps @{thms finite_supp supp_Pair finite_Un}) ]
   232   in
   235   in
   233     Goal.prove ctxt' [] [] goals
   236     Goal.prove ctxt' [] [] goals
   234       (K (HEADGOAL (rtac qinduct THEN_ALL_NEW tac)))
   237       (K (HEADGOAL (rtac qinduct THEN_ALL_NEW tac)))
   235     |> singleton (Proof_Context.export ctxt' ctxt)
   238     |> singleton (Proof_Context.export ctxt' ctxt)
   236     |> Datatype_Aux.split_conj_thm
   239     |> Datatype_Aux.split_conj_thm
   269   end
   272   end
   270 
   273 
   271 fun mk_fvs_goals fv = gen_mk_goals fv mk_supp
   274 fun mk_fvs_goals fv = gen_mk_goals fv mk_supp
   272 fun mk_fv_bns_goals fv_bn alpha_bn = gen_mk_goals fv_bn (mk_supp_rel alpha_bn)
   275 fun mk_fv_bns_goals fv_bn alpha_bn = gen_mk_goals fv_bn (mk_supp_rel alpha_bn)
   273 
   276 
   274 fun add_ss thms =
   277 fun add_simpset ctxt thms = put_simpset HOL_basic_ss ctxt addsimps thms
   275   HOL_basic_ss addsimps thms
       
   276 
   278 
   277 fun symmetric thms = 
   279 fun symmetric thms = 
   278   map (fn thm => thm RS @{thm sym}) thms
   280   map (fn thm => thm RS @{thm sym}) thms
   279 
   281 
   280 val supp_Abs_set = @{thms supp_Abs(1)[symmetric]}
   282 val supp_Abs_set = @{thms supp_Abs(1)[symmetric]}
   287 
   289 
   288 fun mk_supp_abs_tac ctxt [] = []
   290 fun mk_supp_abs_tac ctxt [] = []
   289   | mk_supp_abs_tac ctxt (BC (_, [], _)::xs) = mk_supp_abs_tac ctxt xs
   291   | mk_supp_abs_tac ctxt (BC (_, [], _)::xs) = mk_supp_abs_tac ctxt xs
   290   | mk_supp_abs_tac ctxt (bc::xs) = (DETERM o mk_supp_abs ctxt bc)::mk_supp_abs_tac ctxt xs
   292   | mk_supp_abs_tac ctxt (bc::xs) = (DETERM o mk_supp_abs ctxt bc)::mk_supp_abs_tac ctxt xs
   291 
   293 
   292 fun mk_bn_supp_abs_tac trm =
   294 fun mk_bn_supp_abs_tac ctxt trm =
   293   trm
   295   trm
   294   |> fastype_of
   296   |> fastype_of
   295   |> body_type
   297   |> body_type
   296   |> (fn ty => case ty of
   298   |> (fn ty => case ty of
   297         @{typ "atom set"}  => simp_tac (add_ss supp_Abs_set)
   299         @{typ "atom set"}  => simp_tac (add_simpset ctxt supp_Abs_set)
   298       | @{typ "atom list"} => simp_tac (add_ss supp_Abs_lst)
   300       | @{typ "atom list"} => simp_tac (add_simpset ctxt supp_Abs_lst)
   299       | _ => raise TERM ("mk_bn_supp_abs_tac", [trm]))
   301       | _ => raise TERM ("mk_bn_supp_abs_tac", [trm]))
   300 
   302 
   301 
   303 
   302 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}
   303 val thms2 = @{thms de_Morgan_conj Collect_disj_eq finite_Un}
   305 val thms2 = @{thms de_Morgan_conj Collect_disj_eq finite_Un}
   320                  |> fst o HOLogic.dest_eq
   322                  |> fst o HOLogic.dest_eq
   321                  |> dest_comb
   323                  |> dest_comb
   322           val supp_abs_tac = 
   324           val supp_abs_tac = 
   323             case (AList.lookup (op=) (qtrms ~~ bclausess) (head_of arg)) of
   325             case (AList.lookup (op=) (qtrms ~~ bclausess) (head_of arg)) of
   324               SOME bclauses => EVERY' (mk_supp_abs_tac ctxt bclauses)
   326               SOME bclauses => EVERY' (mk_supp_abs_tac ctxt bclauses)
   325             | NONE => mk_bn_supp_abs_tac fv_fun
   327             | NONE => mk_bn_supp_abs_tac ctxt fv_fun
   326           val eqvt_rconfig = eqvt_relaxed_config addpres (perm_simps @ fv_bn_eqvts)
   328           val eqvt_rconfig = eqvt_relaxed_config addpres (perm_simps @ fv_bn_eqvts)
   327         in
   329         in
   328           EVERY' [ TRY o asm_full_simp_tac (add_ss (@{thm supp_Pair[symmetric]}::fv_simps)),
   330           EVERY' [ TRY o asm_full_simp_tac (add_simpset ctxt (@{thm supp_Pair[symmetric]}::fv_simps)),
   329                    TRY o supp_abs_tac,
   331                    TRY o supp_abs_tac,
   330                    TRY o simp_tac (add_ss @{thms supp_def supp_rel_def}),
   332                    TRY o simp_tac (add_simpset ctxt @{thms supp_def supp_rel_def}),
   331                    TRY o eqvt_tac ctxt eqvt_rconfig, 
   333                    TRY o eqvt_tac ctxt eqvt_rconfig, 
   332                    TRY o simp_tac (add_ss (@{thms Abs_eq_iff} @ eq_iffs)),
   334                    TRY o simp_tac (add_simpset ctxt (@{thms Abs_eq_iff} @ eq_iffs)),
   333                    TRY o asm_full_simp_tac (add_ss thms3),
   335                    TRY o asm_full_simp_tac (add_simpset ctxt thms3),
   334                    TRY o simp_tac (add_ss thms2),
   336                    TRY o simp_tac (add_simpset ctxt thms2),
   335                    TRY o asm_full_simp_tac (add_ss (thms1 @ (symmetric fv_bn_eqvts)))] i
   337                    TRY o asm_full_simp_tac (add_simpset ctxt (thms1 @ (symmetric fv_bn_eqvts)))] i
   336         end)
   338         end)
   337   in
   339   in
   338     induct_prove qtys (goals1 @ goals2) qinduct tac ctxt
   340     induct_prove qtys (goals1 @ goals2) qinduct tac ctxt
   339     |> map atomize
   341     |> map atomize
   340     |> map (simplify (HOL_basic_ss addsimps @{thms fun_eq_iff[symmetric]}))
   342     |> map (simplify (put_simpset HOL_basic_ss ctxt addsimps @{thms fun_eq_iff[symmetric]}))
   341   end
   343   end
   342 
   344 
   343 
   345 
   344 fun prove_bns_finite qtys qbns qinduct qbn_simps ctxt =
   346 fun prove_bns_finite qtys qbns qinduct qbn_simps ctxt =
   345   let
   347   let
   350       in
   352       in
   351         (arg_ty, fn x => finite $ (to_set (qbn $ x)))
   353         (arg_ty, fn x => finite $ (to_set (qbn $ x)))
   352       end
   354       end
   353 
   355 
   354     val props = map mk_goal qbns
   356     val props = map mk_goal qbns
   355     val ss_tac = asm_full_simp_tac (HOL_basic_ss addsimps (qbn_simps @ 
   357     val ss_tac = asm_full_simp_tac (put_simpset HOL_basic_ss ctxt addsimps (qbn_simps @ 
   356       @{thms set.simps set_append finite_insert finite.emptyI finite_Un}))
   358       @{thms set.simps set_append finite_insert finite.emptyI finite_Un}))
   357   in
   359   in
   358     induct_prove qtys props qinduct (K ss_tac) ctxt
   360     induct_prove qtys props qinduct (K ss_tac) ctxt
   359   end
   361   end
   360 
   362 
   371         (arg_ty, fn x => (mk_id (Abs ("", arg_ty, alpha_bn $ Bound 0 $ (qperm_bn $ p $ Bound 0)))) $ x)
   373         (arg_ty, fn x => (mk_id (Abs ("", arg_ty, alpha_bn $ Bound 0 $ (qperm_bn $ p $ Bound 0)))) $ x)
   372       end
   374       end
   373 
   375 
   374     val props = map2 mk_goal qperm_bns alpha_bns
   376     val props = map2 mk_goal qperm_bns alpha_bns
   375     val ss = @{thm id_def}::qperm_bn_simps @ qeq_iffs @ qalpha_refls
   377     val ss = @{thm id_def}::qperm_bn_simps @ qeq_iffs @ qalpha_refls
   376     val ss_tac = asm_full_simp_tac (HOL_ss addsimps ss)
   378     val ss_tac = asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps ss)
   377   in
   379   in
   378     induct_prove qtys props qinduct (K ss_tac) ctxt'
   380     induct_prove qtys props qinduct (K ss_tac) ctxt'
   379     |> Proof_Context.export ctxt' ctxt
   381     |> Proof_Context.export ctxt' ctxt
   380     |> map (simplify (HOL_basic_ss addsimps @{thms id_def})) 
   382     |> map (simplify (put_simpset HOL_basic_ss ctxt addsimps @{thms id_def})) 
   381   end
   383   end
   382 
   384 
   383 fun prove_permute_bn_thms qtys qbns qperm_bns qinduct qperm_bn_simps qbn_defs qbn_eqvts ctxt =
   385 fun prove_permute_bn_thms qtys qbns qperm_bns qinduct qperm_bn_simps qbn_defs qbn_eqvts ctxt =
   384   let 
   386   let 
   385     val ([p], ctxt') = Variable.variant_fixes ["p"] ctxt
   387     val ([p], ctxt') = Variable.variant_fixes ["p"] ctxt
   395       end
   397       end
   396 
   398 
   397     val props = map2 mk_goal qbns qperm_bns
   399     val props = map2 mk_goal qbns qperm_bns
   398     val ss = @{thm id_def}::qperm_bn_simps @ qbn_defs
   400     val ss = @{thm id_def}::qperm_bn_simps @ qbn_defs
   399     val ss_tac = 
   401     val ss_tac = 
   400       EVERY' [asm_full_simp_tac (HOL_basic_ss addsimps ss),
   402       EVERY' [asm_full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps ss),
   401               TRY o eqvt_tac ctxt' (eqvt_strict_config addpres qbn_eqvts),
   403               TRY o eqvt_tac ctxt' (eqvt_strict_config addpres qbn_eqvts),
   402               TRY o asm_full_simp_tac HOL_basic_ss]
   404               TRY o asm_full_simp_tac (put_simpset HOL_basic_ss ctxt')]
   403   in
   405   in
   404     induct_prove qtys props qinduct (K ss_tac) ctxt'
   406     induct_prove qtys props qinduct (K ss_tac) ctxt'
   405     |> Proof_Context.export ctxt' ctxt 
   407     |> Proof_Context.export ctxt' ctxt 
   406     |> map (simplify (HOL_basic_ss addsimps @{thms id_def})) 
   408     |> map (simplify (put_simpset HOL_basic_ss ctxt addsimps @{thms id_def})) 
   407   end
   409   end
   408 
   410 
   409 
   411 
   410 
   412 
   411 (*** proves strong exhauts theorems ***)
   413 (*** proves strong exhauts theorems ***)
   497     val ss = bn_finite_thms @ @{thms supp_Pair finite_supp finite_sets_supp} 
   499     val ss = bn_finite_thms @ @{thms supp_Pair finite_supp finite_sets_supp} 
   498       @ @{thms finite.intros finite_Un finite_set finite_fset}  
   500       @ @{thms finite.intros finite_Un finite_set finite_fset}  
   499   in
   501   in
   500     Goal.prove ctxt [] [] goal
   502     Goal.prove ctxt [] [] goal
   501       (K (HEADGOAL (rtac @{thm at_set_avoiding1}
   503       (K (HEADGOAL (rtac @{thm at_set_avoiding1}
   502           THEN_ALL_NEW (simp_tac (HOL_ss addsimps ss)))))
   504           THEN_ALL_NEW (simp_tac (put_simpset HOL_ss ctxt addsimps ss)))))
   503   end
   505   end
   504 
   506 
   505 
   507 
   506 (* derives an abs_eq theorem of the form 
   508 (* derives an abs_eq theorem of the form 
   507 
   509 
   537         val tac1 = 
   539         val tac1 = 
   538           if rec_flag
   540           if rec_flag
   539           then resolve_tac @{thms Abs_rename_set' Abs_rename_res' Abs_rename_lst'}
   541           then resolve_tac @{thms Abs_rename_set' Abs_rename_res' Abs_rename_lst'}
   540           else resolve_tac @{thms Abs_rename_set  Abs_rename_res  Abs_rename_lst}
   542           else resolve_tac @{thms Abs_rename_set  Abs_rename_res  Abs_rename_lst}
   541         
   543         
   542         val tac2 = EVERY' [simp_tac (HOL_basic_ss addsimps ss), TRY o simp_tac HOL_ss] 
   544         val tac2 =
       
   545           EVERY' [simp_tac (put_simpset HOL_basic_ss ctxt addsimps ss),
       
   546             TRY o simp_tac (put_simpset HOL_ss ctxt)]
   543      in
   547      in
   544        [ Goal.prove ctxt [] [] goal (K (HEADGOAL (tac1 THEN_ALL_NEW tac2)))
   548        [ Goal.prove ctxt [] [] goal (K (HEADGOAL (tac1 THEN_ALL_NEW tac2)))
   545          |> (if rec_flag
   549          |> (if rec_flag
   546              then eqvt_rule ctxt (eqvt_strict_config addpres bn_eqvt)
   550              then eqvt_rule ctxt (eqvt_strict_config addpres bn_eqvt)
   547              else eqvt_rule ctxt (eqvt_strict_config addpres permute_bns)) ]
   551              else eqvt_rule ctxt (eqvt_strict_config addpres permute_bns)) ]
   561             val parms = map (term_of o snd) params
   565             val parms = map (term_of o snd) params
   562             val fthm = fresh_thm ctxt c parms binders bn_finite_thms 
   566             val fthm = fresh_thm ctxt c parms binders bn_finite_thms 
   563   
   567   
   564             val ss = @{thms fresh_star_Pair union_eqvt fresh_star_Un}
   568             val ss = @{thms fresh_star_Pair union_eqvt fresh_star_Un}
   565             val (([(_, fperm)], fprops), ctxt') = Obtain.result
   569             val (([(_, fperm)], fprops), ctxt') = Obtain.result
   566               (K (EVERY1 [etac exE, 
   570               (fn ctxt' => EVERY1 [etac exE, 
   567                           full_simp_tac (HOL_basic_ss addsimps ss), 
   571                             full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps ss), 
   568                           REPEAT o (etac @{thm conjE})])) [fthm] ctxt 
   572                             REPEAT o (etac @{thm conjE})]) [fthm] ctxt
   569   
   573   
   570             val abs_eq_thms = flat 
   574             val abs_eq_thms = flat 
   571              (map (abs_eq_thm ctxt fprops (term_of fperm) parms bn_eqvt permute_bns) bclauses)
   575              (map (abs_eq_thm ctxt fprops (term_of fperm) parms bn_eqvt permute_bns) bclauses)
   572 
   576 
   573             val ((_, eqs), ctxt'') = Obtain.result
   577             val ((_, eqs), ctxt'') = Obtain.result
   574               (K (EVERY1 
   578               (fn ctxt'' => EVERY1 
   575                    [ REPEAT o (etac @{thm exE}), 
   579                    [ REPEAT o (etac @{thm exE}), 
   576                      REPEAT o (etac @{thm conjE}),
   580                      REPEAT o (etac @{thm conjE}),
   577                      REPEAT o (dtac setify),
   581                      REPEAT o (dtac setify),
   578                      full_simp_tac (HOL_basic_ss addsimps @{thms set_append set.simps})])) abs_eq_thms ctxt' 
   582                      full_simp_tac (put_simpset HOL_basic_ss ctxt''
       
   583                       addsimps @{thms set_append set.simps})]) abs_eq_thms ctxt'
   579 
   584 
   580             val (abs_eqs, peqs) = split_filter is_abs_eq eqs
   585             val (abs_eqs, peqs) = split_filter is_abs_eq eqs
   581 
   586 
   582             val fprops' = 
   587             val fprops' = 
   583               map (eqvt_rule ctxt (eqvt_strict_config addpres permute_bns)) fprops
   588               map (eqvt_rule ctxt (eqvt_strict_config addpres permute_bns)) fprops
   584               @ map (eqvt_rule ctxt (eqvt_strict_config addpres bn_eqvt)) fprops
   589               @ map (eqvt_rule ctxt (eqvt_strict_config addpres bn_eqvt)) fprops
   585 
   590 
   586             (* for freshness conditions *) 
   591             (* for freshness conditions *) 
   587             val tac1 = SOLVED' (EVERY'
   592             val tac1 = SOLVED' (EVERY'
   588               [ simp_tac (HOL_basic_ss addsimps peqs),
   593               [ simp_tac (put_simpset HOL_basic_ss ctxt'' addsimps peqs),
   589                 rewrite_goal_tac (@{thms fresh_star_Un[THEN eq_reflection]}),
   594                 rewrite_goal_tac (@{thms fresh_star_Un[THEN eq_reflection]}),
   590                 conj_tac (DETERM o resolve_tac fprops') ]) 
   595                 conj_tac (DETERM o resolve_tac fprops') ]) 
   591 
   596 
   592             (* for equalities between constructors *)
   597             (* for equalities between constructors *)
   593             val tac2 = SOLVED' (EVERY' 
   598             val tac2 = SOLVED' (EVERY' 
   727           
   732           
   728           val thm' = cterm_instantiate (vs_ctrms ~~ assigns) thm
   733           val thm' = cterm_instantiate (vs_ctrms ~~ assigns) thm
   729         in
   734         in
   730           rtac thm' 1
   735           rtac thm' 1
   731         end) ctxt
   736         end) ctxt
   732       THEN_ALL_NEW asm_full_simp_tac HOL_basic_ss
   737       THEN_ALL_NEW asm_full_simp_tac (put_simpset HOL_basic_ss ctxt)
   733  
   738  
       
   739     (* FIXME proper goal context *)
   734     val size_simp_tac = 
   740     val size_simp_tac = 
   735       simp_tac (size_simpset addsimps (@{thms comp_def snd_conv} @ size_thms))
   741       simp_tac (put_simpset size_ss lthy'' addsimps (@{thms comp_def snd_conv} @ size_thms))
   736   in
   742   in
   737     Goal.prove_multi lthy'' [] prems' concls
   743     Goal.prove_multi lthy'' [] prems' concls
   738       (fn {prems, context} => 
   744       (fn {prems, context} => 
   739         Induction_Schema.induction_schema_tac context prems  
   745         Induction_Schema.induction_schema_tac context prems  
   740         THEN RANGE (map (pat_tac context) exhausts) 1
   746         THEN RANGE (map (pat_tac context) exhausts) 1