Debian Codegraph @

Formal_ineqs/informal/informal_verifier.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 verification procedures *)
11 (* -------------------------------------------------------------------------- *)
12
13 (* Dependencies *)
14 needs "Formal_ineqs/informal/informal_taylor.hl";;
15 needs "Formal_ineqs/verifier/certificate.hl";;
16 needs "Formal_ineqs/verifier_options.hl";;
17
18 module Informal_verifier = struct
19
20 open Informal_float;;
21 open Informal_interval;;
22 open Informal_taylor;;
23 open Certificate;;
24 open Verifier_options;;
25
26
27 type verification_funs =
28 {
29 (* p_lin -> p_second -> dom -> ti *)
30 taylor : int -> int -> m_cell_domain -> m_taylor_interval;
31 (* pp -> xx -> zz -> interval *)
32 f : int -> ifloat list -> ifloat list -> interval;
33 (* j -> pp -> xx -> zz -> interval *)
34 df : int -> int -> ifloat list -> ifloat list -> interval;
35 (* i j -> pp -> xx -> zz -> interval *)
36 ddf : int -> int -> int -> ifloat list -> ifloat list -> interval;
37 };;
38
39
40 (* m_subset_interval *)
41 let m_subset_interval a b c d =
42 let prove_le l1 l2 = itlist2 (fun x y r -> le_float x y && r) l1 l2 true in
43 prove_le a c && prove_le d b;;
44
45 (* m_taylor_cell_pass *)
46 let m_taylor_cell_pass pp ti =
47 let upper = eval_m_taylor_upper_bound pp ti in
48 lt0_float upper;;
49
50 (* m_taylor_cell_pass0 *)
51 let m_taylor_cell_pass0 int =
52 (lt0_float o snd o dest_interval) int;;
53
54 (* m_cell_pass_subdomain *)
55 let m_cell_pass_subdomain domain2 pass_domain =
56 let a, b = pass_domain.lo, pass_domain. hi in
57 let c, d = domain2.lo, domain2.hi in
58 m_subset_interval a b c d;;
59
60 (* m_incr_pass *)
61 let m_incr_pass pp j ti =
62 let partial_bound = eval_m_taylor_partial_lower pp j ti in
63 ge0_float partial_bound;;
64
65 (* m_decr_pass *)
66 let m_decr_pass pp j ti =
67 let partial_bound = eval_m_taylor_partial_upper pp j ti in
68 le0_float partial_bound;;
69
70 (* m_mono_pass_gen *)
71 let m_mono_pass_gen decr_flag bound =
72 (if decr_flag then le0_float else ge0_float) bound;;
73
74 (* m_convex_pass *)
75 let m_convex_pass int =
76 (ge0_float o fst o dest_interval) int;;
77
78
79 (* mk_verification_functions *)
80 let mk_verification_functions_poly pp0 f partials partials2 =
81 let n = length partials in
82 let taylor = eval_m_taylor pp0 f partials partials2 in
83 let eval0 = mk_eval_function pp0 f in
84 let eval1 = map (fun i -> mk_eval_function pp0 ((rand o concl o List.nth partials) (i - 1))) (1--n) in
85 let eval2 = map (fun i ->
86 map (fun j ->
87 let d2 = List.nth (List.nth partials2 (i - 1)) (j - 1) in
88 mk_eval_function pp0 ((rand o concl) d2)) (1--i)) (1--n) in
89 {
90 taylor = taylor;
91 f = eval0;
92 df = (fun i -> List.nth eval1 (i - 1));
93 ddf = (fun i j -> List.nth (List.nth eval2 (j - 1)) (i - 1));
94 };;
95
96
97 (* split_domain *)
98 let split_domain pp j domain =
99 let n = length domain.w in
100 let t = List.nth domain.y (j - 1) in
101 let vv = map (fun i -> if i = j then t else List.nth domain.hi (i - 1)) (1--n) in
102 let uu = map (fun i -> if i = j then t else List.nth domain.lo (i - 1)) (1--n) in
103 mk_m_center_domain pp domain.lo vv, mk_m_center_domain pp uu domain.hi;;
104
105
106 (* restrict_domain *)
107 let restrict_domain j left_flag domain =
108 let replace list j v = map (fun i -> if i = j then v else List.nth list (i - 1)) (1--length list) in
109 let t = List.nth (if left_flag then domain.lo else domain.hi) (j - 1) in
110 let lo = if left_flag then domain.lo else replace domain.lo j t in
111 let hi = if left_flag then replace domain.hi j t else domain.hi in
112 let w = replace domain.w j float_0 in
113 let y = replace domain.y j t in
114 {lo = lo; hi = hi; w = w; y = y};;
115
116
117 (*****************************)
118 (* aux list functions *)
119
120 (* Merges lists of indices. Input lists must be sorted *)
121 let merge_indices l1 l2 = uniq (merge (<) l1 l2);;
122
123 (* Returns all elements at the given indices *)
124 let take_all l inds = map (List.nth l) inds;;
125
126
127 (*****************************)
128 (* m_verify_raw *)
129
130 (* Constructs a p_result_tree from the given result_tree *)
131 let m_verify_raw (report_start, total_size) p_split p_min p_max fs_list certificate domain0 ref_list =
132 let r_size = result_size certificate in
133 let r_size2 = float_of_int (if total_size > 0 then total_size else (if r_size > 0 then r_size else 1)) in
134 let k = ref 0 in
135 let kk = ref report_start in
136 let last_report = ref (int_of_float (float_of_int !kk /. r_size2 *. 100.0)) in
137 let ps = p_min -- p_max in
138
139 (* finds an optimal precision value *)
140 let rec find_p p_fun p_list =
141 match p_list with
142 | [] -> failwith "find_p: no good p found"
143 | p :: ps ->
144 let _ = if !info_print_level >= 2 then
145 report (sprintf "Testing p = %d (other: %d)" p (length ps))
146 else () in
147 let flag =
148 (try p_fun p
149 with
150 | Failure msg ->
151 let _ = if !info_print_level >= 2 then
152 report (sprintf "Failure at p = %d: %s" p msg)
153 else () in
154 false
155 | Division_by_zero ->
156 let _ = if !info_print_level >= 2 then
157 report (sprintf "Failure at p = %d: Division_by_zero" p)
158 else () in
159 false) in
160 if flag then
161 let _ = if !info_print_level >= 2 then report (sprintf "p = %d" p) else () in p
162 else find_p p_fun ps in
163
164 (* pass_test *)
165 let pass_test domain (j,f0_flag) pp =
166 let fs = List.nth fs_list j in
167 if f0_flag then
168 m_taylor_cell_pass0 (fs.f pp domain.lo domain.hi)
169 else
170 m_taylor_cell_pass pp (fs.taylor pp pp domain) in
171
172 (* glue_test *)
173 let glue_test domain i convex_flag inds pp =
174 let fss = take_all fs_list inds in
175 if convex_flag then
176 forall (fun fs -> m_convex_pass (fs.ddf (i + 1) (i + 1) pp domain.lo domain.hi)) fss
177 else
178 true in
179
180 (* mono_test *)
181 let mono_test mono domain domains inds pp =
182 let fss = take_all fs_list inds in
183 let xx, zz = domain.lo, domain.hi in
184 let taylors = map (fun fs -> fs.taylor pp pp domain) fss in
185 let gen_mono m =
186 if m.df0_flag then
187 if m.decr_flag then
188 map (fun fs -> (snd o dest_interval) (fs.df m.variable pp xx zz)) fss
189 else
190 map (fun fs -> (fst o dest_interval) (fs.df m.variable pp xx zz)) fss
191 else
192 if m.decr_flag then
193 map (eval_m_taylor_partial_upper pp m.variable) taylors
194 else
195 map (eval_m_taylor_partial_lower pp m.variable) taylors in
196 let monos = map gen_mono mono in
197 rev_itlist (fun (m, bounds) pass ->
198 let flag = m.decr_flag in
199 forall (m_mono_pass_gen flag) bounds && pass) (rev (zip mono monos)) true in
200
201 (* mk_domains *)
202 let rec mk_domains mono dom0 acc =
203 match mono with
204 | [] -> rev acc
205 | m :: ms ->
206 let j, flag = m.variable, m.decr_flag in
207 let dom = restrict_domain j flag dom0 in
208 mk_domains ms dom (dom :: acc) in
209
210 (* rec_verify *)
211 let rec rec_verify domain certificate =
212 match certificate with
213 | Result_mono (mono, r1) ->
214 let _ =
215 if !info_print_level >= 2 then
216 let mono_strs =
217 map (fun m -> sprintf "%s%d (%b)" (if m.decr_flag then "-" else "")
218 m.variable m.df0_flag) mono in
219 report (sprintf "Mono: [%s]" (String.concat ";" mono_strs))
220 else () in
221 let domains = mk_domains mono domain [] in
222 let tree1, inds = rec_verify (last domains) r1 in
223 (try
224 let pp = find_p (mono_test mono domain domains inds) ps in
225 P_result_mono ({pp = pp}, mono, tree1), inds
226 with Failure _ -> failwith "mono: failed")
227
228 | Result_pass (j, f0_flag) ->
229 let _ = k := !k + 1; kk := !kk + 1 in
230 let _ =
231 if !info_print_level >= 2 then
232 report (sprintf "Verifying: %d/%d (f0_flag = %b)" !k r_size f0_flag)
233 else () in
234 let _ = !info_print_level <> 1 ||
235 (let r = int_of_float (float_of_int !kk /. r_size2 *. 100.0) in
236 let _ = if r <> !last_report then (last_report := r; report0 (sprintf "%d " r)) else () in true) in
237
238 (try
239 let pp = find_p (pass_test domain (j, f0_flag)) ps in
240 P_result_pass ({pp = pp}, j, f0_flag), [j]
241 with Failure msg -> failwith ("pass: failed: " ^ msg))
242
243 | Result_glue (i, convex_flag, r1, r2) ->
244 let domain1, domain2 =
245 if convex_flag then
246 let d1 = restrict_domain (i + 1) true domain in
247 let d2 = restrict_domain (i + 1) false domain in
248 d1, d2
249 else
250 split_domain p_split (i + 1) domain in
251 let tree1, inds1 = rec_verify domain1 r1 in
252 let tree2, inds2 = rec_verify domain2 r2 in
253 let inds = merge_indices inds1 inds2 in
254 (try
255 let pp = find_p (glue_test domain i convex_flag inds) ps in
256 P_result_glue ({pp = pp}, i, convex_flag, tree1, tree2), inds
257 with Failure _ -> failwith "glue: failed")
258
259 | Result_pass_ref i ->
260 let _ = if !info_print_level >= 2 then report (sprintf "Ref: %d" i) else () in
261 let pass_flag, inds =
262 if i > 0 then
263 let _, inds = List.nth ref_list (i - 1) in
264 true, inds
265 else
266 let pass_domain, inds = List.nth ref_list (-i - 1) in
267 m_cell_pass_subdomain domain pass_domain, inds in
268 if not pass_flag then
269 failwith "ref: failed"
270 else
271 P_result_ref i, inds
272
273 | _ -> failwith "False result" in
274
275 rec_verify domain0 certificate;;
276
277
278
279 (*****************)
280
281 (* m_verify_raw0 *)
282 let m_verify_raw0 p_split p_min p_max fs_list certificate xx zz =
283 m_verify_raw (0, 0) p_split p_min p_max fs_list certificate (mk_m_center_domain p_split xx zz) [];;
284
285
286 (* m_verify_list *)
287 let m_verify_list p_split p_min p_max fs_list certificate_list xx zz =
288 let domain_hash = Hashtbl.create (length certificate_list * 10) in
289 let mem, find, add = Hashtbl.mem domain_hash,
290 Hashtbl.find domain_hash, Hashtbl.add domain_hash in
291
292 let get_m_cell_domain pp domain0 path =
293 let rec get_rec domain path hash =
294 match path with
295 | [] -> domain
296 | (s, j) :: ps ->
297 let hash' = hash^s^(string_of_int j) in
298 if mem hash' then
299 get_rec (find hash') ps hash'
300 else
301 if s = "l" || s = "r" then
302 let domain1, domain2 = split_domain pp j domain in
303 let hash1 = hash^"l"^(string_of_int j) and
304 hash2 = hash^"r"^(string_of_int j) in
305 let _ = add hash1 domain1; add hash2 domain2 in
306 if s = "l" then
307 get_rec domain1 ps hash'
308 else
309 get_rec domain2 ps hash'
310 else
311 let l_flag = (s = "ml") in
312 let domain' = restrict_domain j l_flag domain in
313 let _ = add hash' domain' in
314 get_rec domain' ps hash' in
315 get_rec domain0 path "" in
316
317 let domain0 = mk_m_center_domain p_split xx zz in
318 let size = length certificate_list in
319 let k = ref 0 in
320 let kk = ref 0 in
321 let total_size = end_itlist (+) (map (result_size o snd) certificate_list) in
322
323 let rec rec_verify certificate_list dom_list tree_list =
324 match certificate_list with
325 | [] -> rev tree_list
326 | (path, certificate) :: cs ->
327 let _ = k := !k + 1 in
328 let _ = !info_print_level < 2 || (report (sprintf "List: %d/%d" !k size); true) in
329 let domain = get_m_cell_domain p_split domain0 path in
330 let tree, inds = m_verify_raw (!kk, total_size) p_split p_min p_max fs_list certificate domain dom_list in
331 let _ = kk := !kk + result_size certificate in
332 rec_verify cs (dom_list @ [domain, inds]) ((path, tree) :: tree_list) in
333 rec_verify certificate_list [] [];;
334
335 end;;
336
337
338