src/HOL/Tools/meson.ML
changeset 39328 268cd501bdc1
parent 39277 f263522ab226
child 39886 8a9f0c97d550
equal deleted inserted replaced
39327:61547eda78b4 39328:268cd501bdc1
     9 sig
     9 sig
    10   val trace: bool Unsynchronized.ref
    10   val trace: bool Unsynchronized.ref
    11   val term_pair_of: indexname * (typ * 'a) -> term * 'a
    11   val term_pair_of: indexname * (typ * 'a) -> term * 'a
    12   val flexflex_first_order: thm -> thm
    12   val flexflex_first_order: thm -> thm
    13   val size_of_subgoals: thm -> int
    13   val size_of_subgoals: thm -> int
    14   val estimated_num_clauses: Proof.context -> int -> term -> int
       
    15   val has_too_many_clauses: Proof.context -> term -> bool
    14   val has_too_many_clauses: Proof.context -> term -> bool
    16   val make_cnf: thm list -> thm -> Proof.context -> thm list * Proof.context
    15   val make_cnf: thm list -> thm -> Proof.context -> thm list * Proof.context
    17   val finish_cnf: thm list -> thm list
    16   val finish_cnf: thm list -> thm list
    18   val presimplify: thm -> thm
    17   val presimplify: thm -> thm
    19   val make_nnf: Proof.context -> thm -> thm
    18   val make_nnf: Proof.context -> thm -> thm
    92 (**** Operators for forward proof ****)
    91 (**** Operators for forward proof ****)
    93 
    92 
    94 
    93 
    95 (** First-order Resolution **)
    94 (** First-order Resolution **)
    96 
    95 
    97 fun typ_pair_of (ix, (sort,ty)) = (TVar (ix,sort), ty);
       
    98 fun term_pair_of (ix, (ty,t)) = (Var (ix,ty), t);
    96 fun term_pair_of (ix, (ty,t)) = (Var (ix,ty), t);
    99 
    97 
   100 (*FIXME: currently does not "rename variables apart"*)
    98 (*FIXME: currently does not "rename variables apart"*)
   101 fun first_order_resolve thA thB =
    99 fun first_order_resolve thA thB =
   102   (case
   100   (case
   115 fun flexflex_first_order th =
   113 fun flexflex_first_order th =
   116   case Thm.tpairs_of th of
   114   case Thm.tpairs_of th of
   117       [] => th
   115       [] => th
   118     | pairs =>
   116     | pairs =>
   119         let val thy = theory_of_thm th
   117         let val thy = theory_of_thm th
   120             val (tyenv, tenv) =
   118             val (_, tenv) =
   121               fold (Pattern.first_order_match thy) pairs (Vartab.empty, Vartab.empty)
   119               fold (Pattern.first_order_match thy) pairs (Vartab.empty, Vartab.empty)
   122             val t_pairs = map term_pair_of (Vartab.dest tenv)
   120             val t_pairs = map term_pair_of (Vartab.dest tenv)
   123             val th' = Thm.instantiate ([], map (pairself (cterm_of thy)) t_pairs) th
   121             val th' = Thm.instantiate ([], map (pairself (cterm_of thy)) t_pairs) th
   124         in  th'  end
   122         in  th'  end
   125         handle THM _ => th;
   123         handle THM _ => th;
   152      | NONE => raise THM("forward_res", 0, [st])
   150      | NONE => raise THM("forward_res", 0, [st])
   153   end;
   151   end;
   154 
   152 
   155 (*Are any of the logical connectives in "bs" present in the term?*)
   153 (*Are any of the logical connectives in "bs" present in the term?*)
   156 fun has_conns bs =
   154 fun has_conns bs =
   157   let fun has (Const(a,_)) = false
   155   let fun has (Const _) = false
   158         | has (Const(@{const_name Trueprop},_) $ p) = has p
   156         | has (Const(@{const_name Trueprop},_) $ p) = has p
   159         | has (Const(@{const_name Not},_) $ p) = has p
   157         | has (Const(@{const_name Not},_) $ p) = has p
   160         | has (Const(@{const_name HOL.disj},_) $ p $ q) = member (op =) bs @{const_name HOL.disj} orelse has p orelse has q
   158         | has (Const(@{const_name HOL.disj},_) $ p $ q) = member (op =) bs @{const_name HOL.disj} orelse has p orelse has q
   161         | has (Const(@{const_name HOL.conj},_) $ p $ q) = member (op =) bs @{const_name HOL.conj} orelse has p orelse has q
   159         | has (Const(@{const_name HOL.conj},_) $ p $ q) = member (op =) bs @{const_name HOL.conj} orelse has p orelse has q
   162         | has (Const(@{const_name All},_) $ Abs(_,_,p)) = member (op =) bs @{const_name All} orelse has p
   160         | has (Const(@{const_name All},_) $ Abs(_,_,p)) = member (op =) bs @{const_name All} orelse has p
   236 
   234 
   237 
   235 
   238 (*** Removal of duplicate literals ***)
   236 (*** Removal of duplicate literals ***)
   239 
   237 
   240 (*Forward proof, passing extra assumptions as theorems to the tactic*)
   238 (*Forward proof, passing extra assumptions as theorems to the tactic*)
   241 fun forward_res2 ctxt nf hyps st =
   239 fun forward_res2 nf hyps st =
   242   case Seq.pull
   240   case Seq.pull
   243         (REPEAT
   241         (REPEAT
   244          (Misc_Legacy.METAHYPS (fn major::minors => rtac (nf (minors@hyps) major) 1) 1)
   242          (Misc_Legacy.METAHYPS (fn major::minors => rtac (nf (minors@hyps) major) 1) 1)
   245          st)
   243          st)
   246   of SOME(th,_) => th
   244   of SOME(th,_) => th
   248 
   246 
   249 (*Remove duplicates in P|Q by assuming ~P in Q
   247 (*Remove duplicates in P|Q by assuming ~P in Q
   250   rls (initially []) accumulates assumptions of the form P==>False*)
   248   rls (initially []) accumulates assumptions of the form P==>False*)
   251 fun nodups_aux ctxt rls th = nodups_aux ctxt rls (th RS disj_assoc)
   249 fun nodups_aux ctxt rls th = nodups_aux ctxt rls (th RS disj_assoc)
   252     handle THM _ => tryres(th,rls)
   250     handle THM _ => tryres(th,rls)
   253     handle THM _ => tryres(forward_res2 ctxt (nodups_aux ctxt) rls (th RS disj_forward2),
   251     handle THM _ => tryres(forward_res2 (nodups_aux ctxt) rls (th RS disj_forward2),
   254                            [disj_FalseD1, disj_FalseD2, asm_rl])
   252                            [disj_FalseD1, disj_FalseD2, asm_rl])
   255     handle THM _ => th;
   253     handle THM _ => th;
   256 
   254 
   257 (*Remove duplicate literals, if there are any*)
   255 (*Remove duplicate literals, if there are any*)
   258 fun nodups ctxt th =
   256 fun nodups ctxt th =
   261     else th;
   259     else th;
   262 
   260 
   263 
   261 
   264 (*** The basic CNF transformation ***)
   262 (*** The basic CNF transformation ***)
   265 
   263 
   266 fun estimated_num_clauses ctxt bound t =
   264 fun estimated_num_clauses bound t =
   267  let
   265  let
   268   fun sum x y = if x < bound andalso y < bound then x+y else bound
   266   fun sum x y = if x < bound andalso y < bound then x+y else bound
   269   fun prod x y = if x < bound andalso y < bound then x*y else bound
   267   fun prod x y = if x < bound andalso y < bound then x*y else bound
   270   
   268   
   271   (*Estimate the number of clauses in order to detect infeasible theorems*)
   269   (*Estimate the number of clauses in order to detect infeasible theorems*)
   292     | signed_nclauses _ _ = 1; (* literal *)
   290     | signed_nclauses _ _ = 1; (* literal *)
   293  in signed_nclauses true t end
   291  in signed_nclauses true t end
   294 
   292 
   295 fun has_too_many_clauses ctxt t =
   293 fun has_too_many_clauses ctxt t =
   296   let val max_cl = Config.get ctxt max_clauses in
   294   let val max_cl = Config.get ctxt max_clauses in
   297     estimated_num_clauses ctxt (max_cl + 1) t > max_cl
   295     estimated_num_clauses (max_cl + 1) t > max_cl
   298   end
   296   end
   299 
   297 
   300 (*Replaces universally quantified variables by FREE variables -- because
   298 (*Replaces universally quantified variables by FREE variables -- because
   301   assumptions may not contain scheme variables.  Later, generalize using Variable.export. *)
   299   assumptions may not contain scheme variables.  Later, generalize using Variable.export. *)
   302 local  
   300 local  
   446   else th;
   444   else th;
   447 
   445 
   448 (*Generate Horn clauses for all contrapositives of a clause. The input, th,
   446 (*Generate Horn clauses for all contrapositives of a clause. The input, th,
   449   is a HOL disjunction.*)
   447   is a HOL disjunction.*)
   450 fun add_contras crules th hcs =
   448 fun add_contras crules th hcs =
   451   let fun rots (0,th) = hcs
   449   let fun rots (0,_) = hcs
   452         | rots (k,th) = zero_var_indexes (make_horn crules th) ::
   450         | rots (k,th) = zero_var_indexes (make_horn crules th) ::
   453                         rots(k-1, assoc_right (th RS disj_comm))
   451                         rots(k-1, assoc_right (th RS disj_comm))
   454   in case nliterals(prop_of th) of
   452   in case nliterals(prop_of th) of
   455         1 => th::hcs
   453         1 => th::hcs
   456       | n => rots(n, assoc_right th)
   454       | n => rots(n, assoc_right th)
   637 (** Iterative deepening version **)
   635 (** Iterative deepening version **)
   638 
   636 
   639 (*This version does only one inference per call;
   637 (*This version does only one inference per call;
   640   having only one eq_assume_tac speeds it up!*)
   638   having only one eq_assume_tac speeds it up!*)
   641 fun prolog_step_tac' horns =
   639 fun prolog_step_tac' horns =
   642     let val (horn0s, hornps) = (*0 subgoals vs 1 or more*)
   640     let val (horn0s, _) = (*0 subgoals vs 1 or more*)
   643             take_prefix Thm.no_prems horns
   641             take_prefix Thm.no_prems horns
   644         val nrtac = net_resolve_tac horns
   642         val nrtac = net_resolve_tac horns
   645     in  fn i => eq_assume_tac i ORELSE
   643     in  fn i => eq_assume_tac i ORELSE
   646                 match_tac horn0s i ORELSE  (*no backtracking if unit MATCHES*)
   644                 match_tac horn0s i ORELSE  (*no backtracking if unit MATCHES*)
   647                 ((assume_tac i APPEND nrtac i) THEN check_tac)
   645                 ((assume_tac i APPEND nrtac i) THEN check_tac)