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