src/HOL/Tools/ATP/atp_util.ML
author wenzelm
Tue Jun 06 13:13:25 2017 +0200 (2017-06-06)
changeset 66020 a31760eee09d
parent 61770 a20048c78891
child 67522 9e712280cc37
permissions -rw-r--r--
discontinued obsolete print mode;
     1 (*  Title:      HOL/Tools/ATP/atp_util.ML
     2     Author:     Jasmin Blanchette, TU Muenchen
     3 
     4 General-purpose functions used by the ATP module.
     5 *)
     6 
     7 signature ATP_UTIL =
     8 sig
     9   val timestamp : unit -> string
    10   val hashw : word * word -> word
    11   val hashw_string : string * word -> word
    12   val hash_string : string -> int
    13   val chunk_list : int -> 'a list -> 'a list list
    14   val stringN_of_int : int -> int -> string
    15   val strip_spaces : bool -> (char -> bool) -> string -> string
    16   val strip_spaces_except_between_idents : string -> string
    17   val elide_string : int -> string -> string
    18   val find_enclosed : string -> string -> string -> string list
    19   val nat_subscript : int -> string
    20   val unquote_tvar : string -> string
    21   val maybe_quote : Keyword.keywords -> string -> string
    22   val string_of_ext_time : bool * Time.time -> string
    23   val string_of_time : Time.time -> string
    24   val type_instance : theory -> typ -> typ -> bool
    25   val type_generalization : theory -> typ -> typ -> bool
    26   val type_intersect : theory -> typ -> typ -> bool
    27   val type_equiv : theory -> typ * typ -> bool
    28   val varify_type : Proof.context -> typ -> typ
    29   val instantiate_type : theory -> typ -> typ -> typ -> typ
    30   val varify_and_instantiate_type : Proof.context -> typ -> typ -> typ -> typ
    31   val is_type_surely_finite : Proof.context -> typ -> bool
    32   val is_type_surely_infinite : Proof.context -> bool -> typ list -> typ -> bool
    33   val s_not : term -> term
    34   val s_conj : term * term -> term
    35   val s_disj : term * term -> term
    36   val s_imp : term * term -> term
    37   val s_iff : term * term -> term
    38   val close_form : term -> term
    39   val hol_close_form_prefix : string
    40   val hol_close_form : term -> term
    41   val hol_open_form : (string -> string) -> term -> term
    42   val eta_expand : typ list -> term -> int -> term
    43   val cong_extensionalize_term : Proof.context -> term -> term
    44   val abs_extensionalize_term : Proof.context -> term -> term
    45   val unextensionalize_def : term -> term
    46   val transform_elim_prop : term -> term
    47   val specialize_type : theory -> (string * typ) -> term -> term
    48   val strip_subgoal : thm -> int -> Proof.context -> (string * typ) list * term list * term
    49   val extract_lambda_def : (term -> string * typ) -> term -> string * term
    50   val short_thm_name : Proof.context -> thm -> string
    51 end;
    52 
    53 structure ATP_Util : ATP_UTIL =
    54 struct
    55 
    56 fun timestamp_format time =
    57   Date.fmt "%Y-%m-%d %H:%M:%S." (Date.fromTimeLocal time) ^
    58   (StringCvt.padLeft #"0" 3 (string_of_int (Time.toMilliseconds time - 1000 * Time.toSeconds time)))
    59 
    60 val timestamp = timestamp_format o Time.now
    61 
    62 (* This hash function is recommended in "Compilers: Principles, Techniques, and
    63    Tools" by Aho, Sethi, and Ullman. The "hashpjw" function, which they
    64    particularly recommend, triggers a bug in versions of Poly/ML up to 4.2.0. *)
    65 fun hashw (u, w) = Word.+ (u, Word.* (0w65599, w))
    66 fun hashw_char (c, w) = hashw (Word.fromInt (Char.ord c), w)
    67 fun hashw_string (s : string, w) = CharVector.foldl hashw_char w s
    68 fun hash_string s = Word.toInt (hashw_string (s, 0w0))
    69 
    70 fun chunk_list _ [] = []
    71   | chunk_list k xs =
    72     let val (xs1, xs2) = chop k xs in xs1 :: chunk_list k xs2 end
    73 
    74 fun stringN_of_int 0 _ = ""
    75   | stringN_of_int k n =
    76     stringN_of_int (k - 1) (n div 10) ^ string_of_int (n mod 10)
    77 
    78 fun is_spaceish c = Char.isSpace c orelse c = #"\127" (* DEL -- no idea where these come from *)
    79 
    80 fun strip_spaces skip_comments is_evil =
    81   let
    82     fun strip_c_style_comment [] accum = accum
    83       | strip_c_style_comment (#"*" :: #"/" :: cs) accum = strip_spaces_in_list true cs accum
    84       | strip_c_style_comment (_ :: cs) accum = strip_c_style_comment cs accum
    85     and strip_spaces_in_list _ [] accum = accum
    86       | strip_spaces_in_list true (#"%" :: cs) accum =
    87         strip_spaces_in_list true (cs |> take_prefix (not_equal #"\n") |> snd) accum
    88       | strip_spaces_in_list true (#"/" :: #"*" :: cs) accum = strip_c_style_comment cs accum
    89       | strip_spaces_in_list _ [c1] accum = accum |> not (is_spaceish c1) ? cons c1
    90       | strip_spaces_in_list skip_comments (cs as [_, _]) accum =
    91         accum |> fold (strip_spaces_in_list skip_comments o single) cs
    92       | strip_spaces_in_list skip_comments (c1 :: c2 :: c3 :: cs) accum =
    93         if is_spaceish c1 then
    94           strip_spaces_in_list skip_comments (c2 :: c3 :: cs) accum
    95         else if is_spaceish c2 then
    96           if is_spaceish c3 then
    97             strip_spaces_in_list skip_comments (c1 :: c3 :: cs) accum
    98           else
    99             strip_spaces_in_list skip_comments (c3 :: cs)
   100               (c1 :: accum |> forall is_evil [c1, c3] ? cons #" ")
   101         else
   102           strip_spaces_in_list skip_comments (c2 :: c3 :: cs) (cons c1 accum)
   103   in
   104     String.explode
   105     #> rpair [] #-> strip_spaces_in_list skip_comments
   106     #> rev #> String.implode
   107   end
   108 
   109 fun is_ident_char c = Char.isAlphaNum c orelse c = #"_"
   110 val strip_spaces_except_between_idents = strip_spaces true is_ident_char
   111 
   112 fun elide_string threshold s =
   113   if size s > threshold then
   114     String.extract (s, 0, SOME (threshold div 2 - 5)) ^ " ...... " ^
   115     String.extract (s, size s - (threshold + 1) div 2 + 6, NONE)
   116   else
   117     s
   118 
   119 fun find_enclosed left right s =
   120   case first_field left s of
   121     SOME (_, s) =>
   122     (case first_field right s of
   123        SOME (enclosed, s) => enclosed :: find_enclosed left right s
   124      | NONE => [])
   125   | NONE => []
   126 
   127 val subscript = implode o map (prefix "\<^sub>") o raw_explode  (* FIXME Symbol.explode (?) *)
   128 fun nat_subscript n =
   129   n |> string_of_int |> not (print_mode_active Print_Mode.ASCII) ? subscript
   130 
   131 val unquote_tvar = perhaps (try (unprefix "'"))
   132 val unquery_var = perhaps (try (unprefix "?"))
   133 
   134 val is_long_identifier = forall Symbol_Pos.is_identifier o Long_Name.explode
   135 fun maybe_quote keywords y =
   136   let val s = YXML.content_of y in
   137     y |> ((not (is_long_identifier (unquote_tvar s)) andalso
   138            not (is_long_identifier (unquery_var s))) orelse
   139            Keyword.is_literal keywords s) ? quote
   140   end
   141 
   142 fun string_of_ext_time (plus, time) =
   143   let val us = Time.toMicroseconds time in
   144     (if plus then "> " else "") ^
   145     (if us < 1000 then string_of_real (Real.fromInt (us div 100) / 10.0) ^ " ms"
   146      else if us < 1000000 then signed_string_of_int (us div 1000) ^ " ms"
   147      else string_of_real (Real.fromInt (us div 100000) / 10.0) ^ " s")
   148   end
   149 
   150 val string_of_time = string_of_ext_time o pair false
   151 
   152 fun type_instance thy T T' = Sign.typ_instance thy (T, T')
   153 fun type_generalization thy T T' = Sign.typ_instance thy (T', T)
   154 
   155 fun type_intersect _ (TVar _) _ = true
   156   | type_intersect _ _ (TVar _) = true
   157   | type_intersect thy T T' =
   158     let
   159       val tvars = Term.add_tvar_namesT T []
   160       val tvars' = Term.add_tvar_namesT T' []
   161       val maxidx' = maxidx_of_typ T'
   162       val T =
   163         T |> exists (member (op =) tvars') tvars ? Logic.incr_tvar (maxidx' + 1)
   164       val maxidx = Integer.max (maxidx_of_typ T) maxidx'
   165     in can (Sign.typ_unify thy (T, T')) (Vartab.empty, maxidx) end
   166 
   167 val type_equiv = Sign.typ_equiv
   168 
   169 fun varify_type ctxt T =
   170   Variable.polymorphic_types ctxt [Const (@{const_name undefined}, T)]
   171   |> snd |> the_single |> dest_Const |> snd
   172 
   173 (* TODO: use "Term_Subst.instantiateT" instead? *)
   174 fun instantiate_type thy T1 T1' T2 =
   175   Same.commit (Envir.subst_type_same
   176                    (Sign.typ_match thy (T1, T1') Vartab.empty)) T2
   177   handle Type.TYPE_MATCH => raise TYPE ("instantiate_type", [T1, T1'], [])
   178 
   179 fun varify_and_instantiate_type ctxt T1 T1' T2 =
   180   let val thy = Proof_Context.theory_of ctxt in
   181     instantiate_type thy (varify_type ctxt T1) T1' (varify_type ctxt T2)
   182   end
   183 
   184 fun free_constructors_of ctxt (Type (s, Ts)) =
   185     (case Ctr_Sugar.ctr_sugar_of ctxt s of
   186       SOME {ctrs, ...} => map_filter (try dest_Const o Ctr_Sugar.mk_ctr Ts) ctrs
   187     | NONE => [])
   188   | free_constructors_of _ _ = []
   189 
   190 (* Similar to "Nitpick_HOL.bounded_exact_card_of_type".
   191    0 means infinite type, 1 means singleton type (e.g., "unit"), and 2 means
   192    cardinality 2 or more. The specified default cardinality is returned if the
   193    cardinality of the type can't be determined. *)
   194 fun tiny_card_of_type ctxt sound assigns default_card T =
   195   let
   196     val thy = Proof_Context.theory_of ctxt
   197     val max = 2 (* 1 would be too small for the "fun" case *)
   198     fun aux slack avoid T =
   199       if member (op =) avoid T then
   200         0
   201       else case AList.lookup (type_equiv thy) assigns T of
   202         SOME k => k
   203       | NONE =>
   204         case T of
   205           Type (@{type_name fun}, [T1, T2]) =>
   206           (case (aux slack avoid T1, aux slack avoid T2) of
   207              (k, 1) => if slack andalso k = 0 then 0 else 1
   208            | (0, _) => 0
   209            | (_, 0) => 0
   210            | (k1, k2) =>
   211              if k1 >= max orelse k2 >= max then max
   212              else Int.min (max, Integer.pow k2 k1))
   213         | Type (@{type_name set}, [T']) => aux slack avoid (T' --> @{typ bool})
   214         | @{typ prop} => 2
   215         | @{typ bool} => 2 (* optimization *)
   216         | @{typ nat} => 0 (* optimization *)
   217         | Type ("Int.int", []) => 0 (* optimization *)
   218         | Type (s, _) =>
   219           (case free_constructors_of ctxt T of
   220              constrs as _ :: _ =>
   221              let
   222                val constr_cards =
   223                  map (Integer.prod o map (aux slack (T :: avoid)) o binder_types o snd) constrs
   224              in
   225                if exists (curry (op =) 0) constr_cards then 0
   226                else Int.min (max, Integer.sum constr_cards)
   227              end
   228            | [] =>
   229              case Typedef.get_info ctxt s of
   230                ({abs_type, rep_type, ...}, _) :: _ =>
   231                if not sound then
   232                  (* We cheat here by assuming that typedef types are infinite if
   233                     their underlying type is infinite. This is unsound in
   234                     general but it's hard to think of a realistic example where
   235                     this would not be the case. We are also slack with
   236                     representation types: If a representation type has the form
   237                     "sigma => tau", we consider it enough to check "sigma" for
   238                     infiniteness. *)
   239                  (case varify_and_instantiate_type ctxt
   240                            (Logic.varifyT_global abs_type) T
   241                            (Logic.varifyT_global rep_type)
   242                        |> aux true avoid of
   243                     0 => 0
   244                   | 1 => 1
   245                   | _ => default_card)
   246                else
   247                  default_card
   248              | [] => default_card)
   249         | TFree _ =>
   250           (* Very slightly unsound: Type variables are assumed not to be
   251              constrained to cardinality 1. (In practice, the user would most
   252              likely have used "unit" directly anyway.) *)
   253           if not sound andalso default_card = 1 then 2 else default_card
   254         | TVar _ => default_card
   255   in Int.min (max, aux false [] T) end
   256 
   257 fun is_type_surely_finite ctxt T = tiny_card_of_type ctxt true [] 0 T <> 0
   258 fun is_type_surely_infinite ctxt sound infinite_Ts T =
   259   tiny_card_of_type ctxt sound (map (rpair 0) infinite_Ts) 1 T = 0
   260 
   261 (* Simple simplifications to ensure that sort annotations don't leave a trail of
   262    spurious "True"s. *)
   263 fun s_not (Const (@{const_name All}, T) $ Abs (s, T', t')) =
   264     Const (@{const_name Ex}, T) $ Abs (s, T', s_not t')
   265   | s_not (Const (@{const_name Ex}, T) $ Abs (s, T', t')) =
   266     Const (@{const_name All}, T) $ Abs (s, T', s_not t')
   267   | s_not (@{const HOL.implies} $ t1 $ t2) = @{const HOL.conj} $ t1 $ s_not t2
   268   | s_not (@{const HOL.conj} $ t1 $ t2) =
   269     @{const HOL.disj} $ s_not t1 $ s_not t2
   270   | s_not (@{const HOL.disj} $ t1 $ t2) =
   271     @{const HOL.conj} $ s_not t1 $ s_not t2
   272   | s_not (@{const False}) = @{const True}
   273   | s_not (@{const True}) = @{const False}
   274   | s_not (@{const Not} $ t) = t
   275   | s_not t = @{const Not} $ t
   276 
   277 fun s_conj (@{const True}, t2) = t2
   278   | s_conj (t1, @{const True}) = t1
   279   | s_conj (@{const False}, _) = @{const False}
   280   | s_conj (_, @{const False}) = @{const False}
   281   | s_conj (t1, t2) = if t1 aconv t2 then t1 else HOLogic.mk_conj (t1, t2)
   282 
   283 fun s_disj (@{const False}, t2) = t2
   284   | s_disj (t1, @{const False}) = t1
   285   | s_disj (@{const True}, _) = @{const True}
   286   | s_disj (_, @{const True}) = @{const True}
   287   | s_disj (t1, t2) = if t1 aconv t2 then t1 else HOLogic.mk_disj (t1, t2)
   288 
   289 fun s_imp (@{const True}, t2) = t2
   290   | s_imp (t1, @{const False}) = s_not t1
   291   | s_imp (@{const False}, _) = @{const True}
   292   | s_imp (_, @{const True}) = @{const True}
   293   | s_imp p = HOLogic.mk_imp p
   294 
   295 fun s_iff (@{const True}, t2) = t2
   296   | s_iff (t1, @{const True}) = t1
   297   | s_iff (@{const False}, t2) = s_not t2
   298   | s_iff (t1, @{const False}) = s_not t1
   299   | s_iff (t1, t2) = if t1 aconv t2 then @{const True} else HOLogic.eq_const HOLogic.boolT $ t1 $ t2
   300 
   301 fun close_form t =
   302   fold (fn ((s, i), T) => fn t' =>
   303       Logic.all_const T $ Abs (s, T, abstract_over (Var ((s, i), T), t')))
   304     (Term.add_vars t []) t
   305 
   306 val hol_close_form_prefix = "ATP."
   307 
   308 fun hol_close_form t =
   309   fold (fn ((s, i), T) => fn t' =>
   310            HOLogic.all_const T
   311            $ Abs (hol_close_form_prefix ^ s, T,
   312                   abstract_over (Var ((s, i), T), t')))
   313        (Term.add_vars t []) t
   314 
   315 fun hol_open_form unprefix
   316       (t as Const (@{const_name All}, _) $ Abs (s, T, t')) =
   317     (case try unprefix s of
   318        SOME s =>
   319        let
   320          val names = Name.make_context (map fst (Term.add_var_names t' []))
   321          val (s, _) = Name.variant s names
   322        in hol_open_form unprefix (subst_bound (Var ((s, 0), T), t')) end
   323      | NONE => t)
   324   | hol_open_form _ t = t
   325 
   326 fun eta_expand _ t 0 = t
   327   | eta_expand Ts (Abs (s, T, t')) n =
   328     Abs (s, T, eta_expand (T :: Ts) t' (n - 1))
   329   | eta_expand Ts t n =
   330     fold_rev (fn T => fn t' => Abs ("x" ^ nat_subscript n, T, t'))
   331              (List.take (binder_types (fastype_of1 (Ts, t)), n))
   332              (list_comb (incr_boundvars n t, map Bound (n - 1 downto 0)))
   333 
   334 fun cong_extensionalize_term ctxt t =
   335   if exists_Const (fn (s, _) => s = @{const_name Not}) t then
   336     t |> Skip_Proof.make_thm (Proof_Context.theory_of ctxt)
   337       |> Meson.cong_extensionalize_thm ctxt
   338       |> Thm.prop_of
   339   else
   340     t
   341 
   342 fun is_fun_equality (@{const_name HOL.eq},
   343                      Type (_, [Type (@{type_name fun}, _), _])) = true
   344   | is_fun_equality _ = false
   345 
   346 fun abs_extensionalize_term ctxt t =
   347   if exists_Const is_fun_equality t then
   348     t |> Thm.cterm_of ctxt |> Meson.abs_extensionalize_conv ctxt
   349       |> Thm.prop_of |> Logic.dest_equals |> snd
   350   else
   351     t
   352 
   353 fun unextensionalize_def t =
   354   case t of
   355     @{const Trueprop} $ (Const (@{const_name HOL.eq}, _) $ lhs $ rhs) =>
   356     (case strip_comb lhs of
   357        (c as Const (_, T), args) =>
   358        if forall is_Var args andalso not (has_duplicates (op =) args) then
   359          @{const Trueprop}
   360          $ (Const (@{const_name HOL.eq}, T --> T --> @{typ bool})
   361             $ c $ fold_rev lambda args rhs)
   362        else
   363          t
   364      | _ => t)
   365   | _ => t
   366 
   367 (* Converts an elim-rule into an equivalent theorem that does not have the
   368    predicate variable. Leaves other theorems unchanged. We simply instantiate
   369    the conclusion variable to "False". (Cf. "transform_elim_theorem" in
   370    "Meson_Clausify".) *)
   371 fun transform_elim_prop t =
   372   case Logic.strip_imp_concl t of
   373     @{const Trueprop} $ Var (z, @{typ bool}) =>
   374     subst_Vars [(z, @{const False})] t
   375   | Var (z, @{typ prop}) => subst_Vars [(z, @{prop False})] t
   376   | _ => t
   377 
   378 fun specialize_type thy (s, T) t =
   379   let
   380     fun subst_for (Const (s', T')) =
   381         if s = s' then
   382           SOME (Sign.typ_match thy (T', T) Vartab.empty)
   383           handle Type.TYPE_MATCH => NONE
   384         else
   385           NONE
   386       | subst_for (t1 $ t2) = (case subst_for t1 of SOME x => SOME x | NONE => subst_for t2)
   387       | subst_for (Abs (_, _, t')) = subst_for t'
   388       | subst_for _ = NONE
   389   in
   390     (case subst_for t of
   391       SOME subst => Envir.subst_term_types subst t
   392     | NONE => raise Type.TYPE_MATCH)
   393   end
   394 
   395 fun strip_subgoal goal i ctxt =
   396   let
   397     val (t, (frees, params)) =
   398       Logic.goal_params (Thm.prop_of goal) i
   399       ||> (map dest_Free #> Variable.variant_frees ctxt [] #> `(map Free))
   400     val hyp_ts = t |> Logic.strip_assums_hyp |> map (curry subst_bounds frees)
   401     val concl_t = t |> Logic.strip_assums_concl |> curry subst_bounds frees
   402   in (rev params, hyp_ts, concl_t) end
   403 
   404 fun extract_lambda_def dest_head (Const (@{const_name HOL.eq}, _) $ t $ u) =
   405     let val (head, args) = strip_comb t in
   406       (head |> dest_head |> fst,
   407        fold_rev (fn t as Var ((s, _), T) =>
   408                     (fn u => Abs (s, T, abstract_over (t, u)))
   409                   | _ => raise Fail "expected \"Var\"") args u)
   410     end
   411   | extract_lambda_def _ _ = raise Fail "malformed lifted lambda"
   412 
   413 fun short_thm_name ctxt th =
   414   let
   415     val long = Thm.get_name_hint th
   416     val short = Long_Name.base_name long
   417   in
   418     if Thm.eq_thm_prop (th, singleton (Attrib.eval_thms ctxt) (Facts.named short, [])) then short
   419     else long
   420   end
   421 
   422 end;