src/HOL/Nominal/nominal_inductive.ML
author wenzelm
Wed Jun 25 17:38:32 2008 +0200 (2008-06-25)
changeset 27353 71c4dd53d4cb
parent 27352 8adeff7fd4bc
child 27449 4880da911af0
permissions -rw-r--r--
moved global keywords from OuterSyntax to OuterKeyword, tuned interfaces;
     1 (*  Title:      HOL/Nominal/nominal_inductive.ML
     2     ID:         $Id$
     3     Author:     Stefan Berghofer, TU Muenchen
     4 
     5 Infrastructure for proving equivariance and strong induction theorems
     6 for inductive predicates involving nominal datatypes.
     7 *)
     8 
     9 signature NOMINAL_INDUCTIVE =
    10 sig
    11   val prove_strong_ind: string -> (string * string list) list -> theory -> Proof.state
    12   val prove_eqvt: string -> string list -> theory -> theory
    13 end
    14 
    15 structure NominalInductive : NOMINAL_INDUCTIVE =
    16 struct
    17 
    18 val inductive_forall_name = "HOL.induct_forall";
    19 val inductive_forall_def = thm "induct_forall_def";
    20 val inductive_atomize = thms "induct_atomize";
    21 val inductive_rulify = thms "induct_rulify";
    22 
    23 fun rulify_term thy = MetaSimplifier.rewrite_term thy inductive_rulify [];
    24 
    25 val atomize_conv =
    26   MetaSimplifier.rewrite_cterm (true, false, false) (K (K NONE))
    27     (HOL_basic_ss addsimps inductive_atomize);
    28 val atomize_intr = Conv.fconv_rule (Conv.prems_conv ~1 atomize_conv);
    29 fun atomize_induct ctxt = Conv.fconv_rule (Conv.prems_conv ~1
    30   (Conv.params_conv ~1 (K (Conv.prems_conv ~1 atomize_conv)) ctxt));
    31 
    32 val finite_Un = thm "finite_Un";
    33 val supp_prod = thm "supp_prod";
    34 val fresh_prod = thm "fresh_prod";
    35 
    36 val perm_bool = mk_meta_eq (thm "perm_bool");
    37 val perm_boolI = thm "perm_boolI";
    38 val (_, [perm_boolI_pi, _]) = Drule.strip_comb (snd (Thm.dest_comb
    39   (Drule.strip_imp_concl (cprop_of perm_boolI))));
    40 
    41 fun mk_perm_bool pi th = th RS Drule.cterm_instantiate
    42   [(perm_boolI_pi, pi)] perm_boolI;
    43 
    44 fun mk_perm_bool_simproc names = Simplifier.simproc_i
    45   (theory_of_thm perm_bool) "perm_bool" [@{term "perm pi x"}] (fn thy => fn ss =>
    46     fn Const ("Nominal.perm", _) $ _ $ t =>
    47          if the_default "" (try (head_of #> dest_Const #> fst) t) mem names
    48          then SOME perm_bool else NONE
    49      | _ => NONE);
    50 
    51 fun transp ([] :: _) = []
    52   | transp xs = map hd xs :: transp (map tl xs);
    53 
    54 fun add_binders thy i (t as (_ $ _)) bs = (case strip_comb t of
    55       (Const (s, T), ts) => (case strip_type T of
    56         (Ts, Type (tname, _)) =>
    57           (case NominalPackage.get_nominal_datatype thy tname of
    58              NONE => fold (add_binders thy i) ts bs
    59            | SOME {descr, index, ...} => (case AList.lookup op =
    60                  (#3 (the (AList.lookup op = descr index))) s of
    61                NONE => fold (add_binders thy i) ts bs
    62              | SOME cargs => fst (fold (fn (xs, x) => fn (bs', cargs') =>
    63                  let val (cargs1, (u, _) :: cargs2) = chop (length xs) cargs'
    64                  in (add_binders thy i u
    65                    (fold (fn (u, T) =>
    66                       if exists (fn j => j < i) (loose_bnos u) then I
    67                       else insert (op aconv o pairself fst)
    68                         (incr_boundvars (~i) u, T)) cargs1 bs'), cargs2)
    69                  end) cargs (bs, ts ~~ Ts))))
    70       | _ => fold (add_binders thy i) ts bs)
    71     | (u, ts) => add_binders thy i u (fold (add_binders thy i) ts bs))
    72   | add_binders thy i (Abs (_, _, t)) bs = add_binders thy (i + 1) t bs
    73   | add_binders thy i _ bs = bs;
    74 
    75 fun split_conj f names (Const ("op &", _) $ p $ q) _ = (case head_of p of
    76       Const (name, _) =>
    77         if name mem names then SOME (f p q) else NONE
    78     | _ => NONE)
    79   | split_conj _ _ _ _ = NONE;
    80 
    81 fun strip_all [] t = t
    82   | strip_all (_ :: xs) (Const ("All", _) $ Abs (s, T, t)) = strip_all xs t;
    83 
    84 (*********************************************************************)
    85 (* maps  R ... & (ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t))  *)
    86 (* or    ALL pi_1 ... pi_n. P (pi_1 o ... o pi_n o t)                *)
    87 (* to    R ... & id (ALL z. (pi_1 o ... o pi_n o t))                 *)
    88 (* or    id (ALL z. (pi_1 o ... o pi_n o t))                         *)
    89 (*                                                                   *)
    90 (* where "id" protects the subformula from simplification            *)
    91 (*********************************************************************)
    92 
    93 fun inst_conj_all names ps pis (Const ("op &", _) $ p $ q) _ =
    94       (case head_of p of
    95          Const (name, _) =>
    96            if name mem names then SOME (HOLogic.mk_conj (p,
    97              Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
    98                (subst_bounds (pis, strip_all pis q))))
    99            else NONE
   100        | _ => NONE)
   101   | inst_conj_all names ps pis t u =
   102       if member (op aconv) ps (head_of u) then
   103         SOME (Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
   104           (subst_bounds (pis, strip_all pis t)))
   105       else NONE
   106   | inst_conj_all _ _ _ _ _ = NONE;
   107 
   108 fun inst_conj_all_tac k = EVERY
   109   [TRY (EVERY [etac conjE 1, rtac conjI 1, atac 1]),
   110    REPEAT_DETERM_N k (etac allE 1),
   111    simp_tac (HOL_basic_ss addsimps [@{thm id_apply}]) 1];
   112 
   113 fun map_term f t u = (case f t u of
   114       NONE => map_term' f t u | x => x)
   115 and map_term' f (t $ u) (t' $ u') = (case (map_term f t t', map_term f u u') of
   116       (NONE, NONE) => NONE
   117     | (SOME t'', NONE) => SOME (t'' $ u)
   118     | (NONE, SOME u'') => SOME (t $ u'')
   119     | (SOME t'', SOME u'') => SOME (t'' $ u''))
   120   | map_term' f (Abs (s, T, t)) (Abs (s', T', t')) = (case map_term f t t' of
   121       NONE => NONE
   122     | SOME t'' => SOME (Abs (s, T, t'')))
   123   | map_term' _ _ _ = NONE;
   124 
   125 (*********************************************************************)
   126 (*         Prove  F[f t]  from  F[t],  where F is monotone           *)
   127 (*********************************************************************)
   128 
   129 fun map_thm ctxt f tac monos opt th =
   130   let
   131     val prop = prop_of th;
   132     fun prove t =
   133       Goal.prove ctxt [] [] t (fn _ =>
   134         EVERY [cut_facts_tac [th] 1, etac rev_mp 1,
   135           REPEAT_DETERM (FIRSTGOAL (resolve_tac monos)),
   136           REPEAT_DETERM (rtac impI 1 THEN (atac 1 ORELSE tac))])
   137   in Option.map prove (map_term f prop (the_default prop opt)) end;
   138 
   139 val eta_contract_cterm = Thm.dest_arg o Thm.cprop_of o Thm.eta_conversion;
   140 
   141 fun first_order_matchs pats objs = Thm.first_order_match
   142   (eta_contract_cterm (Conjunction.mk_conjunction_balanced pats),
   143    eta_contract_cterm (Conjunction.mk_conjunction_balanced objs));
   144 
   145 fun first_order_mrs ths th = ths MRS
   146   Thm.instantiate (first_order_matchs (cprems_of th) (map cprop_of ths)) th;
   147 
   148 fun prove_strong_ind s avoids thy =
   149   let
   150     val ctxt = ProofContext.init thy;
   151     val ({names, ...}, {raw_induct, intrs, elims, ...}) =
   152       InductivePackage.the_inductive ctxt (Sign.intern_const thy s);
   153     val ind_params = InductivePackage.params_of raw_induct;
   154     val raw_induct = atomize_induct ctxt raw_induct;
   155     val elims = map (atomize_induct ctxt) elims;
   156     val monos = InductivePackage.get_monos ctxt;
   157     val eqvt_thms = NominalThmDecls.get_eqvt_thms ctxt;
   158     val _ = (case names \\ foldl (apfst prop_of #> add_term_consts) [] eqvt_thms of
   159         [] => ()
   160       | xs => error ("Missing equivariance theorem for predicate(s): " ^
   161           commas_quote xs));
   162     val induct_cases = map fst (fst (RuleCases.get (the
   163       (Induct.lookup_inductP ctxt (hd names)))));
   164     val raw_induct' = Logic.unvarify (prop_of raw_induct);
   165     val elims' = map (Logic.unvarify o prop_of) elims;
   166     val concls = raw_induct' |> Logic.strip_imp_concl |> HOLogic.dest_Trueprop |>
   167       HOLogic.dest_conj |> map (HOLogic.dest_imp ##> strip_comb);
   168     val ps = map (fst o snd) concls;
   169 
   170     val _ = (case duplicates (op = o pairself fst) avoids of
   171         [] => ()
   172       | xs => error ("Duplicate case names: " ^ commas_quote (map fst xs)));
   173     val _ = assert_all (null o duplicates op = o snd) avoids
   174       (fn (a, _) => error ("Duplicate variable names for case " ^ quote a));
   175     val _ = (case map fst avoids \\ induct_cases of
   176         [] => ()
   177       | xs => error ("No such case(s) in inductive definition: " ^ commas_quote xs));
   178     val avoids' = if null induct_cases then replicate (length intrs) ("", [])
   179       else map (fn name =>
   180         (name, the_default [] (AList.lookup op = avoids name))) induct_cases;
   181     fun mk_avoids params (name, ps) =
   182       let val k = length params - 1
   183       in map (fn x => case find_index (equal x o fst) params of
   184           ~1 => error ("No such variable in case " ^ quote name ^
   185             " of inductive definition: " ^ quote x)
   186         | i => (Bound (k - i), snd (nth params i))) ps
   187       end;
   188 
   189     val prems = map (fn (prem, avoid) =>
   190       let
   191         val prems = map (incr_boundvars 1) (Logic.strip_assums_hyp prem);
   192         val concl = incr_boundvars 1 (Logic.strip_assums_concl prem);
   193         val params = Logic.strip_params prem
   194       in
   195         (params,
   196          fold (add_binders thy 0) (prems @ [concl]) [] @
   197            map (apfst (incr_boundvars 1)) (mk_avoids params avoid),
   198          prems, strip_comb (HOLogic.dest_Trueprop concl))
   199       end) (Logic.strip_imp_prems raw_induct' ~~ avoids');
   200 
   201     val atomTs = distinct op = (maps (map snd o #2) prems);
   202     val ind_sort = if null atomTs then HOLogic.typeS
   203       else Sign.certify_sort thy (map (fn T => Sign.intern_class thy
   204         ("fs_" ^ Sign.base_name (fst (dest_Type T)))) atomTs);
   205     val fs_ctxt_tyname = Name.variant (map fst (term_tfrees raw_induct')) "'n";
   206     val fs_ctxt_name = Name.variant (add_term_names (raw_induct', [])) "z";
   207     val fsT = TFree (fs_ctxt_tyname, ind_sort);
   208 
   209     val inductive_forall_def' = Drule.instantiate'
   210       [SOME (ctyp_of thy fsT)] [] inductive_forall_def;
   211 
   212     fun lift_pred' t (Free (s, T)) ts =
   213       list_comb (Free (s, fsT --> T), t :: ts);
   214     val lift_pred = lift_pred' (Bound 0);
   215 
   216     fun lift_prem (t as (f $ u)) =
   217           let val (p, ts) = strip_comb t
   218           in
   219             if p mem ps then
   220               Const (inductive_forall_name,
   221                 (fsT --> HOLogic.boolT) --> HOLogic.boolT) $
   222                   Abs ("z", fsT, lift_pred p (map (incr_boundvars 1) ts))
   223             else lift_prem f $ lift_prem u
   224           end
   225       | lift_prem (Abs (s, T, t)) = Abs (s, T, lift_prem t)
   226       | lift_prem t = t;
   227 
   228     fun mk_distinct [] = []
   229       | mk_distinct ((x, T) :: xs) = List.mapPartial (fn (y, U) =>
   230           if T = U then SOME (HOLogic.mk_Trueprop
   231             (HOLogic.mk_not (HOLogic.eq_const T $ x $ y)))
   232           else NONE) xs @ mk_distinct xs;
   233 
   234     fun mk_fresh (x, T) = HOLogic.mk_Trueprop
   235       (NominalPackage.fresh_const T fsT $ x $ Bound 0);
   236 
   237     val (prems', prems'') = split_list (map (fn (params, bvars, prems, (p, ts)) =>
   238       let
   239         val params' = params @ [("y", fsT)];
   240         val prem = Logic.list_implies
   241           (map mk_fresh bvars @ mk_distinct bvars @
   242            map (fn prem =>
   243              if null (term_frees prem inter ps) then prem
   244              else lift_prem prem) prems,
   245            HOLogic.mk_Trueprop (lift_pred p ts));
   246         val vs = map (Var o apfst (rpair 0)) (rename_wrt_term prem params')
   247       in
   248         (list_all (params', prem), (rev vs, subst_bounds (vs, prem)))
   249       end) prems);
   250 
   251     val ind_vars =
   252       (DatatypeProp.indexify_names (replicate (length atomTs) "pi") ~~
   253        map NominalAtoms.mk_permT atomTs) @ [("z", fsT)];
   254     val ind_Ts = rev (map snd ind_vars);
   255 
   256     val concl = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   257       (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem,
   258         HOLogic.list_all (ind_vars, lift_pred p
   259           (map (fold_rev (NominalPackage.mk_perm ind_Ts)
   260             (map Bound (length atomTs downto 1))) ts)))) concls));
   261 
   262     val concl' = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   263       (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem,
   264         lift_pred' (Free (fs_ctxt_name, fsT)) p ts)) concls));
   265 
   266     val vc_compat = map (fn (params, bvars, prems, (p, ts)) =>
   267       map (fn q => list_all (params, incr_boundvars ~1 (Logic.list_implies
   268           (List.mapPartial (fn prem =>
   269              if null (ps inter term_frees prem) then SOME prem
   270              else map_term (split_conj (K o I) names) prem prem) prems, q))))
   271         (mk_distinct bvars @
   272          maps (fn (t, T) => map (fn (u, U) => HOLogic.mk_Trueprop
   273            (NominalPackage.fresh_const U T $ u $ t)) bvars)
   274              (ts ~~ binder_types (fastype_of p)))) prems;
   275 
   276     val perm_pi_simp = PureThy.get_thms thy "perm_pi_simp";
   277     val pt2_atoms = map (fn aT => PureThy.get_thm thy
   278       ("pt_" ^ Sign.base_name (fst (dest_Type aT)) ^ "2")) atomTs;
   279     val eqvt_ss = Simplifier.theory_context thy HOL_basic_ss
   280       addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms)
   281       addsimprocs [mk_perm_bool_simproc ["Fun.id"],
   282         NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun];
   283     val fresh_bij = PureThy.get_thms thy "fresh_bij";
   284     val perm_bij = PureThy.get_thms thy "perm_bij";
   285     val fs_atoms = map (fn aT => PureThy.get_thm thy
   286       ("fs_" ^ Sign.base_name (fst (dest_Type aT)) ^ "1")) atomTs;
   287     val exists_fresh' = PureThy.get_thms thy "exists_fresh'";
   288     val fresh_atm = PureThy.get_thms thy "fresh_atm";
   289     val calc_atm = PureThy.get_thms thy "calc_atm";
   290     val perm_fresh_fresh = PureThy.get_thms thy "perm_fresh_fresh";
   291 
   292     fun obtain_fresh_name ts T (freshs1, freshs2, ctxt) =
   293       let
   294         (** protect terms to avoid that supp_prod interferes with   **)
   295         (** pairs used in introduction rules of inductive predicate **)
   296         fun protect t =
   297           let val T = fastype_of t in Const ("Fun.id", T --> T) $ t end;
   298         val p = foldr1 HOLogic.mk_prod (map protect ts @ freshs1);
   299         val ex = Goal.prove ctxt [] [] (HOLogic.mk_Trueprop
   300             (HOLogic.exists_const T $ Abs ("x", T,
   301               NominalPackage.fresh_const T (fastype_of p) $
   302                 Bound 0 $ p)))
   303           (fn _ => EVERY
   304             [resolve_tac exists_fresh' 1,
   305              simp_tac (HOL_ss addsimps (supp_prod :: finite_Un :: fs_atoms)) 1]);
   306         val (([cx], ths), ctxt') = Obtain.result
   307           (fn _ => EVERY
   308             [etac exE 1,
   309              full_simp_tac (HOL_ss addsimps (fresh_prod :: fresh_atm)) 1,
   310              full_simp_tac (HOL_basic_ss addsimps [@{thm id_apply}]) 1,
   311              REPEAT (etac conjE 1)])
   312           [ex] ctxt
   313       in (freshs1 @ [term_of cx], freshs2 @ ths, ctxt') end;
   314 
   315     fun mk_ind_proof thy thss =
   316       Goal.prove_global thy [] prems' concl' (fn {prems = ihyps, context = ctxt} =>
   317         let val th = Goal.prove ctxt [] [] concl (fn {context, ...} =>
   318           rtac raw_induct 1 THEN
   319           EVERY (maps (fn ((((_, bvars, oprems, _), vc_compat_ths), ihyp), (vs, ihypt)) =>
   320             [REPEAT (rtac allI 1), simp_tac eqvt_ss 1,
   321              SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} =>
   322                let
   323                  val (params', (pis, z)) =
   324                    chop (length params - length atomTs - 1) (map term_of params) ||>
   325                    split_last;
   326                  val bvars' = map
   327                    (fn (Bound i, T) => (nth params' (length params' - i), T)
   328                      | (t, T) => (t, T)) bvars;
   329                  val pi_bvars = map (fn (t, _) =>
   330                    fold_rev (NominalPackage.mk_perm []) pis t) bvars';
   331                  val (P, ts) = strip_comb (HOLogic.dest_Trueprop (term_of concl));
   332                  val (freshs1, freshs2, ctxt'') = fold
   333                    (obtain_fresh_name (ts @ pi_bvars))
   334                    (map snd bvars') ([], [], ctxt');
   335                  val freshs2' = NominalPackage.mk_not_sym freshs2;
   336                  val pis' = map NominalPackage.perm_of_pair (pi_bvars ~~ freshs1);
   337                  fun concat_perm pi1 pi2 =
   338                    let val T = fastype_of pi1
   339                    in if T = fastype_of pi2 then
   340                        Const ("List.append", T --> T --> T) $ pi1 $ pi2
   341                      else pi2
   342                    end;
   343                  val pis'' = fold (concat_perm #> map) pis' pis;
   344                  val env = Pattern.first_order_match thy (ihypt, prop_of ihyp)
   345                    (Vartab.empty, Vartab.empty);
   346                  val ihyp' = Thm.instantiate ([], map (pairself (cterm_of thy))
   347                    (map (Envir.subst_vars env) vs ~~
   348                     map (fold_rev (NominalPackage.mk_perm [])
   349                       (rev pis' @ pis)) params' @ [z])) ihyp;
   350                  fun mk_pi th =
   351                    Simplifier.simplify (HOL_basic_ss addsimps [@{thm id_apply}]
   352                        addsimprocs [NominalPackage.perm_simproc])
   353                      (Simplifier.simplify eqvt_ss
   354                        (fold_rev (mk_perm_bool o cterm_of thy)
   355                          (rev pis' @ pis) th));
   356                  val (gprems1, gprems2) = split_list
   357                    (map (fn (th, t) =>
   358                       if null (term_frees t inter ps) then (SOME th, mk_pi th)
   359                       else
   360                         (map_thm ctxt (split_conj (K o I) names)
   361                            (etac conjunct1 1) monos NONE th,
   362                          mk_pi (the (map_thm ctxt (inst_conj_all names ps (rev pis''))
   363                            (inst_conj_all_tac (length pis'')) monos (SOME t) th))))
   364                       (gprems ~~ oprems)) |>> List.mapPartial I;
   365                  val vc_compat_ths' = map (fn th =>
   366                    let
   367                      val th' = first_order_mrs gprems1 th;
   368                      val (bop, lhs, rhs) = (case concl_of th' of
   369                          _ $ (fresh $ lhs $ rhs) =>
   370                            (fn t => fn u => fresh $ t $ u, lhs, rhs)
   371                        | _ $ (_ $ (_ $ lhs $ rhs)) =>
   372                            (curry (HOLogic.mk_not o HOLogic.mk_eq), lhs, rhs));
   373                      val th'' = Goal.prove ctxt'' [] [] (HOLogic.mk_Trueprop
   374                          (bop (fold_rev (NominalPackage.mk_perm []) pis lhs)
   375                             (fold_rev (NominalPackage.mk_perm []) pis rhs)))
   376                        (fn _ => simp_tac (HOL_basic_ss addsimps
   377                           (fresh_bij @ perm_bij)) 1 THEN rtac th' 1)
   378                    in Simplifier.simplify (eqvt_ss addsimps fresh_atm) th'' end)
   379                      vc_compat_ths;
   380                  val vc_compat_ths'' = NominalPackage.mk_not_sym vc_compat_ths';
   381                  (** Since calc_atm simplifies (pi :: 'a prm) o (x :: 'b) to x **)
   382                  (** we have to pre-simplify the rewrite rules                 **)
   383                  val calc_atm_ss = HOL_ss addsimps calc_atm @
   384                     map (Simplifier.simplify (HOL_ss addsimps calc_atm))
   385                       (vc_compat_ths'' @ freshs2');
   386                  val th = Goal.prove ctxt'' [] []
   387                    (HOLogic.mk_Trueprop (list_comb (P $ hd ts,
   388                      map (fold (NominalPackage.mk_perm []) pis') (tl ts))))
   389                    (fn _ => EVERY ([simp_tac eqvt_ss 1, rtac ihyp' 1,
   390                      REPEAT_DETERM_N (nprems_of ihyp - length gprems)
   391                        (simp_tac calc_atm_ss 1),
   392                      REPEAT_DETERM_N (length gprems)
   393                        (simp_tac (HOL_ss
   394                           addsimps inductive_forall_def' :: gprems2
   395                           addsimprocs [NominalPackage.perm_simproc]) 1)]));
   396                  val final = Goal.prove ctxt'' [] [] (term_of concl)
   397                    (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (HOL_ss
   398                      addsimps vc_compat_ths'' @ freshs2' @
   399                        perm_fresh_fresh @ fresh_atm) 1);
   400                  val final' = ProofContext.export ctxt'' ctxt' [final];
   401                in resolve_tac final' 1 end) context 1])
   402                  (prems ~~ thss ~~ ihyps ~~ prems'')))
   403         in
   404           cut_facts_tac [th] 1 THEN REPEAT (etac conjE 1) THEN
   405           REPEAT (REPEAT (resolve_tac [conjI, impI] 1) THEN
   406             etac impE 1 THEN atac 1 THEN REPEAT (etac @{thm allE_Nil} 1) THEN
   407             asm_full_simp_tac (simpset_of thy) 1)
   408         end);
   409 
   410     (** strong case analysis rule **)
   411 
   412     val cases_prems = map (fn ((name, avoids), rule) =>
   413       let
   414         val prem :: prems = Logic.strip_imp_prems rule;
   415         val concl = Logic.strip_imp_concl rule;
   416         val used = add_term_free_names (rule, [])
   417       in
   418         (prem,
   419          List.drop (snd (strip_comb (HOLogic.dest_Trueprop prem)), length ind_params),
   420          concl,
   421          fst (fold_map (fn (prem, (_, avoid)) => fn used =>
   422            let
   423              val prems = Logic.strip_assums_hyp prem;
   424              val params = Logic.strip_params prem;
   425              val bnds = fold (add_binders thy 0) prems [] @ mk_avoids params avoid;
   426              fun mk_subst (p as (s, T)) (i, j, used, ps, qs, is, ts) =
   427                if member (op = o apsnd fst) bnds (Bound i) then
   428                  let
   429                    val s' = Name.variant used s;
   430                    val t = Free (s', T)
   431                  in (i + 1, j, s' :: used, ps, (t, T) :: qs, i :: is, t :: ts) end
   432                else (i + 1, j + 1, used, p :: ps, qs, is, Bound j :: ts);
   433              val (_, _, used', ps, qs, is, ts) = fold_rev mk_subst params
   434                (0, 0, used, [], [], [], [])
   435            in
   436              ((ps, qs, is, map (curry subst_bounds (rev ts)) prems), used')
   437            end) (prems ~~ avoids) used))
   438       end)
   439         (InductivePackage.partition_rules' raw_induct (intrs ~~ avoids') ~~
   440          elims');
   441 
   442     val cases_prems' =
   443       map (fn (prem, args, concl, prems) =>
   444         let
   445           fun mk_prem (ps, [], _, prems) =
   446                 list_all (ps, Logic.list_implies (prems, concl))
   447             | mk_prem (ps, qs, _, prems) =
   448                 list_all (ps, Logic.mk_implies
   449                   (Logic.list_implies
   450                     (mk_distinct qs @
   451                      maps (fn (t, T) => map (fn u => HOLogic.mk_Trueprop
   452                       (NominalPackage.fresh_const T (fastype_of u) $ t $ u))
   453                         args) qs,
   454                      HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
   455                        (map HOLogic.dest_Trueprop prems))),
   456                    concl))
   457           in map mk_prem prems end) cases_prems;
   458 
   459     val cases_eqvt_ss = Simplifier.theory_context thy HOL_ss
   460       addsimps eqvt_thms @ fresh_atm @ perm_pi_simp delsplits [split_if]
   461       addsimprocs [NominalPermeq.perm_simproc_app,
   462         NominalPermeq.perm_simproc_fun];
   463 
   464     val simp_fresh_atm = map
   465       (Simplifier.simplify (HOL_basic_ss addsimps fresh_atm));
   466 
   467     fun mk_cases_proof thy ((((name, thss), elim), (prem, args, concl, prems)),
   468         prems') =
   469       (name, Goal.prove_global thy [] (prem :: prems') concl
   470         (fn {prems = hyp :: hyps, context = ctxt1} =>
   471         EVERY (rtac (hyp RS elim) 1 ::
   472           map (fn (((_, vc_compat_ths), case_hyp), (_, qs, is, _)) =>
   473             SUBPROOF (fn {prems = case_hyps, params, context = ctxt2, concl, ...} =>
   474               if null qs then
   475                 rtac (first_order_mrs case_hyps case_hyp) 1
   476               else
   477                 let
   478                   val params' = map (term_of o nth (rev params)) is;
   479                   val tab = params' ~~ map fst qs;
   480                   val (hyps1, hyps2) = chop (length args) case_hyps;
   481                   (* turns a = t and [x1 # t, ..., xn # t] *)
   482                   (* into [x1 # a, ..., xn # a]            *)
   483                   fun inst_fresh th' ths =
   484                     let val (ths1, ths2) = chop (length qs) ths
   485                     in
   486                       (map (fn th =>
   487                          let
   488                            val (cf, ct) =
   489                              Thm.dest_comb (Thm.dest_arg (cprop_of th));
   490                            val arg_cong' = Drule.instantiate'
   491                              [SOME (ctyp_of_term ct)]
   492                              [NONE, SOME ct, SOME cf] (arg_cong RS iffD2);
   493                            val inst = Thm.first_order_match (ct,
   494                              Thm.dest_arg (Thm.dest_arg (cprop_of th')))
   495                          in [th', th] MRS Thm.instantiate inst arg_cong'
   496                          end) ths1,
   497                        ths2)
   498                     end;
   499                   val (vc_compat_ths1, vc_compat_ths2) =
   500                     chop (length vc_compat_ths - length args * length qs)
   501                       (map (first_order_mrs hyps2) vc_compat_ths);
   502                   val vc_compat_ths' =
   503                     NominalPackage.mk_not_sym vc_compat_ths1 @
   504                     flat (fst (fold_map inst_fresh hyps1 vc_compat_ths2));
   505                   val (freshs1, freshs2, ctxt3) = fold
   506                     (obtain_fresh_name (args @ map fst qs @ params'))
   507                     (map snd qs) ([], [], ctxt2);
   508                   val freshs2' = NominalPackage.mk_not_sym freshs2;
   509                   val pis = map (NominalPackage.perm_of_pair)
   510                     ((freshs1 ~~ map fst qs) @ (params' ~~ freshs1));
   511                   val mk_pis = fold_rev mk_perm_bool (map (cterm_of thy) pis);
   512                   val obj = cterm_of thy (foldr1 HOLogic.mk_conj (map (map_aterms
   513                      (fn x as Free _ =>
   514                            if x mem args then x
   515                            else (case AList.lookup op = tab x of
   516                              SOME y => y
   517                            | NONE => fold_rev (NominalPackage.mk_perm []) pis x)
   518                        | x => x) o HOLogic.dest_Trueprop o prop_of) case_hyps));
   519                   val inst = Thm.first_order_match (Thm.dest_arg
   520                     (Drule.strip_imp_concl (hd (cprems_of case_hyp))), obj);
   521                   val th = Goal.prove ctxt3 [] [] (term_of concl)
   522                     (fn {context = ctxt4, ...} =>
   523                        rtac (Thm.instantiate inst case_hyp) 1 THEN
   524                        SUBPROOF (fn {prems = fresh_hyps, ...} =>
   525                          let
   526                            val fresh_hyps' = NominalPackage.mk_not_sym fresh_hyps;
   527                            val case_ss = cases_eqvt_ss addsimps freshs2' @
   528                              simp_fresh_atm (vc_compat_ths' @ fresh_hyps');
   529                            val fresh_fresh_ss = case_ss addsimps perm_fresh_fresh;
   530                            val calc_atm_ss = case_ss addsimps calc_atm;
   531                            val hyps1' = map
   532                              (mk_pis #> Simplifier.simplify fresh_fresh_ss) hyps1;
   533                            val hyps2' = map
   534                              (mk_pis #> Simplifier.simplify case_ss) hyps2;
   535                            (* calc_atm must be applied last, since *)
   536                            (* it may interfere with other rules    *)
   537                            val case_hyps' = map
   538                              (Simplifier.simplify calc_atm_ss) (hyps1' @ hyps2')
   539                          in
   540                            simp_tac calc_atm_ss 1 THEN
   541                            REPEAT_DETERM (TRY (rtac conjI 1) THEN
   542                              resolve_tac case_hyps' 1)
   543                          end) ctxt4 1)
   544                   val final = ProofContext.export ctxt3 ctxt2 [th]
   545                 in resolve_tac final 1 end) ctxt1 1)
   546                   (thss ~~ hyps ~~ prems))))
   547 
   548   in
   549     thy |>
   550     ProofContext.init |>
   551     Proof.theorem_i NONE (fn thss => ProofContext.theory (fn thy =>
   552       let
   553         val ctxt = ProofContext.init thy;
   554         val rec_name = space_implode "_" (map Sign.base_name names);
   555         val ind_case_names = RuleCases.case_names induct_cases;
   556         val induct_cases' = InductivePackage.partition_rules' raw_induct
   557           (intrs ~~ induct_cases); 
   558         val thss' = map (map atomize_intr) thss;
   559         val thsss = InductivePackage.partition_rules' raw_induct (intrs ~~ thss');
   560         val strong_raw_induct =
   561           mk_ind_proof thy thss' |> InductivePackage.rulify;
   562         val strong_cases = map (mk_cases_proof thy ##> InductivePackage.rulify)
   563           (thsss ~~ elims ~~ cases_prems ~~ cases_prems');
   564         val strong_induct =
   565           if length names > 1 then
   566             (strong_raw_induct, [ind_case_names, RuleCases.consumes 0])
   567           else (strong_raw_induct RSN (2, rev_mp),
   568             [ind_case_names, RuleCases.consumes 1]);
   569         val ([strong_induct'], thy') = thy |>
   570           Sign.add_path rec_name |>
   571           PureThy.add_thms [(("strong_induct", #1 strong_induct), #2 strong_induct)];
   572         val strong_inducts =
   573           ProjectRule.projects ctxt (1 upto length names) strong_induct'
   574       in
   575         thy' |>
   576         PureThy.add_thmss [(("strong_inducts", strong_inducts),
   577           [ind_case_names, RuleCases.consumes 1])] |> snd |>
   578         Sign.parent_path |>
   579         fold (fn ((name, elim), (_, cases)) =>
   580           Sign.add_path (Sign.base_name name) #>
   581           PureThy.add_thms [(("strong_cases", elim),
   582             [RuleCases.case_names (map snd cases),
   583              RuleCases.consumes 1])] #> snd #>
   584           Sign.parent_path) (strong_cases ~~ induct_cases')
   585       end))
   586       (map (map (rulify_term thy #> rpair [])) vc_compat)
   587   end;
   588 
   589 fun prove_eqvt s xatoms thy =
   590   let
   591     val ctxt = ProofContext.init thy;
   592     val ({names, ...}, {raw_induct, intrs, elims, ...}) =
   593       InductivePackage.the_inductive ctxt (Sign.intern_const thy s);
   594     val raw_induct = atomize_induct ctxt raw_induct;
   595     val elims = map (atomize_induct ctxt) elims;
   596     val intrs = map atomize_intr intrs;
   597     val monos = InductivePackage.get_monos ctxt;
   598     val intrs' = InductivePackage.unpartition_rules intrs
   599       (map (fn (((s, ths), (_, k)), th) =>
   600            (s, ths ~~ InductivePackage.infer_intro_vars th k ths))
   601          (InductivePackage.partition_rules raw_induct intrs ~~
   602           InductivePackage.arities_of raw_induct ~~ elims));
   603     val atoms' = NominalAtoms.atoms_of thy;
   604     val atoms =
   605       if null xatoms then atoms' else
   606       let val atoms = map (Sign.intern_type thy) xatoms
   607       in
   608         (case duplicates op = atoms of
   609              [] => ()
   610            | xs => error ("Duplicate atoms: " ^ commas xs);
   611          case atoms \\ atoms' of
   612              [] => ()
   613            | xs => error ("No such atoms: " ^ commas xs);
   614          atoms)
   615       end;
   616     val perm_pi_simp = PureThy.get_thms thy "perm_pi_simp";
   617     val eqvt_ss = Simplifier.theory_context thy HOL_basic_ss addsimps
   618       (NominalThmDecls.get_eqvt_thms ctxt @ perm_pi_simp) addsimprocs
   619       [mk_perm_bool_simproc names,
   620        NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun];
   621     val t = Logic.unvarify (concl_of raw_induct);
   622     val pi = Name.variant (add_term_names (t, [])) "pi";
   623     val ps = map (fst o HOLogic.dest_imp)
   624       (HOLogic.dest_conj (HOLogic.dest_Trueprop t));
   625     fun eqvt_tac pi (intr, vs) st =
   626       let
   627         fun eqvt_err s = error
   628           ("Could not prove equivariance for introduction rule\n" ^
   629            Syntax.string_of_term_global (theory_of_thm intr)
   630              (Logic.unvarify (prop_of intr)) ^ "\n" ^ s);
   631         val res = SUBPROOF (fn {prems, params, ...} =>
   632           let
   633             val prems' = map (fn th => the_default th (map_thm ctxt
   634               (split_conj (K I) names) (etac conjunct2 1) monos NONE th)) prems;
   635             val prems'' = map (fn th => Simplifier.simplify eqvt_ss
   636               (mk_perm_bool (cterm_of thy pi) th)) prems';
   637             val intr' = Drule.cterm_instantiate (map (cterm_of thy) vs ~~
   638                map (cterm_of thy o NominalPackage.mk_perm [] pi o term_of) params)
   639                intr
   640           in (rtac intr' THEN_ALL_NEW (TRY o resolve_tac prems'')) 1
   641           end) ctxt 1 st
   642       in
   643         case (Seq.pull res handle THM (s, _, _) => eqvt_err s) of
   644           NONE => eqvt_err ("Rule does not match goal\n" ^
   645             Syntax.string_of_term_global (theory_of_thm st) (hd (prems_of st)))
   646         | SOME (th, _) => Seq.single th
   647       end;
   648     val thss = map (fn atom =>
   649       let val pi' = Free (pi, NominalAtoms.mk_permT (Type (atom, [])))
   650       in map (fn th => zero_var_indexes (th RS mp))
   651         (DatatypeAux.split_conj_thm (Goal.prove_global thy [] []
   652           (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map (fn p =>
   653             HOLogic.mk_imp (p, list_comb
   654              (apsnd (map (NominalPackage.mk_perm [] pi')) (strip_comb p)))) ps)))
   655           (fn _ => EVERY (rtac raw_induct 1 :: map (fn intr_vs =>
   656               full_simp_tac eqvt_ss 1 THEN
   657               eqvt_tac pi' intr_vs) intrs'))))
   658       end) atoms
   659   in
   660     fold (fn (name, ths) =>
   661       Sign.add_path (Sign.base_name name) #>
   662       PureThy.add_thmss [(("eqvt", ths), [NominalThmDecls.eqvt_add])] #> snd #>
   663       Sign.parent_path) (names ~~ transp thss) thy
   664   end;
   665 
   666 
   667 (* outer syntax *)
   668 
   669 local structure P = OuterParse and K = OuterKeyword in
   670 
   671 val _ = OuterKeyword.keyword "avoids";
   672 
   673 val _ =
   674   OuterSyntax.command "nominal_inductive"
   675     "prove equivariance and strong induction theorem for inductive predicate involving nominal datatypes" K.thy_goal
   676     (P.name -- Scan.optional (P.$$$ "avoids" |-- P.and_list1 (P.name --
   677       (P.$$$ ":" |-- Scan.repeat1 P.name))) [] >> (fn (name, avoids) =>
   678         Toplevel.print o Toplevel.theory_to_proof (prove_strong_ind name avoids)));
   679 
   680 val _ =
   681   OuterSyntax.command "equivariance"
   682     "prove equivariance for inductive predicate involving nominal datatypes" K.thy_decl
   683     (P.name -- Scan.optional (P.$$$ "[" |-- P.list1 P.name --| P.$$$ "]") [] >>
   684       (fn (name, atoms) => Toplevel.theory (prove_eqvt name atoms)));
   685 
   686 end;
   687 
   688 end