src/HOL/Tools/Qelim/cooper.ML
author wenzelm
Sat Aug 16 14:32:26 2014 +0200 (2014-08-16)
changeset 57952 1a9a6dfc255f
parent 57514 bdc2c6b40bf2
child 57955 f28337c2c0a8
permissions -rw-r--r--
updated to named_theorems;
     1 (*  Title:      HOL/Tools/Qelim/cooper.ML
     2     Author:     Amine Chaieb, TU Muenchen
     3 
     4 Presburger arithmetic by Cooper's algorithm.
     5 *)
     6 
     7 signature COOPER =
     8 sig
     9   type entry
    10   val get: Proof.context -> entry
    11   val del: term list -> attribute
    12   val add: term list -> attribute 
    13   exception COOPER of string
    14   val conv: Proof.context -> conv
    15   val tac: bool -> thm list -> thm list -> Proof.context -> int -> tactic
    16   val setup: theory -> theory
    17 end;
    18 
    19 structure Cooper: COOPER =
    20 struct
    21 
    22 type entry = simpset * term list;
    23 
    24 val allowed_consts = 
    25   [@{term "op + :: int => _"}, @{term "op + :: nat => _"},
    26    @{term "op - :: int => _"}, @{term "op - :: nat => _"},
    27    @{term "op * :: int => _"}, @{term "op * :: nat => _"},
    28    @{term "op div :: int => _"}, @{term "op div :: nat => _"},
    29    @{term "op mod :: int => _"}, @{term "op mod :: nat => _"},
    30    @{term HOL.conj}, @{term HOL.disj}, @{term HOL.implies}, 
    31    @{term "op = :: int => _"}, @{term "op = :: nat => _"}, @{term "op = :: bool => _"},
    32    @{term "op < :: int => _"}, @{term "op < :: nat => _"},
    33    @{term "op <= :: int => _"}, @{term "op <= :: nat => _"},
    34    @{term "op dvd :: int => _"}, @{term "op dvd :: nat => _"},
    35    @{term "abs :: int => _"},
    36    @{term "max :: int => _"}, @{term "max :: nat => _"},
    37    @{term "min :: int => _"}, @{term "min :: nat => _"},
    38    @{term "uminus :: int => _"}, (*@ {term "uminus :: nat => _"},*)
    39    @{term "Not"}, @{term Suc},
    40    @{term "Ex :: (int => _) => _"}, @{term "Ex :: (nat => _) => _"},
    41    @{term "All :: (int => _) => _"}, @{term "All :: (nat => _) => _"},
    42    @{term "nat"}, @{term "int"},
    43    @{term "Num.One"}, @{term "Num.Bit0"}, @{term "Num.Bit1"},
    44    @{term "Num.numeral :: num => int"}, @{term "Num.numeral :: num => nat"},
    45    @{term "0::int"}, @{term "1::int"}, @{term "0::nat"}, @{term "1::nat"},
    46    @{term "True"}, @{term "False"}];
    47 
    48 structure Data = Generic_Data
    49 (
    50   type T = simpset * term list;
    51   val empty = (HOL_ss, allowed_consts);
    52   val extend = I;
    53   fun merge ((ss1, ts1), (ss2, ts2)) =
    54     (merge_ss (ss1, ss2), Library.merge (op aconv) (ts1, ts2));
    55 );
    56 
    57 val get = Data.get o Context.Proof;
    58 
    59 fun add ts = Thm.declaration_attribute (fn th => fn context => 
    60   context |> Data.map (fn (ss, ts') =>
    61      (simpset_map (Context.proof_of context) (fn ctxt => ctxt addsimps [th]) ss,
    62       merge (op aconv) (ts', ts))))
    63 
    64 fun del ts = Thm.declaration_attribute (fn th => fn context => 
    65   context |> Data.map (fn (ss, ts') =>
    66      (simpset_map (Context.proof_of context) (fn ctxt => ctxt delsimps [th]) ss,
    67       subtract (op aconv) ts' ts)))
    68 
    69 fun simp_thms_conv ctxt =
    70   Simplifier.rewrite (put_simpset HOL_basic_ss ctxt addsimps @{thms simp_thms});
    71 val FWD = Drule.implies_elim_list;
    72 
    73 val true_tm = @{cterm "True"};
    74 val false_tm = @{cterm "False"};
    75 val zdvd1_eq = @{thm "zdvd1_eq"};
    76 val presburger_ss = simpset_of (@{context} addsimps [zdvd1_eq]);
    77 val lin_ss =
    78   simpset_of (put_simpset presburger_ss @{context}
    79     addsimps (@{thm dvd_eq_mod_eq_0} :: zdvd1_eq :: @{thms ac_simps [where 'a=int]}));
    80 
    81 val iT = HOLogic.intT
    82 val bT = HOLogic.boolT;
    83 val dest_number = HOLogic.dest_number #> snd;
    84 val perhaps_number = try dest_number;
    85 val is_number = can dest_number;
    86 
    87 val [miconj, midisj, mieq, mineq, milt, mile, migt, mige, midvd, mindvd, miP] =
    88     map(instantiate' [SOME @{ctyp "int"}] []) @{thms "minf"};
    89 
    90 val [infDconj, infDdisj, infDdvd,infDndvd,infDP] =
    91     map(instantiate' [SOME @{ctyp "int"}] []) @{thms "inf_period"};
    92 
    93 val [piconj, pidisj, pieq,pineq,pilt,pile,pigt,pige,pidvd,pindvd,piP] =
    94     map (instantiate' [SOME @{ctyp "int"}] []) @{thms "pinf"};
    95 
    96 val [miP, piP] = map (instantiate' [SOME @{ctyp "bool"}] []) [miP, piP];
    97 
    98 val infDP = instantiate' (map SOME [@{ctyp "int"}, @{ctyp "bool"}]) [] infDP;
    99 
   100 val [[asetconj, asetdisj, aseteq, asetneq, asetlt, asetle,
   101       asetgt, asetge, asetdvd, asetndvd,asetP],
   102      [bsetconj, bsetdisj, bseteq, bsetneq, bsetlt, bsetle,
   103       bsetgt, bsetge, bsetdvd, bsetndvd,bsetP]]  = [@{thms "aset"}, @{thms "bset"}];
   104 
   105 val [cpmi, cppi] = [@{thm "cpmi"}, @{thm "cppi"}];
   106 
   107 val unity_coeff_ex = instantiate' [SOME @{ctyp "int"}] [] @{thm "unity_coeff_ex"};
   108 
   109 val [zdvd_mono,simp_from_to,all_not_ex] =
   110      [@{thm "zdvd_mono"}, @{thm "simp_from_to"}, @{thm "all_not_ex"}];
   111 
   112 val [dvd_uminus, dvd_uminus'] = @{thms "uminus_dvd_conv"};
   113 
   114 val eval_ss =
   115   simpset_of (put_simpset presburger_ss @{context}
   116     addsimps [simp_from_to] delsimps [insert_iff, bex_triv]);
   117 fun eval_conv ctxt = Simplifier.rewrite (put_simpset eval_ss ctxt);
   118 
   119 (* recognising cterm without moving to terms *)
   120 
   121 datatype fm = And of cterm*cterm| Or of cterm*cterm| Eq of cterm | NEq of cterm
   122             | Lt of cterm | Le of cterm | Gt of cterm | Ge of cterm
   123             | Dvd of cterm*cterm | NDvd of cterm*cterm | Nox
   124 
   125 fun whatis x ct =
   126 ( case (term_of ct) of
   127   Const(@{const_name HOL.conj},_)$_$_ => And (Thm.dest_binop ct)
   128 | Const (@{const_name HOL.disj},_)$_$_ => Or (Thm.dest_binop ct)
   129 | Const (@{const_name HOL.eq},_)$y$_ => if term_of x aconv y then Eq (Thm.dest_arg ct) else Nox
   130 | Const (@{const_name Not},_) $ (Const (@{const_name HOL.eq},_)$y$_) =>
   131   if term_of x aconv y then NEq (funpow 2 Thm.dest_arg ct) else Nox
   132 | Const (@{const_name Orderings.less}, _) $ y$ z =>
   133    if term_of x aconv y then Lt (Thm.dest_arg ct)
   134    else if term_of x aconv z then Gt (Thm.dest_arg1 ct) else Nox
   135 | Const (@{const_name Orderings.less_eq}, _) $ y $ z =>
   136    if term_of x aconv y then Le (Thm.dest_arg ct)
   137    else if term_of x aconv z then Ge (Thm.dest_arg1 ct) else Nox
   138 | Const (@{const_name Rings.dvd},_)$_$(Const(@{const_name Groups.plus},_)$y$_) =>
   139    if term_of x aconv y then Dvd (Thm.dest_binop ct ||> Thm.dest_arg) else Nox
   140 | Const (@{const_name Not},_) $ (Const (@{const_name Rings.dvd},_)$_$(Const(@{const_name Groups.plus},_)$y$_)) =>
   141    if term_of x aconv y then
   142    NDvd (Thm.dest_binop (Thm.dest_arg ct) ||> Thm.dest_arg) else Nox
   143 | _ => Nox)
   144   handle CTERM _ => Nox;
   145 
   146 fun get_pmi_term t =
   147   let val (x,eq) =
   148      (Thm.dest_abs NONE o Thm.dest_arg o snd o Thm.dest_abs NONE o Thm.dest_arg)
   149         (Thm.dest_arg t)
   150 in (Thm.lambda x o Thm.dest_arg o Thm.dest_arg) eq end;
   151 
   152 val get_pmi = get_pmi_term o cprop_of;
   153 
   154 val p_v' = @{cpat "?P' :: int => bool"};
   155 val q_v' = @{cpat "?Q' :: int => bool"};
   156 val p_v = @{cpat "?P:: int => bool"};
   157 val q_v = @{cpat "?Q:: int => bool"};
   158 
   159 fun myfwd (th1, th2, th3) p q
   160       [(th_1,th_2,th_3), (th_1',th_2',th_3')] =
   161   let
   162    val (mp', mq') = (get_pmi th_1, get_pmi th_1')
   163    val mi_th = FWD (Drule.instantiate_normalize ([],[(p_v,p),(q_v,q), (p_v',mp'),(q_v',mq')]) th1)
   164                    [th_1, th_1']
   165    val infD_th = FWD (Drule.instantiate_normalize ([],[(p_v,mp'), (q_v, mq')]) th3) [th_3,th_3']
   166    val set_th = FWD (Drule.instantiate_normalize ([],[(p_v,p), (q_v,q)]) th2) [th_2, th_2']
   167   in (mi_th, set_th, infD_th)
   168   end;
   169 
   170 val inst' = fn cts => instantiate' [] (map SOME cts);
   171 val infDTrue = instantiate' [] [SOME true_tm] infDP;
   172 val infDFalse = instantiate' [] [SOME false_tm] infDP;
   173 
   174 val cadd =  @{cterm "op + :: int => _"}
   175 val cmulC =  @{cterm "op * :: int => _"}
   176 val cminus =  @{cterm "op - :: int => _"}
   177 val cone =  @{cterm "1 :: int"}
   178 val [addC, mulC, subC] = map term_of [cadd, cmulC, cminus]
   179 val [zero, one] = [@{term "0 :: int"}, @{term "1 :: int"}];
   180 
   181 fun numeral1 f n = HOLogic.mk_number iT (f (dest_number n));
   182 fun numeral2 f m n = HOLogic.mk_number iT (f (dest_number m) (dest_number n));
   183 
   184 val [minus1,plus1] =
   185     map (fn c => fn t => Thm.apply (Thm.apply c t) cone) [cminus,cadd];
   186 
   187 fun decomp_pinf x dvd inS [aseteq, asetneq, asetlt, asetle,
   188                            asetgt, asetge,asetdvd,asetndvd,asetP,
   189                            infDdvd, infDndvd, asetconj,
   190                            asetdisj, infDconj, infDdisj] cp =
   191  case (whatis x cp) of
   192   And (p,q) => ([p,q], myfwd (piconj, asetconj, infDconj) (Thm.lambda x p) (Thm.lambda x q))
   193 | Or (p,q) => ([p,q], myfwd (pidisj, asetdisj, infDdisj) (Thm.lambda x p) (Thm.lambda x q))
   194 | Eq t => ([], K (inst' [t] pieq, FWD (inst' [t] aseteq) [inS (plus1 t)], infDFalse))
   195 | NEq t => ([], K (inst' [t] pineq, FWD (inst' [t] asetneq) [inS t], infDTrue))
   196 | Lt t => ([], K (inst' [t] pilt, FWD (inst' [t] asetlt) [inS t], infDFalse))
   197 | Le t => ([], K (inst' [t] pile, FWD (inst' [t] asetle) [inS (plus1 t)], infDFalse))
   198 | Gt t => ([], K (inst' [t] pigt, (inst' [t] asetgt), infDTrue))
   199 | Ge t => ([], K (inst' [t] pige, (inst' [t] asetge), infDTrue))
   200 | Dvd (d,s) =>
   201    ([],let val dd = dvd d
   202        in K (inst' [d,s] pidvd, FWD (inst' [d,s] asetdvd) [dd],FWD (inst' [d,s] infDdvd) [dd]) end)
   203 | NDvd(d,s) => ([],let val dd = dvd d
   204         in K (inst' [d,s] pindvd, FWD (inst' [d,s] asetndvd) [dd], FWD (inst' [d,s] infDndvd) [dd]) end)
   205 | _ => ([], K (inst' [cp] piP, inst' [cp] asetP, inst' [cp] infDP));
   206 
   207 fun decomp_minf x dvd inS [bseteq,bsetneq,bsetlt, bsetle, bsetgt,
   208                            bsetge,bsetdvd,bsetndvd,bsetP,
   209                            infDdvd, infDndvd, bsetconj,
   210                            bsetdisj, infDconj, infDdisj] cp =
   211  case (whatis x cp) of
   212   And (p,q) => ([p,q], myfwd (miconj, bsetconj, infDconj) (Thm.lambda x p) (Thm.lambda x q))
   213 | Or (p,q) => ([p,q], myfwd (midisj, bsetdisj, infDdisj) (Thm.lambda x p) (Thm.lambda x q))
   214 | Eq t => ([], K (inst' [t] mieq, FWD (inst' [t] bseteq) [inS (minus1 t)], infDFalse))
   215 | NEq t => ([], K (inst' [t] mineq, FWD (inst' [t] bsetneq) [inS t], infDTrue))
   216 | Lt t => ([], K (inst' [t] milt, (inst' [t] bsetlt), infDTrue))
   217 | Le t => ([], K (inst' [t] mile, (inst' [t] bsetle), infDTrue))
   218 | Gt t => ([], K (inst' [t] migt, FWD (inst' [t] bsetgt) [inS t], infDFalse))
   219 | Ge t => ([], K (inst' [t] mige,FWD (inst' [t] bsetge) [inS (minus1 t)], infDFalse))
   220 | Dvd (d,s) => ([],let val dd = dvd d
   221         in K (inst' [d,s] midvd, FWD (inst' [d,s] bsetdvd) [dd] , FWD (inst' [d,s] infDdvd) [dd]) end)
   222 | NDvd (d,s) => ([],let val dd = dvd d
   223         in K (inst' [d,s] mindvd, FWD (inst' [d,s] bsetndvd) [dd], FWD (inst' [d,s] infDndvd) [dd]) end)
   224 | _ => ([], K (inst' [cp] miP, inst' [cp] bsetP, inst' [cp] infDP))
   225 
   226     (* Canonical linear form for terms, formulae etc.. *)
   227 fun provelin ctxt t = Goal.prove ctxt [] [] t
   228   (fn _ => EVERY [simp_tac (put_simpset lin_ss ctxt) 1, TRY (Lin_Arith.tac ctxt 1)]);
   229 fun linear_cmul 0 tm = zero
   230   | linear_cmul n tm = case tm of
   231       Const (@{const_name Groups.plus}, _) $ a $ b => addC $ linear_cmul n a $ linear_cmul n b
   232     | Const (@{const_name Groups.times}, _) $ c $ x => mulC $ numeral1 (fn m => n * m) c $ x
   233     | Const (@{const_name Groups.minus}, _) $ a $ b => subC $ linear_cmul n a $ linear_cmul n b
   234     | (m as Const (@{const_name Groups.uminus}, _)) $ a => m $ linear_cmul n a
   235     | _ => numeral1 (fn m => n * m) tm;
   236 fun earlier [] x y = false
   237   | earlier (h::t) x y =
   238     if h aconv y then false else if h aconv x then true else earlier t x y;
   239 
   240 fun linear_add vars tm1 tm2 = case (tm1, tm2) of
   241     (Const (@{const_name Groups.plus}, _) $ (Const (@{const_name Groups.times}, _) $ c1 $ x1) $ r1,
   242     Const (@{const_name Groups.plus}, _) $ (Const (@{const_name Groups.times}, _) $ c2 $ x2) $ r2) =>
   243    if x1 = x2 then
   244      let val c = numeral2 Integer.add c1 c2
   245       in if c = zero then linear_add vars r1 r2
   246          else addC$(mulC$c$x1)$(linear_add vars r1 r2)
   247      end
   248      else if earlier vars x1 x2 then addC $ (mulC $ c1 $ x1) $ linear_add vars r1 tm2
   249    else addC $ (mulC $ c2 $ x2) $ linear_add vars tm1 r2
   250  | (Const (@{const_name Groups.plus}, _) $ (Const (@{const_name Groups.times}, _) $ c1 $ x1) $ r1, _) =>
   251       addC $ (mulC $ c1 $ x1) $ linear_add vars r1 tm2
   252  | (_, Const (@{const_name Groups.plus}, _) $ (Const (@{const_name Groups.times}, _) $ c2 $ x2) $ r2) =>
   253       addC $ (mulC $ c2 $ x2) $ linear_add vars tm1 r2
   254  | (_, _) => numeral2 Integer.add tm1 tm2;
   255 
   256 fun linear_neg tm = linear_cmul ~1 tm;
   257 fun linear_sub vars tm1 tm2 = linear_add vars tm1 (linear_neg tm2);
   258 
   259 exception COOPER of string;
   260 
   261 fun lint vars tm =  if is_number tm then tm  else case tm of
   262   Const (@{const_name Groups.uminus}, _) $ t => linear_neg (lint vars t)
   263 | Const (@{const_name Groups.plus}, _) $ s $ t => linear_add vars (lint vars s) (lint vars t)
   264 | Const (@{const_name Groups.minus}, _) $ s $ t => linear_sub vars (lint vars s) (lint vars t)
   265 | Const (@{const_name Groups.times}, _) $ s $ t =>
   266   let val s' = lint vars s
   267       val t' = lint vars t
   268   in case perhaps_number s' of SOME n => linear_cmul n t'
   269    | NONE => (case perhaps_number t' of SOME n => linear_cmul n s'
   270    | NONE => raise COOPER "lint: not linear")
   271   end
   272  | _ => addC $ (mulC $ one $ tm) $ zero;
   273 
   274 fun lin (vs as _::_) (Const (@{const_name Not}, _) $ (Const (@{const_name Orderings.less}, T) $ s $ t)) =
   275     lin vs (Const (@{const_name Orderings.less_eq}, T) $ t $ s)
   276   | lin (vs as _::_) (Const (@{const_name Not},_) $ (Const(@{const_name Orderings.less_eq}, T) $ s $ t)) =
   277     lin vs (Const (@{const_name Orderings.less}, T) $ t $ s)
   278   | lin vs (Const (@{const_name Not},T)$t) = Const (@{const_name Not},T)$ (lin vs t)
   279   | lin (vs as _::_) (Const(@{const_name Rings.dvd},_)$d$t) =
   280     HOLogic.mk_binrel @{const_name Rings.dvd} (numeral1 abs d, lint vs t)
   281   | lin (vs as x::_) ((b as Const(@{const_name HOL.eq},_))$s$t) =
   282      (case lint vs (subC$t$s) of
   283       (t as _$(m$c$y)$r) =>
   284         if x <> y then b$zero$t
   285         else if dest_number c < 0 then b$(m$(numeral1 ~ c)$y)$r
   286         else b$(m$c$y)$(linear_neg r)
   287       | t => b$zero$t)
   288   | lin (vs as x::_) (b$s$t) =
   289      (case lint vs (subC$t$s) of
   290       (t as _$(m$c$y)$r) =>
   291         if x <> y then b$zero$t
   292         else if dest_number c < 0 then b$(m$(numeral1 ~ c)$y)$r
   293         else b$(linear_neg r)$(m$c$y)
   294       | t => b$zero$t)
   295   | lin vs fm = fm;
   296 
   297 fun lint_conv ctxt vs ct =
   298 let val t = term_of ct
   299 in (provelin ctxt ((HOLogic.eq_const iT)$t$(lint vs t) |> HOLogic.mk_Trueprop))
   300              RS eq_reflection
   301 end;
   302 
   303 fun is_intrel_type T = T = @{typ "int => int => bool"};
   304 
   305 fun is_intrel (b$_$_) = is_intrel_type (fastype_of b)
   306   | is_intrel (@{term "Not"}$(b$_$_)) = is_intrel_type (fastype_of b)
   307   | is_intrel _ = false;
   308 
   309 fun linearize_conv ctxt vs ct = case term_of ct of
   310   Const(@{const_name Rings.dvd},_)$_$_ =>
   311   let
   312     val th = Conv.binop_conv (lint_conv ctxt vs) ct
   313     val (d',t') = Thm.dest_binop (Thm.rhs_of th)
   314     val (dt',tt') = (term_of d', term_of t')
   315   in if is_number dt' andalso is_number tt'
   316      then Conv.fconv_rule (Conv.arg_conv (Simplifier.rewrite (put_simpset presburger_ss ctxt))) th
   317      else
   318      let
   319        val dth =
   320          case perhaps_number (term_of d') of
   321            SOME d => if d < 0 then
   322              (Conv.fconv_rule (Conv.arg_conv (Conv.arg1_conv (lint_conv ctxt vs)))
   323                               (Thm.transitive th (inst' [d',t'] dvd_uminus))
   324               handle TERM _ => th)
   325             else th
   326          | NONE => raise COOPER "linearize_conv: not linear"
   327       val d'' = Thm.rhs_of dth |> Thm.dest_arg1
   328      in
   329       case tt' of
   330         Const(@{const_name Groups.plus},_)$(Const(@{const_name Groups.times},_)$c$_)$_ =>
   331         let val x = dest_number c
   332         in if x < 0 then Conv.fconv_rule (Conv.arg_conv (Conv.arg_conv (lint_conv ctxt vs)))
   333                                        (Thm.transitive dth (inst' [d'',t'] dvd_uminus'))
   334         else dth end
   335       | _ => dth
   336      end
   337   end
   338 | Const (@{const_name Not},_)$(Const(@{const_name Rings.dvd},_)$_$_) => Conv.arg_conv (linearize_conv ctxt vs) ct
   339 | t => if is_intrel t
   340       then (provelin ctxt ((HOLogic.eq_const bT)$t$(lin vs t) |> HOLogic.mk_Trueprop))
   341        RS eq_reflection
   342       else Thm.reflexive ct;
   343 
   344 val dvdc = @{cterm "op dvd :: int => _"};
   345 
   346 fun unify ctxt q =
   347  let
   348   val (e,(cx,p)) = q |> Thm.dest_comb ||> Thm.dest_abs NONE
   349   val x = term_of cx
   350   val ins = insert (op = : int * int -> bool)
   351   fun h (acc,dacc) t =
   352    case (term_of t) of
   353     Const(s,_)$(Const(@{const_name Groups.times},_)$c$y)$ _ =>
   354     if x aconv y andalso member (op =)
   355       [@{const_name HOL.eq}, @{const_name Orderings.less}, @{const_name Orderings.less_eq}] s
   356     then (ins (dest_number c) acc,dacc) else (acc,dacc)
   357   | Const(s,_)$_$(Const(@{const_name Groups.times},_)$c$y) =>
   358     if x aconv y andalso member (op =)
   359        [@{const_name Orderings.less}, @{const_name Orderings.less_eq}] s
   360     then (ins (dest_number c) acc, dacc) else (acc,dacc)
   361   | Const(@{const_name Rings.dvd},_)$_$(Const(@{const_name Groups.plus},_)$(Const(@{const_name Groups.times},_)$c$y)$_) =>
   362     if x aconv y then (acc,ins (dest_number c) dacc) else (acc,dacc)
   363   | Const(@{const_name HOL.conj},_)$_$_ => h (h (acc,dacc) (Thm.dest_arg1 t)) (Thm.dest_arg t)
   364   | Const(@{const_name HOL.disj},_)$_$_ => h (h (acc,dacc) (Thm.dest_arg1 t)) (Thm.dest_arg t)
   365   | Const (@{const_name Not},_)$_ => h (acc,dacc) (Thm.dest_arg t)
   366   | _ => (acc, dacc)
   367   val (cs,ds) = h ([],[]) p
   368   val l = Integer.lcms (union (op =) cs ds)
   369   fun cv k ct =
   370     let val (tm as b$s$t) = term_of ct
   371     in ((HOLogic.eq_const bT)$tm$(b$(linear_cmul k s)$(linear_cmul k t))
   372          |> HOLogic.mk_Trueprop |> provelin ctxt) RS eq_reflection end
   373   fun nzprop x =
   374    let
   375     val th =
   376      Simplifier.rewrite (put_simpset lin_ss ctxt)
   377       (Thm.apply @{cterm Trueprop} (Thm.apply @{cterm "Not"}
   378            (Thm.apply (Thm.apply @{cterm "op = :: int => _"} (Numeral.mk_cnumber @{ctyp "int"} x))
   379            @{cterm "0::int"})))
   380    in Thm.equal_elim (Thm.symmetric th) TrueI end;
   381   val notz =
   382     let val tab = fold Inttab.update
   383           (ds ~~ (map (fn x => nzprop (l div x)) ds)) Inttab.empty
   384     in
   385       fn ct => the (Inttab.lookup tab (ct |> term_of |> dest_number))
   386         handle Option.Option =>
   387           (writeln ("noz: Theorems-Table contains no entry for " ^
   388               Syntax.string_of_term ctxt (Thm.term_of ct)); raise Option.Option)
   389     end
   390   fun unit_conv t =
   391    case (term_of t) of
   392    Const(@{const_name HOL.conj},_)$_$_ => Conv.binop_conv unit_conv t
   393   | Const(@{const_name HOL.disj},_)$_$_ => Conv.binop_conv unit_conv t
   394   | Const (@{const_name Not},_)$_ => Conv.arg_conv unit_conv t
   395   | Const(s,_)$(Const(@{const_name Groups.times},_)$c$y)$ _ =>
   396     if x=y andalso member (op =)
   397       [@{const_name HOL.eq}, @{const_name Orderings.less}, @{const_name Orderings.less_eq}] s
   398     then cv (l div dest_number c) t else Thm.reflexive t
   399   | Const(s,_)$_$(Const(@{const_name Groups.times},_)$c$y) =>
   400     if x=y andalso member (op =)
   401       [@{const_name Orderings.less}, @{const_name Orderings.less_eq}] s
   402     then cv (l div dest_number c) t else Thm.reflexive t
   403   | Const(@{const_name Rings.dvd},_)$d$(r as (Const(@{const_name Groups.plus},_)$(Const(@{const_name Groups.times},_)$c$y)$_)) =>
   404     if x=y then
   405       let
   406        val k = l div dest_number c
   407        val kt = HOLogic.mk_number iT k
   408        val th1 = inst' [Thm.dest_arg1 t, Thm.dest_arg t]
   409              ((Thm.dest_arg t |> funpow 2 Thm.dest_arg1 |> notz) RS zdvd_mono)
   410        val (d',t') = (mulC$kt$d, mulC$kt$r)
   411        val thc = (provelin ctxt ((HOLogic.eq_const iT)$d'$(lint [] d') |> HOLogic.mk_Trueprop))
   412                    RS eq_reflection
   413        val tht = (provelin ctxt ((HOLogic.eq_const iT)$t'$(linear_cmul k r) |> HOLogic.mk_Trueprop))
   414                  RS eq_reflection
   415       in Thm.transitive th1 (Thm.combination (Drule.arg_cong_rule dvdc thc) tht) end
   416     else Thm.reflexive t
   417   | _ => Thm.reflexive t
   418   val uth = unit_conv p
   419   val clt =  Numeral.mk_cnumber @{ctyp "int"} l
   420   val ltx = Thm.apply (Thm.apply cmulC clt) cx
   421   val th = Drule.arg_cong_rule e (Thm.abstract_rule (fst (dest_Free x )) cx uth)
   422   val th' = inst' [Thm.lambda ltx (Thm.rhs_of uth), clt] unity_coeff_ex
   423   val thf = Thm.transitive th
   424       (Thm.transitive (Thm.symmetric (Thm.beta_conversion true (cprop_of th' |> Thm.dest_arg1))) th')
   425   val (lth,rth) = Thm.dest_comb (cprop_of thf) |>> Thm.dest_arg |>> Thm.beta_conversion true
   426                   ||> Thm.beta_conversion true |>> Thm.symmetric
   427  in Thm.transitive (Thm.transitive lth thf) rth end;
   428 
   429 
   430 val emptyIS = @{cterm "{}::int set"};
   431 val insert_tm = @{cterm "insert :: int => _"};
   432 fun mkISet cts = fold_rev (Thm.apply insert_tm #> Thm.apply) cts emptyIS;
   433 val eqelem_imp_imp = @{thm eqelem_imp_iff} RS iffD1;
   434 val [A_tm,B_tm] = map (fn th => cprop_of th |> funpow 2 Thm.dest_arg |> Thm.dest_abs NONE |> snd |> Thm.dest_arg1 |> Thm.dest_arg
   435                                       |> Thm.dest_abs NONE |> snd |> Thm.dest_fun |> Thm.dest_arg)
   436                       [asetP,bsetP];
   437 
   438 val D_tm = @{cpat "?D::int"};
   439 
   440 fun cooperex_conv ctxt vs q =
   441 let
   442 
   443  val uth = unify ctxt q
   444  val (x,p) = Thm.dest_abs NONE (Thm.dest_arg (Thm.rhs_of uth))
   445  val ins = insert (op aconvc)
   446  fun h t (bacc,aacc,dacc) =
   447   case (whatis x t) of
   448     And (p,q) => h q (h p (bacc,aacc,dacc))
   449   | Or (p,q) => h q  (h p (bacc,aacc,dacc))
   450   | Eq t => (ins (minus1 t) bacc,
   451              ins (plus1 t) aacc,dacc)
   452   | NEq t => (ins t bacc,
   453               ins t aacc, dacc)
   454   | Lt t => (bacc, ins t aacc, dacc)
   455   | Le t => (bacc, ins (plus1 t) aacc,dacc)
   456   | Gt t => (ins t bacc, aacc,dacc)
   457   | Ge t => (ins (minus1 t) bacc, aacc,dacc)
   458   | Dvd (d,_) => (bacc,aacc,insert (op =) (term_of d |> dest_number) dacc)
   459   | NDvd (d,_) => (bacc,aacc,insert (op =) (term_of d|> dest_number) dacc)
   460   | _ => (bacc, aacc, dacc)
   461  val (b0,a0,ds) = h p ([],[],[])
   462  val d = Integer.lcms ds
   463  val cd = Numeral.mk_cnumber @{ctyp "int"} d
   464  fun divprop x =
   465    let
   466     val th =
   467      Simplifier.rewrite (put_simpset lin_ss ctxt)
   468       (Thm.apply @{cterm Trueprop}
   469            (Thm.apply (Thm.apply dvdc (Numeral.mk_cnumber @{ctyp "int"} x)) cd))
   470    in Thm.equal_elim (Thm.symmetric th) TrueI end;
   471  val dvd =
   472    let val tab = fold Inttab.update (ds ~~ (map divprop ds)) Inttab.empty in
   473      fn ct => the (Inttab.lookup tab (term_of ct |> dest_number))
   474        handle Option.Option =>
   475         (writeln ("dvd: Theorems-Table contains no entry for" ^
   476             Syntax.string_of_term ctxt (Thm.term_of ct)); raise Option.Option)
   477    end
   478  val dp =
   479    let val th = Simplifier.rewrite (put_simpset lin_ss ctxt)
   480       (Thm.apply @{cterm Trueprop}
   481            (Thm.apply (Thm.apply @{cterm "op < :: int => _"} @{cterm "0::int"}) cd))
   482    in Thm.equal_elim (Thm.symmetric th) TrueI end;
   483     (* A and B set *)
   484    local
   485      val insI1 = instantiate' [SOME @{ctyp "int"}] [] @{thm "insertI1"}
   486      val insI2 = instantiate' [SOME @{ctyp "int"}] [] @{thm "insertI2"}
   487    in
   488     fun provein x S =
   489      case term_of S of
   490         Const(@{const_name Orderings.bot}, _) => error "Unexpected error in Cooper, please email Amine Chaieb"
   491       | Const(@{const_name insert}, _) $ y $ _ =>
   492          let val (cy,S') = Thm.dest_binop S
   493          in if term_of x aconv y then instantiate' [] [SOME x, SOME S'] insI1
   494          else Thm.implies_elim (instantiate' [] [SOME x, SOME S', SOME cy] insI2)
   495                            (provein x S')
   496          end
   497    end
   498 
   499  val al = map (lint vs o term_of) a0
   500  val bl = map (lint vs o term_of) b0
   501  val (sl,s0,f,abths,cpth) =
   502    if length (distinct (op aconv) bl) <= length (distinct (op aconv) al)
   503    then
   504     (bl,b0,decomp_minf,
   505      fn B => (map (fn th => Thm.implies_elim (Thm.instantiate ([],[(B_tm,B), (D_tm,cd)]) th) dp)
   506                      [bseteq,bsetneq,bsetlt, bsetle, bsetgt,bsetge])@
   507                    (map (Thm.instantiate ([],[(B_tm,B), (D_tm,cd)]))
   508                         [bsetdvd,bsetndvd,bsetP,infDdvd, infDndvd,bsetconj,
   509                          bsetdisj,infDconj, infDdisj]),
   510                        cpmi)
   511      else (al,a0,decomp_pinf,fn A =>
   512           (map (fn th => Thm.implies_elim (Thm.instantiate ([],[(A_tm,A), (D_tm,cd)]) th) dp)
   513                    [aseteq,asetneq,asetlt, asetle, asetgt,asetge])@
   514                    (map (Thm.instantiate ([],[(A_tm,A), (D_tm,cd)]))
   515                    [asetdvd,asetndvd, asetP, infDdvd, infDndvd,asetconj,
   516                          asetdisj,infDconj, infDdisj]),cppi)
   517  val cpth =
   518   let
   519    val sths = map (fn (tl,t0) =>
   520                       if tl = term_of t0
   521                       then instantiate' [SOME @{ctyp "int"}] [SOME t0] refl
   522                       else provelin ctxt ((HOLogic.eq_const iT)$tl$(term_of t0)
   523                                  |> HOLogic.mk_Trueprop))
   524                    (sl ~~ s0)
   525    val csl = distinct (op aconvc) (map (cprop_of #> Thm.dest_arg #> Thm.dest_arg1) sths)
   526    val S = mkISet csl
   527    val inStab = fold (fn ct => fn tab => Termtab.update (term_of ct, provein ct S) tab)
   528                     csl Termtab.empty
   529    val eqelem_th = instantiate' [SOME @{ctyp "int"}] [NONE,NONE, SOME S] eqelem_imp_imp
   530    val inS =
   531      let
   532       val tab = fold Termtab.update
   533         (map (fn eq =>
   534                 let val (s,t) = cprop_of eq |> Thm.dest_arg |> Thm.dest_binop
   535                     val th = if term_of s = term_of t
   536                              then the (Termtab.lookup inStab (term_of s))
   537                              else FWD (instantiate' [] [SOME s, SOME t] eqelem_th)
   538                                 [eq, the (Termtab.lookup inStab (term_of s))]
   539                  in (term_of t, th) end)
   540                   sths) Termtab.empty
   541         in
   542           fn ct => the (Termtab.lookup tab (term_of ct))
   543             handle Option.Option =>
   544               (writeln ("inS: No theorem for " ^ Syntax.string_of_term ctxt (Thm.term_of ct));
   545                 raise Option.Option)
   546         end
   547        val (inf, nb, pd) = divide_and_conquer (f x dvd inS (abths S)) p
   548    in [dp, inf, nb, pd] MRS cpth
   549    end
   550  val cpth' = Thm.transitive uth (cpth RS eq_reflection)
   551 in Thm.transitive cpth' ((simp_thms_conv ctxt then_conv eval_conv ctxt) (Thm.rhs_of cpth'))
   552 end;
   553 
   554 fun literals_conv bops uops env cv =
   555  let fun h t =
   556   case (term_of t) of
   557    b$_$_ => if member (op aconv) bops b then Conv.binop_conv h t else cv env t
   558  | u$_ => if member (op aconv) uops u then Conv.arg_conv h t else cv env t
   559  | _ => cv env t
   560  in h end;
   561 
   562 fun integer_nnf_conv ctxt env =
   563   nnf_conv ctxt then_conv literals_conv [HOLogic.conj, HOLogic.disj] [] env (linearize_conv ctxt);
   564 
   565 val conv_ss =
   566   simpset_of (put_simpset HOL_basic_ss @{context}
   567     addsimps (@{thms simp_thms} @ take 4 @{thms ex_simps} @
   568       [not_all, all_not_ex, @{thm ex_disj_distrib}]));
   569 
   570 fun conv ctxt p =
   571   Qelim.gen_qelim_conv
   572     (Simplifier.rewrite (put_simpset conv_ss ctxt))
   573     (Simplifier.rewrite (put_simpset presburger_ss ctxt))
   574     (Simplifier.rewrite (put_simpset conv_ss ctxt))
   575     (cons o term_of) (Misc_Legacy.term_frees (term_of p))
   576     (linearize_conv ctxt) (integer_nnf_conv ctxt)
   577     (cooperex_conv ctxt) p
   578   handle CTERM _ => raise COOPER "bad cterm"
   579        | THM _ => raise COOPER "bad thm"
   580        | TYPE _ => raise COOPER "bad type"
   581 
   582 fun add_bools t =
   583   let
   584     val ops = [@{term "op = :: int => _"}, @{term "op < :: int => _"}, @{term "op <= :: int => _"},
   585       @{term HOL.conj}, @{term HOL.disj}, @{term HOL.implies}, @{term "op = :: bool => _"},
   586       @{term "Not"}, @{term "All :: (int => _) => _"},
   587       @{term "Ex :: (int => _) => _"}, @{term "True"}, @{term "False"}];
   588     val is_op = member (op =) ops;
   589     val skip = not (fastype_of t = HOLogic.boolT)
   590   in case t of
   591       (l as f $ a) $ b => if skip orelse is_op f then add_bools b o add_bools l
   592               else insert (op aconv) t
   593     | f $ a => if skip orelse is_op f then add_bools a o add_bools f
   594               else insert (op aconv) t
   595     | Abs p => add_bools (snd (Syntax_Trans.variant_abs p))  (* FIXME !? *)
   596     | _ => if skip orelse is_op t then I else insert (op aconv) t
   597   end;
   598 
   599 fun descend vs (abs as (_, xT, _)) =
   600   let
   601     val (xn', p') = Syntax_Trans.variant_abs abs;  (* FIXME !? *)
   602   in ((xn', xT) :: vs, p') end;
   603 
   604 local structure Proc = Cooper_Procedure in
   605 
   606 fun num_of_term vs (Free vT) = Proc.Bound (Proc.nat_of_integer (find_index (fn vT' => vT' = vT) vs))
   607   | num_of_term vs (Term.Bound i) = Proc.Bound (Proc.nat_of_integer i)
   608   | num_of_term vs @{term "0::int"} = Proc.C (Proc.Int_of_integer 0)
   609   | num_of_term vs @{term "1::int"} = Proc.C (Proc.Int_of_integer 1)
   610   | num_of_term vs (t as Const (@{const_name numeral}, _) $ _) =
   611       Proc.C (Proc.Int_of_integer (dest_number t))
   612   | num_of_term vs (Const (@{const_name Groups.uminus}, _) $ t') =
   613       Proc.Neg (num_of_term vs t')
   614   | num_of_term vs (Const (@{const_name Groups.plus}, _) $ t1 $ t2) =
   615       Proc.Add (num_of_term vs t1, num_of_term vs t2)
   616   | num_of_term vs (Const (@{const_name Groups.minus}, _) $ t1 $ t2) =
   617       Proc.Sub (num_of_term vs t1, num_of_term vs t2)
   618   | num_of_term vs (Const (@{const_name Groups.times}, _) $ t1 $ t2) =
   619      (case perhaps_number t1
   620        of SOME n => Proc.Mul (Proc.Int_of_integer n, num_of_term vs t2)
   621         | NONE => (case perhaps_number t2
   622            of SOME n => Proc.Mul (Proc.Int_of_integer n, num_of_term vs t1)
   623             | NONE => raise COOPER "reification: unsupported kind of multiplication"))
   624   | num_of_term _ _ = raise COOPER "reification: bad term";
   625 
   626 fun fm_of_term ps vs (Const (@{const_name True}, _)) = Proc.T
   627   | fm_of_term ps vs (Const (@{const_name False}, _)) = Proc.F
   628   | fm_of_term ps vs (Const (@{const_name HOL.conj}, _) $ t1 $ t2) =
   629       Proc.And (fm_of_term ps vs t1, fm_of_term ps vs t2)
   630   | fm_of_term ps vs (Const (@{const_name HOL.disj}, _) $ t1 $ t2) =
   631       Proc.Or (fm_of_term ps vs t1, fm_of_term ps vs t2)
   632   | fm_of_term ps vs (Const (@{const_name HOL.implies}, _) $ t1 $ t2) =
   633       Proc.Imp (fm_of_term ps vs t1, fm_of_term ps vs t2)
   634   | fm_of_term ps vs (@{term "op = :: bool => _ "} $ t1 $ t2) =
   635       Proc.Iff (fm_of_term ps vs t1, fm_of_term ps vs t2)
   636   | fm_of_term ps vs (Const (@{const_name Not}, _) $ t') =
   637       Proc.Not (fm_of_term ps vs t')
   638   | fm_of_term ps vs (Const (@{const_name Ex}, _) $ Abs abs) =
   639       Proc.E (uncurry (fm_of_term ps) (descend vs abs))
   640   | fm_of_term ps vs (Const (@{const_name All}, _) $ Abs abs) =
   641       Proc.A (uncurry (fm_of_term ps) (descend vs abs))
   642   | fm_of_term ps vs (@{term "op = :: int => _"} $ t1 $ t2) =
   643       Proc.Eq (Proc.Sub (num_of_term vs t1, num_of_term vs t2))
   644   | fm_of_term ps vs (Const (@{const_name Orderings.less_eq}, _) $ t1 $ t2) =
   645       Proc.Le (Proc.Sub (num_of_term vs t1, num_of_term vs t2))
   646   | fm_of_term ps vs (Const (@{const_name Orderings.less}, _) $ t1 $ t2) =
   647       Proc.Lt (Proc.Sub (num_of_term vs t1, num_of_term vs t2))
   648   | fm_of_term ps vs (Const (@{const_name Rings.dvd}, _) $ t1 $ t2) =
   649      (case perhaps_number t1
   650        of SOME n => Proc.Dvd (Proc.Int_of_integer n, num_of_term vs t2)
   651         | NONE => raise COOPER "reification: unsupported dvd")
   652   | fm_of_term ps vs t = let val n = find_index (fn t' => t aconv t') ps
   653       in if n > 0 then Proc.Closed (Proc.nat_of_integer n) else raise COOPER "reification: unknown term" end;
   654 
   655 fun term_of_num vs (Proc.C i) = HOLogic.mk_number HOLogic.intT (Proc.integer_of_int i)
   656   | term_of_num vs (Proc.Bound n) = Free (nth vs (Proc.integer_of_nat n))
   657   | term_of_num vs (Proc.Neg t') =
   658       @{term "uminus :: int => _"} $ term_of_num vs t'
   659   | term_of_num vs (Proc.Add (t1, t2)) =
   660       @{term "op + :: int => _"} $ term_of_num vs t1 $ term_of_num vs t2
   661   | term_of_num vs (Proc.Sub (t1, t2)) =
   662       @{term "op - :: int => _"} $ term_of_num vs t1 $ term_of_num vs t2
   663   | term_of_num vs (Proc.Mul (i, t2)) =
   664       @{term "op * :: int => _"} $ HOLogic.mk_number HOLogic.intT (Proc.integer_of_int i) $ term_of_num vs t2
   665   | term_of_num vs (Proc.Cn (n, i, t')) =
   666       term_of_num vs (Proc.Add (Proc.Mul (i, Proc.Bound n), t'));
   667 
   668 fun term_of_fm ps vs Proc.T = @{term True}
   669   | term_of_fm ps vs Proc.F = @{term False}
   670   | term_of_fm ps vs (Proc.And (t1, t2)) = HOLogic.conj $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
   671   | term_of_fm ps vs (Proc.Or (t1, t2)) = HOLogic.disj $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
   672   | term_of_fm ps vs (Proc.Imp (t1, t2)) = HOLogic.imp $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
   673   | term_of_fm ps vs (Proc.Iff (t1, t2)) = @{term "op = :: bool => _"} $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
   674   | term_of_fm ps vs (Proc.Not t') = HOLogic.Not $ term_of_fm ps vs t'
   675   | term_of_fm ps vs (Proc.Eq t') = @{term "op = :: int => _ "} $ term_of_num vs t'$ @{term "0::int"}
   676   | term_of_fm ps vs (Proc.NEq t') = term_of_fm ps vs (Proc.Not (Proc.Eq t'))
   677   | term_of_fm ps vs (Proc.Lt t') = @{term "op < :: int => _ "} $ term_of_num vs t' $ @{term "0::int"}
   678   | term_of_fm ps vs (Proc.Le t') = @{term "op <= :: int => _ "} $ term_of_num vs t' $ @{term "0::int"}
   679   | term_of_fm ps vs (Proc.Gt t') = @{term "op < :: int => _ "} $ @{term "0::int"} $ term_of_num vs t'
   680   | term_of_fm ps vs (Proc.Ge t') = @{term "op <= :: int => _ "} $ @{term "0::int"} $ term_of_num vs t'
   681   | term_of_fm ps vs (Proc.Dvd (i, t')) = @{term "op dvd :: int => _ "} $
   682       HOLogic.mk_number HOLogic.intT (Proc.integer_of_int i) $ term_of_num vs t'
   683   | term_of_fm ps vs (Proc.NDvd (i, t')) = term_of_fm ps vs (Proc.Not (Proc.Dvd (i, t')))
   684   | term_of_fm ps vs (Proc.Closed n) = nth ps (Proc.integer_of_nat n)
   685   | term_of_fm ps vs (Proc.NClosed n) = term_of_fm ps vs (Proc.Not (Proc.Closed n));
   686 
   687 fun procedure t =
   688   let
   689     val vs = Term.add_frees t [];
   690     val ps = add_bools t [];
   691   in (term_of_fm ps vs o Proc.pa o fm_of_term ps vs) t end;
   692 
   693 end;
   694 
   695 val (_, oracle) = Context.>>> (Context.map_theory_result
   696   (Thm.add_oracle (@{binding cooper},
   697     (fn (ctxt, t) =>
   698       (Thm.cterm_of (Proof_Context.theory_of ctxt) o Logic.mk_equals o pairself HOLogic.mk_Trueprop)
   699         (t, procedure t)))));
   700 
   701 val comp_ss =
   702   simpset_of (put_simpset HOL_ss @{context} addsimps @{thms semiring_norm});
   703 
   704 fun strip_objimp ct =
   705   (case Thm.term_of ct of
   706     Const (@{const_name HOL.implies}, _) $ _ $ _ =>
   707       let val (A, B) = Thm.dest_binop ct
   708       in A :: strip_objimp B end
   709   | _ => [ct]);
   710 
   711 fun strip_objall ct = 
   712  case term_of ct of 
   713   Const (@{const_name All}, _) $ Abs (xn,_,_) => 
   714    let val (a,(v,t')) = (apsnd (Thm.dest_abs (SOME xn)) o Thm.dest_comb) ct
   715    in apfst (cons (a,v)) (strip_objall t')
   716    end
   717 | _ => ([],ct);
   718 
   719 local
   720   val all_maxscope_ss =
   721     simpset_of (put_simpset HOL_basic_ss @{context}
   722       addsimps map (fn th => th RS sym) @{thms "all_simps"})
   723 in
   724 fun thin_prems_tac ctxt P =
   725   simp_tac (put_simpset all_maxscope_ss ctxt) THEN'
   726   CSUBGOAL (fn (p', i) =>
   727     let
   728      val (qvs, p) = strip_objall (Thm.dest_arg p')
   729      val (ps, c) = split_last (strip_objimp p)
   730      val qs = filter P ps
   731      val q = if P c then c else @{cterm "False"}
   732      val ng = fold_rev (fn (a,v) => fn t => Thm.apply a (Thm.lambda v t)) qvs 
   733          (fold_rev (fn p => fn q => Thm.apply (Thm.apply @{cterm HOL.implies} p) q) qs q)
   734      val g = Thm.apply (Thm.apply @{cterm "op ==>"} (Thm.apply @{cterm "Trueprop"} ng)) p'
   735      val ntac = (case qs of [] => q aconvc @{cterm "False"}
   736                          | _ => false)
   737     in 
   738       if ntac then no_tac
   739       else
   740         (case try (fn () =>
   741             Goal.prove_internal ctxt [] g (K (blast_tac (put_claset HOL_cs ctxt) 1))) () of
   742           NONE => no_tac
   743         | SOME r => rtac r i)
   744     end)
   745 end;
   746 
   747 local
   748  fun isnum t = case t of 
   749    Const(@{const_name Groups.zero},_) => true
   750  | Const(@{const_name Groups.one},_) => true
   751  | @{term Suc}$s => isnum s
   752  | @{term "nat"}$s => isnum s
   753  | @{term "int"}$s => isnum s
   754  | Const(@{const_name Groups.uminus},_)$s => isnum s
   755  | Const(@{const_name Groups.plus},_)$l$r => isnum l andalso isnum r
   756  | Const(@{const_name Groups.times},_)$l$r => isnum l andalso isnum r
   757  | Const(@{const_name Groups.minus},_)$l$r => isnum l andalso isnum r
   758  | Const(@{const_name Power.power},_)$l$r => isnum l andalso isnum r
   759  | Const(@{const_name Divides.mod},_)$l$r => isnum l andalso isnum r
   760  | Const(@{const_name Divides.div},_)$l$r => isnum l andalso isnum r
   761  | _ => is_number t orelse can HOLogic.dest_nat t
   762 
   763  fun ty cts t = 
   764  if not (member (op =) [HOLogic.intT, HOLogic.natT, HOLogic.boolT] (typ_of (ctyp_of_term t))) then false 
   765     else case term_of t of 
   766       c$l$r => if member (op =) [@{term"op *::int => _"}, @{term"op *::nat => _"}] c
   767                then not (isnum l orelse isnum r)
   768                else not (member (op aconv) cts c)
   769     | c$_ => not (member (op aconv) cts c)
   770     | c => not (member (op aconv) cts c)
   771 
   772  val term_constants =
   773   let fun h acc t = case t of
   774     Const _ => insert (op aconv) t acc
   775   | a$b => h (h acc a) b
   776   | Abs (_,_,t) => h acc t
   777   | _ => acc
   778  in h [] end;
   779 in 
   780 fun is_relevant ctxt ct = 
   781  subset (op aconv) (term_constants (term_of ct) , snd (get ctxt))
   782  andalso forall (fn Free (_,T) => member (op =) [@{typ int}, @{typ nat}] T) (Misc_Legacy.term_frees (term_of ct))
   783  andalso forall (fn Var (_,T) => member (op =) [@{typ int}, @{typ nat}] T) (Misc_Legacy.term_vars (term_of ct));
   784 
   785 fun int_nat_terms ctxt ct =
   786  let 
   787   val cts = snd (get ctxt)
   788   fun h acc t = if ty cts t then insert (op aconvc) t acc else
   789    case (term_of t) of
   790     _$_ => h (h acc (Thm.dest_arg t)) (Thm.dest_fun t)
   791   | Abs(_,_,_) => Thm.dest_abs NONE t ||> h acc |> uncurry (remove (op aconvc))
   792   | _ => acc
   793  in h [] ct end
   794 end;
   795 
   796 fun generalize_tac f = CSUBGOAL (fn (p, _) => PRIMITIVE (fn st =>
   797  let 
   798    fun all T = Drule.cterm_rule (instantiate' [SOME T] []) @{cpat "Pure.all"}
   799    fun gen x t = Thm.apply (all (ctyp_of_term x)) (Thm.lambda x t)
   800    val ts = sort (fn (a,b) => Term_Ord.fast_term_ord (term_of a, term_of b)) (f p)
   801    val p' = fold_rev gen ts p
   802  in Thm.implies_intr p' (Thm.implies_elim st (fold Thm.forall_elim ts (Thm.assume p'))) end));
   803 
   804 local
   805 val ss1 =
   806   simpset_of (put_simpset comp_ss @{context}
   807     addsimps @{thms simp_thms} @ [@{thm "nat_numeral"} RS sym, @{thm "zdvd_int"}] 
   808         @ map (fn r => r RS sym) 
   809           [@{thm "int_int_eq"}, @{thm "zle_int"}, @{thm "zless_int"}, @{thm "zadd_int"}, 
   810            @{thm "zmult_int"}]
   811     |> Splitter.add_split @{thm "zdiff_int_split"})
   812 
   813 val ss2 =
   814   simpset_of (put_simpset HOL_basic_ss @{context}
   815     addsimps [@{thm "nat_0_le"}, @{thm "int_numeral"},
   816               @{thm "all_nat"}, @{thm "ex_nat"}, @{thm "zero_le_numeral"}, 
   817               @{thm "le_numeral_extra"(3)}, @{thm "int_0"}, @{thm "int_1"}, @{thm "Suc_eq_plus1"}]
   818     |> fold Simplifier.add_cong [@{thm "conj_le_cong"}, @{thm "imp_le_cong"}])
   819 val div_mod_ss =
   820   simpset_of (put_simpset HOL_basic_ss @{context}
   821     addsimps @{thms simp_thms}
   822     @ map (Thm.symmetric o mk_meta_eq) 
   823       [@{thm "dvd_eq_mod_eq_0"},
   824        @{thm "mod_add_left_eq"}, @{thm "mod_add_right_eq"}, 
   825        @{thm "mod_add_eq"}, @{thm "div_add1_eq"}, @{thm "zdiv_zadd1_eq"}]
   826     @ [@{thm "mod_self"}, @{thm "mod_by_0"}, @{thm "div_by_0"},
   827        @{thm "div_0"}, @{thm "mod_0"}, @{thm "div_by_1"}, @{thm "mod_by_1"}, @{thm "div_1"}, 
   828        @{thm "mod_1"}, @{thm "Suc_eq_plus1"}]
   829     @ @{thms ac_simps}
   830    addsimprocs [@{simproc cancel_div_mod_nat}, @{simproc cancel_div_mod_int}])
   831 val splits_ss =
   832   simpset_of (put_simpset comp_ss @{context}
   833     addsimps [@{thm "mod_div_equality'"}]
   834     |> fold Splitter.add_split
   835       [@{thm "split_zdiv"}, @{thm "split_zmod"}, @{thm "split_div'"}, 
   836        @{thm "split_min"}, @{thm "split_max"}, @{thm "abs_split"}])
   837 in
   838 fun nat_to_int_tac ctxt = 
   839   simp_tac (put_simpset ss1 ctxt) THEN_ALL_NEW
   840   simp_tac (put_simpset ss2 ctxt) THEN_ALL_NEW
   841   simp_tac (put_simpset comp_ss ctxt);
   842 
   843 fun div_mod_tac ctxt = simp_tac (put_simpset div_mod_ss ctxt);
   844 fun splits_tac ctxt = simp_tac (put_simpset splits_ss ctxt);
   845 end;
   846 
   847 fun core_tac ctxt = CSUBGOAL (fn (p, i) =>
   848    let
   849     val cpth = 
   850        if Config.get ctxt quick_and_dirty
   851        then oracle (ctxt, Envir.beta_norm (Envir.eta_long [] (term_of (Thm.dest_arg p))))
   852        else Conv.arg_conv (conv ctxt) p
   853     val p' = Thm.rhs_of cpth
   854     val th = Thm.implies_intr p' (Thm.equal_elim (Thm.symmetric cpth) (Thm.assume p'))
   855    in rtac th i end
   856    handle COOPER _ => no_tac);
   857 
   858 fun finish_tac q = SUBGOAL (fn (_, i) =>
   859   (if q then I else TRY) (rtac TrueI i));
   860 
   861 fun tac elim add_ths del_ths = Subgoal.FOCUS_PARAMS (fn {context = ctxt, ...} =>
   862   let
   863     val simpset_ctxt =
   864       put_simpset (fst (get ctxt)) ctxt delsimps del_ths addsimps add_ths
   865   in
   866     Method.insert_tac (Named_Theorems.get ctxt @{named_theorems arith})
   867     THEN_ALL_NEW Object_Logic.full_atomize_tac ctxt
   868     THEN_ALL_NEW CONVERSION Thm.eta_long_conversion
   869     THEN_ALL_NEW simp_tac simpset_ctxt
   870     THEN_ALL_NEW (TRY o generalize_tac (int_nat_terms ctxt))
   871     THEN_ALL_NEW Object_Logic.full_atomize_tac ctxt
   872     THEN_ALL_NEW (thin_prems_tac ctxt (is_relevant ctxt))
   873     THEN_ALL_NEW Object_Logic.full_atomize_tac ctxt
   874     THEN_ALL_NEW div_mod_tac ctxt
   875     THEN_ALL_NEW splits_tac ctxt
   876     THEN_ALL_NEW simp_tac simpset_ctxt
   877     THEN_ALL_NEW CONVERSION Thm.eta_long_conversion
   878     THEN_ALL_NEW nat_to_int_tac ctxt
   879     THEN_ALL_NEW core_tac ctxt
   880     THEN_ALL_NEW finish_tac elim
   881   end 1);
   882 
   883 
   884 (* theory setup *)
   885 
   886 local
   887 
   888 fun keyword k = Scan.lift (Args.$$$ k -- Args.colon) >> K ();
   889 
   890 val constsN = "consts";
   891 val any_keyword = keyword constsN
   892 val thms = Scan.repeat (Scan.unless any_keyword Attrib.multi_thm) >> flat;
   893 val terms = thms >> map (term_of o Drule.dest_term);
   894 
   895 fun optional scan = Scan.optional scan [];
   896 
   897 in
   898 
   899 val setup =
   900   Attrib.setup @{binding presburger}
   901     ((Scan.lift (Args.$$$ "del") |-- optional (keyword constsN |-- terms)) >> del ||
   902       optional (keyword constsN |-- terms) >> add) "data for Cooper's algorithm"
   903   #> Arith_Data.add_tactic "Presburger arithmetic" (K (tac true [] []));
   904 
   905 end;
   906 
   907 end;