nipkow@5982
|
1 |
(* Title: Provers/Arith/fast_lin_arith.ML
|
nipkow@5982
|
2 |
ID: $Id$
|
wenzelm@24076
|
3 |
Author: Tobias Nipkow and Tjark Weber
|
nipkow@5982
|
4 |
|
wenzelm@24076
|
5 |
A generic linear arithmetic package. It provides two tactics
|
wenzelm@24076
|
6 |
(cut_lin_arith_tac, lin_arith_tac) and a simplification procedure
|
wenzelm@24076
|
7 |
(lin_arith_simproc).
|
nipkow@6102
|
8 |
|
wenzelm@24076
|
9 |
Only take premises and conclusions into account that are already
|
wenzelm@24076
|
10 |
(negated) (in)equations. lin_arith_simproc tries to prove or disprove
|
wenzelm@24076
|
11 |
the term.
|
nipkow@5982
|
12 |
*)
|
nipkow@5982
|
13 |
|
paulson@9073
|
14 |
(* Debugging: set Fast_Arith.trace *)
|
nipkow@7582
|
15 |
|
nipkow@5982
|
16 |
(*** Data needed for setting up the linear arithmetic package ***)
|
nipkow@5982
|
17 |
|
nipkow@6102
|
18 |
signature LIN_ARITH_LOGIC =
|
nipkow@6102
|
19 |
sig
|
webertj@20276
|
20 |
val conjI : thm (* P ==> Q ==> P & Q *)
|
webertj@20276
|
21 |
val ccontr : thm (* (~ P ==> False) ==> P *)
|
webertj@20276
|
22 |
val notI : thm (* (P ==> False) ==> ~ P *)
|
webertj@20276
|
23 |
val not_lessD : thm (* ~(m < n) ==> n <= m *)
|
webertj@20276
|
24 |
val not_leD : thm (* ~(m <= n) ==> n < m *)
|
webertj@20276
|
25 |
val sym : thm (* x = y ==> y = x *)
|
webertj@20276
|
26 |
val mk_Eq : thm -> thm
|
webertj@20276
|
27 |
val atomize : thm -> thm list
|
webertj@20276
|
28 |
val mk_Trueprop : term -> term
|
webertj@20276
|
29 |
val neg_prop : term -> term
|
webertj@20276
|
30 |
val is_False : thm -> bool
|
webertj@20276
|
31 |
val is_nat : typ list * term -> bool
|
webertj@20276
|
32 |
val mk_nat_thm : theory -> term -> thm
|
nipkow@6102
|
33 |
end;
|
nipkow@6102
|
34 |
(*
|
nipkow@6102
|
35 |
mk_Eq(~in) = `in == False'
|
nipkow@6102
|
36 |
mk_Eq(in) = `in == True'
|
nipkow@6102
|
37 |
where `in' is an (in)equality.
|
nipkow@6102
|
38 |
|
webertj@23190
|
39 |
neg_prop(t) = neg if t is wrapped up in Trueprop and neg is the
|
webertj@23190
|
40 |
(logically) negated version of t (again wrapped up in Trueprop),
|
webertj@23190
|
41 |
where the negation of a negative term is the term itself (no
|
webertj@23190
|
42 |
double negation!); raises TERM ("neg_prop", [t]) if t is not of
|
webertj@23190
|
43 |
the form 'Trueprop $ _'
|
nipkow@6128
|
44 |
|
nipkow@6128
|
45 |
is_nat(parameter-types,t) = t:nat
|
nipkow@6128
|
46 |
mk_nat_thm(t) = "0 <= t"
|
nipkow@6102
|
47 |
*)
|
nipkow@6102
|
48 |
|
nipkow@5982
|
49 |
signature LIN_ARITH_DATA =
|
nipkow@5982
|
50 |
sig
|
wenzelm@24076
|
51 |
(*internal representation of linear (in-)equations:*)
|
webertj@20268
|
52 |
type decompT = (term * Rat.rat) list * Rat.rat * string * (term * Rat.rat) list * Rat.rat * bool
|
wenzelm@24076
|
53 |
val decomp: Proof.context -> term -> decompT option
|
wenzelm@24076
|
54 |
val domain_is_nat: term -> bool
|
wenzelm@24076
|
55 |
|
wenzelm@24076
|
56 |
(*preprocessing, performed on a representation of subgoals as list of premises:*)
|
wenzelm@24076
|
57 |
val pre_decomp: Proof.context -> typ list * term list -> (typ list * term list) list
|
wenzelm@24076
|
58 |
|
wenzelm@24076
|
59 |
(*preprocessing, performed on the goal -- must do the same as 'pre_decomp':*)
|
wenzelm@24076
|
60 |
val pre_tac: Proof.context -> int -> tactic
|
wenzelm@24076
|
61 |
val number_of: IntInf.int * typ -> term
|
wenzelm@24076
|
62 |
|
wenzelm@24076
|
63 |
(*the limit on the number of ~= allowed; because each ~= is split
|
wenzelm@24076
|
64 |
into two cases, this can lead to an explosion*)
|
wenzelm@24112
|
65 |
val fast_arith_neq_limit: int Config.T
|
nipkow@5982
|
66 |
end;
|
nipkow@5982
|
67 |
(*
|
nipkow@7551
|
68 |
decomp(`x Rel y') should yield (p,i,Rel,q,j,d)
|
nipkow@5982
|
69 |
where Rel is one of "<", "~<", "<=", "~<=" and "=" and
|
webertj@20217
|
70 |
p (q, respectively) is the decomposition of the sum term x
|
webertj@20217
|
71 |
(y, respectively) into a list of summand * multiplicity
|
webertj@20217
|
72 |
pairs and a constant summand and d indicates if the domain
|
webertj@20217
|
73 |
is discrete.
|
webertj@20217
|
74 |
|
webertj@20276
|
75 |
domain_is_nat(`x Rel y') t should yield true iff x is of type "nat".
|
webertj@20276
|
76 |
|
webertj@20217
|
77 |
The relationship between pre_decomp and pre_tac is somewhat tricky. The
|
webertj@20217
|
78 |
internal representation of a subgoal and the corresponding theorem must
|
webertj@20217
|
79 |
be modified by pre_decomp (pre_tac, resp.) in a corresponding way. See
|
webertj@20217
|
80 |
the comment for split_items below. (This is even necessary for eta- and
|
webertj@20217
|
81 |
beta-equivalent modifications, as some of the lin. arith. code is not
|
webertj@20217
|
82 |
insensitive to them.)
|
nipkow@5982
|
83 |
|
wenzelm@9420
|
84 |
ss must reduce contradictory <= to False.
|
nipkow@5982
|
85 |
It should also cancel common summands to keep <= reduced;
|
nipkow@5982
|
86 |
otherwise <= can grow to massive proportions.
|
nipkow@5982
|
87 |
*)
|
nipkow@5982
|
88 |
|
nipkow@6062
|
89 |
signature FAST_LIN_ARITH =
|
nipkow@6062
|
90 |
sig
|
nipkow@15184
|
91 |
val map_data: ({add_mono_thms: thm list, mult_mono_thms: thm list, inj_thms: thm list,
|
nipkow@15922
|
92 |
lessD: thm list, neqE: thm list, simpset: Simplifier.simpset}
|
nipkow@15184
|
93 |
-> {add_mono_thms: thm list, mult_mono_thms: thm list, inj_thms: thm list,
|
nipkow@15922
|
94 |
lessD: thm list, neqE: thm list, simpset: Simplifier.simpset})
|
wenzelm@24076
|
95 |
-> Context.generic -> Context.generic
|
webertj@19314
|
96 |
val trace: bool ref
|
wenzelm@17613
|
97 |
val cut_lin_arith_tac: simpset -> int -> tactic
|
wenzelm@24076
|
98 |
val lin_arith_tac: Proof.context -> bool -> int -> tactic
|
wenzelm@24076
|
99 |
val lin_arith_simproc: simpset -> term -> thm option
|
nipkow@6062
|
100 |
end;
|
nipkow@6062
|
101 |
|
wenzelm@24076
|
102 |
functor Fast_Lin_Arith
|
wenzelm@24076
|
103 |
(structure LA_Logic: LIN_ARITH_LOGIC and LA_Data: LIN_ARITH_DATA): FAST_LIN_ARITH =
|
nipkow@5982
|
104 |
struct
|
nipkow@5982
|
105 |
|
wenzelm@9420
|
106 |
|
wenzelm@9420
|
107 |
(** theory data **)
|
wenzelm@9420
|
108 |
|
wenzelm@24076
|
109 |
structure Data = GenericDataFun
|
wenzelm@22846
|
110 |
(
|
wenzelm@24076
|
111 |
type T =
|
wenzelm@24076
|
112 |
{add_mono_thms: thm list,
|
wenzelm@24076
|
113 |
mult_mono_thms: thm list,
|
wenzelm@24076
|
114 |
inj_thms: thm list,
|
wenzelm@24076
|
115 |
lessD: thm list,
|
wenzelm@24076
|
116 |
neqE: thm list,
|
wenzelm@24076
|
117 |
simpset: Simplifier.simpset};
|
wenzelm@9420
|
118 |
|
nipkow@10691
|
119 |
val empty = {add_mono_thms = [], mult_mono_thms = [], inj_thms = [],
|
nipkow@15922
|
120 |
lessD = [], neqE = [], simpset = Simplifier.empty_ss};
|
wenzelm@16458
|
121 |
val extend = I;
|
wenzelm@16458
|
122 |
fun merge _
|
wenzelm@16458
|
123 |
({add_mono_thms= add_mono_thms1, mult_mono_thms= mult_mono_thms1, inj_thms= inj_thms1,
|
wenzelm@16458
|
124 |
lessD = lessD1, neqE=neqE1, simpset = simpset1},
|
wenzelm@16458
|
125 |
{add_mono_thms= add_mono_thms2, mult_mono_thms= mult_mono_thms2, inj_thms= inj_thms2,
|
wenzelm@16458
|
126 |
lessD = lessD2, neqE=neqE2, simpset = simpset2}) =
|
wenzelm@24039
|
127 |
{add_mono_thms = Thm.merge_thms (add_mono_thms1, add_mono_thms2),
|
wenzelm@24039
|
128 |
mult_mono_thms = Thm.merge_thms (mult_mono_thms1, mult_mono_thms2),
|
wenzelm@24039
|
129 |
inj_thms = Thm.merge_thms (inj_thms1, inj_thms2),
|
wenzelm@24039
|
130 |
lessD = Thm.merge_thms (lessD1, lessD2),
|
wenzelm@24039
|
131 |
neqE = Thm.merge_thms (neqE1, neqE2),
|
nipkow@10575
|
132 |
simpset = Simplifier.merge_ss (simpset1, simpset2)};
|
wenzelm@22846
|
133 |
);
|
wenzelm@9420
|
134 |
|
wenzelm@9420
|
135 |
val map_data = Data.map;
|
wenzelm@24076
|
136 |
val get_data = Data.get o Context.Proof;
|
wenzelm@9420
|
137 |
|
wenzelm@9420
|
138 |
|
wenzelm@9420
|
139 |
|
nipkow@5982
|
140 |
(*** A fast decision procedure ***)
|
nipkow@5982
|
141 |
(*** Code ported from HOL Light ***)
|
nipkow@6056
|
142 |
(* possible optimizations:
|
nipkow@6056
|
143 |
use (var,coeff) rep or vector rep tp save space;
|
nipkow@6056
|
144 |
treat non-negative atoms separately rather than adding 0 <= atom
|
nipkow@6056
|
145 |
*)
|
nipkow@5982
|
146 |
|
paulson@9073
|
147 |
val trace = ref false;
|
paulson@9073
|
148 |
|
nipkow@5982
|
149 |
datatype lineq_type = Eq | Le | Lt;
|
nipkow@5982
|
150 |
|
nipkow@6056
|
151 |
datatype injust = Asm of int
|
nipkow@6056
|
152 |
| Nat of int (* index of atom *)
|
nipkow@6128
|
153 |
| LessD of injust
|
nipkow@6128
|
154 |
| NotLessD of injust
|
nipkow@6128
|
155 |
| NotLeD of injust
|
nipkow@7551
|
156 |
| NotLeDD of injust
|
nipkow@16358
|
157 |
| Multiplied of IntInf.int * injust
|
nipkow@16358
|
158 |
| Multiplied2 of IntInf.int * injust
|
nipkow@5982
|
159 |
| Added of injust * injust;
|
nipkow@5982
|
160 |
|
nipkow@16358
|
161 |
datatype lineq = Lineq of IntInf.int * lineq_type * IntInf.int list * injust;
|
nipkow@5982
|
162 |
|
nipkow@13498
|
163 |
(* ------------------------------------------------------------------------- *)
|
nipkow@13498
|
164 |
(* Finding a (counter) example from the trace of a failed elimination *)
|
nipkow@13498
|
165 |
(* ------------------------------------------------------------------------- *)
|
nipkow@13498
|
166 |
(* Examples are represented as rational numbers, *)
|
nipkow@13498
|
167 |
(* Dont blame John Harrison for this code - it is entirely mine. TN *)
|
nipkow@13498
|
168 |
|
nipkow@13498
|
169 |
exception NoEx;
|
nipkow@13498
|
170 |
|
nipkow@14372
|
171 |
(* Coding: (i,true,cs) means i <= cs and (i,false,cs) means i < cs.
|
nipkow@14372
|
172 |
In general, true means the bound is included, false means it is excluded.
|
nipkow@14372
|
173 |
Need to know if it is a lower or upper bound for unambiguous interpretation!
|
nipkow@14372
|
174 |
*)
|
nipkow@14372
|
175 |
|
haftmann@22950
|
176 |
fun elim_eqns (Lineq (i, Le, cs, _)) = [(i, true, cs)]
|
haftmann@22950
|
177 |
| elim_eqns (Lineq (i, Eq, cs, _)) = [(i, true, cs),(~i, true, map ~ cs)]
|
haftmann@22950
|
178 |
| elim_eqns (Lineq (i, Lt, cs, _)) = [(i, false, cs)];
|
nipkow@13498
|
179 |
|
nipkow@13498
|
180 |
(* PRE: ex[v] must be 0! *)
|
haftmann@22950
|
181 |
fun eval ex v (a:IntInf.int,le,cs:IntInf.int list) =
|
haftmann@22950
|
182 |
let
|
haftmann@22950
|
183 |
val rs = map Rat.rat_of_int cs;
|
haftmann@22950
|
184 |
val rsum = fold2 (Rat.add oo Rat.mult) rs ex Rat.zero;
|
haftmann@23063
|
185 |
in (Rat.mult (Rat.add (Rat.rat_of_int a) (Rat.neg rsum)) (Rat.inv (nth rs v)), le) end;
|
haftmann@23063
|
186 |
(* If nth rs v < 0, le should be negated.
|
nipkow@14372
|
187 |
Instead this swap is taken into account in ratrelmin2.
|
nipkow@14372
|
188 |
*)
|
nipkow@13498
|
189 |
|
haftmann@22950
|
190 |
fun ratrelmin2 (x as (r, ler), y as (s, les)) =
|
haftmann@23520
|
191 |
case Rat.ord (r, s)
|
haftmann@22950
|
192 |
of EQUAL => (r, (not ler) andalso (not les))
|
haftmann@22950
|
193 |
| LESS => x
|
haftmann@22950
|
194 |
| GREATER => y;
|
haftmann@22950
|
195 |
|
haftmann@22950
|
196 |
fun ratrelmax2 (x as (r, ler), y as (s, les)) =
|
haftmann@23520
|
197 |
case Rat.ord (r, s)
|
haftmann@22950
|
198 |
of EQUAL => (r, ler andalso les)
|
haftmann@22950
|
199 |
| LESS => y
|
haftmann@22950
|
200 |
| GREATER => x;
|
nipkow@13498
|
201 |
|
nipkow@14372
|
202 |
val ratrelmin = foldr1 ratrelmin2;
|
nipkow@14372
|
203 |
val ratrelmax = foldr1 ratrelmax2;
|
nipkow@13498
|
204 |
|
haftmann@22950
|
205 |
fun ratexact up (r, exact) =
|
nipkow@14372
|
206 |
if exact then r else
|
haftmann@22950
|
207 |
let
|
haftmann@22950
|
208 |
val (p, q) = Rat.quotient_of_rat r;
|
haftmann@22950
|
209 |
val nth = Rat.inv (Rat.rat_of_int q);
|
haftmann@22950
|
210 |
in Rat.add r (if up then nth else Rat.neg nth) end;
|
nipkow@14372
|
211 |
|
haftmann@22950
|
212 |
fun ratmiddle (r, s) = Rat.mult (Rat.add r s) (Rat.inv Rat.two);
|
nipkow@14372
|
213 |
|
webertj@20217
|
214 |
fun choose2 d ((lb, exactl), (ub, exactu)) =
|
haftmann@23520
|
215 |
let val ord = Rat.sign lb in
|
haftmann@22950
|
216 |
if (ord = LESS orelse exactl) andalso (ord = GREATER orelse exactu)
|
haftmann@22950
|
217 |
then Rat.zero
|
haftmann@22950
|
218 |
else if not d then
|
haftmann@22950
|
219 |
if ord = GREATER
|
webertj@20217
|
220 |
then if exactl then lb else ratmiddle (lb, ub)
|
haftmann@22950
|
221 |
else if exactu then ub else ratmiddle (lb, ub)
|
haftmann@22950
|
222 |
else (*discrete domain, both bounds must be exact*)
|
haftmann@23025
|
223 |
if ord = GREATER
|
haftmann@22950
|
224 |
then let val lb' = Rat.roundup lb in
|
haftmann@22950
|
225 |
if Rat.le lb' ub then lb' else raise NoEx end
|
haftmann@22950
|
226 |
else let val ub' = Rat.rounddown ub in
|
haftmann@22950
|
227 |
if Rat.le lb ub' then ub' else raise NoEx end
|
haftmann@22950
|
228 |
end;
|
nipkow@13498
|
229 |
|
haftmann@22950
|
230 |
fun findex1 discr (v, lineqs) ex =
|
haftmann@22950
|
231 |
let
|
haftmann@23063
|
232 |
val nz = filter (fn (Lineq (_, _, cs, _)) => nth cs v <> 0) lineqs;
|
haftmann@22950
|
233 |
val ineqs = maps elim_eqns nz;
|
haftmann@23063
|
234 |
val (ge, le) = List.partition (fn (_,_,cs) => nth cs v > 0) ineqs
|
haftmann@22950
|
235 |
val lb = ratrelmax (map (eval ex v) ge)
|
haftmann@22950
|
236 |
val ub = ratrelmin (map (eval ex v) le)
|
haftmann@21109
|
237 |
in nth_map v (K (choose2 (nth discr v) (lb, ub))) ex end;
|
nipkow@13498
|
238 |
|
nipkow@13498
|
239 |
fun elim1 v x =
|
haftmann@23063
|
240 |
map (fn (a,le,bs) => (Rat.add a (Rat.neg (Rat.mult (nth bs v) x)), le,
|
haftmann@21109
|
241 |
nth_map v (K Rat.zero) bs));
|
nipkow@13498
|
242 |
|
haftmann@23520
|
243 |
fun single_var v (_, _, cs) = case filter_out (curry (op =) EQUAL o Rat.sign) cs
|
haftmann@23063
|
244 |
of [x] => x =/ nth cs v
|
haftmann@23063
|
245 |
| _ => false;
|
nipkow@13498
|
246 |
|
nipkow@13498
|
247 |
(* The base case:
|
nipkow@13498
|
248 |
all variables occur only with positive or only with negative coefficients *)
|
nipkow@13498
|
249 |
fun pick_vars discr (ineqs,ex) =
|
haftmann@23520
|
250 |
let val nz = filter_out (fn (_,_,cs) => forall (curry (op =) EQUAL o Rat.sign) cs) ineqs
|
nipkow@14372
|
251 |
in case nz of [] => ex
|
nipkow@14372
|
252 |
| (_,_,cs) :: _ =>
|
haftmann@23520
|
253 |
let val v = find_index (not o curry (op =) EQUAL o Rat.sign) cs
|
haftmann@22950
|
254 |
val d = nth discr v;
|
haftmann@23520
|
255 |
val pos = not (Rat.sign (nth cs v) = LESS);
|
haftmann@22950
|
256 |
val sv = filter (single_var v) nz;
|
nipkow@14372
|
257 |
val minmax =
|
haftmann@17951
|
258 |
if pos then if d then Rat.roundup o fst o ratrelmax
|
nipkow@14372
|
259 |
else ratexact true o ratrelmax
|
haftmann@17951
|
260 |
else if d then Rat.rounddown o fst o ratrelmin
|
nipkow@14372
|
261 |
else ratexact false o ratrelmin
|
haftmann@23063
|
262 |
val bnds = map (fn (a,le,bs) => (Rat.mult a (Rat.inv (nth bs v)), le)) sv
|
haftmann@17951
|
263 |
val x = minmax((Rat.zero,if pos then true else false)::bnds)
|
nipkow@14372
|
264 |
val ineqs' = elim1 v x nz
|
haftmann@21109
|
265 |
val ex' = nth_map v (K x) ex
|
nipkow@14372
|
266 |
in pick_vars discr (ineqs',ex') end
|
nipkow@13498
|
267 |
end;
|
nipkow@13498
|
268 |
|
nipkow@13498
|
269 |
fun findex0 discr n lineqs =
|
haftmann@22950
|
270 |
let val ineqs = maps elim_eqns lineqs
|
haftmann@22950
|
271 |
val rineqs = map (fn (a,le,cs) => (Rat.rat_of_int a, le, map Rat.rat_of_int cs))
|
nipkow@14372
|
272 |
ineqs
|
haftmann@17951
|
273 |
in pick_vars discr (rineqs,replicate n Rat.zero) end;
|
nipkow@13498
|
274 |
|
nipkow@13498
|
275 |
(* ------------------------------------------------------------------------- *)
|
webertj@23197
|
276 |
(* End of counterexample finder. The actual decision procedure starts here. *)
|
nipkow@13498
|
277 |
(* ------------------------------------------------------------------------- *)
|
nipkow@13498
|
278 |
|
nipkow@5982
|
279 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
280 |
(* Calculate new (in)equality type after addition. *)
|
nipkow@5982
|
281 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
282 |
|
nipkow@5982
|
283 |
fun find_add_type(Eq,x) = x
|
nipkow@5982
|
284 |
| find_add_type(x,Eq) = x
|
nipkow@5982
|
285 |
| find_add_type(_,Lt) = Lt
|
nipkow@5982
|
286 |
| find_add_type(Lt,_) = Lt
|
nipkow@5982
|
287 |
| find_add_type(Le,Le) = Le;
|
nipkow@5982
|
288 |
|
nipkow@5982
|
289 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
290 |
(* Multiply out an (in)equation. *)
|
nipkow@5982
|
291 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
292 |
|
nipkow@5982
|
293 |
fun multiply_ineq n (i as Lineq(k,ty,l,just)) =
|
nipkow@5982
|
294 |
if n = 1 then i
|
nipkow@5982
|
295 |
else if n = 0 andalso ty = Lt then sys_error "multiply_ineq"
|
nipkow@5982
|
296 |
else if n < 0 andalso (ty=Le orelse ty=Lt) then sys_error "multiply_ineq"
|
paulson@17524
|
297 |
else Lineq (n * k, ty, map (curry op* n) l, Multiplied (n, just));
|
nipkow@5982
|
298 |
|
nipkow@5982
|
299 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
300 |
(* Add together (in)equations. *)
|
nipkow@5982
|
301 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
302 |
|
nipkow@5982
|
303 |
fun add_ineq (i1 as Lineq(k1,ty1,l1,just1)) (i2 as Lineq(k2,ty2,l2,just2)) =
|
haftmann@18330
|
304 |
let val l = map2 (curry (op +)) l1 l2
|
nipkow@5982
|
305 |
in Lineq(k1+k2,find_add_type(ty1,ty2),l,Added(just1,just2)) end;
|
nipkow@5982
|
306 |
|
nipkow@5982
|
307 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
308 |
(* Elimination of variable between a single pair of (in)equations. *)
|
nipkow@5982
|
309 |
(* If they're both inequalities, 1st coefficient must be +ve, 2nd -ve. *)
|
nipkow@5982
|
310 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
311 |
|
nipkow@5982
|
312 |
fun elim_var v (i1 as Lineq(k1,ty1,l1,just1)) (i2 as Lineq(k2,ty2,l2,just2)) =
|
haftmann@23063
|
313 |
let val c1 = nth l1 v and c2 = nth l2 v
|
haftmann@23261
|
314 |
val m = Integer.lcm (abs c1) (abs c2)
|
nipkow@5982
|
315 |
val m1 = m div (abs c1) and m2 = m div (abs c2)
|
nipkow@5982
|
316 |
val (n1,n2) =
|
nipkow@5982
|
317 |
if (c1 >= 0) = (c2 >= 0)
|
nipkow@5982
|
318 |
then if ty1 = Eq then (~m1,m2)
|
nipkow@5982
|
319 |
else if ty2 = Eq then (m1,~m2)
|
nipkow@5982
|
320 |
else sys_error "elim_var"
|
nipkow@5982
|
321 |
else (m1,m2)
|
nipkow@5982
|
322 |
val (p1,p2) = if ty1=Eq andalso ty2=Eq andalso (n1 = ~1 orelse n2 = ~1)
|
nipkow@5982
|
323 |
then (~n1,~n2) else (n1,n2)
|
nipkow@5982
|
324 |
in add_ineq (multiply_ineq n1 i1) (multiply_ineq n2 i2) end;
|
nipkow@5982
|
325 |
|
nipkow@5982
|
326 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
327 |
(* The main refutation-finding code. *)
|
nipkow@5982
|
328 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
329 |
|
nipkow@5982
|
330 |
fun is_trivial (Lineq(_,_,l,_)) = forall (fn i => i=0) l;
|
nipkow@5982
|
331 |
|
nipkow@5982
|
332 |
fun is_answer (ans as Lineq(k,ty,l,_)) =
|
nipkow@5982
|
333 |
case ty of Eq => k <> 0 | Le => k > 0 | Lt => k >= 0;
|
nipkow@5982
|
334 |
|
nipkow@16358
|
335 |
fun calc_blowup (l:IntInf.int list) =
|
haftmann@17496
|
336 |
let val (p,n) = List.partition (curry (op <) 0) (List.filter (curry (op <>) 0) l)
|
nipkow@5982
|
337 |
in (length p) * (length n) end;
|
nipkow@5982
|
338 |
|
nipkow@5982
|
339 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
340 |
(* Main elimination code: *)
|
nipkow@5982
|
341 |
(* *)
|
nipkow@5982
|
342 |
(* (1) Looks for immediate solutions (false assertions with no variables). *)
|
nipkow@5982
|
343 |
(* *)
|
nipkow@5982
|
344 |
(* (2) If there are any equations, picks a variable with the lowest absolute *)
|
nipkow@5982
|
345 |
(* coefficient in any of them, and uses it to eliminate. *)
|
nipkow@5982
|
346 |
(* *)
|
nipkow@5982
|
347 |
(* (3) Otherwise, chooses a variable in the inequality to minimize the *)
|
nipkow@5982
|
348 |
(* blowup (number of consequences generated) and eliminates it. *)
|
nipkow@5982
|
349 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
350 |
|
nipkow@5982
|
351 |
fun allpairs f xs ys =
|
webertj@20217
|
352 |
List.concat (map (fn x => map (fn y => f x y) ys) xs);
|
nipkow@5982
|
353 |
|
nipkow@5982
|
354 |
fun extract_first p =
|
skalberg@15531
|
355 |
let fun extract xs (y::ys) = if p y then (SOME y,xs@ys)
|
nipkow@5982
|
356 |
else extract (y::xs) ys
|
skalberg@15531
|
357 |
| extract xs [] = (NONE,xs)
|
nipkow@5982
|
358 |
in extract [] end;
|
nipkow@5982
|
359 |
|
nipkow@6056
|
360 |
fun print_ineqs ineqs =
|
paulson@9073
|
361 |
if !trace then
|
wenzelm@12262
|
362 |
tracing(cat_lines(""::map (fn Lineq(c,t,l,_) =>
|
nipkow@16358
|
363 |
IntInf.toString c ^
|
paulson@9073
|
364 |
(case t of Eq => " = " | Lt=> " < " | Le => " <= ") ^
|
nipkow@16358
|
365 |
commas(map IntInf.toString l)) ineqs))
|
paulson@9073
|
366 |
else ();
|
nipkow@6056
|
367 |
|
nipkow@13498
|
368 |
type history = (int * lineq list) list;
|
nipkow@13498
|
369 |
datatype result = Success of injust | Failure of history;
|
nipkow@13498
|
370 |
|
webertj@20217
|
371 |
fun elim (ineqs, hist) =
|
webertj@20217
|
372 |
let val dummy = print_ineqs ineqs
|
webertj@20217
|
373 |
val (triv, nontriv) = List.partition is_trivial ineqs in
|
webertj@20217
|
374 |
if not (null triv)
|
nipkow@13186
|
375 |
then case Library.find_first is_answer triv of
|
webertj@20217
|
376 |
NONE => elim (nontriv, hist)
|
skalberg@15531
|
377 |
| SOME(Lineq(_,_,_,j)) => Success j
|
nipkow@5982
|
378 |
else
|
webertj@20217
|
379 |
if null nontriv then Failure hist
|
nipkow@13498
|
380 |
else
|
webertj@20217
|
381 |
let val (eqs, noneqs) = List.partition (fn (Lineq(_,ty,_,_)) => ty=Eq) nontriv in
|
webertj@20217
|
382 |
if not (null eqs) then
|
skalberg@15570
|
383 |
let val clist = Library.foldl (fn (cs,Lineq(_,_,l,_)) => l union cs) ([],eqs)
|
nipkow@16358
|
384 |
val sclist = sort (fn (x,y) => IntInf.compare(abs(x),abs(y)))
|
skalberg@15570
|
385 |
(List.filter (fn i => i<>0) clist)
|
nipkow@5982
|
386 |
val c = hd sclist
|
skalberg@15531
|
387 |
val (SOME(eq as Lineq(_,_,ceq,_)),othereqs) =
|
nipkow@5982
|
388 |
extract_first (fn Lineq(_,_,l,_) => c mem l) eqs
|
webertj@20217
|
389 |
val v = find_index_eq c ceq
|
haftmann@23063
|
390 |
val (ioth,roth) = List.partition (fn (Lineq(_,_,l,_)) => nth l v = 0)
|
nipkow@5982
|
391 |
(othereqs @ noneqs)
|
nipkow@5982
|
392 |
val others = map (elim_var v eq) roth @ ioth
|
nipkow@13498
|
393 |
in elim(others,(v,nontriv)::hist) end
|
nipkow@5982
|
394 |
else
|
nipkow@5982
|
395 |
let val lists = map (fn (Lineq(_,_,l,_)) => l) noneqs
|
haftmann@23063
|
396 |
val numlist = 0 upto (length (hd lists) - 1)
|
haftmann@23063
|
397 |
val coeffs = map (fn i => map (fn xs => nth xs i) lists) numlist
|
nipkow@5982
|
398 |
val blows = map calc_blowup coeffs
|
nipkow@5982
|
399 |
val iblows = blows ~~ numlist
|
haftmann@23063
|
400 |
val nziblows = filter_out (fn (i, _) => i = 0) iblows
|
nipkow@13498
|
401 |
in if null nziblows then Failure((~1,nontriv)::hist)
|
nipkow@13498
|
402 |
else
|
nipkow@5982
|
403 |
let val (c,v) = hd(sort (fn (x,y) => int_ord(fst(x),fst(y))) nziblows)
|
haftmann@23063
|
404 |
val (no,yes) = List.partition (fn (Lineq(_,_,l,_)) => nth l v = 0) ineqs
|
haftmann@23063
|
405 |
val (pos,neg) = List.partition(fn (Lineq(_,_,l,_)) => nth l v > 0) yes
|
nipkow@13498
|
406 |
in elim(no @ allpairs (elim_var v) pos neg, (v,nontriv)::hist) end
|
nipkow@5982
|
407 |
end
|
nipkow@5982
|
408 |
end
|
nipkow@5982
|
409 |
end;
|
nipkow@5982
|
410 |
|
nipkow@5982
|
411 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
412 |
(* Translate back a proof. *)
|
nipkow@5982
|
413 |
(* ------------------------------------------------------------------------- *)
|
nipkow@5982
|
414 |
|
wenzelm@24076
|
415 |
fun trace_thm msg th =
|
wenzelm@24076
|
416 |
(if !trace then (tracing msg; tracing (Display.string_of_thm th)) else (); th);
|
paulson@9073
|
417 |
|
wenzelm@24076
|
418 |
fun trace_term ctxt msg t =
|
wenzelm@24076
|
419 |
(if !trace then tracing (cat_lines [msg, ProofContext.string_of_term ctxt t]) else (); t)
|
wenzelm@24076
|
420 |
|
wenzelm@24076
|
421 |
fun trace_msg msg =
|
wenzelm@24076
|
422 |
if !trace then tracing msg else ();
|
paulson@9073
|
423 |
|
nipkow@13498
|
424 |
(* FIXME OPTIMIZE!!!! (partly done already)
|
nipkow@6056
|
425 |
Addition/Multiplication need i*t representation rather than t+t+...
|
nipkow@10691
|
426 |
Get rid of Mulitplied(2). For Nat LA_Data.number_of should return Suc^n
|
nipkow@10691
|
427 |
because Numerals are not known early enough.
|
nipkow@6056
|
428 |
|
nipkow@6056
|
429 |
Simplification may detect a contradiction 'prematurely' due to type
|
nipkow@6056
|
430 |
information: n+1 <= 0 is simplified to False and does not need to be crossed
|
nipkow@6056
|
431 |
with 0 <= n.
|
nipkow@6056
|
432 |
*)
|
nipkow@6056
|
433 |
local
|
wenzelm@24076
|
434 |
exception FalseE of thm
|
nipkow@6056
|
435 |
in
|
wenzelm@24076
|
436 |
fun mkthm ss asms (just: injust) =
|
wenzelm@24076
|
437 |
let
|
wenzelm@24076
|
438 |
val ctxt = Simplifier.the_context ss;
|
wenzelm@24076
|
439 |
val thy = ProofContext.theory_of ctxt;
|
wenzelm@24076
|
440 |
val {add_mono_thms, mult_mono_thms, inj_thms, lessD, simpset, ...} = get_data ctxt;
|
wenzelm@24076
|
441 |
val simpset' = Simplifier.inherit_context ss simpset;
|
wenzelm@24076
|
442 |
val atoms = Library.foldl (fn (ats, (lhs,_,_,rhs,_,_)) =>
|
nipkow@6056
|
443 |
map fst lhs union (map fst rhs union ats))
|
webertj@20217
|
444 |
([], List.mapPartial (fn thm => if Thm.no_prems thm
|
wenzelm@24076
|
445 |
then LA_Data.decomp ctxt (Thm.concl_of thm)
|
webertj@20217
|
446 |
else NONE) asms)
|
nipkow@6056
|
447 |
|
nipkow@10575
|
448 |
fun add2 thm1 thm2 =
|
nipkow@10575
|
449 |
let val conj = thm1 RS (thm2 RS LA_Logic.conjI)
|
skalberg@15531
|
450 |
in get_first (fn th => SOME(conj RS th) handle THM _ => NONE) add_mono_thms
|
nipkow@10575
|
451 |
end;
|
skalberg@15531
|
452 |
fun try_add [] _ = NONE
|
nipkow@10575
|
453 |
| try_add (thm1::thm1s) thm2 = case add2 thm1 thm2 of
|
skalberg@15531
|
454 |
NONE => try_add thm1s thm2 | some => some;
|
nipkow@10575
|
455 |
|
nipkow@6056
|
456 |
fun addthms thm1 thm2 =
|
nipkow@10575
|
457 |
case add2 thm1 thm2 of
|
skalberg@15531
|
458 |
NONE => (case try_add ([thm1] RL inj_thms) thm2 of
|
webertj@20217
|
459 |
NONE => ( the (try_add ([thm2] RL inj_thms) thm1)
|
wenzelm@15660
|
460 |
handle Option =>
|
nipkow@14360
|
461 |
(trace_thm "" thm1; trace_thm "" thm2;
|
webertj@20217
|
462 |
sys_error "Lin.arith. failed to add thms")
|
webertj@20217
|
463 |
)
|
skalberg@15531
|
464 |
| SOME thm => thm)
|
skalberg@15531
|
465 |
| SOME thm => thm;
|
nipkow@5982
|
466 |
|
nipkow@5982
|
467 |
fun multn(n,thm) =
|
nipkow@5982
|
468 |
let fun mul(i,th) = if i=1 then th else mul(i-1, addthms thm th)
|
nipkow@6102
|
469 |
in if n < 0 then mul(~n,thm) RS LA_Logic.sym else mul(n,thm) end;
|
webertj@20217
|
470 |
|
nipkow@15184
|
471 |
fun multn2(n,thm) =
|
skalberg@15531
|
472 |
let val SOME(mth) =
|
skalberg@15531
|
473 |
get_first (fn th => SOME(thm RS th) handle THM _ => NONE) mult_mono_thms
|
wenzelm@22596
|
474 |
fun cvar(th,_ $ (_ $ _ $ var)) = cterm_of (Thm.theory_of_thm th) var;
|
nipkow@15184
|
475 |
val cv = cvar(mth, hd(prems_of mth));
|
wenzelm@24076
|
476 |
val ct = cterm_of thy (LA_Data.number_of(n,#T(rep_cterm cv)))
|
nipkow@15184
|
477 |
in instantiate ([],[(cv,ct)]) mth end
|
nipkow@10691
|
478 |
|
nipkow@6056
|
479 |
fun simp thm =
|
wenzelm@17515
|
480 |
let val thm' = trace_thm "Simplified:" (full_simplify simpset' thm)
|
nipkow@6102
|
481 |
in if LA_Logic.is_False thm' then raise FalseE thm' else thm' end
|
nipkow@6056
|
482 |
|
wenzelm@24076
|
483 |
fun mk (Asm i) = trace_thm ("Asm " ^ string_of_int i) (nth asms i)
|
wenzelm@24076
|
484 |
| mk (Nat i) = trace_thm ("Nat " ^ string_of_int i) (LA_Logic.mk_nat_thm thy (nth atoms i))
|
webertj@20254
|
485 |
| mk (LessD j) = trace_thm "L" (hd ([mk j] RL lessD))
|
webertj@20254
|
486 |
| mk (NotLeD j) = trace_thm "NLe" (mk j RS LA_Logic.not_leD)
|
webertj@20254
|
487 |
| mk (NotLeDD j) = trace_thm "NLeD" (hd ([mk j RS LA_Logic.not_leD] RL lessD))
|
webertj@20254
|
488 |
| mk (NotLessD j) = trace_thm "NL" (mk j RS LA_Logic.not_lessD)
|
webertj@20254
|
489 |
| mk (Added (j1, j2)) = simp (trace_thm "+" (addthms (mk j1) (mk j2)))
|
webertj@20254
|
490 |
| mk (Multiplied (n, j)) = (trace_msg ("*" ^ IntInf.toString n); trace_thm "*" (multn (n, mk j)))
|
webertj@20254
|
491 |
| mk (Multiplied2 (n, j)) = simp (trace_msg ("**" ^ IntInf.toString n); trace_thm "**" (multn2 (n, mk j)))
|
nipkow@5982
|
492 |
|
paulson@9073
|
493 |
in trace_msg "mkthm";
|
nipkow@12932
|
494 |
let val thm = trace_thm "Final thm:" (mk just)
|
wenzelm@17515
|
495 |
in let val fls = simplify simpset' thm
|
nipkow@13186
|
496 |
in trace_thm "After simplification:" fls;
|
nipkow@13186
|
497 |
if LA_Logic.is_False fls then fls
|
nipkow@13186
|
498 |
else
|
webertj@20217
|
499 |
(tracing "Assumptions:"; List.app (tracing o Display.string_of_thm) asms;
|
webertj@20217
|
500 |
tracing "Proved:"; tracing (Display.string_of_thm fls);
|
nipkow@13186
|
501 |
warning "Linear arithmetic should have refuted the assumptions.\n\
|
nipkow@13186
|
502 |
\Please inform Tobias Nipkow (nipkow@in.tum.de).";
|
nipkow@13186
|
503 |
fls)
|
nipkow@12932
|
504 |
end
|
webertj@20217
|
505 |
end handle FalseE thm => trace_thm "False reached early:" thm
|
nipkow@12932
|
506 |
end
|
nipkow@6056
|
507 |
end;
|
nipkow@5982
|
508 |
|
haftmann@23261
|
509 |
fun coeff poly atom =
|
wenzelm@23577
|
510 |
AList.lookup (op aconv) poly atom |> the_default (0: integer);
|
nipkow@5982
|
511 |
|
wenzelm@23297
|
512 |
fun lcms ks = fold Integer.lcm ks 1;
|
nipkow@10691
|
513 |
|
nipkow@10691
|
514 |
fun integ(rlhs,r,rel,rrhs,s,d) =
|
haftmann@17951
|
515 |
let val (rn,rd) = Rat.quotient_of_rat r and (sn,sd) = Rat.quotient_of_rat s
|
haftmann@17951
|
516 |
val m = lcms(map (abs o snd o Rat.quotient_of_rat) (r :: s :: map snd rlhs @ map snd rrhs))
|
wenzelm@22846
|
517 |
fun mult(t,r) =
|
haftmann@17951
|
518 |
let val (i,j) = Rat.quotient_of_rat r
|
paulson@15965
|
519 |
in (t,i * (m div j)) end
|
nipkow@12932
|
520 |
in (m,(map mult rlhs, rn*(m div rd), rel, map mult rrhs, sn*(m div sd), d)) end
|
nipkow@10691
|
521 |
|
nipkow@13498
|
522 |
fun mklineq n atoms =
|
webertj@20217
|
523 |
fn (item, k) =>
|
webertj@20217
|
524 |
let val (m, (lhs,i,rel,rhs,j,discrete)) = integ item
|
nipkow@13498
|
525 |
val lhsa = map (coeff lhs) atoms
|
nipkow@13498
|
526 |
and rhsa = map (coeff rhs) atoms
|
haftmann@18330
|
527 |
val diff = map2 (curry (op -)) rhsa lhsa
|
nipkow@13498
|
528 |
val c = i-j
|
nipkow@13498
|
529 |
val just = Asm k
|
nipkow@13498
|
530 |
fun lineq(c,le,cs,j) = Lineq(c,le,cs, if m=1 then j else Multiplied2(m,j))
|
nipkow@13498
|
531 |
in case rel of
|
nipkow@13498
|
532 |
"<=" => lineq(c,Le,diff,just)
|
nipkow@13498
|
533 |
| "~<=" => if discrete
|
nipkow@13498
|
534 |
then lineq(1-c,Le,map (op ~) diff,NotLeDD(just))
|
nipkow@13498
|
535 |
else lineq(~c,Lt,map (op ~) diff,NotLeD(just))
|
nipkow@13498
|
536 |
| "<" => if discrete
|
nipkow@13498
|
537 |
then lineq(c+1,Le,diff,LessD(just))
|
nipkow@13498
|
538 |
else lineq(c,Lt,diff,just)
|
nipkow@13498
|
539 |
| "~<" => lineq(~c,Le,map (op~) diff,NotLessD(just))
|
nipkow@13498
|
540 |
| "=" => lineq(c,Eq,diff,just)
|
wenzelm@22846
|
541 |
| _ => sys_error("mklineq" ^ rel)
|
nipkow@5982
|
542 |
end;
|
nipkow@5982
|
543 |
|
nipkow@13498
|
544 |
(* ------------------------------------------------------------------------- *)
|
nipkow@13498
|
545 |
(* Print (counter) example *)
|
nipkow@13498
|
546 |
(* ------------------------------------------------------------------------- *)
|
nipkow@13498
|
547 |
|
nipkow@13498
|
548 |
fun print_atom((a,d),r) =
|
haftmann@17951
|
549 |
let val (p,q) = Rat.quotient_of_rat r
|
paulson@15965
|
550 |
val s = if d then IntInf.toString p else
|
nipkow@13498
|
551 |
if p = 0 then "0"
|
paulson@15965
|
552 |
else IntInf.toString p ^ "/" ^ IntInf.toString q
|
nipkow@13498
|
553 |
in a ^ " = " ^ s end;
|
nipkow@13498
|
554 |
|
wenzelm@19049
|
555 |
fun produce_ex sds =
|
haftmann@17496
|
556 |
curry (op ~~) sds
|
haftmann@17496
|
557 |
#> map print_atom
|
haftmann@17496
|
558 |
#> commas
|
webertj@23197
|
559 |
#> curry (op ^) "Counterexample (possibly spurious):\n";
|
nipkow@13498
|
560 |
|
wenzelm@24076
|
561 |
fun trace_ex ctxt params atoms discr n (hist: history) =
|
webertj@20217
|
562 |
case hist of
|
webertj@20217
|
563 |
[] => ()
|
webertj@20217
|
564 |
| (v, lineqs) :: hist' =>
|
wenzelm@24076
|
565 |
let
|
wenzelm@24076
|
566 |
val frees = map Free params
|
wenzelm@24076
|
567 |
fun show_term t = ProofContext.string_of_term ctxt (subst_bounds (frees, t))
|
wenzelm@24076
|
568 |
val start =
|
wenzelm@24076
|
569 |
if v = ~1 then (hist', findex0 discr n lineqs)
|
haftmann@22950
|
570 |
else (hist, replicate n Rat.zero)
|
wenzelm@24076
|
571 |
val ex = SOME (produce_ex (map show_term atoms ~~ discr)
|
wenzelm@24076
|
572 |
(uncurry (fold (findex1 discr)) start))
|
webertj@20217
|
573 |
handle NoEx => NONE
|
wenzelm@24076
|
574 |
in
|
wenzelm@24076
|
575 |
case ex of
|
wenzelm@24076
|
576 |
SOME s => (warning "arith failed - see trace for a counterexample"; tracing s)
|
wenzelm@24076
|
577 |
| NONE => warning "arith failed"
|
wenzelm@24076
|
578 |
end;
|
nipkow@13498
|
579 |
|
webertj@20217
|
580 |
(* ------------------------------------------------------------------------- *)
|
webertj@20217
|
581 |
|
webertj@20268
|
582 |
fun mknat (pTs : typ list) (ixs : int list) (atom : term, i : int) : lineq option =
|
webertj@20217
|
583 |
if LA_Logic.is_nat (pTs, atom)
|
nipkow@6056
|
584 |
then let val l = map (fn j => if j=i then 1 else 0) ixs
|
webertj@20217
|
585 |
in SOME (Lineq (0, Le, l, Nat i)) end
|
webertj@20217
|
586 |
else NONE;
|
nipkow@6056
|
587 |
|
nipkow@13186
|
588 |
(* This code is tricky. It takes a list of premises in the order they occur
|
skalberg@15531
|
589 |
in the subgoal. Numerical premises are coded as SOME(tuple), non-numerical
|
skalberg@15531
|
590 |
ones as NONE. Going through the premises, each numeric one is converted into
|
nipkow@13186
|
591 |
a Lineq. The tricky bit is to convert ~= which is split into two cases < and
|
nipkow@13498
|
592 |
>. Thus split_items returns a list of equation systems. This may blow up if
|
nipkow@13186
|
593 |
there are many ~=, but in practice it does not seem to happen. The really
|
nipkow@13186
|
594 |
tricky bit is to arrange the order of the cases such that they coincide with
|
nipkow@13186
|
595 |
the order in which the cases are in the end generated by the tactic that
|
nipkow@13186
|
596 |
applies the generated refutation thms (see function 'refute_tac').
|
nipkow@13186
|
597 |
|
nipkow@13186
|
598 |
For variables n of type nat, a constraint 0 <= n is added.
|
nipkow@13186
|
599 |
*)
|
nipkow@13464
|
600 |
|
webertj@20217
|
601 |
(* FIXME: To optimize, the splitting of cases and the search for refutations *)
|
webertj@20276
|
602 |
(* could be intertwined: separate the first (fully split) case, *)
|
webertj@20217
|
603 |
(* refute it, continue with splitting and refuting. Terminate with *)
|
webertj@20217
|
604 |
(* failure as soon as a case could not be refuted; i.e. delay further *)
|
webertj@20217
|
605 |
(* splitting until after a refutation for other cases has been found. *)
|
nipkow@13498
|
606 |
|
wenzelm@24076
|
607 |
fun split_items ctxt do_pre (Ts, terms) : (typ list * (LA_Data.decompT * int) list) list =
|
webertj@20276
|
608 |
let
|
webertj@20276
|
609 |
(* splits inequalities '~=' into '<' and '>'; this corresponds to *)
|
webertj@20276
|
610 |
(* 'REPEAT_DETERM (eresolve_tac neqE i)' at the theorem/tactic *)
|
webertj@20276
|
611 |
(* level *)
|
webertj@20276
|
612 |
(* FIXME: this is currently sensitive to the order of theorems in *)
|
webertj@20276
|
613 |
(* neqE: The theorem for type "nat" must come first. A *)
|
webertj@20276
|
614 |
(* better (i.e. less likely to break when neqE changes) *)
|
webertj@20276
|
615 |
(* implementation should *test* which theorem from neqE *)
|
webertj@20276
|
616 |
(* can be applied, and split the premise accordingly. *)
|
webertj@20276
|
617 |
fun elim_neq (ineqs : (LA_Data.decompT option * bool) list) :
|
webertj@20276
|
618 |
(LA_Data.decompT option * bool) list list =
|
webertj@20217
|
619 |
let
|
webertj@20276
|
620 |
fun elim_neq' nat_only ([] : (LA_Data.decompT option * bool) list) :
|
webertj@20276
|
621 |
(LA_Data.decompT option * bool) list list =
|
webertj@20276
|
622 |
[[]]
|
webertj@20276
|
623 |
| elim_neq' nat_only ((NONE, is_nat) :: ineqs) =
|
webertj@20276
|
624 |
map (cons (NONE, is_nat)) (elim_neq' nat_only ineqs)
|
webertj@20276
|
625 |
| elim_neq' nat_only ((ineq as (SOME (l, i, rel, r, j, d), is_nat)) :: ineqs) =
|
webertj@20276
|
626 |
if rel = "~=" andalso (not nat_only orelse is_nat) then
|
webertj@20276
|
627 |
(* [| ?l ~= ?r; ?l < ?r ==> ?R; ?r < ?l ==> ?R |] ==> ?R *)
|
webertj@20276
|
628 |
elim_neq' nat_only (ineqs @ [(SOME (l, i, "<", r, j, d), is_nat)]) @
|
webertj@20276
|
629 |
elim_neq' nat_only (ineqs @ [(SOME (r, j, "<", l, i, d), is_nat)])
|
webertj@20276
|
630 |
else
|
webertj@20276
|
631 |
map (cons ineq) (elim_neq' nat_only ineqs)
|
webertj@20276
|
632 |
in
|
webertj@20276
|
633 |
ineqs |> elim_neq' true
|
webertj@20276
|
634 |
|> map (elim_neq' false)
|
webertj@20276
|
635 |
|> List.concat
|
webertj@20276
|
636 |
end
|
webertj@20276
|
637 |
|
webertj@20276
|
638 |
fun number_hyps _ [] = []
|
webertj@20276
|
639 |
| number_hyps n (NONE::xs) = number_hyps (n+1) xs
|
webertj@20276
|
640 |
| number_hyps n ((SOME x)::xs) = (x, n) :: number_hyps (n+1) xs
|
webertj@20276
|
641 |
|
webertj@20276
|
642 |
val result = (Ts, terms)
|
webertj@20276
|
643 |
|> (* user-defined preprocessing of the subgoal *)
|
wenzelm@24076
|
644 |
(if do_pre then LA_Data.pre_decomp ctxt else Library.single)
|
webertj@23195
|
645 |
|> tap (fn subgoals => trace_msg ("Preprocessing yields " ^
|
webertj@23195
|
646 |
string_of_int (length subgoals) ^ " subgoal(s) total."))
|
wenzelm@22846
|
647 |
|> (* produce the internal encoding of (in-)equalities *)
|
wenzelm@24076
|
648 |
map (apsnd (map (fn t => (LA_Data.decomp ctxt t, LA_Data.domain_is_nat t))))
|
webertj@20276
|
649 |
|> (* splitting of inequalities *)
|
webertj@20276
|
650 |
map (apsnd elim_neq)
|
wenzelm@22846
|
651 |
|> maps (fn (Ts, subgoals) => map (pair Ts o map fst) subgoals)
|
webertj@20276
|
652 |
|> (* numbering of hypotheses, ignoring irrelevant ones *)
|
webertj@20276
|
653 |
map (apsnd (number_hyps 0))
|
webertj@23195
|
654 |
in
|
webertj@23195
|
655 |
trace_msg ("Splitting of inequalities yields " ^
|
webertj@23195
|
656 |
string_of_int (length result) ^ " subgoal(s) total.");
|
webertj@23195
|
657 |
result
|
webertj@23195
|
658 |
end;
|
webertj@20217
|
659 |
|
webertj@20268
|
660 |
fun add_atoms (ats : term list, ((lhs,_,_,rhs,_,_) : LA_Data.decompT, _)) : term list =
|
webertj@20217
|
661 |
(map fst lhs) union ((map fst rhs) union ats);
|
webertj@20217
|
662 |
|
webertj@20268
|
663 |
fun add_datoms (dats : (bool * term) list, ((lhs,_,_,rhs,_,d) : LA_Data.decompT, _)) :
|
webertj@20268
|
664 |
(bool * term) list =
|
webertj@20268
|
665 |
(map (pair d o fst) lhs) union ((map (pair d o fst) rhs) union dats);
|
webertj@20217
|
666 |
|
webertj@20268
|
667 |
fun discr (initems : (LA_Data.decompT * int) list) : bool list =
|
webertj@20268
|
668 |
map fst (Library.foldl add_datoms ([],initems));
|
webertj@20217
|
669 |
|
wenzelm@24076
|
670 |
fun refutes ctxt params show_ex :
|
webertj@20268
|
671 |
(typ list * (LA_Data.decompT * int) list) list -> injust list -> injust list option =
|
nipkow@13464
|
672 |
let
|
webertj@20268
|
673 |
fun refute ((Ts : typ list, initems : (LA_Data.decompT * int) list)::initemss)
|
webertj@20268
|
674 |
(js : injust list) : injust list option =
|
wenzelm@24076
|
675 |
let
|
wenzelm@24076
|
676 |
val atoms = Library.foldl add_atoms ([], initems)
|
wenzelm@24076
|
677 |
val n = length atoms
|
wenzelm@24076
|
678 |
val mkleq = mklineq n atoms
|
wenzelm@24076
|
679 |
val ixs = 0 upto (n - 1)
|
wenzelm@24076
|
680 |
val iatoms = atoms ~~ ixs
|
wenzelm@24076
|
681 |
val natlineqs = List.mapPartial (mknat Ts ixs) iatoms
|
wenzelm@24076
|
682 |
val ineqs = map mkleq initems @ natlineqs
|
webertj@20217
|
683 |
in case elim (ineqs, []) of
|
webertj@20217
|
684 |
Success j =>
|
wenzelm@24076
|
685 |
(trace_msg ("Contradiction! (" ^ string_of_int (length js + 1) ^ ")");
|
webertj@20268
|
686 |
refute initemss (js@[j]))
|
webertj@20217
|
687 |
| Failure hist =>
|
webertj@20217
|
688 |
(if not show_ex then
|
webertj@20217
|
689 |
()
|
webertj@20217
|
690 |
else let
|
webertj@20276
|
691 |
(* invent names for bound variables that are new, i.e. in Ts, *)
|
webertj@20276
|
692 |
(* but not in params; we assume that Ts still contains (map *)
|
webertj@20276
|
693 |
(* snd params) as a suffix *)
|
webertj@20217
|
694 |
val new_count = length Ts - length params - 1
|
webertj@20217
|
695 |
val new_names = map Name.bound (0 upto new_count)
|
webertj@20217
|
696 |
val params' = (new_names @ map fst params) ~~ Ts
|
webertj@20217
|
697 |
in
|
wenzelm@24076
|
698 |
trace_ex ctxt params' atoms (discr initems) n hist
|
webertj@20217
|
699 |
end; NONE)
|
nipkow@13498
|
700 |
end
|
skalberg@15531
|
701 |
| refute [] js = SOME js
|
nipkow@13498
|
702 |
in refute end;
|
nipkow@13464
|
703 |
|
wenzelm@24076
|
704 |
fun refute ctxt params show_ex do_pre terms : injust list option =
|
wenzelm@24076
|
705 |
refutes ctxt params show_ex (split_items ctxt do_pre (map snd params, terms)) [];
|
webertj@20254
|
706 |
|
haftmann@22950
|
707 |
fun count P xs = length (filter P xs);
|
webertj@20254
|
708 |
|
wenzelm@24076
|
709 |
fun prove ctxt (params : (string * Term.typ) list) show_ex do_pre Hs concl : injust list option =
|
webertj@20254
|
710 |
let
|
webertj@23190
|
711 |
val _ = trace_msg "prove:"
|
webertj@20254
|
712 |
(* append the negated conclusion to 'Hs' -- this corresponds to *)
|
webertj@20254
|
713 |
(* 'DETERM (resolve_tac [LA_Logic.notI, LA_Logic.ccontr] i)' at the *)
|
webertj@20254
|
714 |
(* theorem/tactic level *)
|
webertj@20254
|
715 |
val Hs' = Hs @ [LA_Logic.neg_prop concl]
|
webertj@20254
|
716 |
fun is_neq NONE = false
|
webertj@20254
|
717 |
| is_neq (SOME (_,_,r,_,_,_)) = (r = "~=")
|
wenzelm@24112
|
718 |
val neq_limit = Config.get ctxt LA_Data.fast_arith_neq_limit;
|
webertj@20254
|
719 |
in
|
wenzelm@24076
|
720 |
if count is_neq (map (LA_Data.decomp ctxt) Hs') > neq_limit then
|
wenzelm@24076
|
721 |
(trace_msg ("fast_arith_neq_limit exceeded (current value is " ^
|
wenzelm@24076
|
722 |
string_of_int neq_limit ^ ")"); NONE)
|
wenzelm@24076
|
723 |
else
|
wenzelm@24076
|
724 |
refute ctxt params show_ex do_pre Hs'
|
webertj@23190
|
725 |
end handle TERM ("neg_prop", _) =>
|
webertj@23190
|
726 |
(* since no meta-logic negation is available, we can only fail if *)
|
webertj@23190
|
727 |
(* the conclusion is not of the form 'Trueprop $ _' (simply *)
|
webertj@23190
|
728 |
(* dropping the conclusion doesn't work either, because even *)
|
webertj@23190
|
729 |
(* 'False' does not imply arbitrary 'concl::prop') *)
|
webertj@23190
|
730 |
(trace_msg "prove failed (cannot negate conclusion)."; NONE);
|
webertj@20217
|
731 |
|
wenzelm@22846
|
732 |
fun refute_tac ss (i, justs) =
|
nipkow@6074
|
733 |
fn state =>
|
wenzelm@24076
|
734 |
let
|
wenzelm@24076
|
735 |
val ctxt = Simplifier.the_context ss;
|
wenzelm@24076
|
736 |
val _ = trace_thm ("refute_tac (on subgoal " ^ string_of_int i ^ ", with " ^
|
wenzelm@24076
|
737 |
string_of_int (length justs) ^ " justification(s)):") state
|
wenzelm@24076
|
738 |
val {neqE, ...} = get_data ctxt;
|
wenzelm@24076
|
739 |
fun just1 j =
|
wenzelm@24076
|
740 |
(* eliminate inequalities *)
|
wenzelm@24076
|
741 |
REPEAT_DETERM (eresolve_tac neqE i) THEN
|
wenzelm@24076
|
742 |
PRIMITIVE (trace_thm "State after neqE:") THEN
|
wenzelm@24076
|
743 |
(* use theorems generated from the actual justifications *)
|
wenzelm@24076
|
744 |
METAHYPS (fn asms => rtac (mkthm ss asms j) 1) i
|
wenzelm@24076
|
745 |
in
|
wenzelm@24076
|
746 |
(* rewrite "[| A1; ...; An |] ==> B" to "[| A1; ...; An; ~B |] ==> False" *)
|
wenzelm@24076
|
747 |
DETERM (resolve_tac [LA_Logic.notI, LA_Logic.ccontr] i) THEN
|
wenzelm@24076
|
748 |
(* user-defined preprocessing of the subgoal *)
|
wenzelm@24076
|
749 |
DETERM (LA_Data.pre_tac ctxt i) THEN
|
wenzelm@24076
|
750 |
PRIMITIVE (trace_thm "State after pre_tac:") THEN
|
wenzelm@24076
|
751 |
(* prove every resulting subgoal, using its justification *)
|
wenzelm@24076
|
752 |
EVERY (map just1 justs)
|
webertj@20217
|
753 |
end state;
|
nipkow@6074
|
754 |
|
nipkow@5982
|
755 |
(*
|
nipkow@5982
|
756 |
Fast but very incomplete decider. Only premises and conclusions
|
nipkow@5982
|
757 |
that are already (negated) (in)equations are taken into account.
|
nipkow@5982
|
758 |
*)
|
wenzelm@24076
|
759 |
fun simpset_lin_arith_tac ss show_ex = SUBGOAL (fn (A, i) =>
|
wenzelm@24076
|
760 |
let
|
wenzelm@24076
|
761 |
val ctxt = Simplifier.the_context ss
|
wenzelm@24076
|
762 |
val params = rev (Logic.strip_params A)
|
wenzelm@24076
|
763 |
val Hs = Logic.strip_assums_hyp A
|
wenzelm@24076
|
764 |
val concl = Logic.strip_assums_concl A
|
wenzelm@24076
|
765 |
val _ = trace_term ctxt ("Trying to refute subgoal " ^ string_of_int i) A
|
wenzelm@24076
|
766 |
in
|
wenzelm@24076
|
767 |
case prove ctxt params show_ex true Hs concl of
|
wenzelm@24076
|
768 |
NONE => (trace_msg "Refutation failed."; no_tac)
|
wenzelm@24076
|
769 |
| SOME js => (trace_msg "Refutation succeeded."; refute_tac ss (i, js))
|
wenzelm@24076
|
770 |
end);
|
nipkow@5982
|
771 |
|
wenzelm@24076
|
772 |
fun cut_lin_arith_tac ss =
|
wenzelm@24076
|
773 |
cut_facts_tac (Simplifier.prems_of_ss ss) THEN'
|
wenzelm@24076
|
774 |
simpset_lin_arith_tac ss false;
|
wenzelm@17613
|
775 |
|
wenzelm@24076
|
776 |
fun lin_arith_tac ctxt =
|
wenzelm@24076
|
777 |
simpset_lin_arith_tac (Simplifier.context ctxt Simplifier.empty_ss);
|
wenzelm@24076
|
778 |
|
wenzelm@24076
|
779 |
|
nipkow@5982
|
780 |
|
nipkow@13186
|
781 |
(** Forward proof from theorems **)
|
nipkow@13186
|
782 |
|
webertj@20433
|
783 |
(* More tricky code. Needs to arrange the proofs of the multiple cases (due
|
webertj@20433
|
784 |
to splits of ~= premises) such that it coincides with the order of the cases
|
webertj@20433
|
785 |
generated by function split_items. *)
|
webertj@20433
|
786 |
|
webertj@20433
|
787 |
datatype splittree = Tip of thm list
|
webertj@20433
|
788 |
| Spl of thm * cterm * splittree * cterm * splittree;
|
webertj@20433
|
789 |
|
webertj@20433
|
790 |
(* "(ct1 ==> ?R) ==> (ct2 ==> ?R) ==> ?R" is taken to (ct1, ct2) *)
|
webertj@20433
|
791 |
|
webertj@20433
|
792 |
fun extract (imp : cterm) : cterm * cterm =
|
webertj@20433
|
793 |
let val (Il, r) = Thm.dest_comb imp
|
webertj@20433
|
794 |
val (_, imp1) = Thm.dest_comb Il
|
webertj@20433
|
795 |
val (Ict1, _) = Thm.dest_comb imp1
|
webertj@20433
|
796 |
val (_, ct1) = Thm.dest_comb Ict1
|
webertj@20433
|
797 |
val (Ir, _) = Thm.dest_comb r
|
webertj@20433
|
798 |
val (_, Ict2r) = Thm.dest_comb Ir
|
webertj@20433
|
799 |
val (Ict2, _) = Thm.dest_comb Ict2r
|
webertj@20433
|
800 |
val (_, ct2) = Thm.dest_comb Ict2
|
webertj@20433
|
801 |
in (ct1, ct2) end;
|
webertj@20433
|
802 |
|
wenzelm@24076
|
803 |
fun splitasms ctxt (asms : thm list) : splittree =
|
wenzelm@24076
|
804 |
let val {neqE, ...} = get_data ctxt
|
webertj@20433
|
805 |
fun elim_neq (asms', []) = Tip (rev asms')
|
webertj@20433
|
806 |
| elim_neq (asms', asm::asms) =
|
webertj@20433
|
807 |
(case get_first (fn th => SOME (asm COMP th) handle THM _ => NONE) neqE of
|
webertj@20433
|
808 |
SOME spl =>
|
webertj@20433
|
809 |
let val (ct1, ct2) = extract (cprop_of spl)
|
webertj@20433
|
810 |
val thm1 = assume ct1
|
webertj@20433
|
811 |
val thm2 = assume ct2
|
webertj@20433
|
812 |
in Spl (spl, ct1, elim_neq (asms', asms@[thm1]), ct2, elim_neq (asms', asms@[thm2]))
|
webertj@20433
|
813 |
end
|
webertj@20433
|
814 |
| NONE => elim_neq (asm::asms', asms))
|
webertj@20433
|
815 |
in elim_neq ([], asms) end;
|
webertj@20433
|
816 |
|
wenzelm@24076
|
817 |
fun fwdproof ss (Tip asms : splittree) (j::js : injust list) = (mkthm ss asms j, js)
|
wenzelm@24076
|
818 |
| fwdproof ss (Spl (thm, ct1, tree1, ct2, tree2)) js =
|
wenzelm@24076
|
819 |
let
|
wenzelm@24076
|
820 |
val (thm1, js1) = fwdproof ss tree1 js
|
wenzelm@24076
|
821 |
val (thm2, js2) = fwdproof ss tree2 js1
|
webertj@20433
|
822 |
val thm1' = implies_intr ct1 thm1
|
webertj@20433
|
823 |
val thm2' = implies_intr ct2 thm2
|
wenzelm@24076
|
824 |
in (thm2' COMP (thm1' COMP thm), js2) end;
|
wenzelm@24076
|
825 |
(* FIXME needs handle THM _ => NONE ? *)
|
webertj@20433
|
826 |
|
wenzelm@24076
|
827 |
fun prover ss thms Tconcl (js : injust list) pos : thm option =
|
wenzelm@24076
|
828 |
let
|
wenzelm@24076
|
829 |
val ctxt = Simplifier.the_context ss
|
wenzelm@24076
|
830 |
val thy = ProofContext.theory_of ctxt
|
wenzelm@24076
|
831 |
val nTconcl = LA_Logic.neg_prop Tconcl
|
wenzelm@24076
|
832 |
val cnTconcl = cterm_of thy nTconcl
|
wenzelm@24076
|
833 |
val nTconclthm = assume cnTconcl
|
wenzelm@24076
|
834 |
val tree = splitasms ctxt (thms @ [nTconclthm])
|
wenzelm@24076
|
835 |
val (Falsethm, _) = fwdproof ss tree js
|
wenzelm@24076
|
836 |
val contr = if pos then LA_Logic.ccontr else LA_Logic.notI
|
wenzelm@24076
|
837 |
val concl = implies_intr cnTconcl Falsethm COMP contr
|
wenzelm@24076
|
838 |
in SOME (trace_thm "Proved by lin. arith. prover:" (LA_Logic.mk_Eq concl)) end
|
wenzelm@24076
|
839 |
(*in case concl contains ?-var, which makes assume fail:*) (* FIXME Variable.import_terms *)
|
wenzelm@24076
|
840 |
handle THM _ => NONE;
|
nipkow@6074
|
841 |
|
nipkow@13186
|
842 |
(* PRE: concl is not negated!
|
nipkow@13186
|
843 |
This assumption is OK because
|
wenzelm@24076
|
844 |
1. lin_arith_simproc tries both to prove and disprove concl and
|
wenzelm@24076
|
845 |
2. lin_arith_simproc is applied by the Simplifier which
|
nipkow@13186
|
846 |
dives into terms and will thus try the non-negated concl anyway.
|
nipkow@13186
|
847 |
*)
|
wenzelm@24076
|
848 |
fun lin_arith_simproc ss concl =
|
wenzelm@24076
|
849 |
let
|
wenzelm@24076
|
850 |
val ctxt = Simplifier.the_context ss
|
wenzelm@24076
|
851 |
val thms = List.concat (map LA_Logic.atomize (Simplifier.prems_of_ss ss))
|
wenzelm@24076
|
852 |
val Hs = map Thm.prop_of thms
|
nipkow@6102
|
853 |
val Tconcl = LA_Logic.mk_Trueprop concl
|
wenzelm@24076
|
854 |
in
|
wenzelm@24076
|
855 |
case prove ctxt [] false false Hs Tconcl of (* concl provable? *)
|
wenzelm@24076
|
856 |
SOME js => prover ss thms Tconcl js true
|
wenzelm@24076
|
857 |
| NONE =>
|
wenzelm@24076
|
858 |
let val nTconcl = LA_Logic.neg_prop Tconcl in
|
wenzelm@24076
|
859 |
case prove ctxt [] false false Hs nTconcl of (* ~concl provable? *)
|
wenzelm@24076
|
860 |
SOME js => prover ss thms nTconcl js false
|
wenzelm@24076
|
861 |
| NONE => NONE
|
wenzelm@24076
|
862 |
end
|
wenzelm@24076
|
863 |
end;
|
nipkow@6074
|
864 |
|
nipkow@6074
|
865 |
end;
|