src/HOL/Nominal/nominal_inductive2.ML
author wenzelm
Sun Mar 08 17:26:14 2009 +0100 (2009-03-08)
changeset 30364 577edc39b501
parent 30307 6c74ef5a349f
child 30450 7655e6533209
permissions -rw-r--r--
moved basic algebra of long names from structure NameSpace to Long_Name;
     1 (*  Title:      HOL/Nominal/nominal_inductive2.ML
     2     Author:     Stefan Berghofer, TU Muenchen
     3 
     4 Infrastructure for proving equivariance and strong induction theorems
     5 for inductive predicates involving nominal datatypes.
     6 Experimental version that allows to avoid lists of atoms.
     7 *)
     8 
     9 signature NOMINAL_INDUCTIVE2 =
    10 sig
    11   val prove_strong_ind: string -> (string * string list) list -> local_theory -> Proof.state
    12 end
    13 
    14 structure NominalInductive2 : NOMINAL_INDUCTIVE2 =
    15 struct
    16 
    17 val inductive_forall_name = "HOL.induct_forall";
    18 val inductive_forall_def = thm "induct_forall_def";
    19 val inductive_atomize = thms "induct_atomize";
    20 val inductive_rulify = thms "induct_rulify";
    21 
    22 fun rulify_term thy = MetaSimplifier.rewrite_term thy inductive_rulify [];
    23 
    24 val atomize_conv =
    25   MetaSimplifier.rewrite_cterm (true, false, false) (K (K NONE))
    26     (HOL_basic_ss addsimps inductive_atomize);
    27 val atomize_intr = Conv.fconv_rule (Conv.prems_conv ~1 atomize_conv);
    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));
    30 
    31 val fresh_postprocess =
    32   Simplifier.full_simplify (HOL_basic_ss addsimps
    33     [@{thm fresh_star_set_eq}, @{thm fresh_star_Un_elim},
    34      @{thm fresh_star_insert_elim}, @{thm fresh_star_empty_elim}]);
    35 
    36 fun preds_of ps t = gen_inter (op = o apfst dest_Free) (ps, Term.add_frees t []);
    37 
    38 val perm_bool = mk_meta_eq (thm "perm_bool");
    39 val perm_boolI = thm "perm_boolI";
    40 val (_, [perm_boolI_pi, _]) = Drule.strip_comb (snd (Thm.dest_comb
    41   (Drule.strip_imp_concl (cprop_of perm_boolI))));
    42 
    43 fun mk_perm_bool pi th = th RS Drule.cterm_instantiate
    44   [(perm_boolI_pi, pi)] perm_boolI;
    45 
    46 fun mk_perm_bool_simproc names = Simplifier.simproc_i
    47   (theory_of_thm perm_bool) "perm_bool" [@{term "perm pi x"}] (fn thy => fn ss =>
    48     fn Const ("Nominal.perm", _) $ _ $ t =>
    49          if the_default "" (try (head_of #> dest_Const #> fst) t) mem names
    50          then SOME perm_bool else NONE
    51      | _ => NONE);
    52 
    53 fun transp ([] :: _) = []
    54   | transp xs = map hd xs :: transp (map tl xs);
    55 
    56 fun add_binders thy i (t as (_ $ _)) bs = (case strip_comb t of
    57       (Const (s, T), ts) => (case strip_type T of
    58         (Ts, Type (tname, _)) =>
    59           (case NominalPackage.get_nominal_datatype thy tname of
    60              NONE => fold (add_binders thy i) ts bs
    61            | SOME {descr, index, ...} => (case AList.lookup op =
    62                  (#3 (the (AList.lookup op = descr index))) s of
    63                NONE => fold (add_binders thy i) ts bs
    64              | SOME cargs => fst (fold (fn (xs, x) => fn (bs', cargs') =>
    65                  let val (cargs1, (u, _) :: cargs2) = chop (length xs) cargs'
    66                  in (add_binders thy i u
    67                    (fold (fn (u, T) =>
    68                       if exists (fn j => j < i) (loose_bnos u) then I
    69                       else AList.map_default op = (T, [])
    70                         (insert op aconv (incr_boundvars (~i) u)))
    71                           cargs1 bs'), cargs2)
    72                  end) cargs (bs, ts ~~ Ts))))
    73       | _ => fold (add_binders thy i) ts bs)
    74     | (u, ts) => add_binders thy i u (fold (add_binders thy i) ts bs))
    75   | add_binders thy i (Abs (_, _, t)) bs = add_binders thy (i + 1) t bs
    76   | add_binders thy i _ bs = bs;
    77 
    78 fun mk_set T [] = Const (@{const_name Set.empty}, HOLogic.mk_setT T)
    79   | mk_set T (x :: xs) =
    80       Const ("insert", T --> HOLogic.mk_setT T --> HOLogic.mk_setT T) $ x $
    81         mk_set T xs;
    82 
    83 fun split_conj f names (Const ("op &", _) $ p $ q) _ = (case head_of p of
    84       Const (name, _) =>
    85         if name mem names then SOME (f p q) else NONE
    86     | _ => NONE)
    87   | split_conj _ _ _ _ = NONE;
    88 
    89 fun strip_all [] t = t
    90   | strip_all (_ :: xs) (Const ("All", _) $ Abs (s, T, t)) = strip_all xs t;
    91 
    92 (*********************************************************************)
    93 (* maps  R ... & (ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t))  *)
    94 (* or    ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t)            *)
    95 (* to    R ... & id (ALL z. P z (pi_1 o ... o pi_n o t))             *)
    96 (* or    id (ALL z. P z (pi_1 o ... o pi_n o t))                     *)
    97 (*                                                                   *)
    98 (* where "id" protects the subformula from simplification            *)
    99 (*********************************************************************)
   100 
   101 fun inst_conj_all names ps pis (Const ("op &", _) $ p $ q) _ =
   102       (case head_of p of
   103          Const (name, _) =>
   104            if name mem names then SOME (HOLogic.mk_conj (p,
   105              Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
   106                (subst_bounds (pis, strip_all pis q))))
   107            else NONE
   108        | _ => NONE)
   109   | inst_conj_all names ps pis t u =
   110       if member (op aconv) ps (head_of u) then
   111         SOME (Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
   112           (subst_bounds (pis, strip_all pis t)))
   113       else NONE
   114   | inst_conj_all _ _ _ _ _ = NONE;
   115 
   116 fun inst_conj_all_tac k = EVERY
   117   [TRY (EVERY [etac conjE 1, rtac conjI 1, atac 1]),
   118    REPEAT_DETERM_N k (etac allE 1),
   119    simp_tac (HOL_basic_ss addsimps [@{thm id_apply}]) 1];
   120 
   121 fun map_term f t u = (case f t u of
   122       NONE => map_term' f t u | x => x)
   123 and map_term' f (t $ u) (t' $ u') = (case (map_term f t t', map_term f u u') of
   124       (NONE, NONE) => NONE
   125     | (SOME t'', NONE) => SOME (t'' $ u)
   126     | (NONE, SOME u'') => SOME (t $ u'')
   127     | (SOME t'', SOME u'') => SOME (t'' $ u''))
   128   | map_term' f (Abs (s, T, t)) (Abs (s', T', t')) = (case map_term f t t' of
   129       NONE => NONE
   130     | SOME t'' => SOME (Abs (s, T, t'')))
   131   | map_term' _ _ _ = NONE;
   132 
   133 (*********************************************************************)
   134 (*         Prove  F[f t]  from  F[t],  where F is monotone           *)
   135 (*********************************************************************)
   136 
   137 fun map_thm ctxt f tac monos opt th =
   138   let
   139     val prop = prop_of th;
   140     fun prove t =
   141       Goal.prove ctxt [] [] t (fn _ =>
   142         EVERY [cut_facts_tac [th] 1, etac rev_mp 1,
   143           REPEAT_DETERM (FIRSTGOAL (resolve_tac monos)),
   144           REPEAT_DETERM (rtac impI 1 THEN (atac 1 ORELSE tac))])
   145   in Option.map prove (map_term f prop (the_default prop opt)) end;
   146 
   147 fun abs_params params t =
   148   let val vs =  map (Var o apfst (rpair 0)) (Term.rename_wrt_term t params)
   149   in (list_all (params, t), (rev vs, subst_bounds (vs, t))) end;
   150 
   151 fun inst_params thy (vs, p) th cts =
   152   let val env = Pattern.first_order_match thy (p, prop_of th)
   153     (Vartab.empty, Vartab.empty)
   154   in Thm.instantiate ([],
   155     map (Envir.subst_vars env #> cterm_of thy) vs ~~ cts) th
   156   end;
   157 
   158 fun prove_strong_ind s avoids ctxt =
   159   let
   160     val thy = ProofContext.theory_of ctxt;
   161     val ({names, ...}, {raw_induct, intrs, elims, ...}) =
   162       InductivePackage.the_inductive ctxt (Sign.intern_const thy s);
   163     val ind_params = InductivePackage.params_of raw_induct;
   164     val raw_induct = atomize_induct ctxt raw_induct;
   165     val elims = map (atomize_induct ctxt) elims;
   166     val monos = InductivePackage.get_monos ctxt;
   167     val eqvt_thms = NominalThmDecls.get_eqvt_thms ctxt;
   168     val _ = (case names \\ fold (Term.add_const_names o Thm.prop_of) eqvt_thms [] of
   169         [] => ()
   170       | xs => error ("Missing equivariance theorem for predicate(s): " ^
   171           commas_quote xs));
   172     val induct_cases = map fst (fst (RuleCases.get (the
   173       (Induct.lookup_inductP ctxt (hd names)))));
   174     val induct_cases' = if null induct_cases then replicate (length intrs) ""
   175       else induct_cases;
   176     val ([raw_induct'], ctxt') = Variable.import_terms false [prop_of raw_induct] ctxt;
   177     val concls = raw_induct' |> Logic.strip_imp_concl |> HOLogic.dest_Trueprop |>
   178       HOLogic.dest_conj |> map (HOLogic.dest_imp ##> strip_comb);
   179     val ps = map (fst o snd) concls;
   180 
   181     val _ = (case duplicates (op = o pairself fst) avoids of
   182         [] => ()
   183       | xs => error ("Duplicate case names: " ^ commas_quote (map fst xs)));
   184     val _ = (case map fst avoids \\ induct_cases of
   185         [] => ()
   186       | xs => error ("No such case(s) in inductive definition: " ^ commas_quote xs));
   187     fun mk_avoids params name sets =
   188       let
   189         val (_, ctxt') = ProofContext.add_fixes_i
   190           (map (fn (s, T) => (Binding.name s, SOME T, NoSyn)) params) ctxt;
   191         fun mk s =
   192           let
   193             val t = Syntax.read_term ctxt' s;
   194             val t' = list_abs_free (params, t) |>
   195               funpow (length params) (fn Abs (_, _, t) => t)
   196           in (t', HOLogic.dest_setT (fastype_of t)) end
   197           handle TERM _ =>
   198             error ("Expression " ^ quote s ^ " to be avoided in case " ^
   199               quote name ^ " is not a set type");
   200         fun add_set p [] = [p]
   201           | add_set (t, T) ((u, U) :: ps) =
   202               if T = U then
   203                 let val S = HOLogic.mk_setT T
   204                 in (Const (@{const_name "Un"}, S --> S --> S) $ u $ t, T) :: ps
   205                 end
   206               else (u, U) :: add_set (t, T) ps
   207       in
   208         fold (mk #> add_set) sets []
   209       end;
   210 
   211     val prems = map (fn (prem, name) =>
   212       let
   213         val prems = map (incr_boundvars 1) (Logic.strip_assums_hyp prem);
   214         val concl = incr_boundvars 1 (Logic.strip_assums_concl prem);
   215         val params = Logic.strip_params prem
   216       in
   217         (params,
   218          if null avoids then
   219            map (fn (T, ts) => (mk_set T ts, T))
   220              (fold (add_binders thy 0) (prems @ [concl]) [])
   221          else case AList.lookup op = avoids name of
   222            NONE => []
   223          | SOME sets =>
   224              map (apfst (incr_boundvars 1)) (mk_avoids params name sets),
   225          prems, strip_comb (HOLogic.dest_Trueprop concl))
   226       end) (Logic.strip_imp_prems raw_induct' ~~ induct_cases');
   227 
   228     val atomTs = distinct op = (maps (map snd o #2) prems);
   229     val atoms = map (fst o dest_Type) atomTs;
   230     val ind_sort = if null atomTs then HOLogic.typeS
   231       else Sign.certify_sort thy (map (fn a => Sign.intern_class thy
   232         ("fs_" ^ Long_Name.base_name a)) atoms);
   233     val ([fs_ctxt_tyname], _) = Name.variants ["'n"] (Variable.names_of ctxt');
   234     val ([fs_ctxt_name], ctxt'') = Variable.variant_fixes ["z"] ctxt';
   235     val fsT = TFree (fs_ctxt_tyname, ind_sort);
   236 
   237     val inductive_forall_def' = Drule.instantiate'
   238       [SOME (ctyp_of thy fsT)] [] inductive_forall_def;
   239 
   240     fun lift_pred' t (Free (s, T)) ts =
   241       list_comb (Free (s, fsT --> T), t :: ts);
   242     val lift_pred = lift_pred' (Bound 0);
   243 
   244     fun lift_prem (t as (f $ u)) =
   245           let val (p, ts) = strip_comb t
   246           in
   247             if p mem ps then
   248               Const (inductive_forall_name,
   249                 (fsT --> HOLogic.boolT) --> HOLogic.boolT) $
   250                   Abs ("z", fsT, lift_pred p (map (incr_boundvars 1) ts))
   251             else lift_prem f $ lift_prem u
   252           end
   253       | lift_prem (Abs (s, T, t)) = Abs (s, T, lift_prem t)
   254       | lift_prem t = t;
   255 
   256     fun mk_fresh (x, T) = HOLogic.mk_Trueprop
   257       (NominalPackage.fresh_star_const T fsT $ x $ Bound 0);
   258 
   259     val (prems', prems'') = split_list (map (fn (params, sets, prems, (p, ts)) =>
   260       let
   261         val params' = params @ [("y", fsT)];
   262         val prem = Logic.list_implies
   263           (map mk_fresh sets @
   264            map (fn prem =>
   265              if null (preds_of ps prem) then prem
   266              else lift_prem prem) prems,
   267            HOLogic.mk_Trueprop (lift_pred p ts));
   268       in abs_params params' prem end) prems);
   269 
   270     val ind_vars =
   271       (DatatypeProp.indexify_names (replicate (length atomTs) "pi") ~~
   272        map NominalAtoms.mk_permT atomTs) @ [("z", fsT)];
   273     val ind_Ts = rev (map snd ind_vars);
   274 
   275     val concl = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   276       (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem,
   277         HOLogic.list_all (ind_vars, lift_pred p
   278           (map (fold_rev (NominalPackage.mk_perm ind_Ts)
   279             (map Bound (length atomTs downto 1))) ts)))) concls));
   280 
   281     val concl' = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   282       (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem,
   283         lift_pred' (Free (fs_ctxt_name, fsT)) p ts)) concls));
   284 
   285     val (vc_compat, vc_compat') = map (fn (params, sets, prems, (p, ts)) =>
   286       map (fn q => abs_params params (incr_boundvars ~1 (Logic.list_implies
   287           (List.mapPartial (fn prem =>
   288              if null (preds_of ps prem) then SOME prem
   289              else map_term (split_conj (K o I) names) prem prem) prems, q))))
   290         (maps (fn (t, T) => map (fn (u, U) => HOLogic.mk_Trueprop
   291            (NominalPackage.fresh_star_const U T $ u $ t)) sets)
   292              (ts ~~ binder_types (fastype_of p)) @
   293          map (fn (u, U) => HOLogic.mk_Trueprop (Const (@{const_name finite},
   294            HOLogic.mk_setT U --> HOLogic.boolT) $ u)) sets) |>
   295       split_list) prems |> split_list;
   296 
   297     val perm_pi_simp = PureThy.get_thms thy "perm_pi_simp";
   298     val pt2_atoms = map (fn a => PureThy.get_thm thy
   299       ("pt_" ^ Long_Name.base_name a ^ "2")) atoms;
   300     val eqvt_ss = Simplifier.theory_context thy HOL_basic_ss
   301       addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms)
   302       addsimprocs [mk_perm_bool_simproc ["Fun.id"],
   303         NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun];
   304     val fresh_star_bij = PureThy.get_thms thy "fresh_star_bij";
   305     val pt_insts = map (NominalAtoms.pt_inst_of thy) atoms;
   306     val at_insts = map (NominalAtoms.at_inst_of thy) atoms;
   307     val dj_thms = maps (fn a =>
   308       map (NominalAtoms.dj_thm_of thy a) (atoms \ a)) atoms;
   309     val finite_ineq = map2 (fn th => fn th' => th' RS (th RS
   310       @{thm pt_set_finite_ineq})) pt_insts at_insts;
   311     val perm_set_forget =
   312       map (fn th => th RS @{thm dj_perm_set_forget}) dj_thms;
   313     val perm_freshs_freshs = atomTs ~~ map2 (fn th => fn th' => th' RS (th RS
   314       @{thm pt_freshs_freshs})) pt_insts at_insts;
   315 
   316     fun obtain_fresh_name ts sets (T, fin) (freshs, ths1, ths2, ths3, ctxt) =
   317       let
   318         val thy = ProofContext.theory_of ctxt;
   319         (** protect terms to avoid that fresh_star_prod_set interferes with  **)
   320         (** pairs used in introduction rules of inductive predicate          **)
   321         fun protect t =
   322           let val T = fastype_of t in Const ("Fun.id", T --> T) $ t end;
   323         val p = foldr1 HOLogic.mk_prod (map protect ts);
   324         val atom = fst (dest_Type T);
   325         val {at_inst, ...} = NominalAtoms.the_atom_info thy atom;
   326         val fs_atom = PureThy.get_thm thy
   327           ("fs_" ^ Long_Name.base_name atom ^ "1");
   328         val avoid_th = Drule.instantiate'
   329           [SOME (ctyp_of thy (fastype_of p))] [SOME (cterm_of thy p)]
   330           ([at_inst, fin, fs_atom] MRS @{thm at_set_avoiding});
   331         val (([cx], th1 :: th2 :: ths), ctxt') = Obtain.result
   332           (fn _ => EVERY
   333             [rtac avoid_th 1,
   334              full_simp_tac (HOL_ss addsimps [@{thm fresh_star_prod_set}]) 1,
   335              full_simp_tac (HOL_basic_ss addsimps [@{thm id_apply}]) 1,
   336              rotate_tac 1 1,
   337              REPEAT (etac conjE 1)])
   338           [] ctxt;
   339         val (Ts1, _ :: Ts2) = take_prefix (not o equal T) (map snd sets);
   340         val pTs = map NominalAtoms.mk_permT (Ts1 @ Ts2);
   341         val (pis1, pis2) = chop (length Ts1)
   342           (map Bound (length pTs - 1 downto 0));
   343         val _ $ (f $ (_ $ pi $ l) $ r) = prop_of th2
   344         val th2' =
   345           Goal.prove ctxt [] []
   346             (list_all (map (pair "pi") pTs, HOLogic.mk_Trueprop
   347                (f $ fold_rev (NominalPackage.mk_perm (rev pTs))
   348                   (pis1 @ pi :: pis2) l $ r)))
   349             (fn _ => cut_facts_tac [th2] 1 THEN
   350                full_simp_tac (HOL_basic_ss addsimps perm_set_forget) 1) |>
   351           Simplifier.simplify eqvt_ss
   352       in
   353         (freshs @ [term_of cx],
   354          ths1 @ ths, ths2 @ [th1], ths3 @ [th2'], ctxt')
   355       end;
   356 
   357     fun mk_ind_proof ctxt' thss =
   358       Goal.prove ctxt' [] prems' concl' (fn {prems = ihyps, context = ctxt} =>
   359         let val th = Goal.prove ctxt [] [] concl (fn {context, ...} =>
   360           rtac raw_induct 1 THEN
   361           EVERY (maps (fn (((((_, sets, oprems, _),
   362               vc_compat_ths), vc_compat_vs), ihyp), vs_ihypt) =>
   363             [REPEAT (rtac allI 1), simp_tac eqvt_ss 1,
   364              SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} =>
   365                let
   366                  val (cparams', (pis, z)) =
   367                    chop (length params - length atomTs - 1) params ||>
   368                    (map term_of #> split_last);
   369                  val params' = map term_of cparams'
   370                  val sets' = map (apfst (curry subst_bounds (rev params'))) sets;
   371                  val pi_sets = map (fn (t, _) =>
   372                    fold_rev (NominalPackage.mk_perm []) pis t) sets';
   373                  val (P, ts) = strip_comb (HOLogic.dest_Trueprop (term_of concl));
   374                  val gprems1 = List.mapPartial (fn (th, t) =>
   375                    if null (preds_of ps t) then SOME th
   376                    else
   377                      map_thm ctxt' (split_conj (K o I) names)
   378                        (etac conjunct1 1) monos NONE th)
   379                    (gprems ~~ oprems);
   380                  val vc_compat_ths' = map2 (fn th => fn p =>
   381                    let
   382                      val th' = gprems1 MRS inst_params thy p th cparams';
   383                      val (h, ts) =
   384                        strip_comb (HOLogic.dest_Trueprop (concl_of th'))
   385                    in
   386                      Goal.prove ctxt' [] []
   387                        (HOLogic.mk_Trueprop (list_comb (h,
   388                           map (fold_rev (NominalPackage.mk_perm []) pis) ts)))
   389                        (fn _ => simp_tac (HOL_basic_ss addsimps
   390                           (fresh_star_bij @ finite_ineq)) 1 THEN rtac th' 1)
   391                    end) vc_compat_ths vc_compat_vs;
   392                  val (vc_compat_ths1, vc_compat_ths2) =
   393                    chop (length vc_compat_ths - length sets) vc_compat_ths';
   394                  val vc_compat_ths1' = map
   395                    (Conv.fconv_rule (Conv.arg_conv (Conv.arg_conv
   396                       (Simplifier.rewrite eqvt_ss)))) vc_compat_ths1;
   397                  val (pis', fresh_ths1, fresh_ths2, fresh_ths3, ctxt'') = fold
   398                    (obtain_fresh_name ts sets)
   399                    (map snd sets' ~~ vc_compat_ths2) ([], [], [], [], ctxt');
   400                  fun concat_perm pi1 pi2 =
   401                    let val T = fastype_of pi1
   402                    in if T = fastype_of pi2 then
   403                        Const ("List.append", T --> T --> T) $ pi1 $ pi2
   404                      else pi2
   405                    end;
   406                  val pis'' = fold_rev (concat_perm #> map) pis' pis;
   407                  val ihyp' = inst_params thy vs_ihypt ihyp
   408                    (map (fold_rev (NominalPackage.mk_perm [])
   409                       (pis' @ pis) #> cterm_of thy) params' @ [cterm_of thy z]);
   410                  fun mk_pi th =
   411                    Simplifier.simplify (HOL_basic_ss addsimps [@{thm id_apply}]
   412                        addsimprocs [NominalPackage.perm_simproc])
   413                      (Simplifier.simplify eqvt_ss
   414                        (fold_rev (mk_perm_bool o cterm_of thy)
   415                          (pis' @ pis) th));
   416                  val gprems2 = map (fn (th, t) =>
   417                    if null (preds_of ps t) then mk_pi th
   418                    else
   419                      mk_pi (the (map_thm ctxt (inst_conj_all names ps (rev pis''))
   420                        (inst_conj_all_tac (length pis'')) monos (SOME t) th)))
   421                    (gprems ~~ oprems);
   422                  val perm_freshs_freshs' = map (fn (th, (_, T)) =>
   423                    th RS the (AList.lookup op = perm_freshs_freshs T))
   424                      (fresh_ths2 ~~ sets);
   425                  val th = Goal.prove ctxt'' [] []
   426                    (HOLogic.mk_Trueprop (list_comb (P $ hd ts,
   427                      map (fold_rev (NominalPackage.mk_perm []) pis') (tl ts))))
   428                    (fn _ => EVERY ([simp_tac eqvt_ss 1, rtac ihyp' 1] @
   429                      map (fn th => rtac th 1) fresh_ths3 @
   430                      [REPEAT_DETERM_N (length gprems)
   431                        (simp_tac (HOL_basic_ss
   432                           addsimps [inductive_forall_def']
   433                           addsimprocs [NominalPackage.perm_simproc]) 1 THEN
   434                         resolve_tac gprems2 1)]));
   435                  val final = Goal.prove ctxt'' [] [] (term_of concl)
   436                    (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (HOL_ss
   437                      addsimps vc_compat_ths1' @ fresh_ths1 @
   438                        perm_freshs_freshs') 1);
   439                  val final' = ProofContext.export ctxt'' ctxt' [final];
   440                in resolve_tac final' 1 end) context 1])
   441                  (prems ~~ thss ~~ vc_compat' ~~ ihyps ~~ prems'')))
   442         in
   443           cut_facts_tac [th] 1 THEN REPEAT (etac conjE 1) THEN
   444           REPEAT (REPEAT (resolve_tac [conjI, impI] 1) THEN
   445             etac impE 1 THEN atac 1 THEN REPEAT (etac @{thm allE_Nil} 1) THEN
   446             asm_full_simp_tac (simpset_of thy) 1)
   447         end) |>
   448         fresh_postprocess |>
   449         singleton (ProofContext.export ctxt' ctxt);
   450 
   451   in
   452     ctxt'' |>
   453     Proof.theorem_i NONE (fn thss => fn ctxt =>
   454       let
   455         val rec_name = space_implode "_" (map Long_Name.base_name names);
   456         val rec_qualified = Binding.qualify false rec_name;
   457         val ind_case_names = RuleCases.case_names induct_cases;
   458         val induct_cases' = InductivePackage.partition_rules' raw_induct
   459           (intrs ~~ induct_cases); 
   460         val thss' = map (map atomize_intr) thss;
   461         val thsss = InductivePackage.partition_rules' raw_induct (intrs ~~ thss');
   462         val strong_raw_induct =
   463           mk_ind_proof ctxt thss' |> InductivePackage.rulify;
   464         val strong_induct =
   465           if length names > 1 then
   466             (strong_raw_induct, [ind_case_names, RuleCases.consumes 0])
   467           else (strong_raw_induct RSN (2, rev_mp),
   468             [ind_case_names, RuleCases.consumes 1]);
   469         val ((_, [strong_induct']), ctxt') = LocalTheory.note Thm.theoremK
   470           ((rec_qualified (Binding.name "strong_induct"),
   471             map (Attrib.internal o K) (#2 strong_induct)), [#1 strong_induct])
   472           ctxt;
   473         val strong_inducts =
   474           ProjectRule.projects ctxt' (1 upto length names) strong_induct'
   475       in
   476         ctxt' |>
   477         LocalTheory.note Thm.theoremK
   478           ((rec_qualified (Binding.name "strong_inducts"),
   479             [Attrib.internal (K ind_case_names),
   480              Attrib.internal (K (RuleCases.consumes 1))]),
   481            strong_inducts) |> snd
   482       end)
   483       (map (map (rulify_term thy #> rpair [])) vc_compat)
   484   end;
   485 
   486 
   487 (* outer syntax *)
   488 
   489 local structure P = OuterParse and K = OuterKeyword in
   490 
   491 val _ =
   492   OuterSyntax.local_theory_to_proof "nominal_inductive2"
   493     "prove strong induction theorem for inductive predicate involving nominal datatypes" K.thy_goal
   494     (P.xname -- Scan.optional (P.$$$ "avoids" |-- P.enum1 "|" (P.name --
   495       (P.$$$ ":" |-- P.and_list1 P.term))) [] >> (fn (name, avoids) =>
   496         prove_strong_ind name avoids));
   497 
   498 end;
   499 
   500 end