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