| 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 |
(* Formal interval evaluation of arithmetic expressions *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
needs "Formal_ineqs/arith/float_pow.hl";; |
| 14 |
needs "Formal_ineqs/arith/more_float.hl";; |
| 15 |
needs "Formal_ineqs/trig/exp_eval.hl";; |
| 16 |
needs "Formal_ineqs/trig/log_eval.hl";; |
| 17 |
needs "Formal_ineqs/trig/atn_eval.hl";; |
| 18 |
needs "Formal_ineqs/trig/asn_acs_eval.hl";; |
| 19 |
needs "Formal_ineqs/trig/cos_eval.hl";; |
| 20 |
needs "Formal_ineqs/trig/sin_eval.hl";; |
| 21 |
needs "Formal_ineqs/trig/matan_eval.hl";; |
| 22 |
needs "Formal_ineqs/misc/misc_functions.hl";; |
| 23 |
needs "Formal_ineqs/misc/misc_vars.hl";; |
| 24 |
|
| 25 |
module Eval_interval = struct |
| 26 |
|
| 27 |
open Misc_functions;; |
| 28 |
open Interval_arith;; |
| 29 |
open Arith_float;; |
| 30 |
open Float_pow;; |
| 31 |
open Exp_eval;; |
| 32 |
open Log_eval;; |
| 33 |
open Atn_eval;; |
| 34 |
open Asn_acs_eval;; |
| 35 |
open Cos_eval;; |
| 36 |
open Sin_eval;; |
| 37 |
open Matan_eval;; |
| 38 |
open More_float;; |
| 39 |
open Misc_vars;; |
| 40 |
|
| 41 |
(* Creates an interval approximation of the given decimal term *) |
| 42 |
let mk_float_interval_decimal = |
| 43 |
let DECIMAL' = SPEC_ALL DECIMAL in |
| 44 |
fun pp decimal_tm -> |
| 45 |
let n_tm, d_tm = dest_binary "DECIMAL" decimal_tm in |
| 46 |
let n, d = dest_numeral n_tm, dest_numeral d_tm in |
| 47 |
let n_int, d_int = mk_float_interval_num n, mk_float_interval_num d in |
| 48 |
let int = float_interval_div pp n_int d_int in |
| 49 |
let eq_th = INST[n_tm, x_var_num; d_tm, y_var_num] DECIMAL' in |
| 50 |
norm_interval int eq_th;; |
| 51 |
|
| 52 |
|
| 53 |
(* Unary interval operations *) |
| 54 |
let unary_interval_operations = |
| 55 |
let table = Hashtbl.create 10 in |
| 56 |
let add = Hashtbl.add in |
| 57 |
add table `--` (fun pp -> float_interval_neg); |
| 58 |
add table `abs` (fun pp -> float_interval_abs); |
| 59 |
add table `inv` float_interval_inv; |
| 60 |
add table `sqrt` float_interval_sqrt; |
| 61 |
add table `exp` float_interval_exp; |
| 62 |
add table `log` float_interval_log; |
| 63 |
add table `atn` float_interval_atn; |
| 64 |
add table `acs` float_interval_acs; |
| 65 |
add table `asn` float_interval_asn; |
| 66 |
add table `sin` float_interval_sin; |
| 67 |
add table `cos` float_interval_cos; |
| 68 |
add table `matan` float_interval_matan; |
| 69 |
add table `dmatan` float_interval_dmatan; |
| 70 |
add table `ddmatan` float_interval_ddmatan; |
| 71 |
table;; |
| 72 |
|
| 73 |
|
| 74 |
(* Binary interval operations *) |
| 75 |
let binary_interval_operations = |
| 76 |
let table = Hashtbl.create 10 in |
| 77 |
let add = Hashtbl.add in |
| 78 |
add table `+` float_interval_add; |
| 79 |
add table `-` float_interval_sub; |
| 80 |
add table `*` float_interval_mul; |
| 81 |
add table `/` float_interval_div; |
| 82 |
table;; |
| 83 |
|
| 84 |
|
| 85 |
(* Interval approximations of constants *) |
| 86 |
let interval_constants = |
| 87 |
let table = Hashtbl.create 10 in |
| 88 |
let add = Hashtbl.add in |
| 89 |
add table `pi` (fun pp -> pi_approx_array.(pp)); |
| 90 |
table;; |
| 91 |
|
| 92 |
|
| 93 |
|
| 94 |
(* Type of an interval function *) |
| 95 |
type interval_fun = |
| 96 |
| Int_ref of int |
| 97 |
| Int_var of term |
| 98 |
| Int_const of thm |
| 99 |
| Int_decimal_const of term |
| 100 |
| Int_named_const of term |
| 101 |
| Int_pow of int * interval_fun |
| 102 |
| Int_unary of term * interval_fun |
| 103 |
| Int_binary of term * interval_fun * interval_fun;; |
| 104 |
|
| 105 |
|
| 106 |
(* Evaluates the given interval function at the point |
| 107 |
defined by the given list of variables *) |
| 108 |
let eval_interval_fun pp ifun vars refs = |
| 109 |
let u_find = Hashtbl.find unary_interval_operations and |
| 110 |
b_find = Hashtbl.find binary_interval_operations and |
| 111 |
c_find = Hashtbl.find interval_constants in |
| 112 |
let rec rec_eval f = |
| 113 |
match f with |
| 114 |
| Int_ref i -> List.nth refs i |
| 115 |
| Int_var tm -> assoc tm vars |
| 116 |
| Int_const th -> th |
| 117 |
| Int_decimal_const tm -> mk_float_interval_decimal pp tm |
| 118 |
| Int_named_const tm -> c_find tm pp |
| 119 |
| Int_pow (n,f1) -> float_interval_pow pp n (rec_eval f1) |
| 120 |
| Int_unary (tm,f1) -> u_find tm pp (rec_eval f1) |
| 121 |
| Int_binary (tm,f1,f2) -> b_find tm pp (rec_eval f1) (rec_eval f2) in |
| 122 |
rec_eval ifun;; |
| 123 |
|
| 124 |
|
| 125 |
(* Evaluates all sub-expressions involving constants in the given interval function *) |
| 126 |
let eval_constants pp ifun = |
| 127 |
let u_find = Hashtbl.find unary_interval_operations and |
| 128 |
b_find = Hashtbl.find binary_interval_operations and |
| 129 |
c_find = Hashtbl.find interval_constants in |
| 130 |
let rec rec_eval f = |
| 131 |
match f with |
| 132 |
| Int_decimal_const tm -> Int_const (mk_float_interval_decimal pp tm) |
| 133 |
| Int_named_const tm -> Int_const (c_find tm pp) |
| 134 |
| Int_pow (n,f1) -> |
| 135 |
(let f1_val = rec_eval f1 in |
| 136 |
match f1_val with |
| 137 |
| Int_const th -> Int_const (float_interval_pow pp n th) |
| 138 |
| _ -> Int_pow (n,f1_val)) |
| 139 |
| Int_unary (tm,f1) -> |
| 140 |
(let f1_val = rec_eval f1 in |
| 141 |
match f1_val with |
| 142 |
| Int_const th -> Int_const (u_find tm pp th) |
| 143 |
| _ -> Int_unary (tm, f1_val)) |
| 144 |
| Int_binary (tm,f1,f2) -> |
| 145 |
(let f1_val, f2_val = rec_eval f1, rec_eval f2 in |
| 146 |
match f1_val with |
| 147 |
| Int_const th1 -> |
| 148 |
(match f2_val with |
| 149 |
| Int_const th2 -> Int_const (b_find tm pp th1 th2) |
| 150 |
| _ -> Int_binary (tm, f1_val, f2_val)) |
| 151 |
| _ -> Int_binary (tm, f1_val, f2_val)) |
| 152 |
| _ -> f in |
| 153 |
rec_eval ifun;; |
| 154 |
|
| 155 |
|
| 156 |
|
| 157 |
(**************************************) |
| 158 |
|
| 159 |
(* Builds an interval function from the given term *) |
| 160 |
let rec build_interval_fun expr_tm = |
| 161 |
if is_const expr_tm then |
| 162 |
(* Constant *) |
| 163 |
Int_named_const expr_tm |
| 164 |
else if is_var expr_tm then |
| 165 |
(* Variable *) |
| 166 |
Int_var expr_tm |
| 167 |
else |
| 168 |
let ltm, r_tm = dest_comb expr_tm in |
| 169 |
(* Unary operations *) |
| 170 |
if is_const ltm then |
| 171 |
(* & *) |
| 172 |
if ltm = amp_op_real then |
| 173 |
let n = dest_numeral r_tm in |
| 174 |
Int_const (mk_float_interval_num n) |
| 175 |
else |
| 176 |
let r_fun = build_interval_fun r_tm in |
| 177 |
Int_unary (ltm, r_fun) |
| 178 |
else |
| 179 |
(* Binary operations *) |
| 180 |
let op, l_tm = dest_comb ltm in |
| 181 |
let name = (fst o dest_const) op in |
| 182 |
if name = "DECIMAL" then |
| 183 |
(* DECIMAL *) |
| 184 |
Int_decimal_const expr_tm |
| 185 |
else if name = "real_pow" then |
| 186 |
(* pow *) |
| 187 |
let n = dest_small_numeral r_tm in |
| 188 |
Int_pow (n, build_interval_fun l_tm) |
| 189 |
else if name = "$" then |
| 190 |
(* $ *) |
| 191 |
Int_var expr_tm |
| 192 |
else |
| 193 |
let lhs = build_interval_fun l_tm and |
| 194 |
rhs = build_interval_fun r_tm in |
| 195 |
Int_binary (op, lhs, rhs);; |
| 196 |
|
| 197 |
|
| 198 |
(********************************) |
| 199 |
|
| 200 |
(* Replaces the given subexpression with the given reference index |
| 201 |
in all interval functions in the list. |
| 202 |
Returns the number of replaces and a new list of interval functions *) |
| 203 |
let replace_subexpr expr expr_index f_list = |
| 204 |
let rec replace f = |
| 205 |
if f = expr then |
| 206 |
1, Int_ref expr_index |
| 207 |
else |
| 208 |
match f with |
| 209 |
| Int_pow (k, f1) -> |
| 210 |
let c, f1' = replace f1 in |
| 211 |
c, Int_pow (k, f1') |
| 212 |
| Int_unary (tm, f1) -> |
| 213 |
let c, f1' = replace f1 in |
| 214 |
c, Int_unary (tm, f1') |
| 215 |
| Int_binary (tm, f1, f2) -> |
| 216 |
let c1, f1' = replace f1 in |
| 217 |
let c2, f2' = replace f2 in |
| 218 |
c1 + c2, Int_binary (tm, f1', f2') |
| 219 |
| _ -> 0, f in |
| 220 |
let cs, fs = unzip (map replace f_list) in |
| 221 |
itlist (+) cs 0, fs;; |
| 222 |
|
| 223 |
|
| 224 |
|
| 225 |
let is_leaf f = |
| 226 |
match f with |
| 227 |
| Int_pow _ -> false |
| 228 |
| Int_unary _ -> false |
| 229 |
| Int_binary _ -> false |
| 230 |
| _ -> true;; |
| 231 |
|
| 232 |
let find_and_replace_all f_list acc = |
| 233 |
let rec find_and_replace f i f_list = |
| 234 |
if is_leaf f then |
| 235 |
f, (0, f_list) |
| 236 |
else |
| 237 |
let expr, (c, fs) = |
| 238 |
match f with |
| 239 |
| Int_pow (k, f1) -> find_and_replace f1 i f_list |
| 240 |
| Int_unary (tm, f1) -> find_and_replace f1 i f_list |
| 241 |
| Int_binary (tm, f1, f2) -> |
| 242 |
let expr, (c1, fs) = find_and_replace f1 i f_list in |
| 243 |
if c1 > 1 then expr, (c1, fs) else find_and_replace f2 i f_list |
| 244 |
| _ -> f, (0, f_list) in |
| 245 |
if c > 1 then expr, (c, fs) else f, replace_subexpr f i f_list in |
| 246 |
|
| 247 |
let rec iterate fs acc = |
| 248 |
let i = length acc in |
| 249 |
let expr, (c, fs') = find_and_replace (hd fs) i fs in |
| 250 |
if c > 1 then iterate fs' (acc @ [expr]) else fs, acc in |
| 251 |
|
| 252 |
let rec iterate_all f_list ref_acc f_acc = |
| 253 |
match f_list with |
| 254 |
| [] -> f_acc, ref_acc |
| 255 |
| f :: fs -> |
| 256 |
let fs', acc' = iterate f_list ref_acc in |
| 257 |
iterate_all (tl fs') acc' (f_acc @ [hd fs']) in |
| 258 |
|
| 259 |
iterate_all f_list acc [];; |
| 260 |
|
| 261 |
|
| 262 |
let eval_interval_fun_list pp (f_list, refs) vars = |
| 263 |
let rec eval_refs refs acc = |
| 264 |
match refs with |
| 265 |
| [] -> acc |
| 266 |
| r :: rs -> |
| 267 |
let v = eval_interval_fun pp r vars acc in |
| 268 |
eval_refs rs (acc @ [v]) in |
| 269 |
let rs = eval_refs refs [] in |
| 270 |
map (fun f -> eval_interval_fun pp f vars rs) f_list;; |
| 271 |
|
| 272 |
|
| 273 |
(***************************************) |
| 274 |
|
| 275 |
(* Approximate the bounds of the given interval with floating point numbers *) |
| 276 |
let interval_to_float_interval = |
| 277 |
let th = (UNDISCH_ALL o prove)(`interval_arith x (lo, hi) ==> |
| 278 |
interval_arith lo (a, y) ==> |
| 279 |
interval_arith hi (z, b) |
| 280 |
==> interval_arith x (a, b)`, |
| 281 |
REWRITE_TAC[interval_arith] THEN REAL_ARITH_TAC) in |
| 282 |
fun pp int_th -> |
| 283 |
let x_tm, bounds = dest_interval_arith (concl int_th) in |
| 284 |
let lo, hi = dest_pair bounds in |
| 285 |
let f_lo = build_interval_fun lo and |
| 286 |
f_hi = build_interval_fun hi in |
| 287 |
let th_lo = eval_interval_fun pp f_lo [] [] and |
| 288 |
th_hi = eval_interval_fun pp f_hi [] [] in |
| 289 |
let a_tm, y_tm = (dest_pair o rand o concl) th_lo and |
| 290 |
z_tm, b_tm = (dest_pair o rand o concl) th_hi in |
| 291 |
let th1 = INST[x_tm, x_var_real; lo, lo_var_real; hi, hi_var_real; |
| 292 |
a_tm, a_var_real; y_tm, y_var_real; |
| 293 |
z_tm, z_var_real; b_tm, b_var_real] th in |
| 294 |
(MY_PROVE_HYP int_th o MY_PROVE_HYP th_lo o MY_PROVE_HYP th_hi) th1;; |
| 295 |
|
| 296 |
|
| 297 |
(* Adds a new constant approximation to the table of constants *) |
| 298 |
let add_constant_interval int_th = |
| 299 |
let c_tm, _ = dest_interval_arith (concl int_th) in |
| 300 |
let _ = assert_msg (is_const c_tm, "add_constant_interval: not a constant") in |
| 301 |
let th = interval_to_float_interval 20 int_th in |
| 302 |
let approx_array = Array.init 20 (fun i -> float_interval_round i th) in |
| 303 |
Hashtbl.add interval_constants c_tm (fun pp -> approx_array.(pp));; |
| 304 |
|
| 305 |
end;; |