src/HOL/BNF/Tools/bnf_def.ML
changeset 53289 5e0623448bdb
parent 53288 050d0bc9afa5
child 53290 b6c3be868217
equal deleted inserted replaced
53288:050d0bc9afa5 53289:5e0623448bdb
    70   val rel_mono_strong_of_bnf: bnf -> thm
    70   val rel_mono_strong_of_bnf: bnf -> thm
    71   val rel_eq_of_bnf: bnf -> thm
    71   val rel_eq_of_bnf: bnf -> thm
    72   val rel_flip_of_bnf: bnf -> thm
    72   val rel_flip_of_bnf: bnf -> thm
    73   val set_bd_of_bnf: bnf -> thm list
    73   val set_bd_of_bnf: bnf -> thm list
    74   val set_defs_of_bnf: bnf -> thm list
    74   val set_defs_of_bnf: bnf -> thm list
       
    75   val set_map0_of_bnf: bnf -> thm list
    75   val set_map'_of_bnf: bnf -> thm list
    76   val set_map'_of_bnf: bnf -> thm list
    76   val set_map_of_bnf: bnf -> thm list
       
    77   val wit_thms_of_bnf: bnf -> thm list
    77   val wit_thms_of_bnf: bnf -> thm list
    78   val wit_thmss_of_bnf: bnf -> thm list list
    78   val wit_thmss_of_bnf: bnf -> thm list list
    79 
    79 
    80   val mk_witness: int list * term -> thm list -> nonemptiness_witness
    80   val mk_witness: int list * term -> thm list -> nonemptiness_witness
    81   val minimize_wits: (''a list * 'b) list -> (''a list * 'b) list
    81   val minimize_wits: (''a list * 'b) list -> (''a list * 'b) list
   114 
   114 
   115 type axioms = {
   115 type axioms = {
   116   map_id0: thm,
   116   map_id0: thm,
   117   map_comp0: thm,
   117   map_comp0: thm,
   118   map_cong0: thm,
   118   map_cong0: thm,
   119   set_map: thm list,
   119   set_map0: thm list,
   120   bd_card_order: thm,
   120   bd_card_order: thm,
   121   bd_cinfinite: thm,
   121   bd_cinfinite: thm,
   122   set_bd: thm list,
   122   set_bd: thm list,
   123   map_wpull: thm,
   123   map_wpull: thm,
   124   rel_OO_Grp: thm
   124   rel_OO_Grp: thm
   125 };
   125 };
   126 
   126 
   127 fun mk_axioms' ((((((((id, comp), cong), nat), c_o), cinf), set_bd), wpull), rel) =
   127 fun mk_axioms' ((((((((id, comp), cong), map), c_o), cinf), set_bd), wpull), rel) =
   128   {map_id0 = id, map_comp0 = comp, map_cong0 = cong, set_map = nat, bd_card_order = c_o,
   128   {map_id0 = id, map_comp0 = comp, map_cong0 = cong, set_map0 = map, bd_card_order = c_o,
   129    bd_cinfinite = cinf, set_bd = set_bd, map_wpull = wpull, rel_OO_Grp = rel};
   129    bd_cinfinite = cinf, set_bd = set_bd, map_wpull = wpull, rel_OO_Grp = rel};
   130 
   130 
   131 fun dest_cons [] = raise List.Empty
   131 fun dest_cons [] = raise List.Empty
   132   | dest_cons (x :: xs) = (x, xs);
   132   | dest_cons (x :: xs) = (x, xs);
   133 
   133 
   142   ||>> chop n
   142   ||>> chop n
   143   ||>> dest_cons
   143   ||>> dest_cons
   144   ||> the_single
   144   ||> the_single
   145   |> mk_axioms';
   145   |> mk_axioms';
   146 
   146 
   147 fun zip_axioms mid mcomp mcong snat bdco bdinf sbd wpull rel =
   147 fun zip_axioms mid mcomp mcong smap bdco bdinf sbd wpull rel =
   148   [mid, mcomp, mcong] @ snat @ [bdco, bdinf] @ sbd @ [wpull, rel];
   148   [mid, mcomp, mcong] @ smap @ [bdco, bdinf] @ sbd @ [wpull, rel];
   149 
   149 
   150 fun dest_axioms {map_id0, map_comp0, map_cong0, set_map, bd_card_order, bd_cinfinite, set_bd,
   150 fun dest_axioms {map_id0, map_comp0, map_cong0, set_map0, bd_card_order, bd_cinfinite, set_bd,
   151   map_wpull, rel_OO_Grp} =
   151   map_wpull, rel_OO_Grp} =
   152   zip_axioms map_id0 map_comp0 map_cong0 set_map bd_card_order bd_cinfinite set_bd map_wpull
   152   zip_axioms map_id0 map_comp0 map_cong0 set_map0 bd_card_order bd_cinfinite set_bd map_wpull
   153     rel_OO_Grp;
   153     rel_OO_Grp;
   154 
   154 
   155 fun map_axioms f {map_id0, map_comp0, map_cong0, set_map, bd_card_order, bd_cinfinite, set_bd,
   155 fun map_axioms f {map_id0, map_comp0, map_cong0, set_map0, bd_card_order, bd_cinfinite, set_bd,
   156   map_wpull, rel_OO_Grp} =
   156   map_wpull, rel_OO_Grp} =
   157   {map_id0 = f map_id0,
   157   {map_id0 = f map_id0,
   158     map_comp0 = f map_comp0,
   158     map_comp0 = f map_comp0,
   159     map_cong0 = f map_cong0,
   159     map_cong0 = f map_cong0,
   160     set_map = map f set_map,
   160     set_map0 = map f set_map0,
   161     bd_card_order = f bd_card_order,
   161     bd_card_order = f bd_card_order,
   162     bd_cinfinite = f bd_cinfinite,
   162     bd_cinfinite = f bd_cinfinite,
   163     set_bd = map f set_bd,
   163     set_bd = map f set_bd,
   164     map_wpull = f map_wpull,
   164     map_wpull = f map_wpull,
   165     rel_OO_Grp = f rel_OO_Grp};
   165     rel_OO_Grp = f rel_OO_Grp};
   392 val rel_def_of_bnf = #rel_def o #defs o rep_bnf;
   392 val rel_def_of_bnf = #rel_def o #defs o rep_bnf;
   393 val rel_eq_of_bnf = Lazy.force o #rel_eq o #facts o rep_bnf;
   393 val rel_eq_of_bnf = Lazy.force o #rel_eq o #facts o rep_bnf;
   394 val rel_flip_of_bnf = Lazy.force o #rel_flip o #facts o rep_bnf;
   394 val rel_flip_of_bnf = Lazy.force o #rel_flip o #facts o rep_bnf;
   395 val set_bd_of_bnf = #set_bd o #axioms o rep_bnf;
   395 val set_bd_of_bnf = #set_bd o #axioms o rep_bnf;
   396 val set_defs_of_bnf = #set_defs o #defs o rep_bnf;
   396 val set_defs_of_bnf = #set_defs o #defs o rep_bnf;
   397 val set_map_of_bnf = #set_map o #axioms o rep_bnf;
   397 val set_map0_of_bnf = #set_map0 o #axioms o rep_bnf;
   398 val set_map'_of_bnf = map Lazy.force o #set_map' o #facts o rep_bnf;
   398 val set_map'_of_bnf = map Lazy.force o #set_map' o #facts o rep_bnf;
   399 val rel_cong_of_bnf = Lazy.force o #rel_cong o #facts o rep_bnf;
   399 val rel_cong_of_bnf = Lazy.force o #rel_cong o #facts o rep_bnf;
   400 val rel_mono_of_bnf = Lazy.force o #rel_mono o #facts o rep_bnf;
   400 val rel_mono_of_bnf = Lazy.force o #rel_mono o #facts o rep_bnf;
   401 val rel_mono_strong_of_bnf = Lazy.force o #rel_mono_strong o #facts o rep_bnf;
   401 val rel_mono_strong_of_bnf = Lazy.force o #rel_mono_strong o #facts o rep_bnf;
   402 val rel_Grp_of_bnf = Lazy.force o #rel_Grp o #facts o rep_bnf;
   402 val rel_Grp_of_bnf = Lazy.force o #rel_Grp o #facts o rep_bnf;
   516 val map_congN = "map_cong";
   516 val map_congN = "map_cong";
   517 val map_transferN = "map_transfer";
   517 val map_transferN = "map_transfer";
   518 val map_wpullN = "map_wpull";
   518 val map_wpullN = "map_wpull";
   519 val rel_eqN = "rel_eq";
   519 val rel_eqN = "rel_eq";
   520 val rel_flipN = "rel_flip";
   520 val rel_flipN = "rel_flip";
   521 val set_mapN = "set_map";
   521 val set_map0N = "set_map0";
   522 val set_map'N = "set_map'";
   522 val set_map'N = "set_map'";
   523 val set_bdN = "set_bd";
   523 val set_bdN = "set_bd";
   524 val rel_GrpN = "rel_Grp";
   524 val rel_GrpN = "rel_Grp";
   525 val rel_conversepN = "rel_conversep";
   525 val rel_conversepN = "rel_conversep";
   526 val rel_monoN = "rel_mono"
   526 val rel_monoN = "rel_mono"
   561             (map_comp0N, [#map_comp0 axioms]),
   561             (map_comp0N, [#map_comp0 axioms]),
   562             (map_id0N, [#map_id0 axioms]),
   562             (map_id0N, [#map_id0 axioms]),
   563             (map_transferN, [Lazy.force (#map_transfer facts)]),
   563             (map_transferN, [Lazy.force (#map_transfer facts)]),
   564             (map_wpullN, [#map_wpull axioms]),
   564             (map_wpullN, [#map_wpull axioms]),
   565             (rel_mono_strongN, [Lazy.force (#rel_mono_strong facts)]),
   565             (rel_mono_strongN, [Lazy.force (#rel_mono_strong facts)]),
   566             (set_mapN, #set_map axioms),
   566             (set_map0N, #set_map0 axioms),
   567             (set_bdN, #set_bd axioms)] @
   567             (set_bdN, #set_bd axioms)] @
   568             (witNs ~~ wit_thmss_of_bnf bnf)
   568             (witNs ~~ wit_thmss_of_bnf bnf)
   569             |> map (fn (thmN, thms) =>
   569             |> map (fn (thmN, thms) =>
   570               ((qualify (Binding.qualify true (Binding.name_of bnf_b) (Binding.name thmN)), []),
   570               ((qualify (Binding.qualify true (Binding.name_of bnf_b) (Binding.name thmN)), []),
   571               [(thms, [])]));
   571               [(thms, [])]));
   871           Term.list_comb (bnf_map_AsBs, fs_copy) $ x);
   871           Term.list_comb (bnf_map_AsBs, fs_copy) $ x);
   872       in
   872       in
   873         fold_rev Logic.all (x :: fs @ fs_copy) (Logic.list_implies (prems, eq))
   873         fold_rev Logic.all (x :: fs @ fs_copy) (Logic.list_implies (prems, eq))
   874       end;
   874       end;
   875 
   875 
   876     val set_maps_goal =
   876     val set_map0s_goal =
   877       let
   877       let
   878         fun mk_goal setA setB f =
   878         fun mk_goal setA setB f =
   879           let
   879           let
   880             val set_comp_map =
   880             val set_comp_map =
   881               HOLogic.mk_comp (setB, Term.list_comb (bnf_map_AsBs, fs));
   881               HOLogic.mk_comp (setB, Term.list_comb (bnf_map_AsBs, fs));
   920           (Logic.list_implies (prems, HOLogic.mk_Trueprop map_wpull))
   920           (Logic.list_implies (prems, HOLogic.mk_Trueprop map_wpull))
   921       end;
   921       end;
   922 
   922 
   923     val rel_OO_Grp_goal = fold_rev Logic.all Rs (mk_Trueprop_eq (Term.list_comb (rel, Rs), OO_Grp));
   923     val rel_OO_Grp_goal = fold_rev Logic.all Rs (mk_Trueprop_eq (Term.list_comb (rel, Rs), OO_Grp));
   924 
   924 
   925     val goals = zip_axioms map_id0_goal map_comp0_goal map_cong0_goal set_maps_goal
   925     val goals = zip_axioms map_id0_goal map_comp0_goal map_cong0_goal set_map0s_goal
   926       card_order_bd_goal cinfinite_bd_goal set_bds_goal map_wpull_goal rel_OO_Grp_goal;
   926       card_order_bd_goal cinfinite_bd_goal set_bds_goal map_wpull_goal rel_OO_Grp_goal;
   927 
   927 
   928     fun mk_wit_goals (I, wit) =
   928     fun mk_wit_goals (I, wit) =
   929       let
   929       let
   930         val xs = map (nth bs) I;
   930         val xs = map (nth bs) I;
   963               (map2 (fn h => fn set => HOLogic.mk_comp (mk_image h, set)) hs bnf_sets_As)
   963               (map2 (fn h => fn set => HOLogic.mk_comp (mk_image h, set)) hs bnf_sets_As)
   964               defT;
   964               defT;
   965             (*collect {set1 ... setm} o map f1 ... fm = collect {f1` o set1 ... fm` o setm}*)
   965             (*collect {set1 ... setm} o map f1 ... fm = collect {f1` o set1 ... fm` o setm}*)
   966             val goal = fold_rev Logic.all hs (mk_Trueprop_eq (collect_map, image_collect));
   966             val goal = fold_rev Logic.all hs (mk_Trueprop_eq (collect_map, image_collect));
   967           in
   967           in
   968             Goal.prove_sorry lthy [] [] goal (K (mk_collect_set_map_tac (#set_map axioms)))
   968             Goal.prove_sorry lthy [] [] goal (K (mk_collect_set_map_tac (#set_map0 axioms)))
   969             |> Thm.close_derivation
   969             |> Thm.close_derivation
   970           end;
   970           end;
   971 
   971 
   972         val collect_set_map = Lazy.lazy mk_collect_set_map;
   972         val collect_set_map = Lazy.lazy mk_collect_set_map;
   973 
   973 
  1016             |> Thm.close_derivation
  1016             |> Thm.close_derivation
  1017           end;
  1017           end;
  1018 
  1018 
  1019         val map_cong = Lazy.lazy mk_map_cong;
  1019         val map_cong = Lazy.lazy mk_map_cong;
  1020 
  1020 
  1021         val set_map' = map (fn thm => Lazy.lazy (fn () => mk_set_map' thm)) (#set_map axioms);
  1021         val set_map' = map (fn thm => Lazy.lazy (fn () => mk_set_map' thm)) (#set_map0 axioms);
  1022 
  1022 
  1023         fun mk_in_bd () =
  1023         fun mk_in_bd () =
  1024           let
  1024           let
  1025             val bdT = fst (dest_relT (fastype_of bnf_bd_As));
  1025             val bdT = fst (dest_relT (fastype_of bnf_bd_As));
  1026             val bdTs = replicate live bdT;
  1026             val bdTs = replicate live bdT;
  1333     |> Pretty.writeln
  1333     |> Pretty.writeln
  1334   end;
  1334   end;
  1335 
  1335 
  1336 val _ =
  1336 val _ =
  1337   Outer_Syntax.improper_command @{command_spec "print_bnfs"}
  1337   Outer_Syntax.improper_command @{command_spec "print_bnfs"}
  1338     "print all BNFs (bounded natural functors)"
  1338     "print all bounded natural functors"
  1339     (Scan.succeed (Toplevel.keep (print_bnfs o Toplevel.context_of)));
  1339     (Scan.succeed (Toplevel.keep (print_bnfs o Toplevel.context_of)));
  1340 
  1340 
  1341 val _ =
  1341 val _ =
  1342   Outer_Syntax.local_theory_to_proof @{command_spec "bnf"}
  1342   Outer_Syntax.local_theory_to_proof @{command_spec "bnf"}
  1343     "register a type as a BNF (bounded natural functor)"
  1343     "register a type as a bounded natural functor"
  1344     ((parse_opt_binding_colon -- Parse.term --
  1344     ((parse_opt_binding_colon -- Parse.term --
  1345        (@{keyword "["} |-- Parse.list Parse.term --| @{keyword "]"}) -- Parse.term --
  1345        (@{keyword "["} |-- Parse.list Parse.term --| @{keyword "]"}) -- Parse.term --
  1346        (@{keyword "["} |-- Parse.list Parse.term --| @{keyword "]"}) -- Scan.option Parse.term)
  1346        (@{keyword "["} |-- Parse.list Parse.term --| @{keyword "]"}) -- Scan.option Parse.term)
  1347        >> bnf_cmd);
  1347        >> bnf_cmd);
  1348 
  1348