1 (* Title: HOL/Tools/ATP/atp_reconstruct.ML
2 Author: Lawrence C. Paulson, Cambridge University Computer Laboratory
3 Author: Claire Quigley, Cambridge University Computer Laboratory
4 Author: Jasmin Blanchette, TU Muenchen
6 Proof reconstruction from ATP proofs.
9 signature ATP_RECONSTRUCT =
11 type 'a fo_term = 'a ATP_Problem.fo_term
12 type ('a, 'b, 'c) formula = ('a, 'b, 'c) ATP_Problem.formula
13 type 'a proof = 'a ATP_Proof.proof
14 type locality = ATP_Translate.locality
16 datatype reconstructor =
23 Played of reconstructor * Time.time |
24 Trust_Playable of reconstructor * Time.time option|
25 Failed_to_Play of reconstructor
27 type minimize_command = string list -> string
28 type one_line_params =
29 play * string * (string * locality) list * minimize_command * int * int
31 bool * bool * int * string Symtab.table * int list list * int
32 * (string * locality) list vector * int Symtab.table * string proof * thm
33 val repair_conjecture_shape_and_fact_names :
34 string -> int list list -> int -> (string * locality) list vector
36 -> int list list * int * (string * locality) list vector * int list
37 val used_facts_in_atp_proof :
38 Proof.context -> int -> (string * locality) list vector -> string proof
39 -> (string * locality) list
40 val used_facts_in_unsound_atp_proof :
41 Proof.context -> int list list -> int -> (string * locality) list vector
42 -> 'a proof -> string list option
43 val uses_typed_helpers : int list -> 'a proof -> bool
44 val one_line_proof_text : one_line_params -> string
45 val make_tvar : string -> typ
46 val make_tfree : Proof.context -> string -> typ
48 Proof.context -> bool -> int Symtab.table -> typ option -> string fo_term
51 Proof.context -> bool -> int Symtab.table
52 -> (string, string, string fo_term) formula -> term
54 Proof.context -> bool -> isar_params -> one_line_params -> string
56 Proof.context -> bool -> isar_params -> one_line_params -> string
59 structure ATP_Reconstruct : ATP_RECONSTRUCT =
67 datatype reconstructor =
74 Played of reconstructor * Time.time |
75 Trust_Playable of reconstructor * Time.time option |
76 Failed_to_Play of reconstructor
78 type minimize_command = string list -> string
79 type one_line_params =
80 play * string * (string * locality) list * minimize_command * int * int
82 bool * bool * int * string Symtab.table * int list list * int
83 * (string * locality) list vector * int Symtab.table * string proof * thm
85 fun is_head_digit s = Char.isDigit (String.sub (s, 0))
86 val scan_integer = Scan.many1 is_head_digit >> (the o Int.fromString o implode)
88 val is_typed_helper_name =
89 String.isPrefix helper_prefix andf String.isSuffix typed_helper_suffix
91 fun find_first_in_list_vector vec key =
92 Vector.foldl (fn (ps, NONE) => AList.lookup (op =) ps key
93 | (_, value) => value) NONE vec
96 (** SPASS's FLOTTER hack **)
98 (* This is a hack required for keeping track of facts after they have been
99 clausified by SPASS's FLOTTER preprocessor. The "ATP/scripts/spass" script is
100 also part of this hack. *)
102 val set_ClauseFormulaRelationN = "set_ClauseFormulaRelation"
104 fun extract_clause_sequence output =
106 val tokens_of = String.tokens (not o Char.isAlphaNum)
107 fun extract_num ("clause" :: (ss as _ :: _)) = Int.fromString (List.last ss)
108 | extract_num _ = NONE
109 in output |> split_lines |> map_filter (extract_num o tokens_of) end
111 val parse_clause_formula_pair =
112 $$ "(" |-- scan_integer --| $$ ","
113 -- (Symbol.scan_id ::: Scan.repeat ($$ "," |-- Symbol.scan_id)) --| $$ ")"
114 --| Scan.option ($$ ",")
115 val parse_clause_formula_relation =
116 Scan.this_string set_ClauseFormulaRelationN |-- $$ "("
117 |-- Scan.repeat parse_clause_formula_pair
118 val extract_clause_formula_relation =
119 Substring.full #> Substring.position set_ClauseFormulaRelationN
120 #> snd #> Substring.position "." #> fst #> Substring.string
121 #> raw_explode #> filter_out Symbol.is_blank #> parse_clause_formula_relation
124 val unprefix_fact_number = space_implode "_" o tl o space_explode "_"
126 fun repair_conjecture_shape_and_fact_names output conjecture_shape
127 fact_offset fact_names typed_helpers =
128 if String.isSubstring set_ClauseFormulaRelationN output then
130 val j0 = hd (hd conjecture_shape)
131 val seq = extract_clause_sequence output
132 val name_map = extract_clause_formula_relation output
133 fun renumber_conjecture j =
134 conjecture_prefix ^ string_of_int (j - j0)
135 |> AList.find (fn (s, ss) => member (op =) ss s) name_map
136 |> map (fn s => find_index (curry (op =) s) seq + 1)
137 fun names_for_number j =
138 j |> AList.lookup (op =) name_map |> these
139 |> map_filter (try (unascii_of o unprefix_fact_number
140 o unprefix fact_prefix))
142 (name, name |> find_first_in_list_vector fact_names |> the)
143 handle Option.Option =>
144 error ("No such fact: " ^ quote name ^ "."))
146 (conjecture_shape |> map (maps renumber_conjecture), 0,
147 seq |> map names_for_number |> Vector.fromList,
148 name_map |> filter (forall is_typed_helper_name o snd) |> map fst)
151 (conjecture_shape, fact_offset, fact_names, typed_helpers)
153 val vampire_step_prefix = "f" (* grrr... *)
155 val extract_step_number =
156 Int.fromString o perhaps (try (unprefix vampire_step_prefix))
158 fun resolve_fact _ fact_names (_, SOME s) =
159 (case try (unprefix fact_prefix) s of
161 let val s' = s' |> unprefix_fact_number |> unascii_of in
162 case find_first_in_list_vector fact_names s' of
167 | resolve_fact facts_offset fact_names (num, NONE) =
168 (case extract_step_number num of
170 let val j = j - facts_offset in
171 if j > 0 andalso j <= Vector.length fact_names then
172 Vector.sub (fact_names, j - 1)
178 fun is_fact conjecture_shape = not o null o resolve_fact 0 conjecture_shape
180 fun resolve_conjecture _ (_, SOME s) =
181 (case try (unprefix conjecture_prefix) s of
183 (case Int.fromString s' of
187 | resolve_conjecture conjecture_shape (num, NONE) =
188 case extract_step_number num of
189 SOME i => (case find_index (exists (curry (op =) i)) conjecture_shape of
194 fun is_conjecture conjecture_shape =
195 not o null o resolve_conjecture conjecture_shape
197 fun is_typed_helper _ (_, SOME s) = is_typed_helper_name s
198 | is_typed_helper typed_helpers (num, NONE) =
199 (case extract_step_number num of
200 SOME i => member (op =) typed_helpers i
203 val leo2_ext = "extcnf_equal_neg"
204 val isa_ext = Thm.get_name_hint @{thm ext}
205 val isa_short_ext = Long_Name.base_name isa_ext
208 if Thm.eq_thm_prop (@{thm ext},
209 singleton (Attrib.eval_thms ctxt) (Facts.named isa_short_ext, [])) then
214 fun add_fact _ facts_offset fact_names (Inference (name, _, [])) =
215 union (op =) (resolve_fact facts_offset fact_names name)
216 | add_fact ctxt _ _ (Inference (_, _, deps)) =
217 if AList.defined (op =) deps leo2_ext then
218 insert (op =) (ext_name ctxt, Extensionality)
221 | add_fact _ _ _ _ = I
223 fun used_facts_in_atp_proof ctxt facts_offset fact_names atp_proof =
224 if null atp_proof then Vector.foldl (uncurry (union (op =))) [] fact_names
225 else fold (add_fact ctxt facts_offset fact_names) atp_proof []
227 fun is_conjecture_used_in_proof conjecture_shape =
228 exists (fn Inference (name, _, []) => is_conjecture conjecture_shape name
231 fun used_facts_in_unsound_atp_proof _ _ _ _ [] = NONE
232 | used_facts_in_unsound_atp_proof ctxt conjecture_shape facts_offset
233 fact_names atp_proof =
236 used_facts_in_atp_proof ctxt facts_offset fact_names atp_proof
238 if forall (is_locality_global o snd) used_facts andalso
239 not (is_conjecture_used_in_proof conjecture_shape atp_proof) then
240 SOME (map fst used_facts)
245 fun uses_typed_helpers typed_helpers =
246 exists (fn Inference (name, _, []) => is_typed_helper typed_helpers name
250 (** Soft-core proof reconstruction: Metis one-liner **)
252 (* unfortunate leaking abstraction *)
253 fun name_of_reconstructor Metis = "metis"
254 | name_of_reconstructor Metis_Full_Types = "metis (full_types)"
255 | name_of_reconstructor Metis_No_Types = "metis (no_types)"
256 | name_of_reconstructor (SMT _) = "smt"
258 fun reconstructor_settings (SMT settings) = settings
259 | reconstructor_settings _ = ""
261 fun string_for_label (s, num) = s ^ string_of_int num
263 fun show_time NONE = ""
264 | show_time (SOME ext_time) = " (" ^ string_from_ext_time ext_time ^ ")"
266 fun set_settings "" = ""
267 | set_settings settings = "using [[" ^ settings ^ "]] "
268 fun apply_on_subgoal settings _ 1 = set_settings settings ^ "by "
269 | apply_on_subgoal settings 1 _ = set_settings settings ^ "apply "
270 | apply_on_subgoal settings i n =
271 "prefer " ^ string_of_int i ^ " " ^ apply_on_subgoal settings 1 n
272 fun command_call name [] = name
273 | command_call name args = "(" ^ name ^ " " ^ space_implode " " args ^ ")"
274 fun try_command_line banner time command =
275 banner ^ ": " ^ Markup.markup Markup.sendback command ^ show_time time ^ "."
276 fun using_labels [] = ""
278 "using " ^ space_implode " " (map string_for_label ls) ^ " "
279 fun reconstructor_command reconstructor i n (ls, ss) =
281 apply_on_subgoal (reconstructor_settings reconstructor) i n ^
282 command_call (name_of_reconstructor reconstructor) ss
283 fun minimize_line _ [] = ""
284 | minimize_line minimize_command ss =
285 case minimize_command ss of
287 | command => "\nTo minimize: " ^ Markup.markup Markup.sendback command ^ "."
289 val split_used_facts =
290 List.partition (curry (op =) Chained o snd)
291 #> pairself (sort_distinct (string_ord o pairself fst))
293 fun one_line_proof_text (preplay, banner, used_facts, minimize_command,
294 subgoal, subgoal_count) =
296 val (chained, extra) = split_used_facts used_facts
297 val (failed, reconstructor, ext_time) =
299 Played (reconstructor, time) =>
300 (false, reconstructor, (SOME (false, time)))
301 | Trust_Playable (reconstructor, time) =>
302 (false, reconstructor,
306 if time = Time.zeroTime then NONE else SOME (true, time))
307 | Failed_to_Play reconstructor => (true, reconstructor, NONE)
310 |> reconstructor_command reconstructor subgoal subgoal_count
311 |> (if failed then enclose "One-line proof reconstruction failed: " "."
312 else try_command_line banner ext_time)
313 in try_line ^ minimize_line minimize_command (map fst (extra @ chained)) end
315 (** Hard-core proof reconstruction: structured Isar proofs **)
317 (* Simple simplifications to ensure that sort annotations don't leave a trail of
319 fun s_not (Const (@{const_name All}, T) $ Abs (s, T', t')) =
320 Const (@{const_name Ex}, T) $ Abs (s, T', s_not t')
321 | s_not (Const (@{const_name Ex}, T) $ Abs (s, T', t')) =
322 Const (@{const_name All}, T) $ Abs (s, T', s_not t')
323 | s_not (@{const HOL.implies} $ t1 $ t2) = @{const HOL.conj} $ t1 $ s_not t2
324 | s_not (@{const HOL.conj} $ t1 $ t2) =
325 @{const HOL.disj} $ s_not t1 $ s_not t2
326 | s_not (@{const HOL.disj} $ t1 $ t2) =
327 @{const HOL.conj} $ s_not t1 $ s_not t2
328 | s_not (@{const False}) = @{const True}
329 | s_not (@{const True}) = @{const False}
330 | s_not (@{const Not} $ t) = t
331 | s_not t = @{const Not} $ t
332 fun s_conj (@{const True}, t2) = t2
333 | s_conj (t1, @{const True}) = t1
334 | s_conj p = HOLogic.mk_conj p
335 fun s_disj (@{const False}, t2) = t2
336 | s_disj (t1, @{const False}) = t1
337 | s_disj p = HOLogic.mk_disj p
338 fun s_imp (@{const True}, t2) = t2
339 | s_imp (t1, @{const False}) = s_not t1
340 | s_imp p = HOLogic.mk_imp p
341 fun s_iff (@{const True}, t2) = t2
342 | s_iff (t1, @{const True}) = t1
343 | s_iff (t1, t2) = HOLogic.eq_const HOLogic.boolT $ t1 $ t2
345 fun forall_of v t = HOLogic.all_const (fastype_of v) $ lambda v t
346 fun exists_of v t = HOLogic.exists_const (fastype_of v) $ lambda v t
348 fun make_tvar s = TVar (("'" ^ s, 0), HOLogic.typeS)
349 fun make_tfree ctxt w =
350 let val ww = "'" ^ w in
351 TFree (ww, the_default HOLogic.typeS (Variable.def_sort ctxt (ww, ~1)))
355 val no_label = ("", ~1)
358 val assum_prefix = "A"
359 val have_prefix = "F"
361 fun raw_label_for_name conjecture_shape name =
362 case resolve_conjecture conjecture_shape name of
363 [j] => (conjecture_prefix, j)
364 | _ => case Int.fromString (fst name) of
365 SOME j => (raw_prefix, j)
366 | NONE => (raw_prefix ^ fst name, 0)
368 (**** INTERPRETATION OF TSTP SYNTAX TREES ****)
370 exception FO_TERM of string fo_term list
371 exception FORMULA of (string, string, string fo_term) formula list
372 exception SAME of unit
374 (* Type variables are given the basic sort "HOL.type". Some will later be
375 constrained by information from type literals, or by type inference. *)
376 fun typ_from_atp ctxt (u as ATerm (a, us)) =
377 let val Ts = map (typ_from_atp ctxt) us in
378 case strip_prefix_and_unascii type_const_prefix a of
379 SOME b => Type (invert_const b, Ts)
381 if not (null us) then
382 raise FO_TERM [u] (* only "tconst"s have type arguments *)
383 else case strip_prefix_and_unascii tfree_prefix a of
384 SOME b => make_tfree ctxt b
386 (* Could be an Isabelle variable or a variable from the ATP, say "X1"
387 or "_5018". Sometimes variables from the ATP are indistinguishable
388 from Isabelle variables, which forces us to use a type parameter in
390 (a |> perhaps (strip_prefix_and_unascii tvar_prefix), HOLogic.typeS)
391 |> Type_Infer.param 0
394 (* Type class literal applied to a type. Returns triple of polarity, class,
396 fun type_constraint_from_term ctxt (u as ATerm (a, us)) =
397 case (strip_prefix_and_unascii class_prefix a, map (typ_from_atp ctxt) us) of
398 (SOME b, [T]) => (b, T)
399 | _ => raise FO_TERM [u]
401 (** Accumulate type constraints in a formula: negative type literals **)
402 fun add_var (key, z) = Vartab.map_default (key, []) (cons z)
403 fun add_type_constraint false (cl, TFree (a ,_)) = add_var ((a, ~1), cl)
404 | add_type_constraint false (cl, TVar (ix, _)) = add_var (ix, cl)
405 | add_type_constraint _ _ = I
407 fun repair_variable_name f s =
409 fun subscript_name s n = s ^ nat_subscript n
410 val s = String.map f s
412 case space_explode "_" s of
413 [_] => (case take_suffix Char.isDigit (String.explode s) of
414 (cs1 as _ :: _, cs2 as _ :: _) =>
415 subscript_name (String.implode cs1)
416 (the (Int.fromString (String.implode cs2)))
418 | [s1, s2] => (case Int.fromString s2 of
419 SOME n => subscript_name s1 n
424 fun slack_fastype_of t = fastype_of t handle TERM _ => HOLogic.typeT
426 (* First-order translation. No types are known for variables. "HOLogic.typeT"
427 should allow them to be inferred. *)
428 fun term_from_atp ctxt textual sym_tab =
430 val thy = Proof_Context.theory_of ctxt
431 (* For Metis, we use 1 rather than 0 because variable references in clauses
432 may otherwise conflict with variable constraints in the goal. At least,
433 type inference often fails otherwise. See also "axiom_inference" in
434 "Metis_Reconstruct". *)
435 val var_index = if textual then 0 else 1
436 fun do_term extra_ts opt_T u =
439 if String.isPrefix simple_type_prefix a then
440 @{const True} (* ignore TPTP type information *)
441 else if a = tptp_equal then
442 let val ts = map (do_term [] NONE) us in
443 if textual andalso length ts = 2 andalso
444 hd ts aconv List.last ts then
445 (* Vampire is keen on producing these. *)
448 list_comb (Const (@{const_name HOL.eq}, HOLogic.typeT), ts)
450 else case strip_prefix_and_unascii const_prefix a of
453 val ((s', s), mangled_us) = s |> unmangled_const |>> `invert_const
455 if s' = type_tag_name then
456 case mangled_us @ us of
458 do_term extra_ts (SOME (typ_from_atp ctxt typ_u)) term_u
459 | _ => raise FO_TERM us
460 else if s' = predicator_name then
461 do_term [] (SOME @{typ bool}) (hd us)
462 else if s' = app_op_name then
463 let val extra_t = do_term [] NONE (List.last us) in
464 do_term (extra_t :: extra_ts)
466 SOME T => SOME (slack_fastype_of extra_t --> T)
468 (nth us (length us - 2))
470 else if s' = type_pred_name then
471 @{const True} (* ignore type predicates *)
474 val new_skolem = String.isPrefix new_skolem_const_prefix s
476 length us - the_default 0 (Symtab.lookup sym_tab s)
477 val (type_us, term_us) =
478 chop num_ty_args us |>> append mangled_us
479 val term_ts = map (do_term [] NONE) term_us
481 (if not (null type_us) andalso
482 num_type_args thy s' = length type_us then
483 let val Ts = type_us |> map (typ_from_atp ctxt) in
485 SOME (Type_Infer.paramify_vars (tl Ts ---> hd Ts))
487 try (Sign.const_instance thy) (s', Ts)
494 | NONE => map slack_fastype_of term_ts --->
497 | NONE => HOLogic.typeT))
500 Var ((new_skolem_var_name_from_const s, var_index), T)
502 Const (unproxify_const s', T)
503 in list_comb (t, term_ts @ extra_ts) end
505 | NONE => (* a free or schematic variable *)
507 val ts = map (do_term [] NONE) us @ extra_ts
508 val T = map slack_fastype_of ts ---> HOLogic.typeT
510 case strip_prefix_and_unascii fixed_var_prefix a of
511 SOME b => Free (b, T)
513 case strip_prefix_and_unascii schematic_var_prefix a of
514 SOME b => Var ((b, var_index), T)
516 Var ((a |> textual ? repair_variable_name Char.toLower,
518 in list_comb (t, ts) end
521 fun term_from_atom ctxt textual sym_tab pos (u as ATerm (s, _)) =
522 if String.isPrefix class_prefix s then
523 add_type_constraint pos (type_constraint_from_term ctxt u)
524 #> pair @{const True}
526 pair (term_from_atp ctxt textual sym_tab (SOME @{typ bool}) u)
528 val combinator_table =
529 [(@{const_name Meson.COMBI}, @{thm Meson.COMBI_def_raw}),
530 (@{const_name Meson.COMBK}, @{thm Meson.COMBK_def_raw}),
531 (@{const_name Meson.COMBB}, @{thm Meson.COMBB_def_raw}),
532 (@{const_name Meson.COMBC}, @{thm Meson.COMBC_def_raw}),
533 (@{const_name Meson.COMBS}, @{thm Meson.COMBS_def_raw})]
535 fun uncombine_term thy =
537 fun aux (t1 $ t2) = betapply (pairself aux (t1, t2))
538 | aux (Abs (s, T, t')) = Abs (s, T, aux t')
539 | aux (t as Const (x as (s, _))) =
540 (case AList.lookup (op =) combinator_table s of
541 SOME thm => thm |> prop_of |> specialize_type thy x
542 |> Logic.dest_equals |> snd
547 (* Update schematic type variables with detected sort constraints. It's not
548 totally clear whether this code is necessary. *)
549 fun repair_tvar_sorts (t, tvar_tab) =
551 fun do_type (Type (a, Ts)) = Type (a, map do_type Ts)
552 | do_type (TVar (xi, s)) =
553 TVar (xi, the_default s (Vartab.lookup tvar_tab xi))
554 | do_type (TFree z) = TFree z
555 fun do_term (Const (a, T)) = Const (a, do_type T)
556 | do_term (Free (a, T)) = Free (a, do_type T)
557 | do_term (Var (xi, T)) = Var (xi, do_type T)
558 | do_term (t as Bound _) = t
559 | do_term (Abs (a, T, t)) = Abs (a, do_type T, do_term t)
560 | do_term (t1 $ t2) = do_term t1 $ do_term t2
561 in t |> not (Vartab.is_empty tvar_tab) ? do_term end
563 fun quantify_over_var quant_of var_s t =
565 val vars = [] |> Term.add_vars t |> filter (fn ((s, _), _) => s = var_s)
567 in fold_rev quant_of vars t end
569 (* Interpret an ATP formula as a HOL term, extracting sort constraints as they
570 appear in the formula. *)
571 fun prop_from_atp ctxt textual sym_tab phi =
573 fun do_formula pos phi =
575 AQuant (_, [], phi) => do_formula pos phi
576 | AQuant (q, (s, _) :: xs, phi') =>
577 do_formula pos (AQuant (q, xs, phi'))
579 #>> quantify_over_var (case q of
581 | AExists => exists_of)
582 (s |> textual ? repair_variable_name Char.toLower)
583 | AConn (ANot, [phi']) => do_formula (not pos) phi' #>> s_not
584 | AConn (c, [phi1, phi2]) =>
585 do_formula (pos |> c = AImplies ? not) phi1
586 ##>> do_formula pos phi2
592 | ANot => raise Fail "impossible connective")
593 | AAtom tm => term_from_atom ctxt textual sym_tab pos tm
594 | _ => raise FORMULA [phi]
595 in repair_tvar_sorts (do_formula true phi Vartab.empty) end
597 fun infer_formula_types ctxt =
598 Type.constraint HOLogic.boolT
600 (Proof_Context.set_mode Proof_Context.mode_schematic ctxt)
602 fun uncombined_etc_prop_from_atp ctxt textual sym_tab =
603 let val thy = Proof_Context.theory_of ctxt in
604 prop_from_atp ctxt textual sym_tab
605 #> textual ? uncombine_term thy #> infer_formula_types ctxt
608 (**** Translation of TSTP files to Isar proofs ****)
610 fun unvarify_term (Var ((s, 0), T)) = Free (s, T)
611 | unvarify_term t = raise TERM ("unvarify_term: non-Var", [t])
613 fun decode_line sym_tab (Definition (name, phi1, phi2)) ctxt =
615 val thy = Proof_Context.theory_of ctxt
616 val t1 = prop_from_atp ctxt true sym_tab phi1
617 val vars = snd (strip_comb t1)
618 val frees = map unvarify_term vars
619 val unvarify_args = subst_atomic (vars ~~ frees)
620 val t2 = prop_from_atp ctxt true sym_tab phi2
622 HOLogic.eq_const HOLogic.typeT $ t1 $ t2
623 |> unvarify_args |> uncombine_term thy |> infer_formula_types ctxt
626 (Definition (name, t1, t2),
627 fold Variable.declare_term (maps OldTerm.term_frees [t1, t2]) ctxt)
629 | decode_line sym_tab (Inference (name, u, deps)) ctxt =
630 let val t = u |> uncombined_etc_prop_from_atp ctxt true sym_tab in
631 (Inference (name, t, deps),
632 fold Variable.declare_term (OldTerm.term_frees t) ctxt)
634 fun decode_lines ctxt sym_tab lines =
635 fst (fold_map (decode_line sym_tab) lines ctxt)
637 fun is_same_inference _ (Definition _) = false
638 | is_same_inference t (Inference (_, t', _)) = t aconv t'
640 (* No "real" literals means only type information (tfree_tcs, clsrel, or
642 val is_only_type_information = curry (op aconv) HOLogic.true_const
644 fun replace_one_dependency (old, new) dep =
645 if is_same_atp_step dep old then new else [dep]
646 fun replace_dependencies_in_line _ (line as Definition _) = line
647 | replace_dependencies_in_line p (Inference (name, t, deps)) =
648 Inference (name, t, fold (union (op =) o replace_one_dependency p) deps [])
650 (* Discard facts; consolidate adjacent lines that prove the same formula, since
651 they differ only in type information.*)
652 fun add_line _ _ (line as Definition _) lines = line :: lines
653 | add_line conjecture_shape fact_names (Inference (name, t, [])) lines =
654 (* No dependencies: fact, conjecture, or (for Vampire) internal facts or
656 if is_fact fact_names name then
657 (* Facts are not proof lines. *)
658 if is_only_type_information t then
659 map (replace_dependencies_in_line (name, [])) lines
660 (* Is there a repetition? If so, replace later line by earlier one. *)
661 else case take_prefix (not o is_same_inference t) lines of
662 (_, []) => lines (* no repetition of proof line *)
663 | (pre, Inference (name', _, _) :: post) =>
664 pre @ map (replace_dependencies_in_line (name', [name])) post
665 | _ => raise Fail "unexpected inference"
666 else if is_conjecture conjecture_shape name then
667 Inference (name, s_not t, []) :: lines
669 map (replace_dependencies_in_line (name, [])) lines
670 | add_line _ _ (Inference (name, t, deps)) lines =
671 (* Type information will be deleted later; skip repetition test. *)
672 if is_only_type_information t then
673 Inference (name, t, deps) :: lines
674 (* Is there a repetition? If so, replace later line by earlier one. *)
675 else case take_prefix (not o is_same_inference t) lines of
676 (* FIXME: Doesn't this code risk conflating proofs involving different
678 (_, []) => Inference (name, t, deps) :: lines
679 | (pre, Inference (name', t', _) :: post) =>
680 Inference (name, t', deps) ::
681 pre @ map (replace_dependencies_in_line (name', [name])) post
682 | _ => raise Fail "unexpected inference"
684 (* Recursively delete empty lines (type information) from the proof. *)
685 fun add_nontrivial_line (Inference (name, t, [])) lines =
686 if is_only_type_information t then delete_dependency name lines
687 else Inference (name, t, []) :: lines
688 | add_nontrivial_line line lines = line :: lines
689 and delete_dependency name lines =
690 fold_rev add_nontrivial_line
691 (map (replace_dependencies_in_line (name, [])) lines) []
693 (* ATPs sometimes reuse free variable names in the strangest ways. Removing
694 offending lines often does the trick. *)
695 fun is_bad_free frees (Free x) = not (member (op =) frees x)
696 | is_bad_free _ _ = false
698 fun add_desired_line _ _ _ _ (line as Definition (name, _, _)) (j, lines) =
699 (j, line :: map (replace_dependencies_in_line (name, [])) lines)
700 | add_desired_line isar_shrink_factor conjecture_shape fact_names frees
701 (Inference (name, t, deps)) (j, lines) =
703 if is_fact fact_names name orelse is_conjecture conjecture_shape name orelse
704 (* the last line must be kept *)
706 (not (is_only_type_information t) andalso
707 null (Term.add_tvars t []) andalso
708 not (exists_subterm (is_bad_free frees) t) andalso
709 length deps >= 2 andalso j mod isar_shrink_factor = 0 andalso
710 (* kill next to last line, which usually results in a trivial step *)
712 Inference (name, t, deps) :: lines (* keep line *)
714 map (replace_dependencies_in_line (name, deps)) lines) (* drop line *)
716 (** Isar proof construction and manipulation **)
718 fun merge_fact_sets (ls1, ss1) (ls2, ss2) =
719 (union (op =) ls1 ls2, union (op =) ss1 ss2)
721 type label = string * int
722 type facts = label list * string list
724 datatype isar_qualifier = Show | Then | Moreover | Ultimately
727 Fix of (string * typ) list |
729 Assume of label * term |
730 Have of isar_qualifier list * label * term * byline
733 CaseSplit of isar_step list list * facts
735 fun smart_case_split [] facts = ByMetis facts
736 | smart_case_split proofs facts = CaseSplit (proofs, facts)
738 fun add_fact_from_dependency conjecture_shape facts_offset fact_names name =
739 if is_fact fact_names name then
740 apsnd (union (op =) (map fst (resolve_fact facts_offset fact_names name)))
742 apfst (insert (op =) (raw_label_for_name conjecture_shape name))
744 fun step_for_line _ _ _ _ (Definition (_, t1, t2)) = Let (t1, t2)
745 | step_for_line conjecture_shape _ _ _ (Inference (name, t, [])) =
746 Assume (raw_label_for_name conjecture_shape name, t)
747 | step_for_line conjecture_shape facts_offset fact_names j
748 (Inference (name, t, deps)) =
749 Have (if j = 1 then [Show] else [],
750 raw_label_for_name conjecture_shape name,
751 fold_rev forall_of (map Var (Term.add_vars t [])) t,
752 ByMetis (fold (add_fact_from_dependency conjecture_shape facts_offset
756 fun repair_name "$true" = "c_True"
757 | repair_name "$false" = "c_False"
758 | repair_name "$$e" = tptp_equal (* seen in Vampire proofs *)
760 if is_tptp_equal s orelse
761 (* seen in Vampire proofs *)
762 (String.isPrefix "sQ" s andalso String.isSuffix "_eqProxy" s) then
767 fun isar_proof_from_atp_proof pool ctxt isar_shrink_factor conjecture_shape
768 facts_offset fact_names sym_tab params frees atp_proof =
772 |> clean_up_atp_proof_dependencies
773 |> nasty_atp_proof pool
774 |> map_term_names_in_atp_proof repair_name
775 |> decode_lines ctxt sym_tab
776 |> rpair [] |-> fold_rev (add_line conjecture_shape fact_names)
777 |> rpair [] |-> fold_rev add_nontrivial_line
779 |-> fold_rev (add_desired_line isar_shrink_factor conjecture_shape
783 (if null params then [] else [Fix params]) @
784 map2 (step_for_line conjecture_shape facts_offset fact_names)
785 (length lines downto 1) lines
788 (* When redirecting proofs, we keep information about the labels seen so far in
789 the "backpatches" data structure. The first component indicates which facts
790 should be associated with forthcoming proof steps. The second component is a
791 pair ("assum_ls", "drop_ls"), where "assum_ls" are the labels that should
792 become assumptions and "drop_ls" are the labels that should be dropped in a
794 type backpatches = (label * facts) list * (label list * label list)
796 fun used_labels_of_step (Have (_, _, _, by)) =
798 ByMetis (ls, _) => ls
799 | CaseSplit (proofs, (ls, _)) =>
800 fold (union (op =) o used_labels_of) proofs ls)
801 | used_labels_of_step _ = []
802 and used_labels_of proof = fold (union (op =) o used_labels_of_step) proof []
804 fun new_labels_of_step (Fix _) = []
805 | new_labels_of_step (Let _) = []
806 | new_labels_of_step (Assume (l, _)) = [l]
807 | new_labels_of_step (Have (_, l, _, _)) = [l]
808 val new_labels_of = maps new_labels_of_step
813 | aux proof_tail (proofs as (proof1 :: _)) =
814 if exists null proofs then
816 else if forall (curry (op =) (hd proof1) o hd) (tl proofs) then
817 aux (hd proof1 :: proof_tail) (map tl proofs)
818 else case hd proof1 of
819 Have ([], l, t, _) => (* FIXME: should we really ignore the "by"? *)
820 if forall (fn Have ([], l', t', _) :: _ => (l, t) = (l', t')
821 | _ => false) (tl proofs) andalso
822 not (exists (member (op =) (maps new_labels_of proofs))
823 (used_labels_of proof_tail)) then
824 SOME (l, t, map rev proofs, proof_tail)
828 in aux [] o map rev end
830 fun case_split_qualifiers proofs =
831 case length proofs of
836 fun redirect_proof hyp_ts concl_t proof =
838 (* The first pass outputs those steps that are independent of the negated
839 conjecture. The second pass flips the proof by contradiction to obtain a
840 direct proof, introducing case splits when an inference depends on
841 several facts that depend on the negated conjecture. *)
842 val concl_l = (conjecture_prefix, length hyp_ts)
843 fun first_pass ([], contra) = ([], contra)
844 | first_pass ((step as Fix _) :: proof, contra) =
845 first_pass (proof, contra) |>> cons step
846 | first_pass ((step as Let _) :: proof, contra) =
847 first_pass (proof, contra) |>> cons step
848 | first_pass ((step as Assume (l as (_, j), _)) :: proof, contra) =
849 if l = concl_l then first_pass (proof, contra ||> cons step)
850 else first_pass (proof, contra) |>> cons (Assume (l, nth hyp_ts j))
851 | first_pass (Have (qs, l, t, ByMetis (ls, ss)) :: proof, contra) =
852 let val step = Have (qs, l, t, ByMetis (ls, ss)) in
853 if exists (member (op =) (fst contra)) ls then
854 first_pass (proof, contra |>> cons l ||> cons step)
856 first_pass (proof, contra) |>> cons step
858 | first_pass _ = raise Fail "malformed proof"
859 val (proof_top, (contra_ls, contra_proof)) =
860 first_pass (proof, ([concl_l], []))
861 val backpatch_label = the_default ([], []) oo AList.lookup (op =) o fst
862 fun backpatch_labels patches ls =
863 fold merge_fact_sets (map (backpatch_label patches) ls) ([], [])
864 fun second_pass end_qs ([], assums, patches) =
865 ([Have (end_qs, no_label, concl_t,
866 ByMetis (backpatch_labels patches (map snd assums)))], patches)
867 | second_pass end_qs (Assume (l, t) :: proof, assums, patches) =
868 second_pass end_qs (proof, (t, l) :: assums, patches)
869 | second_pass end_qs (Have (qs, l, t, ByMetis (ls, ss)) :: proof, assums,
871 (if member (op =) (snd (snd patches)) l andalso
872 not (member (op =) (fst (snd patches)) l) andalso
873 not (AList.defined (op =) (fst patches) l) then
874 second_pass end_qs (proof, assums, patches ||> apsnd (append ls))
875 else case List.partition (member (op =) contra_ls) ls of
876 ([contra_l], co_ls) =>
877 if member (op =) qs Show then
878 second_pass end_qs (proof, assums,
879 patches |>> cons (contra_l, (co_ls, ss)))
883 patches |>> cons (contra_l, (l :: co_ls, ss)))
884 |>> cons (if member (op =) (fst (snd patches)) l then
887 Have (qs, l, s_not t,
888 ByMetis (backpatch_label patches l)))
889 | (contra_ls as _ :: _, co_ls) =>
898 val drop_ls = filter (curry (op <>) l) contra_ls
902 patches ||> apfst (insert (op =) l)
903 ||> apsnd (union (op =) drop_ls))
906 val (assumes, facts) =
907 if member (op =) (fst (snd patches)) l then
908 ([Assume (l, s_not t)], (l :: co_ls, ss))
912 (case join_proofs proofs of
913 SOME (l, t, proofs, proof_tail) =>
914 Have (case_split_qualifiers proofs @
915 (if null proof_tail then end_qs else []), l, t,
916 smart_case_split proofs facts) :: proof_tail
918 [Have (case_split_qualifiers proofs @ end_qs, no_label,
919 concl_t, smart_case_split proofs facts)],
923 | _ => raise Fail "malformed proof")
924 | second_pass _ _ = raise Fail "malformed proof"
926 second_pass [Show] (contra_proof, [], ([], ([], []))) |> fst
927 in proof_top @ proof_bottom end
929 (* FIXME: Still needed? Probably not. *)
930 val kill_duplicate_assumptions_in_proof =
932 fun relabel_facts subst =
933 apfst (map (fn l => AList.lookup (op =) subst l |> the_default l))
934 fun do_step (step as Assume (l, t)) (proof, subst, assums) =
935 (case AList.lookup (op aconv) assums t of
936 SOME l' => (proof, (l, l') :: subst, assums)
937 | NONE => (step :: proof, subst, (t, l) :: assums))
938 | do_step (Have (qs, l, t, by)) (proof, subst, assums) =
941 ByMetis facts => ByMetis (relabel_facts subst facts)
942 | CaseSplit (proofs, facts) =>
943 CaseSplit (map do_proof proofs, relabel_facts subst facts)) ::
944 proof, subst, assums)
945 | do_step step (proof, subst, assums) = (step :: proof, subst, assums)
946 and do_proof proof = fold do_step proof ([], [], []) |> #1 |> rev
949 val then_chain_proof =
952 | aux _ ((step as Assume (l, _)) :: proof) = step :: aux l proof
953 | aux l' (Have (qs, l, t, by) :: proof) =
956 Have (if member (op =) ls l' then
958 ByMetis (filter_out (curry (op =) l') ls, ss))
960 (qs, l, t, ByMetis (ls, ss)))
961 | CaseSplit (proofs, facts) =>
962 Have (qs, l, t, CaseSplit (map (aux no_label) proofs, facts))) ::
964 | aux _ (step :: proof) = step :: aux no_label proof
967 fun kill_useless_labels_in_proof proof =
969 val used_ls = used_labels_of proof
970 fun do_label l = if member (op =) used_ls l then l else no_label
971 fun do_step (Assume (l, t)) = Assume (do_label l, t)
972 | do_step (Have (qs, l, t, by)) =
973 Have (qs, do_label l, t,
975 CaseSplit (proofs, facts) =>
976 CaseSplit (map (map do_step) proofs, facts)
978 | do_step step = step
979 in map do_step proof end
981 fun prefix_for_depth n = replicate_string (n + 1)
985 fun aux _ _ _ [] = []
986 | aux subst depth (next_assum, next_fact) (Assume (l, t) :: proof) =
988 Assume (l, t) :: aux subst depth (next_assum, next_fact) proof
990 let val l' = (prefix_for_depth depth assum_prefix, next_assum) in
992 aux ((l, l') :: subst) depth (next_assum + 1, next_fact) proof
994 | aux subst depth (next_assum, next_fact) (Have (qs, l, t, by) :: proof) =
996 val (l', subst, next_fact) =
998 (l, subst, next_fact)
1001 val l' = (prefix_for_depth depth have_prefix, next_fact)
1002 in (l', (l, l') :: subst, next_fact + 1) end
1004 apfst (maps (the_list o AList.lookup (op =) subst))
1007 ByMetis facts => ByMetis (relabel_facts facts)
1008 | CaseSplit (proofs, facts) =>
1009 CaseSplit (map (aux subst (depth + 1) (1, 1)) proofs,
1010 relabel_facts facts)
1012 Have (qs, l', t, by) ::
1013 aux subst depth (next_assum, next_fact) proof
1015 | aux subst depth nextp (step :: proof) =
1016 step :: aux subst depth nextp proof
1017 in aux [] 0 (1, 1) end
1019 fun string_for_proof ctxt0 full_types i n =
1022 ctxt0 |> Config.put show_free_types false
1023 |> Config.put show_types true
1024 |> Config.put show_sorts true
1025 fun fix_print_mode f x =
1026 Print_Mode.setmp (filter (curry (op =) Symbol.xsymbolsN)
1027 (print_mode_value ())) f x
1028 fun do_indent ind = replicate_string (ind * indent_size) " "
1029 fun do_free (s, T) =
1030 maybe_quote s ^ " :: " ^
1031 maybe_quote (fix_print_mode (Syntax.string_of_typ ctxt) T)
1032 fun do_label l = if l = no_label then "" else string_for_label l ^ ": "
1034 (if member (op =) qs Moreover then "moreover " else "") ^
1035 (if member (op =) qs Ultimately then "ultimately " else "") ^
1036 (if member (op =) qs Then then
1037 if member (op =) qs Show then "thus" else "hence"
1039 if member (op =) qs Show then "show" else "have")
1040 val do_term = maybe_quote o fix_print_mode (Syntax.string_of_term ctxt)
1041 val reconstructor = if full_types then Metis_Full_Types else Metis
1042 fun do_facts (ls, ss) =
1043 reconstructor_command reconstructor 1 1
1044 (ls |> sort_distinct (prod_ord string_ord int_ord),
1045 ss |> sort_distinct string_ord)
1046 and do_step ind (Fix xs) =
1047 do_indent ind ^ "fix " ^ space_implode " and " (map do_free xs) ^ "\n"
1048 | do_step ind (Let (t1, t2)) =
1049 do_indent ind ^ "let " ^ do_term t1 ^ " = " ^ do_term t2 ^ "\n"
1050 | do_step ind (Assume (l, t)) =
1051 do_indent ind ^ "assume " ^ do_label l ^ do_term t ^ "\n"
1052 | do_step ind (Have (qs, l, t, ByMetis facts)) =
1053 do_indent ind ^ do_have qs ^ " " ^
1054 do_label l ^ do_term t ^ " " ^ do_facts facts ^ "\n"
1055 | do_step ind (Have (qs, l, t, CaseSplit (proofs, facts))) =
1056 space_implode (do_indent ind ^ "moreover\n")
1057 (map (do_block ind) proofs) ^
1058 do_indent ind ^ do_have qs ^ " " ^ do_label l ^ do_term t ^ " " ^
1059 do_facts facts ^ "\n"
1060 and do_steps prefix suffix ind steps =
1061 let val s = implode (map (do_step ind) steps) in
1062 replicate_string (ind * indent_size - size prefix) " " ^ prefix ^
1063 String.extract (s, ind * indent_size,
1064 SOME (size s - ind * indent_size - 1)) ^
1067 and do_block ind proof = do_steps "{ " " }" (ind + 1) proof
1068 (* One-step proofs are pointless; better use the Metis one-liner
1070 and do_proof [Have (_, _, _, ByMetis _)] = ""
1072 (if i <> 1 then "prefer " ^ string_of_int i ^ "\n" else "") ^
1073 do_indent 0 ^ "proof -\n" ^ do_steps "" "" 1 proof ^ do_indent 0 ^
1074 (if n <> 1 then "next" else "qed")
1077 fun isar_proof_text ctxt isar_proof_requested
1078 (debug, full_types, isar_shrink_factor, pool, conjecture_shape,
1079 facts_offset, fact_names, sym_tab, atp_proof, goal)
1080 (one_line_params as (_, _, _, _, subgoal, subgoal_count)) =
1082 val isar_shrink_factor =
1083 (if isar_proof_requested then 1 else 2) * isar_shrink_factor
1084 val (params, hyp_ts, concl_t) = strip_subgoal ctxt goal subgoal
1085 val frees = fold Term.add_frees (concl_t :: hyp_ts) []
1086 val one_line_proof = one_line_proof_text one_line_params
1087 fun isar_proof_for () =
1089 |> isar_proof_from_atp_proof pool ctxt isar_shrink_factor
1090 conjecture_shape facts_offset fact_names sym_tab params frees
1091 |> redirect_proof hyp_ts concl_t
1092 |> kill_duplicate_assumptions_in_proof
1094 |> kill_useless_labels_in_proof
1096 |> string_for_proof ctxt full_types subgoal subgoal_count of
1098 if isar_proof_requested then
1099 "\nNo structured proof available (proof too short)."
1103 "\n\n" ^ (if isar_proof_requested then "Structured proof"
1104 else "Perhaps this will work") ^
1105 ":\n" ^ Markup.markup Markup.sendback proof
1110 case try isar_proof_for () of
1112 | NONE => if isar_proof_requested then
1113 "\nWarning: The Isar proof construction failed."
1116 in one_line_proof ^ isar_proof end
1118 fun proof_text ctxt isar_proof isar_params
1119 (one_line_params as (preplay, _, _, _, _, _)) =
1120 (if case preplay of Failed_to_Play _ => true | _ => isar_proof then
1121 isar_proof_text ctxt isar_proof isar_params
1123 one_line_proof_text) one_line_params