Debian Codegraph @

Formal_ineqs/verifier/certificate.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 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;;