src/HOL/BNF/Tools/bnf_comp.ML
author blanchet
Wed Sep 26 10:00:59 2012 +0200 (2012-09-26)
changeset 49586 d5e342ffe91e
parent 49585 5c4a12550491
child 49630 9f6ca87ab405
permissions -rw-r--r--
parameterized "subst_tac"
blanchet@49509
     1
(*  Title:      HOL/BNF/Tools/bnf_comp.ML
blanchet@48975
     2
    Author:     Dmitriy Traytel, TU Muenchen
blanchet@48975
     3
    Author:     Jasmin Blanchette, TU Muenchen
blanchet@48975
     4
    Copyright   2012
blanchet@48975
     5
blanchet@48975
     6
Composition of bounded natural functors.
blanchet@48975
     7
*)
blanchet@48975
     8
blanchet@48975
     9
signature BNF_COMP =
blanchet@48975
    10
sig
blanchet@49585
    11
  val ID_bnf: BNF_Def.BNF
blanchet@49585
    12
  val DEADID_bnf: BNF_Def.BNF
blanchet@49585
    13
blanchet@49502
    14
  type unfold_set
blanchet@49502
    15
  val empty_unfolds: unfold_set
blanchet@49502
    16
  val map_unfolds_of: unfold_set -> thm list
blanchet@49507
    17
  val rel_unfolds_of: unfold_set -> thm list
blanchet@49502
    18
  val set_unfoldss_of: unfold_set -> thm list list
blanchet@49506
    19
  val srel_unfolds_of: unfold_set -> thm list
blanchet@48975
    20
traytel@49425
    21
  val bnf_of_typ: BNF_Def.const_policy -> (binding -> binding) ->
blanchet@49502
    22
    ((string * sort) list list -> (string * sort) list) -> typ -> unfold_set * Proof.context ->
blanchet@49502
    23
    (BNF_Def.BNF * (typ list * typ list)) * (unfold_set * Proof.context)
blanchet@49014
    24
  val default_comp_sort: (string * sort) list list -> (string * sort) list
blanchet@48975
    25
  val normalize_bnfs: (int -> binding -> binding) -> ''a list list -> ''a list ->
blanchet@49502
    26
    (''a list list -> ''a list) -> BNF_Def.BNF list -> unfold_set -> Proof.context ->
blanchet@49502
    27
    (int list list * ''a list) * (BNF_Def.BNF list * (unfold_set * Proof.context))
blanchet@49502
    28
  val seal_bnf: unfold_set -> binding -> typ list -> BNF_Def.BNF -> Proof.context ->
traytel@49185
    29
    (BNF_Def.BNF * typ list) * local_theory
blanchet@48975
    30
end;
blanchet@48975
    31
blanchet@48975
    32
structure BNF_Comp : BNF_COMP =
blanchet@48975
    33
struct
blanchet@48975
    34
blanchet@48975
    35
open BNF_Def
blanchet@48975
    36
open BNF_Util
blanchet@48975
    37
open BNF_Tactics
blanchet@48975
    38
open BNF_Comp_Tactics
blanchet@48975
    39
blanchet@49585
    40
val ID_bnf = the (bnf_of @{context} "Basic_BNFs.ID");
blanchet@49585
    41
val DEADID_bnf = the (bnf_of @{context} "Basic_BNFs.DEADID");
blanchet@49585
    42
blanchet@49585
    43
(* TODO: Replace by "BNF_Defs.defs list" *)
blanchet@49502
    44
type unfold_set = {
blanchet@48975
    45
  map_unfolds: thm list,
blanchet@48975
    46
  set_unfoldss: thm list list,
blanchet@49507
    47
  rel_unfolds: thm list,
blanchet@49506
    48
  srel_unfolds: thm list
blanchet@48975
    49
};
blanchet@48975
    50
blanchet@49507
    51
val empty_unfolds = {map_unfolds = [], set_unfoldss = [], rel_unfolds = [], srel_unfolds = []};
blanchet@48975
    52
blanchet@49503
    53
fun add_to_thms thms new = thms |> not (Thm.is_reflexive new) ? insert Thm.eq_thm new;
blanchet@49503
    54
fun adds_to_thms thms news = insert (eq_set Thm.eq_thm) (no_reflexive news) thms;
blanchet@49503
    55
blanchet@49507
    56
fun add_to_unfolds map sets rel srel
blanchet@49507
    57
  {map_unfolds, set_unfoldss, rel_unfolds, srel_unfolds} =
blanchet@49503
    58
  {map_unfolds = add_to_thms map_unfolds map,
blanchet@49503
    59
    set_unfoldss = adds_to_thms set_unfoldss sets,
blanchet@49507
    60
    rel_unfolds = add_to_thms rel_unfolds rel,
blanchet@49506
    61
    srel_unfolds = add_to_thms srel_unfolds srel};
blanchet@48975
    62
blanchet@49503
    63
fun add_bnf_to_unfolds bnf =
blanchet@49507
    64
  add_to_unfolds (map_def_of_bnf bnf) (set_defs_of_bnf bnf) (rel_def_of_bnf bnf)
blanchet@49506
    65
    (srel_def_of_bnf bnf);
blanchet@48975
    66
blanchet@48975
    67
val map_unfolds_of = #map_unfolds;
blanchet@48975
    68
val set_unfoldss_of = #set_unfoldss;
blanchet@49507
    69
val rel_unfolds_of = #rel_unfolds;
blanchet@49506
    70
val srel_unfolds_of = #srel_unfolds;
blanchet@48975
    71
blanchet@48975
    72
val bdTN = "bdT";
blanchet@48975
    73
traytel@49425
    74
fun mk_killN n = "_kill" ^ string_of_int n;
traytel@49425
    75
fun mk_liftN n = "_lift" ^ string_of_int n;
blanchet@48975
    76
fun mk_permuteN src dest =
traytel@49425
    77
  "_permute_" ^ implode (map string_of_int src) ^ "_" ^ implode (map string_of_int dest);
blanchet@48975
    78
blanchet@48975
    79
(*copied from Envir.expand_term_free*)
blanchet@48975
    80
fun expand_term_const defs =
blanchet@48975
    81
  let
blanchet@48975
    82
    val eqs = map ((fn ((x, U), u) => (x, (U, u))) o apfst dest_Const) defs;
blanchet@48975
    83
    val get = fn Const (x, _) => AList.lookup (op =) eqs x | _ => NONE;
blanchet@48975
    84
  in Envir.expand_term get end;
blanchet@48975
    85
blanchet@49502
    86
fun clean_compose_bnf const_policy qualify b outer inners (unfold_set, lthy) =
blanchet@48975
    87
  let
blanchet@48975
    88
    val olive = live_of_bnf outer;
blanchet@48975
    89
    val onwits = nwits_of_bnf outer;
blanchet@48975
    90
    val odead = dead_of_bnf outer;
blanchet@48975
    91
    val inner = hd inners;
blanchet@48975
    92
    val ilive = live_of_bnf inner;
blanchet@48975
    93
    val ideads = map dead_of_bnf inners;
blanchet@48975
    94
    val inwitss = map nwits_of_bnf inners;
blanchet@48975
    95
blanchet@48975
    96
    (* TODO: check olive = length inners > 0,
blanchet@48975
    97
                   forall inner from inners. ilive = live,
blanchet@48975
    98
                   forall inner from inners. idead = dead  *)
blanchet@48975
    99
blanchet@48975
   100
    val (oDs, lthy1) = apfst (map TFree)
blanchet@48975
   101
      (Variable.invent_types (replicate odead HOLogic.typeS) lthy);
blanchet@48975
   102
    val (Dss, lthy2) = apfst (map (map TFree))
blanchet@48975
   103
        (fold_map Variable.invent_types (map (fn n => replicate n HOLogic.typeS) ideads) lthy1);
blanchet@48975
   104
    val (Ass, lthy3) = apfst (replicate ilive o map TFree)
blanchet@48975
   105
      (Variable.invent_types (replicate ilive HOLogic.typeS) lthy2);
blanchet@48975
   106
    val As = if ilive > 0 then hd Ass else [];
blanchet@48975
   107
    val Ass_repl = replicate olive As;
blanchet@48975
   108
    val (Bs, _(*lthy4*)) = apfst (map TFree)
blanchet@48975
   109
      (Variable.invent_types (replicate ilive HOLogic.typeS) lthy3);
blanchet@48975
   110
    val Bss_repl = replicate olive Bs;
blanchet@48975
   111
blanchet@49463
   112
    val ((((fs', Qs'), Asets), xs), _(*names_lthy*)) = lthy
blanchet@48975
   113
      |> apfst snd o mk_Frees' "f" (map2 (curry (op -->)) As Bs)
blanchet@49463
   114
      ||>> apfst snd o mk_Frees' "Q" (map2 mk_pred2T As Bs)
blanchet@49456
   115
      ||>> mk_Frees "A" (map HOLogic.mk_setT As)
blanchet@48975
   116
      ||>> mk_Frees "x" As;
blanchet@48975
   117
blanchet@48975
   118
    val CAs = map3 mk_T_of_bnf Dss Ass_repl inners;
blanchet@48975
   119
    val CCA = mk_T_of_bnf oDs CAs outer;
blanchet@48975
   120
    val CBs = map3 mk_T_of_bnf Dss Bss_repl inners;
blanchet@48975
   121
    val outer_sets = mk_sets_of_bnf (replicate olive oDs) (replicate olive CAs) outer;
blanchet@48975
   122
    val inner_setss = map3 mk_sets_of_bnf (map (replicate ilive) Dss) (replicate olive Ass) inners;
blanchet@48975
   123
    val inner_bds = map3 mk_bd_of_bnf Dss Ass_repl inners;
blanchet@48975
   124
    val outer_bd = mk_bd_of_bnf oDs CAs outer;
blanchet@48975
   125
blanchet@48975
   126
    (*%f1 ... fn. outer.map (inner_1.map f1 ... fn) ... (inner_m.map f1 ... fn)*)
blanchet@49303
   127
    val mapx = fold_rev Term.abs fs'
blanchet@48975
   128
      (Term.list_comb (mk_map_of_bnf oDs CAs CBs outer,
blanchet@49463
   129
        map2 (fn Ds => (fn f => Term.list_comb (f, map Bound (ilive - 1 downto 0))) o
blanchet@48975
   130
          mk_map_of_bnf Ds As Bs) Dss inners));
blanchet@49507
   131
    (*%Q1 ... Qn. outer.rel (inner_1.rel Q1 ... Qn) ... (inner_m.rel Q1 ... Qn)*)
blanchet@49507
   132
    val rel = fold_rev Term.abs Qs'
blanchet@49507
   133
      (Term.list_comb (mk_rel_of_bnf oDs CAs CBs outer,
blanchet@49463
   134
        map2 (fn Ds => (fn f => Term.list_comb (f, map Bound (ilive - 1 downto 0))) o
blanchet@49507
   135
          mk_rel_of_bnf Ds As Bs) Dss inners));
blanchet@48975
   136
blanchet@48975
   137
    (*Union o collect {outer.set_1 ... outer.set_m} o outer.map inner_1.set_i ... inner_m.set_i*)
blanchet@48975
   138
    (*Union o collect {image inner_1.set_i o outer.set_1 ... image inner_m.set_i o outer.set_m}*)
blanchet@49303
   139
    fun mk_set i =
blanchet@48975
   140
      let
blanchet@48975
   141
        val (setTs, T) = `(replicate olive o HOLogic.mk_setT) (nth As i);
blanchet@48975
   142
        val outer_set = mk_collect
blanchet@48975
   143
          (mk_sets_of_bnf (replicate olive oDs) (replicate olive setTs) outer)
blanchet@48975
   144
          (mk_T_of_bnf oDs setTs outer --> HOLogic.mk_setT T);
blanchet@48975
   145
        val inner_sets = map (fn sets => nth sets i) inner_setss;
blanchet@48975
   146
        val outer_map = mk_map_of_bnf oDs CAs setTs outer;
blanchet@48975
   147
        val map_inner_sets = Term.list_comb (outer_map, inner_sets);
blanchet@48975
   148
        val collect_image = mk_collect
blanchet@48975
   149
          (map2 (fn f => fn set => HOLogic.mk_comp (mk_image f, set)) inner_sets outer_sets)
blanchet@48975
   150
          (CCA --> HOLogic.mk_setT T);
blanchet@48975
   151
      in
blanchet@48975
   152
        (Library.foldl1 HOLogic.mk_comp [mk_Union T, outer_set, map_inner_sets],
blanchet@48975
   153
        HOLogic.mk_comp (mk_Union T, collect_image))
blanchet@48975
   154
      end;
blanchet@48975
   155
blanchet@49303
   156
    val (sets, sets_alt) = map_split mk_set (0 upto ilive - 1);
blanchet@48975
   157
blanchet@48975
   158
    (*(inner_1.bd +c ... +c inner_m.bd) *c outer.bd*)
blanchet@49303
   159
    val bd = Term.absdummy CCA (mk_cprod (Library.foldr1 (uncurry mk_csum) inner_bds) outer_bd);
blanchet@48975
   160
blanchet@49303
   161
    fun map_id_tac {context = ctxt, ...} =
blanchet@48975
   162
      let
blanchet@48975
   163
        (*order the theorems by reverse size to prevent bad interaction with nonconfluent rewrite
blanchet@48975
   164
          rules*)
blanchet@48975
   165
        val thms = (map map_id_of_bnf inners
blanchet@48975
   166
          |> map (`(Term.size_of_term o Thm.prop_of))
blanchet@48975
   167
          |> sort (rev_order o int_ord o pairself fst)
blanchet@48975
   168
          |> map snd) @ [map_id_of_bnf outer];
blanchet@48975
   169
      in
blanchet@49586
   170
        (EVERY' (map (fn thm => subst_tac ctxt NONE [thm]) thms) THEN' rtac refl) 1
blanchet@48975
   171
      end;
blanchet@48975
   172
blanchet@49303
   173
    fun map_comp_tac _ =
blanchet@48975
   174
      mk_comp_map_comp_tac (map_comp_of_bnf outer) (map_cong_of_bnf outer)
blanchet@48975
   175
        (map map_comp_of_bnf inners);
blanchet@48975
   176
blanchet@49303
   177
    fun mk_single_set_natural_tac i _ =
blanchet@48975
   178
      mk_comp_set_natural_tac (map_comp_of_bnf outer) (map_cong_of_bnf outer)
blanchet@48975
   179
        (collect_set_natural_of_bnf outer)
blanchet@48975
   180
        (map ((fn thms => nth thms i) o set_natural_of_bnf) inners);
blanchet@48975
   181
blanchet@49303
   182
    val set_natural_tacs = map mk_single_set_natural_tac (0 upto ilive - 1);
blanchet@48975
   183
blanchet@49303
   184
    fun bd_card_order_tac _ =
blanchet@48975
   185
      mk_comp_bd_card_order_tac (map bd_card_order_of_bnf inners) (bd_card_order_of_bnf outer);
blanchet@48975
   186
blanchet@49303
   187
    fun bd_cinfinite_tac _ =
blanchet@48975
   188
      mk_comp_bd_cinfinite_tac (bd_cinfinite_of_bnf inner) (bd_cinfinite_of_bnf outer);
blanchet@48975
   189
blanchet@49303
   190
    val set_alt_thms =
blanchet@48975
   191
      if ! quick_and_dirty then
blanchet@49456
   192
        []
blanchet@48975
   193
      else
traytel@49109
   194
        map (fn goal =>
traytel@49109
   195
          Skip_Proof.prove lthy [] [] goal
traytel@49109
   196
            (fn {context, ...} => (mk_comp_set_alt_tac context (collect_set_natural_of_bnf outer)))
traytel@49109
   197
          |> Thm.close_derivation)
blanchet@49303
   198
        (map2 (curry (HOLogic.mk_Trueprop o HOLogic.mk_eq)) sets sets_alt);
blanchet@48975
   199
blanchet@49303
   200
    fun map_cong_tac _ =
blanchet@49303
   201
      mk_comp_map_cong_tac set_alt_thms (map_cong_of_bnf outer) (map map_cong_of_bnf inners);
blanchet@48975
   202
blanchet@49303
   203
    val set_bd_tacs =
blanchet@48975
   204
      if ! quick_and_dirty then
blanchet@49303
   205
        replicate (length set_alt_thms) (K all_tac)
blanchet@48975
   206
      else
blanchet@48975
   207
        let
blanchet@48975
   208
          val outer_set_bds = set_bd_of_bnf outer;
blanchet@48975
   209
          val inner_set_bdss = map set_bd_of_bnf inners;
blanchet@48975
   210
          val inner_bd_Card_orders = map bd_Card_order_of_bnf inners;
blanchet@49303
   211
          fun single_set_bd_thm i j =
blanchet@48975
   212
            @{thm comp_single_set_bd} OF [nth inner_bd_Card_orders j, nth (nth inner_set_bdss j) i,
blanchet@48975
   213
              nth outer_set_bds j]
blanchet@48975
   214
          val single_set_bd_thmss =
blanchet@49303
   215
            map ((fn f => map f (0 upto olive - 1)) o single_set_bd_thm) (0 upto ilive - 1);
blanchet@48975
   216
        in
blanchet@49303
   217
          map2 (fn set_alt => fn single_set_bds => fn {context, ...} =>
blanchet@49303
   218
            mk_comp_set_bd_tac context set_alt single_set_bds)
blanchet@49303
   219
          set_alt_thms single_set_bd_thmss
blanchet@48975
   220
        end;
blanchet@48975
   221
blanchet@49303
   222
    val in_alt_thm =
traytel@49155
   223
      let
blanchet@49303
   224
        val inx = mk_in Asets sets CCA;
blanchet@49303
   225
        val in_alt = mk_in (map2 (mk_in Asets) inner_setss CAs) outer_sets CCA;
blanchet@49303
   226
        val goal = fold_rev Logic.all Asets (mk_Trueprop_eq (inx, in_alt));
traytel@49155
   227
      in
traytel@49155
   228
        Skip_Proof.prove lthy [] [] goal
blanchet@49303
   229
          (fn {context, ...} => mk_comp_in_alt_tac context set_alt_thms)
traytel@49155
   230
        |> Thm.close_derivation
traytel@49155
   231
      end;
blanchet@48975
   232
blanchet@49303
   233
    fun in_bd_tac _ =
blanchet@49303
   234
      mk_comp_in_bd_tac in_alt_thm (map in_bd_of_bnf inners) (in_bd_of_bnf outer)
blanchet@48975
   235
        (map bd_Cinfinite_of_bnf inners) (bd_Card_order_of_bnf outer);
blanchet@48975
   236
blanchet@49303
   237
    fun map_wpull_tac _ =
blanchet@49303
   238
      mk_map_wpull_tac in_alt_thm (map map_wpull_of_bnf inners) (map_wpull_of_bnf outer);
blanchet@48975
   239
blanchet@49506
   240
    fun srel_O_Gr_tac _ =
blanchet@49456
   241
      let
blanchet@49463
   242
        val basic_thms = @{thms mem_Collect_eq fst_conv snd_conv}; (*TODO: tune*)
blanchet@49506
   243
        val outer_srel_Gr = srel_Gr_of_bnf outer RS sym;
blanchet@49506
   244
        val outer_srel_cong = srel_cong_of_bnf outer;
blanchet@49463
   245
        val thm =
blanchet@49512
   246
          (trans OF [in_alt_thm RS @{thm O_Gr_cong},
blanchet@49463
   247
             trans OF [@{thm arg_cong2[of _ _ _ _ relcomp]} OF
blanchet@49506
   248
               [trans OF [outer_srel_Gr RS @{thm arg_cong[of _ _ converse]},
blanchet@49506
   249
                 srel_converse_of_bnf outer RS sym], outer_srel_Gr],
blanchet@49506
   250
               trans OF [srel_O_of_bnf outer RS sym, outer_srel_cong OF
blanchet@49506
   251
                 (map (fn bnf => srel_O_Gr_of_bnf bnf RS sym) inners)]]] RS sym)
blanchet@49506
   252
          |> unfold_thms lthy (basic_thms @ srel_def_of_bnf outer :: map srel_def_of_bnf inners);
blanchet@49456
   253
      in
blanchet@49504
   254
        unfold_thms_tac lthy basic_thms THEN rtac thm 1
blanchet@49463
   255
      end;
blanchet@49456
   256
blanchet@49460
   257
    val tacs = zip_axioms map_id_tac map_comp_tac map_cong_tac set_natural_tacs bd_card_order_tac
blanchet@49506
   258
      bd_cinfinite_tac set_bd_tacs in_bd_tac map_wpull_tac srel_O_Gr_tac;
blanchet@48975
   259
blanchet@48975
   260
    val outer_wits = mk_wits_of_bnf (replicate onwits oDs) (replicate onwits CAs) outer;
blanchet@48975
   261
blanchet@48975
   262
    val inner_witss = map (map (fn (I, wit) => Term.list_comb (wit, map (nth xs) I)))
blanchet@48975
   263
      (map3 (fn Ds => fn n => mk_wits_of_bnf (replicate n Ds) (replicate n As))
blanchet@48975
   264
        Dss inwitss inners);
blanchet@48975
   265
blanchet@48975
   266
    val inner_witsss = map (map (nth inner_witss) o fst) outer_wits;
blanchet@48975
   267
blanchet@49303
   268
    val wits = (inner_witsss, (map (single o snd) outer_wits))
blanchet@48975
   269
      |-> map2 (fold (map_product (fn iwit => fn owit => owit $ iwit)))
blanchet@48975
   270
      |> flat
blanchet@48975
   271
      |> map (`(fn t => Term.add_frees t []))
blanchet@48975
   272
      |> minimize_wits
blanchet@48975
   273
      |> map (fn (frees, t) => fold absfree frees t);
blanchet@48975
   274
blanchet@48975
   275
    fun wit_tac {context = ctxt, ...} =
blanchet@48975
   276
      mk_comp_wit_tac ctxt (wit_thms_of_bnf outer) (collect_set_natural_of_bnf outer)
blanchet@48975
   277
        (maps wit_thms_of_bnf inners);
blanchet@48975
   278
blanchet@48975
   279
    val (bnf', lthy') =
blanchet@49538
   280
      bnf_def const_policy (K Dont_Note) qualify tacs wit_tac (SOME (oDs @ flat Dss))
blanchet@49507
   281
        (((((b, mapx), sets), bd), wits), SOME rel) lthy;
blanchet@48975
   282
  in
blanchet@49503
   283
    (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
blanchet@48975
   284
  end;
blanchet@48975
   285
blanchet@48975
   286
(* Killing live variables *)
blanchet@48975
   287
blanchet@49502
   288
fun kill_bnf qualify n bnf (unfold_set, lthy) = if n = 0 then (bnf, (unfold_set, lthy)) else
blanchet@48975
   289
  let
traytel@49425
   290
    val b = Binding.suffix_name (mk_killN n) (name_of_bnf bnf);
blanchet@48975
   291
    val live = live_of_bnf bnf;
blanchet@48975
   292
    val dead = dead_of_bnf bnf;
blanchet@48975
   293
    val nwits = nwits_of_bnf bnf;
blanchet@48975
   294
blanchet@48975
   295
    (* TODO: check 0 < n <= live *)
blanchet@48975
   296
blanchet@48975
   297
    val (Ds, lthy1) = apfst (map TFree)
blanchet@48975
   298
      (Variable.invent_types (replicate dead HOLogic.typeS) lthy);
blanchet@48975
   299
    val ((killedAs, As), lthy2) = apfst (`(take n) o map TFree)
blanchet@48975
   300
      (Variable.invent_types (replicate live HOLogic.typeS) lthy1);
blanchet@48975
   301
    val (Bs, _(*lthy3*)) = apfst (append killedAs o map TFree)
blanchet@48975
   302
      (Variable.invent_types (replicate (live - n) HOLogic.typeS) lthy2);
blanchet@48975
   303
blanchet@48975
   304
    val ((Asets, lives), _(*names_lthy*)) = lthy
blanchet@49456
   305
      |> mk_Frees "A" (map HOLogic.mk_setT (drop n As))
blanchet@48975
   306
      ||>> mk_Frees "x" (drop n As);
blanchet@48975
   307
    val xs = map (fn T => HOLogic.choice_const T $ absdummy T @{term True}) killedAs @ lives;
blanchet@48975
   308
blanchet@48975
   309
    val T = mk_T_of_bnf Ds As bnf;
blanchet@48975
   310
blanchet@48975
   311
    (*bnf.map id ... id*)
blanchet@49303
   312
    val mapx = Term.list_comb (mk_map_of_bnf Ds As Bs bnf, map HOLogic.id_const killedAs);
blanchet@49507
   313
    (*bnf.rel (op =) ... (op =)*)
blanchet@49507
   314
    val rel = Term.list_comb (mk_rel_of_bnf Ds As Bs bnf, map HOLogic.eq_const killedAs);
blanchet@48975
   315
blanchet@48975
   316
    val bnf_sets = mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf;
blanchet@49303
   317
    val sets = drop n bnf_sets;
blanchet@48975
   318
blanchet@48975
   319
    (*(|UNIV :: A1 set| +c ... +c |UNIV :: An set|) *c bnf.bd*)
blanchet@48975
   320
    val bnf_bd = mk_bd_of_bnf Ds As bnf;
blanchet@49303
   321
    val bd = mk_cprod
blanchet@48975
   322
      (Library.foldr1 (uncurry mk_csum) (map (mk_card_of o HOLogic.mk_UNIV) killedAs)) bnf_bd;
blanchet@48975
   323
blanchet@49303
   324
    fun map_id_tac _ = rtac (map_id_of_bnf bnf) 1;
blanchet@49303
   325
    fun map_comp_tac {context, ...} =
blanchet@49504
   326
      unfold_thms_tac context ((map_comp_of_bnf bnf RS sym) :: @{thms o_assoc id_o o_id}) THEN
blanchet@48975
   327
      rtac refl 1;
blanchet@49303
   328
    fun map_cong_tac {context, ...} =
blanchet@49304
   329
      mk_kill_map_cong_tac context n (live - n) (map_cong_of_bnf bnf);
blanchet@49303
   330
    val set_natural_tacs = map (fn thm => fn _ => rtac thm 1) (drop n (set_natural_of_bnf bnf));
blanchet@49304
   331
    fun bd_card_order_tac _ = mk_kill_bd_card_order_tac n (bd_card_order_of_bnf bnf);
blanchet@49304
   332
    fun bd_cinfinite_tac _ = mk_kill_bd_cinfinite_tac (bd_Cinfinite_of_bnf bnf);
blanchet@49303
   333
    val set_bd_tacs =
blanchet@49304
   334
      map (fn thm => fn _ => mk_kill_set_bd_tac (bd_Card_order_of_bnf bnf) thm)
blanchet@48975
   335
        (drop n (set_bd_of_bnf bnf));
blanchet@48975
   336
blanchet@49303
   337
    val in_alt_thm =
traytel@49155
   338
      let
blanchet@49303
   339
        val inx = mk_in Asets sets T;
blanchet@49303
   340
        val in_alt = mk_in (map HOLogic.mk_UNIV killedAs @ Asets) bnf_sets T;
blanchet@49303
   341
        val goal = fold_rev Logic.all Asets (mk_Trueprop_eq (inx, in_alt));
traytel@49155
   342
      in
blanchet@49304
   343
        Skip_Proof.prove lthy [] [] goal (K kill_in_alt_tac) |> Thm.close_derivation
traytel@49155
   344
      end;
blanchet@48975
   345
blanchet@49303
   346
    fun in_bd_tac _ =
blanchet@49304
   347
      mk_kill_in_bd_tac n (live > n) in_alt_thm (in_bd_of_bnf bnf) (bd_Card_order_of_bnf bnf)
blanchet@49303
   348
        (bd_Cinfinite_of_bnf bnf) (bd_Cnotzero_of_bnf bnf);
blanchet@49303
   349
    fun map_wpull_tac _ = mk_map_wpull_tac in_alt_thm [] (map_wpull_of_bnf bnf);
blanchet@48975
   350
blanchet@49506
   351
    fun srel_O_Gr_tac _ =
blanchet@49456
   352
      let
blanchet@49506
   353
        val srel_Gr = srel_Gr_of_bnf bnf RS sym
blanchet@49463
   354
        val thm =
blanchet@49512
   355
          (trans OF [in_alt_thm RS @{thm O_Gr_cong},
blanchet@49463
   356
            trans OF [@{thm arg_cong2[of _ _ _ _ relcomp]} OF
blanchet@49506
   357
              [trans OF [srel_Gr RS @{thm arg_cong[of _ _ converse]},
blanchet@49506
   358
                srel_converse_of_bnf bnf RS sym], srel_Gr],
blanchet@49506
   359
              trans OF [srel_O_of_bnf bnf RS sym, srel_cong_of_bnf bnf OF
blanchet@49463
   360
                (replicate n @{thm trans[OF Gr_UNIV_id[OF refl] Id_alt[symmetric]]} @
blanchet@49463
   361
                 replicate (live - n) @{thm Gr_fst_snd})]]] RS sym)
blanchet@49506
   362
          |> unfold_thms lthy (srel_def_of_bnf bnf :: @{thms Id_def' mem_Collect_eq split_conv});
blanchet@49456
   363
      in
blanchet@49463
   364
        rtac thm 1
blanchet@49456
   365
      end;
blanchet@49456
   366
blanchet@49460
   367
    val tacs = zip_axioms map_id_tac map_comp_tac map_cong_tac set_natural_tacs bd_card_order_tac
blanchet@49506
   368
      bd_cinfinite_tac set_bd_tacs in_bd_tac map_wpull_tac srel_O_Gr_tac;
blanchet@48975
   369
blanchet@49303
   370
    val bnf_wits = mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf;
blanchet@48975
   371
blanchet@49303
   372
    val wits = map (fn t => fold absfree (Term.add_frees t []) t)
blanchet@49303
   373
      (map (fn (I, wit) => Term.list_comb (wit, map (nth xs) I)) bnf_wits);
blanchet@48975
   374
blanchet@48975
   375
    fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf);
blanchet@48975
   376
blanchet@48975
   377
    val (bnf', lthy') =
blanchet@49538
   378
      bnf_def Smart_Inline (K Dont_Note) qualify tacs wit_tac (SOME (killedAs @ Ds))
blanchet@49507
   379
        (((((b, mapx), sets), Term.absdummy T bd), wits), SOME rel) lthy;
blanchet@48975
   380
  in
blanchet@49503
   381
    (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
blanchet@48975
   382
  end;
blanchet@48975
   383
blanchet@48975
   384
(* Adding dummy live variables *)
blanchet@48975
   385
blanchet@49502
   386
fun lift_bnf qualify n bnf (unfold_set, lthy) = if n = 0 then (bnf, (unfold_set, lthy)) else
blanchet@48975
   387
  let
traytel@49425
   388
    val b = Binding.suffix_name (mk_liftN n) (name_of_bnf bnf);
blanchet@48975
   389
    val live = live_of_bnf bnf;
blanchet@48975
   390
    val dead = dead_of_bnf bnf;
blanchet@48975
   391
    val nwits = nwits_of_bnf bnf;
blanchet@48975
   392
blanchet@48975
   393
    (* TODO: check 0 < n *)
blanchet@48975
   394
blanchet@48975
   395
    val (Ds, lthy1) = apfst (map TFree)
blanchet@48975
   396
      (Variable.invent_types (replicate dead HOLogic.typeS) lthy);
blanchet@48975
   397
    val ((newAs, As), lthy2) = apfst (chop n o map TFree)
blanchet@48975
   398
      (Variable.invent_types (replicate (n + live) HOLogic.typeS) lthy1);
blanchet@48975
   399
    val ((newBs, Bs), _(*lthy3*)) = apfst (chop n o map TFree)
blanchet@48975
   400
      (Variable.invent_types (replicate (n + live) HOLogic.typeS) lthy2);
blanchet@48975
   401
blanchet@48975
   402
    val (Asets, _(*names_lthy*)) = lthy
blanchet@49456
   403
      |> mk_Frees "A" (map HOLogic.mk_setT (newAs @ As));
blanchet@48975
   404
blanchet@48975
   405
    val T = mk_T_of_bnf Ds As bnf;
blanchet@48975
   406
blanchet@48975
   407
    (*%f1 ... fn. bnf.map*)
blanchet@49303
   408
    val mapx =
blanchet@48975
   409
      fold_rev Term.absdummy (map2 (curry (op -->)) newAs newBs) (mk_map_of_bnf Ds As Bs bnf);
blanchet@49507
   410
    (*%Q1 ... Qn. bnf.rel*)
blanchet@49507
   411
    val rel = fold_rev Term.absdummy (map2 mk_pred2T newAs newBs) (mk_rel_of_bnf Ds As Bs bnf);
blanchet@48975
   412
blanchet@48975
   413
    val bnf_sets = mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf;
blanchet@49303
   414
    val sets = map (fn A => absdummy T (HOLogic.mk_set A [])) newAs @ bnf_sets;
blanchet@48975
   415
blanchet@49303
   416
    val bd = mk_bd_of_bnf Ds As bnf;
blanchet@48975
   417
blanchet@49303
   418
    fun map_id_tac _ = rtac (map_id_of_bnf bnf) 1;
blanchet@49303
   419
    fun map_comp_tac {context, ...} =
blanchet@49504
   420
      unfold_thms_tac context ((map_comp_of_bnf bnf RS sym) :: @{thms o_assoc id_o o_id}) THEN
blanchet@48975
   421
      rtac refl 1;
blanchet@49303
   422
    fun map_cong_tac {context, ...} =
blanchet@48975
   423
      rtac (map_cong_of_bnf bnf) 1 THEN REPEAT_DETERM_N live (Goal.assume_rule_tac context 1);
blanchet@49303
   424
    val set_natural_tacs =
blanchet@48975
   425
      if ! quick_and_dirty then
blanchet@48975
   426
        replicate (n + live) (K all_tac)
blanchet@48975
   427
      else
blanchet@48975
   428
        replicate n (K empty_natural_tac) @
blanchet@48975
   429
        map (fn thm => fn _ => rtac thm 1) (set_natural_of_bnf bnf);
blanchet@49303
   430
    fun bd_card_order_tac _ = rtac (bd_card_order_of_bnf bnf) 1;
blanchet@49303
   431
    fun bd_cinfinite_tac _ = rtac (bd_cinfinite_of_bnf bnf) 1;
blanchet@49303
   432
    val set_bd_tacs =
blanchet@48975
   433
      if ! quick_and_dirty then
blanchet@48975
   434
        replicate (n + live) (K all_tac)
blanchet@48975
   435
      else
blanchet@49304
   436
        replicate n (K (mk_lift_set_bd_tac (bd_Card_order_of_bnf bnf))) @
blanchet@48975
   437
        (map (fn thm => fn _ => rtac thm 1) (set_bd_of_bnf bnf));
blanchet@48975
   438
blanchet@49303
   439
    val in_alt_thm =
traytel@49155
   440
      let
blanchet@49303
   441
        val inx = mk_in Asets sets T;
blanchet@49303
   442
        val in_alt = mk_in (drop n Asets) bnf_sets T;
blanchet@49303
   443
        val goal = fold_rev Logic.all Asets (mk_Trueprop_eq (inx, in_alt));
traytel@49155
   444
      in
blanchet@49304
   445
        Skip_Proof.prove lthy [] [] goal (K lift_in_alt_tac) |> Thm.close_derivation
traytel@49155
   446
      end;
blanchet@48975
   447
blanchet@49304
   448
    fun in_bd_tac _ = mk_lift_in_bd_tac n in_alt_thm (in_bd_of_bnf bnf) (bd_Card_order_of_bnf bnf);
blanchet@49303
   449
    fun map_wpull_tac _ = mk_map_wpull_tac in_alt_thm [] (map_wpull_of_bnf bnf);
blanchet@48975
   450
blanchet@49506
   451
    fun srel_O_Gr_tac _ =
blanchet@49506
   452
      mk_simple_srel_O_Gr_tac lthy (srel_def_of_bnf bnf) (srel_O_Gr_of_bnf bnf) in_alt_thm;
blanchet@49456
   453
blanchet@49460
   454
    val tacs = zip_axioms map_id_tac map_comp_tac map_cong_tac set_natural_tacs bd_card_order_tac
blanchet@49506
   455
      bd_cinfinite_tac set_bd_tacs in_bd_tac map_wpull_tac srel_O_Gr_tac;
blanchet@48975
   456
blanchet@49303
   457
    val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf);
blanchet@48975
   458
blanchet@48975
   459
    fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf);
blanchet@48975
   460
blanchet@48975
   461
    val (bnf', lthy') =
blanchet@49538
   462
      bnf_def Smart_Inline (K Dont_Note) qualify tacs wit_tac (SOME Ds)
blanchet@49507
   463
        (((((b, mapx), sets), Term.absdummy T bd), wits), SOME rel) lthy;
blanchet@48975
   464
blanchet@48975
   465
  in
blanchet@49503
   466
    (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
blanchet@48975
   467
  end;
blanchet@48975
   468
blanchet@48975
   469
(* Changing the order of live variables *)
blanchet@48975
   470
blanchet@49502
   471
fun permute_bnf qualify src dest bnf (unfold_set, lthy) =
blanchet@49502
   472
  if src = dest then (bnf, (unfold_set, lthy)) else
blanchet@48975
   473
  let
traytel@49425
   474
    val b = Binding.suffix_name (mk_permuteN src dest) (name_of_bnf bnf);
blanchet@48975
   475
    val live = live_of_bnf bnf;
blanchet@48975
   476
    val dead = dead_of_bnf bnf;
blanchet@48975
   477
    val nwits = nwits_of_bnf bnf;
blanchet@48975
   478
    fun permute xs = mk_permute src dest xs;
blanchet@48975
   479
    fun permute_rev xs = mk_permute dest src xs;
blanchet@48975
   480
blanchet@48975
   481
    val (Ds, lthy1) = apfst (map TFree)
blanchet@48975
   482
      (Variable.invent_types (replicate dead HOLogic.typeS) lthy);
blanchet@48975
   483
    val (As, lthy2) = apfst (map TFree)
blanchet@48975
   484
      (Variable.invent_types (replicate live HOLogic.typeS) lthy1);
blanchet@48975
   485
    val (Bs, _(*lthy3*)) = apfst (map TFree)
blanchet@48975
   486
      (Variable.invent_types (replicate live HOLogic.typeS) lthy2);
blanchet@48975
   487
blanchet@48975
   488
    val (Asets, _(*names_lthy*)) = lthy
blanchet@49456
   489
      |> mk_Frees "A" (map HOLogic.mk_setT (permute As));
blanchet@48975
   490
blanchet@48975
   491
    val T = mk_T_of_bnf Ds As bnf;
blanchet@48975
   492
blanchet@48975
   493
    (*%f(1) ... f(n). bnf.map f\<sigma>(1) ... f\<sigma>(n)*)
blanchet@49303
   494
    val mapx = fold_rev Term.absdummy (permute (map2 (curry op -->) As Bs))
blanchet@49463
   495
      (Term.list_comb (mk_map_of_bnf Ds As Bs bnf, permute_rev (map Bound (live - 1 downto 0))));
blanchet@49507
   496
    (*%Q(1) ... Q(n). bnf.rel Q\<sigma>(1) ... Q\<sigma>(n)*)
blanchet@49507
   497
    val rel = fold_rev Term.absdummy (permute (map2 mk_pred2T As Bs))
blanchet@49507
   498
      (Term.list_comb (mk_rel_of_bnf Ds As Bs bnf, permute_rev (map Bound (live - 1 downto 0))));
blanchet@48975
   499
blanchet@48975
   500
    val bnf_sets = mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf;
blanchet@49303
   501
    val sets = permute bnf_sets;
blanchet@48975
   502
blanchet@49303
   503
    val bd = mk_bd_of_bnf Ds As bnf;
blanchet@48975
   504
blanchet@49303
   505
    fun map_id_tac _ = rtac (map_id_of_bnf bnf) 1;
blanchet@49303
   506
    fun map_comp_tac _ = rtac (map_comp_of_bnf bnf) 1;
blanchet@49303
   507
    fun map_cong_tac {context, ...} =
blanchet@48975
   508
      rtac (map_cong_of_bnf bnf) 1 THEN REPEAT_DETERM_N live (Goal.assume_rule_tac context 1);
blanchet@49303
   509
    val set_natural_tacs = permute (map (fn thm => fn _ => rtac thm 1) (set_natural_of_bnf bnf));
blanchet@49303
   510
    fun bd_card_order_tac _ = rtac (bd_card_order_of_bnf bnf) 1;
blanchet@49303
   511
    fun bd_cinfinite_tac _ = rtac (bd_cinfinite_of_bnf bnf) 1;
blanchet@49303
   512
    val set_bd_tacs = permute (map (fn thm => fn _ => rtac thm 1) (set_bd_of_bnf bnf));
blanchet@48975
   513
blanchet@49303
   514
    val in_alt_thm =
traytel@49155
   515
      let
blanchet@49303
   516
        val inx = mk_in Asets sets T;
blanchet@49303
   517
        val in_alt = mk_in (permute_rev Asets) bnf_sets T;
blanchet@49303
   518
        val goal = fold_rev Logic.all Asets (mk_Trueprop_eq (inx, in_alt));
traytel@49155
   519
      in
traytel@49155
   520
        Skip_Proof.prove lthy [] [] goal (K (mk_permute_in_alt_tac src dest))
traytel@49155
   521
        |> Thm.close_derivation
traytel@49155
   522
      end;
blanchet@48975
   523
blanchet@49303
   524
    fun in_bd_tac _ =
blanchet@49303
   525
      mk_permute_in_bd_tac src dest in_alt_thm (in_bd_of_bnf bnf) (bd_Card_order_of_bnf bnf);
blanchet@49303
   526
    fun map_wpull_tac _ = mk_map_wpull_tac in_alt_thm [] (map_wpull_of_bnf bnf);
blanchet@48975
   527
blanchet@49506
   528
    fun srel_O_Gr_tac _ =
blanchet@49506
   529
      mk_simple_srel_O_Gr_tac lthy (srel_def_of_bnf bnf) (srel_O_Gr_of_bnf bnf) in_alt_thm;
blanchet@49456
   530
blanchet@49460
   531
    val tacs = zip_axioms map_id_tac map_comp_tac map_cong_tac set_natural_tacs bd_card_order_tac
blanchet@49506
   532
      bd_cinfinite_tac set_bd_tacs in_bd_tac map_wpull_tac srel_O_Gr_tac;
blanchet@48975
   533
blanchet@49303
   534
    val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf);
blanchet@48975
   535
blanchet@48975
   536
    fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf);
blanchet@48975
   537
blanchet@48975
   538
    val (bnf', lthy') =
blanchet@49538
   539
      bnf_def Smart_Inline (K Dont_Note) qualify tacs wit_tac (SOME Ds)
blanchet@49507
   540
        (((((b, mapx), sets), Term.absdummy T bd), wits), SOME rel) lthy;
blanchet@48975
   541
  in
blanchet@49503
   542
    (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
blanchet@48975
   543
  end;
blanchet@48975
   544
blanchet@49014
   545
(* Composition pipeline *)
blanchet@49014
   546
blanchet@49014
   547
fun permute_and_kill qualify n src dest bnf =
blanchet@49014
   548
  bnf
blanchet@49014
   549
  |> permute_bnf qualify src dest
blanchet@49304
   550
  #> uncurry (kill_bnf qualify n);
blanchet@49014
   551
blanchet@49014
   552
fun lift_and_permute qualify n src dest bnf =
blanchet@49014
   553
  bnf
blanchet@49304
   554
  |> lift_bnf qualify n
blanchet@49014
   555
  #> uncurry (permute_bnf qualify src dest);
blanchet@49014
   556
blanchet@49502
   557
fun normalize_bnfs qualify Ass Ds sort bnfs unfold_set lthy =
blanchet@49014
   558
  let
blanchet@49014
   559
    val before_kill_src = map (fn As => 0 upto (length As - 1)) Ass;
blanchet@49014
   560
    val kill_poss = map (find_indices Ds) Ass;
blanchet@49014
   561
    val live_poss = map2 (subtract (op =)) kill_poss before_kill_src;
blanchet@49014
   562
    val before_kill_dest = map2 append kill_poss live_poss;
blanchet@49014
   563
    val kill_ns = map length kill_poss;
blanchet@49502
   564
    val (inners', (unfold_set', lthy')) =
blanchet@49014
   565
      fold_map5 (fn i => permute_and_kill (qualify i))
blanchet@49014
   566
        (if length bnfs = 1 then [0] else (1 upto length bnfs))
blanchet@49502
   567
        kill_ns before_kill_src before_kill_dest bnfs (unfold_set, lthy);
blanchet@49014
   568
blanchet@49014
   569
    val Ass' = map2 (map o nth) Ass live_poss;
blanchet@49014
   570
    val As = sort Ass';
blanchet@49014
   571
    val after_lift_dest = replicate (length Ass') (0 upto (length As - 1));
blanchet@49014
   572
    val old_poss = map (map (fn x => find_index (fn y => x = y) As)) Ass';
blanchet@49014
   573
    val new_poss = map2 (subtract (op =)) old_poss after_lift_dest;
blanchet@49014
   574
    val after_lift_src = map2 append new_poss old_poss;
blanchet@49014
   575
    val lift_ns = map (fn xs => length As - length xs) Ass';
blanchet@49014
   576
  in
blanchet@49014
   577
    ((kill_poss, As), fold_map5 (fn i => lift_and_permute (qualify i))
blanchet@49014
   578
      (if length bnfs = 1 then [0] else (1 upto length bnfs))
blanchet@49502
   579
      lift_ns after_lift_src after_lift_dest inners' (unfold_set', lthy'))
blanchet@49014
   580
  end;
blanchet@49014
   581
blanchet@49014
   582
fun default_comp_sort Ass =
blanchet@49014
   583
  Library.sort (Term_Ord.typ_ord o pairself TFree) (fold (fold (insert (op =))) Ass []);
blanchet@49014
   584
blanchet@49502
   585
fun compose_bnf const_policy qualify sort outer inners oDs Dss tfreess (unfold_set, lthy) =
blanchet@49014
   586
  let
traytel@49425
   587
    val b = name_of_bnf outer;
blanchet@49014
   588
blanchet@49121
   589
    val Ass = map (map Term.dest_TFree) tfreess;
blanchet@49014
   590
    val Ds = fold (fold Term.add_tfreesT) (oDs :: Dss) [];
blanchet@49014
   591
blanchet@49502
   592
    val ((kill_poss, As), (inners', (unfold_set', lthy'))) =
blanchet@49502
   593
      normalize_bnfs qualify Ass Ds sort inners unfold_set lthy;
blanchet@49014
   594
blanchet@49014
   595
    val Ds = oDs @ flat (map3 (append oo map o nth) tfreess kill_poss Dss);
blanchet@49014
   596
    val As = map TFree As;
blanchet@49014
   597
  in
traytel@49425
   598
    apfst (rpair (Ds, As))
blanchet@49502
   599
      (clean_compose_bnf const_policy (qualify 0) b outer inners' (unfold_set', lthy'))
blanchet@49014
   600
  end;
blanchet@49014
   601
blanchet@48975
   602
(* Hide the type of the bound (optimization) and unfold the definitions (nicer to the user) *)
blanchet@48975
   603
blanchet@49502
   604
fun seal_bnf unfold_set b Ds bnf lthy =
blanchet@48975
   605
  let
blanchet@48975
   606
    val live = live_of_bnf bnf;
blanchet@48975
   607
    val nwits = nwits_of_bnf bnf;
blanchet@48975
   608
blanchet@48975
   609
    val (As, lthy1) = apfst (map TFree)
blanchet@48975
   610
      (Variable.invent_types (replicate live HOLogic.typeS) (fold Variable.declare_typ Ds lthy));
blanchet@48975
   611
    val (Bs, _) = apfst (map TFree)
blanchet@48975
   612
      (Variable.invent_types (replicate live HOLogic.typeS) lthy1);
blanchet@48975
   613
blanchet@49502
   614
    val map_unfolds = map_unfolds_of unfold_set;
blanchet@49502
   615
    val set_unfoldss = set_unfoldss_of unfold_set;
blanchet@49507
   616
    val rel_unfolds = rel_unfolds_of unfold_set;
blanchet@49506
   617
    val srel_unfolds = srel_unfolds_of unfold_set;
blanchet@48975
   618
blanchet@49507
   619
    val expand_maps =
blanchet@49507
   620
      fold expand_term_const (map (single o Logic.dest_equals o Thm.prop_of) map_unfolds);
blanchet@49507
   621
    val expand_sets =
blanchet@49507
   622
      fold expand_term_const (map (map (Logic.dest_equals o Thm.prop_of)) set_unfoldss);
blanchet@49507
   623
    val expand_rels =
blanchet@49507
   624
      fold expand_term_const (map (single o Logic.dest_equals o Thm.prop_of) rel_unfolds);
blanchet@49504
   625
    val unfold_maps = fold (unfold_thms lthy o single) map_unfolds;
blanchet@49504
   626
    val unfold_sets = fold (unfold_thms lthy) set_unfoldss;
blanchet@49507
   627
    val unfold_rels = unfold_thms lthy rel_unfolds;
blanchet@49506
   628
    val unfold_srels = unfold_thms lthy srel_unfolds;
blanchet@49507
   629
    val unfold_all = unfold_sets o unfold_maps o unfold_rels o unfold_srels;
blanchet@48975
   630
    val bnf_map = expand_maps (mk_map_of_bnf Ds As Bs bnf);
blanchet@48975
   631
    val bnf_sets = map (expand_maps o expand_sets)
blanchet@48975
   632
      (mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf);
blanchet@48975
   633
    val bnf_bd = mk_bd_of_bnf Ds As bnf;
blanchet@49507
   634
    val bnf_rel = expand_rels (mk_rel_of_bnf Ds As Bs bnf);
blanchet@48975
   635
    val T = mk_T_of_bnf Ds As bnf;
blanchet@48975
   636
blanchet@48975
   637
    (*bd should only depend on dead type variables!*)
blanchet@48975
   638
    val bd_repT = fst (dest_relT (fastype_of bnf_bd));
blanchet@48975
   639
    val bdT_bind = Binding.suffix_name ("_" ^ bdTN) b;
blanchet@48975
   640
    val params = fold Term.add_tfreesT Ds [];
traytel@49185
   641
    val deads = map TFree params;
blanchet@48975
   642
traytel@49228
   643
    val ((bdT_name, (bdT_glob_info, bdT_loc_info)), lthy) =
traytel@49228
   644
      typedef false NONE (bdT_bind, params, NoSyn)
traytel@49228
   645
        (HOLogic.mk_UNIV bd_repT) NONE (EVERY' [rtac exI, rtac UNIV_I] 1) lthy;
blanchet@48975
   646
blanchet@48975
   647
    val bnf_bd' = mk_dir_image bnf_bd
traytel@49185
   648
      (Const (#Abs_name bdT_glob_info, bd_repT --> Type (bdT_name, deads)))
blanchet@48975
   649
traytel@49228
   650
    val Abs_bdT_inj = mk_Abs_inj_thm (#Abs_inject bdT_loc_info);
traytel@49228
   651
    val Abs_bdT_bij = mk_Abs_bij_thm lthy Abs_bdT_inj (#Abs_cases bdT_loc_info);
blanchet@48975
   652
blanchet@48975
   653
    val bd_ordIso = @{thm dir_image} OF [Abs_bdT_inj, bd_Card_order_of_bnf bnf];
blanchet@48975
   654
    val bd_card_order =
blanchet@48975
   655
      @{thm card_order_dir_image} OF [Abs_bdT_bij, bd_card_order_of_bnf bnf];
blanchet@48975
   656
    val bd_cinfinite =
blanchet@48975
   657
      (@{thm Cinfinite_cong} OF [bd_ordIso, bd_Cinfinite_of_bnf bnf]) RS conjunct1;
blanchet@48975
   658
blanchet@48975
   659
    val set_bds =
blanchet@48975
   660
      map (fn thm => @{thm ordLeq_ordIso_trans} OF [thm, bd_ordIso]) (set_bd_of_bnf bnf);
blanchet@48975
   661
    val in_bd =
blanchet@48975
   662
      @{thm ordLeq_ordIso_trans} OF [in_bd_of_bnf bnf,
blanchet@48975
   663
        @{thm cexp_cong2_Cnotzero} OF [bd_ordIso, if live = 0 then
blanchet@48975
   664
          @{thm ctwo_Cnotzero} else @{thm ctwo_Cnotzero} RS @{thm csum_Cnotzero2},
blanchet@48975
   665
            bd_Card_order_of_bnf bnf]];
blanchet@48975
   666
blanchet@49463
   667
    fun mk_tac thm {context = ctxt, prems = _} =
blanchet@49463
   668
      (rtac (unfold_all thm) THEN'
blanchet@48975
   669
      SOLVE o REPEAT_DETERM o (atac ORELSE' Goal.assume_rule_tac ctxt)) 1;
blanchet@49456
   670
blanchet@49460
   671
    val tacs = zip_axioms (mk_tac (map_id_of_bnf bnf)) (mk_tac (map_comp_of_bnf bnf))
blanchet@49456
   672
      (mk_tac (map_cong_of_bnf bnf)) (map mk_tac (set_natural_of_bnf bnf))
blanchet@49456
   673
      (K (rtac bd_card_order 1)) (K (rtac bd_cinfinite 1)) (map mk_tac set_bds) (mk_tac in_bd)
blanchet@49463
   674
      (mk_tac (map_wpull_of_bnf bnf))
blanchet@49506
   675
      (mk_tac (unfold_thms lthy [srel_def_of_bnf bnf] (srel_O_Gr_of_bnf bnf)));
blanchet@48975
   676
blanchet@48975
   677
    val bnf_wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf);
blanchet@48975
   678
blanchet@49463
   679
    fun wit_tac _ = mk_simple_wit_tac (map unfold_all (wit_thms_of_bnf bnf));
blanchet@48975
   680
blanchet@49538
   681
    val (bnf', lthy') = bnf_def Hardly_Inline (user_policy Dont_Note) I tacs wit_tac (SOME deads)
blanchet@49507
   682
      (((((b, bnf_map), bnf_sets), Term.absdummy T bnf_bd'), bnf_wits), SOME bnf_rel) lthy;
blanchet@48975
   683
  in
blanchet@49456
   684
    ((bnf', deads), lthy')
blanchet@48975
   685
  end;
blanchet@48975
   686
blanchet@49456
   687
fun bnf_of_typ _ _ _ (T as TFree _) accum = ((ID_bnf, ([], [T])), accum)
traytel@49425
   688
  | bnf_of_typ _ _ _ (TVar _) _ = error "Unexpected schematic variable"
blanchet@49502
   689
  | bnf_of_typ const_policy qualify' sort (T as Type (C, Ts)) (unfold_set, lthy) =
traytel@49186
   690
    let
traytel@49186
   691
      val tfrees = Term.add_tfreesT T [];
traytel@49236
   692
      val bnf_opt = if null tfrees then NONE else bnf_of lthy C;
blanchet@48975
   693
    in
traytel@49186
   694
      (case bnf_opt of
blanchet@49502
   695
        NONE => ((DEADID_bnf, ([T], [])), (unfold_set, lthy))
traytel@49186
   696
      | SOME bnf =>
traytel@49186
   697
        if forall (can Term.dest_TFree) Ts andalso length Ts = length tfrees then
traytel@49186
   698
          let
traytel@49186
   699
            val T' = T_of_bnf bnf;
traytel@49186
   700
            val deads = deads_of_bnf bnf;
traytel@49186
   701
            val lives = lives_of_bnf bnf;
traytel@49186
   702
            val tvars' = Term.add_tvarsT T' [];
traytel@49186
   703
            val deads_lives =
traytel@49186
   704
              pairself (map (Term.typ_subst_TVars (map fst tvars' ~~ map TFree tfrees)))
traytel@49186
   705
                (deads, lives);
blanchet@49502
   706
          in ((bnf, deads_lives), (unfold_set, lthy)) end
traytel@49186
   707
        else
traytel@49186
   708
          let
traytel@49425
   709
            val name = Long_Name.base_name C;
traytel@49425
   710
            fun qualify i =
traytel@49425
   711
              let val namei = name ^ nonzero_string_of_int i;
traytel@49425
   712
              in qualify' o Binding.qualify true namei end;
traytel@49186
   713
            val odead = dead_of_bnf bnf;
traytel@49186
   714
            val olive = live_of_bnf bnf;
traytel@49186
   715
            val oDs_pos = find_indices [TFree ("dead", [])] (snd (Term.dest_Type
traytel@49186
   716
              (mk_T_of_bnf (replicate odead (TFree ("dead", []))) (replicate olive dummyT) bnf)));
traytel@49186
   717
            val oDs = map (nth Ts) oDs_pos;
traytel@49186
   718
            val Ts' = map (nth Ts) (subtract (op =) oDs_pos (0 upto length Ts - 1));
blanchet@49502
   719
            val ((inners, (Dss, Ass)), (unfold_set', lthy')) =
traytel@49186
   720
              apfst (apsnd split_list o split_list)
traytel@49425
   721
                (fold_map2 (fn i => bnf_of_typ Smart_Inline (qualify i) sort)
blanchet@49502
   722
                (if length Ts' = 1 then [0] else (1 upto length Ts')) Ts' (unfold_set, lthy));
traytel@49186
   723
          in
blanchet@49502
   724
            compose_bnf const_policy qualify sort bnf inners oDs Dss Ass (unfold_set', lthy')
traytel@49186
   725
          end)
blanchet@48975
   726
    end;
blanchet@48975
   727
blanchet@48975
   728
end;