src/HOL/Nominal/nominal_inductive.ML
author berghofe
Thu Sep 13 18:11:59 2007 +0200 (2007-09-13)
changeset 24570 621b60b1df00
parent 23531 38a304b3fe1e
child 24571 a6d0428dea8e
permissions -rw-r--r--
Generalized equivariance and nominal_inductive commands to
inductive definitions involving arbitrary monotone operators.
berghofe@22313
     1
(*  Title:      HOL/Nominal/nominal_inductive.ML
berghofe@22313
     2
    ID:         $Id$
berghofe@22313
     3
    Author:     Stefan Berghofer, TU Muenchen
berghofe@22313
     4
berghofe@22530
     5
Infrastructure for proving equivariance and strong induction theorems
berghofe@22530
     6
for inductive predicates involving nominal datatypes.
berghofe@22313
     7
*)
berghofe@22313
     8
berghofe@22313
     9
signature NOMINAL_INDUCTIVE =
berghofe@22313
    10
sig
berghofe@22730
    11
  val prove_strong_ind: string -> (string * string list) list -> theory -> Proof.state
berghofe@22730
    12
  val prove_eqvt: string -> string list -> theory -> theory
berghofe@22313
    13
end
berghofe@22313
    14
berghofe@22313
    15
structure NominalInductive : NOMINAL_INDUCTIVE =
berghofe@22313
    16
struct
berghofe@22313
    17
berghofe@24570
    18
val inductive_forall_name = "HOL.induct_forall";
berghofe@24570
    19
val inductive_forall_def = thm "induct_forall_def";
berghofe@24570
    20
val inductive_atomize = thms "induct_atomize";
berghofe@24570
    21
val inductive_rulify = thms "induct_rulify";
berghofe@24570
    22
val inductive_rulify_fallback = thms "induct_rulify_fallback";
berghofe@24570
    23
berghofe@24570
    24
val rulify =
berghofe@24570
    25
  hol_simplify inductive_rulify
berghofe@24570
    26
  #> hol_simplify inductive_rulify_fallback;
berghofe@24570
    27
berghofe@24570
    28
fun rulify_term thy = MetaSimplifier.rewrite_term thy inductive_rulify [];
berghofe@24570
    29
berghofe@24570
    30
val atomize_conv =
berghofe@24570
    31
  MetaSimplifier.rewrite_cterm (true, false, false) (K (K NONE))
berghofe@24570
    32
    (HOL_basic_ss addsimps inductive_atomize);
berghofe@24570
    33
val atomize_intr = Conv.fconv_rule (Conv.prems_conv ~1 atomize_conv);
berghofe@24570
    34
val atomize_induct = Conv.fconv_rule (Conv.prems_conv ~1
berghofe@24570
    35
  (Conv.forall_conv ~1 (Conv.prems_conv ~1 atomize_conv)));
berghofe@24570
    36
berghofe@22530
    37
val finite_Un = thm "finite_Un";
berghofe@22530
    38
val supp_prod = thm "supp_prod";
berghofe@22530
    39
val fresh_prod = thm "fresh_prod";
berghofe@22530
    40
berghofe@24570
    41
val perm_bool = mk_meta_eq (thm "perm_bool");
berghofe@22313
    42
val perm_boolI = thm "perm_boolI";
berghofe@22313
    43
val (_, [perm_boolI_pi, _]) = Drule.strip_comb (snd (Thm.dest_comb
berghofe@22313
    44
  (Drule.strip_imp_concl (cprop_of perm_boolI))));
berghofe@22313
    45
berghofe@24570
    46
fun mk_perm_bool_simproc names = Simplifier.simproc_i
berghofe@24570
    47
  (theory_of_thm perm_bool) "perm_bool" [@{term "perm pi x"}] (fn thy => fn ss =>
berghofe@24570
    48
    fn Const ("Nominal.perm", _) $ _ $ t =>
berghofe@24570
    49
         if the_default "" (try (head_of #> dest_Const #> fst) t) mem names
berghofe@24570
    50
         then SOME perm_bool else NONE
berghofe@24570
    51
     | _ => NONE);
berghofe@24570
    52
berghofe@22530
    53
val allE_Nil = read_instantiate_sg (the_context()) [("x", "[]")] allE;
berghofe@22530
    54
berghofe@22313
    55
fun transp ([] :: _) = []
berghofe@22313
    56
  | transp xs = map hd xs :: transp (map tl xs);
berghofe@22313
    57
berghofe@22530
    58
fun add_binders thy i (t as (_ $ _)) bs = (case strip_comb t of
berghofe@22530
    59
      (Const (s, T), ts) => (case strip_type T of
berghofe@22530
    60
        (Ts, Type (tname, _)) =>
berghofe@22530
    61
          (case NominalPackage.get_nominal_datatype thy tname of
berghofe@22530
    62
             NONE => fold (add_binders thy i) ts bs
berghofe@22530
    63
           | SOME {descr, index, ...} => (case AList.lookup op =
berghofe@22530
    64
                 (#3 (the (AList.lookup op = descr index))) s of
berghofe@22530
    65
               NONE => fold (add_binders thy i) ts bs
berghofe@22530
    66
             | SOME cargs => fst (fold (fn (xs, x) => fn (bs', cargs') =>
berghofe@22530
    67
                 let val (cargs1, (u, _) :: cargs2) = chop (length xs) cargs'
berghofe@22530
    68
                 in (add_binders thy i u
berghofe@22530
    69
                   (fold (fn (u, T) =>
berghofe@22530
    70
                      if exists (fn j => j < i) (loose_bnos u) then I
berghofe@22530
    71
                      else insert (op aconv o pairself fst)
berghofe@22530
    72
                        (incr_boundvars (~i) u, T)) cargs1 bs'), cargs2)
berghofe@22530
    73
                 end) cargs (bs, ts ~~ Ts))))
berghofe@22530
    74
      | _ => fold (add_binders thy i) ts bs)
berghofe@22530
    75
    | (u, ts) => add_binders thy i u (fold (add_binders thy i) ts bs))
berghofe@22530
    76
  | add_binders thy i (Abs (_, _, t)) bs = add_binders thy (i + 1) t bs
berghofe@22530
    77
  | add_binders thy i _ bs = bs;
berghofe@22530
    78
berghofe@24570
    79
fun split_conj f names (Const ("op &", _) $ p $ q) _ = (case head_of p of
berghofe@24570
    80
      Const (name, _) =>
berghofe@24570
    81
        if name mem names then SOME (f p q) else NONE
berghofe@24570
    82
    | _ => NONE)
berghofe@24570
    83
  | split_conj _ _ _ _ = NONE;
berghofe@24570
    84
berghofe@24570
    85
fun strip_all [] t = t
berghofe@24570
    86
  | strip_all (_ :: xs) (Const ("All", _) $ Abs (s, T, t)) = strip_all xs t;
berghofe@24570
    87
berghofe@24570
    88
(*********************************************************************)
berghofe@24570
    89
(* maps  R ... & (ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t))  *)
berghofe@24570
    90
(* or    ALL pi_1 ... pi_n. P (pi_1 o ... o pi_n o t)                *)
berghofe@24570
    91
(* to    R ... & id (ALL z. (pi_1 o ... o pi_n o t))                 *)
berghofe@24570
    92
(* or    id (ALL z. (pi_1 o ... o pi_n o t))                         *)
berghofe@24570
    93
(*                                                                   *)
berghofe@24570
    94
(* where "id" protects the subformula from simplification            *)
berghofe@24570
    95
(*********************************************************************)
berghofe@24570
    96
berghofe@24570
    97
fun inst_conj_all names ps pis (Const ("op &", _) $ p $ q) _ =
berghofe@24570
    98
      (case head_of p of
berghofe@24570
    99
         Const (name, _) =>
berghofe@24570
   100
           if name mem names then SOME (HOLogic.mk_conj (p,
berghofe@24570
   101
             Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
berghofe@24570
   102
               (subst_bounds (pis, strip_all pis q))))
berghofe@24570
   103
           else NONE
berghofe@24570
   104
       | _ => NONE)
berghofe@24570
   105
  | inst_conj_all names ps pis t u =
berghofe@24570
   106
      if member (op aconv) ps (head_of u) then
berghofe@24570
   107
        SOME (Const ("Fun.id", HOLogic.boolT --> HOLogic.boolT) $
berghofe@24570
   108
          (subst_bounds (pis, strip_all pis t)))
berghofe@24570
   109
      else NONE
berghofe@24570
   110
  | inst_conj_all _ _ _ _ _ = NONE;
berghofe@24570
   111
berghofe@24570
   112
fun inst_conj_all_tac k = EVERY
berghofe@24570
   113
  [TRY (EVERY [etac conjE 1, rtac conjI 1, atac 1]),
berghofe@24570
   114
   REPEAT_DETERM_N k (etac allE 1),
berghofe@24570
   115
   simp_tac (HOL_basic_ss addsimps [id_apply]) 1];
berghofe@24570
   116
berghofe@24570
   117
fun map_term f t u = (case f t u of
berghofe@24570
   118
      NONE => map_term' f t u | x => x)
berghofe@24570
   119
and map_term' f (t $ u) (t' $ u') = (case (map_term f t t', map_term f u u') of
berghofe@24570
   120
      (NONE, NONE) => NONE
berghofe@24570
   121
    | (SOME t'', NONE) => SOME (t'' $ u)
berghofe@24570
   122
    | (NONE, SOME u'') => SOME (t $ u'')
berghofe@24570
   123
    | (SOME t'', SOME u'') => SOME (t'' $ u''))
berghofe@24570
   124
  | map_term' f (Abs (s, T, t)) (Abs (s', T', t')) = (case map_term f t t' of
berghofe@24570
   125
      NONE => NONE
berghofe@24570
   126
    | SOME t'' => SOME (Abs (s, T, t'')))
berghofe@24570
   127
  | map_term' _ _ _ = NONE;
berghofe@24570
   128
berghofe@24570
   129
(*********************************************************************)
berghofe@24570
   130
(*         Prove  F[f t]  from  F[t],  where F is monotone           *)
berghofe@24570
   131
(*********************************************************************)
berghofe@24570
   132
berghofe@24570
   133
fun map_thm ctxt f tac monos opt th =
berghofe@24570
   134
  let
berghofe@24570
   135
    val prop = prop_of th;
berghofe@24570
   136
    fun prove t =
berghofe@24570
   137
      Goal.prove ctxt [] [] t (fn _ =>
berghofe@24570
   138
        EVERY [cut_facts_tac [th] 1, etac rev_mp 1,
berghofe@24570
   139
          REPEAT_DETERM (FIRSTGOAL (resolve_tac monos)),
berghofe@24570
   140
          REPEAT_DETERM (rtac impI 1 THEN (atac 1 ORELSE tac))])
berghofe@24570
   141
  in Option.map prove (map_term f prop (the_default prop opt)) end;
berghofe@24570
   142
berghofe@22730
   143
fun prove_strong_ind s avoids thy =
berghofe@22313
   144
  let
berghofe@22313
   145
    val ctxt = ProofContext.init thy;
berghofe@22730
   146
    val ({names, ...}, {raw_induct, ...}) =
berghofe@22730
   147
      InductivePackage.the_inductive ctxt (Sign.intern_const thy s);
berghofe@24570
   148
    val raw_induct = atomize_induct raw_induct;
berghofe@24570
   149
    val monos = InductivePackage.get_monos ctxt;
berghofe@22788
   150
    val eqvt_thms = NominalThmDecls.get_eqvt_thms thy;
berghofe@22788
   151
    val _ = (case names \\ foldl (apfst prop_of #> add_term_consts) [] eqvt_thms of
berghofe@22788
   152
        [] => ()
berghofe@22788
   153
      | xs => error ("Missing equivariance theorem for predicate(s): " ^
berghofe@22788
   154
          commas_quote xs));
berghofe@22530
   155
    val induct_cases = map fst (fst (RuleCases.get (the
berghofe@22530
   156
      (InductAttrib.lookup_inductS ctxt (hd names)))));
berghofe@22530
   157
    val raw_induct' = Logic.unvarify (prop_of raw_induct);
berghofe@22530
   158
    val concls = raw_induct' |> Logic.strip_imp_concl |> HOLogic.dest_Trueprop |>
berghofe@22530
   159
      HOLogic.dest_conj |> map (HOLogic.dest_imp ##> strip_comb);
berghofe@22530
   160
    val ps = map (fst o snd) concls;
berghofe@22530
   161
berghofe@22530
   162
    val _ = (case duplicates (op = o pairself fst) avoids of
berghofe@22530
   163
        [] => ()
berghofe@22530
   164
      | xs => error ("Duplicate case names: " ^ commas_quote (map fst xs)));
berghofe@22530
   165
    val _ = assert_all (null o duplicates op = o snd) avoids
berghofe@22530
   166
      (fn (a, _) => error ("Duplicate variable names for case " ^ quote a));
berghofe@22530
   167
    val _ = (case map fst avoids \\ induct_cases of
berghofe@22530
   168
        [] => ()
berghofe@22530
   169
      | xs => error ("No such case(s) in inductive definition: " ^ commas_quote xs));
berghofe@22530
   170
    val avoids' = map (fn name =>
berghofe@22530
   171
      (name, the_default [] (AList.lookup op = avoids name))) induct_cases;
berghofe@22530
   172
    fun mk_avoids params (name, ps) =
berghofe@22530
   173
      let val k = length params - 1
berghofe@22530
   174
      in map (fn x => case find_index (equal x o fst) params of
berghofe@22530
   175
          ~1 => error ("No such variable in case " ^ quote name ^
berghofe@22530
   176
            " of inductive definition: " ^ quote x)
berghofe@22530
   177
        | i => (Bound (k - i), snd (nth params i))) ps
berghofe@22530
   178
      end;
berghofe@22530
   179
berghofe@22530
   180
    val prems = map (fn (prem, avoid) =>
berghofe@22530
   181
      let
berghofe@22530
   182
        val prems = map (incr_boundvars 1) (Logic.strip_assums_hyp prem);
berghofe@22530
   183
        val concl = incr_boundvars 1 (Logic.strip_assums_concl prem);
berghofe@22530
   184
        val params = Logic.strip_params prem
berghofe@22530
   185
      in
berghofe@22530
   186
        (params,
berghofe@22530
   187
         fold (add_binders thy 0) (prems @ [concl]) [] @
berghofe@22530
   188
           map (apfst (incr_boundvars 1)) (mk_avoids params avoid),
berghofe@22530
   189
         prems, strip_comb (HOLogic.dest_Trueprop concl))
berghofe@22530
   190
      end) (Logic.strip_imp_prems raw_induct' ~~ avoids');
berghofe@22530
   191
berghofe@22530
   192
    val atomTs = distinct op = (maps (map snd o #2) prems);
berghofe@22530
   193
    val ind_sort = if null atomTs then HOLogic.typeS
berghofe@22530
   194
      else Sign.certify_sort thy (map (fn T => Sign.intern_class thy
berghofe@22530
   195
        ("fs_" ^ Sign.base_name (fst (dest_Type T)))) atomTs);
berghofe@22530
   196
    val fs_ctxt_tyname = Name.variant (map fst (term_tfrees raw_induct')) "'n";
berghofe@22530
   197
    val fs_ctxt_name = Name.variant (add_term_names (raw_induct', [])) "z";
berghofe@22530
   198
    val fsT = TFree (fs_ctxt_tyname, ind_sort);
berghofe@22530
   199
berghofe@24570
   200
    val inductive_forall_def' = Drule.instantiate'
berghofe@24570
   201
      [SOME (ctyp_of thy fsT)] [] inductive_forall_def;
berghofe@24570
   202
berghofe@22530
   203
    fun lift_pred' t (Free (s, T)) ts =
berghofe@22530
   204
      list_comb (Free (s, fsT --> T), t :: ts);
berghofe@22530
   205
    val lift_pred = lift_pred' (Bound 0);
berghofe@22530
   206
berghofe@24570
   207
    fun lift_prem (t as (f $ u)) =
berghofe@22530
   208
          let val (p, ts) = strip_comb t
berghofe@22530
   209
          in
berghofe@22530
   210
            if p mem ps then
berghofe@24570
   211
              Const (inductive_forall_name,
berghofe@24570
   212
                (fsT --> HOLogic.boolT) --> HOLogic.boolT) $
berghofe@24570
   213
                  Abs ("z", fsT, lift_pred p (map (incr_boundvars 1) ts))
berghofe@22530
   214
            else lift_prem f $ lift_prem u
berghofe@22530
   215
          end
berghofe@22530
   216
      | lift_prem (Abs (s, T, t)) = Abs (s, T, lift_prem t)
berghofe@22530
   217
      | lift_prem t = t;
berghofe@22530
   218
berghofe@22530
   219
    fun mk_distinct [] = []
berghofe@22530
   220
      | mk_distinct ((x, T) :: xs) = List.mapPartial (fn (y, U) =>
berghofe@22530
   221
          if T = U then SOME (HOLogic.mk_Trueprop
berghofe@22530
   222
            (HOLogic.mk_not (HOLogic.eq_const T $ x $ y)))
berghofe@22530
   223
          else NONE) xs @ mk_distinct xs;
berghofe@22530
   224
berghofe@22530
   225
    fun mk_fresh (x, T) = HOLogic.mk_Trueprop
berghofe@22530
   226
      (Const ("Nominal.fresh", T --> fsT --> HOLogic.boolT) $ x $ Bound 0);
berghofe@22530
   227
berghofe@22530
   228
    val (prems', prems'') = split_list (map (fn (params, bvars, prems, (p, ts)) =>
berghofe@22530
   229
      let
berghofe@22530
   230
        val params' = params @ [("y", fsT)];
berghofe@22530
   231
        val prem = Logic.list_implies
berghofe@22530
   232
          (map mk_fresh bvars @ mk_distinct bvars @
berghofe@22530
   233
           map (fn prem =>
berghofe@22530
   234
             if null (term_frees prem inter ps) then prem
berghofe@22530
   235
             else lift_prem prem) prems,
berghofe@22530
   236
           HOLogic.mk_Trueprop (lift_pred p ts));
berghofe@22530
   237
        val vs = map (Var o apfst (rpair 0)) (rename_wrt_term prem params')
berghofe@22530
   238
      in
berghofe@22530
   239
        (list_all (params', prem), (rev vs, subst_bounds (vs, prem)))
berghofe@22530
   240
      end) prems);
berghofe@22530
   241
berghofe@22530
   242
    val ind_vars =
berghofe@22530
   243
      (DatatypeProp.indexify_names (replicate (length atomTs) "pi") ~~
berghofe@22530
   244
       map NominalAtoms.mk_permT atomTs) @ [("z", fsT)];
berghofe@22530
   245
    val ind_Ts = rev (map snd ind_vars);
berghofe@22530
   246
berghofe@22530
   247
    val concl = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
berghofe@22530
   248
      (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem,
berghofe@22530
   249
        HOLogic.list_all (ind_vars, lift_pred p
berghofe@22530
   250
          (map (fold_rev (NominalPackage.mk_perm ind_Ts)
berghofe@22530
   251
            (map Bound (length atomTs downto 1))) ts)))) concls));
berghofe@22530
   252
berghofe@22530
   253
    val concl' = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj
berghofe@22530
   254
      (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem,
berghofe@22530
   255
        lift_pred' (Free (fs_ctxt_name, fsT)) p ts)) concls));
berghofe@22530
   256
berghofe@22530
   257
    val vc_compat = map (fn (params, bvars, prems, (p, ts)) =>
berghofe@22530
   258
      map (fn q => list_all (params, incr_boundvars ~1 (Logic.list_implies
berghofe@24570
   259
          (List.mapPartial (fn prem =>
berghofe@24570
   260
             if null (ps inter term_frees prem) then SOME prem
berghofe@24570
   261
             else map_term (split_conj (K o I) names) prem prem) prems, q))))
berghofe@22530
   262
        (mk_distinct bvars @
berghofe@22530
   263
         maps (fn (t, T) => map (fn (u, U) => HOLogic.mk_Trueprop
berghofe@22530
   264
           (Const ("Nominal.fresh", U --> T --> HOLogic.boolT) $ u $ t)) bvars)
berghofe@22530
   265
             (ts ~~ binder_types (fastype_of p)))) prems;
berghofe@22530
   266
berghofe@24570
   267
    val perm_pi_simp = PureThy.get_thms thy (Name "perm_pi_simp");
berghofe@24570
   268
    val pt2_atoms = map (fn aT => PureThy.get_thm thy
berghofe@24570
   269
      (Name ("pt_" ^ Sign.base_name (fst (dest_Type aT)) ^ "2"))) atomTs;
berghofe@24570
   270
    val eqvt_ss = HOL_basic_ss addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms)
berghofe@24570
   271
      addsimprocs [mk_perm_bool_simproc ["Fun.id"]];
berghofe@22530
   272
    val fresh_bij = PureThy.get_thms thy (Name "fresh_bij");
berghofe@22530
   273
    val perm_bij = PureThy.get_thms thy (Name "perm_bij");
berghofe@22530
   274
    val fs_atoms = map (fn aT => PureThy.get_thm thy
berghofe@22530
   275
      (Name ("fs_" ^ Sign.base_name (fst (dest_Type aT)) ^ "1"))) atomTs;
berghofe@22530
   276
    val exists_fresh' = PureThy.get_thms thy (Name "exists_fresh'");
berghofe@22530
   277
    val fresh_atm = PureThy.get_thms thy (Name "fresh_atm");
berghofe@22530
   278
    val calc_atm = PureThy.get_thms thy (Name "calc_atm");
berghofe@22530
   279
    val perm_fresh_fresh = PureThy.get_thms thy (Name "perm_fresh_fresh");
berghofe@22530
   280
berghofe@22530
   281
    fun obtain_fresh_name ts T (freshs1, freshs2, ctxt) =
berghofe@22530
   282
      let
berghofe@22530
   283
        (** protect terms to avoid that supp_prod interferes with   **)
berghofe@22530
   284
        (** pairs used in introduction rules of inductive predicate **)
berghofe@22530
   285
        fun protect t =
berghofe@22530
   286
          let val T = fastype_of t in Const ("Fun.id", T --> T) $ t end;
berghofe@22530
   287
        val p = foldr1 HOLogic.mk_prod (map protect ts @ freshs1);
berghofe@22530
   288
        val ex = Goal.prove ctxt [] [] (HOLogic.mk_Trueprop
berghofe@22530
   289
            (HOLogic.exists_const T $ Abs ("x", T,
berghofe@22530
   290
              Const ("Nominal.fresh", T --> fastype_of p --> HOLogic.boolT) $
berghofe@22530
   291
                Bound 0 $ p)))
berghofe@22530
   292
          (fn _ => EVERY
berghofe@22530
   293
            [resolve_tac exists_fresh' 1,
berghofe@22530
   294
             simp_tac (HOL_ss addsimps (supp_prod :: finite_Un :: fs_atoms)) 1]);
berghofe@22530
   295
        val (([cx], ths), ctxt') = Obtain.result
berghofe@22530
   296
          (fn _ => EVERY
berghofe@22530
   297
            [etac exE 1,
berghofe@22530
   298
             full_simp_tac (HOL_ss addsimps (fresh_prod :: fresh_atm)) 1,
berghofe@22530
   299
             full_simp_tac (HOL_basic_ss addsimps [id_apply]) 1,
berghofe@22530
   300
             REPEAT (etac conjE 1)])
berghofe@22530
   301
          [ex] ctxt
berghofe@22530
   302
      in (freshs1 @ [term_of cx], freshs2 @ ths, ctxt') end;
berghofe@22530
   303
berghofe@22530
   304
    fun mk_proof thy thss =
berghofe@22530
   305
      let val ctxt = ProofContext.init thy
berghofe@22530
   306
      in Goal.prove_global thy [] prems' concl' (fn ihyps =>
berghofe@22530
   307
        let val th = Goal.prove ctxt [] [] concl (fn {context, ...} =>
berghofe@22530
   308
          rtac raw_induct 1 THEN
berghofe@22530
   309
          EVERY (maps (fn ((((_, bvars, oprems, _), vc_compat_ths), ihyp), (vs, ihypt)) =>
berghofe@22530
   310
            [REPEAT (rtac allI 1), simp_tac eqvt_ss 1,
berghofe@22530
   311
             SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} =>
berghofe@22530
   312
               let
berghofe@22530
   313
                 val (params', (pis, z)) =
berghofe@22530
   314
                   chop (length params - length atomTs - 1) (map term_of params) ||>
berghofe@22530
   315
                   split_last;
berghofe@22530
   316
                 val bvars' = map
berghofe@22530
   317
                   (fn (Bound i, T) => (nth params' (length params' - i), T)
berghofe@22530
   318
                     | (t, T) => (t, T)) bvars;
berghofe@22530
   319
                 val pi_bvars = map (fn (t, _) =>
berghofe@22530
   320
                   fold_rev (NominalPackage.mk_perm []) pis t) bvars';
berghofe@22530
   321
                 val (P, ts) = strip_comb (HOLogic.dest_Trueprop (term_of concl));
berghofe@22530
   322
                 val (freshs1, freshs2, ctxt'') = fold
berghofe@22530
   323
                   (obtain_fresh_name (ts @ pi_bvars))
berghofe@22530
   324
                   (map snd bvars') ([], [], ctxt');
berghofe@22530
   325
                 val freshs2' = NominalPackage.mk_not_sym freshs2;
berghofe@22530
   326
                 val pis' = map NominalPackage.perm_of_pair (pi_bvars ~~ freshs1);
berghofe@24570
   327
                 fun concat_perm pi1 pi2 =
berghofe@24570
   328
                   let val T = fastype_of pi1
berghofe@24570
   329
                   in if T = fastype_of pi2 then
berghofe@24570
   330
                       Const ("List.append", T --> T --> T) $ pi1 $ pi2
berghofe@24570
   331
                     else pi2
berghofe@24570
   332
                   end;
berghofe@24570
   333
                 val pis'' = fold (concat_perm #> map) pis' pis;
berghofe@22530
   334
                 val env = Pattern.first_order_match thy (ihypt, prop_of ihyp)
berghofe@22530
   335
                   (Vartab.empty, Vartab.empty);
berghofe@22530
   336
                 val ihyp' = Thm.instantiate ([], map (pairself (cterm_of thy))
berghofe@22530
   337
                   (map (Envir.subst_vars env) vs ~~
berghofe@22530
   338
                    map (fold_rev (NominalPackage.mk_perm [])
berghofe@22530
   339
                      (rev pis' @ pis)) params' @ [z])) ihyp;
berghofe@24570
   340
                 fun mk_pi th =
berghofe@24570
   341
                   Simplifier.simplify (HOL_basic_ss addsimps [id_apply]
berghofe@24570
   342
                       addsimprocs [NominalPackage.perm_simproc])
berghofe@24570
   343
                     (Simplifier.simplify eqvt_ss
berghofe@24570
   344
                       (fold_rev (fn pi => fn th' => th' RS Drule.cterm_instantiate
berghofe@24570
   345
                         [(perm_boolI_pi, cterm_of thy pi)] perm_boolI)
berghofe@24570
   346
                           (rev pis' @ pis) th));
berghofe@24570
   347
                 val (gprems1, gprems2) = split_list
berghofe@24570
   348
                   (map (fn (th, t) =>
berghofe@24570
   349
                      if null (term_frees t inter ps) then (SOME th, mk_pi th)
berghofe@24570
   350
                      else
berghofe@24570
   351
                        (map_thm ctxt (split_conj (K o I) names)
berghofe@24570
   352
                           (etac conjunct1 1) monos NONE th,
berghofe@24570
   353
                         mk_pi (the (map_thm ctxt (inst_conj_all names ps (rev pis''))
berghofe@24570
   354
                           (inst_conj_all_tac (length pis'')) monos (SOME t) th))))
berghofe@24570
   355
                      (gprems ~~ oprems)) |>> List.mapPartial I;
berghofe@22530
   356
                 val vc_compat_ths' = map (fn th =>
berghofe@22530
   357
                   let
berghofe@22530
   358
                     val th' = gprems1 MRS
wenzelm@22901
   359
                       Thm.instantiate (Thm.first_order_match
wenzelm@23531
   360
                         (Conjunction.mk_conjunction_balanced (cprems_of th),
wenzelm@23531
   361
                          Conjunction.mk_conjunction_balanced (map cprop_of gprems1))) th;
berghofe@22530
   362
                     val (bop, lhs, rhs) = (case concl_of th' of
berghofe@22530
   363
                         _ $ (fresh $ lhs $ rhs) =>
berghofe@22530
   364
                           (fn t => fn u => fresh $ t $ u, lhs, rhs)
berghofe@22530
   365
                       | _ $ (_ $ (_ $ lhs $ rhs)) =>
berghofe@22530
   366
                           (curry (HOLogic.mk_not o HOLogic.mk_eq), lhs, rhs));
berghofe@22530
   367
                     val th'' = Goal.prove ctxt'' [] [] (HOLogic.mk_Trueprop
berghofe@22530
   368
                         (bop (fold_rev (NominalPackage.mk_perm []) pis lhs)
berghofe@22530
   369
                            (fold_rev (NominalPackage.mk_perm []) pis rhs)))
berghofe@22530
   370
                       (fn _ => simp_tac (HOL_basic_ss addsimps
berghofe@22530
   371
                          (fresh_bij @ perm_bij)) 1 THEN rtac th' 1)
berghofe@22530
   372
                   in Simplifier.simplify (eqvt_ss addsimps fresh_atm) th'' end)
berghofe@22530
   373
                     vc_compat_ths;
berghofe@22530
   374
                 val vc_compat_ths'' = NominalPackage.mk_not_sym vc_compat_ths';
berghofe@22530
   375
                 (** Since calc_atm simplifies (pi :: 'a prm) o (x :: 'b) to x **)
berghofe@22530
   376
                 (** we have to pre-simplify the rewrite rules                 **)
berghofe@22530
   377
                 val calc_atm_ss = HOL_ss addsimps calc_atm @
berghofe@22530
   378
                    map (Simplifier.simplify (HOL_ss addsimps calc_atm))
berghofe@22530
   379
                      (vc_compat_ths'' @ freshs2');
berghofe@22530
   380
                 val th = Goal.prove ctxt'' [] []
berghofe@22530
   381
                   (HOLogic.mk_Trueprop (list_comb (P $ hd ts,
berghofe@22530
   382
                     map (fold (NominalPackage.mk_perm []) pis') (tl ts))))
berghofe@22530
   383
                   (fn _ => EVERY ([simp_tac eqvt_ss 1, rtac ihyp' 1,
berghofe@22530
   384
                     REPEAT_DETERM_N (nprems_of ihyp - length gprems)
berghofe@22530
   385
                       (simp_tac calc_atm_ss 1),
berghofe@22530
   386
                     REPEAT_DETERM_N (length gprems)
berghofe@24570
   387
                       (simp_tac (HOL_ss
berghofe@24570
   388
                          addsimps inductive_forall_def' :: gprems2
berghofe@22530
   389
                          addsimprocs [NominalPackage.perm_simproc]) 1)]));
berghofe@22530
   390
                 val final = Goal.prove ctxt'' [] [] (term_of concl)
berghofe@22530
   391
                   (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (HOL_ss
berghofe@22530
   392
                     addsimps vc_compat_ths'' @ freshs2' @
berghofe@22530
   393
                       perm_fresh_fresh @ fresh_atm) 1);
berghofe@22530
   394
                 val final' = ProofContext.export ctxt'' ctxt' [final];
berghofe@22530
   395
               in resolve_tac final' 1 end) context 1])
berghofe@22530
   396
                 (prems ~~ thss ~~ ihyps ~~ prems'')))
berghofe@22530
   397
        in
berghofe@22530
   398
          cut_facts_tac [th] 1 THEN REPEAT (etac conjE 1) THEN
berghofe@22530
   399
          REPEAT (REPEAT (resolve_tac [conjI, impI] 1) THEN
berghofe@22530
   400
            etac impE 1 THEN atac 1 THEN REPEAT (etac allE_Nil 1) THEN
berghofe@22530
   401
            asm_full_simp_tac (simpset_of thy) 1)
berghofe@22530
   402
        end)
berghofe@22530
   403
      end;
berghofe@22530
   404
berghofe@22530
   405
  in
berghofe@22530
   406
    thy |>
berghofe@22530
   407
    ProofContext.init |>
berghofe@22530
   408
    Proof.theorem_i NONE (fn thss => ProofContext.theory (fn thy =>
berghofe@22530
   409
      let
berghofe@22530
   410
        val ctxt = ProofContext.init thy;
berghofe@22530
   411
        val rec_name = space_implode "_" (map Sign.base_name names);
berghofe@22530
   412
        val ind_case_names = RuleCases.case_names induct_cases;
berghofe@24570
   413
        val strong_raw_induct =
berghofe@24570
   414
          mk_proof thy (map (map atomize_intr) thss) |>
berghofe@24570
   415
          rulify |> MetaSimplifier.norm_hhf;
berghofe@22530
   416
        val strong_induct =
berghofe@22530
   417
          if length names > 1 then
berghofe@22530
   418
            (strong_raw_induct, [ind_case_names, RuleCases.consumes 0])
berghofe@22530
   419
          else (strong_raw_induct RSN (2, rev_mp),
berghofe@22530
   420
            [ind_case_names, RuleCases.consumes 1]);
berghofe@22530
   421
        val ([strong_induct'], thy') = thy |>
berghofe@22530
   422
          Theory.add_path rec_name |>
berghofe@22530
   423
          PureThy.add_thms [(("strong_induct", #1 strong_induct), #2 strong_induct)];
berghofe@22530
   424
        val strong_inducts =
berghofe@22530
   425
          ProjectRule.projects ctxt (1 upto length names) strong_induct'
berghofe@22530
   426
      in
berghofe@22530
   427
        thy' |>
berghofe@22530
   428
        PureThy.add_thmss [(("strong_inducts", strong_inducts),
berghofe@22530
   429
          [ind_case_names, RuleCases.consumes 1])] |> snd |>
berghofe@22530
   430
        Theory.parent_path
berghofe@22530
   431
      end))
berghofe@24570
   432
      (map (map (rulify_term thy #> rpair [])) vc_compat)
berghofe@22530
   433
  end;
berghofe@22530
   434
berghofe@22730
   435
fun prove_eqvt s xatoms thy =
berghofe@22530
   436
  let
berghofe@22530
   437
    val ctxt = ProofContext.init thy;
berghofe@22788
   438
    val ({names, ...}, {raw_induct, intrs, elims, ...}) =
berghofe@22730
   439
      InductivePackage.the_inductive ctxt (Sign.intern_const thy s);
berghofe@24570
   440
    val raw_induct = atomize_induct raw_induct;
berghofe@24570
   441
    val elims = map atomize_induct elims;
berghofe@24570
   442
    val intrs = map atomize_intr intrs;
berghofe@24570
   443
    val monos = InductivePackage.get_monos ctxt;
berghofe@22788
   444
    val intrs' = InductivePackage.unpartition_rules intrs
berghofe@22788
   445
      (map (fn (((s, ths), (_, k)), th) =>
berghofe@22788
   446
           (s, ths ~~ InductivePackage.infer_intro_vars th k ths))
berghofe@22788
   447
         (InductivePackage.partition_rules raw_induct intrs ~~
berghofe@22788
   448
          InductivePackage.arities_of raw_induct ~~ elims));
berghofe@22730
   449
    val atoms' = NominalAtoms.atoms_of thy;
berghofe@22730
   450
    val atoms =
berghofe@22730
   451
      if null xatoms then atoms' else
berghofe@22730
   452
      let val atoms = map (Sign.intern_type thy) xatoms
berghofe@22730
   453
      in
berghofe@22730
   454
        (case duplicates op = atoms of
berghofe@22730
   455
             [] => ()
berghofe@22730
   456
           | xs => error ("Duplicate atoms: " ^ commas xs);
berghofe@22730
   457
         case atoms \\ atoms' of
berghofe@22730
   458
             [] => ()
berghofe@22730
   459
           | xs => error ("No such atoms: " ^ commas xs);
berghofe@22730
   460
         atoms)
berghofe@22730
   461
      end;
berghofe@24570
   462
    val perm_pi_simp = PureThy.get_thms thy (Name "perm_pi_simp");
berghofe@24570
   463
    val eqvt_ss = HOL_basic_ss addsimps
berghofe@24570
   464
      (NominalThmDecls.get_eqvt_thms thy @ perm_pi_simp) addsimprocs
berghofe@24570
   465
      [mk_perm_bool_simproc names];
berghofe@22313
   466
    val t = Logic.unvarify (concl_of raw_induct);
berghofe@22313
   467
    val pi = Name.variant (add_term_names (t, [])) "pi";
berghofe@22313
   468
    val ps = map (fst o HOLogic.dest_imp)
berghofe@22313
   469
      (HOLogic.dest_conj (HOLogic.dest_Trueprop t));
berghofe@22788
   470
    fun eqvt_tac th pi (intr, vs) st =
berghofe@22544
   471
      let
berghofe@22544
   472
        fun eqvt_err s = error
berghofe@22544
   473
          ("Could not prove equivariance for introduction rule\n" ^
berghofe@22544
   474
           Sign.string_of_term (theory_of_thm intr)
berghofe@22544
   475
             (Logic.unvarify (prop_of intr)) ^ "\n" ^ s);
berghofe@22788
   476
        val res = SUBPROOF (fn {prems, params, ...} =>
berghofe@22788
   477
          let
berghofe@24570
   478
            val prems' = map (fn th => the_default th (map_thm ctxt
berghofe@24570
   479
              (split_conj (K I) names) (etac conjunct2 1) monos NONE th)) prems;
berghofe@24570
   480
            val prems'' = map (fn th' =>
berghofe@24570
   481
              Simplifier.simplify eqvt_ss (th' RS th)) prems';
berghofe@22788
   482
            val intr' = Drule.cterm_instantiate (map (cterm_of thy) vs ~~
berghofe@22788
   483
               map (cterm_of thy o NominalPackage.mk_perm [] pi o term_of) params)
berghofe@22788
   484
               intr
berghofe@24570
   485
          in (rtac intr' THEN_ALL_NEW (TRY o resolve_tac prems'')) 1
berghofe@22544
   486
          end) ctxt 1 st
berghofe@22544
   487
      in
berghofe@22544
   488
        case (Seq.pull res handle THM (s, _, _) => eqvt_err s) of
berghofe@22544
   489
          NONE => eqvt_err ("Rule does not match goal\n" ^
berghofe@22544
   490
            Sign.string_of_term (theory_of_thm st) (hd (prems_of st)))
berghofe@22544
   491
        | SOME (th, _) => Seq.single th
berghofe@22544
   492
      end;
berghofe@22313
   493
    val thss = map (fn atom =>
berghofe@22313
   494
      let
berghofe@22313
   495
        val pi' = Free (pi, NominalAtoms.mk_permT (Type (atom, [])));
berghofe@22313
   496
        val perm_boolI' = Drule.cterm_instantiate
berghofe@22313
   497
          [(perm_boolI_pi, cterm_of thy pi')] perm_boolI
berghofe@22530
   498
      in map (fn th => zero_var_indexes (th RS mp))
berghofe@22313
   499
        (DatatypeAux.split_conj_thm (Goal.prove_global thy [] []
berghofe@22313
   500
          (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map (fn p =>
berghofe@22313
   501
            HOLogic.mk_imp (p, list_comb
berghofe@22313
   502
             (apsnd (map (NominalPackage.mk_perm [] pi')) (strip_comb p)))) ps)))
berghofe@22788
   503
          (fn _ => EVERY (rtac raw_induct 1 :: map (fn intr_vs =>
berghofe@22788
   504
              full_simp_tac eqvt_ss 1 THEN
berghofe@22788
   505
              eqvt_tac perm_boolI' pi' intr_vs) intrs'))))
berghofe@22544
   506
      end) atoms
berghofe@22544
   507
  in
berghofe@22544
   508
    fold (fn (name, ths) =>
berghofe@22544
   509
      Theory.add_path (Sign.base_name name) #>
berghofe@22544
   510
      PureThy.add_thmss [(("eqvt", ths), [NominalThmDecls.eqvt_add])] #> snd #>
berghofe@22544
   511
      Theory.parent_path) (names ~~ transp thss) thy
berghofe@22544
   512
  end;
berghofe@22313
   513
berghofe@22313
   514
berghofe@22313
   515
(* outer syntax *)
berghofe@22313
   516
berghofe@22313
   517
local structure P = OuterParse and K = OuterKeyword in
berghofe@22313
   518
berghofe@22313
   519
val nominal_inductiveP =
berghofe@22313
   520
  OuterSyntax.command "nominal_inductive"
berghofe@22530
   521
    "prove equivariance and strong induction theorem for inductive predicate involving nominal datatypes" K.thy_goal
berghofe@22530
   522
    (P.name -- Scan.optional (P.$$$ "avoids" |-- P.and_list1 (P.name --
berghofe@22530
   523
      (P.$$$ ":" |-- Scan.repeat1 P.name))) [] >> (fn (name, avoids) =>
berghofe@22730
   524
        Toplevel.print o Toplevel.theory_to_proof (prove_strong_ind name avoids)));
berghofe@22313
   525
berghofe@22530
   526
val equivarianceP =
berghofe@22530
   527
  OuterSyntax.command "equivariance"
berghofe@22530
   528
    "prove equivariance for inductive predicate involving nominal datatypes" K.thy_decl
berghofe@22730
   529
    (P.name -- Scan.optional (P.$$$ "[" |-- P.list1 P.name --| P.$$$ "]") [] >>
berghofe@22730
   530
      (fn (name, atoms) => Toplevel.theory (prove_eqvt name atoms)));
berghofe@22530
   531
berghofe@22530
   532
val _ = OuterSyntax.add_keywords ["avoids"];
berghofe@22530
   533
val _ = OuterSyntax.add_parsers [nominal_inductiveP, equivarianceP];
berghofe@22313
   534
berghofe@22313
   535
end;
berghofe@22313
   536
berghofe@22313
   537
end