168 (* Special version of "resolve_tac" that works around an explosion in the unifier. |
168 (* Special version of "resolve_tac" that works around an explosion in the unifier. |
169 If the goal has the form "?P c", the danger is that resolving it against a |
169 If the goal has the form "?P c", the danger is that resolving it against a |
170 property of the form "... c ... c ... c ..." will lead to a huge unification |
170 property of the form "... c ... c ... c ..." will lead to a huge unification |
171 problem, due to the (spurious) choices between projection and imitation. The |
171 problem, due to the (spurious) choices between projection and imitation. The |
172 workaround is to instantiate "?P := (%c. ... c ... c ... c ...)" manually. *) |
172 workaround is to instantiate "?P := (%c. ... c ... c ... c ...)" manually. *) |
173 fun quant_resolve_tac th i st = |
173 fun quant_resolve_tac ctxt th i st = |
174 case (concl_of st, prop_of th) of |
174 case (concl_of st, prop_of th) of |
175 (@{const Trueprop} $ (Var _ $ (c as Free _)), @{const Trueprop} $ _) => |
175 (@{const Trueprop} $ (Var _ $ (c as Free _)), @{const Trueprop} $ _) => |
176 let |
176 let |
177 val cc = cterm_of (theory_of_thm th) c |
177 val cc = cterm_of (theory_of_thm th) c |
178 val ct = Thm.dest_arg (cprop_of th) |
178 val ct = Thm.dest_arg (cprop_of th) |
179 in resolve_tac [th] i (Drule.instantiate' [] [SOME (Thm.lambda cc ct)] st) end |
179 in resolve_tac ctxt [th] i (Drule.instantiate' [] [SOME (Thm.lambda cc ct)] st) end |
180 | _ => resolve_tac [th] i st |
180 | _ => resolve_tac ctxt [th] i st |
181 |
181 |
182 (*Permits forward proof from rules that discharge assumptions. The supplied proof state st, |
182 (*Permits forward proof from rules that discharge assumptions. The supplied proof state st, |
183 e.g. from conj_forward, should have the form |
183 e.g. from conj_forward, should have the form |
184 "[| P' ==> ?P; Q' ==> ?Q |] ==> ?P & ?Q" |
184 "[| P' ==> ?P; Q' ==> ?Q |] ==> ?P & ?Q" |
185 and the effect should be to instantiate ?P and ?Q with normalized versions of P' and Q'.*) |
185 and the effect should be to instantiate ?P and ?Q with normalized versions of P' and Q'.*) |
186 fun forward_res ctxt nf st = |
186 fun forward_res ctxt nf st = |
187 let |
187 let |
188 fun tacf [prem] = quant_resolve_tac (nf prem) 1 |
188 fun tacf [prem] = quant_resolve_tac ctxt (nf prem) 1 |
189 | tacf prems = |
189 | tacf prems = |
190 error (cat_lines |
190 error (cat_lines |
191 ("Bad proof state in forward_res, please inform lcp@cl.cam.ac.uk:" :: |
191 ("Bad proof state in forward_res, please inform lcp@cl.cam.ac.uk:" :: |
192 Display.string_of_thm ctxt st :: |
192 Display.string_of_thm ctxt st :: |
193 "Premises:" :: map (Display.string_of_thm ctxt) prems)) |
193 "Premises:" :: map (Display.string_of_thm ctxt) prems)) |
285 (*Forward proof, passing extra assumptions as theorems to the tactic*) |
285 (*Forward proof, passing extra assumptions as theorems to the tactic*) |
286 fun forward_res2 ctxt nf hyps st = |
286 fun forward_res2 ctxt nf hyps st = |
287 case Seq.pull |
287 case Seq.pull |
288 (REPEAT |
288 (REPEAT |
289 (Misc_Legacy.METAHYPS ctxt |
289 (Misc_Legacy.METAHYPS ctxt |
290 (fn major::minors => resolve_tac [nf (minors @ hyps) major] 1) 1) |
290 (fn major::minors => resolve_tac ctxt [nf (minors @ hyps) major] 1) 1) |
291 st) |
291 st) |
292 of SOME(th,_) => th |
292 of SOME(th,_) => th |
293 | NONE => raise THM("forward_res2", 0, [st]); |
293 | NONE => raise THM("forward_res2", 0, [st]); |
294 |
294 |
295 (*Remove duplicates in P|Q by assuming ~P in Q |
295 (*Remove duplicates in P|Q by assuming ~P in Q |
388 all combinations of converting P, Q to CNF.*) |
388 all combinations of converting P, Q to CNF.*) |
389 (*There is one assumption, which gets bound to prem and then normalized via |
389 (*There is one assumption, which gets bound to prem and then normalized via |
390 cnf_nil. The normal form is given to resolve_tac, instantiate a Boolean |
390 cnf_nil. The normal form is given to resolve_tac, instantiate a Boolean |
391 variable created by resolution with disj_forward. Since (cnf_nil prem) |
391 variable created by resolution with disj_forward. Since (cnf_nil prem) |
392 returns a LIST of theorems, we can backtrack to get all combinations.*) |
392 returns a LIST of theorems, we can backtrack to get all combinations.*) |
393 let val tac = Misc_Legacy.METAHYPS ctxt (fn [prem] => resolve_tac (cnf_nil prem) 1) 1 |
393 let val tac = Misc_Legacy.METAHYPS ctxt (fn [prem] => resolve_tac ctxt (cnf_nil prem) 1) 1 |
394 in Seq.list_of ((tac THEN tac) (th RS disj_forward)) @ ths end |
394 in Seq.list_of ((tac THEN tac) (th RS disj_forward)) @ ths end |
395 | _ => nodups ctxt th :: ths (*no work to do*) |
395 | _ => nodups ctxt th :: ths (*no work to do*) |
396 and cnf_nil th = cnf_aux (th, []) |
396 and cnf_nil th = cnf_aux (th, []) |
397 val cls = |
397 val cls = |
398 if has_too_many_clauses ctxt (concl_of th) then |
398 if has_too_many_clauses ctxt (concl_of th) then |
498 then Seq.empty else Seq.single st; |
498 then Seq.empty else Seq.single st; |
499 |
499 |
500 |
500 |
501 (* resolve_from_net_tac actually made it slower... *) |
501 (* resolve_from_net_tac actually made it slower... *) |
502 fun prolog_step_tac ctxt horns i = |
502 fun prolog_step_tac ctxt horns i = |
503 (assume_tac ctxt i APPEND resolve_tac horns i) THEN check_tac THEN |
503 (assume_tac ctxt i APPEND resolve_tac ctxt horns i) THEN check_tac THEN |
504 TRYALL_eq_assume_tac; |
504 TRYALL_eq_assume_tac; |
505 |
505 |
506 (*Sums the sizes of the subgoals, ignoring hypotheses (ancestors)*) |
506 (*Sums the sizes of the subgoals, ignoring hypotheses (ancestors)*) |
507 fun addconcl prem sz = size_of_term (Logic.strip_assums_concl prem) + sz; |
507 fun addconcl prem sz = size_of_term (Logic.strip_assums_concl prem) + sz; |
508 |
508 |
696 |
696 |
697 (*Return all negative clauses, as possible goal clauses*) |
697 (*Return all negative clauses, as possible goal clauses*) |
698 fun gocls cls = name_thms "Goal#" (map make_goal (neg_clauses cls)); |
698 fun gocls cls = name_thms "Goal#" (map make_goal (neg_clauses cls)); |
699 |
699 |
700 fun skolemize_prems_tac ctxt prems = |
700 fun skolemize_prems_tac ctxt prems = |
701 cut_facts_tac (maps (try_skolemize_etc ctxt) prems) THEN' REPEAT o eresolve_tac [exE] |
701 cut_facts_tac (maps (try_skolemize_etc ctxt) prems) THEN' REPEAT o eresolve_tac ctxt [exE] |
702 |
702 |
703 (*Basis of all meson-tactics. Supplies cltac with clauses: HOL disjunctions. |
703 (*Basis of all meson-tactics. Supplies cltac with clauses: HOL disjunctions. |
704 Function mkcl converts theorems to clauses.*) |
704 Function mkcl converts theorems to clauses.*) |
705 fun MESON preskolem_tac mkcl cltac ctxt i st = |
705 fun MESON preskolem_tac mkcl cltac ctxt i st = |
706 SELECT_GOAL |
706 SELECT_GOAL |
707 (EVERY [Object_Logic.atomize_prems_tac ctxt 1, |
707 (EVERY [Object_Logic.atomize_prems_tac ctxt 1, |
708 resolve_tac @{thms ccontr} 1, |
708 resolve_tac ctxt @{thms ccontr} 1, |
709 preskolem_tac, |
709 preskolem_tac, |
710 Subgoal.FOCUS (fn {context = ctxt', prems = negs, ...} => |
710 Subgoal.FOCUS (fn {context = ctxt', prems = negs, ...} => |
711 EVERY1 [skolemize_prems_tac ctxt negs, |
711 EVERY1 [skolemize_prems_tac ctxt negs, |
712 Subgoal.FOCUS (cltac o mkcl o #prems) ctxt']) ctxt 1]) i st |
712 Subgoal.FOCUS (cltac o mkcl o #prems) ctxt']) ctxt 1]) i st |
713 handle THM _ => no_tac st; (*probably from make_meta_clause, not first-order*) |
713 handle THM _ => no_tac st; (*probably from make_meta_clause, not first-order*) |
717 |
717 |
718 (*ths is a list of additional clauses (HOL disjunctions) to use.*) |
718 (*ths is a list of additional clauses (HOL disjunctions) to use.*) |
719 fun best_meson_tac sizef ctxt = |
719 fun best_meson_tac sizef ctxt = |
720 MESON all_tac (make_clauses ctxt) |
720 MESON all_tac (make_clauses ctxt) |
721 (fn cls => |
721 (fn cls => |
722 THEN_BEST_FIRST (resolve_tac (gocls cls) 1) |
722 THEN_BEST_FIRST (resolve_tac ctxt (gocls cls) 1) |
723 (has_fewer_prems 1, sizef) |
723 (has_fewer_prems 1, sizef) |
724 (prolog_step_tac ctxt (make_horns cls) 1)) |
724 (prolog_step_tac ctxt (make_horns cls) 1)) |
725 ctxt |
725 ctxt |
726 |
726 |
727 (*First, breaks the goal into independent units*) |
727 (*First, breaks the goal into independent units*) |
730 |
730 |
731 (** Depth-first search version **) |
731 (** Depth-first search version **) |
732 |
732 |
733 fun depth_meson_tac ctxt = |
733 fun depth_meson_tac ctxt = |
734 MESON all_tac (make_clauses ctxt) |
734 MESON all_tac (make_clauses ctxt) |
735 (fn cls => EVERY [resolve_tac (gocls cls) 1, depth_prolog_tac ctxt (make_horns cls)]) |
735 (fn cls => EVERY [resolve_tac ctxt (gocls cls) 1, depth_prolog_tac ctxt (make_horns cls)]) |
736 ctxt |
736 ctxt |
737 |
737 |
738 (** Iterative deepening version **) |
738 (** Iterative deepening version **) |
739 |
739 |
740 (*This version does only one inference per call; |
740 (*This version does only one inference per call; |
762 cat_lines ("meson method called:" :: |
762 cat_lines ("meson method called:" :: |
763 map (Display.string_of_thm ctxt) (cls @ ths) @ |
763 map (Display.string_of_thm ctxt) (cls @ ths) @ |
764 ["clauses:"] @ map (Display.string_of_thm ctxt) horns)) |
764 ["clauses:"] @ map (Display.string_of_thm ctxt) horns)) |
765 in |
765 in |
766 THEN_ITER_DEEPEN iter_deepen_limit |
766 THEN_ITER_DEEPEN iter_deepen_limit |
767 (resolve_tac goes 1) (has_fewer_prems 1) (prolog_step_tac' ctxt horns) |
767 (resolve_tac ctxt goes 1) (has_fewer_prems 1) (prolog_step_tac' ctxt horns) |
768 end)); |
768 end)); |
769 |
769 |
770 fun meson_tac ctxt ths = |
770 fun meson_tac ctxt ths = |
771 SELECT_GOAL (TRY (safe_tac ctxt) THEN TRYALL (iter_deepen_meson_tac ctxt ths)); |
771 SELECT_GOAL (TRY (safe_tac ctxt) THEN TRYALL (iter_deepen_meson_tac ctxt ths)); |
772 |
772 |