src/HOL/Tools/BNF/bnf_comp.ML
changeset 56016 8875cdcfc85b
parent 56013 508836bbfed4
child 56018 c3fc8692dbc1
equal deleted inserted replaced
56015:57e2cfba9c6e 56016:8875cdcfc85b
   336     fun wit_tac ctxt =
   336     fun wit_tac ctxt =
   337       mk_comp_wit_tac ctxt set'_eq_sets (wit_thms_of_bnf outer) (collect_set_map_of_bnf outer)
   337       mk_comp_wit_tac ctxt set'_eq_sets (wit_thms_of_bnf outer) (collect_set_map_of_bnf outer)
   338         (maps wit_thms_of_bnf inners);
   338         (maps wit_thms_of_bnf inners);
   339 
   339 
   340     val (bnf', lthy') =
   340     val (bnf', lthy') =
   341       bnf_def const_policy (K Dont_Note) qualify tacs wit_tac (SOME (oDs @ flat Dss)) Binding.empty
   341       bnf_def const_policy (K Dont_Note) true qualify tacs wit_tac (SOME (oDs @ flat Dss))
   342         Binding.empty [] ((((((b, CCA), mapx), sets'), bd'), wits), SOME rel) lthy;
   342         Binding.empty Binding.empty [] ((((((b, CCA), mapx), sets'), bd'), wits), SOME rel) lthy;
   343 
   343 
   344     val phi =
   344     val phi =
   345       Morphism.thm_morphism "BNF" (unfold_thms lthy' [id_bnf_comp_def])
   345       Morphism.thm_morphism "BNF" (unfold_thms lthy' [id_bnf_comp_def])
   346       $> Morphism.term_morphism "BNF" expand_id_bnf_comp_def;
   346       $> Morphism.term_morphism "BNF" expand_id_bnf_comp_def;
   347 
   347 
   434       (map (fn (I, wit) => Term.list_comb (wit, map (nth xs) I)) bnf_wits);
   434       (map (fn (I, wit) => Term.list_comb (wit, map (nth xs) I)) bnf_wits);
   435 
   435 
   436     fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf);
   436     fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf);
   437 
   437 
   438     val (bnf', lthy') =
   438     val (bnf', lthy') =
   439       bnf_def Smart_Inline (K Dont_Note) qualify tacs wit_tac (SOME (killedAs @ Ds)) Binding.empty
   439       bnf_def Smart_Inline (K Dont_Note) true qualify tacs wit_tac (SOME (killedAs @ Ds))
   440         Binding.empty [] ((((((b, T), mapx), sets), bd), wits), SOME rel) lthy;
   440         Binding.empty Binding.empty [] ((((((b, T), mapx), sets), bd), wits), SOME rel) lthy;
   441   in
   441   in
   442     (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
   442     (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
   443   end;
   443   end;
   444 
   444 
   445 fun kill_bnf qualify n bnf (accum as ((cache, unfold_set), lthy)) =
   445 fun kill_bnf qualify n bnf (accum as ((cache, unfold_set), lthy)) =
   524     val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf);
   524     val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf);
   525 
   525 
   526     fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf);
   526     fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf);
   527 
   527 
   528     val (bnf', lthy') =
   528     val (bnf', lthy') =
   529       bnf_def Smart_Inline (K Dont_Note) qualify tacs wit_tac (SOME Ds) Binding.empty Binding.empty
   529       bnf_def Smart_Inline (K Dont_Note) true qualify tacs wit_tac (SOME Ds) Binding.empty
   530         [] ((((((b, T), mapx), sets), bd), wits), SOME rel) lthy;
   530         Binding.empty [] ((((((b, T), mapx), sets), bd), wits), SOME rel) lthy;
   531   in
   531   in
   532     (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
   532     (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
   533   end;
   533   end;
   534 
   534 
   535 fun lift_bnf qualify n bnf (accum as ((cache, unfold_set), lthy)) =
   535 fun lift_bnf qualify n bnf (accum as ((cache, unfold_set), lthy)) =
   605     val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf);
   605     val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf);
   606 
   606 
   607     fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf);
   607     fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf);
   608 
   608 
   609     val (bnf', lthy') =
   609     val (bnf', lthy') =
   610       bnf_def Smart_Inline (K Dont_Note) qualify tacs wit_tac (SOME Ds) Binding.empty Binding.empty
   610       bnf_def Smart_Inline (K Dont_Note) true qualify tacs wit_tac (SOME Ds) Binding.empty
   611         [] ((((((b, T), mapx), sets), bd), wits), SOME rel) lthy;
   611         Binding.empty [] ((((((b, T), mapx), sets), bd), wits), SOME rel) lthy;
   612   in
   612   in
   613     (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
   613     (bnf', (add_bnf_to_unfolds bnf' unfold_set, lthy'))
   614   end;
   614   end;
   615 
   615 
   616 fun permute_bnf qualify src dest bnf (accum as ((cache, unfold_set), lthy)) =
   616 fun permute_bnf qualify src dest bnf (accum as ((cache, unfold_set), lthy)) =
   763 
   763 
   764     val (((fs, fs'), (Rs, Rs')), _(*names_lthy*)) = lthy
   764     val (((fs, fs'), (Rs, Rs')), _(*names_lthy*)) = lthy
   765       |> mk_Frees' "f" (map2 (curry op -->) As Bs)
   765       |> mk_Frees' "f" (map2 (curry op -->) As Bs)
   766       ||>> mk_Frees' "R" (map2 mk_pred2T As Bs);
   766       ||>> mk_Frees' "R" (map2 mk_pred2T As Bs);
   767 
   767 
   768     val map_unfolds = map (unfold_thms lthy [id_bnf_comp_def]) (#map_unfolds unfold_set);
       
   769     val set_unfoldss = #set_unfoldss unfold_set;
       
   770     val rel_unfolds = map (unfold_thms lthy [id_bnf_comp_def]) (#rel_unfolds unfold_set);
       
   771 
       
   772     val expand_maps = expand_id_bnf_comp_def o
       
   773       fold expand_term_const (map (single o Logic.dest_equals o Thm.prop_of) map_unfolds);
       
   774     val expand_sets =
       
   775       fold expand_term_const (map (map (Logic.dest_equals o Thm.prop_of)) set_unfoldss);
       
   776     val expand_rels = expand_id_bnf_comp_def o
       
   777       fold expand_term_const (map (single o Logic.dest_equals o Thm.prop_of) rel_unfolds);
       
   778     fun unfold_maps ctxt = fold (unfold_thms ctxt o single) (id_bnf_comp_def :: map_unfolds);
       
   779     fun unfold_sets ctxt = fold (unfold_thms ctxt) set_unfoldss;
       
   780     fun unfold_rels ctxt = fold (unfold_thms ctxt o single) (id_bnf_comp_def :: rel_unfolds);
       
   781     fun unfold_all ctxt = unfold_sets ctxt o unfold_maps ctxt o unfold_rels ctxt;
       
   782 
       
   783     val repTA = mk_T_of_bnf Ds As bnf;
   768     val repTA = mk_T_of_bnf Ds As bnf;
   784     val T_bind = qualify b;
   769     val T_bind = qualify b;
   785     val TA_params = Term.add_tfreesT repTA [];
   770     val TA_params = Term.add_tfreesT repTA [];
   786     val ((TA, (Rep_name, Abs_name, type_definition, Abs_inverse, Abs_inject, _)), lthy) =
   771     val ((TA, (Rep_name, Abs_name, type_definition, Abs_inverse, Abs_inject, _)), lthy) =
   787       maybe_typedef (T_bind, TA_params, NoSyn)
   772       maybe_typedef (T_bind, TA_params, NoSyn)
   798 
   783 
   799     val absT_info = {absT = TA, repT = repTA, abs = AbsA, rep = RepA, abs_inject = Abs_inject',
   784     val absT_info = {absT = TA, repT = repTA, abs = AbsA, rep = RepA, abs_inject = Abs_inject',
   800       abs_inverse = Abs_inverse', type_definition = type_definition};
   785       abs_inverse = Abs_inverse', type_definition = type_definition};
   801 
   786 
   802     val bnf_map = fold_rev Term.absfree fs' (HOLogic.mk_comp (HOLogic.mk_comp (AbsB,
   787     val bnf_map = fold_rev Term.absfree fs' (HOLogic.mk_comp (HOLogic.mk_comp (AbsB,
   803       Term.list_comb (expand_maps (mk_map_of_bnf Ds As Bs bnf), fs)), RepA));
   788       Term.list_comb (mk_map_of_bnf Ds As Bs bnf, fs)), RepA));
   804     val bnf_sets = map ((fn t => HOLogic.mk_comp (t, RepA)) o expand_maps o expand_sets)
   789     val bnf_sets = map ((fn t => HOLogic.mk_comp (t, RepA)))
   805       (mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf);
   790       (mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf);
   806     val bnf_bd = mk_bd_of_bnf Ds As bnf;
   791     val bnf_bd = mk_bd_of_bnf Ds As bnf;
   807     val bnf_rel = fold_rev Term.absfree Rs' (mk_vimage2p RepA RepB $
   792     val bnf_rel = fold_rev Term.absfree Rs' (mk_vimage2p RepA RepB $
   808       (Term.list_comb (expand_rels (mk_rel_of_bnf Ds As Bs bnf), Rs)));
   793       (Term.list_comb (mk_rel_of_bnf Ds As Bs bnf, Rs)));
   809 
   794 
   810     (*bd may depend only on dead type variables*)
   795     (*bd may depend only on dead type variables*)
   811     val bd_repT = fst (dest_relT (fastype_of bnf_bd));
   796     val bd_repT = fst (dest_relT (fastype_of bnf_bd));
   812     val bdT_bind = qualify (Binding.suffix_name ("_" ^ bdTN) b);
   797     val bdT_bind = qualify (Binding.suffix_name ("_" ^ bdTN) b);
   813     val params = Term.add_tfreesT bd_repT [];
   798     val params = Term.add_tfreesT bd_repT [];
   834             (@{thm Cinfinite_cong} OF [bd_ordIso, bd_Cinfinite_of_bnf bnf]) RS conjunct1;
   819             (@{thm Cinfinite_cong} OF [bd_ordIso, bd_Cinfinite_of_bnf bnf]) RS conjunct1;
   835         in
   820         in
   836           (bnf_bd', bd_ordIso, bd_card_order, bd_cinfinite)
   821           (bnf_bd', bd_ordIso, bd_card_order, bd_cinfinite)
   837         end;
   822         end;
   838 
   823 
   839     fun map_id0_tac ctxt =
   824     fun map_id0_tac _ =
   840       rtac (@{thm type_copy_map_id0} OF [type_definition, unfold_maps ctxt (map_id0_of_bnf bnf)]) 1;
   825       rtac (@{thm type_copy_map_id0} OF [type_definition, map_id0_of_bnf bnf]) 1;
   841     fun map_comp0_tac ctxt =
   826     fun map_comp0_tac _ =
   842       rtac (@{thm type_copy_map_comp0} OF
   827       rtac (@{thm type_copy_map_comp0} OF [type_definition, map_comp0_of_bnf bnf]) 1;
   843         [type_definition, unfold_maps ctxt (map_comp0_of_bnf bnf)]) 1;
   828     fun map_cong0_tac _ =
   844     fun map_cong0_tac ctxt =
   829       EVERY' (rtac @{thm type_copy_map_cong0} :: rtac (map_cong0_of_bnf bnf) ::
   845       EVERY' (rtac @{thm type_copy_map_cong0} :: rtac (unfold_all ctxt (map_cong0_of_bnf bnf)) ::
       
   846         map (fn i => EVERY' [select_prem_tac live (dtac meta_spec) i, etac meta_mp,
   830         map (fn i => EVERY' [select_prem_tac live (dtac meta_spec) i, etac meta_mp,
   847           etac (o_apply RS equalityD2 RS set_mp)]) (1 upto live)) 1;
   831           etac (o_apply RS equalityD2 RS set_mp)]) (1 upto live)) 1;
   848     fun set_map0_tac thm ctxt =
   832     fun set_map0_tac thm _ =
   849       rtac (@{thm type_copy_set_map0} OF [type_definition, unfold_all ctxt thm]) 1;
   833       rtac (@{thm type_copy_set_map0} OF [type_definition, thm]) 1;
   850     val set_bd_tacs = map (fn thm => fn ctxt => rtac (@{thm ordLeq_ordIso_trans} OF
   834     val set_bd_tacs = map (fn thm => fn _ => rtac (@{thm ordLeq_ordIso_trans} OF
   851         [unfold_sets ctxt thm, bd_ordIso] RS @{thm type_copy_set_bd}) 1)
   835         [thm, bd_ordIso] RS @{thm type_copy_set_bd}) 1) (set_bd_of_bnf bnf);
   852       (set_bd_of_bnf bnf);
   836     fun le_rel_OO_tac _ =
   853     fun le_rel_OO_tac ctxt =
   837       rtac (le_rel_OO_of_bnf bnf RS @{thm vimage2p_relcompp_mono}) 1;
   854       rtac (unfold_rels ctxt (le_rel_OO_of_bnf bnf) RS @{thm vimage2p_relcompp_mono}) 1;
       
   855     fun rel_OO_Grp_tac ctxt =
   838     fun rel_OO_Grp_tac ctxt =
   856       (rtac (unfold_all ctxt (rel_OO_Grp_of_bnf bnf) RS @{thm vimage2p_cong} RS trans) THEN'
   839       (rtac (rel_OO_Grp_of_bnf bnf RS @{thm vimage2p_cong} RS trans) THEN'
   857       SELECT_GOAL (unfold_thms_tac ctxt [o_apply,
   840       SELECT_GOAL (unfold_thms_tac ctxt [o_apply,
   858         type_definition RS @{thm type_copy_vimage2p_Grp_Rep},
   841         type_definition RS @{thm type_copy_vimage2p_Grp_Rep},
   859         type_definition RS @{thm vimage2p_relcompp_converse}]) THEN' rtac refl) 1;
   842         type_definition RS @{thm vimage2p_relcompp_converse}]) THEN' rtac refl) 1;
   860 
   843 
   861     val tacs = zip_axioms map_id0_tac map_comp0_tac map_cong0_tac
   844     val tacs = zip_axioms map_id0_tac map_comp0_tac map_cong0_tac
   862       (map set_map0_tac (set_map0_of_bnf bnf)) (K (rtac bd_card_order 1)) (K (rtac bd_cinfinite 1))
   845       (map set_map0_tac (set_map0_of_bnf bnf)) (K (rtac bd_card_order 1)) (K (rtac bd_cinfinite 1))
   863       set_bd_tacs le_rel_OO_tac rel_OO_Grp_tac;
   846       set_bd_tacs le_rel_OO_tac rel_OO_Grp_tac;
   864 
   847 
   865     val bnf_wits = map (fn (I, t) =>
   848     val bnf_wits = map (fn (I, t) =>
   866         fold Term.absdummy (map (nth As) I)
   849         fold Term.absdummy (map (nth As) I)
   867           (AbsA $ Term.list_comb (expand_id_bnf_comp_def t, map Bound (0 upto length I - 1))))
   850           (AbsA $ Term.list_comb (t, map Bound (0 upto length I - 1))))
   868       (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf);
   851       (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf);
   869 
   852 
   870     fun wit_tac ctxt = ALLGOALS (dtac (type_definition RS @{thm type_copy_wit})) THEN
   853     fun wit_tac _ = ALLGOALS (dtac (type_definition RS @{thm type_copy_wit})) THEN
   871       mk_simple_wit_tac (map (unfold_all ctxt) (wit_thms_of_bnf bnf));
   854       mk_simple_wit_tac (wit_thms_of_bnf bnf);
   872 
   855 
   873     val (bnf', lthy') =
   856     val (bnf', lthy') =
   874       bnf_def Hardly_Inline (user_policy Dont_Note) qualify tacs wit_tac (SOME all_deads)
   857       bnf_def Hardly_Inline (user_policy Dont_Note) true qualify tacs wit_tac (SOME all_deads)
   875         Binding.empty Binding.empty []
   858         Binding.empty Binding.empty []
   876         ((((((b, TA), bnf_map), bnf_sets), bnf_bd'), bnf_wits), SOME bnf_rel) lthy;
   859         ((((((b, TA), bnf_map), bnf_sets), bnf_bd'), bnf_wits), SOME bnf_rel) lthy;
       
   860 
       
   861     val unfolds = @{thm id_bnf_comp_apply} ::
       
   862       (#map_unfolds unfold_set @ flat (#set_unfoldss unfold_set) @ #rel_unfolds unfold_set);
       
   863 
       
   864     val bnf'' = bnf' |> morph_bnf_defs (Morphism.thm_morphism "BNF" (unfold_thms lthy' unfolds));
       
   865     
       
   866     val map_def = map_def_of_bnf bnf'';
       
   867     val set_defs = set_defs_of_bnf bnf'';
       
   868     val rel_def = map_def_of_bnf bnf'';
       
   869 
       
   870     val bnf_b = qualify b;
       
   871     val def_qualify =
       
   872       Thm.def_binding o Binding.conceal o Binding.qualify false (Binding.name_of bnf_b);
       
   873     fun mk_prefix_binding pre = Binding.prefix_name (pre ^ "_") bnf_b;
       
   874     val map_b = def_qualify (mk_prefix_binding mapN);
       
   875     val rel_b = def_qualify (mk_prefix_binding relN);
       
   876     val set_bs = if live = 1 then [def_qualify (mk_prefix_binding setN)]
       
   877       else map (fn i => def_qualify (mk_prefix_binding (mk_setN i))) (1 upto live);
       
   878 
       
   879     val notes = (map_b, map_def) :: (rel_b, rel_def) :: (set_bs ~~ set_defs)
       
   880       |> map (fn (b, def) => ((b, []), [([def], [])]))
       
   881     val lthy'' = lthy' |> Local_Theory.notes notes |> snd
   877   in
   882   in
   878     ((bnf', (all_deads, absT_info)), lthy')
   883     ((bnf'', (all_deads, absT_info)), lthy'')
   879   end;
   884   end;
   880 
   885 
   881 exception BAD_DEAD of typ * typ;
   886 exception BAD_DEAD of typ * typ;
   882 
   887 
   883 fun bnf_of_typ _ _ _ _ Ds0 (T as TFree T') accum =
   888 fun bnf_of_typ _ _ _ _ Ds0 (T as TFree T') accum =