author | paulson |
Wed, 23 Mar 2005 12:09:18 +0100 | |
changeset 15620 | 8ccdc8bc66a2 |
parent 15574 | b1d1b5bfc464 |
child 15661 | 9ef583b08647 |
permissions | -rw-r--r-- |
13876 | 1 |
(* Title: HOL/Integ/presburger.ML |
2 |
ID: $Id$ |
|
3 |
Author: Amine Chaieb and Stefan Berghofer, TU Muenchen |
|
4 |
||
5 |
Tactic for solving arithmetical Goals in Presburger Arithmetic |
|
6 |
*) |
|
7 |
||
14811
9144ec118703
abstraction over functions is no default any more.
chaieb
parents:
14801
diff
changeset
|
8 |
(* This version of presburger deals with occurences of functional symbols in the subgoal and abstract over them to try to prove the more general formula. It then resolves with the subgoal. To enable this feature call the procedure with the parameter abs |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
9 |
*) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
10 |
|
13876 | 11 |
signature PRESBURGER = |
12 |
sig |
|
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
13 |
val presburger_tac : bool -> bool -> int -> tactic |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
14 |
val presburger_method : bool -> bool -> int -> Proof.method |
13876 | 15 |
val setup : (theory -> theory) list |
16 |
val trace : bool ref |
|
17 |
end; |
|
18 |
||
19 |
structure Presburger: PRESBURGER = |
|
20 |
struct |
|
21 |
||
22 |
val trace = ref false; |
|
23 |
fun trace_msg s = if !trace then tracing s else (); |
|
24 |
||
25 |
(*-----------------------------------------------------------------*) |
|
26 |
(*cooper_pp: provefunction for the one-exstance quantifier elimination*) |
|
27 |
(* Here still only one problem : The proof for the arithmetical transformations done on the dvd atomic formulae*) |
|
28 |
(*-----------------------------------------------------------------*) |
|
29 |
||
14941 | 30 |
|
31 |
(* Invoking the oracle *) |
|
32 |
||
33 |
fun pres_oracle sg t = |
|
15240
e1e6db03beee
Replaced the_context() by theory "Presburger" in call of invoke_oracle.
berghofe
parents:
15013
diff
changeset
|
34 |
invoke_oracle (theory "Presburger") "presburger_oracle" |
14941 | 35 |
(sg, CooperDec.COOPER_ORACLE t) ; |
36 |
||
14801
2d27b5ebc447
- deleted unneeded function eta_long (now in Pure/pattern.ML
berghofe
parents:
14758
diff
changeset
|
37 |
val presburger_ss = simpset_of (theory "Presburger"); |
2d27b5ebc447
- deleted unneeded function eta_long (now in Pure/pattern.ML
berghofe
parents:
14758
diff
changeset
|
38 |
|
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
39 |
fun cooper_pp sg (fm as e$Abs(xn,xT,p)) = |
13876 | 40 |
let val (xn1,p1) = variant_abs (xn,xT,p) |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
41 |
in (CooperProof.cooper_prv sg (Free (xn1, xT)) p1) end; |
13876 | 42 |
|
43 |
fun mnnf_pp sg fm = CooperProof.proof_of_cnnf sg fm |
|
44 |
(CooperProof.proof_of_evalc sg); |
|
45 |
||
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
46 |
fun tmproof_of_int_qelim sg fm = |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
47 |
Qelim.tproof_of_mlift_qelim sg CooperDec.is_arith_rel |
13876 | 48 |
(CooperProof.proof_of_linform sg) (mnnf_pp sg) (cooper_pp sg) fm; |
49 |
||
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
50 |
|
13876 | 51 |
(* Theorems to be used in this tactic*) |
52 |
||
53 |
val zdvd_int = thm "zdvd_int"; |
|
54 |
val zdiff_int_split = thm "zdiff_int_split"; |
|
55 |
val all_nat = thm "all_nat"; |
|
56 |
val ex_nat = thm "ex_nat"; |
|
57 |
val number_of1 = thm "number_of1"; |
|
58 |
val number_of2 = thm "number_of2"; |
|
59 |
val split_zdiv = thm "split_zdiv"; |
|
60 |
val split_zmod = thm "split_zmod"; |
|
61 |
val mod_div_equality' = thm "mod_div_equality'"; |
|
62 |
val split_div' = thm "split_div'"; |
|
63 |
val Suc_plus1 = thm "Suc_plus1"; |
|
64 |
val imp_le_cong = thm "imp_le_cong"; |
|
65 |
val conj_le_cong = thm "conj_le_cong"; |
|
66 |
||
67 |
(* extract all the constants in a term*) |
|
68 |
fun add_term_typed_consts (Const (c, T), cs) = (c,T) ins cs |
|
69 |
| add_term_typed_consts (t $ u, cs) = |
|
70 |
add_term_typed_consts (t, add_term_typed_consts (u, cs)) |
|
71 |
| add_term_typed_consts (Abs (_, _, t), cs) = add_term_typed_consts (t, cs) |
|
72 |
| add_term_typed_consts (_, cs) = cs; |
|
73 |
||
74 |
fun term_typed_consts t = add_term_typed_consts(t,[]); |
|
75 |
||
15531 | 76 |
(* SOME Types*) |
13876 | 77 |
val bT = HOLogic.boolT; |
15620
8ccdc8bc66a2
replaced bool by a new datatype "bit" for binary numerals
paulson
parents:
15574
diff
changeset
|
78 |
val bitT = HOLogic.bitT; |
13876 | 79 |
val iT = HOLogic.intT; |
80 |
val binT = HOLogic.binT; |
|
81 |
val nT = HOLogic.natT; |
|
82 |
||
83 |
(* Allowed Consts in formulae for presburger tactic*) |
|
84 |
||
85 |
val allowed_consts = |
|
86 |
[("All", (iT --> bT) --> bT), |
|
87 |
("Ex", (iT --> bT) --> bT), |
|
88 |
("All", (nT --> bT) --> bT), |
|
89 |
("Ex", (nT --> bT) --> bT), |
|
90 |
||
91 |
("op &", bT --> bT --> bT), |
|
92 |
("op |", bT --> bT --> bT), |
|
93 |
("op -->", bT --> bT --> bT), |
|
94 |
("op =", bT --> bT --> bT), |
|
95 |
("Not", bT --> bT), |
|
96 |
||
97 |
("op <=", iT --> iT --> bT), |
|
98 |
("op =", iT --> iT --> bT), |
|
99 |
("op <", iT --> iT --> bT), |
|
100 |
("Divides.op dvd", iT --> iT --> bT), |
|
101 |
("Divides.op div", iT --> iT --> iT), |
|
102 |
("Divides.op mod", iT --> iT --> iT), |
|
103 |
("op +", iT --> iT --> iT), |
|
104 |
("op -", iT --> iT --> iT), |
|
105 |
("op *", iT --> iT --> iT), |
|
106 |
("HOL.abs", iT --> iT), |
|
107 |
("uminus", iT --> iT), |
|
14801
2d27b5ebc447
- deleted unneeded function eta_long (now in Pure/pattern.ML
berghofe
parents:
14758
diff
changeset
|
108 |
("HOL.max", iT --> iT --> iT), |
2d27b5ebc447
- deleted unneeded function eta_long (now in Pure/pattern.ML
berghofe
parents:
14758
diff
changeset
|
109 |
("HOL.min", iT --> iT --> iT), |
13876 | 110 |
|
111 |
("op <=", nT --> nT --> bT), |
|
112 |
("op =", nT --> nT --> bT), |
|
113 |
("op <", nT --> nT --> bT), |
|
114 |
("Divides.op dvd", nT --> nT --> bT), |
|
115 |
("Divides.op div", nT --> nT --> nT), |
|
116 |
("Divides.op mod", nT --> nT --> nT), |
|
117 |
("op +", nT --> nT --> nT), |
|
118 |
("op -", nT --> nT --> nT), |
|
119 |
("op *", nT --> nT --> nT), |
|
120 |
("Suc", nT --> nT), |
|
14801
2d27b5ebc447
- deleted unneeded function eta_long (now in Pure/pattern.ML
berghofe
parents:
14758
diff
changeset
|
121 |
("HOL.max", nT --> nT --> nT), |
2d27b5ebc447
- deleted unneeded function eta_long (now in Pure/pattern.ML
berghofe
parents:
14758
diff
changeset
|
122 |
("HOL.min", nT --> nT --> nT), |
13876 | 123 |
|
15620
8ccdc8bc66a2
replaced bool by a new datatype "bit" for binary numerals
paulson
parents:
15574
diff
changeset
|
124 |
("Numeral.bit.B0", bitT), |
8ccdc8bc66a2
replaced bool by a new datatype "bit" for binary numerals
paulson
parents:
15574
diff
changeset
|
125 |
("Numeral.bit.B1", bitT), |
8ccdc8bc66a2
replaced bool by a new datatype "bit" for binary numerals
paulson
parents:
15574
diff
changeset
|
126 |
("Numeral.Bit", binT --> bitT --> binT), |
15013 | 127 |
("Numeral.Pls", binT), |
128 |
("Numeral.Min", binT), |
|
13876 | 129 |
("Numeral.number_of", binT --> iT), |
130 |
("Numeral.number_of", binT --> nT), |
|
131 |
("0", nT), |
|
132 |
("0", iT), |
|
133 |
("1", nT), |
|
134 |
("1", iT), |
|
135 |
("False", bT), |
|
136 |
("True", bT)]; |
|
137 |
||
138 |
(* Preparation of the formula to be sent to the Integer quantifier *) |
|
139 |
(* elimination procedure *) |
|
140 |
(* Transforms meta implications and meta quantifiers to object *) |
|
141 |
(* implications and object quantifiers *) |
|
142 |
||
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
143 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
144 |
(*==================================*) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
145 |
(* Abstracting on subterms ========*) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
146 |
(*==================================*) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
147 |
(* Returns occurences of terms that are function application of type int or nat*) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
148 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
149 |
fun getfuncs fm = case strip_comb fm of |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
150 |
(Free (_, T), ts as _ :: _) => |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
151 |
if body_type T mem [iT, nT] |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
152 |
andalso not (ts = []) andalso forall (null o loose_bnos) ts |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
153 |
then [fm] |
15570 | 154 |
else Library.foldl op union ([], map getfuncs ts) |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
155 |
| (Var (_, T), ts as _ :: _) => |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
156 |
if body_type T mem [iT, nT] |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
157 |
andalso not (ts = []) andalso forall (null o loose_bnos) ts then [fm] |
15570 | 158 |
else Library.foldl op union ([], map getfuncs ts) |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
159 |
| (Const (s, T), ts) => |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
160 |
if (s, T) mem allowed_consts orelse not (body_type T mem [iT, nT]) |
15570 | 161 |
then Library.foldl op union ([], map getfuncs ts) |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
162 |
else [fm] |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
163 |
| (Abs (s, T, t), _) => getfuncs t |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
164 |
| _ => []; |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
165 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
166 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
167 |
fun abstract_pres sg fm = |
15574
b1d1b5bfc464
Removed practically all references to Library.foldr.
skalberg
parents:
15570
diff
changeset
|
168 |
foldr (fn (t, u) => |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
169 |
let val T = fastype_of t |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
170 |
in all T $ Abs ("x", T, abstract_over (t, u)) end) |
15574
b1d1b5bfc464
Removed practically all references to Library.foldr.
skalberg
parents:
15570
diff
changeset
|
171 |
fm (getfuncs fm); |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
172 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
173 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
174 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
175 |
(* hasfuncs_on_bounds dont care of the type of the functions applied! |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
176 |
It returns true if there is a subterm coresponding to the application of |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
177 |
a function on a bounded variable. |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
178 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
179 |
Function applications are allowed only for well predefined functions a |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
180 |
consts*) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
181 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
182 |
fun has_free_funcs fm = case strip_comb fm of |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
183 |
(Free (_, T), ts as _ :: _) => |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
184 |
if (body_type T mem [iT,nT]) andalso (not (T mem [iT,nT])) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
185 |
then true |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
186 |
else exists (fn x => x) (map has_free_funcs ts) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
187 |
| (Var (_, T), ts as _ :: _) => |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
188 |
if (body_type T mem [iT,nT]) andalso not (T mem [iT,nT]) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
189 |
then true |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
190 |
else exists (fn x => x) (map has_free_funcs ts) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
191 |
| (Const (s, T), ts) => exists (fn x => x) (map has_free_funcs ts) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
192 |
| (Abs (s, T, t), _) => has_free_funcs t |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
193 |
|_ => false; |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
194 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
195 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
196 |
(*returns true if the formula is relevant for presburger arithmetic tactic |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
197 |
The constants occuring in term t should be a subset of the allowed_consts |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
198 |
There also should be no occurences of application of functions on bounded |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
199 |
variables. Whenever this function will be used, it will be ensured that t |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
200 |
will not contain subterms with function symbols that could have been |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
201 |
abstracted over.*) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
202 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
203 |
fun relevant ps t = (term_typed_consts t) subset allowed_consts andalso |
15570 | 204 |
map (fn i => snd (List.nth (ps, i))) (loose_bnos t) @ |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
205 |
map (snd o dest_Free) (term_frees t) @ map (snd o dest_Var) (term_vars t) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
206 |
subset [iT, nT] |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
207 |
andalso not (has_free_funcs t); |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
208 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
209 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
210 |
fun prepare_for_presburger sg q fm = |
13876 | 211 |
let |
212 |
val ps = Logic.strip_params fm |
|
213 |
val hs = map HOLogic.dest_Trueprop (Logic.strip_assums_hyp fm) |
|
214 |
val c = HOLogic.dest_Trueprop (Logic.strip_assums_concl fm) |
|
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
215 |
val _ = if relevant (rev ps) c then () |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
216 |
else (trace_msg ("Conclusion is not a presburger term:\n" ^ |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
217 |
Sign.string_of_term sg c); raise CooperDec.COOPER) |
13876 | 218 |
fun mk_all ((s, T), (P,n)) = |
219 |
if 0 mem loose_bnos P then |
|
220 |
(HOLogic.all_const T $ Abs (s, T, P), n) |
|
221 |
else (incr_boundvars ~1 P, n-1) |
|
222 |
fun mk_all2 (v, t) = HOLogic.all_const (fastype_of v) $ lambda v t; |
|
15570 | 223 |
val (rhs,irhs) = List.partition (relevant (rev ps)) hs |
13876 | 224 |
val np = length ps |
15574
b1d1b5bfc464
Removed practically all references to Library.foldr.
skalberg
parents:
15570
diff
changeset
|
225 |
val (fm',np) = foldr (fn ((x, T), (fm,n)) => mk_all ((x, T), (fm,n))) |
b1d1b5bfc464
Removed practically all references to Library.foldr.
skalberg
parents:
15570
diff
changeset
|
226 |
(foldr HOLogic.mk_imp c rhs, np) ps |
15570 | 227 |
val (vs, _) = List.partition (fn t => q orelse (type_of t) = nT) |
13876 | 228 |
(term_frees fm' @ term_vars fm'); |
15574
b1d1b5bfc464
Removed practically all references to Library.foldr.
skalberg
parents:
15570
diff
changeset
|
229 |
val fm2 = foldr mk_all2 fm' vs |
13876 | 230 |
in (fm2, np + length vs, length rhs) end; |
231 |
||
232 |
(*Object quantifier to meta --*) |
|
233 |
fun spec_step n th = if (n=0) then th else (spec_step (n-1) th) RS spec ; |
|
234 |
||
235 |
(* object implication to meta---*) |
|
236 |
fun mp_step n th = if (n=0) then th else (mp_step (n-1) th) RS mp; |
|
237 |
||
238 |
(* the presburger tactic*) |
|
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
239 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
240 |
(* Parameters : q = flag for quantify ofer free variables ; |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
241 |
a = flag for abstracting over function occurences |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
242 |
i = subgoal *) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
243 |
|
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
244 |
fun presburger_tac q a i = ObjectLogic.atomize_tac i THEN (fn st => |
13876 | 245 |
let |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
246 |
val g = BasisLibrary.List.nth (prems_of st, i - 1) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
247 |
val sg = sign_of_thm st |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
248 |
(* The Abstraction step *) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
249 |
val g' = if a then abstract_pres sg g else g |
13876 | 250 |
(* Transform the term*) |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
251 |
val (t,np,nh) = prepare_for_presburger sg q g' |
15531 | 252 |
(* SOME simpsets for dealing with mod div abs and nat*) |
13876 | 253 |
val simpset0 = HOL_basic_ss |
254 |
addsimps [mod_div_equality', Suc_plus1] |
|
13997 | 255 |
addsplits [split_zdiv, split_zmod, split_div', split_min, split_max] |
13876 | 256 |
(* Simp rules for changing (n::int) to int n *) |
257 |
val simpset1 = HOL_basic_ss |
|
258 |
addsimps [nat_number_of_def, zdvd_int] @ map (fn r => r RS sym) |
|
259 |
[int_int_eq, zle_int, zless_int, zadd_int, zmult_int] |
|
260 |
addsplits [zdiff_int_split] |
|
261 |
(*simp rules for elimination of int n*) |
|
262 |
||
263 |
val simpset2 = HOL_basic_ss |
|
264 |
addsimps [nat_0_le, all_nat, ex_nat, number_of1, number_of2, int_0, int_1] |
|
265 |
addcongs [conj_le_cong, imp_le_cong] |
|
266 |
(* simp rules for elimination of abs *) |
|
14353
79f9fbef9106
Added lemmas to Ring_and_Field with slightly modified simplification rules
paulson
parents:
14130
diff
changeset
|
267 |
val simpset3 = HOL_basic_ss addsplits [abs_split] |
13876 | 268 |
val ct = cterm_of sg (HOLogic.mk_Trueprop t) |
269 |
(* Theorem for the nat --> int transformation *) |
|
270 |
val pre_thm = Seq.hd (EVERY |
|
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
271 |
[simp_tac simpset0 1, |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
272 |
TRY (simp_tac simpset1 1), TRY (simp_tac simpset2 1), |
14801
2d27b5ebc447
- deleted unneeded function eta_long (now in Pure/pattern.ML
berghofe
parents:
14758
diff
changeset
|
273 |
TRY (simp_tac simpset3 1), TRY (simp_tac presburger_ss 1)] |
13876 | 274 |
(trivial ct)) |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
275 |
fun assm_tac i = REPEAT_DETERM_N nh (assume_tac i) |
13876 | 276 |
(* The result of the quantifier elimination *) |
277 |
val (th, tac) = case (prop_of pre_thm) of |
|
278 |
Const ("==>", _) $ (Const ("Trueprop", _) $ t1) $ _ => |
|
14920
a7525235e20f
An oracle is built in. The tactic will not generate any proofs any more, if the quick_and_dirty flag is set on.
chaieb
parents:
14882
diff
changeset
|
279 |
let val pth = |
a7525235e20f
An oracle is built in. The tactic will not generate any proofs any more, if the quick_and_dirty flag is set on.
chaieb
parents:
14882
diff
changeset
|
280 |
(* If quick_and_dirty then run without proof generation as oracle*) |
a7525235e20f
An oracle is built in. The tactic will not generate any proofs any more, if the quick_and_dirty flag is set on.
chaieb
parents:
14882
diff
changeset
|
281 |
if !quick_and_dirty |
14941 | 282 |
then pres_oracle sg (Pattern.eta_long [] t1) |
283 |
(* |
|
284 |
assume (cterm_of sg |
|
14920
a7525235e20f
An oracle is built in. The tactic will not generate any proofs any more, if the quick_and_dirty flag is set on.
chaieb
parents:
14882
diff
changeset
|
285 |
(HOLogic.mk_Trueprop(HOLogic.mk_eq(t1,CooperDec.integer_qelim (Pattern.eta_long [] t1))))) |
14941 | 286 |
*) |
14920
a7525235e20f
An oracle is built in. The tactic will not generate any proofs any more, if the quick_and_dirty flag is set on.
chaieb
parents:
14882
diff
changeset
|
287 |
else tmproof_of_int_qelim sg (Pattern.eta_long [] t1) |
a7525235e20f
An oracle is built in. The tactic will not generate any proofs any more, if the quick_and_dirty flag is set on.
chaieb
parents:
14882
diff
changeset
|
288 |
in |
13876 | 289 |
(trace_msg ("calling procedure with term:\n" ^ |
290 |
Sign.string_of_term sg t1); |
|
14920
a7525235e20f
An oracle is built in. The tactic will not generate any proofs any more, if the quick_and_dirty flag is set on.
chaieb
parents:
14882
diff
changeset
|
291 |
((pth RS iffD2) RS pre_thm, |
13876 | 292 |
assm_tac (i + 1) THEN (if q then I else TRY) (rtac TrueI i))) |
14920
a7525235e20f
An oracle is built in. The tactic will not generate any proofs any more, if the quick_and_dirty flag is set on.
chaieb
parents:
14882
diff
changeset
|
293 |
end |
13876 | 294 |
| _ => (pre_thm, assm_tac i) |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
295 |
in (rtac (((mp_step nh) o (spec_step np)) th) i |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
296 |
THEN tac) st |
14130 | 297 |
end handle Subscript => no_tac st | CooperDec.COOPER => no_tac st); |
13876 | 298 |
|
299 |
fun presburger_args meth = |
|
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
300 |
let val parse_flag = |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
301 |
Args.$$$ "no_quantify" >> K (apfst (K false)) |
14811
9144ec118703
abstraction over functions is no default any more.
chaieb
parents:
14801
diff
changeset
|
302 |
|| Args.$$$ "abs" >> K (apsnd (K true)); |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
303 |
in |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
304 |
Method.simple_args |
14882 | 305 |
(Scan.optional (Args.$$$ "(" |-- Scan.repeat1 parse_flag --| Args.$$$ ")") [] >> |
15570 | 306 |
curry (Library.foldl op |>) (true, false)) |
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
307 |
(fn (q,a) => fn _ => meth q a 1) |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
308 |
end; |
13876 | 309 |
|
14758
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
310 |
fun presburger_method q a i = Method.METHOD (fn facts => |
af3b71a46a1c
A new implementation for presburger arithmetic following the one suggested in technical report Chaieb Amine and Tobias Nipkow. It is generic an smaller.
chaieb
parents:
14353
diff
changeset
|
311 |
Method.insert_tac facts 1 THEN presburger_tac q a i) |
13876 | 312 |
|
313 |
val setup = |
|
314 |
[Method.add_method ("presburger", |
|
315 |
presburger_args presburger_method, |
|
316 |
"decision procedure for Presburger arithmetic"), |
|
317 |
ArithTheoryData.map (fn {splits, inj_consts, discrete, presburger} => |
|
318 |
{splits = splits, inj_consts = inj_consts, discrete = discrete, |
|
15531 | 319 |
presburger = SOME (presburger_tac true false)})]; |
13876 | 320 |
|
321 |
end; |
|
322 |
||
14920
a7525235e20f
An oracle is built in. The tactic will not generate any proofs any more, if the quick_and_dirty flag is set on.
chaieb
parents:
14882
diff
changeset
|
323 |
val presburger_tac = Presburger.presburger_tac true false; |