src/HOL/Tools/Nitpick/nitpick_hol.ML
changeset 57228 d52012eabf0d
parent 57227 4c2156fdfe71
child 57964 3dfc1bf3ac3d
equal deleted inserted replaced
57227:4c2156fdfe71 57228:d52012eabf0d
    96   val is_boolean_type : typ -> bool
    96   val is_boolean_type : typ -> bool
    97   val is_integer_type : typ -> bool
    97   val is_integer_type : typ -> bool
    98   val is_bit_type : typ -> bool
    98   val is_bit_type : typ -> bool
    99   val is_word_type : typ -> bool
    99   val is_word_type : typ -> bool
   100   val is_integer_like_type : typ -> bool
   100   val is_integer_like_type : typ -> bool
   101   val is_record_type : typ -> bool
       
   102   val is_number_type : Proof.context -> typ -> bool
   101   val is_number_type : Proof.context -> typ -> bool
   103   val is_higher_order_type : typ -> bool
   102   val is_higher_order_type : typ -> bool
   104   val elem_type : typ -> typ
   103   val elem_type : typ -> typ
   105   val pseudo_domain_type : typ -> typ
   104   val pseudo_domain_type : typ -> typ
   106   val pseudo_range_type : typ -> typ
   105   val pseudo_range_type : typ -> typ
   114   val is_codatatype : Proof.context -> typ -> bool
   113   val is_codatatype : Proof.context -> typ -> bool
   115   val is_quot_type : Proof.context -> typ -> bool
   114   val is_quot_type : Proof.context -> typ -> bool
   116   val is_pure_typedef : Proof.context -> typ -> bool
   115   val is_pure_typedef : Proof.context -> typ -> bool
   117   val is_univ_typedef : Proof.context -> typ -> bool
   116   val is_univ_typedef : Proof.context -> typ -> bool
   118   val is_data_type : Proof.context -> typ -> bool
   117   val is_data_type : Proof.context -> typ -> bool
   119   val is_record_constr : string * typ -> bool
       
   120   val is_record_get : theory -> string * typ -> bool
   118   val is_record_get : theory -> string * typ -> bool
   121   val is_record_update : theory -> string * typ -> bool
   119   val is_record_update : theory -> string * typ -> bool
   122   val is_abs_fun : Proof.context -> string * typ -> bool
   120   val is_abs_fun : Proof.context -> string * typ -> bool
   123   val is_rep_fun : Proof.context -> string * typ -> bool
   121   val is_rep_fun : Proof.context -> string * typ -> bool
   124   val is_quot_abs_fun : Proof.context -> string * typ -> bool
   122   val is_quot_abs_fun : Proof.context -> string * typ -> bool
   521 fun is_word_type (Type (@{type_name word}, _)) = true
   519 fun is_word_type (Type (@{type_name word}, _)) = true
   522   | is_word_type _ = false
   520   | is_word_type _ = false
   523 
   521 
   524 val is_integer_like_type = is_iterator_type orf is_integer_type orf is_word_type
   522 val is_integer_like_type = is_iterator_type orf is_integer_type orf is_word_type
   525 
   523 
   526 val is_record_type = not o null o Record.dest_recTs
       
   527 
       
   528 fun is_frac_type ctxt (Type (s, [])) =
   524 fun is_frac_type ctxt (Type (s, [])) =
   529     s |> AList.defined (op =) (#frac_types (Data.get (Context.Proof ctxt)))
   525     s |> AList.defined (op =) (#frac_types (Data.get (Context.Proof ctxt)))
   530   | is_frac_type _ _ = false
   526   | is_frac_type _ _ = false
   531 
   527 
   532 fun is_number_type ctxt = is_integer_like_type orf is_frac_type ctxt
   528 fun is_number_type ctxt = is_integer_like_type orf is_frac_type ctxt
   711 
   707 
   712 fun is_pure_typedef ctxt (T as Type (s, _)) =
   708 fun is_pure_typedef ctxt (T as Type (s, _)) =
   713     is_frac_type ctxt T orelse
   709     is_frac_type ctxt T orelse
   714     (is_raw_typedef ctxt s andalso
   710     (is_raw_typedef ctxt s andalso
   715      not (is_raw_free_datatype ctxt s orelse is_raw_quot_type ctxt T orelse
   711      not (is_raw_free_datatype ctxt s orelse is_raw_quot_type ctxt T orelse
   716           is_codatatype ctxt T orelse is_record_type T orelse
   712        is_codatatype ctxt T orelse is_integer_like_type T))
   717           is_integer_like_type T))
       
   718   | is_pure_typedef _ _ = false
   713   | is_pure_typedef _ _ = false
   719 
   714 
   720 fun is_univ_typedef ctxt (Type (s, _)) =
   715 fun is_univ_typedef ctxt (Type (s, _)) =
   721     (case typedef_info ctxt s of
   716     (case typedef_info ctxt s of
   722        SOME {prop_of_Rep, ...} =>
   717        SOME {prop_of_Rep, ...} =>
   748   let val (recs, more) = Record.get_extT_fields thy T in
   743   let val (recs, more) = Record.get_extT_fields thy T in
   749     recs @ more :: all_record_fields thy (snd more)
   744     recs @ more :: all_record_fields thy (snd more)
   750   end
   745   end
   751   handle TYPE _ => []
   746   handle TYPE _ => []
   752 
   747 
   753 fun is_record_constr (s, T) =
       
   754   String.isSuffix Record.extN s andalso
       
   755   let val dataT = body_type T in
       
   756     is_record_type dataT andalso
       
   757     s = unsuffix Record.ext_typeN (fst (dest_Type dataT)) ^ Record.extN
       
   758   end
       
   759 
       
   760 val num_record_fields = Integer.add 1 o length o fst oo Record.get_extT_fields
   748 val num_record_fields = Integer.add 1 o length o fst oo Record.get_extT_fields
   761 
   749 
   762 fun no_of_record_field thy s T1 =
   750 fun no_of_record_field thy s T1 =
   763   find_index (curry (op =) s o fst)
   751   find_index (curry (op =) s o fst) (Record.get_extT_fields thy T1 ||> single |> op @)
   764              (Record.get_extT_fields thy T1 ||> single |> op @)
       
   765 
   752 
   766 fun is_record_get thy (s, Type (@{type_name fun}, [T1, _])) =
   753 fun is_record_get thy (s, Type (@{type_name fun}, [T1, _])) =
   767     exists (curry (op =) s o fst) (all_record_fields thy T1)
   754     exists (curry (op =) s o fst) (all_record_fields thy T1)
   768   | is_record_get _ _ = false
   755   | is_record_get _ _ = false
   769 
   756 
   770 fun is_record_update thy (s, T) =
   757 fun is_record_update thy (s, T) =
   771   String.isSuffix Record.updateN s andalso
   758   String.isSuffix Record.updateN s andalso
   772   exists (curry (op =) (unsuffix Record.updateN s) o fst)
   759   exists (curry (op =) (unsuffix Record.updateN s) o fst) (all_record_fields thy (body_type T))
   773          (all_record_fields thy (body_type T))
       
   774   handle TYPE _ => false
   760   handle TYPE _ => false
   775 
   761 
   776 fun is_abs_fun ctxt (s, Type (@{type_name fun}, [_, Type (s', _)])) =
   762 fun is_abs_fun ctxt (s, Type (@{type_name fun}, [_, Type (s', _)])) =
   777     (case typedef_info ctxt s' of
   763     (case typedef_info ctxt s' of
   778        SOME {Abs_name, ...} => s = Abs_name
   764        SOME {Abs_name, ...} => s = Abs_name
   860 fun is_nonfree_constr ctxt (s, T) =
   846 fun is_nonfree_constr ctxt (s, T) =
   861   member (op =) [@{const_name FunBox}, @{const_name PairBox},
   847   member (op =) [@{const_name FunBox}, @{const_name PairBox},
   862                  @{const_name Quot}, @{const_name Zero_Rep},
   848                  @{const_name Quot}, @{const_name Zero_Rep},
   863                  @{const_name Suc_Rep}] s orelse
   849                  @{const_name Suc_Rep}] s orelse
   864   let val (x as (_, T)) = (s, unarize_unbox_etc_type T) in
   850   let val (x as (_, T)) = (s, unarize_unbox_etc_type T) in
   865     is_raw_free_datatype_constr ctxt x orelse is_record_constr x orelse
   851     is_raw_free_datatype_constr ctxt x orelse
   866     (is_abs_fun ctxt x andalso is_pure_typedef ctxt (range_type T)) orelse
   852     (is_abs_fun ctxt x andalso is_pure_typedef ctxt (range_type T)) orelse
   867     is_registered_coconstr ctxt x
   853     is_registered_coconstr ctxt x
   868   end
   854   end
   869 
   855 
   870 fun is_free_constr ctxt (s, T) =
   856 fun is_free_constr ctxt (s, T) =
   986   #> List.foldr (s_conj o swap) @{const True}
   972   #> List.foldr (s_conj o swap) @{const True}
   987 
   973 
   988 fun zero_const T = Const (@{const_name zero_class.zero}, T)
   974 fun zero_const T = Const (@{const_name zero_class.zero}, T)
   989 fun suc_const T = Const (@{const_name Suc}, T --> T)
   975 fun suc_const T = Const (@{const_name Suc}, T --> T)
   990 
   976 
   991 fun uncached_data_type_constrs ({thy, ctxt, ...} : hol_context)
   977 fun uncached_data_type_constrs ({thy, ctxt, ...} : hol_context) (T as Type (s, _)) =
   992                                (T as Type (s, _)) =
       
   993     if is_interpreted_type s then
   978     if is_interpreted_type s then
   994       []
   979       []
   995     else
   980     else
   996       (case AList.lookup (op =) (#codatatypes (Data.get (Context.Proof ctxt)))
   981       (case AList.lookup (op =) (#codatatypes (Data.get (Context.Proof ctxt))) s of
   997                          s of
       
   998          SOME (_, xs' as (_ :: _)) => map (apsnd (repair_constr_type T)) xs'
   982          SOME (_, xs' as (_ :: _)) => map (apsnd (repair_constr_type T)) xs'
   999        | _ =>
   983        | _ =>
  1000          if is_frac_type ctxt T then
   984          if is_frac_type ctxt T then
  1001            case typedef_info ctxt s of
   985            case typedef_info ctxt s of
  1002              SOME {abs_type, rep_type, Abs_name, ...} =>
   986              SOME {abs_type, rep_type, Abs_name, ...} =>
  1003              [(Abs_name,
   987              [(Abs_name, varify_and_instantiate_type ctxt abs_type T rep_type --> T)]
  1004                varify_and_instantiate_type ctxt abs_type T rep_type --> T)]
       
  1005            | NONE => [] (* impossible *)
   988            | NONE => [] (* impossible *)
  1006          else
   989          else
  1007            case Ctr_Sugar.ctr_sugar_of ctxt s of
   990            case Ctr_Sugar.ctr_sugar_of ctxt s of
  1008              SOME {ctrs, ...} =>
   991              SOME {ctrs, ...} =>
  1009              map (apsnd (repair_constr_type T) o dest_Const) ctrs
   992              map (apsnd (repair_constr_type T) o dest_Const) ctrs
  1010            | NONE =>
   993            | NONE =>
  1011              if is_record_type T then
   994              if is_raw_quot_type ctxt T then
  1012                let
       
  1013                  val s' = unsuffix Record.ext_typeN s ^ Record.extN
       
  1014                  val T' = (Record.get_extT_fields thy T
       
  1015                           |> apsnd single |> uncurry append |> map snd) ---> T
       
  1016                in [(s', T')] end
       
  1017              else if is_raw_quot_type ctxt T then
       
  1018                [(@{const_name Quot}, rep_type_for_quot_type ctxt T --> T)]
   995                [(@{const_name Quot}, rep_type_for_quot_type ctxt T --> T)]
  1019              else case typedef_info ctxt s of
   996              else case typedef_info ctxt s of
  1020                SOME {abs_type, rep_type, Abs_name, ...} =>
   997                SOME {abs_type, rep_type, Abs_name, ...} =>
  1021                [(Abs_name,
   998                [(Abs_name, varify_and_instantiate_type ctxt abs_type T rep_type --> T)]
  1022                  varify_and_instantiate_type ctxt abs_type T rep_type --> T)]
       
  1023              | NONE =>
   999              | NONE =>
  1024                if T = @{typ ind} then
  1000                if T = @{typ ind} then [dest_Const @{const Zero_Rep}, dest_Const @{const Suc_Rep}]
  1025                  [dest_Const @{const Zero_Rep}, dest_Const @{const Suc_Rep}]
  1001                else [])
  1026                else
       
  1027                  [])
       
  1028   | uncached_data_type_constrs _ _ = []
  1002   | uncached_data_type_constrs _ _ = []
  1029 
  1003 
  1030 fun data_type_constrs (hol_ctxt as {constr_cache, ...}) T =
  1004 fun data_type_constrs (hol_ctxt as {constr_cache, ...}) T =
  1031   case AList.lookup (op =) (!constr_cache) T of
  1005   case AList.lookup (op =) (!constr_cache) T of
  1032     SOME xs => xs
  1006     SOME xs => xs
  1216   in aux Ts t handle Same.SAME => t end
  1190   in aux Ts t handle Same.SAME => t end
  1217 
  1191 
  1218 fun discr_term_for_constr hol_ctxt (x as (s, T)) =
  1192 fun discr_term_for_constr hol_ctxt (x as (s, T)) =
  1219   let val dataT = body_type T in
  1193   let val dataT = body_type T in
  1220     if s = @{const_name Suc} then
  1194     if s = @{const_name Suc} then
  1221       Abs (Name.uu, dataT,
  1195       Abs (Name.uu, dataT, @{const Not} $ HOLogic.mk_eq (zero_const dataT, Bound 0))
  1222            @{const Not} $ HOLogic.mk_eq (zero_const dataT, Bound 0))
       
  1223     else if length (data_type_constrs hol_ctxt dataT) >= 2 then
  1196     else if length (data_type_constrs hol_ctxt dataT) >= 2 then
  1224       Const (discr_for_constr x)
  1197       Const (discr_for_constr x)
  1225     else
  1198     else
  1226       Abs (Name.uu, dataT, @{const True})
  1199       Abs (Name.uu, dataT, @{const True})
  1227   end
  1200   end
  1405     | NONE =>
  1378     | NONE =>
  1406       case AList.lookup (op =) built_in_typed_consts (s, unarize_type T) of
  1379       case AList.lookup (op =) built_in_typed_consts (s, unarize_type T) of
  1407         SOME n => SOME n
  1380         SOME n => SOME n
  1408       | NONE =>
  1381       | NONE =>
  1409         case s of
  1382         case s of
  1410           @{const_name zero_class.zero} =>
  1383           @{const_name zero_class.zero} => if is_iterator_type T then SOME 0 else NONE
  1411           if is_iterator_type T then SOME 0 else NONE
  1384         | @{const_name Suc} => if is_iterator_type (domain_type T) then SOME 0 else NONE
  1412         | @{const_name Suc} =>
       
  1413           if is_iterator_type (domain_type T) then SOME 0 else NONE
       
  1414         | _ => if is_fun_type T andalso is_set_like_type (domain_type T) then
  1385         | _ => if is_fun_type T andalso is_set_like_type (domain_type T) then
  1415                  AList.lookup (op =) built_in_set_like_consts s
  1386                  AList.lookup (op =) built_in_set_like_consts s
  1416                else
  1387                else
  1417                  NONE
  1388                  NONE
  1418 
  1389 
  1672                end
  1643                end
  1673              | _ => raise TYPE ("Nitpick_HOL.optimized_record_get", [rec_T], []))
  1644              | _ => raise TYPE ("Nitpick_HOL.optimized_record_get", [rec_T], []))
  1674     | j => select_nth_constr_arg ctxt constr_x t j res_T
  1645     | j => select_nth_constr_arg ctxt constr_x t j res_T
  1675   end
  1646   end
  1676 
  1647 
  1677 fun optimized_record_update (hol_ctxt as {thy, ctxt, ...}) s rec_T fun_t
  1648 fun optimized_record_update (hol_ctxt as {thy, ctxt, ...}) s rec_T fun_t rec_t =
  1678                             rec_t =
       
  1679   let
  1649   let
  1680     val constr_x as (_, constr_T) = hd (data_type_constrs hol_ctxt rec_T)
  1650     val constr_x as (_, constr_T) = hd (data_type_constrs hol_ctxt rec_T)
  1681     val Ts = binder_types constr_T
  1651     val Ts = binder_types constr_T
  1682     val n = length Ts
  1652     val n = length Ts
  1683     val special_j = no_of_record_field thy s rec_T
  1653     val special_j = no_of_record_field thy s rec_T
  2077     val iter_T = @{typ bisim_iterator}
  2047     val iter_T = @{typ bisim_iterator}
  2078     val bisim_max = @{const bisim_iterator_max}
  2048     val bisim_max = @{const bisim_iterator_max}
  2079     val n_var = Var (("n", 0), iter_T)
  2049     val n_var = Var (("n", 0), iter_T)
  2080     val n_var_minus_1 =
  2050     val n_var_minus_1 =
  2081       Const (@{const_name safe_The}, (iter_T --> bool_T) --> iter_T)
  2051       Const (@{const_name safe_The}, (iter_T --> bool_T) --> iter_T)
  2082       $ Abs ("m", iter_T, HOLogic.eq_const iter_T
  2052       $ Abs ("m", iter_T, HOLogic.eq_const iter_T $ (suc_const iter_T $ Bound 0) $ n_var)
  2083                           $ (suc_const iter_T $ Bound 0) $ n_var)
       
  2084     val x_var = Var (("x", 0), T)
  2053     val x_var = Var (("x", 0), T)
  2085     val y_var = Var (("y", 0), T)
  2054     val y_var = Var (("y", 0), T)
  2086     fun bisim_const T = Const (@{const_name bisim}, [iter_T, T, T] ---> bool_T)
  2055     fun bisim_const T = Const (@{const_name bisim}, [iter_T, T, T] ---> bool_T)
  2087     fun nth_sub_bisim x n nth_T =
  2056     fun nth_sub_bisim x n nth_T =
  2088       (if is_codatatype ctxt nth_T then bisim_const nth_T $ n_var_minus_1
  2057       (if is_codatatype ctxt nth_T then bisim_const nth_T $ n_var_minus_1
  2098           |> foldr1 s_conj
  2067           |> foldr1 s_conj
  2099       in fold_rev absdummy arg_Ts core_t end
  2068       in fold_rev absdummy arg_Ts core_t end
  2100   in
  2069   in
  2101     [HOLogic.mk_imp
  2070     [HOLogic.mk_imp
  2102        (HOLogic.mk_disj (HOLogic.eq_const iter_T $ n_var $ zero_const iter_T,
  2071        (HOLogic.mk_disj (HOLogic.eq_const iter_T $ n_var $ zero_const iter_T,
  2103             s_betapply [] (optimized_case_def hol_ctxt [] T bool_T
  2072             s_betapply [] (optimized_case_def hol_ctxt [] T bool_T (map case_func xs), x_var)),
  2104                                               (map case_func xs), x_var)),
       
  2105         bisim_const T $ n_var $ x_var $ y_var),
  2073         bisim_const T $ n_var $ x_var $ y_var),
  2106      HOLogic.eq_const pred_T $ (bisim_const T $ bisim_max $ x_var)
  2074      HOLogic.eq_const pred_T $ (bisim_const T $ bisim_max $ x_var)
  2107      $ Abs (Name.uu, T, HOLogic.mk_eq (x_var, Bound 0))]
  2075      $ Abs (Name.uu, T, HOLogic.mk_eq (x_var, Bound 0))]
  2108     |> map HOLogic.mk_Trueprop
  2076     |> map HOLogic.mk_Trueprop
  2109   end
  2077   end