59 | Prover of (string -> string) |
65 | Prover of (string -> string) |
60 |
66 |
61 (* Turn a rational into a decimal string with d sig digits. *) |
67 (* Turn a rational into a decimal string with d sig digits. *) |
62 |
68 |
63 local |
69 local |
|
70 |
64 fun normalize y = |
71 fun normalize y = |
65 if abs_rat y </ (rat_1 // rat_10) then normalize (rat_10 */ y) - 1 |
72 if abs_rat y </ (rat_1 // rat_10) then normalize (rat_10 */ y) - 1 |
66 else if abs_rat y >=/ rat_1 then normalize (y // rat_10) + 1 |
73 else if abs_rat y >=/ rat_1 then normalize (y // rat_10) + 1 |
67 else 0 |
74 else 0 |
68 in |
75 |
|
76 in |
|
77 |
69 fun decimalize d x = |
78 fun decimalize d x = |
70 if x =/ rat_0 then "0.0" else |
79 if x =/ rat_0 then "0.0" |
71 let |
80 else |
72 val y = Rat.abs x |
81 let |
73 val e = normalize y |
82 val y = Rat.abs x |
74 val z = pow10(~ e) */ y +/ rat_1 |
83 val e = normalize y |
75 val k = int_of_rat (round_rat(pow10 d */ z)) |
84 val z = pow10(~ e) */ y +/ rat_1 |
76 in (if x </ rat_0 then "-0." else "0.") ^ |
85 val k = int_of_rat (round_rat(pow10 d */ z)) |
77 implode(tl(raw_explode(string_of_int k))) ^ |
86 in |
78 (if e = 0 then "" else "e"^string_of_int e) |
87 (if x </ rat_0 then "-0." else "0.") ^ |
79 end |
88 implode (tl (raw_explode(string_of_int k))) ^ |
|
89 (if e = 0 then "" else "e" ^ string_of_int e) |
|
90 end |
|
91 |
80 end; |
92 end; |
81 |
93 |
82 (* Iterations over numbers, and lists indexed by numbers. *) |
94 (* Iterations over numbers, and lists indexed by numbers. *) |
83 |
95 |
84 fun itern k l f a = |
96 fun itern k l f a = |
85 case l of |
97 (case l of |
86 [] => a |
98 [] => a |
87 | h::t => itern (k + 1) t f (f h k a); |
99 | h::t => itern (k + 1) t f (f h k a)); |
88 |
100 |
89 fun iter (m,n) f a = |
101 fun iter (m,n) f a = |
90 if n < m then a |
102 if n < m then a |
91 else iter (m+1,n) f (f m a); |
103 else iter (m + 1, n) f (f m a); |
92 |
104 |
93 (* The main types. *) |
105 (* The main types. *) |
94 |
106 |
95 type vector = int* Rat.rat FuncUtil.Intfunc.table; |
107 type vector = int * Rat.rat FuncUtil.Intfunc.table; |
96 |
108 |
97 type matrix = (int*int)*(Rat.rat FuncUtil.Intpairfunc.table); |
109 type matrix = (int * int) * Rat.rat FuncUtil.Intpairfunc.table; |
98 |
110 |
99 fun iszero (_,r) = r =/ rat_0; |
111 fun iszero (_, r) = r =/ rat_0; |
100 |
112 |
101 |
113 |
102 (* Vectors. Conventionally indexed 1..n. *) |
114 (* Vectors. Conventionally indexed 1..n. *) |
103 |
115 |
104 fun vector_0 n = (n,FuncUtil.Intfunc.empty):vector; |
116 fun vector_0 n = (n, FuncUtil.Intfunc.empty): vector; |
105 |
117 |
106 fun dim (v:vector) = fst v; |
118 fun dim (v: vector) = fst v; |
107 |
119 |
108 fun vector_cmul c (v:vector) = |
120 fun vector_cmul c (v: vector) = |
109 let val n = dim v |
121 let val n = dim v in |
110 in if c =/ rat_0 then vector_0 n |
122 if c =/ rat_0 then vector_0 n |
111 else (n,FuncUtil.Intfunc.map (fn _ => fn x => c */ x) (snd v)) |
123 else (n,FuncUtil.Intfunc.map (fn _ => fn x => c */ x) (snd v)) |
112 end; |
124 end; |
113 |
125 |
114 fun vector_of_list l = |
126 fun vector_of_list l = |
115 let val n = length l |
127 let val n = length l in |
116 in (n,fold_rev2 (curry FuncUtil.Intfunc.update) (1 upto n) l FuncUtil.Intfunc.empty) :vector |
128 (n, fold_rev2 (curry FuncUtil.Intfunc.update) (1 upto n) l FuncUtil.Intfunc.empty): vector |
117 end; |
129 end; |
118 |
130 |
119 (* Matrices; again rows and columns indexed from 1. *) |
131 (* Matrices; again rows and columns indexed from 1. *) |
120 |
132 |
121 fun dimensions (m:matrix) = fst m; |
133 fun dimensions (m: matrix) = fst m; |
122 |
134 |
123 fun row k (m:matrix) = |
135 fun row k (m: matrix) : vector = |
124 let val (_,j) = dimensions m |
136 let val (_, j) = dimensions m in |
125 in (j, |
137 (j, |
126 FuncUtil.Intpairfunc.fold (fn ((i,j), c) => fn a => if i = k then FuncUtil.Intfunc.update (j,c) a else a) (snd m) FuncUtil.Intfunc.empty ) : vector |
138 FuncUtil.Intpairfunc.fold (fn ((i, j), c) => fn a => |
127 end; |
139 if i = k then FuncUtil.Intfunc.update (j, c) a else a) (snd m) FuncUtil.Intfunc.empty) |
|
140 end; |
128 |
141 |
129 (* Monomials. *) |
142 (* Monomials. *) |
130 |
143 |
131 fun monomial_eval assig m = |
144 fun monomial_eval assig m = |
132 FuncUtil.Ctermfunc.fold (fn (x, k) => fn a => a */ rat_pow (FuncUtil.Ctermfunc.apply assig x) k) |
145 FuncUtil.Ctermfunc.fold (fn (x, k) => fn a => a */ rat_pow (FuncUtil.Ctermfunc.apply assig x) k) |
133 m rat_1; |
146 m rat_1; |
|
147 |
134 val monomial_1 = FuncUtil.Ctermfunc.empty; |
148 val monomial_1 = FuncUtil.Ctermfunc.empty; |
135 |
149 |
136 fun monomial_var x = FuncUtil.Ctermfunc.onefunc (x, 1); |
150 fun monomial_var x = FuncUtil.Ctermfunc.onefunc (x, 1); |
137 |
151 |
138 val monomial_mul = |
152 val monomial_mul = |
139 FuncUtil.Ctermfunc.combine Integer.add (K false); |
153 FuncUtil.Ctermfunc.combine Integer.add (K false); |
140 |
154 |
141 fun monomial_multidegree m = |
155 fun monomial_multidegree m = |
142 FuncUtil.Ctermfunc.fold (fn (_, k) => fn a => k + a) m 0;; |
156 FuncUtil.Ctermfunc.fold (fn (_, k) => fn a => k + a) m 0; |
143 |
157 |
144 fun monomial_variables m = FuncUtil.Ctermfunc.dom m;; |
158 fun monomial_variables m = FuncUtil.Ctermfunc.dom m; |
145 |
159 |
146 (* Polynomials. *) |
160 (* Polynomials. *) |
147 |
161 |
148 fun eval assig p = |
162 fun eval assig p = |
149 FuncUtil.Monomialfunc.fold (fn (m, c) => fn a => a +/ c */ monomial_eval assig m) p rat_0; |
163 FuncUtil.Monomialfunc.fold (fn (m, c) => fn a => a +/ c */ monomial_eval assig m) p rat_0; |
150 |
164 |
151 val poly_0 = FuncUtil.Monomialfunc.empty; |
165 val poly_0 = FuncUtil.Monomialfunc.empty; |
152 |
166 |
153 fun poly_isconst p = |
167 fun poly_isconst p = |
154 FuncUtil.Monomialfunc.fold (fn (m, _) => fn a => FuncUtil.Ctermfunc.is_empty m andalso a) p true; |
168 FuncUtil.Monomialfunc.fold (fn (m, _) => fn a => FuncUtil.Ctermfunc.is_empty m andalso a) |
155 |
169 p true; |
156 fun poly_var x = FuncUtil.Monomialfunc.onefunc (monomial_var x,rat_1); |
170 |
|
171 fun poly_var x = FuncUtil.Monomialfunc.onefunc (monomial_var x, rat_1); |
157 |
172 |
158 fun poly_const c = |
173 fun poly_const c = |
159 if c =/ rat_0 then poly_0 else FuncUtil.Monomialfunc.onefunc(monomial_1, c); |
174 if c =/ rat_0 then poly_0 else FuncUtil.Monomialfunc.onefunc (monomial_1, c); |
160 |
175 |
161 fun poly_cmul c p = |
176 fun poly_cmul c p = |
162 if c =/ rat_0 then poly_0 |
177 if c =/ rat_0 then poly_0 |
163 else FuncUtil.Monomialfunc.map (fn _ => fn x => c */ x) p; |
178 else FuncUtil.Monomialfunc.map (fn _ => fn x => c */ x) p; |
164 |
179 |
165 fun poly_neg p = FuncUtil.Monomialfunc.map (K Rat.neg) p;; |
180 fun poly_neg p = FuncUtil.Monomialfunc.map (K Rat.neg) p; |
|
181 |
166 |
182 |
167 fun poly_add p1 p2 = |
183 fun poly_add p1 p2 = |
168 FuncUtil.Monomialfunc.combine (curry op +/) (fn x => x =/ rat_0) p1 p2; |
184 FuncUtil.Monomialfunc.combine (curry op +/) (fn x => x =/ rat_0) p1 p2; |
169 |
185 |
170 fun poly_sub p1 p2 = poly_add p1 (poly_neg p2); |
186 fun poly_sub p1 p2 = poly_add p1 (poly_neg p2); |
171 |
187 |
172 fun poly_cmmul (c,m) p = |
188 fun poly_cmmul (c,m) p = |
173 if c =/ rat_0 then poly_0 |
189 if c =/ rat_0 then poly_0 |
174 else if FuncUtil.Ctermfunc.is_empty m |
190 else |
175 then FuncUtil.Monomialfunc.map (fn _ => fn d => c */ d) p |
191 if FuncUtil.Ctermfunc.is_empty m |
176 else FuncUtil.Monomialfunc.fold (fn (m', d) => fn a => (FuncUtil.Monomialfunc.update (monomial_mul m m', c */ d) a)) p poly_0; |
192 then FuncUtil.Monomialfunc.map (fn _ => fn d => c */ d) p |
|
193 else |
|
194 FuncUtil.Monomialfunc.fold (fn (m', d) => fn a => |
|
195 (FuncUtil.Monomialfunc.update (monomial_mul m m', c */ d) a)) p poly_0; |
177 |
196 |
178 fun poly_mul p1 p2 = |
197 fun poly_mul p1 p2 = |
179 FuncUtil.Monomialfunc.fold (fn (m, c) => fn a => poly_add (poly_cmmul (c,m) p2) a) p1 poly_0; |
198 FuncUtil.Monomialfunc.fold (fn (m, c) => fn a => poly_add (poly_cmmul (c,m) p2) a) p1 poly_0; |
180 |
199 |
181 fun poly_square p = poly_mul p p; |
200 fun poly_square p = poly_mul p p; |
182 |
201 |
183 fun poly_pow p k = |
202 fun poly_pow p k = |
184 if k = 0 then poly_const rat_1 |
203 if k = 0 then poly_const rat_1 |
185 else if k = 1 then p |
204 else if k = 1 then p |
186 else let val q = poly_square(poly_pow p (k div 2)) in |
205 else |
187 if k mod 2 = 1 then poly_mul p q else q end; |
206 let val q = poly_square(poly_pow p (k div 2)) |
|
207 in if k mod 2 = 1 then poly_mul p q else q end; |
188 |
208 |
189 fun multidegree p = |
209 fun multidegree p = |
190 FuncUtil.Monomialfunc.fold (fn (m, _) => fn a => max (monomial_multidegree m) a) p 0; |
210 FuncUtil.Monomialfunc.fold (fn (m, _) => fn a => max (monomial_multidegree m) a) p 0; |
191 |
211 |
192 fun poly_variables p = |
212 fun poly_variables p = |
193 sort FuncUtil.cterm_ord (FuncUtil.Monomialfunc.fold_rev (fn (m, _) => union (is_equal o FuncUtil.cterm_ord) (monomial_variables m)) p []);; |
213 sort FuncUtil.cterm_ord |
|
214 (FuncUtil.Monomialfunc.fold_rev |
|
215 (fn (m, _) => union (is_equal o FuncUtil.cterm_ord) (monomial_variables m)) p []); |
194 |
216 |
195 (* Conversion from HOL term. *) |
217 (* Conversion from HOL term. *) |
196 |
218 |
197 local |
219 local |
198 val neg_tm = @{cterm "uminus :: real => _"} |
220 val neg_tm = @{cterm "uminus :: real => _"} |
199 val add_tm = @{cterm "op + :: real => _"} |
221 val add_tm = @{cterm "op + :: real => _"} |
200 val sub_tm = @{cterm "op - :: real => _"} |
222 val sub_tm = @{cterm "op - :: real => _"} |
201 val mul_tm = @{cterm "op * :: real => _"} |
223 val mul_tm = @{cterm "op * :: real => _"} |
202 val inv_tm = @{cterm "inverse :: real => _"} |
224 val inv_tm = @{cterm "inverse :: real => _"} |
203 val div_tm = @{cterm "op / :: real => _"} |
225 val div_tm = @{cterm "op / :: real => _"} |
204 val pow_tm = @{cterm "op ^ :: real => _"} |
226 val pow_tm = @{cterm "op ^ :: real => _"} |
205 val zero_tm = @{cterm "0:: real"} |
227 val zero_tm = @{cterm "0:: real"} |
206 val is_numeral = can (HOLogic.dest_number o term_of) |
228 val is_numeral = can (HOLogic.dest_number o term_of) |
207 fun poly_of_term tm = |
229 fun poly_of_term tm = |
208 if tm aconvc zero_tm then poly_0 |
230 if tm aconvc zero_tm then poly_0 |
209 else if RealArith.is_ratconst tm |
231 else |
210 then poly_const(RealArith.dest_ratconst tm) |
232 if RealArith.is_ratconst tm |
211 else |
233 then poly_const(RealArith.dest_ratconst tm) |
212 (let val (lop,r) = Thm.dest_comb tm |
234 else |
213 in if lop aconvc neg_tm then poly_neg(poly_of_term r) |
235 (let |
214 else if lop aconvc inv_tm then |
236 val (lop, r) = Thm.dest_comb tm |
215 let val p = poly_of_term r |
237 in |
216 in if poly_isconst p |
238 if lop aconvc neg_tm then poly_neg(poly_of_term r) |
217 then poly_const(Rat.inv (eval FuncUtil.Ctermfunc.empty p)) |
239 else if lop aconvc inv_tm then |
218 else error "poly_of_term: inverse of non-constant polyomial" |
240 let val p = poly_of_term r in |
219 end |
241 if poly_isconst p |
220 else (let val (opr,l) = Thm.dest_comb lop |
242 then poly_const(Rat.inv (eval FuncUtil.Ctermfunc.empty p)) |
221 in |
243 else error "poly_of_term: inverse of non-constant polyomial" |
222 if opr aconvc pow_tm andalso is_numeral r |
244 end |
223 then poly_pow (poly_of_term l) ((snd o HOLogic.dest_number o term_of) r) |
245 else |
224 else if opr aconvc add_tm |
246 (let |
225 then poly_add (poly_of_term l) (poly_of_term r) |
247 val (opr,l) = Thm.dest_comb lop |
226 else if opr aconvc sub_tm |
248 in |
227 then poly_sub (poly_of_term l) (poly_of_term r) |
249 if opr aconvc pow_tm andalso is_numeral r |
228 else if opr aconvc mul_tm |
250 then poly_pow (poly_of_term l) ((snd o HOLogic.dest_number o term_of) r) |
229 then poly_mul (poly_of_term l) (poly_of_term r) |
251 else if opr aconvc add_tm |
230 else if opr aconvc div_tm |
252 then poly_add (poly_of_term l) (poly_of_term r) |
231 then let |
253 else if opr aconvc sub_tm |
|
254 then poly_sub (poly_of_term l) (poly_of_term r) |
|
255 else if opr aconvc mul_tm |
|
256 then poly_mul (poly_of_term l) (poly_of_term r) |
|
257 else if opr aconvc div_tm |
|
258 then |
|
259 let |
232 val p = poly_of_term l |
260 val p = poly_of_term l |
233 val q = poly_of_term r |
261 val q = poly_of_term r |
234 in if poly_isconst q then poly_cmul (Rat.inv (eval FuncUtil.Ctermfunc.empty q)) p |
262 in |
235 else error "poly_of_term: division by non-constant polynomial" |
263 if poly_isconst q |
|
264 then poly_cmul (Rat.inv (eval FuncUtil.Ctermfunc.empty q)) p |
|
265 else error "poly_of_term: division by non-constant polynomial" |
236 end |
266 end |
237 else poly_var tm |
267 else poly_var tm |
238 |
268 end handle CTERM ("dest_comb",_) => poly_var tm) |
239 end |
269 end handle CTERM ("dest_comb",_) => poly_var tm) |
240 handle CTERM ("dest_comb",_) => poly_var tm) |
|
241 end |
|
242 handle CTERM ("dest_comb",_) => poly_var tm) |
|
243 in |
270 in |
244 val poly_of_term = fn tm => |
271 val poly_of_term = fn tm => |
245 if type_of (term_of tm) = @{typ real} then poly_of_term tm |
272 if type_of (term_of tm) = @{typ real} |
246 else error "poly_of_term: term does not have real type" |
273 then poly_of_term tm |
|
274 else error "poly_of_term: term does not have real type" |
247 end; |
275 end; |
248 |
276 |
249 (* String of vector (just a list of space-separated numbers). *) |
277 (* String of vector (just a list of space-separated numbers). *) |
250 |
278 |
251 fun sdpa_of_vector (v:vector) = |
279 fun sdpa_of_vector (v: vector) = |
252 let |
280 let |
253 val n = dim v |
281 val n = dim v |
254 val strs = map (decimalize 20 o (fn i => FuncUtil.Intfunc.tryapplyd (snd v) i rat_0)) (1 upto n) |
282 val strs = |
255 in space_implode " " strs ^ "\n" |
283 map (decimalize 20 o (fn i => FuncUtil.Intfunc.tryapplyd (snd v) i rat_0)) (1 upto n) |
256 end; |
284 in space_implode " " strs ^ "\n" end; |
257 |
285 |
258 fun triple_int_ord ((a,b,c),(a',b',c')) = |
286 fun triple_int_ord ((a, b, c), (a', b', c')) = |
259 prod_ord int_ord (prod_ord int_ord int_ord) |
287 prod_ord int_ord (prod_ord int_ord int_ord) ((a, (b, c)), (a', (b', c'))); |
260 ((a,(b,c)),(a',(b',c'))); |
288 structure Inttriplefunc = FuncFun(type key = int * int * int val ord = triple_int_ord); |
261 structure Inttriplefunc = FuncFun(type key = int*int*int val ord = triple_int_ord); |
|
262 |
289 |
263 fun index_char str chr pos = |
290 fun index_char str chr pos = |
264 if pos >= String.size str then ~1 |
291 if pos >= String.size str then ~1 |
265 else if String.sub(str,pos) = chr then pos |
292 else if String.sub(str,pos) = chr then pos |
266 else index_char str chr (pos + 1); |
293 else index_char str chr (pos + 1); |
267 fun rat_of_quotient (a,b) = if b = 0 then rat_0 else Rat.rat_of_quotient (a,b); |
294 |
|
295 fun rat_of_quotient (a,b) = |
|
296 if b = 0 then rat_0 else Rat.rat_of_quotient (a, b); |
|
297 |
268 fun rat_of_string s = |
298 fun rat_of_string s = |
269 let val n = index_char s #"/" 0 in |
299 let val n = index_char s #"/" 0 in |
270 if n = ~1 then s |> Int.fromString |> the |> Rat.rat_of_int |
300 if n = ~1 then s |> Int.fromString |> the |> Rat.rat_of_int |
271 else |
301 else |
272 let val SOME numer = Int.fromString(String.substring(s,0,n)) |
302 let |
273 val SOME den = Int.fromString (String.substring(s,n+1,String.size s - n - 1)) |
303 val SOME numer = Int.fromString(String.substring(s,0,n)) |
274 in rat_of_quotient(numer, den) |
304 val SOME den = Int.fromString (String.substring(s,n+1,String.size s - n - 1)) |
275 end |
305 in rat_of_quotient(numer, den) end |
276 end; |
306 end; |
277 |
307 |
278 |
308 |
279 fun isnum x = member (op =) ["0","1","2","3","4","5","6","7","8","9"] x; |
309 fun isnum x = member (op =) ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"] x; |
280 |
310 |
281 (* More parser basics. *) |
311 (* More parser basics. *) |
282 (* FIXME improper use of parser combinators ahead *) |
312 (* FIXME improper use of parser combinators ahead *) |
283 |
313 |
284 val numeral = Scan.one isnum |
314 val numeral = Scan.one isnum |
285 val decimalint = Scan.repeat1 numeral >> (rat_of_string o implode) |
315 val decimalint = Scan.repeat1 numeral >> (rat_of_string o implode) |
286 val decimalfrac = Scan.repeat1 numeral |
316 val decimalfrac = Scan.repeat1 numeral |
287 >> (fn s => rat_of_string(implode s) // pow10 (length s)) |
317 >> (fn s => rat_of_string(implode s) // pow10 (length s)) |
288 val decimalsig = |
318 val decimalsig = |
289 decimalint -- Scan.option (Scan.$$ "." |-- decimalfrac) |
319 decimalint -- Scan.option (Scan.$$ "." |-- decimalfrac) |
290 >> (fn (h,NONE) => h | (h,SOME x) => h +/ x) |
320 >> (fn (h,NONE) => h | (h,SOME x) => h +/ x) |
291 fun signed prs = |
321 fun signed prs = |
292 $$ "-" |-- prs >> Rat.neg |
322 $$ "-" |-- prs >> Rat.neg |
293 || $$ "+" |-- prs |
323 || $$ "+" |-- prs |
294 || prs; |
324 || prs; |
295 |
325 |
296 fun emptyin def xs = if null xs then (def,xs) else Scan.fail xs |
326 fun emptyin def xs = if null xs then (def, xs) else Scan.fail xs |
297 |
327 |
298 val exponent = ($$ "e" || $$ "E") |-- signed decimalint; |
328 val exponent = ($$ "e" || $$ "E") |-- signed decimalint; |
299 |
329 |
300 val decimal = signed decimalsig -- (emptyin rat_0|| exponent) |
330 val decimal = signed decimalsig -- (emptyin rat_0|| exponent) |
301 >> (fn (h, x) => h */ pow10 (int_of_rat x)); |
331 >> (fn (h, x) => h */ pow10 (int_of_rat x)); |
302 |
332 |
303 fun mkparser p s = |
333 fun mkparser p s = |
304 let val (x,rst) = p (raw_explode s) |
334 let val (x,rst) = p (raw_explode s) |
305 in if null rst then x |
335 in if null rst then x else error "mkparser: unparsed input" end; |
306 else error "mkparser: unparsed input" |
|
307 end;; |
|
308 |
336 |
309 (* Parse back csdp output. *) |
337 (* Parse back csdp output. *) |
310 (* FIXME improper use of parser combinators ahead *) |
338 (* FIXME improper use of parser combinators ahead *) |
311 |
339 |
312 fun ignore _ = ((),[]) |
340 fun ignore _ = ((),[]) |
313 fun csdpoutput inp = |
341 fun csdpoutput inp = |
314 ((decimal -- Scan.repeat (Scan.$$ " " |-- Scan.option decimal) >> |
342 ((decimal -- Scan.repeat (Scan.$$ " " |-- Scan.option decimal) >> |
315 (fn (h,to) => map_filter I ((SOME h)::to))) --| ignore >> vector_of_list) inp |
343 (fn (h,to) => map_filter I ((SOME h)::to))) --| ignore >> vector_of_list) inp |
316 val parse_csdpoutput = mkparser csdpoutput |
344 val parse_csdpoutput = mkparser csdpoutput |
317 |
345 |
318 (* Try some apparently sensible scaling first. Note that this is purely to *) |
346 (* Try some apparently sensible scaling first. Note that this is purely to *) |
319 (* get a cleaner translation to floating-point, and doesn't affect any of *) |
347 (* get a cleaner translation to floating-point, and doesn't affect any of *) |
320 (* the results, in principle. In practice it seems a lot better when there *) |
348 (* the results, in principle. In practice it seems a lot better when there *) |
321 (* are extreme numbers in the original problem. *) |
349 (* are extreme numbers in the original problem. *) |
322 |
350 |
323 (* Version for (int*int*int) keys *) |
351 (* Version for (int*int*int) keys *) |
324 local |
352 local |
325 fun max_rat x y = if x </ y then y else x |
353 fun max_rat x y = if x </ y then y else x |
326 fun common_denominator fld amat acc = |
354 fun common_denominator fld amat acc = |
327 fld (fn (_,c) => fn a => lcm_rat (denominator_rat c) a) amat acc |
355 fld (fn (_,c) => fn a => lcm_rat (denominator_rat c) a) amat acc |
328 fun maximal_element fld amat acc = |
356 fun maximal_element fld amat acc = |
329 fld (fn (_,c) => fn maxa => max_rat maxa (abs_rat c)) amat acc |
357 fld (fn (_,c) => fn maxa => max_rat maxa (abs_rat c)) amat acc |
330 fun float_of_rat x = let val (a,b) = Rat.quotient_of_rat x |
358 fun float_of_rat x = |
331 in Real.fromInt a / Real.fromInt b end; |
359 let val (a,b) = Rat.quotient_of_rat x |
332 fun int_of_float x = (trunc x handle Overflow => 0 | Domain => 0) |
360 in Real.fromInt a / Real.fromInt b end; |
|
361 fun int_of_float x = (trunc x handle Overflow => 0 | Domain => 0) |
333 in |
362 in |
334 |
363 |
335 fun tri_scale_then solver (obj:vector) mats = |
364 fun tri_scale_then solver (obj:vector) mats = |
336 let |
365 let |
337 val cd1 = fold_rev (common_denominator Inttriplefunc.fold) mats (rat_1) |
366 val cd1 = fold_rev (common_denominator Inttriplefunc.fold) mats (rat_1) |
338 val cd2 = common_denominator FuncUtil.Intfunc.fold (snd obj) (rat_1) |
367 val cd2 = common_denominator FuncUtil.Intfunc.fold (snd obj) (rat_1) |
339 val mats' = map (Inttriplefunc.map (fn _ => fn x => cd1 */ x)) mats |
368 val mats' = map (Inttriplefunc.map (fn _ => fn x => cd1 */ x)) mats |
340 val obj' = vector_cmul cd2 obj |
369 val obj' = vector_cmul cd2 obj |
341 val max1 = fold_rev (maximal_element Inttriplefunc.fold) mats' (rat_0) |
370 val max1 = fold_rev (maximal_element Inttriplefunc.fold) mats' (rat_0) |
342 val max2 = maximal_element FuncUtil.Intfunc.fold (snd obj') (rat_0) |
371 val max2 = maximal_element FuncUtil.Intfunc.fold (snd obj') (rat_0) |
343 val scal1 = pow2 (20 - int_of_float(Math.ln (float_of_rat max1) / Math.ln 2.0)) |
372 val scal1 = pow2 (20 - int_of_float(Math.ln (float_of_rat max1) / Math.ln 2.0)) |
344 val scal2 = pow2 (20 - int_of_float(Math.ln (float_of_rat max2) / Math.ln 2.0)) |
373 val scal2 = pow2 (20 - int_of_float(Math.ln (float_of_rat max2) / Math.ln 2.0)) |
345 val mats'' = map (Inttriplefunc.map (fn _ => fn x => x */ scal1)) mats' |
374 val mats'' = map (Inttriplefunc.map (fn _ => fn x => x */ scal1)) mats' |
346 val obj'' = vector_cmul scal2 obj' |
375 val obj'' = vector_cmul scal2 obj' |
347 in solver obj'' mats'' |
376 in solver obj'' mats'' end |
348 end |
|
349 end; |
377 end; |
350 |
378 |
351 (* Round a vector to "nice" rationals. *) |
379 (* Round a vector to "nice" rationals. *) |
352 |
380 |
353 fun nice_rational n x = round_rat (n */ x) // n;; |
381 fun nice_rational n x = round_rat (n */ x) // n; |
354 fun nice_vector n ((d,v) : vector) = |
382 fun nice_vector n ((d,v) : vector) = |
355 (d, FuncUtil.Intfunc.fold (fn (i,c) => fn a => |
383 (d, FuncUtil.Intfunc.fold (fn (i,c) => fn a => |
356 let val y = nice_rational n c |
384 let val y = nice_rational n c in |
357 in if c =/ rat_0 then a |
385 if c =/ rat_0 then a |
358 else FuncUtil.Intfunc.update (i,y) a end) v FuncUtil.Intfunc.empty):vector |
386 else FuncUtil.Intfunc.update (i,y) a |
|
387 end) v FuncUtil.Intfunc.empty): vector |
359 |
388 |
360 fun dest_ord f x = is_equal (f x); |
389 fun dest_ord f x = is_equal (f x); |
361 |
390 |
362 (* Stuff for "equations" ((int*int*int)->num functions). *) |
391 (* Stuff for "equations" ((int*int*int)->num functions). *) |
363 |
392 |
364 fun tri_equation_cmul c eq = |
393 fun tri_equation_cmul c eq = |
365 if c =/ rat_0 then Inttriplefunc.empty else Inttriplefunc.map (fn _ => fn d => c */ d) eq; |
394 if c =/ rat_0 then Inttriplefunc.empty |
366 |
395 else Inttriplefunc.map (fn _ => fn d => c */ d) eq; |
367 fun tri_equation_add eq1 eq2 = Inttriplefunc.combine (curry op +/) (fn x => x =/ rat_0) eq1 eq2; |
396 |
|
397 fun tri_equation_add eq1 eq2 = |
|
398 Inttriplefunc.combine (curry op +/) (fn x => x =/ rat_0) eq1 eq2; |
368 |
399 |
369 fun tri_equation_eval assig eq = |
400 fun tri_equation_eval assig eq = |
370 let fun value v = Inttriplefunc.apply assig v |
401 let |
371 in Inttriplefunc.fold (fn (v, c) => fn a => a +/ value v */ c) eq rat_0 |
402 fun value v = Inttriplefunc.apply assig v |
372 end; |
403 in Inttriplefunc.fold (fn (v, c) => fn a => a +/ value v */ c) eq rat_0 end; |
373 |
404 |
374 (* Eliminate all variables, in an essentially arbitrary order. *) |
405 (* Eliminate all variables, in an essentially arbitrary order. *) |
375 |
406 |
376 fun tri_eliminate_all_equations one = |
407 fun tri_eliminate_all_equations one = |
377 let |
408 let |
378 fun choose_variable eq = |
409 fun choose_variable eq = |
379 let val (v,_) = Inttriplefunc.choose eq |
410 let val (v,_) = Inttriplefunc.choose eq |
380 in if is_equal (triple_int_ord(v,one)) then |
411 in |
381 let val eq' = Inttriplefunc.delete_safe v eq |
412 if is_equal (triple_int_ord(v,one)) then |
382 in if Inttriplefunc.is_empty eq' then error "choose_variable" |
413 let |
383 else fst (Inttriplefunc.choose eq') |
414 val eq' = Inttriplefunc.delete_safe v eq |
|
415 in |
|
416 if Inttriplefunc.is_empty eq' then error "choose_variable" |
|
417 else fst (Inttriplefunc.choose eq') |
|
418 end |
|
419 else v |
384 end |
420 end |
385 else v |
421 |
386 end |
422 fun eliminate dun eqs = |
387 fun eliminate dun eqs = case eqs of |
423 (case eqs of |
388 [] => dun |
424 [] => dun |
389 | eq::oeqs => |
425 | eq :: oeqs => |
390 if Inttriplefunc.is_empty eq then eliminate dun oeqs else |
426 if Inttriplefunc.is_empty eq then eliminate dun oeqs |
391 let val v = choose_variable eq |
427 else |
392 val a = Inttriplefunc.apply eq v |
428 let |
393 val eq' = tri_equation_cmul ((Rat.rat_of_int ~1) // a) |
429 val v = choose_variable eq |
394 (Inttriplefunc.delete_safe v eq) |
430 val a = Inttriplefunc.apply eq v |
395 fun elim e = |
431 val eq' = |
396 let val b = Inttriplefunc.tryapplyd e v rat_0 |
432 tri_equation_cmul ((Rat.rat_of_int ~1) // a) (Inttriplefunc.delete_safe v eq) |
397 in if b =/ rat_0 then e |
433 fun elim e = |
398 else tri_equation_add e (tri_equation_cmul (Rat.neg b // a) eq) |
434 let val b = Inttriplefunc.tryapplyd e v rat_0 in |
399 end |
435 if b =/ rat_0 then e |
400 in eliminate (Inttriplefunc.update(v, eq') (Inttriplefunc.map (K elim) dun)) |
436 else tri_equation_add e (tri_equation_cmul (Rat.neg b // a) eq) |
401 (map elim oeqs) |
437 end |
402 end |
438 in |
403 in fn eqs => |
439 eliminate (Inttriplefunc.update(v, eq') (Inttriplefunc.map (K elim) dun)) |
404 let |
440 (map elim oeqs) |
405 val assig = eliminate Inttriplefunc.empty eqs |
441 end) |
406 val vs = Inttriplefunc.fold (fn (_, f) => fn a => remove (dest_ord triple_int_ord) one (Inttriplefunc.dom f) @ a) assig [] |
442 in |
407 in (distinct (dest_ord triple_int_ord) vs,assig) |
443 fn eqs => |
408 end |
444 let |
409 end; |
445 val assig = eliminate Inttriplefunc.empty eqs |
|
446 val vs = Inttriplefunc.fold (fn (_, f) => fn a => |
|
447 remove (dest_ord triple_int_ord) one (Inttriplefunc.dom f) @ a) assig [] |
|
448 in (distinct (dest_ord triple_int_ord) vs,assig) end |
|
449 end; |
410 |
450 |
411 (* Multiply equation-parametrized poly by regular poly and add accumulator. *) |
451 (* Multiply equation-parametrized poly by regular poly and add accumulator. *) |
412 |
452 |
413 fun tri_epoly_pmul p q acc = |
453 fun tri_epoly_pmul p q acc = |
414 FuncUtil.Monomialfunc.fold (fn (m1, c) => fn a => |
454 FuncUtil.Monomialfunc.fold (fn (m1, c) => fn a => |
415 FuncUtil.Monomialfunc.fold (fn (m2,e) => fn b => |
455 FuncUtil.Monomialfunc.fold (fn (m2, e) => fn b => |
416 let val m = monomial_mul m1 m2 |
456 let |
417 val es = FuncUtil.Monomialfunc.tryapplyd b m Inttriplefunc.empty |
457 val m = monomial_mul m1 m2 |
418 in FuncUtil.Monomialfunc.update (m,tri_equation_add (tri_equation_cmul c e) es) b |
458 val es = FuncUtil.Monomialfunc.tryapplyd b m Inttriplefunc.empty |
419 end) q a) p acc ; |
459 in |
|
460 FuncUtil.Monomialfunc.update (m,tri_equation_add (tri_equation_cmul c e) es) b |
|
461 end) q a) p acc; |
420 |
462 |
421 (* Hence produce the "relevant" monomials: those whose squares lie in the *) |
463 (* Hence produce the "relevant" monomials: those whose squares lie in the *) |
422 (* Newton polytope of the monomials in the input. (This is enough according *) |
464 (* Newton polytope of the monomials in the input. (This is enough according *) |
423 (* to Reznik: "Extremal PSD forms with few terms", Duke Math. Journal, *) |
465 (* to Reznik: "Extremal PSD forms with few terms", Duke Math. Journal, *) |
424 (* vol 45, pp. 363--374, 1978. *) |
466 (* vol 45, pp. 363--374, 1978. *) |
428 (* quadratic form that will tend to display constants. *) |
470 (* quadratic form that will tend to display constants. *) |
429 |
471 |
430 (* Diagonalize (Cholesky/LDU) the matrix corresponding to a quadratic form. *) |
472 (* Diagonalize (Cholesky/LDU) the matrix corresponding to a quadratic form. *) |
431 |
473 |
432 local |
474 local |
433 fun diagonalize n i m = |
475 fun diagonalize n i m = |
434 if FuncUtil.Intpairfunc.is_empty (snd m) then [] |
476 if FuncUtil.Intpairfunc.is_empty (snd m) then [] |
435 else |
477 else |
436 let val a11 = FuncUtil.Intpairfunc.tryapplyd (snd m) (i,i) rat_0 |
478 let |
437 in if a11 </ rat_0 then raise Failure "diagonalize: not PSD" |
479 val a11 = FuncUtil.Intpairfunc.tryapplyd (snd m) (i,i) rat_0 |
438 else if a11 =/ rat_0 then |
480 in |
439 if FuncUtil.Intfunc.is_empty (snd (row i m)) then diagonalize n (i + 1) m |
481 if a11 </ rat_0 then raise Failure "diagonalize: not PSD" |
|
482 else if a11 =/ rat_0 then |
|
483 if FuncUtil.Intfunc.is_empty (snd (row i m)) |
|
484 then diagonalize n (i + 1) m |
440 else raise Failure "diagonalize: not PSD ___ " |
485 else raise Failure "diagonalize: not PSD ___ " |
441 else |
486 else |
442 let |
487 let |
443 val v = row i m |
488 val v = row i m |
444 val v' = (fst v, FuncUtil.Intfunc.fold (fn (i, c) => fn a => |
489 val v' = |
445 let val y = c // a11 |
490 (fst v, FuncUtil.Intfunc.fold (fn (i, c) => fn a => |
446 in if y = rat_0 then a else FuncUtil.Intfunc.update (i,y) a |
491 let val y = c // a11 |
447 end) (snd v) FuncUtil.Intfunc.empty) |
492 in if y = rat_0 then a else FuncUtil.Intfunc.update (i,y) a |
448 fun upt0 x y a = if y = rat_0 then a else FuncUtil.Intpairfunc.update (x,y) a |
493 end) (snd v) FuncUtil.Intfunc.empty) |
449 val m' = |
494 fun upt0 x y a = |
450 ((n,n), |
495 if y = rat_0 then a |
451 iter (i+1,n) (fn j => |
496 else FuncUtil.Intpairfunc.update (x,y) a |
452 iter (i+1,n) (fn k => |
497 val m' = |
453 (upt0 (j,k) (FuncUtil.Intpairfunc.tryapplyd (snd m) (j,k) rat_0 -/ FuncUtil.Intfunc.tryapplyd (snd v) j rat_0 */ FuncUtil.Intfunc.tryapplyd (snd v') k rat_0)))) |
498 ((n, n), |
454 FuncUtil.Intpairfunc.empty) |
499 iter (i + 1, n) (fn j => |
455 in (a11,v')::diagonalize n (i + 1) m' |
500 iter (i + 1, n) (fn k => |
456 end |
501 (upt0 (j, k) |
457 end |
502 (FuncUtil.Intpairfunc.tryapplyd (snd m) (j, k) rat_0 -/ |
|
503 FuncUtil.Intfunc.tryapplyd (snd v) j rat_0 */ |
|
504 FuncUtil.Intfunc.tryapplyd (snd v') k rat_0)))) |
|
505 FuncUtil.Intpairfunc.empty) |
|
506 in (a11, v') :: diagonalize n (i + 1) m' end |
|
507 end |
458 in |
508 in |
459 fun diag m = |
509 fun diag m = |
460 let |
510 let |
461 val nn = dimensions m |
511 val nn = dimensions m |
462 val n = fst nn |
512 val n = fst nn |
463 in if snd nn <> n then error "diagonalize: non-square matrix" |
513 in |
464 else diagonalize n 1 m |
514 if snd nn <> n then error "diagonalize: non-square matrix" |
465 end |
515 else diagonalize n 1 m |
|
516 end |
466 end; |
517 end; |
467 |
518 |
468 (* Enumeration of monomials with given multidegree bound. *) |
519 (* Enumeration of monomials with given multidegree bound. *) |
469 |
520 |
470 fun enumerate_monomials d vars = |
521 fun enumerate_monomials d vars = |
471 if d < 0 then [] |
522 if d < 0 then [] |
472 else if d = 0 then [FuncUtil.Ctermfunc.empty] |
523 else if d = 0 then [FuncUtil.Ctermfunc.empty] |
473 else if null vars then [monomial_1] else |
524 else if null vars then [monomial_1] |
474 let val alts = |
525 else |
475 map_range (fn k => let val oths = enumerate_monomials (d - k) (tl vars) |
526 let val alts = |
476 in map (fn ks => if k = 0 then ks else FuncUtil.Ctermfunc.update (hd vars, k) ks) oths end) (d + 1) |
527 map_range (fn k => |
477 in flat alts |
528 let |
478 end; |
529 val oths = enumerate_monomials (d - k) (tl vars) |
|
530 in map (fn ks => if k = 0 then ks else FuncUtil.Ctermfunc.update (hd vars, k) ks) oths end) |
|
531 (d + 1) |
|
532 in flat alts end; |
479 |
533 |
480 (* Enumerate products of distinct input polys with degree <= d. *) |
534 (* Enumerate products of distinct input polys with degree <= d. *) |
481 (* We ignore any constant input polynomials. *) |
535 (* We ignore any constant input polynomials. *) |
482 (* Give the output polynomial and a record of how it was derived. *) |
536 (* Give the output polynomial and a record of how it was derived. *) |
483 |
537 |
484 fun enumerate_products d pols = |
538 fun enumerate_products d pols = |
485 if d = 0 then [(poly_const rat_1,RealArith.Rational_lt rat_1)] |
539 if d = 0 then [(poly_const rat_1,RealArith.Rational_lt rat_1)] |
486 else if d < 0 then [] else |
540 else if d < 0 then [] |
487 case pols of |
541 else |
488 [] => [(poly_const rat_1,RealArith.Rational_lt rat_1)] |
542 (case pols of |
489 | (p,b)::ps => |
543 [] => [(poly_const rat_1, RealArith.Rational_lt rat_1)] |
490 let val e = multidegree p |
544 | (p, b) :: ps => |
491 in if e = 0 then enumerate_products d ps else |
545 let val e = multidegree p in |
492 enumerate_products d ps @ |
546 if e = 0 then enumerate_products d ps |
493 map (fn (q,c) => (poly_mul p q,RealArith.Product(b,c))) |
547 else |
494 (enumerate_products (d - e) ps) |
548 enumerate_products d ps @ |
495 end |
549 map (fn (q, c) => (poly_mul p q, RealArith.Product (b, c))) |
|
550 (enumerate_products (d - e) ps) |
|
551 end) |
496 |
552 |
497 (* Convert regular polynomial. Note that we treat (0,0,0) as -1. *) |
553 (* Convert regular polynomial. Note that we treat (0,0,0) as -1. *) |
498 |
554 |
499 fun epoly_of_poly p = |
555 fun epoly_of_poly p = |
500 FuncUtil.Monomialfunc.fold (fn (m,c) => fn a => FuncUtil.Monomialfunc.update (m, Inttriplefunc.onefunc ((0,0,0), Rat.neg c)) a) p FuncUtil.Monomialfunc.empty; |
556 FuncUtil.Monomialfunc.fold (fn (m, c) => fn a => |
|
557 FuncUtil.Monomialfunc.update (m, Inttriplefunc.onefunc ((0, 0, 0), Rat.neg c)) a) |
|
558 p FuncUtil.Monomialfunc.empty; |
501 |
559 |
502 (* String for block diagonal matrix numbered k. *) |
560 (* String for block diagonal matrix numbered k. *) |
503 |
561 |
504 fun sdpa_of_blockdiagonal k m = |
562 fun sdpa_of_blockdiagonal k m = |
505 let |
563 let |
506 val pfx = string_of_int k ^" " |
564 val pfx = string_of_int k ^" " |
507 val ents = |
565 val ents = |
508 Inttriplefunc.fold |
566 Inttriplefunc.fold |
509 (fn ((b,i,j),c) => fn a => if i > j then a else ((b,i,j),c)::a) |
567 (fn ((b, i, j), c) => fn a => if i > j then a else ((b, i, j), c) :: a) |
510 m [] |
568 m [] |
511 val entss = sort (triple_int_ord o pairself fst) ents |
569 val entss = sort (triple_int_ord o pairself fst) ents |
512 in fold_rev (fn ((b,i,j),c) => fn a => |
570 in |
513 pfx ^ string_of_int b ^ " " ^ string_of_int i ^ " " ^ string_of_int j ^ |
571 fold_rev (fn ((b,i,j),c) => fn a => |
514 " " ^ decimalize 20 c ^ "\n" ^ a) entss "" |
572 pfx ^ string_of_int b ^ " " ^ string_of_int i ^ " " ^ string_of_int j ^ |
515 end; |
573 " " ^ decimalize 20 c ^ "\n" ^ a) entss "" |
|
574 end; |
516 |
575 |
517 (* SDPA for problem using block diagonal (i.e. multiple SDPs) *) |
576 (* SDPA for problem using block diagonal (i.e. multiple SDPs) *) |
518 |
577 |
519 fun sdpa_of_blockproblem nblocks blocksizes obj mats = |
578 fun sdpa_of_blockproblem nblocks blocksizes obj mats = |
520 let val m = length mats - 1 |
579 let val m = length mats - 1 |
521 in |
580 in |
522 string_of_int m ^ "\n" ^ |
581 string_of_int m ^ "\n" ^ |
523 string_of_int nblocks ^ "\n" ^ |
582 string_of_int nblocks ^ "\n" ^ |
524 (space_implode " " (map string_of_int blocksizes)) ^ |
583 (space_implode " " (map string_of_int blocksizes)) ^ |
525 "\n" ^ |
584 "\n" ^ |
526 sdpa_of_vector obj ^ |
585 sdpa_of_vector obj ^ |
527 fold_rev2 (fn k => fn m => fn a => sdpa_of_blockdiagonal (k - 1) m ^ a) |
586 fold_rev2 (fn k => fn m => fn a => sdpa_of_blockdiagonal (k - 1) m ^ a) |
528 (1 upto length mats) mats "" |
587 (1 upto length mats) mats "" |
529 end; |
588 end; |
530 |
589 |
531 (* Run prover on a problem in block diagonal form. *) |
590 (* Run prover on a problem in block diagonal form. *) |
532 |
591 |
533 fun run_blockproblem prover nblocks blocksizes obj mats= |
592 fun run_blockproblem prover nblocks blocksizes obj mats = |
534 parse_csdpoutput (prover (sdpa_of_blockproblem nblocks blocksizes obj mats)) |
593 parse_csdpoutput (prover (sdpa_of_blockproblem nblocks blocksizes obj mats)) |
535 |
594 |
536 (* 3D versions of matrix operations to consider blocks separately. *) |
595 (* 3D versions of matrix operations to consider blocks separately. *) |
537 |
596 |
538 val bmatrix_add = Inttriplefunc.combine (curry op +/) (fn x => x =/ rat_0); |
597 val bmatrix_add = Inttriplefunc.combine (curry op +/) (fn x => x =/ rat_0); |
560 fun tryfind f = tryfind_with "tryfind" f |
623 fun tryfind f = tryfind_with "tryfind" f |
561 end |
624 end |
562 |
625 |
563 (* Positiv- and Nullstellensatz. Flag "linf" forces a linear representation. *) |
626 (* Positiv- and Nullstellensatz. Flag "linf" forces a linear representation. *) |
564 |
627 |
565 |
|
566 fun real_positivnullstellensatz_general ctxt prover linf d eqs leqs pol = |
628 fun real_positivnullstellensatz_general ctxt prover linf d eqs leqs pol = |
567 let |
629 let |
568 val vars = fold_rev (union (op aconvc) o poly_variables) |
630 val vars = |
569 (pol :: eqs @ map fst leqs) [] |
631 fold_rev (union (op aconvc) o poly_variables) |
570 val monoid = if linf then |
632 (pol :: eqs @ map fst leqs) [] |
571 (poly_const rat_1,RealArith.Rational_lt rat_1):: |
633 val monoid = |
572 (filter (fn (p,_) => multidegree p <= d) leqs) |
634 if linf then |
573 else enumerate_products d leqs |
635 (poly_const rat_1,RealArith.Rational_lt rat_1):: |
574 val nblocks = length monoid |
636 (filter (fn (p,_) => multidegree p <= d) leqs) |
575 fun mk_idmultiplier k p = |
637 else enumerate_products d leqs |
576 let |
638 val nblocks = length monoid |
577 val e = d - multidegree p |
639 fun mk_idmultiplier k p = |
578 val mons = enumerate_monomials e vars |
640 let |
579 val nons = mons ~~ (1 upto length mons) |
641 val e = d - multidegree p |
580 in (mons, |
642 val mons = enumerate_monomials e vars |
581 fold_rev (fn (m,n) => FuncUtil.Monomialfunc.update(m,Inttriplefunc.onefunc((~k,~n,n),rat_1))) nons FuncUtil.Monomialfunc.empty) |
643 val nons = mons ~~ (1 upto length mons) |
|
644 in |
|
645 (mons, |
|
646 fold_rev (fn (m, n) => |
|
647 FuncUtil.Monomialfunc.update (m, Inttriplefunc.onefunc ((~k, ~n, n), rat_1))) |
|
648 nons FuncUtil.Monomialfunc.empty) |
|
649 end |
|
650 |
|
651 fun mk_sqmultiplier k (p,_) = |
|
652 let |
|
653 val e = (d - multidegree p) div 2 |
|
654 val mons = enumerate_monomials e vars |
|
655 val nons = mons ~~ (1 upto length mons) |
|
656 in |
|
657 (mons, |
|
658 fold_rev (fn (m1, n1) => |
|
659 fold_rev (fn (m2, n2) => fn a => |
|
660 let val m = monomial_mul m1 m2 in |
|
661 if n1 > n2 then a |
|
662 else |
|
663 let |
|
664 val c = if n1 = n2 then rat_1 else rat_2 |
|
665 val e = FuncUtil.Monomialfunc.tryapplyd a m Inttriplefunc.empty |
|
666 in |
|
667 FuncUtil.Monomialfunc.update |
|
668 (m, tri_equation_add (Inttriplefunc.onefunc ((k, n1, n2), c)) e) a |
|
669 end |
|
670 end) nons) nons FuncUtil.Monomialfunc.empty) |
|
671 end |
|
672 |
|
673 val (sqmonlist,sqs) = split_list (map2 mk_sqmultiplier (1 upto length monoid) monoid) |
|
674 val (_(*idmonlist*),ids) = split_list (map2 mk_idmultiplier (1 upto length eqs) eqs) |
|
675 val blocksizes = map length sqmonlist |
|
676 val bigsum = |
|
677 fold_rev2 (fn p => fn q => fn a => tri_epoly_pmul p q a) eqs ids |
|
678 (fold_rev2 (fn (p,_) => fn s => fn a => tri_epoly_pmul p s a) monoid sqs |
|
679 (epoly_of_poly(poly_neg pol))) |
|
680 val eqns = FuncUtil.Monomialfunc.fold (fn (_, e) => fn a => e :: a) bigsum [] |
|
681 val (pvs, assig) = tri_eliminate_all_equations (0, 0, 0) eqns |
|
682 val qvars = (0, 0, 0) :: pvs |
|
683 val allassig = |
|
684 fold_rev (fn v => Inttriplefunc.update (v, (Inttriplefunc.onefunc (v, rat_1)))) pvs assig |
|
685 fun mk_matrix v = |
|
686 Inttriplefunc.fold (fn ((b, i, j), ass) => fn m => |
|
687 if b < 0 then m |
|
688 else |
|
689 let val c = Inttriplefunc.tryapplyd ass v rat_0 in |
|
690 if c = rat_0 then m |
|
691 else Inttriplefunc.update ((b, j, i), c) (Inttriplefunc.update ((b, i, j), c) m) |
|
692 end) |
|
693 allassig Inttriplefunc.empty |
|
694 val diagents = |
|
695 Inttriplefunc.fold |
|
696 (fn ((b, i, j), e) => fn a => if b > 0 andalso i = j then tri_equation_add e a else a) |
|
697 allassig Inttriplefunc.empty |
|
698 |
|
699 val mats = map mk_matrix qvars |
|
700 val obj = |
|
701 (length pvs, |
|
702 itern 1 pvs (fn v => fn i => |
|
703 FuncUtil.Intfunc.updatep iszero (i,Inttriplefunc.tryapplyd diagents v rat_0)) |
|
704 FuncUtil.Intfunc.empty) |
|
705 val raw_vec = |
|
706 if null pvs then vector_0 0 |
|
707 else tri_scale_then (run_blockproblem prover nblocks blocksizes) obj mats |
|
708 fun int_element (_, v) i = FuncUtil.Intfunc.tryapplyd v i rat_0 |
|
709 |
|
710 fun find_rounding d = |
|
711 let |
|
712 val _ = |
|
713 if Config.get ctxt trace |
|
714 then writeln ("Trying rounding with limit "^Rat.string_of_rat d ^ "\n") |
|
715 else () |
|
716 val vec = nice_vector d raw_vec |
|
717 val blockmat = |
|
718 iter (1, dim vec) |
|
719 (fn i => fn a => bmatrix_add (bmatrix_cmul (int_element vec i) (nth mats i)) a) |
|
720 (bmatrix_neg (nth mats 0)) |
|
721 val allmats = blocks blocksizes blockmat |
|
722 in (vec, map diag allmats) end |
|
723 val (vec, ratdias) = |
|
724 if null pvs then find_rounding rat_1 |
|
725 else tryfind find_rounding (map Rat.rat_of_int (1 upto 31) @ map pow2 (5 upto 66)) |
|
726 val newassigs = |
|
727 fold_rev (fn k => Inttriplefunc.update (nth pvs (k - 1), int_element vec k)) |
|
728 (1 upto dim vec) (Inttriplefunc.onefunc ((0, 0, 0), Rat.rat_of_int ~1)) |
|
729 val finalassigs = |
|
730 Inttriplefunc.fold (fn (v, e) => fn a => |
|
731 Inttriplefunc.update (v, tri_equation_eval newassigs e) a) allassig newassigs |
|
732 fun poly_of_epoly p = |
|
733 FuncUtil.Monomialfunc.fold (fn (v, e) => fn a => |
|
734 FuncUtil.Monomialfunc.updatep iszero (v, tri_equation_eval finalassigs e) a) |
|
735 p FuncUtil.Monomialfunc.empty |
|
736 fun mk_sos mons = |
|
737 let |
|
738 fun mk_sq (c, m) = |
|
739 (c, fold_rev (fn k => fn a => |
|
740 FuncUtil.Monomialfunc.updatep iszero (nth mons (k - 1), int_element m k) a) |
|
741 (1 upto length mons) FuncUtil.Monomialfunc.empty) |
|
742 in map mk_sq end |
|
743 val sqs = map2 mk_sos sqmonlist ratdias |
|
744 val cfs = map poly_of_epoly ids |
|
745 val msq = filter (fn (_, b) => not (null b)) (map2 pair monoid sqs) |
|
746 fun eval_sq sqs = fold_rev (fn (c, q) => poly_add (poly_cmul c (poly_mul q q))) sqs poly_0 |
|
747 val sanity = |
|
748 fold_rev (fn ((p, _), s) => poly_add (poly_mul p (eval_sq s))) msq |
|
749 (fold_rev2 (fn p => fn q => poly_add (poly_mul p q)) cfs eqs (poly_neg pol)) |
|
750 in |
|
751 if not(FuncUtil.Monomialfunc.is_empty sanity) then raise Sanity |
|
752 else (cfs, map (fn (a, b) => (snd a, b)) msq) |
582 end |
753 end |
583 |
|
584 fun mk_sqmultiplier k (p,_) = |
|
585 let |
|
586 val e = (d - multidegree p) div 2 |
|
587 val mons = enumerate_monomials e vars |
|
588 val nons = mons ~~ (1 upto length mons) |
|
589 in (mons, |
|
590 fold_rev (fn (m1,n1) => |
|
591 fold_rev (fn (m2,n2) => fn a => |
|
592 let val m = monomial_mul m1 m2 |
|
593 in if n1 > n2 then a else |
|
594 let val c = if n1 = n2 then rat_1 else rat_2 |
|
595 val e = FuncUtil.Monomialfunc.tryapplyd a m Inttriplefunc.empty |
|
596 in FuncUtil.Monomialfunc.update(m, tri_equation_add (Inttriplefunc.onefunc((k,n1,n2), c)) e) a |
|
597 end |
|
598 end) nons) |
|
599 nons FuncUtil.Monomialfunc.empty) |
|
600 end |
|
601 |
|
602 val (sqmonlist,sqs) = split_list (map2 mk_sqmultiplier (1 upto length monoid) monoid) |
|
603 val (_(*idmonlist*),ids) = split_list(map2 mk_idmultiplier (1 upto length eqs) eqs) |
|
604 val blocksizes = map length sqmonlist |
|
605 val bigsum = |
|
606 fold_rev2 (fn p => fn q => fn a => tri_epoly_pmul p q a) eqs ids |
|
607 (fold_rev2 (fn (p,_) => fn s => fn a => tri_epoly_pmul p s a) monoid sqs |
|
608 (epoly_of_poly(poly_neg pol))) |
|
609 val eqns = FuncUtil.Monomialfunc.fold (fn (_,e) => fn a => e::a) bigsum [] |
|
610 val (pvs,assig) = tri_eliminate_all_equations (0,0,0) eqns |
|
611 val qvars = (0,0,0)::pvs |
|
612 val allassig = fold_rev (fn v => Inttriplefunc.update(v,(Inttriplefunc.onefunc(v,rat_1)))) pvs assig |
|
613 fun mk_matrix v = |
|
614 Inttriplefunc.fold (fn ((b,i,j), ass) => fn m => |
|
615 if b < 0 then m else |
|
616 let val c = Inttriplefunc.tryapplyd ass v rat_0 |
|
617 in if c = rat_0 then m else |
|
618 Inttriplefunc.update ((b,j,i), c) (Inttriplefunc.update ((b,i,j), c) m) |
|
619 end) |
|
620 allassig Inttriplefunc.empty |
|
621 val diagents = Inttriplefunc.fold |
|
622 (fn ((b,i,j), e) => fn a => if b > 0 andalso i = j then tri_equation_add e a else a) |
|
623 allassig Inttriplefunc.empty |
|
624 |
|
625 val mats = map mk_matrix qvars |
|
626 val obj = (length pvs, |
|
627 itern 1 pvs (fn v => fn i => FuncUtil.Intfunc.updatep iszero (i,Inttriplefunc.tryapplyd diagents v rat_0)) |
|
628 FuncUtil.Intfunc.empty) |
|
629 val raw_vec = if null pvs then vector_0 0 |
|
630 else tri_scale_then (run_blockproblem prover nblocks blocksizes) obj mats |
|
631 fun int_element (_,v) i = FuncUtil.Intfunc.tryapplyd v i rat_0 |
|
632 |
|
633 fun find_rounding d = |
|
634 let |
|
635 val _ = |
|
636 if Config.get ctxt trace |
|
637 then writeln ("Trying rounding with limit "^Rat.string_of_rat d ^ "\n") |
|
638 else () |
|
639 val vec = nice_vector d raw_vec |
|
640 val blockmat = iter (1,dim vec) |
|
641 (fn i => fn a => bmatrix_add (bmatrix_cmul (int_element vec i) (nth mats i)) a) |
|
642 (bmatrix_neg (nth mats 0)) |
|
643 val allmats = blocks blocksizes blockmat |
|
644 in (vec,map diag allmats) |
|
645 end |
|
646 val (vec,ratdias) = |
|
647 if null pvs then find_rounding rat_1 |
|
648 else tryfind find_rounding (map Rat.rat_of_int (1 upto 31) @ |
|
649 map pow2 (5 upto 66)) |
|
650 val newassigs = |
|
651 fold_rev (fn k => Inttriplefunc.update (nth pvs (k - 1), int_element vec k)) |
|
652 (1 upto dim vec) (Inttriplefunc.onefunc ((0,0,0), Rat.rat_of_int ~1)) |
|
653 val finalassigs = |
|
654 Inttriplefunc.fold (fn (v,e) => fn a => Inttriplefunc.update(v, tri_equation_eval newassigs e) a) allassig newassigs |
|
655 fun poly_of_epoly p = |
|
656 FuncUtil.Monomialfunc.fold (fn (v,e) => fn a => FuncUtil.Monomialfunc.updatep iszero (v,tri_equation_eval finalassigs e) a) |
|
657 p FuncUtil.Monomialfunc.empty |
|
658 fun mk_sos mons = |
|
659 let fun mk_sq (c,m) = |
|
660 (c,fold_rev (fn k=> fn a => FuncUtil.Monomialfunc.updatep iszero (nth mons (k - 1), int_element m k) a) |
|
661 (1 upto length mons) FuncUtil.Monomialfunc.empty) |
|
662 in map mk_sq |
|
663 end |
|
664 val sqs = map2 mk_sos sqmonlist ratdias |
|
665 val cfs = map poly_of_epoly ids |
|
666 val msq = filter (fn (_,b) => not (null b)) (map2 pair monoid sqs) |
|
667 fun eval_sq sqs = fold_rev (fn (c,q) => poly_add (poly_cmul c (poly_mul q q))) sqs poly_0 |
|
668 val sanity = |
|
669 fold_rev (fn ((p,_),s) => poly_add (poly_mul p (eval_sq s))) msq |
|
670 (fold_rev2 (fn p => fn q => poly_add (poly_mul p q)) cfs eqs |
|
671 (poly_neg pol)) |
|
672 |
|
673 in if not(FuncUtil.Monomialfunc.is_empty sanity) then raise Sanity else |
|
674 (cfs,map (fn (a,b) => (snd a,b)) msq) |
|
675 end |
|
676 |
754 |
677 |
755 |
678 (* Iterative deepening. *) |
756 (* Iterative deepening. *) |
679 |
757 |
680 fun deepen f n = |
758 fun deepen f n = |
682 (f n handle Failure s => (writeln ("failed with message: " ^ s); deepen f (n + 1)))); |
760 (f n handle Failure s => (writeln ("failed with message: " ^ s); deepen f (n + 1)))); |
683 |
761 |
684 |
762 |
685 (* Map back polynomials and their composites to a positivstellensatz. *) |
763 (* Map back polynomials and their composites to a positivstellensatz. *) |
686 |
764 |
687 fun cterm_of_sqterm (c,p) = RealArith.Product(RealArith.Rational_lt c,RealArith.Square p); |
765 fun cterm_of_sqterm (c, p) = RealArith.Product (RealArith.Rational_lt c, RealArith.Square p); |
688 |
766 |
689 fun cterm_of_sos (pr,sqs) = if null sqs then pr |
767 fun cterm_of_sos (pr,sqs) = |
690 else RealArith.Product(pr,foldr1 RealArith.Sum (map cterm_of_sqterm sqs)); |
768 if null sqs then pr |
|
769 else RealArith.Product (pr, foldr1 RealArith.Sum (map cterm_of_sqterm sqs)); |
691 |
770 |
692 (* Interface to HOL. *) |
771 (* Interface to HOL. *) |
693 local |
772 local |
694 open Conv |
773 open Conv |
695 val concl = Thm.dest_arg o cprop_of |
774 val concl = Thm.dest_arg o cprop_of |
696 fun simple_cterm_ord t u = Term_Ord.fast_term_ord (term_of t, term_of u) = LESS |
775 fun simple_cterm_ord t u = Term_Ord.fast_term_ord (term_of t, term_of u) = LESS |
697 in |
776 in |
698 (* FIXME: Replace tryfind by get_first !! *) |
777 (* FIXME: Replace tryfind by get_first !! *) |
699 fun real_nonlinear_prover proof_method ctxt = |
778 fun real_nonlinear_prover proof_method ctxt = |
700 let |
779 let |
701 val {add = _, mul = _, neg = _, pow = _, |
780 val {add = _, mul = _, neg = _, pow = _, sub = _, main = real_poly_conv} = |
702 sub = _, main = real_poly_conv} = |
|
703 Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt |
781 Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt |
704 (the (Semiring_Normalizer.match ctxt @{cterm "(0::real) + 1"})) |
782 (the (Semiring_Normalizer.match ctxt @{cterm "(0::real) + 1"})) |
705 simple_cterm_ord |
783 simple_cterm_ord |
706 fun mainf cert_choice translator (eqs,les,lts) = |
784 fun mainf cert_choice translator (eqs, les, lts) = |
707 let |
785 let |
708 val eq0 = map (poly_of_term o Thm.dest_arg1 o concl) eqs |
786 val eq0 = map (poly_of_term o Thm.dest_arg1 o concl) eqs |
709 val le0 = map (poly_of_term o Thm.dest_arg o concl) les |
787 val le0 = map (poly_of_term o Thm.dest_arg o concl) les |
710 val lt0 = map (poly_of_term o Thm.dest_arg o concl) lts |
788 val lt0 = map (poly_of_term o Thm.dest_arg o concl) lts |
711 val eqp0 = map_index (fn (i, t) => (t,RealArith.Axiom_eq i)) eq0 |
789 val eqp0 = map_index (fn (i, t) => (t,RealArith.Axiom_eq i)) eq0 |
712 val lep0 = map_index (fn (i, t) => (t,RealArith.Axiom_le i)) le0 |
790 val lep0 = map_index (fn (i, t) => (t,RealArith.Axiom_le i)) le0 |
713 val ltp0 = map_index (fn (i, t) => (t,RealArith.Axiom_lt i)) lt0 |
791 val ltp0 = map_index (fn (i, t) => (t,RealArith.Axiom_lt i)) lt0 |
714 val (keq,eq) = List.partition (fn (p,_) => multidegree p = 0) eqp0 |
792 val (keq,eq) = List.partition (fn (p, _) => multidegree p = 0) eqp0 |
715 val (klep,lep) = List.partition (fn (p,_) => multidegree p = 0) lep0 |
793 val (klep,lep) = List.partition (fn (p, _) => multidegree p = 0) lep0 |
716 val (kltp,ltp) = List.partition (fn (p,_) => multidegree p = 0) ltp0 |
794 val (kltp,ltp) = List.partition (fn (p, _) => multidegree p = 0) ltp0 |
717 fun trivial_axiom (p,ax) = |
795 fun trivial_axiom (p, ax) = |
718 case ax of |
796 (case ax of |
719 RealArith.Axiom_eq n => if eval FuncUtil.Ctermfunc.empty p <>/ Rat.zero then nth eqs n |
797 RealArith.Axiom_eq n => |
720 else raise Failure "trivial_axiom: Not a trivial axiom" |
798 if eval FuncUtil.Ctermfunc.empty p <>/ Rat.zero then nth eqs n |
721 | RealArith.Axiom_le n => if eval FuncUtil.Ctermfunc.empty p </ Rat.zero then nth les n |
799 else raise Failure "trivial_axiom: Not a trivial axiom" |
722 else raise Failure "trivial_axiom: Not a trivial axiom" |
800 | RealArith.Axiom_le n => |
723 | RealArith.Axiom_lt n => if eval FuncUtil.Ctermfunc.empty p <=/ Rat.zero then nth lts n |
801 if eval FuncUtil.Ctermfunc.empty p </ Rat.zero then nth les n |
724 else raise Failure "trivial_axiom: Not a trivial axiom" |
802 else raise Failure "trivial_axiom: Not a trivial axiom" |
725 | _ => error "trivial_axiom: Not a trivial axiom" |
803 | RealArith.Axiom_lt n => |
726 in |
804 if eval FuncUtil.Ctermfunc.empty p <=/ Rat.zero then nth lts n |
727 (let val th = tryfind trivial_axiom (keq @ klep @ kltp) |
805 else raise Failure "trivial_axiom: Not a trivial axiom" |
728 in |
806 | _ => error "trivial_axiom: Not a trivial axiom") |
729 (fconv_rule (arg_conv (arg1_conv (real_poly_conv ctxt)) |
807 in |
730 then_conv Numeral_Simprocs.field_comp_conv ctxt) th, |
808 let val th = tryfind trivial_axiom (keq @ klep @ kltp) in |
731 RealArith.Trivial) |
809 (fconv_rule (arg_conv (arg1_conv (real_poly_conv ctxt)) |
732 end) |
810 then_conv Numeral_Simprocs.field_comp_conv ctxt) th, |
733 handle Failure _ => |
811 RealArith.Trivial) |
734 (let val proof = |
812 end handle Failure _ => |
735 (case proof_method of Certificate certs => |
813 let |
736 (* choose certificate *) |
814 val proof = |
737 let |
815 (case proof_method of |
738 fun chose_cert [] (RealArith.Cert c) = c |
816 Certificate certs => |
739 | chose_cert (RealArith.Left::s) (RealArith.Branch (l, _)) = chose_cert s l |
817 (* choose certificate *) |
740 | chose_cert (RealArith.Right::s) (RealArith.Branch (_, r)) = chose_cert s r |
818 let |
741 | chose_cert _ _ = error "certificate tree in invalid form" |
819 fun chose_cert [] (RealArith.Cert c) = c |
742 in |
820 | chose_cert (RealArith.Left::s) (RealArith.Branch (l, _)) = chose_cert s l |
743 chose_cert cert_choice certs |
821 | chose_cert (RealArith.Right::s) (RealArith.Branch (_, r)) = chose_cert s r |
744 end |
822 | chose_cert _ _ = error "certificate tree in invalid form" |
745 | Prover prover => |
823 in |
746 (* call prover *) |
824 chose_cert cert_choice certs |
747 let |
825 end |
748 val pol = fold_rev poly_mul (map fst ltp) (poly_const Rat.one) |
826 | Prover prover => |
749 val leq = lep @ ltp |
827 (* call prover *) |
750 fun tryall d = |
828 let |
751 let val e = multidegree pol |
829 val pol = fold_rev poly_mul (map fst ltp) (poly_const Rat.one) |
752 val k = if e = 0 then 0 else d div e |
830 val leq = lep @ ltp |
753 val eq' = map fst eq |
831 fun tryall d = |
754 in tryfind (fn i => (d,i,real_positivnullstellensatz_general ctxt prover false d eq' leq |
832 let |
755 (poly_neg(poly_pow pol i)))) |
833 val e = multidegree pol |
756 (0 upto k) |
834 val k = if e = 0 then 0 else d div e |
757 end |
835 val eq' = map fst eq |
758 val (_,i,(cert_ideal,cert_cone)) = deepen tryall 0 |
836 in |
759 val proofs_ideal = |
837 tryfind (fn i => |
760 map2 (fn q => fn (_,ax) => RealArith.Eqmul(q,ax)) cert_ideal eq |
838 (d, i, real_positivnullstellensatz_general ctxt prover false d eq' leq |
761 val proofs_cone = map cterm_of_sos cert_cone |
839 (poly_neg(poly_pow pol i)))) |
762 val proof_ne = if null ltp then RealArith.Rational_lt Rat.one else |
840 (0 upto k) |
763 let val p = foldr1 RealArith.Product (map snd ltp) |
841 end |
764 in funpow i (fn q => RealArith.Product(p,q)) (RealArith.Rational_lt Rat.one) |
842 val (_,i,(cert_ideal,cert_cone)) = deepen tryall 0 |
765 end |
843 val proofs_ideal = |
766 in |
844 map2 (fn q => fn (_,ax) => RealArith.Eqmul(q,ax)) cert_ideal eq |
767 foldr1 RealArith.Sum (proof_ne :: proofs_ideal @ proofs_cone) |
845 val proofs_cone = map cterm_of_sos cert_cone |
768 end) |
846 val proof_ne = |
769 in |
847 if null ltp then RealArith.Rational_lt Rat.one |
770 (translator (eqs,les,lts) proof, RealArith.Cert proof) |
848 else |
771 end) |
849 let val p = foldr1 RealArith.Product (map snd ltp) in |
772 end |
850 funpow i (fn q => RealArith.Product (p, q)) |
773 in mainf end |
851 (RealArith.Rational_lt Rat.one) |
|
852 end |
|
853 in |
|
854 foldr1 RealArith.Sum (proof_ne :: proofs_ideal @ proofs_cone) |
|
855 end) |
|
856 in |
|
857 (translator (eqs,les,lts) proof, RealArith.Cert proof) |
|
858 end |
|
859 end |
|
860 in mainf end |
774 end |
861 end |
775 |
862 |
776 fun C f x y = f y x; |
863 fun C f x y = f y x; |
777 (* FIXME : This is very bad!!!*) |
864 (* FIXME : This is very bad!!!*) |
778 fun subst_conv eqs t = |
865 fun subst_conv eqs t = |
779 let |
866 let |
780 val t' = fold (Thm.lambda o Thm.lhs_of) eqs t |
867 val t' = fold (Thm.lambda o Thm.lhs_of) eqs t |
781 in Conv.fconv_rule (Thm.beta_conversion true) (fold (C Thm.combination) eqs (Thm.reflexive t')) |
868 in |
782 end |
869 Conv.fconv_rule (Thm.beta_conversion true) (fold (C Thm.combination) eqs (Thm.reflexive t')) |
|
870 end |
783 |
871 |
784 (* A wrapper that tries to substitute away variables first. *) |
872 (* A wrapper that tries to substitute away variables first. *) |
785 |
873 |
786 local |
874 local |
787 open Conv |
875 open Conv |
788 fun simple_cterm_ord t u = Term_Ord.fast_term_ord (term_of t, term_of u) = LESS |
876 fun simple_cterm_ord t u = Term_Ord.fast_term_ord (term_of t, term_of u) = LESS |
789 val concl = Thm.dest_arg o cprop_of |
877 val concl = Thm.dest_arg o cprop_of |
790 val shuffle1 = |
878 val shuffle1 = |
791 fconv_rule (rewr_conv @{lemma "(a + x == y) == (x == y - (a::real))" by (atomize (full)) (simp add: field_simps) }) |
879 fconv_rule (rewr_conv @{lemma "(a + x == y) == (x == y - (a::real))" |
792 val shuffle2 = |
880 by (atomize (full)) (simp add: field_simps)}) |
793 fconv_rule (rewr_conv @{lemma "(x + a == y) == (x == y - (a::real))" by (atomize (full)) (simp add: field_simps)}) |
881 val shuffle2 = |
794 fun substitutable_monomial fvs tm = case term_of tm of |
882 fconv_rule (rewr_conv @{lemma "(x + a == y) == (x == y - (a::real))" |
795 Free(_,@{typ real}) => if not (member (op aconvc) fvs tm) then (Rat.one,tm) |
883 by (atomize (full)) (simp add: field_simps)}) |
796 else raise Failure "substitutable_monomial" |
884 fun substitutable_monomial fvs tm = |
797 | @{term "op * :: real => _"}$_$(Free _) => |
885 (case term_of tm of |
798 if RealArith.is_ratconst (Thm.dest_arg1 tm) andalso not (member (op aconvc) fvs (Thm.dest_arg tm)) |
886 Free (_, @{typ real}) => |
799 then (RealArith.dest_ratconst (Thm.dest_arg1 tm),Thm.dest_arg tm) else raise Failure "substitutable_monomial" |
887 if not (member (op aconvc) fvs tm) then (Rat.one, tm) |
800 | @{term "op + :: real => _"}$_$_ => |
888 else raise Failure "substitutable_monomial" |
801 (substitutable_monomial (Thm.add_cterm_frees (Thm.dest_arg tm) fvs) (Thm.dest_arg1 tm) |
889 | @{term "op * :: real => _"} $ _ $ (Free _) => |
802 handle Failure _ => substitutable_monomial (Thm.add_cterm_frees (Thm.dest_arg1 tm) fvs) (Thm.dest_arg tm)) |
890 if RealArith.is_ratconst (Thm.dest_arg1 tm) andalso |
803 | _ => raise Failure "substitutable_monomial" |
891 not (member (op aconvc) fvs (Thm.dest_arg tm)) |
|
892 then (RealArith.dest_ratconst (Thm.dest_arg1 tm), Thm.dest_arg tm) |
|
893 else raise Failure "substitutable_monomial" |
|
894 | @{term "op + :: real => _"}$_$_ => |
|
895 (substitutable_monomial (Thm.add_cterm_frees (Thm.dest_arg tm) fvs) (Thm.dest_arg1 tm) |
|
896 handle Failure _ => |
|
897 substitutable_monomial (Thm.add_cterm_frees (Thm.dest_arg1 tm) fvs) (Thm.dest_arg tm)) |
|
898 | _ => raise Failure "substitutable_monomial") |
804 |
899 |
805 fun isolate_variable v th = |
900 fun isolate_variable v th = |
806 let val w = Thm.dest_arg1 (cprop_of th) |
901 let |
807 in if v aconvc w then th |
902 val w = Thm.dest_arg1 (cprop_of th) |
808 else case term_of w of |
903 in |
809 @{term "op + :: real => _"}$_$_ => |
904 if v aconvc w then th |
810 if Thm.dest_arg1 w aconvc v then shuffle2 th |
905 else |
811 else isolate_variable v (shuffle1 th) |
906 (case term_of w of |
812 | _ => error "isolate variable : This should not happen?" |
907 @{term "op + :: real => _"} $ _ $ _ => |
|
908 if Thm.dest_arg1 w aconvc v then shuffle2 th |
|
909 else isolate_variable v (shuffle1 th) |
|
910 | _ => error "isolate variable : This should not happen?") |
813 end |
911 end |
814 in |
912 in |
815 |
913 |
816 fun real_nonlinear_subst_prover prover ctxt = |
914 fun real_nonlinear_subst_prover prover ctxt = |
817 let |
915 let |
818 val {add = _, mul = real_poly_mul_conv, neg = _, |
916 val {add = _, mul = real_poly_mul_conv, neg = _, pow = _, sub = _, main = real_poly_conv} = |
819 pow = _, sub = _, main = real_poly_conv} = |
|
820 Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt |
917 Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt |
821 (the (Semiring_Normalizer.match ctxt @{cterm "(0::real) + 1"})) |
918 (the (Semiring_Normalizer.match ctxt @{cterm "(0::real) + 1"})) |
822 simple_cterm_ord |
919 simple_cterm_ord |
823 |
920 |
824 fun make_substitution th = |
921 fun make_substitution th = |
825 let |
922 let |
826 val (c,v) = substitutable_monomial [] (Thm.dest_arg1(concl th)) |
923 val (c,v) = substitutable_monomial [] (Thm.dest_arg1(concl th)) |
827 val th1 = Drule.arg_cong_rule (Thm.apply @{cterm "op * :: real => _"} (RealArith.cterm_of_rat (Rat.inv c))) (mk_meta_eq th) |
924 val th1 = |
828 val th2 = fconv_rule (binop_conv (real_poly_mul_conv ctxt)) th1 |
925 Drule.arg_cong_rule |
829 in fconv_rule (arg_conv (real_poly_conv ctxt)) (isolate_variable v th2) |
926 (Thm.apply @{cterm "op * :: real => _"} (RealArith.cterm_of_rat (Rat.inv c))) |
830 end |
927 (mk_meta_eq th) |
831 fun oprconv cv ct = |
928 val th2 = fconv_rule (binop_conv (real_poly_mul_conv ctxt)) th1 |
832 let val g = Thm.dest_fun2 ct |
929 in fconv_rule (arg_conv (real_poly_conv ctxt)) (isolate_variable v th2) end |
833 in if g aconvc @{cterm "op <= :: real => _"} |
930 |
834 orelse g aconvc @{cterm "op < :: real => _"} |
931 fun oprconv cv ct = |
835 then arg_conv cv ct else arg1_conv cv ct |
932 let val g = Thm.dest_fun2 ct in |
836 end |
933 if g aconvc @{cterm "op <= :: real => _"} orelse g aconvc @{cterm "op < :: real => _"} |
837 fun mainf cert_choice translator = |
934 then arg_conv cv ct else arg1_conv cv ct |
838 let |
935 end |
839 fun substfirst(eqs,les,lts) = |
936 fun mainf cert_choice translator = |
840 ((let |
937 let |
841 val eth = tryfind make_substitution eqs |
938 fun substfirst (eqs, les, lts) = |
842 val modify = |
939 (let |
843 fconv_rule (arg_conv (oprconv(subst_conv [eth] then_conv (real_poly_conv ctxt)))) |
940 val eth = tryfind make_substitution eqs |
844 in substfirst |
941 val modify = |
845 (filter_out (fn t => (Thm.dest_arg1 o Thm.dest_arg o cprop_of) t |
942 fconv_rule (arg_conv (oprconv(subst_conv [eth] then_conv (real_poly_conv ctxt)))) |
846 aconvc @{cterm "0::real"}) (map modify eqs), |
943 in |
847 map modify les,map modify lts) |
944 substfirst |
848 end) |
945 (filter_out |
849 handle Failure _ => real_nonlinear_prover prover ctxt cert_choice translator (rev eqs, rev les, rev lts)) |
946 (fn t => (Thm.dest_arg1 o Thm.dest_arg o cprop_of) t aconvc @{cterm "0::real"}) |
850 in substfirst |
947 (map modify eqs), |
851 end |
948 map modify les, |
852 |
949 map modify lts) |
853 |
950 end handle Failure _ => |
854 in mainf |
951 real_nonlinear_prover prover ctxt cert_choice translator (rev eqs, rev les, rev lts)) |
855 end |
952 in substfirst end |
|
953 in mainf end |
856 |
954 |
857 (* Overall function. *) |
955 (* Overall function. *) |
858 |
956 |
859 fun real_sos prover ctxt = |
957 fun real_sos prover ctxt = |
860 RealArith.gen_prover_real_arith ctxt (real_nonlinear_subst_prover prover ctxt) |
958 RealArith.gen_prover_real_arith ctxt (real_nonlinear_subst_prover prover ctxt) |
|
959 |
861 end; |
960 end; |
862 |
961 |
863 val known_sos_constants = |
962 val known_sos_constants = |
864 [@{term "op ==>"}, @{term "Trueprop"}, |
963 [@{term "op ==>"}, @{term "Trueprop"}, |
865 @{term HOL.implies}, @{term HOL.conj}, @{term HOL.disj}, |
964 @{term HOL.implies}, @{term HOL.conj}, @{term HOL.disj}, |
876 @{term "numeral :: num => nat"}, |
975 @{term "numeral :: num => nat"}, |
877 @{term "numeral :: num => real"}, |
976 @{term "numeral :: num => real"}, |
878 @{term "Num.Bit0"}, @{term "Num.Bit1"}, @{term "Num.One"}]; |
977 @{term "Num.Bit0"}, @{term "Num.Bit1"}, @{term "Num.One"}]; |
879 |
978 |
880 fun check_sos kcts ct = |
979 fun check_sos kcts ct = |
881 let |
980 let |
882 val t = term_of ct |
981 val t = term_of ct |
883 val _ = if not (null (Term.add_tfrees t []) |
982 val _ = |
884 andalso null (Term.add_tvars t [])) |
983 if not (null (Term.add_tfrees t []) andalso null (Term.add_tvars t [])) |
885 then error "SOS: not sos. Additional type varables" else () |
984 then error "SOS: not sos. Additional type varables" |
886 val fs = Term.add_frees t [] |
985 else () |
887 val _ = if exists (fn ((_,T)) => not (T = @{typ "real"})) fs |
986 val fs = Term.add_frees t [] |
888 then error "SOS: not sos. Variables with type not real" else () |
987 val _ = |
889 val vs = Term.add_vars t [] |
988 if exists (fn ((_,T)) => not (T = @{typ "real"})) fs |
890 val _ = if exists (fn ((_,T)) => not (T = @{typ "real"})) vs |
989 then error "SOS: not sos. Variables with type not real" |
891 then error "SOS: not sos. Variables with type not real" else () |
990 else () |
892 val ukcs = subtract (fn (t,p) => Const p aconv t) kcts (Term.add_consts t []) |
991 val vs = Term.add_vars t [] |
893 val _ = if null ukcs then () |
992 val _ = |
894 else error ("SOSO: Unknown constants in Subgoal:" ^ commas (map fst ukcs)) |
993 if exists (fn ((_,T)) => not (T = @{typ "real"})) vs |
895 in () end |
994 then error "SOS: not sos. Variables with type not real" |
|
995 else () |
|
996 val ukcs = subtract (fn (t,p) => Const p aconv t) kcts (Term.add_consts t []) |
|
997 val _ = |
|
998 if null ukcs then () |
|
999 else error ("SOSO: Unknown constants in Subgoal:" ^ commas (map fst ukcs)) |
|
1000 in () end |
896 |
1001 |
897 fun core_sos_tac print_cert prover = SUBPROOF (fn {concl, context, ...} => |
1002 fun core_sos_tac print_cert prover = SUBPROOF (fn {concl, context, ...} => |
898 let |
1003 let |
899 val _ = check_sos known_sos_constants concl |
1004 val _ = check_sos known_sos_constants concl |
900 val (ths, certificates) = real_sos prover context (Thm.dest_arg concl) |
1005 val (ths, certificates) = real_sos prover context (Thm.dest_arg concl) |
901 val _ = print_cert certificates |
1006 val _ = print_cert certificates |
902 in rtac ths 1 end) |
1007 in rtac ths 1 end); |
903 |
1008 |
904 fun default_SOME _ NONE v = SOME v |
1009 fun default_SOME _ NONE v = SOME v |
905 | default_SOME _ (SOME v) _ = SOME v; |
1010 | default_SOME _ (SOME v) _ = SOME v; |
906 |
1011 |
907 fun lift_SOME f NONE a = f a |
1012 fun lift_SOME f NONE a = f a |
908 | lift_SOME _ (SOME a) _ = SOME a; |
1013 | lift_SOME _ (SOME a) _ = SOME a; |
909 |
1014 |
910 |
1015 |
911 local |
1016 local |
912 val is_numeral = can (HOLogic.dest_number o term_of) |
1017 val is_numeral = can (HOLogic.dest_number o term_of) |
913 in |
1018 in |
914 fun get_denom b ct = case term_of ct of |
1019 fun get_denom b ct = |
915 @{term "op / :: real => _"} $ _ $ _ => |
1020 (case term_of ct of |
916 if is_numeral (Thm.dest_arg ct) then get_denom b (Thm.dest_arg1 ct) |
1021 @{term "op / :: real => _"} $ _ $ _ => |
917 else default_SOME (get_denom b) (get_denom b (Thm.dest_arg ct)) (Thm.dest_arg ct, b) |
1022 if is_numeral (Thm.dest_arg ct) |
918 | @{term "op < :: real => _"} $ _ $ _ => lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct) |
1023 then get_denom b (Thm.dest_arg1 ct) |
919 | @{term "op <= :: real => _"} $ _ $ _ => lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct) |
1024 else default_SOME (get_denom b) (get_denom b (Thm.dest_arg ct)) (Thm.dest_arg ct, b) |
920 | _ $ _ => lift_SOME (get_denom b) (get_denom b (Thm.dest_fun ct)) (Thm.dest_arg ct) |
1025 | @{term "op < :: real => _"} $ _ $ _ => |
921 | _ => NONE |
1026 lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct) |
|
1027 | @{term "op <= :: real => _"} $ _ $ _ => |
|
1028 lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct) |
|
1029 | _ $ _ => lift_SOME (get_denom b) (get_denom b (Thm.dest_fun ct)) (Thm.dest_arg ct) |
|
1030 | _ => NONE) |
922 end; |
1031 end; |
923 |
1032 |
924 fun elim_one_denom_tac ctxt = |
1033 fun elim_one_denom_tac ctxt = CSUBGOAL (fn (P, i) => |
925 CSUBGOAL (fn (P,i) => |
1034 (case get_denom false P of |
926 case get_denom false P of |
1035 NONE => no_tac |
927 NONE => no_tac |
1036 | SOME (d, ord) => |
928 | SOME (d,ord) => |
1037 let |
929 let |
1038 val simp_ctxt = |
930 val simp_ctxt = |
1039 ctxt addsimps @{thms field_simps} |
931 ctxt addsimps @{thms field_simps} |
1040 addsimps [@{thm nonzero_power_divide}, @{thm power_divide}] |
932 addsimps [@{thm nonzero_power_divide}, @{thm power_divide}] |
1041 val th = |
933 val th = instantiate' [] [SOME d, SOME (Thm.dest_arg P)] |
1042 instantiate' [] [SOME d, SOME (Thm.dest_arg P)] |
934 (if ord then @{lemma "(d=0 --> P) & (d>0 --> P) & (d<(0::real) --> P) ==> P" by auto} |
1043 (if ord then @{lemma "(d=0 --> P) & (d>0 --> P) & (d<(0::real) --> P) ==> P" by auto} |
935 else @{lemma "(d=0 --> P) & (d ~= (0::real) --> P) ==> P" by blast}) |
1044 else @{lemma "(d=0 --> P) & (d ~= (0::real) --> P) ==> P" by blast}) |
936 in rtac th i THEN Simplifier.asm_full_simp_tac simp_ctxt i end); |
1045 in rtac th i THEN Simplifier.asm_full_simp_tac simp_ctxt i end)); |
937 |
1046 |
938 fun elim_denom_tac ctxt i = REPEAT (elim_one_denom_tac ctxt i); |
1047 fun elim_denom_tac ctxt i = REPEAT (elim_one_denom_tac ctxt i); |
939 |
1048 |
940 fun sos_tac print_cert prover ctxt = |
1049 fun sos_tac print_cert prover ctxt = |
941 Object_Logic.full_atomize_tac ctxt THEN' |
1050 Object_Logic.full_atomize_tac ctxt THEN' |