Debian Codegraph @

Formal_ineqs/arith/eval_interval.hl

raw
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;;