39 (case find_first (fn (_, (f, _)) => f type_enc = s) metis_name_table of |
39 (case find_first (fn (_, (f, _)) => f type_enc = s) metis_name_table of |
40 SOME ((s, _), (_, swap)) => (s, swap) |
40 SOME ((s, _), (_, swap)) => (s, swap) |
41 | _ => (s, false)) |
41 | _ => (s, false)) |
42 |
42 |
43 fun atp_term_of_metis type_enc (Metis_Term.Fn (s, tms)) = |
43 fun atp_term_of_metis type_enc (Metis_Term.Fn (s, tms)) = |
44 let val (s, swap) = atp_name_of_metis type_enc (Metis_Name.toString s) in |
44 let val (s, swap) = atp_name_of_metis type_enc (Metis_Name.toString s) |
45 ATerm ((s, []), tms |> map (atp_term_of_metis type_enc) |> swap ? rev) |
45 in ATerm ((s, []), tms |> map (atp_term_of_metis type_enc) |> swap ? rev) end |
46 end |
|
47 | atp_term_of_metis _ (Metis_Term.Var s) = |
46 | atp_term_of_metis _ (Metis_Term.Var s) = |
48 ATerm ((Metis_Name.toString s, []), []) |
47 ATerm ((Metis_Name.toString s, []), []) |
49 |
48 |
50 fun hol_term_of_metis ctxt type_enc sym_tab = |
49 fun hol_term_of_metis ctxt type_enc sym_tab = |
51 atp_term_of_metis type_enc #> term_of_atp ctxt ATP_Problem.CNF type_enc false sym_tab NONE |
50 atp_term_of_metis type_enc #> term_of_atp ctxt ATP_Problem.CNF type_enc false sym_tab NONE |
52 |
51 |
53 fun atp_literal_of_metis type_enc (pos, atom) = |
52 fun atp_literal_of_metis type_enc (pos, atom) = |
78 val _ = List.app (fn t => trace_msg ctxt |
77 val _ = List.app (fn t => trace_msg ctxt |
79 (fn () => " final term: " ^ Syntax.string_of_term ctxt t ^ |
78 (fn () => " final term: " ^ Syntax.string_of_term ctxt t ^ |
80 " of type " ^ Syntax.string_of_typ ctxt (type_of t))) ts' |
79 " of type " ^ Syntax.string_of_typ ctxt (type_of t))) ts' |
81 in ts' end |
80 in ts' end |
82 |
81 |
83 (* ------------------------------------------------------------------------- *) |
82 |
84 (* FOL step Inference Rules *) |
83 |
85 (* ------------------------------------------------------------------------- *) |
84 (** FOL step Inference Rules **) |
86 |
85 |
87 fun lookth th_pairs fth = |
86 fun lookth th_pairs fth = |
88 the (AList.lookup (uncurry Metis_Thm.equal) th_pairs fth) |
87 the (AList.lookup (uncurry Metis_Thm.equal) th_pairs fth) |
89 handle Option.Option => raise Fail ("Failed to find Metis theorem " ^ Metis_Thm.toString fth) |
88 handle Option.Option => raise Fail ("Failed to find Metis theorem " ^ Metis_Thm.toString fth) |
90 |
89 |
91 fun cterm_incr_types ctxt idx = |
90 fun cterm_incr_types ctxt idx = |
92 Thm.cterm_of ctxt o map_types (Logic.incr_tvar idx) |
91 Thm.cterm_of ctxt o map_types (Logic.incr_tvar idx) |
93 |
92 |
|
93 |
94 (* INFERENCE RULE: AXIOM *) |
94 (* INFERENCE RULE: AXIOM *) |
95 |
95 |
96 (* This causes variables to have an index of 1 by default. See also |
96 (*This causes variables to have an index of 1 by default. See also |
97 "term_of_atp" in "ATP_Proof_Reconstruct". *) |
97 "term_of_atp" in "ATP_Proof_Reconstruct".*) |
98 val axiom_inference = Thm.incr_indexes 1 oo lookth |
98 val axiom_inference = Thm.incr_indexes 1 oo lookth |
99 |
99 |
|
100 |
100 (* INFERENCE RULE: ASSUME *) |
101 (* INFERENCE RULE: ASSUME *) |
101 |
102 |
102 val EXCLUDED_MIDDLE = @{lemma "P \<Longrightarrow> \<not> P \<Longrightarrow> False" by (rule notE)} |
103 val EXCLUDED_MIDDLE = @{lemma "P \<Longrightarrow> \<not> P \<Longrightarrow> False" by (rule notE)} |
103 |
104 |
104 fun inst_excluded_middle ctxt i_atom = |
105 fun inst_excluded_middle ctxt i_atom = |
105 let |
106 let val [vx] = Term.add_vars (Thm.prop_of EXCLUDED_MIDDLE) [] |
106 val th = EXCLUDED_MIDDLE |
107 in infer_instantiate_types ctxt [(vx, Thm.cterm_of ctxt i_atom)] EXCLUDED_MIDDLE end |
107 val [vx] = Term.add_vars (Thm.prop_of th) [] |
|
108 in |
|
109 infer_instantiate_types ctxt [(vx, Thm.cterm_of ctxt i_atom)] th |
|
110 end |
|
111 |
108 |
112 fun assume_inference ctxt type_enc concealed sym_tab atom = |
109 fun assume_inference ctxt type_enc concealed sym_tab atom = |
113 inst_excluded_middle ctxt |
110 inst_excluded_middle ctxt |
114 (singleton (hol_terms_of_metis ctxt type_enc concealed sym_tab) (Metis_Term.Fn atom)) |
111 (singleton (hol_terms_of_metis ctxt type_enc concealed sym_tab) (Metis_Term.Fn atom)) |
115 |
112 |
125 |
122 |
126 fun find_var x = the (List.find (fn ((a,_),_) => a=x) i_th_vars) |
123 fun find_var x = the (List.find (fn ((a,_),_) => a=x) i_th_vars) |
127 fun subst_translation (x,y) = |
124 fun subst_translation (x,y) = |
128 let |
125 let |
129 val v = find_var x |
126 val v = find_var x |
130 (* We call "polish_hol_terms" below. *) |
127 (*We call "polish_hol_terms" below.*) |
131 val t = hol_term_of_metis ctxt type_enc sym_tab y |
128 val t = hol_term_of_metis ctxt type_enc sym_tab y |
132 in |
129 in |
133 SOME (Thm.cterm_of ctxt (Var v), t) |
130 SOME (Thm.cterm_of ctxt (Var v), t) |
134 end |
131 end |
135 handle Option.Option => |
132 handle Option.Option => |
144 let val a = Metis_Name.toString a in |
141 let val a = Metis_Name.toString a in |
145 (case unprefix_and_unascii schematic_var_prefix a of |
142 (case unprefix_and_unascii schematic_var_prefix a of |
146 SOME b => SOME (b, t) |
143 SOME b => SOME (b, t) |
147 | NONE => |
144 | NONE => |
148 (case unprefix_and_unascii tvar_prefix a of |
145 (case unprefix_and_unascii tvar_prefix a of |
149 SOME _ => NONE (* type instantiations are forbidden *) |
146 SOME _ => NONE (*type instantiations are forbidden*) |
150 | NONE => SOME (a, t) (* internal Metis var? *))) |
147 | NONE => SOME (a, t) (*internal Metis var?*))) |
151 end |
148 end |
152 val _ = trace_msg ctxt (fn () => " isa th: " ^ Thm.string_of_thm ctxt i_th) |
149 val _ = trace_msg ctxt (fn () => " isa th: " ^ Thm.string_of_thm ctxt i_th) |
153 val substs = map_filter remove_typeinst (Metis_Subst.toList fsubst) |
150 val substs = map_filter remove_typeinst (Metis_Subst.toList fsubst) |
154 val (vars, tms) = |
151 val (vars, tms) = |
155 ListPair.unzip (map_filter subst_translation substs) |
152 ListPair.unzip (map_filter subst_translation substs) |
165 infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) substs') i_th |
162 infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) substs') i_th |
166 end |
163 end |
167 handle THM (msg, _, _) => raise METIS_RECONSTRUCT ("inst_inference", msg) |
164 handle THM (msg, _, _) => raise METIS_RECONSTRUCT ("inst_inference", msg) |
168 | ERROR msg => raise METIS_RECONSTRUCT ("inst_inference", msg) |
165 | ERROR msg => raise METIS_RECONSTRUCT ("inst_inference", msg) |
169 |
166 |
|
167 |
170 (* INFERENCE RULE: RESOLVE *) |
168 (* INFERENCE RULE: RESOLVE *) |
171 |
169 |
172 (*Increment the indexes of only the type variables*) |
170 (*Increment the indexes of only the type variables*) |
173 fun incr_type_indexes ctxt inc th = |
171 fun incr_type_indexes ctxt inc th = |
174 let |
172 let |
176 fun inc_tvar ((a, i), s) = (((a, i), s), Thm.ctyp_of ctxt (TVar ((a, i + inc), s))) |
174 fun inc_tvar ((a, i), s) = (((a, i), s), Thm.ctyp_of ctxt (TVar ((a, i + inc), s))) |
177 in |
175 in |
178 Thm.instantiate (map inc_tvar tvs, []) th |
176 Thm.instantiate (map inc_tvar tvs, []) th |
179 end |
177 end |
180 |
178 |
181 (* Like RSN, but we rename apart only the type variables. Vars here typically |
179 (*Like RSN, but we rename apart only the type variables. Vars here typically |
182 have an index of 1, and the use of RSN would increase this typically to 3. |
180 have an index of 1, and the use of RSN would increase this typically to 3. |
183 Instantiations of those Vars could then fail. *) |
181 Instantiations of those Vars could then fail.*) |
184 fun resolve_inc_tyvars ctxt tha i thb = |
182 fun resolve_inc_tyvars ctxt tha i thb = |
185 let |
183 let |
186 val tha = incr_type_indexes ctxt (1 + Thm.maxidx_of thb) tha |
184 val tha = incr_type_indexes ctxt (1 + Thm.maxidx_of thb) tha |
187 fun res (tha, thb) = |
185 fun res (tha, thb) = |
188 (case Thm.bicompose (SOME ctxt) {flatten = true, match = false, incremented = true} |
186 (case Thm.bicompose (SOME ctxt) {flatten = true, match = false, incremented = true} |
210 |> rpair Envir.init |
208 |> rpair Envir.init |
211 |-> fold (Pattern.unify (Context.Proof ctxt)) |
209 |-> fold (Pattern.unify (Context.Proof ctxt)) |
212 |> Envir.type_env |> Vartab.dest |
210 |> Envir.type_env |> Vartab.dest |
213 |> map (fn (x, (S, T)) => ((x, S), Thm.ctyp_of ctxt T)) |
211 |> map (fn (x, (S, T)) => ((x, S), Thm.ctyp_of ctxt T)) |
214 in |
212 in |
215 (* The unifier, which is invoked from "Thm.bicompose", will sometimes refuse to unify |
213 (*The unifier, which is invoked from "Thm.bicompose", will sometimes refuse to unify |
216 "?a::?'a" with "?a::?'b" or "?a::nat" and throw a "TERM" exception (with "add_ffpair" as |
214 "?a::?'a" with "?a::?'b" or "?a::nat" and throw a "TERM" exception (with "add_ffpair" as |
217 first argument). We then perform unification of the types of variables by hand and try |
215 first argument). We then perform unification of the types of variables by hand and try |
218 again. We could do this the first time around but this error occurs seldom and we don't |
216 again. We could do this the first time around but this error occurs seldom and we don't |
219 want to break existing proofs in subtle ways or slow them down. *) |
217 want to break existing proofs in subtle ways or slow them down.*) |
220 if null ps then raise TERM z |
218 if null ps then raise TERM z |
221 else res (apply2 (Drule.instantiate_normalize (ps, [])) (tha, thb)) |
219 else res (apply2 (Drule.instantiate_normalize (ps, [])) (tha, thb)) |
222 end |
220 end |
223 end |
221 end |
224 |
222 |
228 | simp_not_not (\<^const>\<open>Not\<close> $ t) = s_not (simp_not_not t) |
226 | simp_not_not (\<^const>\<open>Not\<close> $ t) = s_not (simp_not_not t) |
229 | simp_not_not t = t |
227 | simp_not_not t = t |
230 |
228 |
231 val normalize_literal = simp_not_not o Envir.eta_contract |
229 val normalize_literal = simp_not_not o Envir.eta_contract |
232 |
230 |
233 (* Find the relative location of an untyped term within a list of terms as a |
231 (*Find the relative location of an untyped term within a list of terms as a |
234 1-based index. Returns 0 in case of failure. *) |
232 1-based index. Returns 0 in case of failure.*) |
235 fun index_of_literal lit haystack = |
233 fun index_of_literal lit haystack = |
236 let |
234 let |
237 fun match_lit normalize = |
235 fun match_lit normalize = |
238 HOLogic.dest_Trueprop #> normalize |
236 HOLogic.dest_Trueprop #> normalize |
239 #> curry Term.aconv_untyped (lit |> normalize) |
237 #> curry Term.aconv_untyped (lit |> normalize) |
241 (case find_index (match_lit I) haystack of |
239 (case find_index (match_lit I) haystack of |
242 ~1 => find_index (match_lit (simp_not_not o Envir.eta_contract)) haystack |
240 ~1 => find_index (match_lit (simp_not_not o Envir.eta_contract)) haystack |
243 | j => j) + 1 |
241 | j => j) + 1 |
244 end |
242 end |
245 |
243 |
246 (* Permute a rule's premises to move the i-th premise to the last position. *) |
244 (*Permute a rule's premises to move the i-th premise to the last position.*) |
247 fun make_last i th = |
245 fun make_last i th = |
248 let val n = Thm.nprems_of th in |
246 let val n = Thm.nprems_of th in |
249 if i >= 1 andalso i <= n then Thm.permute_prems (i - 1) 1 th |
247 if i >= 1 andalso i <= n then Thm.permute_prems (i - 1) 1 th |
250 else raise THM ("select_literal", i, [th]) |
248 else raise THM ("select_literal", i, [th]) |
251 end |
249 end |
252 |
250 |
253 (* Maps a rule that ends "... ==> P ==> False" to "... ==> ~ P" while avoiding |
251 (*Maps a rule that ends "... ==> P ==> False" to "... ==> ~ P" while avoiding |
254 to create double negations. The "select" wrapper is a trick to ensure that |
252 to create double negations. The "select" wrapper is a trick to ensure that |
255 "P ==> ~ False ==> False" is rewritten to "P ==> False", not to "~ P". We |
253 "P ==> ~ False ==> False" is rewritten to "P ==> False", not to "~ P". We |
256 don't use this trick in general because it makes the proof object uglier than |
254 don't use this trick in general because it makes the proof object uglier than |
257 necessary. FIXME. *) |
255 necessary. FIXME.*) |
258 fun negate_head ctxt th = |
256 fun negate_head ctxt th = |
259 if exists (fn t => t aconv \<^prop>\<open>\<not> False\<close>) (Thm.prems_of th) then |
257 if exists (fn t => t aconv \<^prop>\<open>\<not> False\<close>) (Thm.prems_of th) then |
260 (th RS @{thm select_FalseI}) |
258 (th RS @{thm select_FalseI}) |
261 |> fold (rewrite_rule ctxt o single) @{thms not_atomize_select atomize_not_select} |
259 |> fold (rewrite_rule ctxt o single) @{thms not_atomize_select atomize_not_select} |
262 else |
260 else |
294 resolve_inc_tyvars ctxt (select_literal ctxt j1 i_th1) j2 i_th2 |
292 resolve_inc_tyvars ctxt (select_literal ctxt j1 i_th1) j2 i_th2 |
295 handle TERM (s, _) => raise METIS_RECONSTRUCT ("resolve_inference", s))))) |
293 handle TERM (s, _) => raise METIS_RECONSTRUCT ("resolve_inference", s))))) |
296 end |
294 end |
297 end |
295 end |
298 |
296 |
|
297 |
299 (* INFERENCE RULE: REFL *) |
298 (* INFERENCE RULE: REFL *) |
300 |
299 |
301 val REFL_THM = Thm.incr_indexes 2 @{lemma "t \<noteq> t \<Longrightarrow> False" by (drule notE) (rule refl)} |
300 val REFL_THM = Thm.incr_indexes 2 @{lemma "t \<noteq> t \<Longrightarrow> False" by (drule notE) (rule refl)} |
302 |
301 |
303 val [refl_x] = Term.add_vars (Thm.prop_of REFL_THM) []; |
302 val [refl_x] = Term.add_vars (Thm.prop_of REFL_THM) []; |
308 val i_t = singleton (hol_terms_of_metis ctxt type_enc concealed sym_tab) t |
307 val i_t = singleton (hol_terms_of_metis ctxt type_enc concealed sym_tab) t |
309 val _ = trace_msg ctxt (fn () => " term: " ^ Syntax.string_of_term ctxt i_t) |
308 val _ = trace_msg ctxt (fn () => " term: " ^ Syntax.string_of_term ctxt i_t) |
310 val c_t = cterm_incr_types ctxt refl_idx i_t |
309 val c_t = cterm_incr_types ctxt refl_idx i_t |
311 in infer_instantiate_types ctxt [(refl_x, c_t)] REFL_THM end |
310 in infer_instantiate_types ctxt [(refl_x, c_t)] REFL_THM end |
312 |
311 |
|
312 |
313 (* INFERENCE RULE: EQUALITY *) |
313 (* INFERENCE RULE: EQUALITY *) |
314 |
314 |
315 val subst_em = @{lemma "s = t \<Longrightarrow> P s \<Longrightarrow> \<not> P t \<Longrightarrow> False" by (erule notE) (erule subst)} |
315 val subst_em = @{lemma "s = t \<Longrightarrow> P s \<Longrightarrow> \<not> P t \<Longrightarrow> False" by (erule notE) (erule subst)} |
316 val ssubst_em = @{lemma "s = t \<Longrightarrow> P t \<Longrightarrow> \<not> P s \<Longrightarrow> False" by (erule notE) (erule ssubst)} |
316 val ssubst_em = @{lemma "s = t \<Longrightarrow> P t \<Longrightarrow> \<not> P s \<Longrightarrow> False" by (erule notE) (erule ssubst)} |
317 |
317 |
318 fun equality_inference ctxt type_enc concealed sym_tab (pos, atom) fp fr = |
318 fun equality_inference ctxt type_enc concealed sym_tab (pos, atom) fp fr = |
319 let val thy = Proof_Context.theory_of ctxt |
319 let |
320 val m_tm = Metis_Term.Fn atom |
320 val m_tm = Metis_Term.Fn atom |
321 val [i_atom, i_tm] = hol_terms_of_metis ctxt type_enc concealed sym_tab [m_tm, fr] |
321 val [i_atom, i_tm] = hol_terms_of_metis ctxt type_enc concealed sym_tab [m_tm, fr] |
322 val _ = trace_msg ctxt (fn () => "sign of the literal: " ^ Bool.toString pos) |
322 val _ = trace_msg ctxt (fn () => "sign of the literal: " ^ Bool.toString pos) |
323 fun replace_item_list lx 0 (_::ls) = lx::ls |
323 fun replace_item_list lx 0 (_::ls) = lx::ls |
324 | replace_item_list lx i (l::ls) = l :: replace_item_list lx (i-1) ls |
324 | replace_item_list lx i (l::ls) = l :: replace_item_list lx (i-1) ls |
325 fun path_finder_fail tm ps t = |
325 fun path_finder_fail tm ps t = |
326 raise METIS_RECONSTRUCT ("equality_inference (path_finder)", |
326 raise METIS_RECONSTRUCT ("equality_inference (path_finder)", |
327 "path = " ^ space_implode " " (map string_of_int ps) ^ |
327 "path = " ^ space_implode " " (map string_of_int ps) ^ |
328 " isa-term: " ^ Syntax.string_of_term ctxt tm ^ |
328 " isa-term: " ^ Syntax.string_of_term ctxt tm ^ |
329 (case t of |
329 (case t of |
330 SOME t => " fol-term: " ^ Metis_Term.toString t |
330 SOME t => " fol-term: " ^ Metis_Term.toString t |
331 | NONE => "")) |
331 | NONE => "")) |
332 fun path_finder tm [] _ = (tm, Bound 0) |
332 fun path_finder tm [] _ = (tm, Bound 0) |
333 | path_finder tm (p :: ps) (t as Metis_Term.Fn (s, ts)) = |
333 | path_finder tm (p :: ps) (t as Metis_Term.Fn (s, ts)) = |
334 let |
334 let |
335 val s = s |> Metis_Name.toString |
335 val s = s |> Metis_Name.toString |
336 |> perhaps (try (unprefix_and_unascii const_prefix |
336 |> perhaps (try (unprefix_and_unascii const_prefix |
337 #> the #> unmangled_const_name #> hd)) |
337 #> the #> unmangled_const_name #> hd)) |
338 in |
338 in |
359 "path_finder: " ^ string_of_int p ^ " " ^ |
359 "path_finder: " ^ string_of_int p ^ " " ^ |
360 Syntax.string_of_term ctxt tm_p) |
360 Syntax.string_of_term ctxt tm_p) |
361 val (r, t) = path_finder tm_p ps (nth ts p) |
361 val (r, t) = path_finder tm_p ps (nth ts p) |
362 in (r, list_comb (tm1, replace_item_list t p' args)) end |
362 in (r, list_comb (tm1, replace_item_list t p' args)) end |
363 end |
363 end |
364 | path_finder tm ps t = path_finder_fail tm ps (SOME t) |
364 | path_finder tm ps t = path_finder_fail tm ps (SOME t) |
365 val (tm_subst, body) = path_finder i_atom fp m_tm |
365 val (tm_subst, body) = path_finder i_atom fp m_tm |
366 val tm_abs = Abs ("x", type_of tm_subst, body) |
366 val tm_abs = Abs ("x", type_of tm_subst, body) |
367 val _ = trace_msg ctxt (fn () => "abstraction: " ^ Syntax.string_of_term ctxt tm_abs) |
367 val _ = trace_msg ctxt (fn () => "abstraction: " ^ Syntax.string_of_term ctxt tm_abs) |
368 val _ = trace_msg ctxt (fn () => "i_tm: " ^ Syntax.string_of_term ctxt i_tm) |
368 val _ = trace_msg ctxt (fn () => "i_tm: " ^ Syntax.string_of_term ctxt i_tm) |
369 val _ = trace_msg ctxt (fn () => "located term: " ^ Syntax.string_of_term ctxt tm_subst) |
369 val _ = trace_msg ctxt (fn () => "located term: " ^ Syntax.string_of_term ctxt tm_subst) |
370 val imax = maxidx_of_term (i_tm $ tm_abs $ tm_subst) (*ill-typed but gives right max*) |
370 val imax = maxidx_of_term (i_tm $ tm_abs $ tm_subst) (*ill-typed but gives right max*) |
371 val subst' = Thm.incr_indexes (imax+1) (if pos then subst_em else ssubst_em) |
371 val subst' = Thm.incr_indexes (imax+1) (if pos then subst_em else ssubst_em) |
372 val _ = trace_msg ctxt (fn () => "subst' " ^ Thm.string_of_thm ctxt subst') |
372 val _ = trace_msg ctxt (fn () => "subst' " ^ Thm.string_of_thm ctxt subst') |
373 val eq_terms = |
373 val eq_terms = |
374 map (apply2 (Thm.cterm_of ctxt)) |
374 map (apply2 (Thm.cterm_of ctxt)) |
375 (ListPair.zip (Misc_Legacy.term_vars (Thm.prop_of subst'), [tm_abs, tm_subst, i_tm])) |
375 (ListPair.zip (Misc_Legacy.term_vars (Thm.prop_of subst'), [tm_abs, tm_subst, i_tm])) |
376 in |
376 in |
377 infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) eq_terms) subst' |
377 infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) eq_terms) subst' |
378 end |
378 end |
379 |
379 |
380 val factor = Seq.hd o distinct_subgoals_tac |
380 val factor = Seq.hd o distinct_subgoals_tac |
382 fun one_step ctxt type_enc concealed sym_tab th_pairs p = |
382 fun one_step ctxt type_enc concealed sym_tab th_pairs p = |
383 (case p of |
383 (case p of |
384 (fol_th, Metis_Proof.Axiom _) => axiom_inference th_pairs fol_th |> factor |
384 (fol_th, Metis_Proof.Axiom _) => axiom_inference th_pairs fol_th |> factor |
385 | (_, Metis_Proof.Assume f_atom) => assume_inference ctxt type_enc concealed sym_tab f_atom |
385 | (_, Metis_Proof.Assume f_atom) => assume_inference ctxt type_enc concealed sym_tab f_atom |
386 | (_, Metis_Proof.Metis_Subst (f_subst, f_th1)) => |
386 | (_, Metis_Proof.Metis_Subst (f_subst, f_th1)) => |
387 inst_inference ctxt type_enc concealed sym_tab th_pairs f_subst f_th1 |> factor |
387 inst_inference ctxt type_enc concealed sym_tab th_pairs f_subst f_th1 |> factor |
388 | (_, Metis_Proof.Resolve(f_atom, f_th1, f_th2)) => |
388 | (_, Metis_Proof.Resolve(f_atom, f_th1, f_th2)) => |
389 resolve_inference ctxt type_enc concealed sym_tab th_pairs f_atom f_th1 f_th2 |> factor |
389 resolve_inference ctxt type_enc concealed sym_tab th_pairs f_atom f_th1 f_th2 |> factor |
390 | (_, Metis_Proof.Refl f_tm) => refl_inference ctxt type_enc concealed sym_tab f_tm |
390 | (_, Metis_Proof.Refl f_tm) => refl_inference ctxt type_enc concealed sym_tab f_tm |
391 | (_, Metis_Proof.Equality (f_lit, f_p, f_r)) => |
391 | (_, Metis_Proof.Equality (f_lit, f_p, f_r)) => |
392 equality_inference ctxt type_enc concealed sym_tab f_lit f_p f_r) |
392 equality_inference ctxt type_enc concealed sym_tab f_lit f_p f_r) |
393 |
393 |
394 fun flexflex_first_order ctxt th = |
394 fun flexflex_first_order ctxt th = |
395 (case Thm.tpairs_of th of |
395 (case Thm.tpairs_of th of |
396 [] => th |
396 [] => th |
397 | pairs => |
397 | pairs => |
398 let |
398 let |
399 val thy = Proof_Context.theory_of ctxt |
399 val thy = Proof_Context.theory_of ctxt |
400 val (tyenv, tenv) = fold (Pattern.first_order_match thy) pairs (Vartab.empty, Vartab.empty) |
400 val (tyenv, tenv) = fold (Pattern.first_order_match thy) pairs (Vartab.empty, Vartab.empty) |
401 |
401 |
402 fun mkT (v, (S, T)) = ((v, S), Thm.ctyp_of ctxt T) |
402 fun mkT (v, (S, T)) = ((v, S), Thm.ctyp_of ctxt T) |
403 fun mk (v, (T, t)) = ((v, Envir.subst_type tyenv T), Thm.cterm_of ctxt t) |
403 fun mk (v, (T, t)) = ((v, Envir.subst_type tyenv T), Thm.cterm_of ctxt t) |
404 |
404 |
405 val instsT = Vartab.fold (cons o mkT) tyenv [] |
405 val instsT = Vartab.fold (cons o mkT) tyenv [] |
406 val insts = Vartab.fold (cons o mk) tenv [] |
406 val insts = Vartab.fold (cons o mk) tenv [] |
407 in |
407 in |
408 Thm.instantiate (instsT, insts) th |
408 Thm.instantiate (instsT, insts) th |
409 end |
409 end |
414 fun is_isabelle_literal_genuine t = |
414 fun is_isabelle_literal_genuine t = |
415 (case t of _ $ (Const (\<^const_name>\<open>Meson.skolem\<close>, _) $ _) => false | _ => true) |
415 (case t of _ $ (Const (\<^const_name>\<open>Meson.skolem\<close>, _) $ _) => false | _ => true) |
416 |
416 |
417 fun count p xs = fold (fn x => if p x then Integer.add 1 else I) xs 0 |
417 fun count p xs = fold (fn x => if p x then Integer.add 1 else I) xs 0 |
418 |
418 |
419 (* Seldomly needed hack. A Metis clause is represented as a set, so duplicate |
419 (*Seldomly needed hack. A Metis clause is represented as a set, so duplicate |
420 disjuncts are impossible. In the Isabelle proof, in spite of efforts to |
420 disjuncts are impossible. In the Isabelle proof, in spite of efforts to |
421 eliminate them, duplicates sometimes appear with slightly different (but |
421 eliminate them, duplicates sometimes appear with slightly different (but |
422 unifiable) types. *) |
422 unifiable) types.*) |
423 fun resynchronize ctxt fol_th th = |
423 fun resynchronize ctxt fol_th th = |
424 let |
424 let |
425 val num_metis_lits = |
425 val num_metis_lits = |
426 count is_metis_literal_genuine (Metis_LiteralSet.toList (Metis_Thm.clause fol_th)) |
426 count is_metis_literal_genuine (Metis_LiteralSet.toList (Metis_Thm.clause fol_th)) |
427 val num_isabelle_lits = count is_isabelle_literal_genuine (Thm.prems_of th) |
427 val num_isabelle_lits = count is_isabelle_literal_genuine (Thm.prems_of th) |
445 Goal.prove ctxt' [] [] goal (K tac) |
445 Goal.prove ctxt' [] [] goal (K tac) |
446 |> resynchronize ctxt' fol_th |
446 |> resynchronize ctxt' fol_th |
447 end |
447 end |
448 end |
448 end |
449 |
449 |
450 fun replay_one_inference ctxt type_enc concealed sym_tab (fol_th, inf) |
450 fun replay_one_inference ctxt type_enc concealed sym_tab (fol_th, inf) th_pairs = |
451 th_pairs = |
|
452 if not (null th_pairs) andalso Thm.prop_of (snd (hd th_pairs)) aconv \<^prop>\<open>False\<close> then |
451 if not (null th_pairs) andalso Thm.prop_of (snd (hd th_pairs)) aconv \<^prop>\<open>False\<close> then |
453 (* Isabelle sometimes identifies literals (premises) that are distinct in |
452 (*Isabelle sometimes identifies literals (premises) that are distinct in |
454 Metis (e.g., because of type variables). We give the Isabelle proof the |
453 Metis (e.g., because of type variables). We give the Isabelle proof the |
455 benefice of the doubt. *) |
454 benefice of the doubt.*) |
456 th_pairs |
455 th_pairs |
457 else |
456 else |
458 let |
457 let |
459 val _ = trace_msg ctxt (fn () => "=============================================") |
458 val _ = trace_msg ctxt (fn () => "=============================================") |
460 val _ = trace_msg ctxt (fn () => "METIS THM: " ^ Metis_Thm.toString fol_th) |
459 val _ = trace_msg ctxt (fn () => "METIS THM: " ^ Metis_Thm.toString fol_th) |
466 val _ = trace_msg ctxt (fn () => "=============================================") |
465 val _ = trace_msg ctxt (fn () => "=============================================") |
467 in |
466 in |
468 (fol_th, th) :: th_pairs |
467 (fol_th, th) :: th_pairs |
469 end |
468 end |
470 |
469 |
471 (* It is normally sufficient to apply "assume_tac" to unify the conclusion with |
470 (*It is normally sufficient to apply "assume_tac" to unify the conclusion with |
472 one of the premises. Unfortunately, this sometimes yields "Variable |
471 one of the premises. Unfortunately, this sometimes yields "Variable |
473 has two distinct types" errors. To avoid this, we instantiate the |
472 has two distinct types" errors. To avoid this, we instantiate the |
474 variables before applying "assume_tac". Typical constraints are of the form |
473 variables before applying "assume_tac". Typical constraints are of the form |
475 ?SK_a_b_c_x SK_d_e_f_y ... SK_a_b_c_x ... SK_g_h_i_z \<equiv>\<^sup>? SK_a_b_c_x, |
474 ?SK_a_b_c_x SK_d_e_f_y ... SK_a_b_c_x ... SK_g_h_i_z \<equiv>\<^sup>? SK_a_b_c_x, |
476 where the nonvariables are goal parameters. *) |
475 where the nonvariables are goal parameters.*) |
477 fun unify_first_prem_with_concl ctxt i th = |
476 fun unify_first_prem_with_concl ctxt i th = |
478 let |
477 let |
479 val goal = Logic.get_goal (Thm.prop_of th) i |> Envir.beta_eta_contract |
478 val goal = Logic.get_goal (Thm.prop_of th) i |> Envir.beta_eta_contract |
480 val prem = goal |> Logic.strip_assums_hyp |> hd |
479 val prem = goal |> Logic.strip_assums_hyp |> hd |
481 val concl = goal |> Logic.strip_assums_concl |
480 val concl = goal |> Logic.strip_assums_concl |
521 |> the_default [] (* FIXME *) |
520 |> the_default [] (* FIXME *) |
522 in |
521 in |
523 infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) t_inst) th |
522 infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) t_inst) th |
524 end |
523 end |
525 |
524 |
526 val copy_prem = @{lemma "P ==> (P ==> P ==> Q) ==> Q" by assumption} |
525 val copy_prem = @{lemma "P \<Longrightarrow> (P \<Longrightarrow> P \<Longrightarrow> Q) \<Longrightarrow> Q" by assumption} |
527 |
526 |
528 fun copy_prems_tac ctxt [] ns i = |
527 fun copy_prems_tac ctxt [] ns i = |
529 if forall (curry (op =) 1) ns then all_tac else copy_prems_tac ctxt (rev ns) [] i |
528 if forall (curry (op =) 1) ns then all_tac else copy_prems_tac ctxt (rev ns) [] i |
530 | copy_prems_tac ctxt (1 :: ms) ns i = rotate_tac 1 i THEN copy_prems_tac ctxt ms (1 :: ns) i |
529 | copy_prems_tac ctxt (1 :: ms) ns i = rotate_tac 1 i THEN copy_prems_tac ctxt ms (1 :: ns) i |
531 | copy_prems_tac ctxt (m :: ms) ns i = |
530 | copy_prems_tac ctxt (m :: ms) ns i = |
532 eresolve_tac ctxt [copy_prem] i THEN copy_prems_tac ctxt ms (m div 2 :: (m + 1) div 2 :: ns) i |
531 eresolve_tac ctxt [copy_prem] i THEN copy_prems_tac ctxt ms (m div 2 :: (m + 1) div 2 :: ns) i |
533 |
532 |
534 (* Metis generates variables of the form _nnn. *) |
533 (*Metis generates variables of the form _nnn.*) |
535 val is_metis_fresh_variable = String.isPrefix "_" |
534 val is_metis_fresh_variable = String.isPrefix "_" |
536 |
535 |
537 fun instantiate_forall_tac ctxt t i st = |
536 fun instantiate_forall_tac ctxt t i st = |
538 let |
537 let |
539 val params = Logic.strip_params (Logic.get_goal (Thm.prop_of st) i) |> rev |
538 val params = Logic.strip_params (Logic.get_goal (Thm.prop_of st) i) |> rev |
540 |
539 |
541 fun repair (t as (Var ((s, _), _))) = |
540 fun repair (t as (Var ((s, _), _))) = |
542 (case find_index (fn (s', _) => s' = s) params of |
541 (case find_index (fn (s', _) => s' = s) params of |
543 ~1 => t |
542 ~1 => t |
544 | j => Bound j) |
543 | j => Bound j) |
545 | repair (t $ u) = |
544 | repair (t $ u) = |
546 (case (repair t, repair u) of |
545 (case (repair t, repair u) of |
547 (t as Bound j, u as Bound k) => |
546 (t as Bound j, u as Bound k) => |
548 (* This is a trick to repair the discrepancy between the fully skolemized term that MESON |
547 (*This is a trick to repair the discrepancy between the fully skolemized term that MESON |
549 gives us (where existentials were pulled out) and the reality. *) |
548 gives us (where existentials were pulled out) and the reality.*) |
550 if k > j then t else t $ u |
549 if k > j then t else t $ u |
551 | (t, u) => t $ u) |
550 | (t, u) => t $ u) |
552 | repair t = t |
551 | repair t = t |
553 |
552 |
554 val t' = t |> repair |> fold (absdummy o snd) params |
553 val t' = t |> repair |> fold (absdummy o snd) params |
555 |
554 |
556 fun do_instantiate th = |
555 fun do_instantiate th = |
616 prod_ord int_ord (prod_ord int_ord (prod_ord bool_ord int_ord)) (apply2 cluster_key p) |
615 prod_ord int_ord (prod_ord int_ord (prod_ord bool_ord int_ord)) (apply2 cluster_key p) |
617 |
616 |
618 val tysubst_ord = |
617 val tysubst_ord = |
619 list_ord (prod_ord Term_Ord.fast_indexname_ord (prod_ord Term_Ord.sort_ord Term_Ord.typ_ord)) |
618 list_ord (prod_ord Term_Ord.fast_indexname_ord (prod_ord Term_Ord.sort_ord Term_Ord.typ_ord)) |
620 |
619 |
621 structure Int_Tysubst_Table = |
620 structure Int_Tysubst_Table = Table |
622 Table(type key = int * (indexname * (sort * typ)) list |
621 ( |
623 val ord = prod_ord int_ord tysubst_ord) |
622 type key = int * (indexname * (sort * typ)) list |
624 |
623 val ord = prod_ord int_ord tysubst_ord |
625 structure Int_Pair_Graph = |
624 ) |
626 Graph(type key = int * int val ord = prod_ord int_ord int_ord) |
625 |
|
626 structure Int_Pair_Graph = Graph( |
|
627 type key = int * int |
|
628 val ord = prod_ord int_ord int_ord |
|
629 ) |
627 |
630 |
628 fun shuffle_key (((axiom_no, (_, index_no)), _), _) = (axiom_no, index_no) |
631 fun shuffle_key (((axiom_no, (_, index_no)), _), _) = (axiom_no, index_no) |
629 fun shuffle_ord p = prod_ord int_ord int_ord (apply2 shuffle_key p) |
632 fun shuffle_ord p = prod_ord int_ord int_ord (apply2 shuffle_key p) |
630 |
633 |
631 (* Attempts to derive the theorem "False" from a theorem of the form |
634 (*Attempts to derive the theorem "False" from a theorem of the form |
632 "P1 ==> ... ==> Pn ==> False", where the "Pi"s are to be discharged using the |
635 "P1 ==> ... ==> Pn ==> False", where the "Pi"s are to be discharged using the |
633 specified axioms. The axioms have leading "All" and "Ex" quantifiers, which |
636 specified axioms. The axioms have leading "All" and "Ex" quantifiers, which |
634 must be eliminated first. *) |
637 must be eliminated first.*) |
635 fun discharge_skolem_premises ctxt axioms prems_imp_false = |
638 fun discharge_skolem_premises ctxt axioms prems_imp_false = |
636 if Thm.prop_of prems_imp_false aconv \<^prop>\<open>False\<close> then |
639 if Thm.prop_of prems_imp_false aconv \<^prop>\<open>False\<close> then prems_imp_false |
637 prems_imp_false |
|
638 else |
640 else |
639 let |
641 let |
640 val thy = Proof_Context.theory_of ctxt |
642 val thy = Proof_Context.theory_of ctxt |
641 |
643 |
642 fun match_term p = |
644 fun match_term p = |