| 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 |
(* Informal interval evaluation of arithmetic expressions *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
needs "Formal_ineqs/informal/informal_exp.hl";; |
| 14 |
needs "Formal_ineqs/informal/informal_log.hl";; |
| 15 |
needs "Formal_ineqs/informal/informal_atn.hl";; |
| 16 |
needs "Formal_ineqs/informal/informal_asn_acs.hl";; |
| 17 |
needs "Formal_ineqs/informal/informal_sin_cos.hl";; |
| 18 |
needs "Formal_ineqs/informal/informal_matan.hl";; |
| 19 |
|
| 20 |
|
| 21 |
module Informal_eval_interval = struct |
| 22 |
|
| 23 |
open Informal_interval;; |
| 24 |
open Informal_float;; |
| 25 |
open Informal_log;; |
| 26 |
open Informal_exp;; |
| 27 |
open Informal_atn;; |
| 28 |
open Informal_asn_acs;; |
| 29 |
open Informal_sin_cos;; |
| 30 |
open Informal_matan;; |
| 31 |
|
| 32 |
(* Creates an interval approximation of the given decimal term *) |
| 33 |
let mk_float_interval_decimal pp decimal_tm = |
| 34 |
let n_tm, d_tm = dest_binary "DECIMAL" decimal_tm in |
| 35 |
let n, d = dest_numeral n_tm, dest_numeral d_tm in |
| 36 |
let n_int, d_int = mk_num_interval n, mk_num_interval d in |
| 37 |
div_interval pp n_int d_int;; |
| 38 |
|
| 39 |
|
| 40 |
(* Unary interval operations *) |
| 41 |
let unary_interval_operations = |
| 42 |
let table = Hashtbl.create 10 in |
| 43 |
let add = Hashtbl.add in |
| 44 |
add table "real_neg" (fun pp -> neg_interval); |
| 45 |
add table "real_abs" (fun pp -> abs_interval); |
| 46 |
add table "real_inv" inv_interval; |
| 47 |
add table "sqrt" sqrt_interval; |
| 48 |
add table "exp" exp_interval; |
| 49 |
add table "log" log_interval; |
| 50 |
add table "cos" cos_interval; |
| 51 |
add table "sin" sin_interval; |
| 52 |
add table "atn" atn_interval; |
| 53 |
add table "acs" acs_interval; |
| 54 |
add table "asn" asn_interval; |
| 55 |
add table "matan" matan_interval; |
| 56 |
add table "dmatan" dmatan_interval; |
| 57 |
add table "ddmatan" ddmatan_interval; |
| 58 |
table;; |
| 59 |
|
| 60 |
|
| 61 |
(* Binary interval operations *) |
| 62 |
let binary_interval_operations = |
| 63 |
let table = Hashtbl.create 10 in |
| 64 |
let add = Hashtbl.add in |
| 65 |
add table "real_add" add_interval; |
| 66 |
add table "real_sub" sub_interval; |
| 67 |
add table "real_mul" mul_interval; |
| 68 |
add table "real_div" div_interval; |
| 69 |
table;; |
| 70 |
|
| 71 |
|
| 72 |
(* Interval approximations of constants *) |
| 73 |
let interval_constants = |
| 74 |
let table = Hashtbl.create 10 in |
| 75 |
let add = Hashtbl.add in |
| 76 |
add table "pi" (fun pp -> pi_approx_array.(pp)); |
| 77 |
table;; |
| 78 |
|
| 79 |
|
| 80 |
|
| 81 |
(* Type of an interval function *) |
| 82 |
type interval_fun = |
| 83 |
| Int_ref of int |
| 84 |
| Int_var of int |
| 85 |
| Int_const of interval |
| 86 |
| Int_decimal_const of term |
| 87 |
| Int_named_const of string |
| 88 |
| Int_pow of int * interval_fun |
| 89 |
| Int_unary of string * interval_fun |
| 90 |
| Int_binary of string * interval_fun * interval_fun;; |
| 91 |
|
| 92 |
|
| 93 |
(* Equality of interval functions *) |
| 94 |
let rec eq_ifun ifun1 ifun2 = |
| 95 |
match (ifun1, ifun2) with |
| 96 |
| (Int_ref r1, Int_ref r2) -> r1 = r2 |
| 97 |
| (Int_var v1, Int_var v2) -> v1 = v2 |
| 98 |
| (Int_decimal_const tm1, Int_decimal_const tm2) -> tm1 = tm2 |
| 99 |
| (Int_named_const name1, Int_named_const name2) -> name1 = name2 |
| 100 |
| (Int_pow (n1, f1), Int_pow (n2, f2)) -> n1 = n2 && eq_ifun f1 f2 |
| 101 |
| (Int_unary (op1, f1), Int_unary (op2, f2)) -> op1 = op2 && eq_ifun f1 f2 |
| 102 |
| (Int_binary (op1, f1, g1), Int_binary (op2, f2, g2)) -> op1 = op2 && eq_ifun f1 f2 && eq_ifun g1 g2 |
| 103 |
| (Int_const int1, Int_const int2) -> |
| 104 |
let lo1, hi1 = dest_interval int1 and |
| 105 |
lo2, hi2 = dest_interval int2 in |
| 106 |
eq_float lo1 lo2 && eq_float hi1 hi2 |
| 107 |
| _ -> false;; |
| 108 |
|
| 109 |
|
| 110 |
(* Evaluates the given interval function at the point |
| 111 |
defined by the given list of variables *) |
| 112 |
let eval_interval_fun = |
| 113 |
let u_find = Hashtbl.find unary_interval_operations and |
| 114 |
b_find = Hashtbl.find binary_interval_operations and |
| 115 |
c_find = Hashtbl.find interval_constants in |
| 116 |
fun pp ifun vars refs -> |
| 117 |
let rec rec_eval f = |
| 118 |
match f with |
| 119 |
| Int_ref i -> List.nth refs i |
| 120 |
| Int_var i -> List.nth vars (i - 1) |
| 121 |
| Int_const int -> int |
| 122 |
| Int_decimal_const tm -> mk_float_interval_decimal pp tm |
| 123 |
| Int_named_const name -> (c_find name) pp |
| 124 |
| Int_pow (n,f1) -> pow_interval pp n (rec_eval f1) |
| 125 |
| Int_unary (op,f1) -> (u_find op) pp (rec_eval f1) |
| 126 |
| Int_binary (op,f1,f2) -> (b_find op) pp (rec_eval f1) (rec_eval f2) in |
| 127 |
rec_eval ifun;; |
| 128 |
|
| 129 |
|
| 130 |
(* Evaluates all sub-expressions involving constants in the given interval function *) |
| 131 |
let eval_constants = |
| 132 |
let u_find = Hashtbl.find unary_interval_operations and |
| 133 |
b_find = Hashtbl.find binary_interval_operations and |
| 134 |
c_find = Hashtbl.find interval_constants in |
| 135 |
fun pp ifun -> |
| 136 |
let rec rec_eval f = |
| 137 |
match f with |
| 138 |
| Int_decimal_const tm -> Int_const (mk_float_interval_decimal pp tm) |
| 139 |
| Int_named_const name -> Int_const (c_find name pp) |
| 140 |
| Int_pow (n, f1) -> |
| 141 |
(let f1_val = rec_eval f1 in |
| 142 |
match f1_val with |
| 143 |
| Int_const int -> Int_const (pow_interval pp n int) |
| 144 |
| _ -> Int_pow (n,f1_val)) |
| 145 |
| Int_unary (op, f1) -> |
| 146 |
(let f1_val = rec_eval f1 in |
| 147 |
match f1_val with |
| 148 |
| Int_const int -> Int_const (u_find op pp int) |
| 149 |
| _ -> Int_unary (op, f1_val)) |
| 150 |
| Int_binary (op, f1, f2) -> |
| 151 |
(let f1_val, f2_val = rec_eval f1, rec_eval f2 in |
| 152 |
match f1_val with |
| 153 |
| Int_const int1 -> |
| 154 |
(match f2_val with |
| 155 |
| Int_const int2 -> Int_const (b_find op pp int1 int2) |
| 156 |
| _ -> Int_binary (op, f1_val, f2_val)) |
| 157 |
| _ -> Int_binary (op, f1_val, f2_val)) |
| 158 |
| _ -> f in |
| 159 |
rec_eval ifun;; |
| 160 |
|
| 161 |
|
| 162 |
|
| 163 |
(**************************************) |
| 164 |
|
| 165 |
(* Builds an interval function from the given term expression *) |
| 166 |
let build_interval_fun = |
| 167 |
let amp_op_real = `(&):num -> real` in |
| 168 |
let rec rec_build expr_tm = |
| 169 |
if is_const expr_tm then |
| 170 |
(* Constant *) |
| 171 |
Int_named_const (fst (dest_const expr_tm)) |
| 172 |
else if is_var expr_tm then |
| 173 |
(* Variables should be of the form name$i *) |
| 174 |
failwith ("Variables should be of the form name$i: " ^ string_of_term expr_tm) |
| 175 |
else |
| 176 |
let ltm, r_tm = dest_comb expr_tm in |
| 177 |
(* Unary operations *) |
| 178 |
if is_const ltm then |
| 179 |
(* & *) |
| 180 |
if ltm = amp_op_real then |
| 181 |
let n = dest_numeral r_tm in |
| 182 |
Int_const (mk_num_interval n) |
| 183 |
else |
| 184 |
let r_fun = rec_build r_tm in |
| 185 |
Int_unary ((fst o dest_const) ltm, r_fun) |
| 186 |
else |
| 187 |
(* Binary operations *) |
| 188 |
let op, l_tm = dest_comb ltm in |
| 189 |
let name = (fst o dest_const) op in |
| 190 |
if name = "DECIMAL" then |
| 191 |
(* DECIMAL *) |
| 192 |
Int_decimal_const expr_tm |
| 193 |
else if name = "real_pow" then |
| 194 |
(* pow *) |
| 195 |
let n = dest_small_numeral r_tm in |
| 196 |
Int_pow (n, rec_build l_tm) |
| 197 |
else if name = "$" then |
| 198 |
(* $ *) |
| 199 |
Int_var (dest_small_numeral (rand expr_tm)) |
| 200 |
else |
| 201 |
let lhs = rec_build l_tm and |
| 202 |
rhs = rec_build r_tm in |
| 203 |
Int_binary ((fst o dest_const) op, lhs, rhs) in |
| 204 |
rec_build;; |
| 205 |
|
| 206 |
|
| 207 |
(* Replaces the given subexpression with the given reference index |
| 208 |
for all interval functions in the list. |
| 209 |
Returns the number of replaces and a new list of interval functions *) |
| 210 |
let replace_subexpr expr expr_index f_list = |
| 211 |
let rec replace f = |
| 212 |
if eq_ifun f expr then |
| 213 |
1, Int_ref expr_index |
| 214 |
else |
| 215 |
match f with |
| 216 |
| Int_pow (k, f1) -> |
| 217 |
let c, f1' = replace f1 in |
| 218 |
c, Int_pow (k, f1') |
| 219 |
| Int_unary (op, f1) -> |
| 220 |
let c, f1' = replace f1 in |
| 221 |
c, Int_unary (op, f1') |
| 222 |
| Int_binary (op, f1, f2) -> |
| 223 |
let c1, f1' = replace f1 in |
| 224 |
let c2, f2' = replace f2 in |
| 225 |
c1 + c2, Int_binary (op, f1', f2') |
| 226 |
| _ -> 0, f in |
| 227 |
let cs, fs = unzip (map replace f_list) in |
| 228 |
itlist (+) cs 0, fs;; |
| 229 |
|
| 230 |
|
| 231 |
|
| 232 |
let is_leaf f = |
| 233 |
match f with |
| 234 |
| Int_pow _ -> false |
| 235 |
| Int_unary _ -> false |
| 236 |
| Int_binary _ -> false |
| 237 |
| _ -> true;; |
| 238 |
|
| 239 |
let find_and_replace_all f_list acc = |
| 240 |
let rec find_and_replace f i f_list = |
| 241 |
if is_leaf f then |
| 242 |
f, (0, f_list) |
| 243 |
else |
| 244 |
let expr, (c, fs) = |
| 245 |
match f with |
| 246 |
| Int_pow (k, f1) -> find_and_replace f1 i f_list |
| 247 |
| Int_unary (op, f1) -> find_and_replace f1 i f_list |
| 248 |
| Int_binary (op, f1, f2) -> |
| 249 |
let expr, (c1, fs) = find_and_replace f1 i f_list in |
| 250 |
if c1 > 1 then expr, (c1, fs) else find_and_replace f2 i f_list |
| 251 |
| _ -> f, (0, f_list) in |
| 252 |
if c > 1 then expr, (c, fs) else f, replace_subexpr f i f_list in |
| 253 |
|
| 254 |
let rec iterate fs acc = |
| 255 |
let i = length acc in |
| 256 |
let expr, (c, fs') = find_and_replace (hd fs) i fs in |
| 257 |
if c > 1 then iterate fs' (acc @ [expr]) else fs, acc in |
| 258 |
|
| 259 |
let rec iterate_all f_list ref_acc f_acc = |
| 260 |
match f_list with |
| 261 |
| [] -> f_acc, ref_acc |
| 262 |
| f :: fs -> |
| 263 |
let fs', acc' = iterate f_list ref_acc in |
| 264 |
iterate_all (tl fs') acc' (f_acc @ [hd fs']) in |
| 265 |
|
| 266 |
iterate_all f_list acc [];; |
| 267 |
|
| 268 |
|
| 269 |
let eval_interval_fun_list pp (f_list, refs) vars = |
| 270 |
let rec eval_refs refs acc = |
| 271 |
match refs with |
| 272 |
| [] -> acc |
| 273 |
| r :: rs -> |
| 274 |
let v = eval_interval_fun pp r vars acc in |
| 275 |
eval_refs rs (acc @ [v]) in |
| 276 |
let rs = eval_refs refs [] in |
| 277 |
map (fun f -> eval_interval_fun pp f vars rs) f_list;; |
| 278 |
|
| 279 |
|
| 280 |
(* Approximate the bounds of the given interval with floating point numbers *) |
| 281 |
let interval_to_float_interval pp int_th = |
| 282 |
let lo_tm, hi_tm = (dest_pair o rand o concl) int_th in |
| 283 |
let f_lo = build_interval_fun lo_tm and |
| 284 |
f_hi = build_interval_fun hi_tm in |
| 285 |
let int_lo = eval_interval_fun pp f_lo [] [] and |
| 286 |
int_hi = eval_interval_fun pp f_hi [] [] in |
| 287 |
let a, _ = dest_interval int_lo and |
| 288 |
_, b = dest_interval int_hi in |
| 289 |
mk_interval (a, b);; |
| 290 |
|
| 291 |
|
| 292 |
(* Adds a new constant approximation to the table of constants *) |
| 293 |
let add_constant_interval int_th = |
| 294 |
let c_tm = (rand o rator o concl) int_th in |
| 295 |
let _ = is_const c_tm || failwith "add_constant_interval: not a constant" in |
| 296 |
let interval = interval_to_float_interval 20 int_th in |
| 297 |
let approx_array = Array.init 20 (fun i -> round_interval (if i = 0 then 1 else i) interval) in |
| 298 |
Hashtbl.add interval_constants (fst (dest_const c_tm)) (fun pp -> approx_array.(pp));; |
| 299 |
|
| 300 |
|
| 301 |
end;; |