src/Provers/Arith/fast_lin_arith.ML
changeset 16458 4c6fd0c01d28
parent 16358 2e2a506553a3
child 16735 008d089822e3
equal deleted inserted replaced
16457:e0f22edf38a5 16458:4c6fd0c01d28
     9     lin_arith_tac:         int -> tactic
     9     lin_arith_tac:         int -> tactic
    10 cut_lin_arith_tac: thms -> int -> tactic
    10 cut_lin_arith_tac: thms -> int -> tactic
    11 
    11 
    12 and a simplification procedure
    12 and a simplification procedure
    13 
    13 
    14     lin_arith_prover: Sign.sg -> simpset -> term -> thm option
    14     lin_arith_prover: theory -> simpset -> term -> thm option
    15 
    15 
    16 Only take premises and conclusions into account that are already (negated)
    16 Only take premises and conclusions into account that are already (negated)
    17 (in)equations. lin_arith_prover tries to prove or disprove the term.
    17 (in)equations. lin_arith_prover tries to prove or disprove the term.
    18 *)
    18 *)
    19 
    19 
    32   val mk_Eq: thm -> thm
    32   val mk_Eq: thm -> thm
    33   val mk_Trueprop: term -> term
    33   val mk_Trueprop: term -> term
    34   val neg_prop: term -> term
    34   val neg_prop: term -> term
    35   val is_False: thm -> bool
    35   val is_False: thm -> bool
    36   val is_nat: typ list * term -> bool
    36   val is_nat: typ list * term -> bool
    37   val mk_nat_thm: Sign.sg -> term -> thm
    37   val mk_nat_thm: theory -> term -> thm
    38 end;
    38 end;
    39 (*
    39 (*
    40 mk_Eq(~in) = `in == False'
    40 mk_Eq(~in) = `in == False'
    41 mk_Eq(in) = `in == True'
    41 mk_Eq(in) = `in == True'
    42 where `in' is an (in)equality.
    42 where `in' is an (in)equality.
    50 *)
    50 *)
    51 
    51 
    52 signature LIN_ARITH_DATA =
    52 signature LIN_ARITH_DATA =
    53 sig
    53 sig
    54   val decomp:
    54   val decomp:
    55     Sign.sg -> term -> ((term*rat)list * rat * string * (term*rat)list * rat * bool)option
    55     theory -> term -> ((term*rat)list * rat * string * (term*rat)list * rat * bool)option
    56   val number_of: IntInf.int * typ -> term
    56   val number_of: IntInf.int * typ -> term
    57 end;
    57 end;
    58 (*
    58 (*
    59 decomp(`x Rel y') should yield (p,i,Rel,q,j,d)
    59 decomp(`x Rel y') should yield (p,i,Rel,q,j,d)
    60    where Rel is one of "<", "~<", "<=", "~<=" and "=" and
    60    where Rel is one of "<", "~<", "<=", "~<=" and "=" and
    75                  -> {add_mono_thms: thm list, mult_mono_thms: thm list, inj_thms: thm list,
    75                  -> {add_mono_thms: thm list, mult_mono_thms: thm list, inj_thms: thm list,
    76                      lessD: thm list, neqE: thm list, simpset: Simplifier.simpset})
    76                      lessD: thm list, neqE: thm list, simpset: Simplifier.simpset})
    77                 -> theory -> theory
    77                 -> theory -> theory
    78   val trace           : bool ref
    78   val trace           : bool ref
    79   val fast_arith_neq_limit: int ref
    79   val fast_arith_neq_limit: int ref
    80   val lin_arith_prover: Sign.sg -> simpset -> term -> thm option
    80   val lin_arith_prover: theory -> simpset -> term -> thm option
    81   val     lin_arith_tac:     bool -> int -> tactic
    81   val     lin_arith_tac:     bool -> int -> tactic
    82   val cut_lin_arith_tac: thm list -> int -> tactic
    82   val cut_lin_arith_tac: thm list -> int -> tactic
    83 end;
    83 end;
    84 
    84 
    85 functor Fast_Lin_Arith(structure LA_Logic:LIN_ARITH_LOGIC 
    85 functor Fast_Lin_Arith(structure LA_Logic:LIN_ARITH_LOGIC 
    89 
    89 
    90 (** theory data **)
    90 (** theory data **)
    91 
    91 
    92 (* data kind 'Provers/fast_lin_arith' *)
    92 (* data kind 'Provers/fast_lin_arith' *)
    93 
    93 
    94 structure DataArgs =
    94 structure Data = TheoryDataFun
    95 struct
    95 (struct
    96   val name = "Provers/fast_lin_arith";
    96   val name = "Provers/fast_lin_arith";
    97   type T = {add_mono_thms: thm list, mult_mono_thms: thm list, inj_thms: thm list,
    97   type T = {add_mono_thms: thm list, mult_mono_thms: thm list, inj_thms: thm list,
    98             lessD: thm list, neqE: thm list, simpset: Simplifier.simpset};
    98             lessD: thm list, neqE: thm list, simpset: Simplifier.simpset};
    99 
    99 
   100   val empty = {add_mono_thms = [], mult_mono_thms = [], inj_thms = [],
   100   val empty = {add_mono_thms = [], mult_mono_thms = [], inj_thms = [],
   101                lessD = [], neqE = [], simpset = Simplifier.empty_ss};
   101                lessD = [], neqE = [], simpset = Simplifier.empty_ss};
   102   val copy = I;
   102   val copy = I;
   103   val prep_ext = I;
   103   val extend = I;
   104 
   104 
   105   fun merge ({add_mono_thms= add_mono_thms1, mult_mono_thms= mult_mono_thms1, inj_thms= inj_thms1,
   105   fun merge _
   106               lessD = lessD1, neqE=neqE1, simpset = simpset1},
   106     ({add_mono_thms= add_mono_thms1, mult_mono_thms= mult_mono_thms1, inj_thms= inj_thms1,
   107              {add_mono_thms= add_mono_thms2, mult_mono_thms= mult_mono_thms2, inj_thms= inj_thms2,
   107       lessD = lessD1, neqE=neqE1, simpset = simpset1},
   108               lessD = lessD2, neqE=neqE2, simpset = simpset2}) =
   108      {add_mono_thms= add_mono_thms2, mult_mono_thms= mult_mono_thms2, inj_thms= inj_thms2,
       
   109       lessD = lessD2, neqE=neqE2, simpset = simpset2}) =
   109     {add_mono_thms = Drule.merge_rules (add_mono_thms1, add_mono_thms2),
   110     {add_mono_thms = Drule.merge_rules (add_mono_thms1, add_mono_thms2),
   110      mult_mono_thms = Drule.merge_rules (mult_mono_thms1, mult_mono_thms2),
   111      mult_mono_thms = Drule.merge_rules (mult_mono_thms1, mult_mono_thms2),
   111      inj_thms = Drule.merge_rules (inj_thms1, inj_thms2),
   112      inj_thms = Drule.merge_rules (inj_thms1, inj_thms2),
   112      lessD = Drule.merge_rules (lessD1, lessD2),
   113      lessD = Drule.merge_rules (lessD1, lessD2),
   113      neqE = Drule.merge_rules (neqE1, neqE2),
   114      neqE = Drule.merge_rules (neqE1, neqE2),
   114      simpset = Simplifier.merge_ss (simpset1, simpset2)};
   115      simpset = Simplifier.merge_ss (simpset1, simpset2)};
   115 
   116 
   116   fun print _ _ = ();
   117   fun print _ _ = ();
   117 end;
   118 end);
   118 
   119 
   119 structure Data = TheoryDataFun(DataArgs);
       
   120 val map_data = Data.map;
   120 val map_data = Data.map;
   121 val setup = [Data.init];
   121 val setup = [Data.init];
   122 
   122 
   123 
   123 
   124 
   124 
   418 local
   418 local
   419  exception FalseE of thm
   419  exception FalseE of thm
   420 in
   420 in
   421 fun mkthm sg asms just =
   421 fun mkthm sg asms just =
   422   let val {add_mono_thms, mult_mono_thms, inj_thms, lessD, simpset, ...} =
   422   let val {add_mono_thms, mult_mono_thms, inj_thms, lessD, simpset, ...} =
   423           Data.get_sg sg;
   423           Data.get sg;
   424       val atoms = Library.foldl (fn (ats,(lhs,_,_,rhs,_,_)) =>
   424       val atoms = Library.foldl (fn (ats,(lhs,_,_,rhs,_,_)) =>
   425                             map fst lhs  union  (map fst rhs  union  ats))
   425                             map fst lhs  union  (map fst rhs  union  ats))
   426                         ([], List.mapPartial (fn thm => if Thm.no_prems thm
   426                         ([], List.mapPartial (fn thm => if Thm.no_prems thm
   427                                         then LA_Data.decomp sg (concl_of thm)
   427                                         then LA_Data.decomp sg (concl_of thm)
   428                                         else NONE) asms)
   428                                         else NONE) asms)
   623 fun refute sg ps ex items = refutes sg ps ex (split_items items) [];
   623 fun refute sg ps ex items = refutes sg ps ex (split_items items) [];
   624 
   624 
   625 fun refute_tac(i,justs) =
   625 fun refute_tac(i,justs) =
   626   fn state =>
   626   fn state =>
   627     let val sg = #sign(rep_thm state)
   627     let val sg = #sign(rep_thm state)
   628         val {neqE, ...} = Data.get_sg sg;
   628         val {neqE, ...} = Data.get sg;
   629         fun just1 j = REPEAT_DETERM(eresolve_tac neqE i) THEN
   629         fun just1 j = REPEAT_DETERM(eresolve_tac neqE i) THEN
   630                       METAHYPS (fn asms => rtac (mkthm sg asms j) 1) i
   630                       METAHYPS (fn asms => rtac (mkthm sg asms j) 1) i
   631     in DETERM(resolve_tac [LA_Logic.notI,LA_Logic.ccontr] i) THEN
   631     in DETERM(resolve_tac [LA_Logic.notI,LA_Logic.ccontr] i) THEN
   632        EVERY(map just1 justs)
   632        EVERY(map just1 justs)
   633     end
   633     end
   689     val (Ict2,_) = Thm.dest_comb Ict2r
   689     val (Ict2,_) = Thm.dest_comb Ict2r
   690     val (_,ct2) = Thm.dest_comb Ict2
   690     val (_,ct2) = Thm.dest_comb Ict2
   691 in (ct1,ct2) end;
   691 in (ct1,ct2) end;
   692 
   692 
   693 fun splitasms sg asms =
   693 fun splitasms sg asms =
   694 let val {neqE, ...}  = Data.get_sg sg;
   694 let val {neqE, ...}  = Data.get sg;
   695     fun split(asms',[]) = Tip(rev asms')
   695     fun split(asms',[]) = Tip(rev asms')
   696       | split(asms',asm::asms) =
   696       | split(asms',asm::asms) =
   697       (case get_first (fn th => SOME(asm COMP th) handle THM _ => NONE) neqE
   697       (case get_first (fn th => SOME(asm COMP th) handle THM _ => NONE) neqE
   698        of SOME spl =>
   698        of SOME spl =>
   699           let val (ct1,ct2) = extract(cprop_of spl)
   699           let val (ct1,ct2) = extract(cprop_of spl)