src/HOL/Tools/Sledgehammer/sledgehammer_proof_reconstruct.ML
changeset 37962 d7dbe01f48d7
parent 37961 6a48c85a211a
child 37991 3093ab32f1e7
equal deleted inserted replaced
37961:6a48c85a211a 37962:d7dbe01f48d7
    31 open Sledgehammer_Fact_Filter
    31 open Sledgehammer_Fact_Filter
    32 open Sledgehammer_TPTP_Format
    32 open Sledgehammer_TPTP_Format
    33 
    33 
    34 type minimize_command = string list -> string
    34 type minimize_command = string list -> string
    35 
    35 
    36 fun is_ident_char c = Char.isAlphaNum c orelse c = #"_"
       
    37 fun is_head_digit s = Char.isDigit (String.sub (s, 0))
       
    38 
       
    39 val index_in_shape : int -> int list list -> int =
    36 val index_in_shape : int -> int list list -> int =
    40   find_index o exists o curry (op =)
    37   find_index o exists o curry (op =)
    41 fun is_axiom_clause_number thm_names num = num <= Vector.length thm_names
    38 fun is_axiom_clause_number thm_names num =
       
    39   num > 0 andalso num <= Vector.length thm_names andalso
       
    40   Vector.sub (thm_names, num - 1) <> ""
    42 fun is_conjecture_clause_number conjecture_shape num =
    41 fun is_conjecture_clause_number conjecture_shape num =
    43   index_in_shape num conjecture_shape >= 0
    42   index_in_shape num conjecture_shape >= 0
    44 
    43 
    45 fun smart_lambda v t =
    44 fun smart_lambda v t =
    46   Abs (case v of
    45   Abs (case v of
    55   Definition of 'a * 'b * 'c |
    54   Definition of 'a * 'b * 'c |
    56   Inference of 'a * 'd * 'e list
    55   Inference of 'a * 'd * 'e list
    57 
    56 
    58 (**** PARSING OF TSTP FORMAT ****)
    57 (**** PARSING OF TSTP FORMAT ****)
    59 
    58 
    60 fun strip_spaces_in_list [] = ""
       
    61   | strip_spaces_in_list [c1] = if Char.isSpace c1 then "" else str c1
       
    62   | strip_spaces_in_list [c1, c2] =
       
    63     strip_spaces_in_list [c1] ^ strip_spaces_in_list [c2]
       
    64   | strip_spaces_in_list (c1 :: c2 :: c3 :: cs) =
       
    65     if Char.isSpace c1 then
       
    66       strip_spaces_in_list (c2 :: c3 :: cs)
       
    67     else if Char.isSpace c2 then
       
    68       if Char.isSpace c3 then
       
    69         strip_spaces_in_list (c1 :: c3 :: cs)
       
    70       else
       
    71         str c1 ^ (if forall is_ident_char [c1, c3] then " " else "") ^
       
    72         strip_spaces_in_list (c3 :: cs)
       
    73     else
       
    74       str c1 ^ strip_spaces_in_list (c2 :: c3 :: cs)
       
    75 val strip_spaces = strip_spaces_in_list o String.explode
       
    76 
       
    77 (* Syntax trees, either term list or formulae *)
    59 (* Syntax trees, either term list or formulae *)
    78 datatype node = IntLeaf of int | StrNode of string * node list
    60 datatype node = IntLeaf of int | StrNode of string * node list
    79 
    61 
    80 fun str_leaf s = StrNode (s, [])
    62 fun str_leaf s = StrNode (s, [])
    81 
    63 
    82 fun scons (x, y) = StrNode ("cons", [x, y])
    64 fun scons (x, y) = StrNode ("cons", [x, y])
    83 val slist_of = List.foldl scons (str_leaf "nil")
    65 val slist_of = List.foldl scons (str_leaf "nil")
    84 
    66 
    85 (*Strings enclosed in single quotes, e.g. filenames*)
    67 (*Strings enclosed in single quotes, e.g. filenames*)
    86 val parse_quoted = $$ "'" |-- Scan.repeat (~$$ "'") --| $$ "'" >> implode;
    68 val parse_quoted = $$ "'" |-- Scan.repeat (~$$ "'") --| $$ "'" >> implode;
    87 
       
    88 (*Integer constants, typically proof line numbers*)
       
    89 val parse_integer = Scan.many1 is_head_digit >> (the o Int.fromString o implode)
       
    90 
    69 
    91 val parse_dollar_name =
    70 val parse_dollar_name =
    92   Scan.repeat ($$ "$") -- Symbol.scan_id >> (fn (ss, s) => implode ss ^ s)
    71   Scan.repeat ($$ "$") -- Symbol.scan_id >> (fn (ss, s) => implode ss ^ s)
    93 
    72 
    94 (* needed for SPASS's output format *)
    73 (* needed for SPASS's output format *)
   100 (* Generalized first-order terms, which include file names, numbers, etc. *)
    79 (* Generalized first-order terms, which include file names, numbers, etc. *)
   101 (* The "x" argument is not strictly necessary, but without it Poly/ML loops
    80 (* The "x" argument is not strictly necessary, but without it Poly/ML loops
   102    forever at compile time. *)
    81    forever at compile time. *)
   103 fun parse_term pool x =
    82 fun parse_term pool x =
   104      (parse_quoted >> str_leaf
    83      (parse_quoted >> str_leaf
   105    || parse_integer >> IntLeaf
    84    || scan_integer >> IntLeaf
   106    || (parse_dollar_name >> repair_name pool)
    85    || (parse_dollar_name >> repair_name pool)
   107       -- Scan.optional ($$ "(" |-- parse_terms pool --| $$ ")") [] >> StrNode
    86       -- Scan.optional ($$ "(" |-- parse_terms pool --| $$ ")") [] >> StrNode
   108    || $$ "(" |-- parse_term pool --| $$ ")"
    87    || $$ "(" |-- parse_term pool --| $$ ")"
   109    || $$ "[" |-- Scan.optional (parse_terms pool) [] --| $$ "]" >> slist_of) x
    88    || $$ "[" |-- Scan.optional (parse_terms pool) [] --| $$ "]" >> slist_of) x
   110 and parse_terms pool x =
    89 and parse_terms pool x =
   147 (* Syntax: cnf(<num>, <formula_role>, <cnf_formula> <annotations>).
   126 (* Syntax: cnf(<num>, <formula_role>, <cnf_formula> <annotations>).
   148    The <num> could be an identifier, but we assume integers. *)
   127    The <num> could be an identifier, but we assume integers. *)
   149 fun finish_tstp_definition_line (num, (u, us)) = Definition (num, u, us)
   128 fun finish_tstp_definition_line (num, (u, us)) = Definition (num, u, us)
   150 fun finish_tstp_inference_line ((num, us), deps) = Inference (num, us, deps)
   129 fun finish_tstp_inference_line ((num, us), deps) = Inference (num, us, deps)
   151 fun parse_tstp_line pool =
   130 fun parse_tstp_line pool =
   152      ((Scan.this_string "fof" -- $$ "(") |-- parse_integer --| $$ ","
   131      ((Scan.this_string "fof" -- $$ "(") |-- scan_integer --| $$ ","
   153        --| Scan.this_string "definition" --| $$ "," -- parse_definition pool
   132        --| Scan.this_string "definition" --| $$ "," -- parse_definition pool
   154        --| parse_tstp_annotations --| $$ ")" --| $$ "."
   133        --| parse_tstp_annotations --| $$ ")" --| $$ "."
   155       >> finish_tstp_definition_line)
   134       >> finish_tstp_definition_line)
   156   || ((Scan.this_string "cnf" -- $$ "(") |-- parse_integer --| $$ ","
   135   || ((Scan.this_string "cnf" -- $$ "(") |-- scan_integer --| $$ ","
   157        --| Symbol.scan_id --| $$ "," -- parse_clause pool
   136        --| Symbol.scan_id --| $$ "," -- parse_clause pool
   158        -- parse_tstp_annotations --| $$ ")" --| $$ "."
   137        -- parse_tstp_annotations --| $$ ")" --| $$ "."
   159       >> finish_tstp_inference_line)
   138       >> finish_tstp_inference_line)
   160 
   139 
   161 (**** PARSING OF SPASS OUTPUT ****)
   140 (**** PARSING OF SPASS OUTPUT ****)
   162 
   141 
   163 (* SPASS returns clause references of the form "x.y". We ignore "y", whose role
   142 (* SPASS returns clause references of the form "x.y". We ignore "y", whose role
   164    is not clear anyway. *)
   143    is not clear anyway. *)
   165 val parse_dot_name = parse_integer --| $$ "." --| parse_integer
   144 val parse_dot_name = scan_integer --| $$ "." --| scan_integer
   166 
   145 
   167 val parse_spass_annotations =
   146 val parse_spass_annotations =
   168   Scan.optional ($$ ":" |-- Scan.repeat (parse_dot_name
   147   Scan.optional ($$ ":" |-- Scan.repeat (parse_dot_name
   169                                          --| Scan.option ($$ ","))) []
   148                                          --| Scan.option ($$ ","))) []
   170 
   149 
   183 
   162 
   184 (* Syntax: <num>[0:<inference><annotations>]
   163 (* Syntax: <num>[0:<inference><annotations>]
   185    <cnf_formulas> || <cnf_formulas> -> <cnf_formulas>. *)
   164    <cnf_formulas> || <cnf_formulas> -> <cnf_formulas>. *)
   186 fun finish_spass_line ((num, deps), us) = Inference (num, us, deps)
   165 fun finish_spass_line ((num, deps), us) = Inference (num, us, deps)
   187 fun parse_spass_line pool =
   166 fun parse_spass_line pool =
   188   parse_integer --| $$ "[" --| $$ "0" --| $$ ":" --| Symbol.scan_id
   167   scan_integer --| $$ "[" --| $$ "0" --| $$ ":" --| Symbol.scan_id
   189   -- parse_spass_annotations --| $$ "]" -- parse_horn_clause pool --| $$ "."
   168   -- parse_spass_annotations --| $$ "]" -- parse_horn_clause pool --| $$ "."
   190   >> finish_spass_line
   169   >> finish_spass_line
   191 
   170 
   192 fun parse_line pool = parse_tstp_line pool || parse_spass_line pool
   171 fun parse_line pool = parse_tstp_line pool || parse_spass_line pool
   193 fun parse_lines pool = Scan.repeat1 (parse_line pool)
   172 fun parse_lines pool = Scan.repeat1 (parse_line pool)
   533    number (108) is extracted.
   512    number (108) is extracted.
   534    SPASS: Lines have the form "108[0:Inp] ...", where the first number (108) is
   513    SPASS: Lines have the form "108[0:Inp] ...", where the first number (108) is
   535    extracted. *)
   514    extracted. *)
   536 fun extract_formula_numbers_in_atp_proof atp_proof =
   515 fun extract_formula_numbers_in_atp_proof atp_proof =
   537   let
   516   let
   538     val tokens_of = String.tokens (not o is_ident_char)
   517     val tokens_of = String.tokens (not o Char.isAlphaNum)
   539     fun extract_num ("fof" :: num :: "axiom" :: _) = Int.fromString num
   518     fun extract_num ("fof" :: num :: "axiom" :: _) = Int.fromString num
   540       | extract_num (num :: "0" :: "Inp" :: _) = Int.fromString num
   519       | extract_num (num :: "0" :: "Inp" :: _) = Int.fromString num
   541       | extract_num _ = NONE
   520       | extract_num _ = NONE
   542   in atp_proof |> split_lines |> map_filter (extract_num o tokens_of) end
   521   in atp_proof |> split_lines |> map_filter (extract_num o tokens_of) end
   543 
   522