src/HOL/Nominal/nominal_inductive2.ML
changeset 51717 9e7d1c139569
parent 50771 2852f997bfb5
child 54895 515630483010
equal deleted inserted replaced
51709:19b47bfac6ef 51717:9e7d1c139569
    19 val inductive_atomize = @{thms induct_atomize};
    19 val inductive_atomize = @{thms induct_atomize};
    20 val inductive_rulify = @{thms induct_rulify};
    20 val inductive_rulify = @{thms induct_rulify};
    21 
    21 
    22 fun rulify_term thy = Raw_Simplifier.rewrite_term thy inductive_rulify [];
    22 fun rulify_term thy = Raw_Simplifier.rewrite_term thy inductive_rulify [];
    23 
    23 
    24 val atomize_conv =
    24 fun atomize_conv ctxt =
    25   Raw_Simplifier.rewrite_cterm (true, false, false) (K (K NONE))
    25   Raw_Simplifier.rewrite_cterm (true, false, false) (K (K NONE))
    26     (HOL_basic_ss addsimps inductive_atomize);
    26     (put_simpset HOL_basic_ss ctxt addsimps inductive_atomize);
    27 val atomize_intr = Conv.fconv_rule (Conv.prems_conv ~1 atomize_conv);
    27 fun atomize_intr ctxt = Conv.fconv_rule (Conv.prems_conv ~1 (atomize_conv ctxt));
    28 fun atomize_induct ctxt = Conv.fconv_rule (Conv.prems_conv ~1
    28 fun atomize_induct ctxt = Conv.fconv_rule (Conv.prems_conv ~1
    29   (Conv.params_conv ~1 (K (Conv.prems_conv ~1 atomize_conv)) ctxt));
    29   (Conv.params_conv ~1 (K (Conv.prems_conv ~1 (atomize_conv ctxt))) ctxt));
    30 
    30 
    31 val fresh_postprocess =
    31 fun fresh_postprocess ctxt =
    32   Simplifier.full_simplify (HOL_basic_ss addsimps
    32   Simplifier.full_simplify (put_simpset HOL_basic_ss ctxt addsimps
    33     [@{thm fresh_star_set_eq}, @{thm fresh_star_Un_elim},
    33     [@{thm fresh_star_set_eq}, @{thm fresh_star_Un_elim},
    34      @{thm fresh_star_insert_elim}, @{thm fresh_star_empty_elim}]);
    34      @{thm fresh_star_insert_elim}, @{thm fresh_star_empty_elim}]);
    35 
    35 
    36 fun preds_of ps t = inter (op = o apsnd dest_Free) ps (Term.add_frees t []);
    36 fun preds_of ps t = inter (op = o apsnd dest_Free) ps (Term.add_frees t []);
    37 
    37 
    42 
    42 
    43 fun mk_perm_bool pi th = th RS Drule.cterm_instantiate
    43 fun mk_perm_bool pi th = th RS Drule.cterm_instantiate
    44   [(perm_boolI_pi, pi)] perm_boolI;
    44   [(perm_boolI_pi, pi)] perm_boolI;
    45 
    45 
    46 fun mk_perm_bool_simproc names = Simplifier.simproc_global_i
    46 fun mk_perm_bool_simproc names = Simplifier.simproc_global_i
    47   (theory_of_thm perm_bool) "perm_bool" [@{term "perm pi x"}] (fn thy => fn ss =>
    47   (theory_of_thm perm_bool) "perm_bool" [@{term "perm pi x"}] (fn ctxt =>
    48     fn Const ("Nominal.perm", _) $ _ $ t =>
    48     fn Const ("Nominal.perm", _) $ _ $ t =>
    49          if member (op =) names (the_default "" (try (head_of #> dest_Const #> fst) t))
    49          if member (op =) names (the_default "" (try (head_of #> dest_Const #> fst) t))
    50          then SOME perm_bool else NONE
    50          then SOME perm_bool else NONE
    51      | _ => NONE);
    51      | _ => NONE);
    52 
    52 
   106         SOME (Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
   106         SOME (Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
   107           (subst_bounds (pis, strip_all pis t)))
   107           (subst_bounds (pis, strip_all pis t)))
   108       else NONE
   108       else NONE
   109   | inst_conj_all _ _ _ _ _ = NONE;
   109   | inst_conj_all _ _ _ _ _ = NONE;
   110 
   110 
   111 fun inst_conj_all_tac k = EVERY
   111 fun inst_conj_all_tac ctxt k = EVERY
   112   [TRY (EVERY [etac conjE 1, rtac conjI 1, atac 1]),
   112   [TRY (EVERY [etac conjE 1, rtac conjI 1, atac 1]),
   113    REPEAT_DETERM_N k (etac allE 1),
   113    REPEAT_DETERM_N k (etac allE 1),
   114    simp_tac (HOL_basic_ss addsimps [@{thm id_apply}]) 1];
   114    simp_tac (put_simpset HOL_basic_ss ctxt addsimps [@{thm id_apply}]) 1];
   115 
   115 
   116 fun map_term f t u = (case f t u of
   116 fun map_term f t u = (case f t u of
   117       NONE => map_term' f t u | x => x)
   117       NONE => map_term' f t u | x => x)
   118 and map_term' f (t $ u) (t' $ u') = (case (map_term f t t', map_term f u u') of
   118 and map_term' f (t $ u) (t' $ u') = (case (map_term f t t', map_term f u u') of
   119       (NONE, NONE) => NONE
   119       (NONE, NONE) => NONE
   288       split_list) prems |> split_list;
   288       split_list) prems |> split_list;
   289 
   289 
   290     val perm_pi_simp = Global_Theory.get_thms thy "perm_pi_simp";
   290     val perm_pi_simp = Global_Theory.get_thms thy "perm_pi_simp";
   291     val pt2_atoms = map (fn a => Global_Theory.get_thm thy
   291     val pt2_atoms = map (fn a => Global_Theory.get_thm thy
   292       ("pt_" ^ Long_Name.base_name a ^ "2")) atoms;
   292       ("pt_" ^ Long_Name.base_name a ^ "2")) atoms;
   293     val eqvt_ss = Simplifier.global_context thy HOL_basic_ss
   293     val eqvt_ss = simpset_of (Simplifier.global_context thy HOL_basic_ss
   294       addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms)
   294       addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms)
   295       addsimprocs [mk_perm_bool_simproc ["Fun.id"],
   295       addsimprocs [mk_perm_bool_simproc ["Fun.id"],
   296         NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun];
   296         NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun]);
   297     val fresh_star_bij = Global_Theory.get_thms thy "fresh_star_bij";
   297     val fresh_star_bij = Global_Theory.get_thms thy "fresh_star_bij";
   298     val pt_insts = map (NominalAtoms.pt_inst_of thy) atoms;
   298     val pt_insts = map (NominalAtoms.pt_inst_of thy) atoms;
   299     val at_insts = map (NominalAtoms.at_inst_of thy) atoms;
   299     val at_insts = map (NominalAtoms.at_inst_of thy) atoms;
   300     val dj_thms = maps (fn a =>
   300     val dj_thms = maps (fn a =>
   301       map (NominalAtoms.dj_thm_of thy a) (remove (op =) a atoms)) atoms;
   301       map (NominalAtoms.dj_thm_of thy a) (remove (op =) a atoms)) atoms;
   320           ("fs_" ^ Long_Name.base_name atom ^ "1");
   320           ("fs_" ^ Long_Name.base_name atom ^ "1");
   321         val avoid_th = Drule.instantiate'
   321         val avoid_th = Drule.instantiate'
   322           [SOME (ctyp_of thy (fastype_of p))] [SOME (cterm_of thy p)]
   322           [SOME (ctyp_of thy (fastype_of p))] [SOME (cterm_of thy p)]
   323           ([at_inst, fin, fs_atom] MRS @{thm at_set_avoiding});
   323           ([at_inst, fin, fs_atom] MRS @{thm at_set_avoiding});
   324         val (([(_, cx)], th1 :: th2 :: ths), ctxt') = Obtain.result
   324         val (([(_, cx)], th1 :: th2 :: ths), ctxt') = Obtain.result
   325           (fn _ => EVERY
   325           (fn ctxt' => EVERY
   326             [rtac avoid_th 1,
   326             [rtac avoid_th 1,
   327              full_simp_tac (HOL_ss addsimps [@{thm fresh_star_prod_set}]) 1,
   327              full_simp_tac (put_simpset HOL_ss ctxt' addsimps [@{thm fresh_star_prod_set}]) 1,
   328              full_simp_tac (HOL_basic_ss addsimps [@{thm id_apply}]) 1,
   328              full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps [@{thm id_apply}]) 1,
   329              rotate_tac 1 1,
   329              rotate_tac 1 1,
   330              REPEAT (etac conjE 1)])
   330              REPEAT (etac conjE 1)])
   331           [] ctxt;
   331           [] ctxt;
   332         val (Ts1, _ :: Ts2) = take_prefix (not o equal T) (map snd sets);
   332         val (Ts1, _ :: Ts2) = take_prefix (not o equal T) (map snd sets);
   333         val pTs = map NominalAtoms.mk_permT (Ts1 @ Ts2);
   333         val pTs = map NominalAtoms.mk_permT (Ts1 @ Ts2);
   338           Goal.prove ctxt [] []
   338           Goal.prove ctxt [] []
   339             (Logic.list_all (map (pair "pi") pTs, HOLogic.mk_Trueprop
   339             (Logic.list_all (map (pair "pi") pTs, HOLogic.mk_Trueprop
   340                (f $ fold_rev (NominalDatatype.mk_perm (rev pTs))
   340                (f $ fold_rev (NominalDatatype.mk_perm (rev pTs))
   341                   (pis1 @ pi :: pis2) l $ r)))
   341                   (pis1 @ pi :: pis2) l $ r)))
   342             (fn _ => cut_facts_tac [th2] 1 THEN
   342             (fn _ => cut_facts_tac [th2] 1 THEN
   343                full_simp_tac (HOL_basic_ss addsimps perm_set_forget) 1) |>
   343                full_simp_tac (put_simpset HOL_basic_ss ctxt addsimps perm_set_forget) 1) |>
   344           Simplifier.simplify eqvt_ss
   344           Simplifier.simplify (put_simpset eqvt_ss ctxt)
   345       in
   345       in
   346         (freshs @ [term_of cx],
   346         (freshs @ [term_of cx],
   347          ths1 @ ths, ths2 @ [th1], ths3 @ [th2'], ctxt')
   347          ths1 @ ths, ths2 @ [th1], ths3 @ [th2'], ctxt')
   348       end;
   348       end;
   349 
   349 
   351       Goal.prove ctxt' [] prems' concl' (fn {prems = ihyps, context = ctxt} =>
   351       Goal.prove ctxt' [] prems' concl' (fn {prems = ihyps, context = ctxt} =>
   352         let val th = Goal.prove ctxt [] [] concl (fn {context, ...} =>
   352         let val th = Goal.prove ctxt [] [] concl (fn {context, ...} =>
   353           rtac raw_induct 1 THEN
   353           rtac raw_induct 1 THEN
   354           EVERY (maps (fn (((((_, sets, oprems, _),
   354           EVERY (maps (fn (((((_, sets, oprems, _),
   355               vc_compat_ths), vc_compat_vs), ihyp), vs_ihypt) =>
   355               vc_compat_ths), vc_compat_vs), ihyp), vs_ihypt) =>
   356             [REPEAT (rtac allI 1), simp_tac eqvt_ss 1,
   356             [REPEAT (rtac allI 1), simp_tac (put_simpset eqvt_ss context) 1,
   357              SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} =>
   357              SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} =>
   358                let
   358                let
   359                  val (cparams', (pis, z)) =
   359                  val (cparams', (pis, z)) =
   360                    chop (length params - length atomTs - 1) (map #2 params) ||>
   360                    chop (length params - length atomTs - 1) (map #2 params) ||>
   361                    (map term_of #> split_last);
   361                    (map term_of #> split_last);
   377                        strip_comb (HOLogic.dest_Trueprop (concl_of th'))
   377                        strip_comb (HOLogic.dest_Trueprop (concl_of th'))
   378                    in
   378                    in
   379                      Goal.prove ctxt' [] []
   379                      Goal.prove ctxt' [] []
   380                        (HOLogic.mk_Trueprop (list_comb (h,
   380                        (HOLogic.mk_Trueprop (list_comb (h,
   381                           map (fold_rev (NominalDatatype.mk_perm []) pis) ts)))
   381                           map (fold_rev (NominalDatatype.mk_perm []) pis) ts)))
   382                        (fn _ => simp_tac (HOL_basic_ss addsimps
   382                        (fn _ => simp_tac (put_simpset HOL_basic_ss ctxt' addsimps
   383                           (fresh_star_bij @ finite_ineq)) 1 THEN rtac th' 1)
   383                           (fresh_star_bij @ finite_ineq)) 1 THEN rtac th' 1)
   384                    end) vc_compat_ths vc_compat_vs;
   384                    end) vc_compat_ths vc_compat_vs;
   385                  val (vc_compat_ths1, vc_compat_ths2) =
   385                  val (vc_compat_ths1, vc_compat_ths2) =
   386                    chop (length vc_compat_ths - length sets) vc_compat_ths';
   386                    chop (length vc_compat_ths - length sets) vc_compat_ths';
   387                  val vc_compat_ths1' = map
   387                  val vc_compat_ths1' = map
   388                    (Conv.fconv_rule (Conv.arg_conv (Conv.arg_conv
   388                    (Conv.fconv_rule (Conv.arg_conv (Conv.arg_conv
   389                       (Simplifier.rewrite eqvt_ss)))) vc_compat_ths1;
   389                       (Simplifier.rewrite (put_simpset eqvt_ss ctxt'))))) vc_compat_ths1;
   390                  val (pis', fresh_ths1, fresh_ths2, fresh_ths3, ctxt'') = fold
   390                  val (pis', fresh_ths1, fresh_ths2, fresh_ths3, ctxt'') = fold
   391                    (obtain_fresh_name ts sets)
   391                    (obtain_fresh_name ts sets)
   392                    (map snd sets' ~~ vc_compat_ths2) ([], [], [], [], ctxt');
   392                    (map snd sets' ~~ vc_compat_ths2) ([], [], [], [], ctxt');
   393                  fun concat_perm pi1 pi2 =
   393                  fun concat_perm pi1 pi2 =
   394                    let val T = fastype_of pi1
   394                    let val T = fastype_of pi1
   399                  val pis'' = fold_rev (concat_perm #> map) pis' pis;
   399                  val pis'' = fold_rev (concat_perm #> map) pis' pis;
   400                  val ihyp' = inst_params thy vs_ihypt ihyp
   400                  val ihyp' = inst_params thy vs_ihypt ihyp
   401                    (map (fold_rev (NominalDatatype.mk_perm [])
   401                    (map (fold_rev (NominalDatatype.mk_perm [])
   402                       (pis' @ pis) #> cterm_of thy) params' @ [cterm_of thy z]);
   402                       (pis' @ pis) #> cterm_of thy) params' @ [cterm_of thy z]);
   403                  fun mk_pi th =
   403                  fun mk_pi th =
   404                    Simplifier.simplify (HOL_basic_ss addsimps [@{thm id_apply}]
   404                    Simplifier.simplify (put_simpset HOL_basic_ss ctxt addsimps [@{thm id_apply}]
   405                        addsimprocs [NominalDatatype.perm_simproc])
   405                        addsimprocs [NominalDatatype.perm_simproc])
   406                      (Simplifier.simplify eqvt_ss
   406                      (Simplifier.simplify (put_simpset eqvt_ss ctxt)
   407                        (fold_rev (mk_perm_bool o cterm_of thy)
   407                        (fold_rev (mk_perm_bool o cterm_of thy)
   408                          (pis' @ pis) th));
   408                          (pis' @ pis) th));
   409                  val gprems2 = map (fn (th, t) =>
   409                  val gprems2 = map (fn (th, t) =>
   410                    if null (preds_of ps t) then mk_pi th
   410                    if null (preds_of ps t) then mk_pi th
   411                    else
   411                    else
   412                      mk_pi (the (map_thm ctxt (inst_conj_all names ps (rev pis''))
   412                      mk_pi (the (map_thm ctxt (inst_conj_all names ps (rev pis''))
   413                        (inst_conj_all_tac (length pis'')) monos (SOME t) th)))
   413                        (inst_conj_all_tac ctxt (length pis'')) monos (SOME t) th)))
   414                    (gprems ~~ oprems);
   414                    (gprems ~~ oprems);
   415                  val perm_freshs_freshs' = map (fn (th, (_, T)) =>
   415                  val perm_freshs_freshs' = map (fn (th, (_, T)) =>
   416                    th RS the (AList.lookup op = perm_freshs_freshs T))
   416                    th RS the (AList.lookup op = perm_freshs_freshs T))
   417                      (fresh_ths2 ~~ sets);
   417                      (fresh_ths2 ~~ sets);
   418                  val th = Goal.prove ctxt'' [] []
   418                  val th = Goal.prove ctxt'' [] []
   419                    (HOLogic.mk_Trueprop (list_comb (P $ hd ts,
   419                    (HOLogic.mk_Trueprop (list_comb (P $ hd ts,
   420                      map (fold_rev (NominalDatatype.mk_perm []) pis') (tl ts))))
   420                      map (fold_rev (NominalDatatype.mk_perm []) pis') (tl ts))))
   421                    (fn _ => EVERY ([simp_tac eqvt_ss 1, rtac ihyp' 1] @
   421                    (fn _ => EVERY ([simp_tac (put_simpset eqvt_ss ctxt'') 1, rtac ihyp' 1] @
   422                      map (fn th => rtac th 1) fresh_ths3 @
   422                      map (fn th => rtac th 1) fresh_ths3 @
   423                      [REPEAT_DETERM_N (length gprems)
   423                      [REPEAT_DETERM_N (length gprems)
   424                        (simp_tac (HOL_basic_ss
   424                        (simp_tac (put_simpset HOL_basic_ss ctxt''
   425                           addsimps [inductive_forall_def']
   425                           addsimps [inductive_forall_def']
   426                           addsimprocs [NominalDatatype.perm_simproc]) 1 THEN
   426                           addsimprocs [NominalDatatype.perm_simproc]) 1 THEN
   427                         resolve_tac gprems2 1)]));
   427                         resolve_tac gprems2 1)]));
   428                  val final = Goal.prove ctxt'' [] [] (term_of concl)
   428                  val final = Goal.prove ctxt'' [] [] (term_of concl)
   429                    (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (HOL_ss
   429                    (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (put_simpset HOL_ss ctxt''
   430                      addsimps vc_compat_ths1' @ fresh_ths1 @
   430                      addsimps vc_compat_ths1' @ fresh_ths1 @
   431                        perm_freshs_freshs') 1);
   431                        perm_freshs_freshs') 1);
   432                  val final' = Proof_Context.export ctxt'' ctxt' [final];
   432                  val final' = Proof_Context.export ctxt'' ctxt' [final];
   433                in resolve_tac final' 1 end) context 1])
   433                in resolve_tac final' 1 end) context 1])
   434                  (prems ~~ thss ~~ vc_compat' ~~ ihyps ~~ prems'')))
   434                  (prems ~~ thss ~~ vc_compat' ~~ ihyps ~~ prems'')))
   435         in
   435         in
   436           cut_facts_tac [th] 1 THEN REPEAT (etac conjE 1) THEN
   436           cut_facts_tac [th] 1 THEN REPEAT (etac conjE 1) THEN
   437           REPEAT (REPEAT (resolve_tac [conjI, impI] 1) THEN
   437           REPEAT (REPEAT (resolve_tac [conjI, impI] 1) THEN
   438             etac impE 1 THEN atac 1 THEN REPEAT (etac @{thm allE_Nil} 1) THEN
   438             etac impE 1 THEN atac 1 THEN REPEAT (etac @{thm allE_Nil} 1) THEN
   439             asm_full_simp_tac (simpset_of ctxt) 1)
   439             asm_full_simp_tac ctxt 1)
   440         end) |>
   440         end) |>
   441         fresh_postprocess |>
   441         fresh_postprocess ctxt' |>
   442         singleton (Proof_Context.export ctxt' ctxt);
   442         singleton (Proof_Context.export ctxt' ctxt);
   443 
   443 
   444   in
   444   in
   445     ctxt'' |>
   445     ctxt'' |>
   446     Proof.theorem NONE (fn thss => fn ctxt =>  (* FIXME ctxt/ctxt' should be called lthy/lthy' *)
   446     Proof.theorem NONE (fn thss => fn ctxt =>  (* FIXME ctxt/ctxt' should be called lthy/lthy' *)
   448         val rec_name = space_implode "_" (map Long_Name.base_name names);
   448         val rec_name = space_implode "_" (map Long_Name.base_name names);
   449         val rec_qualified = Binding.qualify false rec_name;
   449         val rec_qualified = Binding.qualify false rec_name;
   450         val ind_case_names = Rule_Cases.case_names induct_cases;
   450         val ind_case_names = Rule_Cases.case_names induct_cases;
   451         val induct_cases' = Inductive.partition_rules' raw_induct
   451         val induct_cases' = Inductive.partition_rules' raw_induct
   452           (intrs ~~ induct_cases); 
   452           (intrs ~~ induct_cases); 
   453         val thss' = map (map atomize_intr) thss;
   453         val thss' = map (map (atomize_intr ctxt)) thss;
   454         val thsss = Inductive.partition_rules' raw_induct (intrs ~~ thss');
   454         val thsss = Inductive.partition_rules' raw_induct (intrs ~~ thss');
   455         val strong_raw_induct =
   455         val strong_raw_induct =
   456           mk_ind_proof ctxt thss' |> Inductive.rulify;
   456           mk_ind_proof ctxt thss' |> Inductive.rulify ctxt;
   457         val strong_induct_atts =
   457         val strong_induct_atts =
   458           map (Attrib.internal o K)
   458           map (Attrib.internal o K)
   459             [ind_case_names, Rule_Cases.consumes (~ (Thm.nprems_of strong_raw_induct))];
   459             [ind_case_names, Rule_Cases.consumes (~ (Thm.nprems_of strong_raw_induct))];
   460         val strong_induct =
   460         val strong_induct =
   461           if length names > 1 then strong_raw_induct
   461           if length names > 1 then strong_raw_induct