src/HOL/BNF/Tools/bnf_fp_def_sugar.ML
changeset 54237 7cc6e286fe28
parent 54236 e00009523727
child 54243 a596292be9a8
equal deleted inserted replaced
54236:e00009523727 54237:7cc6e286fe28
    38   val flat_corec_preds_predsss_gettersss: 'a list -> 'a list list list -> 'a list list list ->
    38   val flat_corec_preds_predsss_gettersss: 'a list -> 'a list list list -> 'a list list list ->
    39     'a list
    39     'a list
    40   val mk_co_iter: theory -> BNF_FP_Util.fp_kind -> typ -> typ list -> term -> term
    40   val mk_co_iter: theory -> BNF_FP_Util.fp_kind -> typ -> typ list -> term -> term
    41   val nesty_bnfs: Proof.context -> typ list list list -> typ list -> BNF_Def.bnf list
    41   val nesty_bnfs: Proof.context -> typ list list list -> typ list -> BNF_Def.bnf list
    42   val dest_map: Proof.context -> string -> term -> term * term list
    42   val dest_map: Proof.context -> string -> term -> term * term list
    43   val dest_ctr: Proof.context -> string -> term -> term * term list
       
    44 
    43 
    45   type lfp_sugar_thms =
    44   type lfp_sugar_thms =
    46     (thm list * thm * Args.src list)
    45     (thm list * thm * Args.src list)
    47     * (thm list list * thm list list * Args.src list)
    46     * (thm list list * thm list list * Args.src list)
    48 
    47 
   346   in snd oo add end;
   345   in snd oo add end;
   347 
   346 
   348 fun nesty_bnfs ctxt ctr_Tsss Us =
   347 fun nesty_bnfs ctxt ctr_Tsss Us =
   349   map_filter (bnf_of ctxt) (fold (fold (fold (add_nesty_bnf_names Us))) ctr_Tsss []);
   348   map_filter (bnf_of ctxt) (fold (fold (fold (add_nesty_bnf_names Us))) ctr_Tsss []);
   350 
   349 
   351 fun indexify proj xs f p = f (find_index (curry op = (proj p)) xs) p;
   350 fun indexify proj xs f p = f (find_index (curry (op =) (proj p)) xs) p;
   352 
   351 
   353 type lfp_sugar_thms =
   352 type lfp_sugar_thms =
   354   (thm list * thm * Args.src list)
   353   (thm list * thm * Args.src list)
   355   * (thm list list * thm list list * Args.src list)
   354   * (thm list list * thm list list * Args.src list)
   356 
   355 
   388               map2 unzip_recT ctr_Ts (dest_tupleT m ctor_iter_fun_T))
   387               map2 unzip_recT ctr_Ts (dest_tupleT m ctor_iter_fun_T))
   389             ms ctr_Tss (dest_sumTN_balanced n (domain_type (co_rec_of ctor_iter_fun_Ts))))
   388             ms ctr_Tss (dest_sumTN_balanced n (domain_type (co_rec_of ctor_iter_fun_Ts))))
   390         ns mss ctr_Tsss ctor_iter_fun_Tss;
   389         ns mss ctr_Tsss ctor_iter_fun_Tss;
   391 
   390 
   392     val z_Tsss' = map (map flat_rec_arg_args) z_Tssss;
   391     val z_Tsss' = map (map flat_rec_arg_args) z_Tssss;
   393     val h_Tss = map2 (map2 (curry op --->)) z_Tsss' Css;
   392     val h_Tss = map2 (map2 (curry (op --->))) z_Tsss' Css;
   394 
   393 
   395     val hss = map2 (map2 retype_free) h_Tss gss;
   394     val hss = map2 (map2 retype_free) h_Tss gss;
   396     val zssss_hd = map2 (map2 (map2 (retype_free o hd))) z_Tssss ysss;
   395     val zssss_hd = map2 (map2 (map2 (retype_free o hd))) z_Tssss ysss;
   397     val (zssss_tl, lthy) =
   396     val (zssss_tl, lthy) =
   398       lthy
   397       lthy
   410 
   409 
   411     val ctr_Tsss' = map repair_arity ctr_Tsss;
   410     val ctr_Tsss' = map repair_arity ctr_Tsss;
   412     val f_sum_prod_Ts = map range_type fun_Ts;
   411     val f_sum_prod_Ts = map range_type fun_Ts;
   413     val f_prod_Tss = map2 dest_sumTN_balanced ns f_sum_prod_Ts;
   412     val f_prod_Tss = map2 dest_sumTN_balanced ns f_sum_prod_Ts;
   414     val f_Tsss = map2 (map2 (dest_tupleT o length)) ctr_Tsss' f_prod_Tss;
   413     val f_Tsss = map2 (map2 (dest_tupleT o length)) ctr_Tsss' f_prod_Tss;
   415     val f_Tssss = map3 (fn C => map2 (map2 (map (curry op --> C) oo unzip_corecT)))
   414     val f_Tssss = map3 (fn C => map2 (map2 (map (curry (op -->) C) oo unzip_corecT)))
   416       Cs ctr_Tsss' f_Tsss;
   415       Cs ctr_Tsss' f_Tsss;
   417     val q_Tssss = map (map (map (fn [_] => [] | [_, T] => [mk_pred1T (domain_type T)]))) f_Tssss;
   416     val q_Tssss = map (map (map (fn [_] => [] | [_, T] => [mk_pred1T (domain_type T)]))) f_Tssss;
   418   in
   417   in
   419     (q_Tssss, f_Tsss, f_Tssss, f_sum_prod_Ts)
   418     (q_Tssss, f_Tsss, f_Tssss, f_sum_prod_Ts)
   420   end;
   419   end;
   535 
   534 
   536     val fpT_to_C as Type (_, [fpT, _]) = snd (strip_typeN nn (fastype_of (hd ctor_iters)));
   535     val fpT_to_C as Type (_, [fpT, _]) = snd (strip_typeN nn (fastype_of (hd ctor_iters)));
   537 
   536 
   538     fun generate_iter suf (f_Tss, _, fss, xssss) ctor_iter =
   537     fun generate_iter suf (f_Tss, _, fss, xssss) ctor_iter =
   539       let
   538       let
   540         val res_T = fold_rev (curry op --->) f_Tss fpT_to_C;
   539         val res_T = fold_rev (curry (op --->)) f_Tss fpT_to_C;
   541         val b = mk_binding suf;
   540         val b = mk_binding suf;
   542         val spec =
   541         val spec =
   543           mk_Trueprop_eq (lists_bmoc fss (Free (Binding.name_of b, res_T)),
   542           mk_Trueprop_eq (lists_bmoc fss (Free (Binding.name_of b, res_T)),
   544             mk_iter_body ctor_iter fss xssss);
   543             mk_iter_body ctor_iter fss xssss);
   545       in (b, spec) end;
   544       in (b, spec) end;
   554 
   553 
   555     val C_to_fpT as Type (_, [_, fpT]) = snd (strip_typeN nn (fastype_of (hd dtor_coiters)));
   554     val C_to_fpT as Type (_, [_, fpT]) = snd (strip_typeN nn (fastype_of (hd dtor_coiters)));
   556 
   555 
   557     fun generate_coiter suf ((pfss, cqfsss), (f_sum_prod_Ts, pf_Tss)) dtor_coiter =
   556     fun generate_coiter suf ((pfss, cqfsss), (f_sum_prod_Ts, pf_Tss)) dtor_coiter =
   558       let
   557       let
   559         val res_T = fold_rev (curry op --->) pf_Tss C_to_fpT;
   558         val res_T = fold_rev (curry (op --->)) pf_Tss C_to_fpT;
   560         val b = mk_binding suf;
   559         val b = mk_binding suf;
   561         val spec =
   560         val spec =
   562           mk_Trueprop_eq (lists_bmoc pfss (Free (Binding.name_of b, res_T)),
   561           mk_Trueprop_eq (lists_bmoc pfss (Free (Binding.name_of b, res_T)),
   563             mk_coiter_body cs cpss f_sum_prod_Ts cqfsss dtor_coiter);
   562             mk_coiter_body cs cpss f_sum_prod_Ts cqfsss dtor_coiter);
   564       in (b, spec) end;
   563       in (b, spec) end;
   603       let
   602       let
   604         val Type (T_name, Us) = T_of_bnf bnf;
   603         val Type (T_name, Us) = T_of_bnf bnf;
   605         val lives = lives_of_bnf bnf;
   604         val lives = lives_of_bnf bnf;
   606         val sets = sets_of_bnf bnf;
   605         val sets = sets_of_bnf bnf;
   607         fun mk_set U =
   606         fun mk_set U =
   608           (case find_index (curry op = U) lives of
   607           (case find_index (curry (op =) U) lives of
   609             ~1 => Term.dummy
   608             ~1 => Term.dummy
   610           | i => nth sets i);
   609           | i => nth sets i);
   611       in
   610       in
   612         (T_name, map mk_set Us)
   611         (T_name, map mk_set Us)
   613       end;
   612       end;
   620           let val Type (_, Ts0) = domain_type (fastype_of t) in
   619           let val Type (_, Ts0) = domain_type (fastype_of t) in
   621             Term.subst_atomic_types (Ts0 ~~ Ts) t
   620             Term.subst_atomic_types (Ts0 ~~ Ts) t
   622           end;
   621           end;
   623 
   622 
   624         fun mk_raw_prem_prems _ (x as Free (_, Type _)) (X as TFree _) =
   623         fun mk_raw_prem_prems _ (x as Free (_, Type _)) (X as TFree _) =
   625             [([], (find_index (curry op = X) Xs + 1, x))]
   624             [([], (find_index (curry (op =) X) Xs + 1, x))]
   626           | mk_raw_prem_prems names_lthy (x as Free (s, Type (T_name, Ts0))) (Type (_, Xs_Ts0)) =
   625           | mk_raw_prem_prems names_lthy (x as Free (s, Type (T_name, Ts0))) (Type (_, Xs_Ts0)) =
   627             (case AList.lookup (op =) setss_nested T_name of
   626             (case AList.lookup (op =) setss_nested T_name of
   628               NONE => []
   627               NONE => []
   629             | SOME raw_sets0 =>
   628             | SOME raw_sets0 =>
   630               let
   629               let
   660 
   659 
   661         val raw_premss = map4 (map3 o mk_raw_prem) ps ctrss ctr_Tsss ctrXs_Tsss;
   660         val raw_premss = map4 (map3 o mk_raw_prem) ps ctrss ctr_Tsss ctrXs_Tsss;
   662 
   661 
   663         val goal =
   662         val goal =
   664           Library.foldr (Logic.list_implies o apfst (map mk_prem)) (raw_premss,
   663           Library.foldr (Logic.list_implies o apfst (map mk_prem)) (raw_premss,
   665             HOLogic.mk_Trueprop (Library.foldr1 HOLogic.mk_conj (map2 (curry op $) ps us)));
   664             HOLogic.mk_Trueprop (Library.foldr1 HOLogic.mk_conj (map2 (curry (op $)) ps us)));
   666 
   665 
   667         val kksss = map (map (map (fst o snd) o #2)) raw_premss;
   666         val kksss = map (map (map (fst o snd) o #2)) raw_premss;
   668 
   667 
   669         val ctor_induct' = ctor_induct OF (map mk_sumEN_tupled_balanced mss);
   668         val ctor_induct' = ctor_induct OF (map mk_sumEN_tupled_balanced mss);
   670 
   669 
   779         val uv_eqs = map2 (curry HOLogic.mk_eq) us vs;
   778         val uv_eqs = map2 (curry HOLogic.mk_eq) us vs;
   780         val strong_rs =
   779         val strong_rs =
   781           map4 (fn u => fn v => fn uvr => fn uv_eq =>
   780           map4 (fn u => fn v => fn uvr => fn uv_eq =>
   782             fold_rev Term.lambda [u, v] (HOLogic.mk_disj (uvr, uv_eq))) us vs uvrs uv_eqs;
   781             fold_rev Term.lambda [u, v] (HOLogic.mk_disj (uvr, uv_eq))) us vs uvrs uv_eqs;
   783 
   782 
   784         fun build_rel rs' T =
   783         fun build_the_rel rs' T Xs_T =
   785           (case find_index (curry op = T) fpTs of
   784           build_rel lthy (fn (_, X) => nth rs' (find_index (curry (op =) X) Xs)) (T, Xs_T)
   786             ~1 =>
   785           |> Term.subst_atomic_types (Xs ~~ fpTs);
   787             if exists_subtype_in fpTs T then
   786 
   788               let
   787         fun build_rel_app rs' usel vsel Xs_T =
   789                 val Type (s, Ts) = T
   788           fold rapp [usel, vsel] (build_the_rel rs' (fastype_of usel) Xs_T);
   790                 val bnf = the (bnf_of lthy s);
   789 
   791                 val live = live_of_bnf bnf;
   790         fun mk_prem_ctr_concls rs' n k udisc usels vdisc vsels ctrXs_Ts =
   792                 val rel = mk_rel live Ts Ts (rel_of_bnf bnf);
       
   793                 val Ts' = map domain_type (fst (strip_typeN live (fastype_of rel)));
       
   794               in Term.list_comb (rel, map (build_rel rs') Ts') end
       
   795             else
       
   796               HOLogic.eq_const T
       
   797           | kk => nth rs' kk);
       
   798 
       
   799         fun build_rel_app rs' usel vsel = fold rapp [usel, vsel] (build_rel rs' (fastype_of usel));
       
   800 
       
   801         fun mk_prem_ctr_concls rs' n k udisc usels vdisc vsels =
       
   802           (if k = n then [] else [HOLogic.mk_eq (udisc, vdisc)]) @
   791           (if k = n then [] else [HOLogic.mk_eq (udisc, vdisc)]) @
   803           (if null usels then
   792           (if null usels then
   804              []
   793              []
   805            else
   794            else
   806              [Library.foldr HOLogic.mk_imp (if n = 1 then [] else [udisc, vdisc],
   795              [Library.foldr HOLogic.mk_imp (if n = 1 then [] else [udisc, vdisc],
   807                 Library.foldr1 HOLogic.mk_conj (map2 (build_rel_app rs') usels vsels))]);
   796                 Library.foldr1 HOLogic.mk_conj (map3 (build_rel_app rs') usels vsels ctrXs_Ts))]);
   808 
   797 
   809         fun mk_prem_concl rs' n udiscs uselss vdiscs vselss =
   798         fun mk_prem_concl rs' n udiscs uselss vdiscs vselss ctrXs_Tss =
   810           Library.foldr1 HOLogic.mk_conj
   799           Library.foldr1 HOLogic.mk_conj (flat (map6 (mk_prem_ctr_concls rs' n)
   811             (flat (map5 (mk_prem_ctr_concls rs' n) (1 upto n) udiscs uselss vdiscs vselss))
   800             (1 upto n) udiscs uselss vdiscs vselss ctrXs_Tss))
   812           handle List.Empty => @{term True};
   801           handle List.Empty => @{term True};
   813 
   802 
   814         fun mk_prem rs' uvr u v n udiscs uselss vdiscs vselss =
   803         fun mk_prem rs' uvr u v n udiscs uselss vdiscs vselss ctrXs_Tss =
   815           fold_rev Logic.all [u, v] (Logic.mk_implies (HOLogic.mk_Trueprop uvr,
   804           fold_rev Logic.all [u, v] (Logic.mk_implies (HOLogic.mk_Trueprop uvr,
   816             HOLogic.mk_Trueprop (mk_prem_concl rs' n udiscs uselss vdiscs vselss)));
   805             HOLogic.mk_Trueprop (mk_prem_concl rs' n udiscs uselss vdiscs vselss ctrXs_Tss)));
   817 
   806 
   818         val concl =
   807         val concl =
   819           HOLogic.mk_Trueprop (Library.foldr1 HOLogic.mk_conj
   808           HOLogic.mk_Trueprop (Library.foldr1 HOLogic.mk_conj
   820             (map3 (fn uvr => fn u => fn v => HOLogic.mk_imp (uvr, HOLogic.mk_eq (u, v)))
   809             (map3 (fn uvr => fn u => fn v => HOLogic.mk_imp (uvr, HOLogic.mk_eq (u, v)))
   821                uvrs us vs));
   810                uvrs us vs));
   822 
   811 
   823         fun mk_goal rs' =
   812         fun mk_goal rs' =
   824           Logic.list_implies (map8 (mk_prem rs') uvrs us vs ns udiscss uselsss vdiscss vselsss,
   813           Logic.list_implies (map9 (mk_prem rs') uvrs us vs ns udiscss uselsss vdiscss vselsss
   825             concl);
   814             ctrXs_Tsss, concl);
   826 
   815 
   827         val goals = map mk_goal [rs, strong_rs];
   816         val goals = map mk_goal [rs, strong_rs];
   828 
   817 
   829         fun prove dtor_coinduct' goal =
   818         fun prove dtor_coinduct' goal =
   830           Goal.prove_sorry lthy [] [] goal (fn {context = ctxt, ...} =>
   819           Goal.prove_sorry lthy [] [] goal (fn {context = ctxt, ...} =>