blanchet@45515
|
1 |
(* Title: HOL/Tools/Metis/metis_tactic.ML
|
blanchet@38261
|
2 |
Author: Kong W. Susanto, Cambridge University Computer Laboratory
|
blanchet@38261
|
3 |
Author: Lawrence C. Paulson, Cambridge University Computer Laboratory
|
blanchet@38261
|
4 |
Author: Jasmin Blanchette, TU Muenchen
|
wenzelm@23442
|
5 |
Copyright Cambridge University 2007
|
wenzelm@23447
|
6 |
|
wenzelm@29266
|
7 |
HOL setup for the Metis prover.
|
wenzelm@23442
|
8 |
*)
|
wenzelm@23442
|
9 |
|
blanchet@45515
|
10 |
signature METIS_TACTIC =
|
wenzelm@23442
|
11 |
sig
|
blanchet@43891
|
12 |
val metisN : string
|
blanchet@44069
|
13 |
val full_typesN : string
|
blanchet@44069
|
14 |
val partial_typesN : string
|
blanchet@44069
|
15 |
val no_typesN : string
|
blanchet@44493
|
16 |
val really_full_type_enc : string
|
blanchet@44493
|
17 |
val full_type_enc : string
|
blanchet@44493
|
18 |
val partial_type_enc : string
|
blanchet@44493
|
19 |
val no_type_enc : string
|
blanchet@44174
|
20 |
val full_type_syss : string list
|
blanchet@44174
|
21 |
val partial_type_syss : string list
|
blanchet@40160
|
22 |
val trace : bool Config.T
|
blanchet@40913
|
23 |
val verbose : bool Config.T
|
blanchet@40072
|
24 |
val new_skolemizer : bool Config.T
|
blanchet@44053
|
25 |
val metis_tac : string list -> Proof.context -> thm list -> int -> tactic
|
blanchet@39737
|
26 |
val setup : theory -> theory
|
wenzelm@23442
|
27 |
end
|
wenzelm@23442
|
28 |
|
blanchet@45515
|
29 |
structure Metis_Tactic : METIS_TACTIC =
|
wenzelm@23442
|
30 |
struct
|
wenzelm@23442
|
31 |
|
blanchet@43926
|
32 |
open ATP_Translate
|
blanchet@39734
|
33 |
open Metis_Translate
|
blanchet@39737
|
34 |
open Metis_Reconstruct
|
blanchet@35826
|
35 |
|
wenzelm@44416
|
36 |
val metisN = "metis"
|
blanchet@44069
|
37 |
|
blanchet@44046
|
38 |
val full_typesN = "full_types"
|
blanchet@44069
|
39 |
val partial_typesN = "partial_types"
|
blanchet@44069
|
40 |
val no_typesN = "no_types"
|
blanchet@44052
|
41 |
|
blanchet@45349
|
42 |
val really_full_type_enc = "mono_tags_uniform"
|
blanchet@45261
|
43 |
val full_type_enc = "poly_guards_uniform_query"
|
blanchet@44493
|
44 |
val partial_type_enc = "poly_args"
|
blanchet@44493
|
45 |
val no_type_enc = "erased"
|
blanchet@44069
|
46 |
|
blanchet@44493
|
47 |
val full_type_syss = [full_type_enc, really_full_type_enc]
|
blanchet@44493
|
48 |
val partial_type_syss = partial_type_enc :: full_type_syss
|
blanchet@44174
|
49 |
|
blanchet@44493
|
50 |
val type_enc_aliases =
|
blanchet@44174
|
51 |
[(full_typesN, full_type_syss),
|
blanchet@44174
|
52 |
(partial_typesN, partial_type_syss),
|
blanchet@44493
|
53 |
(no_typesN, [no_type_enc])]
|
blanchet@43891
|
54 |
|
blanchet@44493
|
55 |
fun method_call_for_type_enc type_syss =
|
blanchet@44069
|
56 |
metisN ^ " (" ^
|
blanchet@44493
|
57 |
(case AList.find (op =) type_enc_aliases type_syss of
|
blanchet@44069
|
58 |
[alias] => alias
|
blanchet@44174
|
59 |
| _ => hd type_syss) ^ ")"
|
blanchet@44046
|
60 |
|
blanchet@43930
|
61 |
val new_skolemizer =
|
blanchet@43930
|
62 |
Attrib.setup_config_bool @{binding metis_new_skolemizer} (K false)
|
wenzelm@23442
|
63 |
|
blanchet@43975
|
64 |
(* Designed to work also with monomorphic instances of polymorphic theorems. *)
|
blanchet@39737
|
65 |
fun have_common_thm ths1 ths2 =
|
blanchet@44172
|
66 |
exists (member (Term.aconv_untyped o pairself prop_of) ths1)
|
blanchet@43975
|
67 |
(map Meson.make_meta_clause ths2)
|
wenzelm@32956
|
68 |
|
wenzelm@32956
|
69 |
(*Determining which axiom clauses are actually used*)
|
blanchet@39665
|
70 |
fun used_axioms axioms (th, Metis_Proof.Axiom _) = SOME (lookth axioms th)
|
blanchet@43969
|
71 |
| used_axioms _ _ = NONE
|
wenzelm@32956
|
72 |
|
blanchet@43970
|
73 |
(* Lightweight predicate type information comes in two flavors, "t = t'" and
|
blanchet@43970
|
74 |
"t => t'", where "t" and "t'" are the same term modulo type tags.
|
blanchet@43970
|
75 |
In Isabelle, type tags are stripped away, so we are left with "t = t" or
|
blanchet@44000
|
76 |
"t => t". Type tag idempotence is also handled this way. *)
|
blanchet@45347
|
77 |
fun reflexive_or_trivial_from_metis ctxt type_enc sym_tab old_skolems mth =
|
blanchet@43977
|
78 |
let val thy = Proof_Context.theory_of ctxt in
|
blanchet@45347
|
79 |
case hol_clause_from_metis ctxt type_enc sym_tab old_skolems mth of
|
blanchet@43977
|
80 |
Const (@{const_name HOL.eq}, _) $ _ $ t =>
|
blanchet@45267
|
81 |
let
|
blanchet@45267
|
82 |
val ct = cterm_of thy t
|
blanchet@45267
|
83 |
val cT = ctyp_of_term ct
|
blanchet@45267
|
84 |
in refl |> Drule.instantiate' [SOME cT] [SOME ct] end
|
blanchet@43977
|
85 |
| Const (@{const_name disj}, _) $ t1 $ t2 =>
|
blanchet@43977
|
86 |
(if can HOLogic.dest_not t1 then t2 else t1)
|
blanchet@43977
|
87 |
|> HOLogic.mk_Trueprop |> cterm_of thy |> Thm.trivial
|
blanchet@43977
|
88 |
| _ => raise Fail "unexpected tags sym clause"
|
blanchet@43977
|
89 |
end
|
blanchet@43970
|
90 |
|> Meson.make_meta_clause
|
blanchet@43970
|
91 |
|
blanchet@45452
|
92 |
val clause_params =
|
blanchet@39690
|
93 |
{ordering = Metis_KnuthBendixOrder.default,
|
blanchet@45347
|
94 |
orderLiterals = Metis_Clause.UnsignedLiteralOrder,
|
blanchet@39690
|
95 |
orderTerms = true}
|
blanchet@45452
|
96 |
val active_params =
|
blanchet@45452
|
97 |
{clause = clause_params,
|
blanchet@39690
|
98 |
prefactor = #prefactor Metis_Active.default,
|
blanchet@39690
|
99 |
postfactor = #postfactor Metis_Active.default}
|
blanchet@39690
|
100 |
val waiting_params =
|
blanchet@39690
|
101 |
{symbolsWeight = 1.0,
|
blanchet@39690
|
102 |
variablesWeight = 0.0,
|
blanchet@39690
|
103 |
literalsWeight = 0.0,
|
blanchet@39690
|
104 |
models = []}
|
blanchet@45452
|
105 |
val resolution_params = {active = active_params, waiting = waiting_params}
|
blanchet@37573
|
106 |
|
blanchet@37516
|
107 |
(* Main function to start Metis proof and reconstruction *)
|
blanchet@44493
|
108 |
fun FOL_SOLVE (type_enc :: fallback_type_syss) ctxt cls ths0 =
|
wenzelm@43232
|
109 |
let val thy = Proof_Context.theory_of ctxt
|
blanchet@40082
|
110 |
val new_skolemizer =
|
blanchet@40131
|
111 |
Config.get ctxt new_skolemizer orelse null (Meson.choice_theorems thy)
|
blanchet@35826
|
112 |
val th_cls_pairs =
|
blanchet@40075
|
113 |
map2 (fn j => fn th =>
|
blanchet@40075
|
114 |
(Thm.get_name_hint th,
|
blanchet@40082
|
115 |
Meson_Clausify.cnf_axiom ctxt new_skolemizer j th))
|
blanchet@40075
|
116 |
(0 upto length ths0 - 1) ths0
|
blanchet@43933
|
117 |
val ths = maps (snd o snd) th_cls_pairs
|
blanchet@40119
|
118 |
val dischargers = map (fst o snd) th_cls_pairs
|
blanchet@40159
|
119 |
val _ = trace_msg ctxt (fn () => "FOL_SOLVE: CONJECTURE CLAUSES")
|
blanchet@40159
|
120 |
val _ = app (fn th => trace_msg ctxt (fn () => Display.string_of_thm ctxt th)) cls
|
blanchet@40159
|
121 |
val _ = trace_msg ctxt (fn () => "THEOREM CLAUSES")
|
blanchet@43933
|
122 |
val _ = app (fn th => trace_msg ctxt (fn () => Display.string_of_thm ctxt th)) ths
|
blanchet@45270
|
123 |
val _ = trace_msg ctxt (fn () => "type_enc = " ^ type_enc)
|
blanchet@45492
|
124 |
val type_enc = type_enc_from_string Sound type_enc
|
blanchet@44053
|
125 |
val (sym_tab, axioms, old_skolems) =
|
blanchet@44493
|
126 |
prepare_metis_problem ctxt type_enc cls ths
|
blanchet@44000
|
127 |
fun get_isa_thm mth Isa_Reflexive_or_Trivial =
|
blanchet@45347
|
128 |
reflexive_or_trivial_from_metis ctxt type_enc sym_tab old_skolems mth
|
blanchet@44000
|
129 |
| get_isa_thm _ (Isa_Raw ith) = ith
|
blanchet@44000
|
130 |
val axioms = axioms |> map (fn (mth, ith) => (mth, get_isa_thm mth ith))
|
blanchet@40159
|
131 |
val _ = trace_msg ctxt (fn () => "CLAUSES GIVEN TO METIS")
|
blanchet@44000
|
132 |
val thms = axioms |> map fst
|
blanchet@40159
|
133 |
val _ = app (fn th => trace_msg ctxt (fn () => Metis_Thm.toString th)) thms
|
blanchet@40159
|
134 |
val _ = trace_msg ctxt (fn () => "START METIS PROVE PROCESS")
|
wenzelm@32956
|
135 |
in
|
blanchet@44000
|
136 |
case filter (fn t => prop_of t aconv @{prop False}) cls of
|
blanchet@44000
|
137 |
false_th :: _ => [false_th RS @{thm FalseE}]
|
wenzelm@32956
|
138 |
| [] =>
|
blanchet@45452
|
139 |
case Metis_Resolution.new resolution_params
|
blanchet@45270
|
140 |
{axioms = thms, conjecture = []}
|
blanchet@39737
|
141 |
|> Metis_Resolution.loop of
|
blanchet@39665
|
142 |
Metis_Resolution.Contradiction mth =>
|
blanchet@40159
|
143 |
let val _ = trace_msg ctxt (fn () => "METIS RECONSTRUCTION START: " ^
|
blanchet@39665
|
144 |
Metis_Thm.toString mth)
|
wenzelm@32956
|
145 |
val ctxt' = fold Variable.declare_constraints (map prop_of cls) ctxt
|
wenzelm@32956
|
146 |
(*add constraints arising from converting goal to clause form*)
|
blanchet@39665
|
147 |
val proof = Metis_Proof.proof mth
|
blanchet@43935
|
148 |
val result =
|
blanchet@44053
|
149 |
axioms
|
blanchet@45347
|
150 |
|> fold (replay_one_inference ctxt' type_enc old_skolems sym_tab) proof
|
blanchet@43975
|
151 |
val used = map_filter (used_axioms axioms) proof
|
blanchet@40159
|
152 |
val _ = trace_msg ctxt (fn () => "METIS COMPLETED...clauses actually used:")
|
blanchet@40159
|
153 |
val _ = app (fn th => trace_msg ctxt (fn () => Display.string_of_thm ctxt th)) used
|
blanchet@43975
|
154 |
val names = th_cls_pairs |> map fst
|
blanchet@43975
|
155 |
val used_names =
|
blanchet@43975
|
156 |
th_cls_pairs
|
blanchet@43975
|
157 |
|> map_filter (fn (name, (_, cls)) =>
|
blanchet@43975
|
158 |
if have_common_thm used cls then SOME name
|
blanchet@43975
|
159 |
else NONE)
|
blanchet@43975
|
160 |
val unused_names = names |> subtract (op =) used_names
|
wenzelm@32956
|
161 |
in
|
blanchet@39737
|
162 |
if not (null cls) andalso not (have_common_thm used cls) then
|
blanchet@43521
|
163 |
verbose_warning ctxt "The assumptions are inconsistent"
|
blanchet@36383
|
164 |
else
|
blanchet@36383
|
165 |
();
|
blanchet@43975
|
166 |
if not (null unused_names) then
|
blanchet@43975
|
167 |
"Unused theorems: " ^ commas_quote unused_names
|
blanchet@43975
|
168 |
|> verbose_warning ctxt
|
blanchet@36230
|
169 |
else
|
blanchet@36230
|
170 |
();
|
wenzelm@32956
|
171 |
case result of
|
wenzelm@32956
|
172 |
(_,ith)::_ =>
|
blanchet@40159
|
173 |
(trace_msg ctxt (fn () => "Success: " ^ Display.string_of_thm ctxt ith);
|
blanchet@40068
|
174 |
[discharge_skolem_premises ctxt dischargers ith])
|
blanchet@40159
|
175 |
| _ => (trace_msg ctxt (fn () => "Metis: No result"); [])
|
wenzelm@32956
|
176 |
end
|
blanchet@39665
|
177 |
| Metis_Resolution.Satisfiable _ =>
|
blanchet@40159
|
178 |
(trace_msg ctxt (fn () => "Metis: No first-order proof with the lemmas supplied");
|
blanchet@44053
|
179 |
if null fallback_type_syss then
|
blanchet@43875
|
180 |
()
|
blanchet@43875
|
181 |
else
|
blanchet@43521
|
182 |
raise METIS ("FOL_SOLVE",
|
blanchet@43875
|
183 |
"No first-order proof with the lemmas supplied");
|
blanchet@38343
|
184 |
[])
|
blanchet@43598
|
185 |
end
|
blanchet@43598
|
186 |
handle METIS (loc, msg) =>
|
blanchet@44053
|
187 |
case fallback_type_syss of
|
blanchet@43875
|
188 |
[] => error ("Failed to replay Metis proof in Isabelle." ^
|
blanchet@43875
|
189 |
(if Config.get ctxt verbose then "\n" ^ loc ^ ": " ^ msg
|
blanchet@43875
|
190 |
else ""))
|
blanchet@44174
|
191 |
| _ =>
|
blanchet@44069
|
192 |
(verbose_warning ctxt
|
blanchet@44069
|
193 |
("Falling back on " ^
|
blanchet@44493
|
194 |
quote (method_call_for_type_enc fallback_type_syss) ^ "...");
|
blanchet@44069
|
195 |
FOL_SOLVE fallback_type_syss ctxt cls ths0)
|
wenzelm@23442
|
196 |
|
blanchet@44835
|
197 |
fun neg_clausify ctxt =
|
blanchet@38262
|
198 |
single
|
blanchet@44835
|
199 |
#> Meson.make_clauses_unsorted ctxt
|
blanchet@40071
|
200 |
#> map Meson_Clausify.introduce_combinators_in_theorem
|
blanchet@38262
|
201 |
#> Meson.finish_cnf
|
blanchet@38262
|
202 |
|
blanchet@39496
|
203 |
fun preskolem_tac ctxt st0 =
|
blanchet@39496
|
204 |
(if exists (Meson.has_too_many_clauses ctxt)
|
blanchet@39496
|
205 |
(Logic.prems_of_goal (prop_of st0) 1) then
|
blanchet@43207
|
206 |
Simplifier.full_simp_tac (Meson_Clausify.ss_only @{thms not_all not_ex}) 1
|
blanchet@43207
|
207 |
THEN cnf.cnfx_rewrite_tac ctxt 1
|
blanchet@39496
|
208 |
else
|
blanchet@39496
|
209 |
all_tac) st0
|
blanchet@39496
|
210 |
|
blanchet@38890
|
211 |
val type_has_top_sort =
|
blanchet@38890
|
212 |
exists_subtype (fn TFree (_, []) => true | TVar (_, []) => true | _ => false)
|
blanchet@38890
|
213 |
|
blanchet@44053
|
214 |
fun generic_metis_tac type_syss ctxt ths i st0 =
|
blanchet@38166
|
215 |
let
|
blanchet@40159
|
216 |
val _ = trace_msg ctxt (fn () =>
|
blanchet@44035
|
217 |
"Metis called with theorems\n" ^
|
blanchet@43875
|
218 |
cat_lines (map (Display.string_of_thm ctxt) ths))
|
blanchet@44053
|
219 |
fun tac clause = resolve_tac (FOL_SOLVE type_syss ctxt clause ths) 1
|
wenzelm@32956
|
220 |
in
|
blanchet@37626
|
221 |
if exists_type type_has_top_sort (prop_of st0) then
|
blanchet@44170
|
222 |
verbose_warning ctxt "Proof state contains the universal sort {}"
|
wenzelm@35568
|
223 |
else
|
blanchet@44170
|
224 |
();
|
blanchet@44835
|
225 |
Meson.MESON (preskolem_tac ctxt) (maps (neg_clausify ctxt)) tac ctxt i st0
|
wenzelm@32956
|
226 |
end
|
wenzelm@23442
|
227 |
|
blanchet@44174
|
228 |
fun metis_tac [] = generic_metis_tac partial_type_syss
|
blanchet@44053
|
229 |
| metis_tac type_syss = generic_metis_tac type_syss
|
wenzelm@23442
|
230 |
|
blanchet@38855
|
231 |
(* Whenever "X" has schematic type variables, we treat "using X by metis" as
|
blanchet@43941
|
232 |
"by (metis X)" to prevent "Subgoal.FOCUS" from freezing the type variables.
|
blanchet@38855
|
233 |
We don't do it for nonschematic facts "X" because this breaks a few proofs
|
blanchet@38855
|
234 |
(in the rare and subtle case where a proof relied on extensionality not being
|
blanchet@39238
|
235 |
applied) and brings few benefits. *)
|
blanchet@38855
|
236 |
val has_tvar =
|
blanchet@38855
|
237 |
exists_type (exists_subtype (fn TVar _ => true | _ => false)) o prop_of
|
blanchet@43875
|
238 |
|
blanchet@44174
|
239 |
fun method default_type_syss (override_type_syss, ths) ctxt facts =
|
blanchet@43941
|
240 |
let
|
blanchet@44069
|
241 |
val _ =
|
blanchet@44174
|
242 |
if default_type_syss = full_type_syss then
|
wenzelm@44923
|
243 |
legacy_feature "Old \"metisFT\" method -- use \"metis (full_types)\" instead"
|
blanchet@44069
|
244 |
else
|
blanchet@44069
|
245 |
()
|
blanchet@43941
|
246 |
val (schem_facts, nonschem_facts) = List.partition has_tvar facts
|
blanchet@44174
|
247 |
val type_syss = override_type_syss |> the_default default_type_syss
|
blanchet@43941
|
248 |
in
|
blanchet@43940
|
249 |
HEADGOAL (Method.insert_tac nonschem_facts THEN'
|
blanchet@44053
|
250 |
CHANGED_PROP
|
blanchet@44053
|
251 |
o generic_metis_tac type_syss ctxt (schem_facts @ ths))
|
blanchet@43940
|
252 |
end
|
blanchet@43941
|
253 |
|
blanchet@44076
|
254 |
fun setup_method (binding, type_syss) =
|
blanchet@44174
|
255 |
((Args.parens (Scan.repeat Parse.short_ident)
|
blanchet@44834
|
256 |
>> maps (fn s => AList.lookup (op =) type_enc_aliases s |> the_default [s]))
|
blanchet@44174
|
257 |
|> Scan.option |> Scan.lift)
|
blanchet@44053
|
258 |
-- Attrib.thms >> (METHOD oo method type_syss)
|
blanchet@44069
|
259 |
|> Method.setup binding
|
wenzelm@23442
|
260 |
|
wenzelm@32956
|
261 |
val setup =
|
blanchet@44174
|
262 |
[((@{binding metis}, partial_type_syss),
|
blanchet@44069
|
263 |
"Metis for FOL and HOL problems"),
|
blanchet@44174
|
264 |
((@{binding metisFT}, full_type_syss),
|
blanchet@44053
|
265 |
"Metis for FOL/HOL problems with fully-typed translation")]
|
blanchet@43875
|
266 |
|> fold (uncurry setup_method)
|
wenzelm@23442
|
267 |
|
wenzelm@23442
|
268 |
end;
|