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