Debian Codegraph @

Formal_ineqs/informal/informal_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 (* 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;;