src/HOL/Tools/ATP/atp_proof_reconstruct.ML
author blanchet
Wed Feb 20 08:44:24 2013 +0100 (2013-02-20)
changeset 51192 4dc6bb65c3c3
parent 50704 cd1fcda1ea88
child 51878 f11039b31bae
permissions -rw-r--r--
slacker comparison for Skolems, to avoid trivial equations
blanchet@46320
     1
(*  Title:      HOL/Tools/ATP/atp_proof_reconstruct.ML
blanchet@38027
     2
    Author:     Lawrence C. Paulson, Cambridge University Computer Laboratory
blanchet@38027
     3
    Author:     Claire Quigley, Cambridge University Computer Laboratory
blanchet@36392
     4
    Author:     Jasmin Blanchette, TU Muenchen
paulson@21978
     5
blanchet@49914
     6
Basic proof reconstruction from ATP proofs.
wenzelm@33310
     7
*)
wenzelm@33310
     8
blanchet@46320
     9
signature ATP_PROOF_RECONSTRUCT =
paulson@24425
    10
sig
nik@43678
    11
  type ('a, 'b) ho_term = ('a, 'b) ATP_Problem.ho_term
blanchet@48135
    12
  type ('a, 'b, 'c, 'd) formula = ('a, 'b, 'c, 'd) ATP_Problem.formula
blanchet@45519
    13
blanchet@45519
    14
  val metisN : string
blanchet@45519
    15
  val full_typesN : string
blanchet@45519
    16
  val partial_typesN : string
blanchet@45519
    17
  val no_typesN : string
blanchet@45519
    18
  val really_full_type_enc : string
blanchet@45519
    19
  val full_type_enc : string
blanchet@45519
    20
  val partial_type_enc : string
blanchet@45519
    21
  val no_type_enc : string
blanchet@45519
    22
  val full_type_encs : string list
blanchet@45519
    23
  val partial_type_encs : string list
blanchet@45554
    24
  val metis_default_lam_trans : string
blanchet@45554
    25
  val metis_call : string -> string -> string
blanchet@49983
    26
  val forall_of : term -> term -> term
blanchet@49983
    27
  val exists_of : term -> term -> term
blanchet@45519
    28
  val unalias_type_enc : string -> string list
blanchet@43094
    29
  val term_from_atp :
blanchet@49914
    30
    Proof.context -> bool -> int Symtab.table -> typ option ->
blanchet@49914
    31
    (string, string) ho_term -> term
blanchet@43127
    32
  val prop_from_atp :
blanchet@49914
    33
    Proof.context -> bool -> int Symtab.table ->
blanchet@49914
    34
    (string, string, (string, string) ho_term, string) formula -> term
paulson@24425
    35
end;
paulson@21978
    36
blanchet@46320
    37
structure ATP_Proof_Reconstruct : ATP_PROOF_RECONSTRUCT =
paulson@21978
    38
struct
paulson@21978
    39
blanchet@43085
    40
open ATP_Util
blanchet@38028
    41
open ATP_Problem
blanchet@39452
    42
open ATP_Proof
blanchet@46320
    43
open ATP_Problem_Generate
paulson@21978
    44
blanchet@45519
    45
val metisN = "metis"
blanchet@45519
    46
blanchet@45519
    47
val full_typesN = "full_types"
blanchet@45519
    48
val partial_typesN = "partial_types"
blanchet@45519
    49
val no_typesN = "no_types"
blanchet@45519
    50
blanchet@45519
    51
val really_full_type_enc = "mono_tags"
blanchet@45519
    52
val full_type_enc = "poly_guards_query"
blanchet@45519
    53
val partial_type_enc = "poly_args"
blanchet@45519
    54
val no_type_enc = "erased"
blanchet@45519
    55
blanchet@45519
    56
val full_type_encs = [full_type_enc, really_full_type_enc]
blanchet@45519
    57
val partial_type_encs = partial_type_enc :: full_type_encs
blanchet@45519
    58
blanchet@45519
    59
val type_enc_aliases =
blanchet@45519
    60
  [(full_typesN, full_type_encs),
blanchet@45519
    61
   (partial_typesN, partial_type_encs),
blanchet@45519
    62
   (no_typesN, [no_type_enc])]
blanchet@45519
    63
blanchet@45519
    64
fun unalias_type_enc s =
blanchet@45519
    65
  AList.lookup (op =) type_enc_aliases s |> the_default [s]
blanchet@45519
    66
blanchet@46365
    67
val metis_default_lam_trans = combsN
blanchet@45519
    68
blanchet@45519
    69
fun metis_call type_enc lam_trans =
blanchet@45519
    70
  let
blanchet@45519
    71
    val type_enc =
blanchet@45519
    72
      case AList.find (fn (enc, encs) => enc = hd encs) type_enc_aliases
blanchet@45519
    73
                      type_enc of
blanchet@45519
    74
        [alias] => alias
blanchet@45519
    75
      | _ => type_enc
blanchet@45522
    76
    val opts = [] |> type_enc <> partial_typesN ? cons type_enc
blanchet@45519
    77
                  |> lam_trans <> metis_default_lam_trans ? cons lam_trans
blanchet@45520
    78
  in metisN ^ (if null opts then "" else " (" ^ commas opts ^ ")") end
blanchet@45519
    79
blanchet@50670
    80
fun term_name' (Var ((s, _), _)) = perhaps (try Name.dest_skolem) s
blanchet@50670
    81
  | term_name' t = ""
blanchet@50670
    82
blanchet@50670
    83
fun lambda' v = Term.lambda_name (term_name' v, v)
blanchet@50670
    84
blanchet@50670
    85
fun forall_of v t = HOLogic.all_const (fastype_of v) $ lambda' v t
blanchet@50670
    86
fun exists_of v t = HOLogic.exists_const (fastype_of v) $ lambda' v t
blanchet@39425
    87
blanchet@43135
    88
fun make_tfree ctxt w =
blanchet@43135
    89
  let val ww = "'" ^ w in
blanchet@43135
    90
    TFree (ww, the_default HOLogic.typeS (Variable.def_sort ctxt (ww, ~1)))
blanchet@43135
    91
  end
blanchet@43135
    92
nik@43678
    93
exception HO_TERM of (string, string) ho_term list
blanchet@48135
    94
exception FORMULA of
blanchet@48135
    95
    (string, string, (string, string) ho_term, string) formula list
blanchet@37991
    96
exception SAME of unit
paulson@21978
    97
blanchet@36909
    98
(* Type variables are given the basic sort "HOL.type". Some will later be
blanchet@37991
    99
   constrained by information from type literals, or by type inference. *)
blanchet@48132
   100
fun typ_from_atp ctxt (u as ATerm ((a, _), us)) =
blanchet@43135
   101
  let val Ts = map (typ_from_atp ctxt) us in
blanchet@45511
   102
    case unprefix_and_unascii type_const_prefix a of
blanchet@37991
   103
      SOME b => Type (invert_const b, Ts)
blanchet@37991
   104
    | NONE =>
blanchet@37991
   105
      if not (null us) then
nik@43678
   106
        raise HO_TERM [u]  (* only "tconst"s have type arguments *)
blanchet@45511
   107
      else case unprefix_and_unascii tfree_prefix a of
blanchet@43135
   108
        SOME b => make_tfree ctxt b
blanchet@36486
   109
      | NONE =>
blanchet@43302
   110
        (* Could be an Isabelle variable or a variable from the ATP, say "X1"
blanchet@43302
   111
           or "_5018". Sometimes variables from the ATP are indistinguishable
blanchet@43302
   112
           from Isabelle variables, which forces us to use a type parameter in
blanchet@43302
   113
           all cases. *)
blanchet@45511
   114
        (a |> perhaps (unprefix_and_unascii tvar_prefix), HOLogic.typeS)
blanchet@43302
   115
        |> Type_Infer.param 0
blanchet@37991
   116
  end
paulson@21978
   117
blanchet@38014
   118
(* Type class literal applied to a type. Returns triple of polarity, class,
blanchet@38014
   119
   type. *)
blanchet@48132
   120
fun type_constraint_from_term ctxt (u as ATerm ((a, _), us)) =
blanchet@45511
   121
  case (unprefix_and_unascii class_prefix a, map (typ_from_atp ctxt) us) of
blanchet@42606
   122
    (SOME b, [T]) => (b, T)
nik@43678
   123
  | _ => raise HO_TERM [u]
blanchet@38014
   124
blanchet@43907
   125
(* Accumulate type constraints in a formula: negative type literals. *)
blanchet@38014
   126
fun add_var (key, z)  = Vartab.map_default (key, []) (cons z)
blanchet@42606
   127
fun add_type_constraint false (cl, TFree (a ,_)) = add_var ((a, ~1), cl)
blanchet@42606
   128
  | add_type_constraint false (cl, TVar (ix, _)) = add_var (ix, cl)
blanchet@42606
   129
  | add_type_constraint _ _ = I
blanchet@38014
   130
blanchet@50676
   131
fun repair_var_name s =
blanchet@36486
   132
  let
blanchet@36486
   133
    fun subscript_name s n = s ^ nat_subscript n
blanchet@50704
   134
    val s = s |> String.map Char.toLower
blanchet@36486
   135
  in
blanchet@36486
   136
    case space_explode "_" s of
blanchet@36486
   137
      [_] => (case take_suffix Char.isDigit (String.explode s) of
blanchet@36486
   138
                (cs1 as _ :: _, cs2 as _ :: _) =>
blanchet@36486
   139
                subscript_name (String.implode cs1)
blanchet@36486
   140
                               (the (Int.fromString (String.implode cs2)))
blanchet@36486
   141
              | (_, _) => s)
blanchet@36486
   142
    | [s1, s2] => (case Int.fromString s2 of
blanchet@36486
   143
                     SOME n => subscript_name s1 n
blanchet@36486
   144
                   | NONE => s)
blanchet@36486
   145
    | _ => s
blanchet@36486
   146
  end
blanchet@43182
   147
blanchet@43907
   148
(* The number of type arguments of a constant, zero if it's monomorphic. For
blanchet@43907
   149
   (instances of) Skolem pseudoconstants, this information is encoded in the
blanchet@43907
   150
   constant name. *)
blanchet@43907
   151
fun num_type_args thy s =
blanchet@43907
   152
  if String.isPrefix skolem_const_prefix s then
wenzelm@46711
   153
    s |> Long_Name.explode |> List.last |> Int.fromString |> the
blanchet@45554
   154
  else if String.isPrefix lam_lifted_prefix s then
blanchet@45554
   155
    if String.isPrefix lam_lifted_poly_prefix s then 2 else 0
blanchet@43907
   156
  else
blanchet@43907
   157
    (s, Sign.the_const_type thy s) |> Sign.const_typargs thy |> length
blanchet@43907
   158
blanchet@43182
   159
fun slack_fastype_of t = fastype_of t handle TERM _ => HOLogic.typeT
blanchet@43182
   160
blanchet@51192
   161
(* Cope with "tt(X) = X" atoms, where "X" is existentially quantified. *)
blanchet@51192
   162
fun loose_aconv (Free (s, _), Free (s', _)) = s = s'
blanchet@51192
   163
  | loose_aconv (t, t') = t aconv t'
blanchet@51192
   164
blanchet@50703
   165
val vampire_skolem_prefix = "sK"
blanchet@50703
   166
blanchet@36909
   167
(* First-order translation. No types are known for variables. "HOLogic.typeT"
blanchet@38014
   168
   should allow them to be inferred. *)
blanchet@43135
   169
fun term_from_atp ctxt textual sym_tab =
blanchet@36909
   170
  let
blanchet@43135
   171
    val thy = Proof_Context.theory_of ctxt
blanchet@43212
   172
    (* For Metis, we use 1 rather than 0 because variable references in clauses
blanchet@43212
   173
       may otherwise conflict with variable constraints in the goal. At least,
blanchet@43212
   174
       type inference often fails otherwise. See also "axiom_inference" in
blanchet@43212
   175
       "Metis_Reconstruct". *)
blanchet@43094
   176
    val var_index = if textual then 0 else 1
blanchet@43131
   177
    fun do_term extra_ts opt_T u =
blanchet@36909
   178
      case u of
blanchet@48132
   179
        ATerm ((s, _), us) =>
blanchet@46435
   180
        if String.isPrefix native_type_prefix s then
blanchet@42962
   181
          @{const True} (* ignore TPTP type information *)
blanchet@44773
   182
        else if s = tptp_equal then
blanchet@43093
   183
          let val ts = map (do_term [] NONE) us in
blanchet@43094
   184
            if textual andalso length ts = 2 andalso
blanchet@51192
   185
               loose_aconv (hd ts, List.last ts) then
blanchet@39106
   186
              @{const True}
blanchet@39106
   187
            else
blanchet@39106
   188
              list_comb (Const (@{const_name HOL.eq}, HOLogic.typeT), ts)
blanchet@39106
   189
          end
blanchet@45511
   190
        else case unprefix_and_unascii const_prefix s of
blanchet@44773
   191
          SOME s' =>
blanchet@42761
   192
          let
blanchet@44773
   193
            val ((s', s''), mangled_us) =
blanchet@44773
   194
              s' |> unmangled_const |>> `invert_const
blanchet@42761
   195
          in
blanchet@42755
   196
            if s' = type_tag_name then
blanchet@42589
   197
              case mangled_us @ us of
blanchet@42589
   198
                [typ_u, term_u] =>
blanchet@43135
   199
                do_term extra_ts (SOME (typ_from_atp ctxt typ_u)) term_u
nik@43678
   200
              | _ => raise HO_TERM us
blanchet@42966
   201
            else if s' = predicator_name then
blanchet@43093
   202
              do_term [] (SOME @{typ bool}) (hd us)
blanchet@42966
   203
            else if s' = app_op_name then
blanchet@43131
   204
              let val extra_t = do_term [] NONE (List.last us) in
blanchet@43131
   205
                do_term (extra_t :: extra_ts)
blanchet@43131
   206
                        (case opt_T of
blanchet@43182
   207
                           SOME T => SOME (slack_fastype_of extra_t --> T)
blanchet@43131
   208
                         | NONE => NONE)
blanchet@43131
   209
                        (nth us (length us - 2))
blanchet@43131
   210
              end
blanchet@44396
   211
            else if s' = type_guard_name then
blanchet@42551
   212
              @{const True} (* ignore type predicates *)
blanchet@42549
   213
            else
blanchet@42549
   214
              let
blanchet@44773
   215
                val new_skolem = String.isPrefix new_skolem_const_prefix s''
blanchet@42755
   216
                val num_ty_args =
blanchet@42755
   217
                  length us - the_default 0 (Symtab.lookup sym_tab s)
blanchet@42549
   218
                val (type_us, term_us) =
blanchet@42549
   219
                  chop num_ty_args us |>> append mangled_us
blanchet@43093
   220
                val term_ts = map (do_term [] NONE) term_us
blanchet@42549
   221
                val T =
blanchet@43183
   222
                  (if not (null type_us) andalso
blanchet@43183
   223
                      num_type_args thy s' = length type_us then
blanchet@43191
   224
                     let val Ts = type_us |> map (typ_from_atp ctxt) in
blanchet@43191
   225
                       if new_skolem then
blanchet@43191
   226
                         SOME (Type_Infer.paramify_vars (tl Ts ---> hd Ts))
blanchet@43200
   227
                       else if textual then
blanchet@43200
   228
                         try (Sign.const_instance thy) (s', Ts)
blanchet@43191
   229
                       else
blanchet@43200
   230
                         NONE
blanchet@43191
   231
                     end
blanchet@43183
   232
                   else
blanchet@43183
   233
                     NONE)
blanchet@43183
   234
                  |> (fn SOME T => T
blanchet@43183
   235
                       | NONE => map slack_fastype_of term_ts --->
blanchet@43183
   236
                                 (case opt_T of
blanchet@43183
   237
                                    SOME T => T
blanchet@43183
   238
                                  | NONE => HOLogic.typeT))
blanchet@43191
   239
                val t =
blanchet@43191
   240
                  if new_skolem then
blanchet@44773
   241
                    Var ((new_skolem_var_name_from_const s'', var_index), T)
blanchet@43191
   242
                  else
blanchet@43191
   243
                    Const (unproxify_const s', T)
blanchet@43191
   244
              in list_comb (t, term_ts @ extra_ts) end
blanchet@42549
   245
          end
blanchet@36909
   246
        | NONE => (* a free or schematic variable *)
blanchet@36909
   247
          let
blanchet@50693
   248
            (* This assumes that distinct names are mapped to distinct names by
blanchet@50693
   249
               "Variable.variant_frees". This does not hold in general but
blanchet@50693
   250
               should hold for ATP-generated Skolem function names, since these
blanchet@50693
   251
               end with a digit and "variant_frees" appends letters. *)
blanchet@50676
   252
            fun fresh_up s =
blanchet@50676
   253
              [(s, ())] |> Variable.variant_frees ctxt [] |> hd |> fst
blanchet@50703
   254
            val term_ts =
blanchet@50703
   255
              map (do_term [] NONE) us
blanchet@50703
   256
              (* Vampire (2.6) passes arguments to Skolem functions in reverse
blanchet@50703
   257
                 order *)
blanchet@50703
   258
              |> String.isPrefix vampire_skolem_prefix s ? rev
blanchet@45042
   259
            val ts = term_ts @ extra_ts
blanchet@45042
   260
            val T =
blanchet@45042
   261
              case opt_T of
blanchet@45042
   262
                SOME T => map slack_fastype_of term_ts ---> T
blanchet@45042
   263
              | NONE => map slack_fastype_of ts ---> HOLogic.typeT
blanchet@36909
   264
            val t =
blanchet@45511
   265
              case unprefix_and_unascii fixed_var_prefix s of
blanchet@45511
   266
                SOME s => Free (s, T)
blanchet@36909
   267
              | NONE =>
blanchet@45511
   268
                case unprefix_and_unascii schematic_var_prefix s of
blanchet@44773
   269
                  SOME s => Var ((s, var_index), T)
blanchet@36909
   270
                | NONE =>
blanchet@50676
   271
                  if textual andalso not (is_tptp_variable s) then
blanchet@50676
   272
                    Free (s |> textual ? (repair_var_name #> fresh_up), T)
blanchet@50676
   273
                  else
blanchet@50676
   274
                    Var ((s |> textual ? repair_var_name, var_index), T)
blanchet@36909
   275
          in list_comb (t, ts) end
blanchet@43093
   276
  in do_term [] end
paulson@21978
   277
blanchet@48132
   278
fun term_from_atom ctxt textual sym_tab pos (u as ATerm ((s, _), _)) =
blanchet@38014
   279
  if String.isPrefix class_prefix s then
blanchet@43135
   280
    add_type_constraint pos (type_constraint_from_term ctxt u)
blanchet@38014
   281
    #> pair @{const True}
blanchet@38014
   282
  else
blanchet@43135
   283
    pair (term_from_atp ctxt textual sym_tab (SOME @{typ bool}) u)
blanchet@36402
   284
blanchet@37991
   285
(* Update schematic type variables with detected sort constraints. It's not
blanchet@42563
   286
   totally clear whether this code is necessary. *)
blanchet@38014
   287
fun repair_tvar_sorts (t, tvar_tab) =
blanchet@36909
   288
  let
blanchet@37991
   289
    fun do_type (Type (a, Ts)) = Type (a, map do_type Ts)
blanchet@37991
   290
      | do_type (TVar (xi, s)) =
blanchet@37991
   291
        TVar (xi, the_default s (Vartab.lookup tvar_tab xi))
blanchet@37991
   292
      | do_type (TFree z) = TFree z
blanchet@37991
   293
    fun do_term (Const (a, T)) = Const (a, do_type T)
blanchet@37991
   294
      | do_term (Free (a, T)) = Free (a, do_type T)
blanchet@37991
   295
      | do_term (Var (xi, T)) = Var (xi, do_type T)
blanchet@37991
   296
      | do_term (t as Bound _) = t
blanchet@37991
   297
      | do_term (Abs (a, T, t)) = Abs (a, do_type T, do_term t)
blanchet@37991
   298
      | do_term (t1 $ t2) = do_term t1 $ do_term t2
blanchet@37991
   299
  in t |> not (Vartab.is_empty tvar_tab) ? do_term end
blanchet@37991
   300
blanchet@39425
   301
fun quantify_over_var quant_of var_s t =
blanchet@39425
   302
  let
blanchet@39425
   303
    val vars = [] |> Term.add_vars t |> filter (fn ((s, _), _) => s = var_s)
blanchet@39425
   304
                  |> map Var
blanchet@39425
   305
  in fold_rev quant_of vars t end
blanchet@37991
   306
blanchet@38085
   307
(* Interpret an ATP formula as a HOL term, extracting sort constraints as they
blanchet@38085
   308
   appear in the formula. *)
blanchet@43184
   309
fun prop_from_atp ctxt textual sym_tab phi =
blanchet@38014
   310
  let
blanchet@38014
   311
    fun do_formula pos phi =
blanchet@37991
   312
      case phi of
blanchet@38014
   313
        AQuant (_, [], phi) => do_formula pos phi
blanchet@42526
   314
      | AQuant (q, (s, _) :: xs, phi') =>
blanchet@38014
   315
        do_formula pos (AQuant (q, xs, phi'))
blanchet@42526
   316
        (* FIXME: TFF *)
blanchet@49914
   317
        #>> quantify_over_var
blanchet@49914
   318
              (case q of AForall => forall_of | AExists => exists_of)
blanchet@50676
   319
              (s |> textual ? repair_var_name)
blanchet@38014
   320
      | AConn (ANot, [phi']) => do_formula (not pos) phi' #>> s_not
blanchet@37991
   321
      | AConn (c, [phi1, phi2]) =>
blanchet@38014
   322
        do_formula (pos |> c = AImplies ? not) phi1
blanchet@38014
   323
        ##>> do_formula pos phi2
blanchet@38014
   324
        #>> (case c of
blanchet@38014
   325
               AAnd => s_conj
blanchet@38014
   326
             | AOr => s_disj
blanchet@38014
   327
             | AImplies => s_imp
blanchet@38038
   328
             | AIff => s_iff
blanchet@43163
   329
             | ANot => raise Fail "impossible connective")
blanchet@43135
   330
      | AAtom tm => term_from_atom ctxt textual sym_tab pos tm
blanchet@37991
   331
      | _ => raise FORMULA [phi]
blanchet@38014
   332
  in repair_tvar_sorts (do_formula true phi Vartab.empty) end
blanchet@37991
   333
immler@31038
   334
end;