| 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 verification certificate *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
needs "Formal_ineqs/misc/report.hl";; |
| 14 |
|
| 15 |
module Certificate = struct |
| 16 |
|
| 17 |
open Report;; |
| 18 |
|
| 19 |
(* ------------------------------ *) |
| 20 |
(* Main data types *) |
| 21 |
(* ------------------------------ *) |
| 22 |
|
| 23 |
type mono_status = { |
| 24 |
variable : int; |
| 25 |
decr_flag : bool; |
| 26 |
df0_flag : bool; |
| 27 |
ti_flag : bool; |
| 28 |
};; |
| 29 |
|
| 30 |
type result_tree = |
| 31 |
| Result_false of (float list * float list) |
| 32 |
(* function number, raw flag *) |
| 33 |
| Result_pass of (int * bool) |
| 34 |
| Result_pass_mono of mono_status |
| 35 |
| Result_pass_ref of int |
| 36 |
| Result_mono of mono_status list * result_tree |
| 37 |
(* variable, convex_flag, r1, r2 *) |
| 38 |
| Result_glue of (int * bool * result_tree * result_tree);; |
| 39 |
|
| 40 |
type p_status = { |
| 41 |
pp : int; |
| 42 |
};; |
| 43 |
|
| 44 |
type p_result_tree = |
| 45 |
| P_result_pass of p_status * int * bool |
| 46 |
| P_result_mono of p_status * mono_status list * p_result_tree |
| 47 |
| P_result_glue of p_status * int * bool * p_result_tree * p_result_tree |
| 48 |
| P_result_ref of int;; |
| 49 |
|
| 50 |
|
| 51 |
(* ------------------------------ *) |
| 52 |
(* Statistics *) |
| 53 |
(* ------------------------------ *) |
| 54 |
|
| 55 |
let rec result_size r = |
| 56 |
match r with |
| 57 |
| Result_false _ -> failwith "False result detected" |
| 58 |
| Result_mono (_,r1) -> result_size r1 |
| 59 |
| Result_glue (_, _, r1, r2) -> result_size r1 + result_size r2 |
| 60 |
| Result_pass_mono _ -> 1 |
| 61 |
| Result_pass _ -> 1 |
| 62 |
| _ -> 0;; |
| 63 |
|
| 64 |
let rec p_result_size r = |
| 65 |
match r with |
| 66 |
| P_result_pass _ -> 1 |
| 67 |
| P_result_mono (_, _, r1) -> p_result_size r1 |
| 68 |
| P_result_glue (_, _, _, r1, r2) -> p_result_size r1 + p_result_size r2 |
| 69 |
| _ -> 0;; |
| 70 |
|
| 71 |
|
| 72 |
type certificate_stats = { |
| 73 |
pass : int; |
| 74 |
pass_raw : int; |
| 75 |
pass_mono : int; |
| 76 |
mono : int; |
| 77 |
glue : int; |
| 78 |
glue_convex : int; |
| 79 |
};; |
| 80 |
|
| 81 |
let dummy_stats = { |
| 82 |
pass = 0; |
| 83 |
pass_raw = 0; |
| 84 |
pass_mono = 0; |
| 85 |
mono = 0; |
| 86 |
glue = 0; |
| 87 |
glue_convex = 0; |
| 88 |
};; |
| 89 |
|
| 90 |
|
| 91 |
(* Computes result statistics *) |
| 92 |
let result_stats result = |
| 93 |
let pass = ref 0 and |
| 94 |
mono = ref 0 and |
| 95 |
glue = ref 0 and |
| 96 |
pass_mono = ref 0 and |
| 97 |
pass_raw = ref 0 and |
| 98 |
glue_convex = ref 0 in |
| 99 |
|
| 100 |
let rec count r = |
| 101 |
match r with |
| 102 |
| Result_false _ -> failwith "False result" |
| 103 |
| Result_pass (_, flag) -> |
| 104 |
pass := !pass + 1; |
| 105 |
if flag then pass_raw := !pass_raw + 1 else () |
| 106 |
| Result_pass_mono _ -> pass_mono := !pass_mono + 1 |
| 107 |
| Result_pass_ref _ -> () |
| 108 |
| Result_mono (_, r1) -> mono := !mono + 1; count r1 |
| 109 |
| Result_glue (_, flag, r1, r2) -> |
| 110 |
glue := !glue + 1; |
| 111 |
if flag then glue_convex := !glue_convex + 1 else (); |
| 112 |
count r1; count r2 in |
| 113 |
|
| 114 |
let _ = count result in |
| 115 |
{pass = !pass; pass_raw = !pass_raw; pass_mono = !pass_mono; |
| 116 |
mono = !mono; glue = !glue; glue_convex = !glue_convex};; |
| 117 |
|
| 118 |
|
| 119 |
let report_stats stats = |
| 120 |
let s = sprintf "pass = %d (pass_raw = %d)\nmono = %d\nglue = %d (glue_convex = %d)\npass_mono = %d" |
| 121 |
stats.pass stats.pass_raw stats.mono stats.glue stats.glue_convex stats.pass_mono in |
| 122 |
report s;; |
| 123 |
|
| 124 |
|
| 125 |
let result_p_stats glue_flag p_result = |
| 126 |
let p_table = Hashtbl.create 10 in |
| 127 |
let add1 p = |
| 128 |
let c = if Hashtbl.mem p_table p then Hashtbl.find p_table p else 0 in |
| 129 |
Hashtbl.replace p_table p (succ c) in |
| 130 |
|
| 131 |
let rec count r = |
| 132 |
match r with |
| 133 |
| P_result_ref _ -> () |
| 134 |
| P_result_pass (pp, _, _) -> add1 pp.pp |
| 135 |
| P_result_mono (pp, _, r1) -> add1 pp.pp; count r1 |
| 136 |
| P_result_glue (pp, _, _, r1, r2) -> |
| 137 |
if glue_flag then add1 pp.pp else (); |
| 138 |
count r1; count r2 in |
| 139 |
|
| 140 |
let _ = count p_result in |
| 141 |
let s = Hashtbl.fold |
| 142 |
(fun p c s -> (sprintf "p = %d: %d\n" p c) ^ s) p_table "" in |
| 143 |
report s;; |
| 144 |
|
| 145 |
|
| 146 |
(* ------------------------------ *) |
| 147 |
(* Certificate transformations *) |
| 148 |
(* ------------------------------ *) |
| 149 |
|
| 150 |
let domain_str x z = |
| 151 |
let s1 = map string_of_float x and |
| 152 |
s2 = map string_of_float z in |
| 153 |
sprintf "[%s], [%s]" (String.concat "; " s1) (String.concat "; " s2);; |
| 154 |
|
| 155 |
let path_str p = |
| 156 |
String.concat "," (map (fun s, j -> sprintf "%s(%d)" s j) p);; |
| 157 |
|
| 158 |
|
| 159 |
(* get_results0 *) |
| 160 |
(* This function finds all subtrees of the given solution tree which can be |
| 161 |
veified immediately (no Result_pass_mono). These subtrees are added to |
| 162 |
the accumulator. Paths to the roots of all subtrees are also saved in |
| 163 |
the accumulator. The third returned value is a solution tree where all |
| 164 |
found subtrees are replaced with Result_pass_ref j, with j = #of the corresponding |
| 165 |
subtree in the accumulator (1-based) *) |
| 166 |
|
| 167 |
let get_results0 path r acc = |
| 168 |
let dummy_tree = Result_false ([], []) in |
| 169 |
let is_ref r = match r with Result_pass_ref _ -> true | _ -> false in |
| 170 |
|
| 171 |
let rec get_rec path r acc = |
| 172 |
match r with |
| 173 |
| Result_mono (mono, r1) -> |
| 174 |
let get_m m = (if m.decr_flag then "ml" else "mr"), m.variable in |
| 175 |
let path' = rev_itlist (fun m l -> get_m m :: l) mono path in |
| 176 |
let flag, acc', tree = get_rec path' r1 acc in |
| 177 |
if flag then true, acc', dummy_tree |
| 178 |
else false, acc', Result_mono (mono, tree) |
| 179 |
| Result_glue (j, convex_flag, r1, r2) -> |
| 180 |
let s1, s2 = if convex_flag then "ml", "mr" else "l", "r" in |
| 181 |
let p1, p2 = ((s1, j + 1) :: path), ((s2, j + 1) :: path) in |
| 182 |
let flag1, acc1, tree1 = get_rec p1 r1 acc in |
| 183 |
let flag2, acc', tree2 = get_rec p2 r2 acc1 in |
| 184 |
let n = (length acc' + 1) in |
| 185 |
if flag1 then |
| 186 |
if flag2 then |
| 187 |
true, acc', dummy_tree |
| 188 |
else if is_ref r1 then |
| 189 |
false, acc', Result_glue (j, convex_flag, r1, tree2) |
| 190 |
else |
| 191 |
false, acc' @ [rev p1, r1], Result_glue (j, convex_flag, Result_pass_ref n, tree2) |
| 192 |
else |
| 193 |
if flag2 then |
| 194 |
if is_ref r2 then |
| 195 |
false, acc', Result_glue (j, convex_flag, tree1, r2) |
| 196 |
else |
| 197 |
false, acc' @ [rev p2, r2], Result_glue (j, convex_flag, tree1, Result_pass_ref n) |
| 198 |
else |
| 199 |
false, acc', Result_glue (j, convex_flag, tree1, tree2) |
| 200 |
|
| 201 |
| Result_pass_mono _ -> false, acc, r |
| 202 |
| _ -> true, acc, dummy_tree in |
| 203 |
|
| 204 |
get_rec path r acc;; |
| 205 |
|
| 206 |
|
| 207 |
(* transform_result *) |
| 208 |
|
| 209 |
let transform_result x z r = |
| 210 |
(* get_domain *) |
| 211 |
(* Subdivides the given domain (x,z) according to the given path *) |
| 212 |
let domain_hash = Hashtbl.create 1000 in |
| 213 |
let find_hash, mem_hash, add_hash = |
| 214 |
Hashtbl.find domain_hash, Hashtbl.mem domain_hash, Hashtbl.add domain_hash in |
| 215 |
|
| 216 |
let get_domain path = |
| 217 |
let n = length x in |
| 218 |
let table f = map f (0--(n - 1)) in |
| 219 |
let rec rec_domain (x, z) path hash = |
| 220 |
match path with |
| 221 |
| [] -> x, z |
| 222 |
| (s, j) :: ps -> |
| 223 |
let hash' = hash^s^(string_of_int j) in |
| 224 |
if mem_hash hash' then |
| 225 |
rec_domain (find_hash hash') ps hash' |
| 226 |
else |
| 227 |
let j = j - 1 in |
| 228 |
let domain' = |
| 229 |
if s = "l" || s = "r" then |
| 230 |
let ( ++ ), ( / ) = (+.), (/.) in |
| 231 |
let yj = (List.nth x j ++ List.nth z j) / 2.0 in |
| 232 |
let delta b v = table (fun i -> if i = j && b then yj else List.nth v i) in |
| 233 |
if s = "l" then |
| 234 |
delta false x, delta true z |
| 235 |
else |
| 236 |
delta true x, delta false z |
| 237 |
else |
| 238 |
if s = "ml" then |
| 239 |
x, table (fun i -> if i = j then List.nth x i else List.nth z i) |
| 240 |
else |
| 241 |
table (fun i -> if i = j then List.nth z i else List.nth x i), z in |
| 242 |
let _ = add_hash hash' domain' in |
| 243 |
rec_domain domain' ps hash' in |
| 244 |
rec_domain (x,z) path "" in |
| 245 |
|
| 246 |
(* sub_domain *) |
| 247 |
(* Verifies if interval [x',z'] SUBSET interval [x,z] *) |
| 248 |
let sub_domain (x',z') (x,z) = |
| 249 |
let le a b = itlist2 (fun a b c -> c && (a <= b)) a b true in |
| 250 |
le x x' && le z' z in |
| 251 |
|
| 252 |
(* transform_pass_mono *) |
| 253 |
(* Replaces all (Result_pass_mono m) with (Result_mono [m] (Result_ref j)) where |
| 254 |
j is the reference to the corresponding domain *) |
| 255 |
let transform_pass_mono x z domains r = |
| 256 |
let domains_i = zip domains (1--length domains) in |
| 257 |
|
| 258 |
let find_domain x' z' = |
| 259 |
try find (fun d, _ -> sub_domain (x', z') d) domains_i with Failure _ -> (x,z), -1 in |
| 260 |
|
| 261 |
let get_m m = (if m.decr_flag then "ml" else "mr"), m.variable in |
| 262 |
|
| 263 |
let rec rec_transform path r = |
| 264 |
match r with |
| 265 |
| Result_mono (mono, r1) -> |
| 266 |
let path' = rev_itlist (fun m l -> get_m m :: l) mono path in |
| 267 |
Result_mono (mono, rec_transform path' r1) |
| 268 |
| Result_glue (j, convex_flag, r1, r2) -> |
| 269 |
let s1, s2 = if convex_flag then "ml", "mr" else "l", "r" in |
| 270 |
let p1, p2 = ((s1, j + 1) :: path), ((s2, j + 1) :: path) in |
| 271 |
let t1 = rec_transform p1 r1 in |
| 272 |
let t2 = rec_transform p2 r2 in |
| 273 |
Result_glue (j, convex_flag, t1, t2) |
| 274 |
| Result_pass_mono m -> |
| 275 |
let path' = rev (get_m m :: path) in |
| 276 |
let x', z' = get_domain path' in |
| 277 |
let _, i = find_domain x' z' in |
| 278 |
(* let _ = report (sprintf "p = %s, d = %s, found: %d" |
| 279 |
(domain_str x' z') (path_str path') i) in *) |
| 280 |
if i >= 0 then Result_mono ([m], Result_pass_ref (-i)) else r |
| 281 |
| _ -> r in |
| 282 |
|
| 283 |
rec_transform [] r in |
| 284 |
|
| 285 |
let rec transform acc r = |
| 286 |
let flag, rs, r' = get_results0 [] r acc in |
| 287 |
if flag then (rs @ [[], r]) |
| 288 |
else |
| 289 |
let domains = map (fun p, _ -> get_domain p) rs in |
| 290 |
let r_next = transform_pass_mono x z domains r' in |
| 291 |
let _ = r_next <> r' || failwith "transform_result: deadlock" in |
| 292 |
transform rs r_next in |
| 293 |
transform [] r;; |
| 294 |
|
| 295 |
|
| 296 |
end;; |