src/HOL/BNF/Tools/bnf_gfp_rec_sugar.ML
changeset 54951 e25b4d22082b
parent 54948 516adecd99dd
child 54954 a4ef9253a0b8
equal deleted inserted replaced
54950:f00012c20344 54951:e25b4d22082b
   566       user_eqn = user_eqn
   566       user_eqn = user_eqn
   567     }, matchedsss')
   567     }, matchedsss')
   568   end;
   568   end;
   569 
   569 
   570 fun dissect_coeqn_sel fun_names (basic_ctr_specss : basic_corec_ctr_spec list list) eqn_pos
   570 fun dissect_coeqn_sel fun_names (basic_ctr_specss : basic_corec_ctr_spec list list) eqn_pos
   571     ctr_rhs_opt code_rhs_opt eqn' of_spec_opt eqn =
   571     ctr_rhs_opt code_rhs_opt eqn0 of_spec_opt eqn =
   572   let
   572   let
   573     val (lhs, rhs) = HOLogic.dest_eq eqn
   573     val (lhs, rhs) = HOLogic.dest_eq eqn
   574       handle TERM _ =>
   574       handle TERM _ =>
   575         primcorec_error_eqn "malformed function equation (expected \"lhs = rhs\")" eqn;
   575         primcorec_error_eqn "malformed function equation (expected \"lhs = rhs\")" eqn;
   576     val sel = head_of lhs;
   576     val sel = head_of lhs;
   583     val {ctr, ...} =
   583     val {ctr, ...} =
   584       (case of_spec_opt of
   584       (case of_spec_opt of
   585         SOME of_spec => the (find_first (curry (op =) of_spec o #ctr) basic_ctr_specs)
   585         SOME of_spec => the (find_first (curry (op =) of_spec o #ctr) basic_ctr_specs)
   586       | NONE => filter (exists (curry (op =) sel) o #sels) basic_ctr_specs |> the_single
   586       | NONE => filter (exists (curry (op =) sel) o #sels) basic_ctr_specs |> the_single
   587           handle List.Empty => primcorec_error_eqn "ambiguous selector - use \"of\"" eqn);
   587           handle List.Empty => primcorec_error_eqn "ambiguous selector - use \"of\"" eqn);
   588     val user_eqn = drop_All eqn';
   588     val user_eqn = drop_All eqn0;
   589   in
   589   in
   590     Sel {
   590     Sel {
   591       fun_name = fun_name,
   591       fun_name = fun_name,
   592       fun_T = fun_T,
   592       fun_T = fun_T,
   593       fun_args = fun_args,
   593       fun_args = fun_args,
   600       user_eqn = user_eqn
   600       user_eqn = user_eqn
   601     }
   601     }
   602   end;
   602   end;
   603 
   603 
   604 fun dissect_coeqn_ctr fun_names sequentials (basic_ctr_specss : basic_corec_ctr_spec list list)
   604 fun dissect_coeqn_ctr fun_names sequentials (basic_ctr_specss : basic_corec_ctr_spec list list)
   605     eqn_pos eqn' code_rhs_opt prems concl matchedsss =
   605     eqn_pos eqn0 code_rhs_opt prems concl matchedsss =
   606   let
   606   let
   607     val (lhs, rhs) = HOLogic.dest_eq concl;
   607     val (lhs, rhs) = HOLogic.dest_eq concl;
   608     val (fun_name, fun_args) = strip_comb lhs |>> fst o dest_Free;
   608     val (fun_name, fun_args) = strip_comb lhs |>> fst o dest_Free;
   609     val SOME basic_ctr_specs = AList.lookup (op =) (fun_names ~~ basic_ctr_specss) fun_name;
   609     val SOME basic_ctr_specs = AList.lookup (op =) (fun_names ~~ basic_ctr_specss) fun_name;
   610     val (ctr, ctr_args) = strip_comb (unfold_let rhs);
   610     val (ctr, ctr_args) = strip_comb (unfold_let rhs);
   628  space_implode "\n    \<cdot> " (map (Syntax.string_of_term @{context}) prems));
   628  space_implode "\n    \<cdot> " (map (Syntax.string_of_term @{context}) prems));
   629 *)
   629 *)
   630 
   630 
   631     val eqns_data_sel =
   631     val eqns_data_sel =
   632       map (dissect_coeqn_sel fun_names basic_ctr_specss eqn_pos
   632       map (dissect_coeqn_sel fun_names basic_ctr_specss eqn_pos
   633         (SOME (abstract (List.rev fun_args) rhs)) code_rhs_opt eqn' (SOME ctr)) sel_concls;
   633         (SOME (abstract (List.rev fun_args) rhs)) code_rhs_opt eqn0 (SOME ctr)) sel_concls;
   634   in
   634   in
   635     (the_list eqn_data_disc_opt @ eqns_data_sel, matchedsss')
   635     (the_list eqn_data_disc_opt @ eqns_data_sel, matchedsss')
   636   end;
   636   end;
   637 
   637 
   638 fun dissect_coeqn_code lthy has_call fun_names basic_ctr_specss eqn_pos eqn' concl matchedsss =
   638 fun dissect_coeqn_code lthy has_call fun_names basic_ctr_specss eqn_pos eqn0 concl matchedsss =
   639   let
   639   let
   640     val (lhs, (rhs', rhs)) = HOLogic.dest_eq concl ||> `(expand_corec_code_rhs lthy has_call []);
   640     val (lhs, (rhs', rhs)) = HOLogic.dest_eq concl ||> `(expand_corec_code_rhs lthy has_call []);
   641     val (fun_name, fun_args) = strip_comb lhs |>> fst o dest_Free;
   641     val (fun_name, fun_args) = strip_comb lhs |>> fst o dest_Free;
   642     val SOME basic_ctr_specs = AList.lookup (op =) (fun_names ~~ basic_ctr_specss) fun_name;
   642     val SOME basic_ctr_specs = AList.lookup (op =) (fun_names ~~ basic_ctr_specss) fun_name;
   643 
   643 
   655         |> curry list_comb ctr
   655         |> curry list_comb ctr
   656         |> curry HOLogic.mk_eq lhs);
   656         |> curry HOLogic.mk_eq lhs);
   657 
   657 
   658     val sequentials = replicate (length fun_names) false;
   658     val sequentials = replicate (length fun_names) false;
   659   in
   659   in
   660     fold_map2 (dissect_coeqn_ctr fun_names sequentials basic_ctr_specss eqn_pos eqn'
   660     fold_map2 (dissect_coeqn_ctr fun_names sequentials basic_ctr_specss eqn_pos eqn0
   661         (SOME (abstract (List.rev fun_args) rhs)))
   661         (SOME (abstract (List.rev fun_args) rhs)))
   662       ctr_premss ctr_concls matchedsss
   662       ctr_premss ctr_concls matchedsss
   663   end;
   663   end;
   664 
   664 
   665 fun dissect_coeqn lthy has_call fun_names sequentials
   665 fun dissect_coeqn lthy has_call fun_names sequentials
   666     (basic_ctr_specss : basic_corec_ctr_spec list list) (eqn_pos, eqn') of_spec_opt matchedsss =
   666     (basic_ctr_specss : basic_corec_ctr_spec list list) (eqn_pos, eqn0) of_spec_opt matchedsss =
   667   let
   667   let
   668     val eqn = drop_All eqn'
   668     val eqn = drop_All eqn0
   669       handle TERM _ => primcorec_error_eqn "malformed function equation" eqn';
   669       handle TERM _ => primcorec_error_eqn "malformed function equation" eqn0;
   670     val (prems, concl) = Logic.strip_horn eqn
   670     val (prems, concl) = Logic.strip_horn eqn
   671       |> apfst (map HOLogic.dest_Trueprop) o apsnd HOLogic.dest_Trueprop;
   671       |> apfst (map HOLogic.dest_Trueprop) o apsnd HOLogic.dest_Trueprop;
   672 
   672 
   673     val head = concl
   673     val head = concl
   674       |> perhaps (try HOLogic.dest_not) |> perhaps (try (fst o HOLogic.dest_eq))
   674       |> perhaps (try HOLogic.dest_not) |> perhaps (try (fst o HOLogic.dest_eq))
   679     val discs = maps (map #disc) basic_ctr_specss;
   679     val discs = maps (map #disc) basic_ctr_specss;
   680     val sels = maps (maps #sels) basic_ctr_specss;
   680     val sels = maps (maps #sels) basic_ctr_specss;
   681     val ctrs = maps (map #ctr) basic_ctr_specss;
   681     val ctrs = maps (map #ctr) basic_ctr_specss;
   682   in
   682   in
   683     if member (op =) discs head orelse
   683     if member (op =) discs head orelse
   684       is_some rhs_opt andalso
   684         is_some rhs_opt andalso
   685         member (op =) (filter (null o binder_types o fastype_of) ctrs) (the rhs_opt) then
   685           member (op =) (filter (null o binder_types o fastype_of) ctrs) (the rhs_opt) then
   686       dissect_coeqn_disc fun_names sequentials basic_ctr_specss eqn_pos NONE NONE prems concl matchedsss
   686       dissect_coeqn_disc fun_names sequentials basic_ctr_specss eqn_pos NONE NONE prems concl
       
   687         matchedsss
   687       |>> single
   688       |>> single
   688     else if member (op =) sels head then
   689     else if member (op =) sels head then
   689       ([dissect_coeqn_sel fun_names basic_ctr_specss eqn_pos NONE NONE eqn' of_spec_opt concl],
   690       ([dissect_coeqn_sel fun_names basic_ctr_specss eqn_pos NONE NONE eqn0 of_spec_opt concl],
   690        matchedsss)
   691        matchedsss)
   691     else if is_Free head andalso member (op =) fun_names (fst (dest_Free head)) andalso
   692     else if is_Free head andalso member (op =) fun_names (fst (dest_Free head)) then
   692       member (op =) ctrs (head_of (unfold_let (the rhs_opt))) then
   693       if member (op =) ctrs (head_of (unfold_let (the rhs_opt))) then
   693       dissect_coeqn_ctr fun_names sequentials basic_ctr_specss eqn_pos eqn' NONE prems concl matchedsss
   694         dissect_coeqn_ctr fun_names sequentials basic_ctr_specss eqn_pos eqn0
   694     else if is_Free head andalso member (op =) fun_names (fst (dest_Free head)) andalso
   695           (if null prems then SOME eqn0 else NONE) prems concl matchedsss
   695       null prems then
   696       else if null prems then
   696       dissect_coeqn_code lthy has_call fun_names basic_ctr_specss eqn_pos eqn' concl matchedsss
   697         dissect_coeqn_code lthy has_call fun_names basic_ctr_specss eqn_pos eqn0 concl matchedsss
   697       |>> flat
   698         |>> flat
       
   699       else
       
   700         primcorec_error_eqn "malformed constructor or code view equation" eqn
   698     else
   701     else
   699       primcorec_error_eqn "malformed function equation" eqn
   702       primcorec_error_eqn "malformed function equation" eqn
   700   end;
   703   end;
   701 
   704 
   702 fun build_corec_arg_disc (ctr_specs : corec_ctr_spec list)
   705 fun build_corec_arg_disc (ctr_specs : corec_ctr_spec list)
   937 val _ = tracing ("exclusiveness properties:\n    \<cdot> " ^
   940 val _ = tracing ("exclusiveness properties:\n    \<cdot> " ^
   938  space_implode "\n    \<cdot> " (maps (map (Syntax.string_of_term lthy o snd)) excludess'));
   941  space_implode "\n    \<cdot> " (maps (map (Syntax.string_of_term lthy o snd)) excludess'));
   939 *)
   942 *)
   940 
   943 
   941     val excludess'' = map2 (fn sequential => map (fn (idx, goal) =>
   944     val excludess'' = map2 (fn sequential => map (fn (idx, goal) =>
   942         (idx, (Option.map (Goal.prove lthy [] [] goal #> Thm.close_derivation)
   945         (idx, (Option.map (Goal.prove_sorry lthy [] [] goal #> Thm.close_derivation)
   943            (exclude_tac sequential idx), goal))))
   946            (exclude_tac sequential idx), goal))))
   944       sequentials excludess';
   947       sequentials excludess';
   945     val taut_thmss = map (map (apsnd (the o fst)) o filter (is_some o fst o snd)) excludess'';
   948     val taut_thmss = map (map (apsnd (the o fst)) o filter (is_some o fst o snd)) excludess'';
   946     val (goal_idxss, goalss') = excludess''
   949     val (goal_idxss, goalss') = excludess''
   947       |> map (map (apsnd (rpair [] o snd)) o filter (is_none o fst o snd))
   950       |> map (map (apsnd (rpair [] o snd)) o filter (is_none o fst o snd))
   958         disc_eqnss;
   961         disc_eqnss;
   959     val de_facto_exhaustives =
   962     val de_facto_exhaustives =
   960       map2 (fn b => fn b' => b orelse b') exhaustives syntactic_exhaustives;
   963       map2 (fn b => fn b' => b orelse b') exhaustives syntactic_exhaustives;
   961 
   964 
   962     fun map_prove_with_tac tac =
   965     fun map_prove_with_tac tac =
   963       map (fn goal => Goal.prove lthy [] [] goal tac |> Thm.close_derivation);
   966       map (fn goal => Goal.prove_sorry lthy [] [] goal tac |> Thm.close_derivation);
   964 
   967 
   965     val nchotomy_goalss =
   968     val nchotomy_goalss =
   966       map2 (fn false => K [] | true => single o HOLogic.mk_Trueprop o mk_dnf o map #prems)
   969       map2 (fn false => K [] | true => single o HOLogic.mk_Trueprop o mk_dnf o map #prems)
   967         de_facto_exhaustives disc_eqnss
   970         de_facto_exhaustives disc_eqnss
   968       |> list_all_fun_args []
   971       |> list_all_fun_args []
  1002           |> list_all_fun_args ps
  1005           |> list_all_fun_args ps
  1003           |> map3 (fn disc_eqns as {fun_args, ...} :: _ => fn [] => K []
  1006           |> map3 (fn disc_eqns as {fun_args, ...} :: _ => fn [] => K []
  1004               | [nchotomy_thm] => fn [goal] =>
  1007               | [nchotomy_thm] => fn [goal] =>
  1005                 [mk_primcorec_exhaust_tac lthy ("" (* for "P" *) :: map (fst o dest_Free) fun_args)
  1008                 [mk_primcorec_exhaust_tac lthy ("" (* for "P" *) :: map (fst o dest_Free) fun_args)
  1006                    (length disc_eqns) nchotomy_thm
  1009                    (length disc_eqns) nchotomy_thm
  1007                  |> K |> Goal.prove lthy [] [] goal
  1010                  |> K |> Goal.prove_sorry lthy [] [] goal
  1008                  |> Thm.close_derivation])
  1011                  |> Thm.close_derivation])
  1009             disc_eqnss nchotomy_thmss;
  1012             disc_eqnss nchotomy_thmss;
  1010         val nontriv_exhaust_thmss = map (filter_out is_trivial_implies) exhaust_thmss;
  1013         val nontriv_exhaust_thmss = map (filter_out is_trivial_implies) exhaust_thmss;
  1011 
  1014 
  1012         val excludess' = map (op ~~) (goal_idxss ~~ exclude_thmss);
  1015         val excludess' = map (op ~~) (goal_idxss ~~ exclude_thmss);
  1035             in
  1038             in
  1036               if prems = [@{term False}] then
  1039               if prems = [@{term False}] then
  1037                 []
  1040                 []
  1038               else
  1041               else
  1039                 mk_primcorec_disc_tac lthy def_thms disc_corec k m excludesss
  1042                 mk_primcorec_disc_tac lthy def_thms disc_corec k m excludesss
  1040                 |> K |> Goal.prove lthy [] [] goal
  1043                 |> K |> Goal.prove_sorry lthy [] [] goal
  1041                 |> Thm.close_derivation
  1044                 |> Thm.close_derivation
  1042                 |> pair (#disc (nth ctr_specs ctr_no))
  1045                 |> pair (#disc (nth ctr_specs ctr_no))
  1043                 |> pair eqn_pos
  1046                 |> pair eqn_pos
  1044                 |> single
  1047                 |> single
  1045             end;
  1048             end;
  1065               |> curry Logic.list_all (map dest_Free fun_args);
  1068               |> curry Logic.list_all (map dest_Free fun_args);
  1066             val (distincts, _, sel_splits, sel_split_asms) = case_thms_of_term lthy [] rhs_term;
  1069             val (distincts, _, sel_splits, sel_split_asms) = case_thms_of_term lthy [] rhs_term;
  1067           in
  1070           in
  1068             mk_primcorec_sel_tac lthy def_thms distincts sel_splits sel_split_asms nested_map_idents
  1071             mk_primcorec_sel_tac lthy def_thms distincts sel_splits sel_split_asms nested_map_idents
  1069               nested_map_comps sel_corec k m excludesss
  1072               nested_map_comps sel_corec k m excludesss
  1070             |> K |> Goal.prove lthy [] [] goal
  1073             |> K |> Goal.prove_sorry lthy [] [] goal
  1071             |> Thm.close_derivation
  1074             |> Thm.close_derivation
  1072             |> pair sel
  1075             |> pair sel
  1073             |> pair eqn_pos
  1076             |> pair eqn_pos
  1074           end;
  1077           end;
  1075 
  1078 
  1079           if not (exists (curry (op =) ctr o #ctr) disc_eqns)
  1082           if not (exists (curry (op =) ctr o #ctr) disc_eqns)
  1080               andalso not (exists (curry (op =) ctr o #ctr) sel_eqns)
  1083               andalso not (exists (curry (op =) ctr o #ctr) sel_eqns)
  1081             orelse
  1084             orelse
  1082               filter (curry (op =) ctr o #ctr) sel_eqns
  1085               filter (curry (op =) ctr o #ctr) sel_eqns
  1083               |> fst o finds ((op =) o apsnd #sel) sels
  1086               |> fst o finds ((op =) o apsnd #sel) sels
  1084               |> exists (null o snd)
  1087               |> exists (null o snd) then
  1085           then [] else
  1088             []
       
  1089           else
  1086             let
  1090             let
  1087               val (fun_name, fun_T, fun_args, prems, rhs_opt, eqn_pos) =
  1091               val (fun_name, fun_T, fun_args, prems, rhs_opt, eqn_pos) =
  1088                 (find_first (curry (op =) ctr o #ctr) disc_eqns,
  1092                 (find_first (curry (op =) ctr o #ctr) disc_eqns,
  1089                  find_first (curry (op =) ctr o #ctr) sel_eqns)
  1093                  find_first (curry (op =) ctr o #ctr) sel_eqns)
  1090                 |>> Option.map (fn x => (#fun_name x, #fun_T x, #fun_args x, #prems x,
  1094                 |>> Option.map (fn x => (#fun_name x, #fun_T x, #fun_args x, #prems x,
  1107               val disc_thm_opt = AList.lookup (op =) disc_alist disc;
  1111               val disc_thm_opt = AList.lookup (op =) disc_alist disc;
  1108               val sel_thms = map snd (filter (member (op =) sels o fst) sel_alist);
  1112               val sel_thms = map snd (filter (member (op =) sels o fst) sel_alist);
  1109             in
  1113             in
  1110               if prems = [@{term False}] then [] else
  1114               if prems = [@{term False}] then [] else
  1111                 mk_primcorec_ctr_of_dtr_tac lthy m collapse disc_thm_opt sel_thms
  1115                 mk_primcorec_ctr_of_dtr_tac lthy m collapse disc_thm_opt sel_thms
  1112                 |> K |> Goal.prove lthy [] [] goal
  1116                 |> K |> Goal.prove_sorry lthy [] [] goal
  1113                 |> Thm.close_derivation
  1117                 |> Thm.close_derivation
  1114                 |> pair ctr
  1118                 |> pair ctr
  1115                 |> pair eqn_pos
  1119                 |> pair eqn_pos
  1116                 |> single
  1120                 |> single
  1117             end;
  1121             end;
  1189                       case_thms_of_term lthy bound_Ts raw_rhs;
  1193                       case_thms_of_term lthy bound_Ts raw_rhs;
  1190 
  1194 
  1191                     val raw_code_thm = mk_primcorec_raw_code_of_ctr_tac lthy distincts discIs
  1195                     val raw_code_thm = mk_primcorec_raw_code_of_ctr_tac lthy distincts discIs
  1192                         sel_splits sel_split_asms ms ctr_thms
  1196                         sel_splits sel_split_asms ms ctr_thms
  1193                         (if exhaustive_code then try the_single nchotomys else NONE)
  1197                         (if exhaustive_code then try the_single nchotomys else NONE)
  1194                       |> K |> Goal.prove lthy [] [] raw_goal
  1198                       |> K |> Goal.prove_sorry lthy [] [] raw_goal
  1195                       |> Thm.close_derivation;
  1199                       |> Thm.close_derivation;
  1196                   in
  1200                   in
  1197                     mk_primcorec_code_of_raw_code_tac lthy distincts sel_splits raw_code_thm
  1201                     mk_primcorec_code_of_raw_code_tac lthy distincts sel_splits raw_code_thm
  1198                     |> K |> Goal.prove lthy [] [] goal
  1202                     |> K |> Goal.prove_sorry lthy [] [] goal
  1199                     |> Thm.close_derivation
  1203                     |> Thm.close_derivation
  1200                     |> single
  1204                     |> single
  1201                   end)
  1205                   end)
  1202               end)
  1206               end)
  1203           end;
  1207           end;
  1225               if prems = [@{term False}] then
  1229               if prems = [@{term False}] then
  1226                 []
  1230                 []
  1227               else
  1231               else
  1228                 mk_primcorec_disc_iff_tac lthy (map (fst o dest_Free) fun_args)
  1232                 mk_primcorec_disc_iff_tac lthy (map (fst o dest_Free) fun_args)
  1229                   (the_single exhaust_thms) (the_single disc_thms) disc_thmss' (flat disc_excludess)
  1233                   (the_single exhaust_thms) (the_single disc_thms) disc_thmss' (flat disc_excludess)
  1230                 |> K |> Goal.prove lthy [] [] goal
  1234                 |> K |> Goal.prove_sorry lthy [] [] goal
  1231                 |> Thm.close_derivation
  1235                 |> Thm.close_derivation
  1232                 |> pair eqn_pos
  1236                 |> pair eqn_pos
  1233                 |> single
  1237                 |> single
  1234             end;
  1238             end;
  1235 
  1239