blanchet@47148
|
1 |
(* Title: HOL/Tools/Metis/metis_generate.ML
|
blanchet@38261
|
2 |
Author: Jia Meng, Cambridge University Computer Laboratory and NICTA
|
blanchet@39737
|
3 |
Author: Kong W. Susanto, Cambridge University Computer Laboratory
|
blanchet@39737
|
4 |
Author: Lawrence C. Paulson, Cambridge University Computer Laboratory
|
blanchet@36393
|
5 |
Author: Jasmin Blanchette, TU Muenchen
|
paulson@15347
|
6 |
|
blanchet@39734
|
7 |
Translation of HOL to FOL for Metis.
|
paulson@15347
|
8 |
*)
|
paulson@15347
|
9 |
|
blanchet@47148
|
10 |
signature METIS_GENERATE =
|
wenzelm@24310
|
11 |
sig
|
blanchet@47148
|
12 |
type type_enc = ATP_Problem_Generate.type_enc
|
blanchet@45270
|
13 |
|
blanchet@44000
|
14 |
datatype isa_thm =
|
blanchet@44000
|
15 |
Isa_Reflexive_or_Trivial |
|
blanchet@46382
|
16 |
Isa_Lambda_Lifted |
|
blanchet@44000
|
17 |
Isa_Raw of thm
|
blanchet@44000
|
18 |
|
blanchet@43935
|
19 |
val metis_equal : string
|
blanchet@43935
|
20 |
val metis_predicator : string
|
blanchet@43935
|
21 |
val metis_app_op : string
|
blanchet@45347
|
22 |
val metis_systematic_type_tag : string
|
blanchet@45347
|
23 |
val metis_ad_hoc_type_tag : string
|
blanchet@42962
|
24 |
val metis_generated_var_prefix : string
|
blanchet@44072
|
25 |
val trace : bool Config.T
|
blanchet@44072
|
26 |
val verbose : bool Config.T
|
blanchet@44072
|
27 |
val trace_msg : Proof.context -> (unit -> string) -> unit
|
blanchet@44072
|
28 |
val verbose_warning : Proof.context -> string -> unit
|
blanchet@45347
|
29 |
val metis_name_table : ((string * int) * ((type_enc -> string) * bool)) list
|
blanchet@40067
|
30 |
val reveal_old_skolem_terms : (string * term) list -> term -> term
|
blanchet@46440
|
31 |
val reveal_lam_lifted : (string * term) list -> term -> term
|
blanchet@40398
|
32 |
val prepare_metis_problem :
|
blanchet@46379
|
33 |
Proof.context -> type_enc -> string -> thm list -> thm list
|
blanchet@46379
|
34 |
-> int Symtab.table * (Metis_Thm.thm * isa_thm) list
|
blanchet@47910
|
35 |
* (unit -> (string * int) list)
|
blanchet@46379
|
36 |
* ((string * term) list * (string * term) list)
|
wenzelm@24310
|
37 |
end
|
paulson@15347
|
38 |
|
blanchet@47148
|
39 |
structure Metis_Generate : METIS_GENERATE =
|
paulson@15347
|
40 |
struct
|
paulson@15347
|
41 |
|
blanchet@43933
|
42 |
open ATP_Problem
|
blanchet@47148
|
43 |
open ATP_Problem_Generate
|
blanchet@43926
|
44 |
|
blanchet@43935
|
45 |
val metis_equal = "="
|
blanchet@43935
|
46 |
val metis_predicator = "{}"
|
blanchet@45347
|
47 |
val metis_app_op = Metis_Name.toString Metis_Term.appName
|
blanchet@45347
|
48 |
val metis_systematic_type_tag =
|
blanchet@45347
|
49 |
Metis_Name.toString Metis_Term.hasTypeFunctionName
|
blanchet@45347
|
50 |
val metis_ad_hoc_type_tag = "**"
|
blanchet@42962
|
51 |
val metis_generated_var_prefix = "_"
|
blanchet@42962
|
52 |
|
blanchet@44072
|
53 |
val trace = Attrib.setup_config_bool @{binding metis_trace} (K false)
|
blanchet@44072
|
54 |
val verbose = Attrib.setup_config_bool @{binding metis_verbose} (K true)
|
blanchet@44072
|
55 |
|
blanchet@44072
|
56 |
fun trace_msg ctxt msg = if Config.get ctxt trace then tracing (msg ()) else ()
|
blanchet@44072
|
57 |
fun verbose_warning ctxt msg =
|
blanchet@44072
|
58 |
if Config.get ctxt verbose then warning ("Metis: " ^ msg) else ()
|
blanchet@44072
|
59 |
|
blanchet@43935
|
60 |
val metis_name_table =
|
blanchet@45347
|
61 |
[((tptp_equal, 2), (K metis_equal, false)),
|
blanchet@45347
|
62 |
((tptp_old_equal, 2), (K metis_equal, false)),
|
blanchet@45347
|
63 |
((prefixed_predicator_name, 1), (K metis_predicator, false)),
|
blanchet@45347
|
64 |
((prefixed_app_op_name, 2), (K metis_app_op, false)),
|
blanchet@45347
|
65 |
((prefixed_type_tag_name, 2),
|
blanchet@45650
|
66 |
(fn type_enc =>
|
blanchet@45650
|
67 |
if level_of_type_enc type_enc = All_Types then metis_systematic_type_tag
|
blanchet@45650
|
68 |
else metis_ad_hoc_type_tag, true))]
|
blanchet@43935
|
69 |
|
blanchet@40077
|
70 |
fun old_skolem_const_name i j num_T_args =
|
blanchet@40077
|
71 |
old_skolem_const_prefix ^ Long_Name.separator ^
|
wenzelm@41739
|
72 |
(space_implode Long_Name.separator (map string_of_int [i, j, num_T_args]))
|
blanchet@37577
|
73 |
|
blanchet@40067
|
74 |
fun conceal_old_skolem_terms i old_skolems t =
|
blanchet@40134
|
75 |
if exists_Const (curry (op =) @{const_name Meson.skolem} o fst) t then
|
blanchet@37577
|
76 |
let
|
blanchet@40067
|
77 |
fun aux old_skolems
|
blanchet@40134
|
78 |
(t as (Const (@{const_name Meson.skolem}, Type (_, [_, T])) $ _)) =
|
blanchet@37577
|
79 |
let
|
blanchet@40067
|
80 |
val (old_skolems, s) =
|
blanchet@37577
|
81 |
if i = ~1 then
|
blanchet@40067
|
82 |
(old_skolems, @{const_name undefined})
|
blanchet@40067
|
83 |
else case AList.find (op aconv) old_skolems t of
|
blanchet@40067
|
84 |
s :: _ => (old_skolems, s)
|
blanchet@37577
|
85 |
| [] =>
|
blanchet@37577
|
86 |
let
|
blanchet@40077
|
87 |
val s = old_skolem_const_name i (length old_skolems)
|
blanchet@40077
|
88 |
(length (Term.add_tvarsT T []))
|
blanchet@40067
|
89 |
in ((s, t) :: old_skolems, s) end
|
blanchet@40067
|
90 |
in (old_skolems, Const (s, T)) end
|
blanchet@40067
|
91 |
| aux old_skolems (t1 $ t2) =
|
blanchet@37577
|
92 |
let
|
blanchet@40067
|
93 |
val (old_skolems, t1) = aux old_skolems t1
|
blanchet@40067
|
94 |
val (old_skolems, t2) = aux old_skolems t2
|
blanchet@40067
|
95 |
in (old_skolems, t1 $ t2) end
|
blanchet@40067
|
96 |
| aux old_skolems (Abs (s, T, t')) =
|
blanchet@40067
|
97 |
let val (old_skolems, t') = aux old_skolems t' in
|
blanchet@40067
|
98 |
(old_skolems, Abs (s, T, t'))
|
blanchet@37577
|
99 |
end
|
blanchet@40067
|
100 |
| aux old_skolems t = (old_skolems, t)
|
blanchet@40067
|
101 |
in aux old_skolems t end
|
blanchet@37577
|
102 |
else
|
blanchet@40067
|
103 |
(old_skolems, t)
|
blanchet@37577
|
104 |
|
blanchet@40067
|
105 |
fun reveal_old_skolem_terms old_skolems =
|
blanchet@37632
|
106 |
map_aterms (fn t as Const (s, _) =>
|
blanchet@40077
|
107 |
if String.isPrefix old_skolem_const_prefix s then
|
blanchet@40067
|
108 |
AList.lookup (op =) old_skolems s |> the
|
blanchet@44690
|
109 |
|> map_types (map_type_tvar (K dummyT))
|
blanchet@37632
|
110 |
else
|
blanchet@37632
|
111 |
t
|
blanchet@37632
|
112 |
| t => t)
|
blanchet@37632
|
113 |
|
blanchet@46440
|
114 |
fun reveal_lam_lifted lambdas =
|
blanchet@46382
|
115 |
map_aterms (fn t as Const (s, _) =>
|
blanchet@46425
|
116 |
if String.isPrefix lam_lifted_prefix s then
|
blanchet@46379
|
117 |
case AList.lookup (op =) lambdas s of
|
blanchet@46382
|
118 |
SOME t =>
|
blanchet@46382
|
119 |
Const (@{const_name Metis.lambda}, dummyT)
|
blanchet@46436
|
120 |
$ map_types (map_type_tvar (K dummyT))
|
blanchet@46440
|
121 |
(reveal_lam_lifted lambdas t)
|
blanchet@46379
|
122 |
| NONE => t
|
blanchet@46379
|
123 |
else
|
blanchet@46379
|
124 |
t
|
blanchet@46379
|
125 |
| t => t)
|
blanchet@46379
|
126 |
|
blanchet@37577
|
127 |
|
blanchet@39737
|
128 |
(* ------------------------------------------------------------------------- *)
|
blanchet@39737
|
129 |
(* Logic maps manage the interface between HOL and first-order logic. *)
|
blanchet@39737
|
130 |
(* ------------------------------------------------------------------------- *)
|
blanchet@39737
|
131 |
|
blanchet@44000
|
132 |
datatype isa_thm =
|
blanchet@44000
|
133 |
Isa_Reflexive_or_Trivial |
|
blanchet@46382
|
134 |
Isa_Lambda_Lifted |
|
blanchet@44000
|
135 |
Isa_Raw of thm
|
blanchet@44000
|
136 |
|
blanchet@44000
|
137 |
val proxy_defs = map (fst o snd o snd) proxy_table
|
blanchet@44000
|
138 |
val prepare_helper =
|
blanchet@44000
|
139 |
Meson.make_meta_clause #> rewrite_rule (map safe_mk_meta_eq proxy_defs)
|
blanchet@44000
|
140 |
|
blanchet@49147
|
141 |
fun metis_term_from_atp type_enc (ATerm ((s, []), tms)) =
|
blanchet@43935
|
142 |
if is_tptp_variable s then
|
blanchet@44109
|
143 |
Metis_Term.Var (Metis_Name.fromString s)
|
blanchet@43935
|
144 |
else
|
blanchet@45347
|
145 |
(case AList.lookup (op =) metis_name_table (s, length tms) of
|
blanchet@45347
|
146 |
SOME (f, swap) => (f type_enc, swap)
|
blanchet@45347
|
147 |
| NONE => (s, false))
|
blanchet@45347
|
148 |
|> (fn (s, swap) =>
|
blanchet@45347
|
149 |
Metis_Term.Fn (Metis_Name.fromString s,
|
blanchet@45347
|
150 |
tms |> map (metis_term_from_atp type_enc)
|
blanchet@45347
|
151 |
|> swap ? rev))
|
blanchet@45347
|
152 |
fun metis_atom_from_atp type_enc (AAtom tm) =
|
blanchet@45347
|
153 |
(case metis_term_from_atp type_enc tm of
|
blanchet@43945
|
154 |
Metis_Term.Fn x => x
|
blanchet@43945
|
155 |
| _ => raise Fail "non CNF -- expected function")
|
blanchet@45347
|
156 |
| metis_atom_from_atp _ _ = raise Fail "not CNF -- expected atom"
|
blanchet@45347
|
157 |
fun metis_literal_from_atp type_enc (AConn (ANot, [phi])) =
|
blanchet@45347
|
158 |
(false, metis_atom_from_atp type_enc phi)
|
blanchet@45347
|
159 |
| metis_literal_from_atp type_enc phi =
|
blanchet@45347
|
160 |
(true, metis_atom_from_atp type_enc phi)
|
blanchet@45347
|
161 |
fun metis_literals_from_atp type_enc (AConn (AOr, phis)) =
|
blanchet@45347
|
162 |
maps (metis_literals_from_atp type_enc) phis
|
blanchet@45347
|
163 |
| metis_literals_from_atp type_enc phi = [metis_literal_from_atp type_enc phi]
|
blanchet@45347
|
164 |
fun metis_axiom_from_atp type_enc clauses (Formula (ident, _, phi, _, _)) =
|
blanchet@44014
|
165 |
let
|
blanchet@44014
|
166 |
fun some isa =
|
blanchet@45347
|
167 |
SOME (phi |> metis_literals_from_atp type_enc
|
blanchet@45347
|
168 |
|> Metis_LiteralSet.fromList
|
blanchet@44014
|
169 |
|> Metis_Thm.axiom, isa)
|
blanchet@44014
|
170 |
in
|
blanchet@47917
|
171 |
if String.isPrefix tags_sym_formula_prefix ident then
|
blanchet@44014
|
172 |
Isa_Reflexive_or_Trivial |> some
|
blanchet@44153
|
173 |
else if String.isPrefix conjecture_prefix ident then
|
blanchet@44153
|
174 |
NONE
|
blanchet@44014
|
175 |
else if String.isPrefix helper_prefix ident then
|
blanchet@44035
|
176 |
case (String.isSuffix typed_helper_suffix ident,
|
blanchet@44035
|
177 |
space_explode "_" ident) of
|
blanchet@44035
|
178 |
(needs_fairly_sound, _ :: const :: j :: _) =>
|
blanchet@48961
|
179 |
nth (AList.lookup (op =) helper_table (const, needs_fairly_sound)
|
blanchet@48961
|
180 |
|> the)
|
blanchet@44014
|
181 |
(the (Int.fromString j) - 1)
|
blanchet@48961
|
182 |
|> snd |> prepare_helper
|
blanchet@44035
|
183 |
|> Isa_Raw |> some
|
blanchet@44014
|
184 |
| _ => raise Fail ("malformed helper identifier " ^ quote ident)
|
blanchet@44153
|
185 |
else case try (unprefix fact_prefix) ident of
|
blanchet@44014
|
186 |
SOME s =>
|
blanchet@46382
|
187 |
let val s = s |> space_explode "_" |> tl |> space_implode "_"
|
blanchet@46382
|
188 |
in
|
blanchet@46382
|
189 |
case Int.fromString s of
|
blanchet@46382
|
190 |
SOME j =>
|
blanchet@46382
|
191 |
Meson.make_meta_clause (snd (nth clauses j)) |> Isa_Raw |> some
|
blanchet@46382
|
192 |
| NONE =>
|
blanchet@46425
|
193 |
if String.isPrefix lam_fact_prefix (unascii_of s) then
|
blanchet@46382
|
194 |
Isa_Lambda_Lifted |> some
|
blanchet@46382
|
195 |
else
|
blanchet@46382
|
196 |
raise Fail ("malformed fact identifier " ^ quote ident)
|
blanchet@46382
|
197 |
end
|
blanchet@44014
|
198 |
| NONE => TrueI |> Isa_Raw |> some
|
blanchet@44014
|
199 |
end
|
blanchet@45347
|
200 |
| metis_axiom_from_atp _ _ _ = raise Fail "not CNF -- expected formula"
|
blanchet@43933
|
201 |
|
blanchet@46440
|
202 |
fun eliminate_lam_wrappers (Const (@{const_name Metis.lambda}, _) $ t) =
|
blanchet@46440
|
203 |
eliminate_lam_wrappers t
|
blanchet@46440
|
204 |
| eliminate_lam_wrappers (t $ u) =
|
blanchet@46440
|
205 |
eliminate_lam_wrappers t $ eliminate_lam_wrappers u
|
blanchet@46440
|
206 |
| eliminate_lam_wrappers (Abs (s, T, t)) =
|
blanchet@46440
|
207 |
Abs (s, T, eliminate_lam_wrappers t)
|
blanchet@46440
|
208 |
| eliminate_lam_wrappers t = t
|
blanchet@46440
|
209 |
|
blanchet@39737
|
210 |
(* Function to generate metis clauses, including comb and type clauses *)
|
blanchet@46385
|
211 |
fun prepare_metis_problem ctxt type_enc lam_trans conj_clauses fact_clauses =
|
blanchet@44053
|
212 |
let
|
blanchet@44153
|
213 |
val (conj_clauses, fact_clauses) =
|
blanchet@49146
|
214 |
if is_type_enc_polymorphic type_enc then
|
blanchet@44153
|
215 |
(conj_clauses, fact_clauses)
|
blanchet@44153
|
216 |
else
|
blanchet@44153
|
217 |
conj_clauses @ fact_clauses
|
blanchet@44153
|
218 |
|> map (pair 0)
|
blanchet@45908
|
219 |
|> rpair (ctxt |> Config.put Monomorph.keep_partial_instances false)
|
blanchet@44153
|
220 |
|-> Monomorph.monomorph atp_schematic_consts_of
|
blanchet@44153
|
221 |
|> fst |> chop (length conj_clauses)
|
blanchet@44153
|
222 |
|> pairself (maps (map (zero_var_indexes o snd)))
|
blanchet@44153
|
223 |
val num_conjs = length conj_clauses
|
blanchet@47910
|
224 |
(* Pretend every clause is a "simp" rule, to guide the term ordering. *)
|
blanchet@44053
|
225 |
val clauses =
|
blanchet@47910
|
226 |
map2 (fn j => pair (Int.toString j, (Local, Simp)))
|
blanchet@44153
|
227 |
(0 upto num_conjs - 1) conj_clauses @
|
blanchet@47910
|
228 |
map2 (fn j => pair (Int.toString (num_conjs + j), (Local, Simp)))
|
blanchet@44153
|
229 |
(0 upto length fact_clauses - 1) fact_clauses
|
blanchet@44053
|
230 |
val (old_skolems, props) =
|
blanchet@44153
|
231 |
fold_rev (fn (name, th) => fn (old_skolems, props) =>
|
blanchet@44153
|
232 |
th |> prop_of |> Logic.strip_imp_concl
|
blanchet@44153
|
233 |
|> conceal_old_skolem_terms (length clauses) old_skolems
|
blanchet@47193
|
234 |
||> (lam_trans = liftingN orelse lam_trans = lam_liftingN)
|
blanchet@47193
|
235 |
? eliminate_lam_wrappers
|
blanchet@44153
|
236 |
||> (fn prop => (name, prop) :: props))
|
blanchet@44153
|
237 |
clauses ([], [])
|
blanchet@44153
|
238 |
(*
|
blanchet@44153
|
239 |
val _ =
|
blanchet@45907
|
240 |
tracing ("PROPS:\n" ^
|
blanchet@45907
|
241 |
cat_lines (map (Syntax.string_of_term ctxt o snd) props))
|
blanchet@44153
|
242 |
*)
|
blanchet@47193
|
243 |
val lam_trans = if lam_trans = combsN then no_lamsN else lam_trans
|
blanchet@46422
|
244 |
val (atp_problem, _, _, lifted, sym_tab) =
|
blanchet@48961
|
245 |
prepare_atp_problem ctxt CNF Hypothesis type_enc Metis lam_trans false
|
blanchet@48927
|
246 |
false false [] @{prop False} props
|
blanchet@46381
|
247 |
(*
|
blanchet@44153
|
248 |
val _ = tracing ("ATP PROBLEM: " ^
|
blanchet@46379
|
249 |
cat_lines (lines_for_atp_problem CNF atp_problem))
|
blanchet@46381
|
250 |
*)
|
blanchet@46379
|
251 |
(* "rev" is for compatibility with existing proof scripts. *)
|
blanchet@44053
|
252 |
val axioms =
|
blanchet@45347
|
253 |
atp_problem
|
blanchet@45347
|
254 |
|> maps (map_filter (metis_axiom_from_atp type_enc clauses) o snd) |> rev
|
blanchet@47910
|
255 |
fun ord_info () = atp_problem_term_order_info atp_problem
|
blanchet@47910
|
256 |
in (sym_tab, axioms, ord_info, (lifted, old_skolems)) end
|
blanchet@39737
|
257 |
|
paulson@15347
|
258 |
end;
|