| 1 |
(* ========================================================================== *) |
| 2 |
(* Formal verification of nonlinear inequalities in HOL Light *) |
| 3 |
(* *) |
| 4 |
(* Copyright (c) 2012 Alexey Solovyev *) |
| 5 |
(* *) |
| 6 |
(* This file is distributed under the terms of the MIT licence *) |
| 7 |
(* ========================================================================== *) |
| 8 |
|
| 9 |
(* -------------------------------------------------------------------------- *) |
| 10 |
(* Additional floating point procedures *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
needs "Formal_ineqs/arith/arith_float.hl";; |
| 14 |
needs "Formal_ineqs/misc/misc_vars.hl";; |
| 15 |
|
| 16 |
module More_float = struct |
| 17 |
|
| 18 |
open Misc_functions;; |
| 19 |
open Float_theory;; |
| 20 |
open Interval_arith;; |
| 21 |
open Arith_float;; |
| 22 |
open Misc_vars;; |
| 23 |
|
| 24 |
prioritize_real();; |
| 25 |
|
| 26 |
let RULE = UNDISCH_ALL o Arith_nat.NUMERALS_TO_NUM o REWRITE_RULE[FLOAT_OF_NUM; min_exp_def; GSYM IMP_IMP] o SPEC_ALL;; |
| 27 |
|
| 28 |
(*************************************) |
| 29 |
(* More float *) |
| 30 |
|
| 31 |
|
| 32 |
(* Converts a float term to the corresponding rational number *) |
| 33 |
let num_of_float_tm tm = |
| 34 |
let s, n_tm, e_tm = dest_float tm in |
| 35 |
let b = Num.num_of_int Arith_num.arith_base in |
| 36 |
let m = Num.num_of_int Float_theory.min_exp in |
| 37 |
let ( * ), (^), (-), (!) = ( */ ), ( **/ ), (-/), Arith_nat.raw_dest_hash in |
| 38 |
let r = !n_tm * (b ^ (!e_tm - m)) in |
| 39 |
if s = "T" then minus_num r else r;; |
| 40 |
|
| 41 |
(* Converts a float term to a floating-point number *) |
| 42 |
let float_of_float_tm tm = |
| 43 |
(Num.float_of_num o num_of_float_tm) tm;; |
| 44 |
|
| 45 |
(* Converts a floating-point number into a float term *) |
| 46 |
let float_tm_of_float = |
| 47 |
let split = |
| 48 |
let b = float_of_int Arith_num.arith_base in |
| 49 |
let log_b = log b in |
| 50 |
let rec fix t k = |
| 51 |
if t = 0.0 || t = infinity || t = nan then |
| 52 |
t, k |
| 53 |
else if t < 1.0 then |
| 54 |
fix (t *. b) (k - 1) |
| 55 |
else if t >= b then |
| 56 |
fix (t /. b) (k + 1) |
| 57 |
else |
| 58 |
t, k in |
| 59 |
fun f -> |
| 60 |
if f = 0.0 then |
| 61 |
false, f, 0 |
| 62 |
else |
| 63 |
let s, x = if f < 0.0 then true, -.f else false, f in |
| 64 |
let e = -.floor (log x /. log_b) in |
| 65 |
let k = -int_of_float e in |
| 66 |
let t, n = fix (x *. (b ** e)) k in |
| 67 |
s, t, n |
| 68 |
and extract = |
| 69 |
let b = float_of_int Arith_num.arith_base in |
| 70 |
let nb = Num.num_of_int Arith_num.arith_base in |
| 71 |
let rec step k f acc = |
| 72 |
if k <= 0 then |
| 73 |
acc |
| 74 |
else |
| 75 |
let d = int_of_float f in |
| 76 |
step (k - 1) ((f -. float_of_int d) *. b) (Num.num_of_int d +/ (nb */ acc)) in |
| 77 |
fun pp f -> |
| 78 |
step pp f (Num.num_of_int 0) |
| 79 |
in |
| 80 |
fun pp f -> |
| 81 |
let s, x, k = split f in |
| 82 |
let n = extract pp x in |
| 83 |
let n_tm = rand (Arith_num.mk_numeral_array n) in |
| 84 |
let e_tm = rand (Arith_num.mk_small_numeral_array (min_exp + k - pp + 1)) in |
| 85 |
let sign = if s then "T" else "F" in |
| 86 |
make_float sign n_tm e_tm;; |
| 87 |
|
| 88 |
(* Creates a (not normalized) floating-point number from a given natural number. *) |
| 89 |
(* Returns the theorem |- &n = float F n min_exp and the term n *) |
| 90 |
let float_eq_th_of_num = |
| 91 |
let conv_th = (Arith_nat.NUMERALS_TO_NUM o REWRITE_RULE[min_exp_def] o SPEC_ALL) FLOAT_OF_NUM in |
| 92 |
fun n -> |
| 93 |
let _ = if sign_num n < 0 then failwith "float_eq_th_of_num: negative number" in |
| 94 |
let n_tm = rand (Arith_nat.mk_numeral_array n) in |
| 95 |
INST[n_tm, n_var_num] conv_th, n_tm;; |
| 96 |
|
| 97 |
(* |- ##0 = &0, |- ##1 = &1, |- ##2 = &2, |- ##3 = &3, |- ##4 = &4 *) |
| 98 |
let float0_eq = FLOAT_TO_NUM_CONV (mk_float 0 0) and |
| 99 |
float1_eq = FLOAT_TO_NUM_CONV (mk_float 1 0) and |
| 100 |
float2_eq = FLOAT_TO_NUM_CONV (mk_float 2 0) and |
| 101 |
float3_eq = FLOAT_TO_NUM_CONV (mk_float 3 0) and |
| 102 |
float4_eq = FLOAT_TO_NUM_CONV (mk_float 4 0);; |
| 103 |
|
| 104 |
(* |- D_k _0 = k for k = 1, 2, 3 *) |
| 105 |
let num1_eq, num2_eq, num3_eq = |
| 106 |
let conv = SYM o REWRITE_RULE[Arith_num.NUM_THM] o Arith_nat.NUMERAL_TO_NUM_CONV in |
| 107 |
conv `1`, conv `2`, conv `3`;; |
| 108 |
|
| 109 |
(*********************) |
| 110 |
|
| 111 |
let float_F_const = `float_num F`;; |
| 112 |
|
| 113 |
let mk_float_small n = |
| 114 |
let n_tm0 = mk_small_numeral n in |
| 115 |
let n_th = Arith_nat.NUMERAL_TO_NUM_CONV n_tm0 in |
| 116 |
let n_tm = rand(rand(concl n_th)) in |
| 117 |
mk_comb(mk_comb(float_F_const, n_tm), min_exp_num_const);; |
| 118 |
|
| 119 |
(* Small float constants and intervals *) |
| 120 |
let one_float = mk_float_small 1 and |
| 121 |
two_float = mk_float_small 2 and |
| 122 |
one_interval = mk_float_interval_small_num 1 and |
| 123 |
two_interval = mk_float_interval_small_num 2;; |
| 124 |
let neg_two_interval = float_interval_neg two_interval;; |
| 125 |
|
| 126 |
(* ----------------------------------------- *) |
| 127 |
(* float_eq0 *) |
| 128 |
(* ----------------------------------------- *) |
| 129 |
|
| 130 |
let FLOAT_EQ_0' = (GEN_REWRITE_RULE (RAND_CONV o RAND_CONV) [NUMERAL] o SPEC_ALL) |
| 131 |
FLOAT_EQ_0;; |
| 132 |
|
| 133 |
|
| 134 |
let float_eq0 f_tm = |
| 135 |
let lhs, e_tm = dest_comb f_tm in |
| 136 |
let lhs2, n_tm = dest_comb lhs in |
| 137 |
let th0 = INST[rand lhs2, s_var_bool; n_tm, n_var_num; e_tm, e_var_num] FLOAT_EQ_0' in |
| 138 |
let eq_th = Arith_nat.raw_eq0_hash_conv n_tm in |
| 139 |
TRANS th0 eq_th;; |
| 140 |
|
| 141 |
|
| 142 |
|
| 143 |
(* ----------------------------------------- *) |
| 144 |
(* float_interval_scale *) |
| 145 |
(* ----------------------------------------- *) |
| 146 |
|
| 147 |
|
| 148 |
let float_interval_scale pp c_tm th = |
| 149 |
let c_th = mk_const_interval c_tm in |
| 150 |
float_interval_mul pp c_th th;; |
| 151 |
|
| 152 |
|
| 153 |
(* ----------------------------------------- *) |
| 154 |
(* float_interval_lt0 *) |
| 155 |
(* ----------------------------------------- *) |
| 156 |
|
| 157 |
|
| 158 |
let FLOAT_INTERVAL_LT0' = (UNDISCH_ALL o prove) |
| 159 |
(`interval_arith x (lo, hi) ==> (hi < &0 <=> T) ==> x < &0`, |
| 160 |
REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC);; |
| 161 |
|
| 162 |
let float_interval_lt0 th = |
| 163 |
let x_tm, bounds = dest_interval_arith (concl th) in |
| 164 |
let lo_tm, hi_tm = dest_pair bounds in |
| 165 |
let lt0_th = float_lt0 hi_tm in |
| 166 |
let _ = ((rand o concl) lt0_th = t_const) || failwith "float_interval_lt0: &0 <= hi" in |
| 167 |
let th0 = INST[x_tm, x_var_real; lo_tm, lo_var_real; hi_tm, hi_var_real] FLOAT_INTERVAL_LT0' in |
| 168 |
(MY_PROVE_HYP th o MY_PROVE_HYP lt0_th) th0;; |
| 169 |
|
| 170 |
|
| 171 |
(* ----------------------------------------- *) |
| 172 |
(* float_pos *) |
| 173 |
(* ----------------------------------------- *) |
| 174 |
|
| 175 |
let FLOAT_F_POS' = SPEC_ALL FLOAT_F_POS;; |
| 176 |
|
| 177 |
(* Returns &0 <= float F n e *) |
| 178 |
let float_pos tm = |
| 179 |
let _, n_tm, e_tm = dest_float tm in |
| 180 |
INST[n_tm, n_var_num; e_tm, e_var_num] FLOAT_F_POS';; |
| 181 |
|
| 182 |
|
| 183 |
|
| 184 |
(* ----------------------------------------- *) |
| 185 |
(* float_iabs *) |
| 186 |
(* ----------------------------------------- *) |
| 187 |
|
| 188 |
let FLOAT_NEG_F' = RULE FLOAT_NEG_T;; |
| 189 |
let FLOAT_NEG_T' = RULE FLOAT_NEG_F;; |
| 190 |
|
| 191 |
let float_neg tm = |
| 192 |
let sign, n_tm, e_tm = dest_float tm in |
| 193 |
if sign = "T" then |
| 194 |
INST[n_tm, n_var_num; e_tm, e_var_num] FLOAT_NEG_T' |
| 195 |
else |
| 196 |
INST[n_tm, n_var_num; e_tm, e_var_num] FLOAT_NEG_F';; |
| 197 |
|
| 198 |
|
| 199 |
let IABS' = RULE iabs;; |
| 200 |
|
| 201 |
|
| 202 |
let float_iabs int_tm = |
| 203 |
let lo_tm, hi_tm = dest_pair int_tm in |
| 204 |
let neg_lo_th = float_neg lo_tm in |
| 205 |
let max_th = SYM (float_max hi_tm ((rand o rator o concl) neg_lo_th)) in |
| 206 |
let lhs, rhs = dest_comb (concl max_th) in |
| 207 |
let th0 = SYM (EQ_MP (AP_TERM lhs (AP_TERM (rator rhs) neg_lo_th)) max_th) in |
| 208 |
let th1 = INST[lo_tm, x_lo_var; hi_tm, x_hi_var] IABS' in |
| 209 |
TRANS th1 th0;; |
| 210 |
|
| 211 |
|
| 212 |
let FLOAT_IABS_FF = prove(`iabs (float_num F n1 e1, float_num F n2 e2) = float_num F n2 e2`, |
| 213 |
REWRITE_TAC[iabs] THEN |
| 214 |
MP_TAC (SPECL [`n1:num`; `e1:num`] FLOAT_F_POS) THEN |
| 215 |
MP_TAC (SPECL [`n2:num`; `e2:num`] FLOAT_F_POS) THEN |
| 216 |
REAL_ARITH_TAC);; |
| 217 |
|
| 218 |
|
| 219 |
let FLOAT_IABS_TT = prove(`iabs (float_num T n1 e1, float_num T n2 e2) = float_num F n1 e1`, |
| 220 |
REWRITE_TAC[iabs; GSYM FLOAT_NEG_F] THEN |
| 221 |
MP_TAC (SPECL [`n1:num`; `e1:num`] FLOAT_F_POS) THEN |
| 222 |
MP_TAC (SPECL [`n2:num`; `e2:num`] FLOAT_T_NEG) THEN |
| 223 |
REAL_ARITH_TAC);; |
| 224 |
|
| 225 |
|
| 226 |
(* ----------------------------------------- *) |
| 227 |
(* interval_not_zero *) |
| 228 |
(* ----------------------------------------- *) |
| 229 |
|
| 230 |
let INTERVAL_NOT_ZERO1' = (UNDISCH_ALL o prove) |
| 231 |
(`(&0 < lo <=> T) ==> interval_not_zero (lo, hi)`, SIMP_TAC[interval_not_zero]);; |
| 232 |
let INTERVAL_NOT_ZERO2' = (UNDISCH_ALL o prove) |
| 233 |
(`(hi < &0 <=> T) ==> interval_not_zero (lo, hi)`, SIMP_TAC[interval_not_zero]);; |
| 234 |
|
| 235 |
|
| 236 |
let check_interval_not_zero int_tm = |
| 237 |
let lo, hi = dest_pair int_tm in |
| 238 |
let inst = INST[lo, lo_var_real; hi, hi_var_real] in |
| 239 |
let s1, _, _ = dest_float lo in |
| 240 |
if s1 = "F" then |
| 241 |
let gt_th = float_gt0 lo in |
| 242 |
if (fst o dest_const o rand o concl) gt_th <> "T" then |
| 243 |
failwith "check_interval_not_zero: &0 < lo <=> F" |
| 244 |
else |
| 245 |
(MY_PROVE_HYP gt_th o inst) INTERVAL_NOT_ZERO1' |
| 246 |
else |
| 247 |
let lt_th = float_lt0 hi in |
| 248 |
if (fst o dest_const o rand o concl) lt_th <> "T" then |
| 249 |
failwith "check_interval_not_zero: hi < &0 <=> F" |
| 250 |
else |
| 251 |
(MY_PROVE_HYP lt_th o inst) INTERVAL_NOT_ZERO2';; |
| 252 |
|
| 253 |
|
| 254 |
|
| 255 |
(* ----------------------------------------- *) |
| 256 |
(* interval_pos *) |
| 257 |
(* ----------------------------------------- *) |
| 258 |
|
| 259 |
let INTERVAL_POS' = (UNDISCH_ALL o prove) |
| 260 |
(`(&0 < lo <=> T) ==> interval_pos (lo, hi:real)`, SIMP_TAC[interval_pos]);; |
| 261 |
|
| 262 |
|
| 263 |
let check_interval_pos int_tm = |
| 264 |
let lo, hi = dest_pair int_tm in |
| 265 |
let gt_th = float_gt0 lo in |
| 266 |
if (fst o dest_const o rand o concl) gt_th <> "T" then |
| 267 |
failwith "check_interval_pos: &0 < lo <=> F" |
| 268 |
else |
| 269 |
(MY_PROVE_HYP gt_th o INST[lo, lo_var_real; hi, hi_var_real]) INTERVAL_POS';; |
| 270 |
|
| 271 |
|
| 272 |
(* ----------------------------------------- *) |
| 273 |
(* interval_neg *) |
| 274 |
(* ----------------------------------------- *) |
| 275 |
|
| 276 |
let INTERVAL_NEG' = (UNDISCH_ALL o prove) |
| 277 |
(`(hi < &0 <=> T) ==> interval_neg (lo:real, hi:real)`, SIMP_TAC[interval_neg]);; |
| 278 |
|
| 279 |
|
| 280 |
let check_interval_neg int_tm = |
| 281 |
let lo, hi = dest_pair int_tm in |
| 282 |
let cmp_th = float_lt0 hi in |
| 283 |
if (fst o dest_const o rand o concl) cmp_th <> "T" then |
| 284 |
failwith "check_interval_neg: hi < &0 <=> F" |
| 285 |
else |
| 286 |
(MY_PROVE_HYP cmp_th o INST[lo, lo_var_real; hi, hi_var_real]) INTERVAL_NEG';; |
| 287 |
|
| 288 |
(* ----------------------------------------- *) |
| 289 |
(* interval_gt *) |
| 290 |
(* ----------------------------------------- *) |
| 291 |
|
| 292 |
let check_interval_gt = |
| 293 |
let gt_th0 = (UNDISCH_ALL o prove)(`(y < lo <=> T) ==> interval_gt y (lo, hi:real)`, |
| 294 |
REWRITE_TAC[interval_gt]) in |
| 295 |
fun y_tm int_tm -> |
| 296 |
let lo, hi = dest_pair int_tm in |
| 297 |
let lt_th = float_lt y_tm lo in |
| 298 |
if (fst o dest_const o rand o concl) lt_th <> "T" then |
| 299 |
failwith "check_interval_gt: y < lo <=> F" |
| 300 |
else |
| 301 |
(MY_PROVE_HYP lt_th o |
| 302 |
INST[lo, lo_var_real; hi, hi_var_real; y_tm, y_var_real]) gt_th0;; |
| 303 |
|
| 304 |
|
| 305 |
(* ----------------------------------------- *) |
| 306 |
(* check_interval_iabs *) |
| 307 |
(* ----------------------------------------- *) |
| 308 |
|
| 309 |
|
| 310 |
(* proves |- iabs int < rhs <=> T *) |
| 311 |
let check_interval_iabs int_tm rhs_tm = |
| 312 |
let iabs_eq = float_iabs int_tm in |
| 313 |
let lt_th = float_lt (rand (concl iabs_eq)) rhs_tm in |
| 314 |
if (fst o dest_const o rand o concl) lt_th <> "T" then |
| 315 |
failwith "check_interval_iabs: iabs < rhs <=> F" |
| 316 |
else |
| 317 |
let th0 = AP_THM (AP_TERM lt_op_real iabs_eq) rhs_tm in |
| 318 |
TRANS th0 lt_th;; |
| 319 |
|
| 320 |
|
| 321 |
|
| 322 |
(* ----------------------------------------- *) |
| 323 |
(* inv *) |
| 324 |
(* ----------------------------------------- *) |
| 325 |
|
| 326 |
let float_inv_hi = |
| 327 |
let div_lemma = (RULE o prove) |
| 328 |
(`&1 / x <= hi ==> inv x <= hi`, |
| 329 |
REWRITE_TAC[real_div; REAL_MUL_LID]) in |
| 330 |
fun pp tm -> |
| 331 |
let div_th = float_div_hi pp one_float tm in |
| 332 |
let hi_tm = rand (concl div_th) in |
| 333 |
let th0 = INST[tm, x_var_real; hi_tm, hi_var_real] div_lemma in |
| 334 |
MY_PROVE_HYP div_th th0;; |
| 335 |
|
| 336 |
let float_inv_lo = |
| 337 |
let div_lemma = (RULE o prove) |
| 338 |
(`lo <= &1 / x ==> lo <= inv x`, |
| 339 |
REWRITE_TAC[real_div; REAL_MUL_LID]) in |
| 340 |
fun pp tm -> |
| 341 |
let div_th = float_div_lo pp one_float tm in |
| 342 |
let lo_tm = rand (rator (concl div_th)) in |
| 343 |
let th0 = INST[tm, x_var_real; lo_tm, lo_var_real] div_lemma in |
| 344 |
MY_PROVE_HYP div_th th0;; |
| 345 |
|
| 346 |
let float_interval_inv = |
| 347 |
let INV_EQ_DIV_LEMMA = prove(`&1 / x = inv x`, REWRITE_TAC[real_div; REAL_MUL_LID]) in |
| 348 |
fun pp th -> |
| 349 |
let x_tm = (rand o rator o concl) th in |
| 350 |
let div_th = INST[x_tm, x_var_real] INV_EQ_DIV_LEMMA in |
| 351 |
let th0 = float_interval_div pp one_interval th in |
| 352 |
let lhs, rhs = dest_comb (concl th0) in |
| 353 |
let lhs2, rhs2 = dest_comb lhs in |
| 354 |
EQ_MP (AP_THM (AP_TERM lhs2 div_th) rhs) th0;; |
| 355 |
|
| 356 |
|
| 357 |
(* Explicit representation of inv(&2) *) |
| 358 |
let float_inv2_th = |
| 359 |
let one_float_eq_one = FLOAT_TO_NUM_CONV one_float in |
| 360 |
let inv2_eq_lemma = prove(`interval_arith (&2 * x) (&1, &1) ==> inv (&2) = x`, |
| 361 |
REWRITE_TAC[interval_arith] THEN CONV_TAC REAL_FIELD) in |
| 362 |
let half_tm = (fst o dest_pair o rand o concl) (float_interval_inv 1 two_interval) in |
| 363 |
let half_interval = mk_const_interval half_tm in |
| 364 |
let mul_th = REWRITE_RULE[one_float_eq_one] (float_interval_mul 2 two_interval half_interval) in |
| 365 |
MATCH_MP inv2_eq_lemma mul_th;; |
| 366 |
|
| 367 |
let float_inv2 = rand (concl float_inv2_th);; |
| 368 |
let inv2_interval = mk_const_interval float_inv2;; |
| 369 |
|
| 370 |
|
| 371 |
|
| 372 |
(*****************************************) |
| 373 |
(* bounded_on_int *) |
| 374 |
|
| 375 |
let norm_derivative d_th eq_th = |
| 376 |
let lhs, rhs = (dest_eq o concl) d_th in |
| 377 |
let lhs2, rhs2 = dest_comb lhs in |
| 378 |
let th0 = AP_THM (AP_TERM (rator lhs2) eq_th) rhs2 in |
| 379 |
TRANS (SYM th0) d_th;; |
| 380 |
|
| 381 |
let norm_diff d_th eq_th = |
| 382 |
let lhs, rhs = (dest_comb o concl) d_th in |
| 383 |
let th0 = AP_THM (AP_TERM (rator lhs) eq_th) rhs in |
| 384 |
EQ_MP th0 d_th;; |
| 385 |
|
| 386 |
let norm_interval int_th eq_th = |
| 387 |
let lhs, rhs = (dest_comb o concl) int_th in |
| 388 |
let th0 = AP_THM (AP_TERM (rator lhs) eq_th) rhs in |
| 389 |
EQ_MP (SYM th0) int_th;; |
| 390 |
|
| 391 |
let norm_second_derivative th eq_th = |
| 392 |
let lhs, dd_bounds = dest_comb (concl th) in |
| 393 |
let lhs2, int_tm = dest_comb lhs in |
| 394 |
let th0 = AP_THM (AP_THM (AP_TERM (rator lhs2) eq_th) int_tm) dd_bounds in |
| 395 |
EQ_MP th0 th;; |
| 396 |
|
| 397 |
let norm_lin_approx th eq_th = |
| 398 |
let lhs, df_bounds = dest_comb (concl th) in |
| 399 |
let lhs2, f_bounds = dest_comb lhs in |
| 400 |
let lhs3, x_tm = dest_comb lhs2 in |
| 401 |
let th0 = AP_THM (AP_THM (AP_THM (AP_TERM (rator lhs3) eq_th) x_tm) f_bounds) df_bounds in |
| 402 |
EQ_MP th0 th;; |
| 403 |
|
| 404 |
|
| 405 |
|
| 406 |
let BOUNDED_ON_INT = (UNDISCH_ALL o prove)(`(!x. interval_arith x int ==> |
| 407 |
interval_arith (f x) f_bounds) |
| 408 |
==> bounded_on_int f int f_bounds`, |
| 409 |
REWRITE_TAC[bounded_on_int; interval_arith]);; |
| 410 |
|
| 411 |
|
| 412 |
let BOUNDED_ON_INT_DEST = (UNDISCH_ALL o prove)(`bounded_on_int f int f_bounds ==> |
| 413 |
(!x. interval_arith x int ==> interval_arith (f x) f_bounds)`, |
| 414 |
REWRITE_TAC[bounded_on_int; interval_arith]);; |
| 415 |
|
| 416 |
|
| 417 |
(* Given a theorem (interval_arith x int |- interval_arith (f x) f_bounds), yields |
| 418 |
|- bounded_on_int (\x. f x) int f_bounds *) |
| 419 |
let mk_bounded_on_int th = |
| 420 |
let int_tm = (rand o hd o hyp) th in |
| 421 |
let lhs, f_bounds_tm = dest_comb (concl th) in |
| 422 |
let lhs2, rhs2 = dest_comb lhs in |
| 423 |
let f_tm = mk_abs (x_var_real, rhs2) in |
| 424 |
let b_th0 = (SYM o BETA_CONV) (mk_comb (f_tm , x_var_real)) in |
| 425 |
let b_th1 = AP_THM (AP_TERM lhs2 b_th0) f_bounds_tm in |
| 426 |
let th2 = EQ_MP b_th1 th in |
| 427 |
let th3 = DISCH_ALL th2 in |
| 428 |
let th4 = GEN x_var_real th3 in |
| 429 |
let th_int = INST[int_tm, int_var; f_bounds_tm, f_bounds_var; |
| 430 |
f_tm, f_var_fun] BOUNDED_ON_INT in |
| 431 |
MY_PROVE_HYP th4 th_int;; |
| 432 |
|
| 433 |
|
| 434 |
let dest_bounded_on_int th = |
| 435 |
let lhs, f_bounds = dest_comb (concl th) in |
| 436 |
let lhs2, int_tm = dest_comb lhs in |
| 437 |
let f_tm = rand lhs2 in |
| 438 |
let th0 = INST[f_tm, f_var_fun; int_tm, int_var; f_bounds, f_bounds_var] BOUNDED_ON_INT_DEST in |
| 439 |
let th1 = UNDISCH_ALL (SPEC x_var_real (MY_PROVE_HYP th th0)) in |
| 440 |
if is_abs f_tm then |
| 441 |
let f_tm = (rand o rator o concl) th1 in |
| 442 |
let eq_th = BETA_CONV f_tm in |
| 443 |
norm_interval th1 (SYM eq_th) |
| 444 |
else |
| 445 |
th1;; |
| 446 |
|
| 447 |
|
| 448 |
let dest_bounded_on_int_raw th = |
| 449 |
let lhs, f_bounds = dest_comb (concl th) in |
| 450 |
let lhs2, int_tm = dest_comb lhs in |
| 451 |
let f_tm = rand lhs2 in |
| 452 |
let th0 = INST[f_tm, f_var_fun; int_tm, int_var; f_bounds, f_bounds_var] BOUNDED_ON_INT_DEST in |
| 453 |
UNDISCH_ALL (SPEC x_var_real (MY_PROVE_HYP th th0));; |
| 454 |
|
| 455 |
|
| 456 |
(***********************************) |
| 457 |
(* bounded_on_int arithmetic *) |
| 458 |
|
| 459 |
let bounded_on_int_scale pp c_tm th = |
| 460 |
let i_th = dest_bounded_on_int th in |
| 461 |
let th0 = float_interval_scale pp c_tm i_th in |
| 462 |
mk_bounded_on_int th0;; |
| 463 |
|
| 464 |
|
| 465 |
let bounded_on_int_mul_int pp int_th th = |
| 466 |
let i_th = dest_bounded_on_int th in |
| 467 |
let th0 = float_interval_mul pp int_th i_th in |
| 468 |
mk_bounded_on_int th0;; |
| 469 |
|
| 470 |
|
| 471 |
let bounded_on_int_neg th1 = |
| 472 |
let i_th = dest_bounded_on_int th1 in |
| 473 |
let th0 = float_interval_neg i_th in |
| 474 |
mk_bounded_on_int th0;; |
| 475 |
|
| 476 |
|
| 477 |
let bounded_on_int_add pp th1 th2 = |
| 478 |
let i_th1, i_th2 = dest_bounded_on_int th1, dest_bounded_on_int th2 in |
| 479 |
let th0 = float_interval_add pp i_th1 i_th2 in |
| 480 |
mk_bounded_on_int th0;; |
| 481 |
|
| 482 |
|
| 483 |
let bounded_on_int_sub pp th1 th2 = |
| 484 |
let i_th1, i_th2 = dest_bounded_on_int th1, dest_bounded_on_int th2 in |
| 485 |
let th0 = float_interval_sub pp i_th1 i_th2 in |
| 486 |
mk_bounded_on_int th0;; |
| 487 |
|
| 488 |
|
| 489 |
let bounded_on_int_mul pp th1 th2 = |
| 490 |
let i_th1, i_th2 = dest_bounded_on_int th1, dest_bounded_on_int th2 in |
| 491 |
let th0 = float_interval_mul pp i_th1 i_th2 in |
| 492 |
mk_bounded_on_int th0;; |
| 493 |
|
| 494 |
|
| 495 |
let bounded_on_int_mul_raw pp th1 th2 = |
| 496 |
let i_th1, i_th2 = dest_bounded_on_int_raw th1, dest_bounded_on_int_raw th2 in |
| 497 |
let th0 = float_interval_mul pp i_th1 i_th2 in |
| 498 |
mk_bounded_on_int th0;; |
| 499 |
|
| 500 |
|
| 501 |
|
| 502 |
let bounded_on_int_div pp th1 th2 = |
| 503 |
let i_th1, i_th2 = dest_bounded_on_int th1, dest_bounded_on_int th2 in |
| 504 |
let th0 = float_interval_div pp i_th1 i_th2 in |
| 505 |
mk_bounded_on_int th0;; |
| 506 |
|
| 507 |
|
| 508 |
(************************************) |
| 509 |
let ADD_INEQ_HI = (RULE o REAL_ARITH) `x1 <= y1 /\ x2 <= y2 /\ y1 + y2 <= y ==> x1 + x2 <= y`;; |
| 510 |
let ADD_INEQ_LO = (RULE o REAL_ARITH) `x1 <= y1 /\ x2 <= y2 /\ x <= x1 + x2 ==> x <= y1 + y2`;; |
| 511 |
let SUB_INEQ_HI = (RULE o REAL_ARITH) `x1 <= y1 /\ y2 <= x2 /\ y1 - y2 <= y ==> x1 - x2 <= y`;; |
| 512 |
let SUB_INEQ_LO = (RULE o REAL_ARITH) `x1 <= y1 /\ y2 <= x2 /\ x <= x1 - x2 ==> x <= y1 - y2`;; |
| 513 |
let MUL_INEQ_HI = (UNDISCH_ALL o REWRITE_RULE[GSYM IMP_IMP] o prove) |
| 514 |
(`&0 <= x1 /\ &0 <= x2 /\ x1 <= y1 /\ x2 <= y2 /\ y1 * y2 <= y ==> x1 * x2 <= y`, |
| 515 |
DISCH_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN |
| 516 |
EXISTS_TAC `y1 * y2` THEN ASM_REWRITE_TAC[] THEN |
| 517 |
MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[]);; |
| 518 |
|
| 519 |
let MUL_INEQ_POS_CONST_HI = (UNDISCH_ALL o prove) |
| 520 |
(`(&0 <= x <=> T) ==> y1 <= y2 ==> x * y2 <= z ==> x * y1 <= z`, |
| 521 |
REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x * y2` THEN |
| 522 |
ASM_REWRITE_TAC[] THEN MATCH_MP_TAC REAL_LE_LMUL THEN ASM_REWRITE_TAC[]);; |
| 523 |
|
| 524 |
|
| 525 |
let mk_refl_ineq = |
| 526 |
let REAL_LE_REFL' = RULE REAL_LE_REFL in |
| 527 |
fun tm -> INST[tm, x_var_real] REAL_LE_REFL';; |
| 528 |
|
| 529 |
let dest_le_op ineq = |
| 530 |
let lhs, y_tm = dest_comb ineq in |
| 531 |
(rand lhs, y_tm);; |
| 532 |
|
| 533 |
|
| 534 |
let mul_ineq_pos_const_hi pp c_tm ineq = |
| 535 |
let y1_tm, y2_tm = dest_le_op (concl ineq) in |
| 536 |
let ge0_th = float_ge0 c_tm in |
| 537 |
let mul_hi_th = float_mul_hi pp c_tm y2_tm in |
| 538 |
let z_tm = (rand o concl) mul_hi_th in |
| 539 |
(MY_PROVE_HYP ge0_th o MY_PROVE_HYP ineq o MY_PROVE_HYP mul_hi_th o |
| 540 |
INST[c_tm, x_var_real; y1_tm, y1_var_real; y2_tm, y2_var_real; z_tm, z_var_real]) |
| 541 |
MUL_INEQ_POS_CONST_HI;; |
| 542 |
|
| 543 |
|
| 544 |
let mul_ineq_hi pp ineq1 ineq2 = |
| 545 |
let x1_tm, y1_tm = dest_le_op (concl ineq1) in |
| 546 |
let x2_tm, y2_tm = dest_le_op (concl ineq2) in |
| 547 |
let x1_pos, x2_pos = float_pos x1_tm, float_pos x2_tm in |
| 548 |
let rhs_mul = float_mul_hi pp y1_tm y2_tm in |
| 549 |
let y_tm = (rand o concl) rhs_mul in |
| 550 |
let th0 = INST[x1_tm, x1_var_real; y1_tm, y1_var_real; |
| 551 |
x2_tm, x2_var_real; y2_tm, y2_var_real; |
| 552 |
y_tm, y_var_real] MUL_INEQ_HI in |
| 553 |
(MY_PROVE_HYP x1_pos o MY_PROVE_HYP x2_pos o MY_PROVE_HYP ineq1 o |
| 554 |
MY_PROVE_HYP ineq2 o MY_PROVE_HYP rhs_mul) th0;; |
| 555 |
|
| 556 |
|
| 557 |
|
| 558 |
let sub_ineq_hi pp ineq1 ineq2 = |
| 559 |
let x1_tm, y1_tm = dest_le_op (concl ineq1) in |
| 560 |
let y2_tm, x2_tm = dest_le_op (concl ineq2) in |
| 561 |
let rhs_sub = float_sub_hi pp y1_tm y2_tm in |
| 562 |
let y_tm = (rand o concl) rhs_sub in |
| 563 |
let th0 = INST[x1_tm, x1_var_real; y1_tm, y1_var_real; |
| 564 |
x2_tm, x2_var_real; y2_tm, y2_var_real; |
| 565 |
y_tm, y_var_real] SUB_INEQ_HI in |
| 566 |
MY_PROVE_HYP ineq1 (MY_PROVE_HYP ineq2 (MY_PROVE_HYP rhs_sub th0));; |
| 567 |
|
| 568 |
|
| 569 |
let sub_ineq_lo pp ineq1 ineq2 = |
| 570 |
let x1_tm, y1_tm = dest_le_op (concl ineq1) in |
| 571 |
let y2_tm, x2_tm = dest_le_op (concl ineq2) in |
| 572 |
let lhs_sub = float_sub_lo pp x1_tm x2_tm in |
| 573 |
let x_tm = (lhand o concl) lhs_sub in |
| 574 |
let th0 = INST[x1_tm, x1_var_real; y1_tm, y1_var_real; |
| 575 |
x2_tm, x2_var_real; y2_tm, y2_var_real; |
| 576 |
x_tm, x_var_real] SUB_INEQ_LO in |
| 577 |
MY_PROVE_HYP ineq1 (MY_PROVE_HYP ineq2 (MY_PROVE_HYP lhs_sub th0));; |
| 578 |
|
| 579 |
|
| 580 |
let add_ineq_hi pp ineq1 ineq2 = |
| 581 |
let x1_tm, y1_tm = dest_le_op (concl ineq1) in |
| 582 |
let x2_tm, y2_tm = dest_le_op (concl ineq2) in |
| 583 |
let rhs_sum = float_add_hi pp y1_tm y2_tm in |
| 584 |
let y_tm = (rand o concl) rhs_sum in |
| 585 |
let th0 = INST[x1_tm, x1_var_real; y1_tm, y1_var_real; |
| 586 |
x2_tm, x2_var_real; y2_tm, y2_var_real; |
| 587 |
y_tm, y_var_real] ADD_INEQ_HI in |
| 588 |
MY_PROVE_HYP ineq1 (MY_PROVE_HYP ineq2 (MY_PROVE_HYP rhs_sum th0));; |
| 589 |
|
| 590 |
|
| 591 |
let add_ineq_lo pp ineq1 ineq2 = |
| 592 |
let x1_tm, y1_tm = dest_le_op (concl ineq1) in |
| 593 |
let x2_tm, y2_tm = dest_le_op (concl ineq2) in |
| 594 |
let lhs_sum = float_add_lo pp x1_tm x2_tm in |
| 595 |
let x_tm = (lhand o concl) lhs_sum in |
| 596 |
let th0 = INST[x1_tm, x1_var_real; y1_tm, y1_var_real; |
| 597 |
x2_tm, x2_var_real; y2_tm, y2_var_real; |
| 598 |
x_tm, x_var_real] ADD_INEQ_LO in |
| 599 |
MY_PROVE_HYP ineq1 (MY_PROVE_HYP ineq2 (MY_PROVE_HYP lhs_sum th0));; |
| 600 |
|
| 601 |
|
| 602 |
end;; |