More general, still experimental version of nominal_inductive for
authorberghofe
Tue Oct 21 21:20:17 2008 +0200 (2008-10-21)
changeset 286534593c70e228e
parent 28652 659d64d59f16
child 28654 2f9857126498
More general, still experimental version of nominal_inductive for
avoiding sets of names.
src/HOL/Nominal/nominal_inductive2.ML
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/HOL/Nominal/nominal_inductive2.ML	Tue Oct 21 21:20:17 2008 +0200
     1.3 @@ -0,0 +1,487 @@
     1.4 +(*  Title:      HOL/Nominal/nominal_inductive2.ML
     1.5 +    ID:         $Id$
     1.6 +    Author:     Stefan Berghofer, TU Muenchen
     1.7 +
     1.8 +Infrastructure for proving equivariance and strong induction theorems
     1.9 +for inductive predicates involving nominal datatypes.
    1.10 +Experimental version that allows to avoid lists of atoms.
    1.11 +*)
    1.12 +
    1.13 +signature NOMINAL_INDUCTIVE2 =
    1.14 +sig
    1.15 +  val prove_strong_ind: string -> (string * string list) list -> theory -> Proof.state
    1.16 +end
    1.17 +
    1.18 +structure NominalInductive2 : NOMINAL_INDUCTIVE2 =
    1.19 +struct
    1.20 +
    1.21 +val inductive_forall_name = "HOL.induct_forall";
    1.22 +val inductive_forall_def = thm "induct_forall_def";
    1.23 +val inductive_atomize = thms "induct_atomize";
    1.24 +val inductive_rulify = thms "induct_rulify";
    1.25 +
    1.26 +fun rulify_term thy = MetaSimplifier.rewrite_term thy inductive_rulify [];
    1.27 +
    1.28 +val atomize_conv =
    1.29 +  MetaSimplifier.rewrite_cterm (true, false, false) (K (K NONE))
    1.30 +    (HOL_basic_ss addsimps inductive_atomize);
    1.31 +val atomize_intr = Conv.fconv_rule (Conv.prems_conv ~1 atomize_conv);
    1.32 +fun atomize_induct ctxt = Conv.fconv_rule (Conv.prems_conv ~1
    1.33 +  (Conv.params_conv ~1 (K (Conv.prems_conv ~1 atomize_conv)) ctxt));
    1.34 +
    1.35 +val perm_bool = mk_meta_eq (thm "perm_bool");
    1.36 +val perm_boolI = thm "perm_boolI";
    1.37 +val (_, [perm_boolI_pi, _]) = Drule.strip_comb (snd (Thm.dest_comb
    1.38 +  (Drule.strip_imp_concl (cprop_of perm_boolI))));
    1.39 +
    1.40 +fun mk_perm_bool pi th = th RS Drule.cterm_instantiate
    1.41 +  [(perm_boolI_pi, pi)] perm_boolI;
    1.42 +
    1.43 +fun mk_perm_bool_simproc names = Simplifier.simproc_i
    1.44 +  (theory_of_thm perm_bool) "perm_bool" [@{term "perm pi x"}] (fn thy => fn ss =>
    1.45 +    fn Const ("Nominal.perm", _) $ _ $ t =>
    1.46 +         if the_default "" (try (head_of #> dest_Const #> fst) t) mem names
    1.47 +         then SOME perm_bool else NONE
    1.48 +     | _ => NONE);
    1.49 +
    1.50 +fun transp ([] :: _) = []
    1.51 +  | transp xs = map hd xs :: transp (map tl xs);
    1.52 +
    1.53 +fun add_binders thy i (t as (_ $ _)) bs = (case strip_comb t of
    1.54 +      (Const (s, T), ts) => (case strip_type T of
    1.55 +        (Ts, Type (tname, _)) =>
    1.56 +          (case NominalPackage.get_nominal_datatype thy tname of
    1.57 +             NONE => fold (add_binders thy i) ts bs
    1.58 +           | SOME {descr, index, ...} => (case AList.lookup op =
    1.59 +                 (#3 (the (AList.lookup op = descr index))) s of
    1.60 +               NONE => fold (add_binders thy i) ts bs
    1.61 +             | SOME cargs => fst (fold (fn (xs, x) => fn (bs', cargs') =>
    1.62 +                 let val (cargs1, (u, _) :: cargs2) = chop (length xs) cargs'
    1.63 +                 in (add_binders thy i u
    1.64 +                   (fold (fn (u, T) =>
    1.65 +                      if exists (fn j => j < i) (loose_bnos u) then I
    1.66 +                      else AList.map_default op = (T, [])
    1.67 +                        (insert op aconv (incr_boundvars (~i) u)))
    1.68 +                          cargs1 bs'), cargs2)
    1.69 +                 end) cargs (bs, ts ~~ Ts))))
    1.70 +      | _ => fold (add_binders thy i) ts bs)
    1.71 +    | (u, ts) => add_binders thy i u (fold (add_binders thy i) ts bs))
    1.72 +  | add_binders thy i (Abs (_, _, t)) bs = add_binders thy (i + 1) t bs
    1.73 +  | add_binders thy i _ bs = bs;
    1.74 +
    1.75 +fun mk_set T [] = Const ("{}", HOLogic.mk_setT T)
    1.76 +  | mk_set T (x :: xs) =
    1.77 +      Const ("insert", T --> HOLogic.mk_setT T --> HOLogic.mk_setT T) $ x $
    1.78 +        mk_set T xs;
    1.79 +
    1.80 +fun split_conj f names (Const ("op &", _) $ p $ q) _ = (case head_of p of
    1.81 +      Const (name, _) =>
    1.82 +        if name mem names then SOME (f p q) else NONE
    1.83 +    | _ => NONE)
    1.84 +  | split_conj _ _ _ _ = NONE;
    1.85 +
    1.86 +fun strip_all [] t = t
    1.87 +  | strip_all (_ :: xs) (Const ("All", _) $ Abs (s, T, t)) = strip_all xs t;
    1.88 +
    1.89 +(*********************************************************************)
    1.90 +(* maps  R ... & (ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t))  *)
    1.91 +(* or    ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t)            *)
    1.92 +(* to    R ... & id (ALL z. P z (pi_1 o ... o pi_n o t))             *)
    1.93 +(* or    id (ALL z. P z (pi_1 o ... o pi_n o t))                     *)
    1.94 +(*                                                                   *)
    1.95 +(* where "id" protects the subformula from simplification            *)
    1.96 +(*********************************************************************)
    1.97 +
    1.98 +fun inst_conj_all names ps pis (Const ("op &", _) $ p $ q) _ =
    1.99 +      (case head_of p of
   1.100 +         Const (name, _) =>
   1.101 +           if name mem names then SOME (HOLogic.mk_conj (p,
   1.102 +             Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
   1.103 +               (subst_bounds (pis, strip_all pis q))))
   1.104 +           else NONE
   1.105 +       | _ => NONE)
   1.106 +  | inst_conj_all names ps pis t u =
   1.107 +      if member (op aconv) ps (head_of u) then
   1.108 +        SOME (Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
   1.109 +          (subst_bounds (pis, strip_all pis t)))
   1.110 +      else NONE
   1.111 +  | inst_conj_all _ _ _ _ _ = NONE;
   1.112 +
   1.113 +fun inst_conj_all_tac k = EVERY
   1.114 +  [TRY (EVERY [etac conjE 1, rtac conjI 1, atac 1]),
   1.115 +   REPEAT_DETERM_N k (etac allE 1),
   1.116 +   simp_tac (HOL_basic_ss addsimps [@{thm id_apply}]) 1];
   1.117 +
   1.118 +fun map_term f t u = (case f t u of
   1.119 +      NONE => map_term' f t u | x => x)
   1.120 +and map_term' f (t $ u) (t' $ u') = (case (map_term f t t', map_term f u u') of
   1.121 +      (NONE, NONE) => NONE
   1.122 +    | (SOME t'', NONE) => SOME (t'' $ u)
   1.123 +    | (NONE, SOME u'') => SOME (t $ u'')
   1.124 +    | (SOME t'', SOME u'') => SOME (t'' $ u''))
   1.125 +  | map_term' f (Abs (s, T, t)) (Abs (s', T', t')) = (case map_term f t t' of
   1.126 +      NONE => NONE
   1.127 +    | SOME t'' => SOME (Abs (s, T, t'')))
   1.128 +  | map_term' _ _ _ = NONE;
   1.129 +
   1.130 +(*********************************************************************)
   1.131 +(*         Prove  F[f t]  from  F[t],  where F is monotone           *)
   1.132 +(*********************************************************************)
   1.133 +
   1.134 +fun map_thm ctxt f tac monos opt th =
   1.135 +  let
   1.136 +    val prop = prop_of th;
   1.137 +    fun prove t =
   1.138 +      Goal.prove ctxt [] [] t (fn _ =>
   1.139 +        EVERY [cut_facts_tac [th] 1, etac rev_mp 1,
   1.140 +          REPEAT_DETERM (FIRSTGOAL (resolve_tac monos)),
   1.141 +          REPEAT_DETERM (rtac impI 1 THEN (atac 1 ORELSE tac))])
   1.142 +  in Option.map prove (map_term f prop (the_default prop opt)) end;
   1.143 +
   1.144 +fun abs_params params t =
   1.145 +  let val vs =  map (Var o apfst (rpair 0)) (rename_wrt_term t params)
   1.146 +  in (list_all (params, t), (rev vs, subst_bounds (vs, t))) end;
   1.147 +
   1.148 +fun inst_params thy (vs, p) th cts =
   1.149 +  let val env = Pattern.first_order_match thy (p, prop_of th)
   1.150 +    (Vartab.empty, Vartab.empty)
   1.151 +  in Thm.instantiate ([],
   1.152 +    map (Envir.subst_vars env #> cterm_of thy) vs ~~ cts) th
   1.153 +  end;
   1.154 +
   1.155 +fun prove_strong_ind s avoids thy =
   1.156 +  let
   1.157 +    val ctxt = ProofContext.init thy;
   1.158 +    val ({names, ...}, {raw_induct, intrs, elims, ...}) =
   1.159 +      InductivePackage.the_inductive ctxt (Sign.intern_const thy s);
   1.160 +    val ind_params = InductivePackage.params_of raw_induct;
   1.161 +    val raw_induct = atomize_induct ctxt raw_induct;
   1.162 +    val elims = map (atomize_induct ctxt) elims;
   1.163 +    val monos = InductivePackage.get_monos ctxt;
   1.164 +    val eqvt_thms = NominalThmDecls.get_eqvt_thms ctxt;
   1.165 +    val _ = (case names \\ foldl (apfst prop_of #> add_term_consts) [] eqvt_thms of
   1.166 +        [] => ()
   1.167 +      | xs => error ("Missing equivariance theorem for predicate(s): " ^
   1.168 +          commas_quote xs));
   1.169 +    val induct_cases = map fst (fst (RuleCases.get (the
   1.170 +      (Induct.lookup_inductP ctxt (hd names)))));
   1.171 +    val induct_cases' = if null induct_cases then replicate (length intrs) ""
   1.172 +      else induct_cases;
   1.173 +    val raw_induct' = Logic.unvarify (prop_of raw_induct);
   1.174 +    val elims' = map (Logic.unvarify o prop_of) elims;
   1.175 +    val concls = raw_induct' |> Logic.strip_imp_concl |> HOLogic.dest_Trueprop |>
   1.176 +      HOLogic.dest_conj |> map (HOLogic.dest_imp ##> strip_comb);
   1.177 +    val ps = map (fst o snd) concls;
   1.178 +
   1.179 +    val _ = (case duplicates (op = o pairself fst) avoids of
   1.180 +        [] => ()
   1.181 +      | xs => error ("Duplicate case names: " ^ commas_quote (map fst xs)));
   1.182 +    val _ = (case map fst avoids \\ induct_cases of
   1.183 +        [] => ()
   1.184 +      | xs => error ("No such case(s) in inductive definition: " ^ commas_quote xs));
   1.185 +    fun mk_avoids params name sets =
   1.186 +      let
   1.187 +        val (_, ctxt') = ProofContext.add_fixes_i
   1.188 +          (map (fn (s, T) => (Name.binding s, SOME T, NoSyn)) params) ctxt;
   1.189 +        fun mk s =
   1.190 +          let
   1.191 +            val t = Syntax.read_term ctxt' s;
   1.192 +            val t' = list_abs_free (params, t) |>
   1.193 +              funpow (length params) (fn Abs (_, _, t) => t)
   1.194 +          in (t', HOLogic.dest_setT (fastype_of t)) end
   1.195 +          handle TERM _ =>
   1.196 +            error ("Expression " ^ quote s ^ " to be avoided in case " ^
   1.197 +              quote name ^ " is not a set type");
   1.198 +        val ps = map mk sets
   1.199 +      in
   1.200 +        case duplicates op = (map snd ps) of
   1.201 +          [] => ps
   1.202 +        | Ts => error ("More than one set in case " ^ quote name ^
   1.203 +            " for type(s) " ^ commas_quote (map (Syntax.string_of_typ ctxt') Ts))
   1.204 +      end;
   1.205 +
   1.206 +    val prems = map (fn (prem, name) =>
   1.207 +      let
   1.208 +        val prems = map (incr_boundvars 1) (Logic.strip_assums_hyp prem);
   1.209 +        val concl = incr_boundvars 1 (Logic.strip_assums_concl prem);
   1.210 +        val params = Logic.strip_params prem
   1.211 +      in
   1.212 +        (params,
   1.213 +         if null avoids then
   1.214 +           map (fn (T, ts) => (mk_set T ts, T))
   1.215 +             (fold (add_binders thy 0) (prems @ [concl]) [])
   1.216 +         else case AList.lookup op = avoids name of
   1.217 +           NONE => []
   1.218 +         | SOME sets =>
   1.219 +             map (apfst (incr_boundvars 1)) (mk_avoids params name sets),
   1.220 +         prems, strip_comb (HOLogic.dest_Trueprop concl))
   1.221 +      end) (Logic.strip_imp_prems raw_induct' ~~ induct_cases');
   1.222 +
   1.223 +    val atomTs = distinct op = (maps (map snd o #2) prems);
   1.224 +    val atoms = map (fst o dest_Type) atomTs;
   1.225 +    val ind_sort = if null atomTs then HOLogic.typeS
   1.226 +      else Sign.certify_sort thy (map (fn a => Sign.intern_class thy
   1.227 +        ("fs_" ^ Sign.base_name a)) atoms);
   1.228 +    val fs_ctxt_tyname = Name.variant (map fst (term_tfrees raw_induct')) "'n";
   1.229 +    val fs_ctxt_name = Name.variant (add_term_names (raw_induct', [])) "z";
   1.230 +    val fsT = TFree (fs_ctxt_tyname, ind_sort);
   1.231 +
   1.232 +    val inductive_forall_def' = Drule.instantiate'
   1.233 +      [SOME (ctyp_of thy fsT)] [] inductive_forall_def;
   1.234 +
   1.235 +    fun lift_pred' t (Free (s, T)) ts =
   1.236 +      list_comb (Free (s, fsT --> T), t :: ts);
   1.237 +    val lift_pred = lift_pred' (Bound 0);
   1.238 +
   1.239 +    fun lift_prem (t as (f $ u)) =
   1.240 +          let val (p, ts) = strip_comb t
   1.241 +          in
   1.242 +            if p mem ps then
   1.243 +              Const (inductive_forall_name,
   1.244 +                (fsT --> HOLogic.boolT) --> HOLogic.boolT) $
   1.245 +                  Abs ("z", fsT, lift_pred p (map (incr_boundvars 1) ts))
   1.246 +            else lift_prem f $ lift_prem u
   1.247 +          end
   1.248 +      | lift_prem (Abs (s, T, t)) = Abs (s, T, lift_prem t)
   1.249 +      | lift_prem t = t;
   1.250 +
   1.251 +    fun mk_fresh (x, T) = HOLogic.mk_Trueprop
   1.252 +      (NominalPackage.fresh_star_const T fsT $ x $ Bound 0);
   1.253 +
   1.254 +    val (prems', prems'') = split_list (map (fn (params, sets, prems, (p, ts)) =>
   1.255 +      let
   1.256 +        val params' = params @ [("y", fsT)];
   1.257 +        val prem = Logic.list_implies
   1.258 +          (map mk_fresh sets @
   1.259 +           map (fn prem =>
   1.260 +             if null (term_frees prem inter ps) then prem
   1.261 +             else lift_prem prem) prems,
   1.262 +           HOLogic.mk_Trueprop (lift_pred p ts));
   1.263 +      in abs_params params' prem end) prems);
   1.264 +
   1.265 +    val ind_vars =
   1.266 +      (DatatypeProp.indexify_names (replicate (length atomTs) "pi") ~~
   1.267 +       map NominalAtoms.mk_permT atomTs) @ [("z", fsT)];
   1.268 +    val ind_Ts = rev (map snd ind_vars);
   1.269 +
   1.270 +    val concl = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   1.271 +      (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem,
   1.272 +        HOLogic.list_all (ind_vars, lift_pred p
   1.273 +          (map (fold_rev (NominalPackage.mk_perm ind_Ts)
   1.274 +            (map Bound (length atomTs downto 1))) ts)))) concls));
   1.275 +
   1.276 +    val concl' = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   1.277 +      (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem,
   1.278 +        lift_pred' (Free (fs_ctxt_name, fsT)) p ts)) concls));
   1.279 +
   1.280 +    val (vc_compat, vc_compat') = map (fn (params, sets, prems, (p, ts)) =>
   1.281 +      map (fn q => abs_params params (incr_boundvars ~1 (Logic.list_implies
   1.282 +          (List.mapPartial (fn prem =>
   1.283 +             if null (ps inter term_frees prem) then SOME prem
   1.284 +             else map_term (split_conj (K o I) names) prem prem) prems, q))))
   1.285 +        (maps (fn (t, T) => map (fn (u, U) => HOLogic.mk_Trueprop
   1.286 +           (NominalPackage.fresh_star_const U T $ u $ t)) sets)
   1.287 +             (ts ~~ binder_types (fastype_of p)) @
   1.288 +         map (fn (u, U) => HOLogic.mk_Trueprop (Const (@{const_name finite},
   1.289 +           HOLogic.mk_setT U --> HOLogic.boolT) $ u)) sets) |>
   1.290 +      split_list) prems |> split_list;
   1.291 +
   1.292 +    val perm_pi_simp = PureThy.get_thms thy "perm_pi_simp";
   1.293 +    val pt2_atoms = map (fn a => PureThy.get_thm thy
   1.294 +      ("pt_" ^ Sign.base_name a ^ "2")) atoms;
   1.295 +    val eqvt_ss = Simplifier.theory_context thy HOL_basic_ss
   1.296 +      addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms)
   1.297 +      addsimprocs [mk_perm_bool_simproc ["Fun.id"],
   1.298 +        NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun];
   1.299 +    val fresh_star_bij = PureThy.get_thms thy "fresh_star_bij";
   1.300 +    val pt_insts = map (NominalAtoms.the_atom_info thy #> #pt_inst) atoms;
   1.301 +    val at_insts = map (NominalAtoms.the_atom_info thy #> #at_inst) atoms;
   1.302 +    val dj_thms = maps (NominalAtoms.the_atom_info thy #> #dj_thms) atoms;
   1.303 +    val finite_ineq = map2 (fn th => fn th' => th' RS (th RS
   1.304 +      @{thm pt_set_finite_ineq})) pt_insts at_insts;
   1.305 +    val perm_set_forget =
   1.306 +      map (fn th => th RS @{thm dj_perm_set_forget}) dj_thms;
   1.307 +    val perm_freshs_freshs = atomTs ~~ map2 (fn th => fn th' => th' RS (th RS
   1.308 +      @{thm pt_freshs_freshs})) pt_insts at_insts;
   1.309 +
   1.310 +    fun obtain_fresh_name ts sets (T, fin) (freshs, ths1, ths2, ths3, ctxt) =
   1.311 +      let
   1.312 +        val thy = ProofContext.theory_of ctxt;
   1.313 +        (** protect terms to avoid that fresh_star_prod_set interferes with  **)
   1.314 +        (** pairs used in introduction rules of inductive predicate          **)
   1.315 +        fun protect t =
   1.316 +          let val T = fastype_of t in Const ("Fun.id", T --> T) $ t end;
   1.317 +        val p = foldr1 HOLogic.mk_prod (map protect ts);
   1.318 +        val atom = fst (dest_Type T);
   1.319 +        val {at_inst, ...} = NominalAtoms.the_atom_info thy atom;
   1.320 +        val fs_atom = PureThy.get_thm thy
   1.321 +          ("fs_" ^ Sign.base_name atom ^ "1");
   1.322 +        val avoid_th = Drule.instantiate'
   1.323 +          [SOME (ctyp_of thy (fastype_of p))] [SOME (cterm_of thy p)]
   1.324 +          ([at_inst, fin, fs_atom] MRS @{thm at_set_avoiding});
   1.325 +        val (([cx], th1 :: th2 :: ths), ctxt') = Obtain.result
   1.326 +          (fn _ => EVERY
   1.327 +            [rtac avoid_th 1,
   1.328 +             full_simp_tac (HOL_ss addsimps [@{thm fresh_star_prod_set}]) 1,
   1.329 +             full_simp_tac (HOL_basic_ss addsimps [@{thm id_apply}]) 1,
   1.330 +             rotate_tac 1 1,
   1.331 +             REPEAT (etac conjE 1)])
   1.332 +          [] ctxt;
   1.333 +        val (Ts1, _ :: Ts2) = take_prefix (not o equal T) (map snd sets);
   1.334 +        val pTs = map NominalAtoms.mk_permT (Ts1 @ Ts2);
   1.335 +        val (pis1, pis2) = chop (length Ts1)
   1.336 +          (map Bound (length pTs - 1 downto 0));
   1.337 +        val _ $ (f $ (_ $ pi $ l) $ r) = prop_of th2
   1.338 +        val th2' =
   1.339 +          Goal.prove ctxt [] []
   1.340 +            (list_all (map (pair "pi") pTs, HOLogic.mk_Trueprop
   1.341 +               (f $ fold_rev (NominalPackage.mk_perm (rev pTs))
   1.342 +                  (pis1 @ pi :: pis2) l $ r)))
   1.343 +            (fn _ => cut_facts_tac [th2] 1 THEN
   1.344 +               full_simp_tac (HOL_basic_ss addsimps perm_set_forget) 1) |>
   1.345 +          Simplifier.simplify eqvt_ss
   1.346 +      in
   1.347 +        (freshs @ [term_of cx],
   1.348 +         ths1 @ ths, ths2 @ [th1], ths3 @ [th2'], ctxt')
   1.349 +      end;
   1.350 +
   1.351 +    fun mk_ind_proof thy thss =
   1.352 +      Goal.prove_global thy [] prems' concl' (fn {prems = ihyps, context = ctxt} =>
   1.353 +        let val th = Goal.prove ctxt [] [] concl (fn {context, ...} =>
   1.354 +          rtac raw_induct 1 THEN
   1.355 +          EVERY (maps (fn (((((_, sets, oprems, _),
   1.356 +              vc_compat_ths), vc_compat_vs), ihyp), vs_ihypt) =>
   1.357 +            [REPEAT (rtac allI 1), simp_tac eqvt_ss 1,
   1.358 +             SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} =>
   1.359 +               let
   1.360 +                 val (cparams', (pis, z)) =
   1.361 +                   chop (length params - length atomTs - 1) params ||>
   1.362 +                   (map term_of #> split_last);
   1.363 +                 val params' = map term_of cparams'
   1.364 +                 val sets' = map (apfst (curry subst_bounds (rev params'))) sets;
   1.365 +                 val pi_sets = map (fn (t, _) =>
   1.366 +                   fold_rev (NominalPackage.mk_perm []) pis t) sets';
   1.367 +                 val (P, ts) = strip_comb (HOLogic.dest_Trueprop (term_of concl));
   1.368 +                 val gprems1 = List.mapPartial (fn (th, t) =>
   1.369 +                   if null (term_frees t inter ps) then SOME th
   1.370 +                   else
   1.371 +                     map_thm ctxt' (split_conj (K o I) names)
   1.372 +                       (etac conjunct1 1) monos NONE th)
   1.373 +                   (gprems ~~ oprems);
   1.374 +                 val vc_compat_ths' = map2 (fn th => fn p =>
   1.375 +                   let
   1.376 +                     val th' = gprems1 MRS inst_params thy p th cparams';
   1.377 +                     val (h, ts) =
   1.378 +                       strip_comb (HOLogic.dest_Trueprop (concl_of th'))
   1.379 +                   in
   1.380 +                     Goal.prove ctxt' [] []
   1.381 +                       (HOLogic.mk_Trueprop (list_comb (h,
   1.382 +                          map (fold_rev (NominalPackage.mk_perm []) pis) ts)))
   1.383 +                       (fn _ => simp_tac (HOL_basic_ss addsimps
   1.384 +                          (fresh_star_bij @ finite_ineq)) 1 THEN rtac th' 1)
   1.385 +                   end) vc_compat_ths vc_compat_vs;
   1.386 +                 val (vc_compat_ths1, vc_compat_ths2) =
   1.387 +                   chop (length vc_compat_ths - length sets) vc_compat_ths';
   1.388 +                 val vc_compat_ths1' = map
   1.389 +                   (Conv.fconv_rule (Conv.arg_conv (Conv.arg_conv
   1.390 +                      (Simplifier.rewrite eqvt_ss)))) vc_compat_ths1;
   1.391 +                 val (pis', fresh_ths1, fresh_ths2, fresh_ths3, ctxt'') = fold
   1.392 +                   (obtain_fresh_name ts sets)
   1.393 +                   (map snd sets' ~~ vc_compat_ths2) ([], [], [], [], ctxt');
   1.394 +                 fun concat_perm pi1 pi2 =
   1.395 +                   let val T = fastype_of pi1
   1.396 +                   in if T = fastype_of pi2 then
   1.397 +                       Const ("List.append", T --> T --> T) $ pi1 $ pi2
   1.398 +                     else pi2
   1.399 +                   end;
   1.400 +                 val pis'' = fold_rev (concat_perm #> map) pis' pis;
   1.401 +                 val ihyp' = inst_params thy vs_ihypt ihyp
   1.402 +                   (map (fold_rev (NominalPackage.mk_perm [])
   1.403 +                      (pis' @ pis) #> cterm_of thy) params' @ [cterm_of thy z]);
   1.404 +                 fun mk_pi th =
   1.405 +                   Simplifier.simplify (HOL_basic_ss addsimps [@{thm id_apply}]
   1.406 +                       addsimprocs [NominalPackage.perm_simproc])
   1.407 +                     (Simplifier.simplify eqvt_ss
   1.408 +                       (fold_rev (mk_perm_bool o cterm_of thy)
   1.409 +                         (pis' @ pis) th));
   1.410 +                 val gprems2 = map (fn (th, t) =>
   1.411 +                   if null (term_frees t inter ps) then mk_pi th
   1.412 +                   else
   1.413 +                     mk_pi (the (map_thm ctxt (inst_conj_all names ps (rev pis''))
   1.414 +                       (inst_conj_all_tac (length pis'')) monos (SOME t) th)))
   1.415 +                   (gprems ~~ oprems);
   1.416 +                 val perm_freshs_freshs' = map (fn (th, (_, T)) =>
   1.417 +                   th RS the (AList.lookup op = perm_freshs_freshs T))
   1.418 +                     (fresh_ths2 ~~ sets);
   1.419 +                 val th = Goal.prove ctxt'' [] []
   1.420 +                   (HOLogic.mk_Trueprop (list_comb (P $ hd ts,
   1.421 +                     map (fold_rev (NominalPackage.mk_perm []) pis') (tl ts))))
   1.422 +                   (fn _ => EVERY ([simp_tac eqvt_ss 1, rtac ihyp' 1] @
   1.423 +                     map (fn th => rtac th 1) fresh_ths3 @
   1.424 +                     [REPEAT_DETERM_N (length gprems)
   1.425 +                       (simp_tac (HOL_basic_ss
   1.426 +                          addsimps [inductive_forall_def']
   1.427 +                          addsimprocs [NominalPackage.perm_simproc]) 1 THEN
   1.428 +                        resolve_tac gprems2 1)]));
   1.429 +                 val final = Goal.prove ctxt'' [] [] (term_of concl)
   1.430 +                   (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (HOL_ss
   1.431 +                     addsimps vc_compat_ths1' @ fresh_ths1 @
   1.432 +                       perm_freshs_freshs') 1);
   1.433 +                 val final' = ProofContext.export ctxt'' ctxt' [final];
   1.434 +               in resolve_tac final' 1 end) context 1])
   1.435 +                 (prems ~~ thss ~~ vc_compat' ~~ ihyps ~~ prems'')))
   1.436 +        in
   1.437 +          cut_facts_tac [th] 1 THEN REPEAT (etac conjE 1) THEN
   1.438 +          REPEAT (REPEAT (resolve_tac [conjI, impI] 1) THEN
   1.439 +            etac impE 1 THEN atac 1 THEN REPEAT (etac @{thm allE_Nil} 1) THEN
   1.440 +            asm_full_simp_tac (simpset_of thy) 1)
   1.441 +        end);
   1.442 +
   1.443 +  in
   1.444 +    thy |>
   1.445 +    ProofContext.init |>
   1.446 +    Proof.theorem_i NONE (fn thss => ProofContext.theory (fn thy =>
   1.447 +      let
   1.448 +        val ctxt = ProofContext.init thy;
   1.449 +        val rec_name = space_implode "_" (map Sign.base_name names);
   1.450 +        val ind_case_names = RuleCases.case_names induct_cases;
   1.451 +        val induct_cases' = InductivePackage.partition_rules' raw_induct
   1.452 +          (intrs ~~ induct_cases); 
   1.453 +        val thss' = map (map atomize_intr) thss;
   1.454 +        val thsss = InductivePackage.partition_rules' raw_induct (intrs ~~ thss');
   1.455 +        val strong_raw_induct =
   1.456 +          mk_ind_proof thy thss' |> InductivePackage.rulify;
   1.457 +        val strong_induct =
   1.458 +          if length names > 1 then
   1.459 +            (strong_raw_induct, [ind_case_names, RuleCases.consumes 0])
   1.460 +          else (strong_raw_induct RSN (2, rev_mp),
   1.461 +            [ind_case_names, RuleCases.consumes 1]);
   1.462 +        val ([strong_induct'], thy') = thy |>
   1.463 +          Sign.add_path rec_name |>
   1.464 +          PureThy.add_thms [(("strong_induct", #1 strong_induct), #2 strong_induct)];
   1.465 +        val strong_inducts =
   1.466 +          ProjectRule.projects ctxt (1 upto length names) strong_induct'
   1.467 +      in
   1.468 +        thy' |>
   1.469 +        PureThy.add_thmss [(("strong_inducts", strong_inducts),
   1.470 +          [ind_case_names, RuleCases.consumes 1])] |> snd |>
   1.471 +        Sign.parent_path
   1.472 +      end))
   1.473 +      (map (map (rulify_term thy #> rpair [])) vc_compat)
   1.474 +  end;
   1.475 +
   1.476 +
   1.477 +(* outer syntax *)
   1.478 +
   1.479 +local structure P = OuterParse and K = OuterKeyword in
   1.480 +
   1.481 +val _ =
   1.482 +  OuterSyntax.command "nominal_inductive2"
   1.483 +    "prove strong induction theorem for inductive predicate involving nominal datatypes" K.thy_goal
   1.484 +    (P.name -- Scan.optional (P.$$$ "avoids" |-- P.enum1 "|" (P.name --
   1.485 +      (P.$$$ ":" |-- P.and_list1 P.term))) [] >> (fn (name, avoids) =>
   1.486 +        Toplevel.print o Toplevel.theory_to_proof (prove_strong_ind name avoids)));
   1.487 +
   1.488 +end;
   1.489 +
   1.490 +end