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