Debian Codegraph @

Formal_ineqs/trig/poly_eval.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2014 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Formal interval evaluation of polynomials *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/trig/poly.hl";;
14 needs "Formal_ineqs/misc/misc_functions.hl";;
15 needs "Formal_ineqs/misc/misc_vars.hl";;
16 needs "Formal_ineqs/arith/more_float.hl";;
17
18 module Poly_eval = struct
19
20 open Poly;;
21 open Misc_functions;;
22 open Interval_arith;;
23 open Float_theory;;
24 open Arith_float;;
25 open More_list;;
26 open More_float;;
27 open Misc_vars;;
28
29 prioritize_real();;
30
31 (* Creates an interval approximation of the given decimal term *)
32 let mk_float_interval_decimal =
33 let DECIMAL' = SPEC_ALL DECIMAL in
34 fun pp decimal_tm ->
35 let n_tm, d_tm = dest_binary "DECIMAL" decimal_tm in
36 let n, d = dest_numeral n_tm, dest_numeral d_tm in
37 let n_int, d_int = mk_float_interval_num n, mk_float_interval_num d in
38 let int = float_interval_div pp n_int d_int in
39 let eq_th = INST[n_tm, x_var_num; d_tm, y_var_num] DECIMAL' in
40 norm_interval int eq_th;;
41
42
43 (* A simple interval evaluation function *)
44 let rec float_interval_calc pp expr_tm x_th =
45 if is_var expr_tm then
46 x_th
47 else
48 let ltm, r_tm = dest_comb expr_tm in
49 if is_comb ltm then
50 let op, l_tm = dest_comb ltm in
51 let name = (fst o dest_const) op in
52 match name with
53 | "DECIMAL" -> mk_float_interval_decimal pp expr_tm
54 | _ ->
55 let l_th = float_interval_calc pp l_tm x_th in
56 let r_th = float_interval_calc pp r_tm x_th in
57 if op = add_op_real then
58 float_interval_add pp l_th r_th
59 else if op = mul_op_real then
60 float_interval_mul pp l_th r_th
61 else if op = div_op_real then
62 float_interval_div pp l_th r_th
63 else if op = sub_op_real then
64 float_interval_sub pp l_th r_th
65 else
66 failwith ("Unknown operation: " ^ name)
67 else
68 if ltm = neg_op_real then
69 let r_th = float_interval_calc pp r_tm x_th in
70 float_interval_neg r_th
71 else if ltm = inv_op_real then
72 let r_th = float_interval_calc pp r_tm x_th in
73 float_interval_inv pp r_th
74 else
75 mk_float_interval_num (dest_numeral r_tm);;
76
77 let float_interval_const pp expr_tm =
78 float_interval_calc pp expr_tm TRUTH;;
79
80 (* Data structure for a polynomial coefficient *)
81 type poly_coeff = {
82 c_tm : term;
83 bounds_tm : term;
84 interval_th : thm;
85 (* high_th : thm;
86 low_th : thm;
87 *)
88 sign : int;
89 sign_high_th : thm;
90 sign_low_th : thm;
91 };;
92
93 (* Creates polynomial coefficients from the given list of constant expressions *)
94 let mk_poly_coeffs =
95 let interval_pos = prove(`interval_arith x (float_num F n e, f)
96 ==> interval_arith x (&0, f) /\ interval_arith (float_num F n e) (&0, x)`,
97 REWRITE_TAC[interval_arith] THEN
98 MP_TAC (SPECL[`n:num`; `e:num`] FLOAT_F_POS) THEN
99 REAL_ARITH_TAC) and
100 interval_neg = prove(`interval_arith x (f, float_num T n e)
101 ==> interval_arith x (f, &0) /\ interval_arith (float_num T n e) (x, &0)`,
102 REWRITE_TAC[interval_arith] THEN
103 MP_TAC (SPECL[`n:num`; `e:num`] FLOAT_T_NEG) THEN
104 REAL_ARITH_TAC) in
105 let mk_poly_coeff pp cs_tm =
106 let eq_th = NUM_REDUCE_CONV cs_tm in
107 let expr_tm = (rand o concl) eq_th in
108 let int_th = REWRITE_RULE[GSYM eq_th] (float_interval_const pp expr_tm) in
109 (* let bounds_th = REWRITE_RULE[interval_arith] int_th in *)
110 (* let low_th, high_th = pair_of_list (CONJUNCTS bounds_th) in *)
111 let c_tm, bounds = dest_interval_arith (concl int_th) in
112 let a, b = dest_pair bounds in
113 let s1, _, _ = dest_float a in
114 let s2, _, _ = dest_float b in
115 let sign, sign_th =
116 match (s1, s2) with
117 | "F", _ -> 1, MATCH_MP interval_pos int_th
118 | _, "T" -> -1, MATCH_MP interval_neg int_th
119 | _ -> 0, TRUTH in
120 let sign_high, sign_low = pair_of_list (CONJUNCTS sign_th) in
121 {
122 c_tm = c_tm;
123 bounds_tm = bounds;
124 interval_th = int_th;
125 (* high_th = high_th;
126 low_th = low_th;
127 *)
128 sign = sign;
129 sign_high_th = sign_high;
130 sign_low_th = sign_low;
131 } in
132 fun pp list_tm ->
133 map (mk_poly_coeff pp) (dest_list list_tm);;
134
135 (* Evaluates a polynomial on a given interval *)
136 let eval_interval_poly_f =
137 let poly_f_empty' = RULE poly_f_empty_interval and
138 poly_f_sing' = RULE poly_f_sing and
139 poly_f_cons' = RULE poly_f_cons and
140 interval_const = `interval_arith` in
141 fun pp (cs_tm, cs_list) x_th ->
142 let rec eval cs_tm cs_list x_tm x_th =
143 match cs_list with
144 | [] ->
145 INST[x_tm, x_var_real] poly_f_empty'
146 | [first] ->
147 let th0 = INST[first.c_tm, c_var_real; x_tm, x_var_real] poly_f_sing' in
148 EQ_MP (SYM (AP_THM (AP_TERM interval_const th0) first.bounds_tm)) first.interval_th
149 | first :: rest ->
150 let ltm, t_tm = dest_comb cs_tm in
151 let h_tm = rand ltm in
152 let th0 = INST[h_tm, h_var_real; t_tm, t_var_real_list; x_tm, x_var_real] poly_f_cons' in
153 let r_th = eval t_tm rest x_tm x_th in
154 let th1 = float_interval_add pp first.interval_th
155 (float_interval_mul pp x_th r_th) in
156 let bounds = rand (concl th1) in
157 EQ_MP (SYM (AP_THM (AP_TERM interval_const th0) bounds)) th1
158 in
159 let x_tm = rand (rator (concl x_th)) in
160 eval cs_tm cs_list x_tm x_th;;
161
162 (* Evaluates an upper bound of a polynomial on a given non-negative number.
163 * All coefficients of the polynomial must be non-negative.
164 * The argument x should be in the form: |- interval_arith x (&0, f) *)
165 let eval_high_poly_f_pos_pos =
166 let RULE' = (UNDISCH_ALL o REWRITE_RULE[real_zero] o DISCH_ALL o RULE) in
167 let poly_f_empty_high' = RULE' poly_f_empty_high_pos and
168 poly_f_sing_high' = RULE' poly_f_sing_high_pos and
169 poly_f_cons_high' = RULE' poly_f_cons_high_pos_pos in
170 let check_pos c =
171 if c.sign = 1 then () else
172 failwith (Printf.sprintf "eval_high_poly_f_pos_pos: non-positive coefficient: %s, %s"
173 (string_of_term c.c_tm)
174 (string_of_term c.bounds_tm)) in
175 fun pp (cs_tm, cs_list) x_th ->
176 let rec eval cs_tm cs_list x_tm x_th =
177 match cs_list with
178 | [] -> INST[x_tm, x_var_real] poly_f_empty_high'
179 | [first] ->
180 let _ = check_pos first in
181 let bounds_tm = rand (concl first.sign_high_th) in
182 let th0 = INST[first.c_tm, c_var_real; bounds_tm, bounds_var; x_tm, x_var_real]
183 poly_f_sing_high' in
184 MY_PROVE_HYP first.sign_high_th th0
185 | first :: rest ->
186 let _ = check_pos first in
187 let ltm, t_tm = dest_comb cs_tm in
188 let h_tm = rand ltm in
189 let rest_th = eval t_tm rest x_tm x_th in
190 let a_tm = (rand o rand o concl) rest_th in
191 let b_tm = (rand o rand o concl) first.sign_high_th in
192 let c_tm = (rand o rand o concl) x_th in
193 let m_bound_th = float_mul_hi pp c_tm a_tm in
194 let m_tm = (rand o concl) m_bound_th in
195 let r_bound_th = float_add_hi pp b_tm m_tm in
196 let r_tm = (rand o concl) r_bound_th in
197 let th0 = INST[h_tm, h_var_real; t_tm, t_var_real_list; x_tm, x_var_real;
198 a_tm, a_var_real; b_tm, b_var_real; c_tm, c_var_real;
199 m_tm, m_var_real; r_tm, r_var_real] poly_f_cons_high' in
200 MY_PROVE_HYP r_bound_th
201 (MY_PROVE_HYP m_bound_th
202 (MY_PROVE_HYP first.sign_high_th
203 (MY_PROVE_HYP rest_th (MY_PROVE_HYP x_th th0))))
204 in
205 let x_tm = rand (rator (concl x_th)) in
206 eval cs_tm cs_list x_tm x_th;;
207
208
209 (* Evaluates a lower bound of a polynomial on a given non-negative number.
210 * All coefficients of the polynomial must be non-negative.
211 * The argument x should be in the form: |- interval_arith f (&0, x) *)
212 let eval_low_poly_f_pos_pos =
213 let RULE' = (UNDISCH_ALL o REWRITE_RULE[real_zero] o DISCH_ALL o RULE) in
214 let poly_f_empty_low' = RULE' poly_f_empty_low_pos and
215 poly_f_sing_low' = RULE' poly_f_sing_low_pos and
216 poly_f_cons_low' = RULE' poly_f_cons_low_pos_pos in
217 let check_pos c =
218 if c.sign = 1 then () else
219 failwith (Printf.sprintf "eval_low_poly_f_pos_pos: non-positive coefficient: %s, %s"
220 (string_of_term c.c_tm)
221 (string_of_term c.bounds_tm)) in
222 fun pp (cs_tm, cs_list) x_th ->
223 let rec eval cs_tm cs_list x_tm x_th =
224 match cs_list with
225 | [] -> INST[x_tm, x_var_real] poly_f_empty_low'
226 | [first] ->
227 let _ = check_pos first in
228 let b_tm = (rand o rator o concl) first.sign_low_th in
229 let th0 = INST[first.c_tm, c_var_real; b_tm, b_var_real; x_tm, x_var_real]
230 poly_f_sing_low' in
231 MY_PROVE_HYP first.sign_low_th th0
232 | first :: rest ->
233 let _ = check_pos first in
234 let ltm, t_tm = dest_comb cs_tm in
235 let h_tm = rand ltm in
236 let rest_th = eval t_tm rest x_tm x_th in
237 let a_tm = (rand o rator o concl) rest_th in
238 let b_tm = (rand o rator o concl) first.sign_low_th in
239 let c_tm = (rand o rator o concl) x_th in
240 let m_bound_th = float_mul_lo pp c_tm a_tm in
241 let m_tm = (rand o rator o concl) m_bound_th in
242 let r_bound_th = float_add_lo pp b_tm m_tm in
243 let r_tm = (rand o rator o concl) r_bound_th in
244 let r_ge0_th = EQT_ELIM (float_ge0 r_tm) in
245 let th0 = INST[h_tm, h_var_real; t_tm, t_var_real_list; x_tm, x_var_real;
246 a_tm, a_var_real; b_tm, b_var_real; c_tm, c_var_real;
247 m_tm, m_var_real; r_tm, r_var_real] poly_f_cons_low' in
248 MY_PROVE_HYP r_ge0_th
249 (MY_PROVE_HYP r_bound_th
250 (MY_PROVE_HYP m_bound_th
251 (MY_PROVE_HYP first.sign_low_th
252 (MY_PROVE_HYP rest_th (MY_PROVE_HYP x_th th0)))))
253 in
254 let x_tm = rand (rand (concl x_th)) in
255 eval cs_tm cs_list x_tm x_th;;
256
257
258 let eval_pow2_high =
259 let pow2_th = (UNDISCH_ALL o prove)(`x * x <= a ==> interval_arith (x pow 2) (&0, a)`,
260 REWRITE_TAC[interval_arith; REAL_POW_2; REAL_LE_SQUARE]) in
261 fun pp f_tm ->
262 let mul_th = float_mul_hi pp f_tm f_tm in
263 let a_tm = (rand o concl) mul_th in
264 let th0 = INST[f_tm, x_var_real; a_tm, a_var_real] pow2_th in
265 MY_PROVE_HYP mul_th th0;;
266
267 let eval_pow2_low =
268 let pow2_th = (UNDISCH_ALL o prove)(`(&0 <= a <=> T) ==> a <= x * x
269 ==> interval_arith a (&0, x pow 2)`,
270 SIMP_TAC[interval_arith; REAL_POW_2]) in
271 fun pp f_tm ->
272 let mul_th = float_mul_lo pp f_tm f_tm in
273 let a_tm = (rand o rator o concl) mul_th in
274 let a_ge0_th = float_ge0 a_tm in
275 let th0 = INST[f_tm, x_var_real; a_tm, a_var_real] pow2_th in
276 MY_PROVE_HYP mul_th (MY_PROVE_HYP a_ge0_th th0);;
277
278 let eval_pow4_high =
279 let pow4_th = (UNDISCH_ALL o prove)(`x * x <= a ==>
280 a * a <= b ==>
281 interval_arith (x pow 4) (&0, b)`,
282 REWRITE_TAC[interval_arith; ARITH_RULE `4 = 2 + 2`; REAL_POW_ADD] THEN
283 REPEAT STRIP_TAC THENL [
284 MATCH_MP_TAC REAL_LE_MUL THEN REWRITE_TAC[REAL_LE_POW_2];
285 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a * a:real` THEN
286 ASM_REWRITE_TAC[] THEN
287 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[REAL_LE_POW_2; REAL_POW_2]
288 ]) in
289 fun pp f_tm ->
290 let mul1_th = float_mul_hi pp f_tm f_tm in
291 let a_tm = (rand o concl) mul1_th in
292 let mul2_th = float_mul_hi pp a_tm a_tm in
293 let b_tm = (rand o concl) mul2_th in
294 let th0 = INST[f_tm, x_var_real; a_tm, a_var_real; b_tm, b_var_real] pow4_th in
295 MY_PROVE_HYP mul1_th (MY_PROVE_HYP mul2_th th0);;
296
297 let eval_pow4_low =
298 let pow4_th = (UNDISCH_ALL o prove)(`a <= x * x ==>
299 b <= a * a ==>
300 (&0 <= a <=> T) ==>
301 (&0 <= b <=> T) ==>
302 interval_arith b (&0, x pow 4)`,
303 REWRITE_TAC[interval_arith; ARITH_RULE `4 = 2 + 2`; REAL_POW_ADD] THEN
304 REPEAT STRIP_TAC THEN ASM_REWRITE_TAC[] THEN
305 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a * a:real` THEN
306 ASM_REWRITE_TAC[] THEN
307 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[REAL_LE_POW_2; REAL_POW_2])
308 in
309 fun pp f_tm ->
310 let mul1_th = float_mul_lo pp f_tm f_tm in
311 let a_tm = (rand o rator o concl) mul1_th in
312 let mul2_th = float_mul_lo pp a_tm a_tm in
313 let b_tm = (rand o rator o concl) mul2_th in
314 let a_ge0 = float_ge0 a_tm in
315 let b_ge0 = float_ge0 b_tm in
316 let th0 = INST[f_tm, x_var_real; a_tm, a_var_real; b_tm, b_var_real] pow4_th in
317 itlist MY_PROVE_HYP [mul1_th; mul2_th; a_ge0; b_ge0] th0;;
318
319 let eval_pow2_pow4_high =
320 let pow4_th = (UNDISCH_ALL o prove)(`interval_arith (x pow 2) (&0, a) ==>
321 a * a <= b ==>
322 interval_arith (x pow 4) (&0, b)`,
323 REWRITE_TAC[interval_arith; ARITH_RULE `4 = 2 + 2`; REAL_POW_ADD] THEN
324 REPEAT STRIP_TAC THENL [
325 MATCH_MP_TAC REAL_LE_MUL THEN REWRITE_TAC[REAL_LE_POW_2];
326 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a * a:real` THEN
327 ASM_REWRITE_TAC[] THEN
328 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[REAL_LE_POW_2]
329 ]) in
330 fun pp f_tm ->
331 let pow2_th = eval_pow2_high pp f_tm in
332 let a_tm = (rand o rand o concl) pow2_th in
333 let mul_th = float_mul_hi pp a_tm a_tm in
334 let b_tm = (rand o concl) mul_th in
335 let th0 = INST[f_tm, x_var_real; a_tm, a_var_real; b_tm, b_var_real] pow4_th in
336 pow2_th, MY_PROVE_HYP mul_th (MY_PROVE_HYP pow2_th th0);;
337
338 let eval_pow2_pow4_low =
339 let pow4_th = (UNDISCH_ALL o prove)(`interval_arith a (&0, x pow 2) ==>
340 b <= a * a ==>
341 (&0 <= b <=> T) ==>
342 interval_arith b (&0, x pow 4)`,
343 REWRITE_TAC[interval_arith; ARITH_RULE `4 = 2 + 2`; REAL_POW_ADD] THEN
344 REPEAT STRIP_TAC THENL [
345 ASM_REWRITE_TAC[];
346 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `a * a:real` THEN
347 ASM_REWRITE_TAC[] THEN
348 MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[REAL_LE_POW_2]
349 ]) in
350 fun pp f_tm ->
351 let pow2_th = eval_pow2_low pp f_tm in
352 let a_tm = (rand o rator o concl) pow2_th in
353 let mul_th = float_mul_lo pp a_tm a_tm in
354 let b_tm = (rand o rator o concl) mul_th in
355 let b_ge0_th = float_ge0 b_tm in
356 let th0 = INST[f_tm, x_var_real; a_tm, a_var_real; b_tm, b_var_real] pow4_th in
357 pow2_th, MY_PROVE_HYP b_ge0_th (MY_PROVE_HYP mul_th (MY_PROVE_HYP pow2_th th0));;
358
359
360 end;;
361
362
363 (*
364 let pp = 5;;
365 let cs_tm = `[&1 / &3; #0.1]`;;
366 let cs_list = mk_poly_coeffs pp cs_tm;;
367 let x_tm = `pi:real`;;
368 let x_th = (REWRITE_RULE[real_zero] o RULE o ASSUME) `interval_arith (&3) (real_zero, pi)`;;
369 let x_th = float_interval_const pp x_tm;;
370 let x_th = (REWRITE_RULE[real_zero] o RULE o ASSUME) `interval_arith x (real_zero, &3)`;;
371
372
373
374 ;;
375 let pp = 10;;
376 let cs_tm = `[&1 / &3; &1 / &10; #2.1]`;;
377 let cs_list = mk_poly_coeffs pp cs_tm;;
378 let x_th = (RULE o ASSUME) `interval_arith x (&3, &3)`;;
379 let y_th = (REWRITE_RULE[real_zero] o RULE o ASSUME) `interval_arith y (real_zero, &3)`;;
380 let z_th = (REWRITE_RULE[real_zero] o RULE o ASSUME) `interval_arith (&3) (real_zero, z)`;;
381 test 1000 (eval_interval_poly_f pp (cs_tm, cs_list)) x_th;;
382 test 1000 (eval_high_poly_f_pos_pos pp (cs_tm, cs_list)) y_th;;
383 test 1000 (eval_low_poly_f_pos_pos pp (cs_tm, cs_list)) z_th;;
384 *)