introduced SMT.distinct as a representation of the solvers' built-in predicate; check that SMT.distinct is always applied to an explicit list
1 (* Title: HOL/Tools/SMT/z3_proof_reconstruction.ML
2 Author: Sascha Boehme, TU Muenchen
4 Proof reconstruction for proofs found by Z3.
7 signature Z3_PROOF_RECONSTRUCTION =
9 val add_z3_rule: thm -> Context.generic -> Context.generic
10 val reconstruct: Proof.context -> SMT_Translate.recon -> string list ->
11 (int list * thm) * Proof.context
12 val setup: theory -> theory
15 structure Z3_Proof_Reconstruction: Z3_PROOF_RECONSTRUCTION =
18 structure P = Z3_Proof_Parser
19 structure T = Z3_Proof_Tools
20 structure L = Z3_Proof_Literals
22 fun z3_exn msg = raise SMT_Solver.SMT (SMT_Solver.Other_Failure
23 ("Z3 proof reconstruction: " ^ msg))
27 (** net of schematic rules **)
29 val z3_ruleN = "z3_rule"
32 val description = "declaration of Z3 proof rules"
36 structure Z3_Rules = Generic_Data
41 val merge = Net.merge eq
44 val prep = `Thm.prop_of o Simplifier.rewrite_rule [L.rewrite_true]
46 fun ins thm net = Net.insert_term eq (prep thm) net handle Net.INSERT => net
47 fun del thm net = Net.delete_term eq (prep thm) net handle Net.DELETE => net
49 val add = Thm.declaration_attribute (Z3_Rules.map o ins)
50 val del = Thm.declaration_attribute (Z3_Rules.map o del)
53 val add_z3_rule = Z3_Rules.map o ins
55 fun by_schematic_rule ctxt ct =
56 the (T.net_instance (Z3_Rules.get (Context.Proof ctxt)) ct)
59 Attrib.setup (Binding.name z3_ruleN) (Attrib.add_del add del) description #>
60 Global_Theory.add_thms_dynamic (Binding.name z3_ruleN, Net.content o Z3_Rules.get)
68 fun named ctxt name prover ct =
69 let val _ = SMT_Solver.trace_msg ctxt I ("Z3: trying " ^ name ^ " ...")
72 fun NAMED ctxt name tac i st =
73 let val _ = SMT_Solver.trace_msg ctxt I ("Z3: trying " ^ name ^ " ...")
76 fun pretty_goal ctxt thms t =
77 [Pretty.block [Pretty.str "proposition: ", Syntax.pretty_term ctxt t]]
78 |> not (null thms) ? cons (Pretty.big_list "assumptions:"
79 (map (Display.pretty_thm ctxt) thms))
81 fun try_apply ctxt thms =
83 fun try_apply_err ct = Pretty.string_of (Pretty.chunks [
84 Pretty.big_list ("Z3 found a proof," ^
85 " but proof reconstruction failed at the following subgoal:")
86 (pretty_goal ctxt thms (Thm.term_of ct)),
87 Pretty.str ("Adding a rule to the lemma group " ^ quote z3_ruleN ^
88 " might solve this problem.")])
90 fun apply [] ct = error (try_apply_err ct)
91 | apply (prover :: provers) ct =
92 (case try prover ct of
93 SOME thm => (SMT_Solver.trace_msg ctxt I "Z3: succeeded"; thm)
94 | NONE => apply provers ct)
96 in apply o cons (named ctxt "schematic rules" (by_schematic_rule ctxt)) end
100 @{lemma "(if P then Q1 else Q2) = ((P --> Q1) & (~P --> Q2))" by simp}
103 Simplifier.simp_tac (HOL_ss addsimps [rewr_if])
104 THEN_ALL_NEW Classical.fast_tac HOL_cs
109 (** theorems and proofs **)
111 (* theorem incarnations *)
114 Thm of thm | (* theorem without special features *)
115 MetaEq of thm | (* meta equality "t == s" *)
116 Literals of thm * L.littab
117 (* "P1 & ... & Pn" and table of all literals P1, ..., Pn *)
119 fun thm_of (Thm thm) = thm
120 | thm_of (MetaEq thm) = thm COMP @{thm meta_eq_to_obj_eq}
121 | thm_of (Literals (thm, _)) = thm
123 fun meta_eq_of (MetaEq thm) = thm
124 | meta_eq_of p = mk_meta_eq (thm_of p)
126 fun literals_of (Literals (_, lits)) = lits
127 | literals_of p = L.make_littab [thm_of p]
130 (* proof representation *)
132 datatype proof = Unproved of P.proof_step | Proved of theorem
136 (** core proof rules **)
141 val remove_trigger = @{lemma "trigger t p == p"
142 by (rule eq_reflection, rule trigger_def)}
144 val prep_rules = [@{thm Let_def}, remove_trigger, L.rewrite_true]
146 fun rewrite_conv ctxt eqs = Simplifier.full_rewrite
147 (Simplifier.context ctxt Simplifier.empty_ss addsimps eqs)
149 fun rewrites f ctxt eqs = map (f (Conv.fconv_rule (rewrite_conv ctxt eqs)))
151 fun burrow_snd_option f (i, thm) = Option.map (pair i) (f thm)
152 fun lookup_assm ctxt assms ct =
153 (case T.net_instance' burrow_snd_option assms ct of
155 | _ => z3_exn ("not asserted: " ^
156 quote (Syntax.string_of_term ctxt (Thm.term_of ct))))
158 fun prepare_assms ctxt unfolds assms =
160 val unfolds' = rewrites I ctxt [L.rewrite_true] unfolds
162 rewrites apsnd ctxt (union Thm.eq_thm unfolds' prep_rules) assms
163 in (unfolds', T.thm_net_of snd assms') end
165 fun asserted ctxt (unfolds, assms) ct =
166 let val revert_conv = rewrite_conv ctxt unfolds
167 in Thm (T.with_conv revert_conv (snd o lookup_assm ctxt assms) ct) end
169 fun find_assm ctxt (unfolds, assms) ct =
170 fst (lookup_assm ctxt assms (Thm.rhs_of (rewrite_conv ctxt unfolds ct)))
175 (* P = Q ==> P ==> Q or P --> Q ==> P ==> Q *)
177 val meta_iffD1 = @{lemma "P == Q ==> P ==> (Q::bool)" by simp}
178 val meta_iffD1_c = T.precompose2 Thm.dest_binop meta_iffD1
180 val iffD1_c = T.precompose2 (Thm.dest_binop o Thm.dest_arg) @{thm iffD1}
181 val mp_c = T.precompose2 (Thm.dest_binop o Thm.dest_arg) @{thm mp}
183 fun mp (MetaEq thm) p = Thm (Thm.implies_elim (T.compose meta_iffD1_c thm) p)
187 val thm = T.compose iffD1_c pq handle THM _ => T.compose mp_c pq
188 in Thm (Thm.implies_elim thm p) end
193 (* and_elim: P1 & ... & Pn ==> Pi *)
194 (* not_or_elim: ~(P1 | ... | Pn) ==> ~Pi *)
196 fun is_sublit conj t = L.exists_lit conj (fn u => u aconv t)
198 fun derive conj t lits idx ptab =
200 val lit = the (L.get_first_lit (is_sublit conj t) lits)
201 val ls = L.explode conj false false [t] lit
202 val lits' = fold L.insert_lit ls (L.delete_lit lit lits)
204 fun upd (Proved thm) = Proved (Literals (thm_of thm, lits'))
206 in (the (L.lookup_lit lits' t), Inttab.map_entry idx upd ptab) end
208 fun lit_elim conj (p, idx) ct ptab =
209 let val lits = literals_of p
211 (case L.lookup_lit lits (T.term_of ct) of
212 SOME lit => (Thm lit, ptab)
213 | NONE => apfst Thm (derive conj (T.term_of ct) lits idx ptab))
216 val and_elim = lit_elim true
217 val not_or_elim = lit_elim false
222 (* P1, ..., Pn |- False ==> |- ~P1 | ... | ~Pn *)
225 Thm.implies_elim (Thm.implies_intr (Thm.cprop_of lit) thm) lit
226 val explode_disj = L.explode false false false
227 fun intro hyps thm th = fold step (explode_disj hyps th) thm
229 fun dest_ccontr ct = [Thm.dest_arg (Thm.dest_arg (Thm.dest_arg1 ct))]
230 val ccontr = T.precompose dest_ccontr @{thm ccontr}
234 val cu = Thm.capply @{cterm Not} (Thm.dest_arg ct)
235 val hyps = map_filter (try HOLogic.dest_Trueprop) (#hyps (Thm.rep_thm thm))
236 in Thm (T.compose ccontr (T.under_assumption (intro hyps thm) cu)) end
241 (* \/{P1, ..., Pn, Q1, ..., Qn}, ~P1, ..., ~Pn ==> \/{Q1, ..., Qn} *)
243 val explode_disj = L.explode false true false
244 val join_disj = L.join false
245 fun unit thm thms th =
246 let val t = @{term Not} $ T.prop_of thm and ts = map T.prop_of thms
247 in join_disj (L.make_littab (thms @ explode_disj ts th)) t end
249 fun dest_arg2 ct = Thm.dest_arg (Thm.dest_arg ct)
250 fun dest ct = pairself dest_arg2 (Thm.dest_binop ct)
251 val contrapos = T.precompose2 dest @{lemma "(~P ==> ~Q) ==> Q ==> P" by fast}
253 fun unit_resolution thm thms ct =
254 Thm.capply @{cterm Not} (Thm.dest_arg ct)
255 |> T.under_assumption (unit thm thms)
256 |> Thm o T.discharge thm o T.compose contrapos
261 (* P ==> P == True or P ==> P == False *)
263 val iff1 = @{lemma "P ==> P == (~ False)" by simp}
264 val iff2 = @{lemma "~P ==> P == False" by simp}
266 fun iff_true thm = MetaEq (thm COMP iff1)
267 fun iff_false thm = MetaEq (thm COMP iff2)
272 (* distributivity of | over & *)
273 fun distributivity ctxt = Thm o try_apply ctxt [] [
274 named ctxt "fast" (T.by_tac (Classical.fast_tac HOL_cs))]
275 (* FIXME: not very well tested *)
279 (* Tseitin-like axioms *)
282 val disjI1 = @{lemma "(P ==> Q) ==> ~P | Q" by fast}
283 val disjI2 = @{lemma "(~P ==> Q) ==> P | Q" by fast}
284 val disjI3 = @{lemma "(~Q ==> P) ==> P | Q" by fast}
285 val disjI4 = @{lemma "(Q ==> P) ==> P | ~Q" by fast}
287 fun prove' conj1 conj2 ct2 thm =
288 let val lits = L.true_thm :: L.explode conj1 true (conj1 <> conj2) [] thm
289 in L.join conj2 (L.make_littab lits) (Thm.term_of ct2) end
291 fun prove rule (ct1, conj1) (ct2, conj2) =
292 T.under_assumption (prove' conj1 conj2 ct2) ct1 COMP rule
294 fun prove_def_axiom ct =
295 let val (ct1, ct2) = Thm.dest_binop (Thm.dest_arg ct)
297 (case Thm.term_of ct1 of
298 @{term Not} $ (@{term HOL.conj} $ _ $ _) =>
299 prove disjI1 (Thm.dest_arg ct1, true) (ct2, true)
300 | @{term HOL.conj} $ _ $ _ =>
301 prove disjI3 (Thm.capply @{cterm Not} ct2, false) (ct1, true)
302 | @{term Not} $ (@{term HOL.disj} $ _ $ _) =>
303 prove disjI3 (Thm.capply @{cterm Not} ct2, false) (ct1, false)
304 | @{term HOL.disj} $ _ $ _ =>
305 prove disjI2 (Thm.capply @{cterm Not} ct1, false) (ct2, true)
306 | Const (@{const_name SMT.distinct}, _) $ _ =>
308 fun dis_conv cv = Conv.arg_conv (Conv.arg1_conv cv)
310 let val (cu1, cu2) = Thm.dest_binop (Thm.dest_arg cu)
311 in prove disjI4 (Thm.dest_arg cu2, true) (cu1, true) end
312 in T.with_conv (dis_conv T.unfold_distinct_conv) prv ct end
313 | @{term Not} $ (Const (@{const_name SMT.distinct}, _) $ _) =>
315 fun dis_conv cv = Conv.arg_conv (Conv.arg1_conv (Conv.arg_conv cv))
317 let val (cu1, cu2) = Thm.dest_binop (Thm.dest_arg cu)
318 in prove disjI1 (Thm.dest_arg cu1, true) (cu2, true) end
319 in T.with_conv (dis_conv T.unfold_distinct_conv) prv ct end
320 | _ => raise CTERM ("prove_def_axiom", [ct]))
323 fun def_axiom ctxt = Thm o try_apply ctxt [] [
324 named ctxt "conj/disj/distinct" prove_def_axiom,
325 T.by_abstraction (true, false) ctxt [] (fn ctxt' =>
326 named ctxt' "simp+fast" (T.by_tac simp_fast_tac))]
331 (* local definitions *)
334 @{lemma "n == P ==> (~n | P) & (n | ~P)" by simp},
335 @{lemma "n == (if P then s else t) ==> (~P | n = s) & (P | n = t)"
337 @{lemma "n == P ==> n = P" by (rule meta_eq_to_obj_eq)} ]
340 @{lemma "(~n | P) & (n | ~P) ==> P == n" by (atomize(full)) fast},
341 @{lemma "(~P | n = s) & (P | n = t) ==> (if P then s else t) == n"
342 by (atomize(full)) fastsimp} ]
344 val inst_rule = T.match_instantiate Thm.dest_arg
347 (case get_first (try (inst_rule ct)) intro_rules of
349 | NONE => raise CTERM ("intro_def", [ct]))
351 fun intro_def ct = T.make_hyp_def (apply_rule ct) #>> Thm
354 get_first (try (fn rule => MetaEq (thm COMP rule))) apply_rules
355 |> the_default (Thm thm)
360 (* negation normal form *)
363 val quant_rules1 = ([
364 @{lemma "(!!x. P x == Q) ==> ALL x. P x == Q" by simp},
365 @{lemma "(!!x. P x == Q) ==> EX x. P x == Q" by simp}], [
366 @{lemma "(!!x. P x == Q x) ==> ALL x. P x == ALL x. Q x" by simp},
367 @{lemma "(!!x. P x == Q x) ==> EX x. P x == EX x. Q x" by simp}])
369 val quant_rules2 = ([
370 @{lemma "(!!x. ~P x == Q) ==> ~(ALL x. P x) == Q" by simp},
371 @{lemma "(!!x. ~P x == Q) ==> ~(EX x. P x) == Q" by simp}], [
372 @{lemma "(!!x. ~P x == Q x) ==> ~(ALL x. P x) == EX x. Q x" by simp},
373 @{lemma "(!!x. ~P x == Q x) ==> ~(EX x. P x) == ALL x. Q x" by simp}])
375 fun nnf_quant_tac thm (qs as (qs1, qs2)) i st = (
376 Tactic.rtac thm ORELSE'
377 (Tactic.match_tac qs1 THEN' nnf_quant_tac thm qs) ORELSE'
378 (Tactic.match_tac qs2 THEN' nnf_quant_tac thm qs)) i st
380 fun nnf_quant vars qs p ct =
382 |> T.by_tac (nnf_quant_tac (T.varify vars (meta_eq_of p)) qs)
384 fun prove_nnf ctxt = try_apply ctxt [] [
385 named ctxt "conj/disj" L.prove_conj_disj_eq,
386 T.by_abstraction (true, false) ctxt [] (fn ctxt' =>
387 named ctxt' "simp+fast" (T.by_tac simp_fast_tac))]
389 fun nnf ctxt vars ps ct =
390 (case T.term_of ct of
391 _ $ (l as Const _ $ Abs _) $ (r as Const _ $ Abs _) =>
393 then MetaEq (Thm.reflexive (Thm.dest_arg (Thm.dest_arg ct)))
394 else MetaEq (nnf_quant vars quant_rules1 (hd ps) ct)
395 | _ $ (@{term Not} $ (Const _ $ Abs _)) $ (Const _ $ Abs _) =>
396 MetaEq (nnf_quant vars quant_rules2 (hd ps) ct)
399 val nnf_rewr_conv = Conv.arg_conv (Conv.arg_conv
400 (T.unfold_eqs ctxt (map (Thm.symmetric o meta_eq_of) ps)))
401 in Thm (T.with_conv nnf_rewr_conv (prove_nnf ctxt) ct) end)
406 (** equality proof rules **)
409 fun refl ct = MetaEq (Thm.reflexive (Thm.dest_arg (Thm.dest_arg ct)))
413 (* s = t ==> t = s *)
415 val symm_rule = @{lemma "s = t ==> t == s" by simp}
417 fun symm (MetaEq thm) = MetaEq (Thm.symmetric thm)
418 | symm p = MetaEq (thm_of p COMP symm_rule)
423 (* s = t ==> t = u ==> s = u *)
425 val trans1 = @{lemma "s == t ==> t = u ==> s == u" by simp}
426 val trans2 = @{lemma "s = t ==> t == u ==> s == u" by simp}
427 val trans3 = @{lemma "s = t ==> t = u ==> s == u" by simp}
429 fun trans (MetaEq thm1) (MetaEq thm2) = MetaEq (Thm.transitive thm1 thm2)
430 | trans (MetaEq thm) q = MetaEq (thm_of q COMP (thm COMP trans1))
431 | trans p (MetaEq thm) = MetaEq (thm COMP (thm_of p COMP trans2))
432 | trans p q = MetaEq (thm_of q COMP (thm_of p COMP trans3))
437 (* t1 = s1 ==> ... ==> tn = sn ==> f t1 ... tn = f s1 .. sn
438 (reflexive antecendents are droppped) *)
442 fun prove_refl (ct, _) = Thm.reflexive ct
443 fun prove_comb f g cp =
444 let val ((ct1, ct2), (cu1, cu2)) = pairself Thm.dest_comb cp
445 in Thm.combination (f (ct1, cu1)) (g (ct2, cu2)) end
446 fun prove_arg f = prove_comb prove_refl f
448 fun prove f cp = prove_comb (prove f) f cp handle CTERM _ => prove_refl cp
450 fun prove_nary is_comb f =
452 fun prove (cp as (ct, _)) = f cp handle MONO =>
453 if is_comb (Thm.term_of ct)
454 then prove_comb (prove_arg prove) prove cp
458 fun prove_list f n cp =
459 if n = 0 then prove_refl cp
460 else prove_comb (prove_arg f) (prove_list f (n-1)) cp
462 fun with_length f (cp as (cl, _)) =
463 f (length (HOLogic.dest_list (Thm.term_of cl))) cp
465 fun prove_distinct f = prove_arg (with_length (prove_list f))
467 fun prove_eq exn lookup cp =
468 (case lookup (Logic.mk_equals (pairself Thm.term_of cp)) of
470 | NONE => if exn then raise MONO else prove_refl cp)
472 val prove_eq_exn = prove_eq true
473 and prove_eq_safe = prove_eq false
475 fun mono f (cp as (cl, _)) =
476 (case Term.head_of (Thm.term_of cl) of
477 @{term HOL.conj} => prove_nary L.is_conj (prove_eq_exn f)
478 | @{term HOL.disj} => prove_nary L.is_disj (prove_eq_exn f)
479 | Const (@{const_name SMT.distinct}, _) => prove_distinct (prove_eq_safe f)
480 | _ => prove (prove_eq_safe f)) cp
482 fun monotonicity eqs ct =
484 val lookup = AList.lookup (op aconv) (map (`Thm.prop_of o meta_eq_of) eqs)
485 val cp = Thm.dest_binop (Thm.dest_arg ct)
486 in MetaEq (prove_eq_exn lookup cp handle MONO => mono lookup cp) end
491 (* |- f a b = f b a (where f is equality) *)
493 val rule = @{lemma "a = b == b = a" by (atomize(full)) (rule eq_commute)}
495 fun commutativity ct = MetaEq (T.match_instantiate I (T.as_meta_eq ct) rule)
500 (** quantifier proof rules **)
502 (* P ?x = Q ?x ==> (ALL x. P x) = (ALL x. Q x)
503 P ?x = Q ?x ==> (EX x. P x) = (EX x. Q x) *)
506 @{lemma "(!!x. P x == Q x) ==> (ALL x. P x) == (ALL x. Q x)" by simp},
507 @{lemma "(!!x. P x == Q x) ==> (EX x. P x) == (EX x. Q x)" by simp}]
509 fun quant_intro vars p ct =
511 val thm = meta_eq_of p
512 val rules' = T.varify vars thm :: rules
513 val cu = T.as_meta_eq ct
514 in MetaEq (T.by_tac (REPEAT_ALL_NEW (Tactic.match_tac rules')) cu) end
519 (* |- ((ALL x. P x) | Q) = (ALL x. P x | Q) *)
520 fun pull_quant ctxt = Thm o try_apply ctxt [] [
521 named ctxt "fast" (T.by_tac (Classical.fast_tac HOL_cs))]
522 (* FIXME: not very well tested *)
526 (* |- (ALL x. P x & Q x) = ((ALL x. P x) & (ALL x. Q x)) *)
527 fun push_quant ctxt = Thm o try_apply ctxt [] [
528 named ctxt "fast" (T.by_tac (Classical.fast_tac HOL_cs))]
529 (* FIXME: not very well tested *)
533 (* |- (ALL x1 ... xn y1 ... yn. P x1 ... xn) = (ALL x1 ... xn. P x1 ... xn) *)
535 val elim_all = @{lemma "(ALL x. P) == P" by simp}
536 val elim_ex = @{lemma "(EX x. P) == P" by simp}
538 fun elim_unused_conv ctxt =
539 Conv.params_conv ~1 (K (Conv.arg_conv (Conv.arg1_conv
540 (Conv.rewrs_conv [elim_all, elim_ex])))) ctxt
542 fun elim_unused_tac ctxt =
544 Tactic.match_tac [@{thm refl}, @{thm iff_allI}, @{thm iff_exI}]
545 ORELSE' CONVERSION (elim_unused_conv ctxt))
547 fun elim_unused_vars ctxt = Thm o T.by_tac (elim_unused_tac ctxt)
552 (* |- (ALL x1 ... xn. ~(x1 = t1 & ... xn = tn) | P x1 ... xn) = P t1 ... tn *)
553 fun dest_eq_res ctxt = Thm o try_apply ctxt [] [
554 named ctxt "fast" (T.by_tac (Classical.fast_tac HOL_cs))]
555 (* FIXME: not very well tested *)
559 (* |- ~(ALL x1...xn. P x1...xn) | P a1...an *)
561 val rule = @{lemma "~ P x | Q ==> ~(ALL x. P x) | Q" by fast}
563 val quant_inst = Thm o T.by_tac (
564 REPEAT_ALL_NEW (Tactic.match_tac [rule])
565 THEN' Tactic.rtac @{thm excluded_middle})
570 (* c = SOME x. P x |- (EX x. P x) = P c
571 c = SOME x. ~ P x |- ~(ALL x. P x) = ~ P c *)
573 val elim_ex = @{lemma "EX x. P == P" by simp}
574 val elim_all = @{lemma "~ (ALL x. P) == ~P" by simp}
575 val sk_ex = @{lemma "c == SOME x. P x ==> EX x. P x == P c"
576 by simp (intro eq_reflection some_eq_ex[symmetric])}
577 val sk_all = @{lemma "c == SOME x. ~ P x ==> ~(ALL x. P x) == ~ P c"
578 by (simp only: not_all) (intro eq_reflection some_eq_ex[symmetric])}
579 val sk_ex_rule = ((sk_ex, I), elim_ex)
580 and sk_all_rule = ((sk_all, Thm.dest_arg), elim_all)
583 Thm.dest_comb (f (Thm.dest_arg (Thm.dest_arg (Thm.cprop_of sk_rule))))
584 fun type_of f sk_rule = Thm.ctyp_of_term (snd (dest f sk_rule))
585 fun pair2 (a, b) (c, d) = [(a, c), (b, d)]
586 fun inst_sk (sk_rule, f) p c =
587 Thm.instantiate ([(type_of f sk_rule, Thm.ctyp_of_term c)], []) sk_rule
588 |> (fn sk' => Thm.instantiate ([], (pair2 (dest f sk') (p, c))) sk')
589 |> Conv.fconv_rule (Thm.beta_conversion true)
591 fun kind (Const (@{const_name Ex}, _) $ _) = (sk_ex_rule, I, I)
592 | kind (@{term Not} $ (Const (@{const_name All}, _) $ _)) =
593 (sk_all_rule, Thm.dest_arg, Thm.capply @{cterm Not})
594 | kind t = raise TERM ("skolemize", [t])
596 fun dest_abs_type (Abs (_, T, _)) = T
597 | dest_abs_type t = raise TERM ("dest_abs_type", [t])
599 fun bodies_of thy lhs rhs =
601 val (rule, dest, make) = kind (Thm.term_of lhs)
603 fun dest_body idx cbs ct =
605 val cb = Thm.dest_arg (dest ct)
606 val T = dest_abs_type (Thm.term_of cb)
607 val cv = Thm.cterm_of thy (Var (("x", idx), T))
608 val cu = make (Drule.beta_conv cb cv)
609 val cbs' = (cv, cb) :: cbs
611 (snd (Thm.first_order_match (cu, rhs)), rev cbs')
612 handle Pattern.MATCH => dest_body (idx+1) cbs' cu
614 in (rule, dest_body 1 [] lhs) end
616 fun transitive f thm = Thm.transitive thm (f (Thm.rhs_of thm))
618 fun sk_step (rule, elim) (cv, mct, cb) ((is, thm), ctxt) =
622 |> T.make_hyp_def (inst_sk rule (Thm.instantiate_cterm ([], is) cb) ct)
623 |>> pair ((cv, ct) :: is) o Thm.transitive thm
624 | NONE => ((is, transitive (Conv.rewr_conv elim) thm), ctxt))
626 fun skolemize ct ctxt =
628 val (lhs, rhs) = Thm.dest_binop (Thm.dest_arg ct)
629 val (rule, (ctab, cbs)) = bodies_of (ProofContext.theory_of ctxt) lhs rhs
630 fun lookup_var (cv, cb) = (cv, AList.lookup (op aconvc) ctab cv, cb)
632 (([], Thm.reflexive lhs), ctxt)
633 |> fold (sk_step rule) (map lookup_var cbs)
640 (** theory proof rules **)
642 (* theory lemmas: linear arithmetic, arrays *)
644 fun th_lemma ctxt simpset thms = Thm o try_apply ctxt thms [
645 T.by_abstraction (false, true) ctxt thms (fn ctxt' => T.by_tac (
646 NAMED ctxt' "arith" (Arith_Data.arith_tac ctxt')
647 ORELSE' NAMED ctxt' "simp+arith" (Simplifier.simp_tac simpset THEN_ALL_NEW
648 Arith_Data.arith_tac ctxt')))]
652 (* rewriting: prove equalities:
653 * ACI of conjunction/disjunction
654 * contradiction, excluded middle
655 * logical rewriting rules (for negation, implication, equivalence,
657 * normal forms for polynoms (integer/real arithmetic)
658 * quantifier elimination over linear arithmetic
660 structure Z3_Simps = Named_Thms
663 val description = "simplification rules for Z3 proof reconstruction"
667 fun spec_meta_eq_of thm =
668 (case try (fn th => th RS @{thm spec}) thm of
669 SOME thm' => spec_meta_eq_of thm'
670 | NONE => mk_meta_eq thm)
672 fun prep (Thm thm) = spec_meta_eq_of thm
673 | prep (MetaEq thm) = thm
674 | prep (Literals (thm, _)) = spec_meta_eq_of thm
676 fun unfold_conv ctxt ths =
677 Conv.arg_conv (Conv.binop_conv (T.unfold_eqs ctxt (map prep ths)))
679 fun with_conv _ [] prv = prv
680 | with_conv ctxt ths prv = T.with_conv (unfold_conv ctxt ths) prv
683 Conv.arg_conv (Conv.binop_conv (Conv.try_conv T.unfold_distinct_conv))
684 val prove_conj_disj_eq = T.with_conv unfold_conv L.prove_conj_disj_eq
687 fun rewrite ctxt simpset ths = Thm o with_conv ctxt ths (try_apply ctxt [] [
688 named ctxt "conj/disj/distinct" prove_conj_disj_eq,
689 T.by_abstraction (true, false) ctxt [] (fn ctxt' => T.by_tac (
690 NAMED ctxt' "simp (logic)" (Simplifier.simp_tac simpset)
691 THEN_ALL_NEW NAMED ctxt' "fast (logic)" (Classical.fast_tac HOL_cs))),
692 T.by_abstraction (false, true) ctxt [] (fn ctxt' => T.by_tac (
693 NAMED ctxt' "simp (theory)" (Simplifier.simp_tac simpset)
695 NAMED ctxt' "fast (theory)" (Classical.fast_tac HOL_cs)
696 ORELSE' NAMED ctxt' "arith (theory)" (Arith_Data.arith_tac ctxt')))),
697 T.by_abstraction (true, true) ctxt [] (fn ctxt' => T.by_tac (
698 NAMED ctxt' "simp (full)" (Simplifier.simp_tac simpset)
700 NAMED ctxt' "fast (full)" (Classical.fast_tac HOL_cs)
701 ORELSE' NAMED ctxt' "arith (full)" (Arith_Data.arith_tac ctxt'))))])
707 (** proof reconstruction **)
709 (* tracing and checking *)
712 fun count_rules ptab =
714 fun count (_, Unproved _) (solved, total) = (solved, total + 1)
715 | count (_, Proved _) (solved, total) = (solved + 1, total + 1)
716 in Inttab.fold count ptab (0, 0) end
718 fun header idx r (solved, total) =
719 "Z3: #" ^ string_of_int idx ^ ": " ^ P.string_of_rule r ^ " (goal " ^
720 string_of_int (solved + 1) ^ " of " ^ string_of_int total ^ ")"
722 fun check ctxt idx r ps ct p =
723 let val thm = thm_of p |> tap (Thm.join_proofs o single)
725 if (Thm.cprop_of thm) aconvc ct then ()
726 else z3_exn (Pretty.string_of (Pretty.big_list ("proof step failed: " ^
727 quote (P.string_of_rule r) ^ " (#" ^ string_of_int idx ^ ")")
728 (pretty_goal ctxt (map (thm_of o fst) ps) (Thm.prop_of thm) @
729 [Pretty.block [Pretty.str "expected: ",
730 Syntax.pretty_term ctxt (Thm.term_of ct)]])))
733 fun trace_rule idx prove r ps ct (cxp as (ctxt, ptab)) =
735 val _ = SMT_Solver.trace_msg ctxt (header idx r o count_rules) ptab
736 val result as (p, (ctxt', _)) = prove r ps ct cxp
737 val _ = if not (Config.get ctxt' SMT_Solver.trace) then ()
738 else check ctxt' idx r ps ct p
743 (* overall reconstruction procedure *)
746 fun not_supported r = raise Fail ("Z3: proof rule not implemented: " ^
747 quote (P.string_of_rule r))
749 fun step assms simpset vars r ps ct (cxp as (cx, ptab)) =
752 (P.TrueAxiom, _) => (Thm L.true_thm, cxp)
753 | (P.Asserted, _) => (asserted cx assms ct, cxp)
754 | (P.Goal, _) => (asserted cx assms ct, cxp)
755 | (P.ModusPonens, [(p, _), (q, _)]) => (mp q (thm_of p), cxp)
756 | (P.ModusPonensOeq, [(p, _), (q, _)]) => (mp q (thm_of p), cxp)
757 | (P.AndElim, [(p, i)]) => and_elim (p, i) ct ptab ||> pair cx
758 | (P.NotOrElim, [(p, i)]) => not_or_elim (p, i) ct ptab ||> pair cx
759 | (P.Hypothesis, _) => (Thm (Thm.assume ct), cxp)
760 | (P.Lemma, [(p, _)]) => (lemma (thm_of p) ct, cxp)
761 | (P.UnitResolution, (p, _) :: ps) =>
762 (unit_resolution (thm_of p) (map (thm_of o fst) ps) ct, cxp)
763 | (P.IffTrue, [(p, _)]) => (iff_true (thm_of p), cxp)
764 | (P.IffFalse, [(p, _)]) => (iff_false (thm_of p), cxp)
765 | (P.Distributivity, _) => (distributivity cx ct, cxp)
766 | (P.DefAxiom, _) => (def_axiom cx ct, cxp)
767 | (P.IntroDef, _) => intro_def ct cx ||> rpair ptab
768 | (P.ApplyDef, [(p, _)]) => (apply_def (thm_of p), cxp)
769 | (P.IffOeq, [(p, _)]) => (p, cxp)
770 | (P.NnfPos, _) => (nnf cx vars (map fst ps) ct, cxp)
771 | (P.NnfNeg, _) => (nnf cx vars (map fst ps) ct, cxp)
774 | (P.Reflexivity, _) => (refl ct, cxp)
775 | (P.Symmetry, [(p, _)]) => (symm p, cxp)
776 | (P.Transitivity, [(p, _), (q, _)]) => (trans p q, cxp)
777 | (P.Monotonicity, _) => (monotonicity (map fst ps) ct, cxp)
778 | (P.Commutativity, _) => (commutativity ct, cxp)
780 (* quantifier rules *)
781 | (P.QuantIntro, [(p, _)]) => (quant_intro vars p ct, cxp)
782 | (P.PullQuant, _) => (pull_quant cx ct, cxp)
783 | (P.PushQuant, _) => (push_quant cx ct, cxp)
784 | (P.ElimUnusedVars, _) => (elim_unused_vars cx ct, cxp)
785 | (P.DestEqRes, _) => (dest_eq_res cx ct, cxp)
786 | (P.QuantInst, _) => (quant_inst ct, cxp)
787 | (P.Skolemize, _) => skolemize ct cx ||> rpair ptab
791 (th_lemma cx simpset (map (thm_of o fst) ps) ct, cxp)
792 | (P.Rewrite, _) => (rewrite cx simpset [] ct, cxp)
793 | (P.RewriteStar, ps) =>
794 (rewrite cx simpset (map fst ps) ct, cxp)
796 | (P.NnfStar, _) => not_supported r
797 | (P.CnfStar, _) => not_supported r
798 | (P.TransitivityStar, _) => not_supported r
799 | (P.PullQuantStar, _) => not_supported r
801 | _ => raise Fail ("Z3: proof rule " ^ quote (P.string_of_rule r) ^
802 " has an unexpected number of arguments."))
804 fun prove ctxt assms vars =
806 val simpset = T.make_simpset ctxt (Z3_Simps.get ctxt)
808 fun conclude idx rule prop (ps, cxp) =
809 trace_rule idx (step assms simpset vars) rule ps prop cxp
810 |-> (fn p => apsnd (Inttab.update (idx, Proved p)) #> pair p)
812 fun lookup idx (cxp as (_, ptab)) =
813 (case Inttab.lookup ptab idx of
814 SOME (Unproved (P.Proof_Step {rule, prems, prop})) =>
815 fold_map lookup prems cxp
817 |> conclude idx rule prop
818 | SOME (Proved p) => (p, cxp)
819 | NONE => z3_exn ("unknown proof id: " ^ quote (string_of_int idx)))
821 fun result (p, (cx, _)) = (thm_of p, cx)
823 (fn idx => result o lookup idx o pair ctxt o Inttab.map (K Unproved))
826 fun filter_assms ctxt assms ptab =
830 P.Asserted => insert (op =) (find_assm ctxt assms ct)
831 | P.Goal => insert (op =) (find_assm ctxt assms ct)
835 (case Inttab.lookup ptab idx of
836 SOME (P.Proof_Step {rule, prems, prop}) =>
837 fold lookup prems #> step rule prop
838 | NONE => z3_exn ("unknown proof id: " ^ quote (string_of_int idx)))
842 fun reconstruct ctxt {typs, terms, unfolds, assms} output =
844 val (idx, (ptab, vars, cx)) = P.parse ctxt typs terms output
845 val assms' = prepare_assms cx unfolds assms
847 if Config.get cx SMT_Solver.filter_only
848 then ((filter_assms cx assms' ptab idx [], @{thm TrueI}), cx)
849 else apfst (pair []) (prove cx assms' vars idx ptab)
854 val setup = z3_rules_setup #> Z3_Simps.setup