src/HOL/Tools/Meson/meson.ML
changeset 59498 50b60f501b05
parent 59171 75ec7271b426
child 59580 cbc38731d42f
equal deleted inserted replaced
59497:0c5cd369a643 59498:50b60f501b05
   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