src/HOL/Tools/Nitpick/nitpick_preproc.ML
changeset 55888 cac1add157e8
parent 51706 0a4b4735d8bd
child 55889 6bfbec3dff62
equal deleted inserted replaced
55887:25bd4745ee38 55888:cac1add157e8
    68 
    68 
    69 (** Uncurrying **)
    69 (** Uncurrying **)
    70 
    70 
    71 fun add_to_uncurry_table ctxt t =
    71 fun add_to_uncurry_table ctxt t =
    72   let
    72   let
    73     val thy = Proof_Context.theory_of ctxt
       
    74     fun aux (t1 $ t2) args table =
    73     fun aux (t1 $ t2) args table =
    75         let val table = aux t2 [] table in aux t1 (t2 :: args) table end
    74         let val table = aux t2 [] table in aux t1 (t2 :: args) table end
    76       | aux (Abs (_, _, t')) _ table = aux t' [] table
    75       | aux (Abs (_, _, t')) _ table = aux t' [] table
    77       | aux (t as Const (x as (s, _))) args table =
    76       | aux (t as Const (x as (s, _))) args table =
    78         if is_built_in_const thy [(NONE, true)] x orelse
    77         if is_built_in_const x orelse is_constr_like ctxt x orelse
    79            is_constr_like ctxt x orelse
       
    80            is_sel s orelse s = @{const_name Sigma} then
    78            is_sel s orelse s = @{const_name Sigma} then
    81           table
    79           table
    82         else
    80         else
    83           Termtab.map_default (t, 65536) (Integer.min (length args)) table
    81           Termtab.map_default (t, 65536) (Integer.min (length args)) table
    84       | aux _ _ table = table
    82       | aux _ _ table = table
   124       | aux t args = s_betapplys [] (t, args)
   122       | aux t args = s_betapplys [] (t, args)
   125   in aux t [] end
   123   in aux t [] end
   126 
   124 
   127 (** Boxing **)
   125 (** Boxing **)
   128 
   126 
   129 fun box_fun_and_pair_in_term (hol_ctxt as {ctxt, thy, stds, ...}) def orig_t =
   127 fun box_fun_and_pair_in_term (hol_ctxt as {ctxt, ...}) def orig_t =
   130   let
   128   let
   131     fun box_relational_operator_type (Type (@{type_name fun}, Ts)) =
   129     fun box_relational_operator_type (Type (@{type_name fun}, Ts)) =
   132         Type (@{type_name fun}, map box_relational_operator_type Ts)
   130         Type (@{type_name fun}, map box_relational_operator_type Ts)
   133       | box_relational_operator_type (Type (@{type_name prod}, Ts)) =
   131       | box_relational_operator_type (Type (@{type_name prod}, Ts)) =
   134         Type (@{type_name prod}, map (box_type hol_ctxt InPair) Ts)
   132         Type (@{type_name prod}, map (box_type hol_ctxt InPair) Ts)
   227                       box_relational_operator_type T
   225                       box_relational_operator_type T
   228                     else if String.isPrefix quot_normal_prefix s then
   226                     else if String.isPrefix quot_normal_prefix s then
   229                       let val T' = box_type hol_ctxt InFunLHS (domain_type T) in
   227                       let val T' = box_type hol_ctxt InFunLHS (domain_type T) in
   230                         T' --> T'
   228                         T' --> T'
   231                       end
   229                       end
   232                     else if is_built_in_const thy stds x orelse
   230                     else if is_built_in_const x orelse
   233                             s = @{const_name Sigma} then
   231                             s = @{const_name Sigma} then
   234                       T
   232                       T
   235                     else if is_constr_like ctxt x then
   233                     else if is_constr_like ctxt x then
   236                       box_type hol_ctxt InConstr T
   234                       box_type hol_ctxt InConstr T
   237                     else if is_sel s orelse is_rep_fun ctxt x then
   235                     else if is_sel s orelse is_rep_fun ctxt x then
   249           val t2 = coerce_term hol_ctxt new_Ts (hd Ts1) T2 t2
   247           val t2 = coerce_term hol_ctxt new_Ts (hd Ts1) T2 t2
   250         in
   248         in
   251           s_betapply new_Ts (if s1 = @{type_name fun} then
   249           s_betapply new_Ts (if s1 = @{type_name fun} then
   252                                t1
   250                                t1
   253                              else
   251                              else
   254                                select_nth_constr_arg ctxt stds
   252                                select_nth_constr_arg ctxt
   255                                    (@{const_name FunBox},
   253                                    (@{const_name FunBox},
   256                                     Type (@{type_name fun}, Ts1) --> T1) t1 0
   254                                     Type (@{type_name fun}, Ts1) --> T1) t1 0
   257                                    (Type (@{type_name fun}, Ts1)), t2)
   255                                    (Type (@{type_name fun}, Ts1)), t2)
   258         end
   256         end
   259       | t1 $ t2 =>
   257       | t1 $ t2 =>
   266           val t2 = coerce_term hol_ctxt new_Ts (hd Ts1) T2 t2
   264           val t2 = coerce_term hol_ctxt new_Ts (hd Ts1) T2 t2
   267         in
   265         in
   268           s_betapply new_Ts (if s1 = @{type_name fun} then
   266           s_betapply new_Ts (if s1 = @{type_name fun} then
   269                                t1
   267                                t1
   270                              else
   268                              else
   271                                select_nth_constr_arg ctxt stds
   269                                select_nth_constr_arg ctxt
   272                                    (@{const_name FunBox},
   270                                    (@{const_name FunBox},
   273                                     Type (@{type_name fun}, Ts1) --> T1) t1 0
   271                                     Type (@{type_name fun}, Ts1) --> T1) t1 0
   274                                    (Type (@{type_name fun}, Ts1)), t2)
   272                                    (Type (@{type_name fun}, Ts1)), t2)
   275         end
   273         end
   276       | Free (s, T) => Free (s, box_type hol_ctxt InExpr T)
   274       | Free (s, T) => Free (s, box_type hol_ctxt InExpr T)
   304     fun aux [] = false
   302     fun aux [] = false
   305       | aux [T] = is_fun_or_set_type T orelse is_pair_type T
   303       | aux [T] = is_fun_or_set_type T orelse is_pair_type T
   306       | aux _ = true
   304       | aux _ = true
   307   in aux (map snd (Term.add_vars t []) @ map (nth Ts) (loose_bnos t)) end
   305   in aux (map snd (Term.add_vars t []) @ map (nth Ts) (loose_bnos t)) end
   308 
   306 
   309 fun pull_out_constr_comb ({ctxt, stds, ...} : hol_context) Ts relax k level t
   307 fun pull_out_constr_comb ({ctxt, ...} : hol_context) Ts relax k level t args
   310                          args seen =
   308                          seen =
   311   let val t_comb = list_comb (t, args) in
   309   let val t_comb = list_comb (t, args) in
   312     case t of
   310     case t of
   313       Const x =>
   311       Const x =>
   314       if not relax andalso is_constr ctxt stds x andalso
   312       if not relax andalso is_constr ctxt x andalso
   315          not (is_fun_or_set_type (fastype_of1 (Ts, t_comb))) andalso
   313          not (is_fun_or_set_type (fastype_of1 (Ts, t_comb))) andalso
   316          has_heavy_bounds_or_vars Ts t_comb andalso
   314          has_heavy_bounds_or_vars Ts t_comb andalso
   317          not (loose_bvar (t_comb, level)) then
   315          not (loose_bvar (t_comb, level)) then
   318         let
   316         let
   319           val (j, seen) = case find_index (curry (op =) t_comb) seen of
   317           val (j, seen) = case find_index (curry (op =) t_comb) seen of
   396           pull_out_constr_comb hol_ctxt Ts false k num_exists t args seen
   394           pull_out_constr_comb hol_ctxt Ts false k num_exists t args seen
   397         else
   395         else
   398           (list_comb (t, args), seen)
   396           (list_comb (t, args), seen)
   399   in aux [] 0 t [] [] |> fst end
   397   in aux [] 0 t [] [] |> fst end
   400 
   398 
   401 fun destroy_pulled_out_constrs (hol_ctxt as {ctxt, stds, ...}) axiom strong t =
   399 fun destroy_pulled_out_constrs (hol_ctxt as {ctxt, ...}) axiom strong t =
   402   let
   400   let
   403     val num_occs_of_var =
   401     val num_occs_of_var =
   404       fold_aterms (fn Var z => (fn f => fn z' => f z' |> z = z' ? Integer.add 1)
   402       fold_aterms (fn Var z => (fn f => fn z' => f z' |> z = z' ? Integer.add 1)
   405                     | _ => I) t (K 0)
   403                     | _ => I) t (K 0)
   406     fun aux Ts careful ((t0 as Const (@{const_name "=="}, _)) $ t1 $ t2) =
   404     fun aux Ts careful ((t0 as Const (@{const_name "=="}, _)) $ t1 $ t2) =
   432           let
   430           let
   433             val (arg_Ts, dataT) = strip_type T
   431             val (arg_Ts, dataT) = strip_type T
   434             val n = length arg_Ts
   432             val n = length arg_Ts
   435           in
   433           in
   436             if length args = n andalso
   434             if length args = n andalso
   437                (is_constr ctxt stds x orelse s = @{const_name Pair} orelse
   435                (is_constr ctxt x orelse s = @{const_name Pair} orelse
   438                 x = (@{const_name Suc}, nat_T --> nat_T)) andalso
   436                 x = (@{const_name Suc}, nat_T --> nat_T)) andalso
   439                (not careful orelse not (is_Var t1) orelse
   437                (not careful orelse not (is_Var t1) orelse
   440                 String.isPrefix val_var_prefix (fst (fst (dest_Var t1)))) then
   438                 String.isPrefix val_var_prefix (fst (fst (dest_Var t1)))) then
   441                 s_let Ts "l" (n + 1) dataT bool_T
   439                 s_let Ts "l" (n + 1) dataT bool_T
   442                       (fn t1 =>
   440                       (fn t1 =>
   449         | _ => raise SAME ())
   447         | _ => raise SAME ())
   450        |> body_type (type_of t0) = prop_T ? HOLogic.mk_Trueprop)
   448        |> body_type (type_of t0) = prop_T ? HOLogic.mk_Trueprop)
   451       handle SAME () => if pass1 then aux_eq Ts careful false t0 t2 t1
   449       handle SAME () => if pass1 then aux_eq Ts careful false t0 t2 t1
   452                         else t0 $ aux Ts false t2 $ aux Ts false t1
   450                         else t0 $ aux Ts false t2 $ aux Ts false t1
   453     and sel_eq Ts x t n nth_T nth_t =
   451     and sel_eq Ts x t n nth_T nth_t =
   454       HOLogic.eq_const nth_T $ nth_t
   452       HOLogic.eq_const nth_T $ nth_t $ select_nth_constr_arg ctxt x t n nth_T
   455                              $ select_nth_constr_arg ctxt stds x t n nth_T
       
   456       |> aux Ts false
   453       |> aux Ts false
   457   in aux [] axiom t end
   454   in aux [] axiom t end
   458 
   455 
   459 (** Destruction of universal and existential equalities **)
   456 (** Destruction of universal and existential equalities **)
   460 
   457 
   485         aux prems zs (subst_free [(Var z, t')] t2)
   482         aux prems zs (subst_free [(Var z, t')] t2)
   486       else
   483       else
   487         aux (t1 :: prems) (Term.add_vars t1 zs) t2
   484         aux (t1 :: prems) (Term.add_vars t1 zs) t2
   488   in aux [] [] end
   485   in aux [] [] end
   489 
   486 
   490 fun find_bound_assign ctxt stds j =
   487 fun find_bound_assign ctxt j =
   491   let
   488   let
   492     fun do_term _ [] = NONE
   489     fun do_term _ [] = NONE
   493       | do_term seen (t :: ts) =
   490       | do_term seen (t :: ts) =
   494         let
   491         let
   495           fun do_eq pass1 t1 t2 =
   492           fun do_eq pass1 t1 t2 =
   498              else case t1 of
   495              else case t1 of
   499                Bound j' => if j' = j then SOME (t2, ts @ seen) else raise SAME ()
   496                Bound j' => if j' = j then SOME (t2, ts @ seen) else raise SAME ()
   500              | Const (s, Type (@{type_name fun}, [T1, T2])) $ Bound j' =>
   497              | Const (s, Type (@{type_name fun}, [T1, T2])) $ Bound j' =>
   501                if j' = j andalso
   498                if j' = j andalso
   502                   s = nth_sel_name_for_constr_name @{const_name FunBox} 0 then
   499                   s = nth_sel_name_for_constr_name @{const_name FunBox} 0 then
   503                  SOME (construct_value ctxt stds
   500                  SOME (construct_value ctxt
   504                                        (@{const_name FunBox}, T2 --> T1) [t2],
   501                                        (@{const_name FunBox}, T2 --> T1) [t2],
   505                        ts @ seen)
   502                        ts @ seen)
   506                else
   503                else
   507                  raise SAME ()
   504                  raise SAME ()
   508              | _ => raise SAME ())
   505              | _ => raise SAME ())
   525         (aux (f, lev) $ (aux (t, lev) handle SAME () => t)
   522         (aux (f, lev) $ (aux (t, lev) handle SAME () => t)
   526          handle SAME () => f $ aux (t, lev))
   523          handle SAME () => f $ aux (t, lev))
   527       | aux _ = raise SAME ()
   524       | aux _ = raise SAME ()
   528   in aux (t, j) handle SAME () => t end
   525   in aux (t, j) handle SAME () => t end
   529 
   526 
   530 fun destroy_existential_equalities ({ctxt, stds, ...} : hol_context) =
   527 fun destroy_existential_equalities ({ctxt, ...} : hol_context) =
   531   let
   528   let
   532     fun kill [] [] ts = foldr1 s_conj ts
   529     fun kill [] [] ts = foldr1 s_conj ts
   533       | kill (s :: ss) (T :: Ts) ts =
   530       | kill (s :: ss) (T :: Ts) ts =
   534         (case find_bound_assign ctxt stds (length ss) [] ts of
   531         (case find_bound_assign ctxt (length ss) [] ts of
   535            SOME (_, []) => @{const True}
   532            SOME (_, []) => @{const True}
   536          | SOME (arg_t, ts) =>
   533          | SOME (arg_t, ts) =>
   537            kill ss Ts (map (subst_one_bound (length ss)
   534            kill ss Ts (map (subst_one_bound (length ss)
   538                                 (incr_bv (~1, length ss + 1, arg_t))) ts)
   535                                 (incr_bv (~1, length ss + 1, arg_t))) ts)
   539          | NONE =>
   536          | NONE =>
   729 fun special_fun_aconv ((x1, js1, ts1), (x2, js2, ts2)) =
   726 fun special_fun_aconv ((x1, js1, ts1), (x2, js2, ts2)) =
   730   x1 = x2 andalso js1 = js2 andalso length ts1 = length ts2 andalso
   727   x1 = x2 andalso js1 = js2 andalso length ts1 = length ts2 andalso
   731   forall (op aconv) (ts1 ~~ ts2)
   728   forall (op aconv) (ts1 ~~ ts2)
   732 
   729 
   733 fun specialize_consts_in_term
   730 fun specialize_consts_in_term
   734         (hol_ctxt as {ctxt, thy, stds, specialize, def_tables, simp_table,
   731         (hol_ctxt as {ctxt, thy, specialize, def_tables, simp_table,
   735                       special_funs, ...}) def depth t =
   732                       special_funs, ...}) def depth t =
   736   if not specialize orelse depth > special_max_depth then
   733   if not specialize orelse depth > special_max_depth then
   737     t
   734     t
   738   else
   735   else
   739     let
   736     let
   740       val blacklist =
   737       val blacklist =
   741         if def then case term_under_def t of Const x => [x] | _ => [] else []
   738         if def then case term_under_def t of Const x => [x] | _ => [] else []
   742       fun aux args Ts (Const (x as (s, T))) =
   739       fun aux args Ts (Const (x as (s, T))) =
   743           ((if not (member (op =) blacklist x) andalso not (null args) andalso
   740           ((if not (member (op =) blacklist x) andalso not (null args) andalso
   744                not (String.isPrefix special_prefix s) andalso
   741                not (String.isPrefix special_prefix s) andalso
   745                not (is_built_in_const thy stds x) andalso
   742                not (is_built_in_const x) andalso
   746                (is_equational_fun_but_no_plain_def hol_ctxt x orelse
   743                (is_equational_fun_but_no_plain_def hol_ctxt x orelse
   747                 (is_some (def_of_const thy def_tables x) andalso
   744                 (is_some (def_of_const thy def_tables x) andalso
   748                  not (is_of_class_const thy x) andalso
   745                  not (is_of_class_const thy x) andalso
   749                  not (is_constr ctxt stds x) andalso
   746                  not (is_constr ctxt x) andalso
   750                  not (is_choice_spec_fun hol_ctxt x))) then
   747                  not (is_choice_spec_fun hol_ctxt x))) then
   751               let
   748               let
   752                 val eligible_args =
   749                 val eligible_args =
   753                   filter (is_special_eligible_arg true Ts o snd)
   750                   filter (is_special_eligible_arg true Ts o snd)
   754                          (index_seq 0 (length args) ~~ args)
   751                          (index_seq 0 (length args) ~~ args)
   893 
   890 
   894 (* Prevents divergence in case of cyclic or infinite axiom dependencies. *)
   891 (* Prevents divergence in case of cyclic or infinite axiom dependencies. *)
   895 val axioms_max_depth = 255
   892 val axioms_max_depth = 255
   896 
   893 
   897 fun axioms_for_term
   894 fun axioms_for_term
   898         (hol_ctxt as {thy, ctxt, max_bisim_depth, stds, user_axioms,
   895         (hol_ctxt as {thy, ctxt, max_bisim_depth, user_axioms, evals,
   899                       evals, def_tables, nondef_table, choice_spec_table,
   896                       def_tables, nondef_table, choice_spec_table, nondefs,
   900                       nondefs, ...}) assm_ts neg_t =
   897                       ...}) assm_ts neg_t =
   901   let
   898   let
   902     val (def_assm_ts, nondef_assm_ts) =
   899     val (def_assm_ts, nondef_assm_ts) =
   903       List.partition (assumption_exclusively_defines_free assm_ts) assm_ts
   900       List.partition (assumption_exclusively_defines_free assm_ts) assm_ts
   904     val def_assm_table = map (`(the o defined_free_by_assumption)) def_assm_ts
   901     val def_assm_table = map (`(the o defined_free_by_assumption)) def_assm_ts
   905     type accumulator = styp list * (term list * term list)
   902     type accumulator = styp list * (term list * term list)
   926        else add_nondef_axiom) depth t
   923        else add_nondef_axiom) depth t
   927     and add_axioms_for_term depth t (accum as (seen, axs)) =
   924     and add_axioms_for_term depth t (accum as (seen, axs)) =
   928       case t of
   925       case t of
   929         t1 $ t2 => accum |> fold (add_axioms_for_term depth) [t1, t2]
   926         t1 $ t2 => accum |> fold (add_axioms_for_term depth) [t1, t2]
   930       | Const (x as (s, T)) =>
   927       | Const (x as (s, T)) =>
   931         (if member (op aconv) seen t orelse is_built_in_const thy stds x then
   928         (if member (op aconv) seen t orelse is_built_in_const x then
   932            accum
   929            accum
   933          else
   930          else
   934            let val accum = (t :: seen, axs) in
   931            let val accum = (t :: seen, axs) in
   935              if depth > axioms_max_depth then
   932              if depth > axioms_max_depth then
   936                raise TOO_LARGE ("Nitpick_Preproc.axioms_for_term.\
   933                raise TOO_LARGE ("Nitpick_Preproc.axioms_for_term.\
   947                                       (get_class_def thy class)
   944                                       (get_class_def thy class)
   948                in
   945                in
   949                  fold (add_maybe_def_axiom depth) (map_filter I [ax1, ax2])
   946                  fold (add_maybe_def_axiom depth) (map_filter I [ax1, ax2])
   950                       accum
   947                       accum
   951                end
   948                end
   952              else if is_constr ctxt stds x then
   949              else if is_constr ctxt x then
   953                accum
   950                accum
   954              else if is_descr (original_name s) then
   951              else if is_descr (original_name s) then
   955                fold (add_nondef_axiom depth) (equational_fun_axioms hol_ctxt x)
   952                fold (add_nondef_axiom depth) (equational_fun_axioms hol_ctxt x)
   956                     accum
   953                     accum
   957              else if is_equational_fun_but_no_plain_def hol_ctxt x then
   954              else if is_equational_fun_but_no_plain_def hol_ctxt x then
  1015       | Type (z as (_, Ts)) =>
  1012       | Type (z as (_, Ts)) =>
  1016         fold (add_axioms_for_type depth) Ts
  1013         fold (add_axioms_for_type depth) Ts
  1017         #> (if is_pure_typedef ctxt T then
  1014         #> (if is_pure_typedef ctxt T then
  1018               fold (add_maybe_def_axiom depth) (optimized_typedef_axioms ctxt z)
  1015               fold (add_maybe_def_axiom depth) (optimized_typedef_axioms ctxt z)
  1019             else if is_quot_type ctxt T then
  1016             else if is_quot_type ctxt T then
  1020               fold (add_def_axiom depth)
  1017               fold (add_def_axiom depth) (optimized_quot_type_axioms ctxt z)
  1021                    (optimized_quot_type_axioms ctxt stds z)
       
  1022             else if max_bisim_depth >= 0 andalso is_codatatype ctxt T then
  1018             else if max_bisim_depth >= 0 andalso is_codatatype ctxt T then
  1023               fold (add_maybe_def_axiom depth)
  1019               fold (add_maybe_def_axiom depth)
  1024                    (codatatype_bisim_axioms hol_ctxt T)
  1020                    (codatatype_bisim_axioms hol_ctxt T)
  1025             else
  1021             else
  1026               I)
  1022               I)
  1251 (** Preprocessor entry point **)
  1247 (** Preprocessor entry point **)
  1252 
  1248 
  1253 val max_skolem_depth = 3
  1249 val max_skolem_depth = 3
  1254 
  1250 
  1255 fun preprocess_formulas
  1251 fun preprocess_formulas
  1256         (hol_ctxt as {thy, ctxt, stds, binary_ints, destroy_constrs, boxes,
  1252         (hol_ctxt as {ctxt, binary_ints, destroy_constrs, boxes, needs, ...})
  1257                       needs, ...}) assm_ts neg_t =
  1253         assm_ts neg_t =
  1258   let
  1254   let
  1259     val (nondef_ts, def_ts, got_all_mono_user_axioms, no_poly_user_axioms) =
  1255     val (nondef_ts, def_ts, got_all_mono_user_axioms, no_poly_user_axioms) =
  1260       neg_t |> unfold_defs_in_term hol_ctxt
  1256       neg_t |> unfold_defs_in_term hol_ctxt
  1261             |> close_form
  1257             |> close_form
  1262             |> skolemize_term_and_more hol_ctxt max_skolem_depth
  1258             |> skolemize_term_and_more hol_ctxt max_skolem_depth
  1263             |> specialize_consts_in_term hol_ctxt false 0
  1259             |> specialize_consts_in_term hol_ctxt false 0
  1264             |> axioms_for_term hol_ctxt assm_ts
  1260             |> axioms_for_term hol_ctxt assm_ts
  1265     val binarize =
  1261     val binarize =
  1266       is_standard_datatype thy stds nat_T andalso
       
  1267       case binary_ints of
  1262       case binary_ints of
  1268         SOME false => false
  1263         SOME false => false
  1269       | _ => forall (may_use_binary_ints false) nondef_ts andalso
  1264       | _ => forall (may_use_binary_ints false) nondef_ts andalso
  1270              forall (may_use_binary_ints true) def_ts andalso
  1265              forall (may_use_binary_ints true) def_ts andalso
  1271              (binary_ints = SOME true orelse
  1266              (binary_ints = SOME true orelse