Debian Codegraph @

Formal_ineqs/verifier/m_verifier_main.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 (* Main formal verification functions *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/verifier/m_verifier.hl";;
14 needs "Formal_ineqs/verifier/m_verifier_build.hl";;
15 needs "Formal_ineqs/taylor/m_taylor_arith2.hl";;
16 needs "Formal_ineqs/misc/misc_vars.hl";;
17
18 needs "Formal_ineqs/verifier/certificate.hl";;
19 needs "Formal_ineqs/informal/informal_search.hl";;
20 needs "Formal_ineqs/informal/informal_verifier.hl";;
21
22
23 module M_verifier_main = struct
24
25 open Misc_functions;;
26 open Interval_arith;;
27 open Eval_interval;;
28 open More_float;;
29 open M_verifier;;
30 open M_verifier_build;;
31 open M_taylor;;
32 open M_taylor_arith2;;
33 open Misc_vars;;
34 open Verifier_options;;
35
36
37 (* Parameters *)
38 type verification_parameters =
39 {
40 (* If true, then monotonicity properties can be used *)
41 (* to reduce the dimension of a problem *)
42 allow_derivatives : bool;
43 (* If true, then convexity can be used *)
44 (* to reduce the dimension of a problem *)
45 convex_flag : bool;
46 (* If true, then verification on internal subdomains can be skipped *)
47 (* for a monotone function *)
48 mono_pass_flag : bool;
49 (* If true, then raw interval arithmetic can be used for values of a function *)
50 (* (without Taylor approximations) *)
51 raw_intervals0 : bool;
52 (* If true, then raw interval arithmetic can be used for values of derivatives *)
53 raw_intervals1 : bool;
54 (* If true, then an informal procedure is used to determine *)
55 (* the optimal precision for the formal verification *)
56 adaptive_precision : bool;
57 (* This parameter might be used in cases when the certificate search *)
58 (* procedure returns a wrong result due to rounding errors *)
59 (* (this parameter will be eliminated when the search procedure is corrected) *)
60 eps : float;
61
62 eps_width : float;
63 test_certificate : bool;
64 };;
65
66 let default_params =
67 {
68 allow_derivatives = true;
69 convex_flag = false;
70 mono_pass_flag = true;
71 raw_intervals0 = true;
72 raw_intervals1 = true;
73 adaptive_precision = true;
74 eps = 0.0;
75
76 eps_width = 1e-12;
77 test_certificate = false;
78 };;
79
80
81 type verification_stats =
82 {
83 total_time : float;
84 formal_verification_time : float;
85 certificate : Certificate.certificate_stats;
86 };;
87
88
89 (********************************)
90
91 let rec unzip3 = function
92 | [] -> [], [], []
93 | (a,b,c) :: t ->
94 let x,y,z = unzip3 t in
95 a::x, b::y, c::z;;
96
97 (* Adds a constant approximation to the table of known constants *)
98 let add_constant_interval int_th =
99 Eval_interval.add_constant_interval int_th;
100 Informal_eval_interval.add_constant_interval int_th;;
101
102
103 (* Tests if an expression has only given binary and unary operations *)
104 let test_expression bin_ops unary_ops =
105 let rec test =
106 (* Tests if the expression is in the form `a$i` *)
107 let test_vector tm =
108 let var, index = dest_binary "$" tm in
109 dest_var var, dest_small_numeral index in
110 (* Tests if the expression is a valid binary operation *)
111 let test_binary tm =
112 try
113 let lhs, rhs = dest_comb tm in
114 let op, lhs = dest_comb lhs in
115 let c, _ = dest_const op in
116 if mem c bin_ops then (test lhs && test rhs) else false
117 with Failure _ -> false in
118 (* Tests if the expression is a valid unary operation *)
119 let test_unary tm =
120 try
121 let lhs, rhs = dest_comb tm in
122 let c, _ = dest_const lhs in
123 if mem c unary_ops then test rhs else false
124 with Failure _ -> false
125 in
126 fun tm ->
127 frees tm = [] ||
128 can dest_var tm ||
129 can test_vector tm ||
130 test_unary tm ||
131 test_binary tm in
132 test;;
133
134
135 (* Tests if the given expression is a polynomial expression *)
136 let is_poly =
137 let bin_ops = ["real_add"; "real_mul"; "real_sub"; "real_pow"] in
138 let unary_ops = ["real_neg"] in
139 test_expression bin_ops unary_ops;;
140
141
142 (**********************************)
143
144 (* Creates basic verification functions *)
145 let rec mk_funs =
146 (* add *)
147 let mk_add n (f1, ti1) (f2, ti2) =
148 (fun p1 p2 x ->
149 let a = f1 p1 p2 x and
150 b = f2 p1 p2 x in
151 eval_m_taylor_add2 n p1 p2 a b),
152 (fun p1 p2 x ->
153 let a = ti1 p1 p2 x and
154 b = ti2 p1 p2 x in
155 Informal_taylor.eval_m_taylor_add p1 p2 a b) in
156 (* sub *)
157 let mk_sub n (f1, ti1) (f2, ti2) =
158 (fun p1 p2 x ->
159 let a = f1 p1 p2 x and
160 b = f2 p1 p2 x in
161 eval_m_taylor_sub2 n p1 p2 a b),
162 (fun p1 p2 x ->
163 let a = ti1 p1 p2 x and
164 b = ti2 p1 p2 x in
165 Informal_taylor.eval_m_taylor_sub p1 p2 a b) in
166 (* mul *)
167 let mk_mul n (f1, ti1) (f2, ti2) =
168 (fun p1 p2 x ->
169 let a = f1 p1 p2 x and
170 b = f2 p1 p2 x in
171 eval_m_taylor_mul2 n p1 p2 a b),
172 (fun p1 p2 x ->
173 let a = ti1 p1 p2 x and
174 b = ti2 p1 p2 x in
175 Informal_taylor.eval_m_taylor_mul p1 p2 a b) in
176 (* pow *)
177 let mk_pow n (f1, ti1) k =
178 let eval_pow = M_taylor_arith.eval_m_taylor_pow k and
179 ieval_pow = Informal_taylor.eval_m_taylor_pow k in
180 (fun p1 p2 x ->
181 let a = f1 p1 p2 x in
182 eval_pow n p1 p2 a),
183 (fun p1 p2 x ->
184 let a = ti1 p1 p2 x in
185 ieval_pow p1 p2 a) in
186 (* neg *)
187 let mk_neg n (f1, ti1) =
188 (fun p1 p2 x ->
189 let a = f1 p1 p2 x in
190 eval_m_taylor_neg2 n a),
191 (fun p1 p2 x ->
192 let a = ti1 p1 p2 x in
193 Informal_taylor.eval_m_taylor_neg a) in
194 (* abs *)
195 let mk_real_abs n (f1, ti1) =
196 (fun p1 p2 x ->
197 let a = f1 p1 p2 x in
198 eval_m_taylor_abs2 n p2 a),
199 (fun p1 p2 x ->
200 let a = ti1 p1 p2 x in
201 Informal_taylor.eval_m_taylor_abs p2 a) in
202 (* sqrt *)
203 let mk_sqrt n (f1, ti1) =
204 (fun p1 p2 x ->
205 let a = f1 p1 p2 x in
206 eval_m_taylor_sqrt2 n p1 p2 a),
207 (fun p1 p2 x ->
208 let a = ti1 p1 p2 x in
209 Informal_taylor.eval_m_taylor_sqrt p1 p2 a) in
210 (* inv *)
211 let mk_inv n (f1, ti1) =
212 (fun p1 p2 x ->
213 let a = f1 p1 p2 x in
214 eval_m_taylor_inv2 n p1 p2 a),
215 (fun p1 p2 x ->
216 let a = ti1 p1 p2 x in
217 Informal_taylor.eval_m_taylor_inv p1 p2 a) in
218 (* exp *)
219 let mk_exp n (f1, ti1) =
220 (fun p1 p2 x ->
221 let a = f1 p1 p2 x in
222 eval_m_taylor_exp2 n p1 p2 a),
223 (fun p1 p2 x ->
224 let a = ti1 p1 p2 x in
225 Informal_taylor.eval_m_taylor_exp p1 p2 a) in
226 (* log *)
227 let mk_log n (f1, ti1) =
228 (fun p1 p2 x ->
229 let a = f1 p1 p2 x in
230 eval_m_taylor_log2 n p1 p2 a),
231 (fun p1 p2 x ->
232 let a = ti1 p1 p2 x in
233 Informal_taylor.eval_m_taylor_log p1 p2 a) in
234 (* atn *)
235 let mk_atn n (f1, ti1) =
236 (fun p1 p2 x ->
237 let a = f1 p1 p2 x in
238 eval_m_taylor_atn2 n p1 p2 a),
239 (fun p1 p2 x ->
240 let a = ti1 p1 p2 x in
241 Informal_taylor.eval_m_taylor_atn p1 p2 a) in
242 (* cos *)
243 let mk_cos n (f1, ti1) =
244 (fun p1 p2 x ->
245 let a = f1 p1 p2 x in
246 eval_m_taylor_cos2 n p1 p2 a),
247 (fun p1 p2 x ->
248 let a = ti1 p1 p2 x in
249 Informal_taylor.eval_m_taylor_cos p1 p2 a) in
250 (* sin *)
251 let mk_sin n (f1, ti1) =
252 (fun p1 p2 x ->
253 let a = f1 p1 p2 x in
254 eval_m_taylor_sin2 n p1 p2 a),
255 (fun p1 p2 x ->
256 let a = ti1 p1 p2 x in
257 Informal_taylor.eval_m_taylor_sin p1 p2 a) in
258 (* acs *)
259 let mk_acs n (f1, ti1) =
260 (fun p1 p2 x ->
261 let a = f1 p1 p2 x in
262 eval_m_taylor_acs2 n p1 p2 a),
263 (fun p1 p2 x ->
264 let a = ti1 p1 p2 x in
265 Informal_taylor.eval_m_taylor_acs p1 p2 a) in
266 (* asn *)
267 let mk_asn n (f1, ti1) =
268 (fun p1 p2 x ->
269 let a = f1 p1 p2 x in
270 eval_m_taylor_asn2 n p1 p2 a),
271 (fun p1 p2 x ->
272 let a = ti1 p1 p2 x in
273 Informal_taylor.eval_m_taylor_asn p1 p2 a) in
274 (* matan *)
275 let mk_matan n (f1, ti1) =
276 (fun p1 p2 x ->
277 let a = f1 p1 p2 x in
278 eval_m_taylor_matan2 n p1 p2 a),
279 (fun p1 p2 x ->
280 let a = ti1 p1 p2 x in
281 Informal_taylor.eval_m_taylor_matan p1 p2 a) in
282
283 (* binary operations *)
284 let bin_ops =
285 ["real_add", mk_add;
286 "real_sub", mk_sub;
287 "real_mul", mk_mul] in
288 (* unary operations *)
289 let unary_ops =
290 ["real_neg", mk_neg;
291 "real_abs", mk_real_abs;
292 "sqrt", mk_sqrt;
293 "exp", mk_exp;
294 "log", mk_log;
295 "atn", mk_atn;
296 "cos", mk_cos;
297 "sin", mk_sin;
298 "asn", mk_asn;
299 "acs", mk_acs;
300 "matan", mk_matan;
301 "real_inv", mk_inv] in
302 (* makes a binary operation *)
303 let mk_bin n pp x_var tm =
304 let lhs, rhs = dest_comb tm in
305 let op, lhs = dest_comb lhs in
306 let name = fst (dest_const op) in
307 if name = "real_pow" then
308 let l_funs = mk_funs n pp (mk_abs (x_var, lhs)) in
309 let k = dest_small_numeral rhs in
310 mk_pow n l_funs k
311 else
312 let mk_f = assoc name bin_ops in
313 let l_funs = mk_funs n pp (mk_abs (x_var, lhs)) and
314 r_funs = mk_funs n pp (mk_abs (x_var, rhs)) in
315 mk_f n l_funs r_funs in
316 (* makes an unary operation *)
317 let mk_unary n pp x_var tm =
318 let op, rhs = dest_comb tm in
319 let mk_f = assoc ((fst o dest_const) op) unary_ops in
320 let funs = mk_funs n pp (mk_abs(x_var, rhs)) in
321 mk_f n funs in
322 (* the main function *)
323 fun n pp fun_tm ->
324 let x_var, body_tm = dest_abs fun_tm in
325 if is_poly body_tm then
326 let eval_fs, ti = mk_verification_functions_poly pp fun_tm in
327 eval_fs.taylor, ti.Informal_verifier.taylor
328 else
329 try mk_bin n pp x_var body_tm with Failure _ ->
330 mk_unary n pp x_var body_tm;;
331
332
333 (* Prepares verification functions *)
334 (* fun_tm must be in the form `\x. f x` *)
335 let mk_verification_functions =
336 let (* dummy_f pp lo hi = failwith "dummy f" and *)
337 dummy_df i pp lo hi = failwith "dummy df" and
338 dummy_ddf i j pp lo hi = failwith "dummy ddf" and
339 dummy_diff2 lo hi = failwith "dummy diff2" in
340 fun params pp fun_tm ->
341 let x_var, body_tm = dest_abs fun_tm in
342 if is_poly body_tm then
343 mk_verification_functions_poly pp fun_tm
344 else
345 let n = get_dim x_var in
346 let eval_taylor, eval_ti = mk_funs n pp fun_tm in
347 let eval0 = mk_eval_function pp fun_tm in
348 let eval0_informal = Informal_taylor.mk_eval_function pp fun_tm in
349 let _ = params := {
350 !params with
351 raw_intervals1 = false;
352 convex_flag = false
353 } in
354 {
355 taylor = eval_taylor;
356 f = eval0;
357 df = dummy_df;
358 ddf = dummy_ddf;
359 diff2_f = dummy_diff2
360 },
361 {
362 Informal_verifier.taylor = eval_ti;
363 Informal_verifier.f = eval0_informal;
364 Informal_verifier.df = dummy_df;
365 Informal_verifier.ddf = dummy_ddf
366 };;
367
368
369 (********************************)
370
371 let convert_to_float_list pp lo_flag list_tm =
372 let tms = dest_list list_tm in
373 let i_funs = map build_interval_fun tms in
374 let ints = map (fun f -> eval_interval_fun pp f [] []) i_funs in
375 let extract = (if lo_flag then fst else snd) o dest_pair o rand o concl in
376 mk_list (map extract ints, real_ty);;
377
378
379 (* Creates a theorem |- interval[xx_tm, zz_tm] SUBSET interval[float(xx_tm), float(zz_tm)]
380 and two lists: float(xx_tm) and float(zz_tm) *)
381 let mk_float_domain pp (xx_tm, zz_tm) =
382 let xx_list = dest_list xx_tm and
383 zz_list = dest_list zz_tm in
384 let n = length xx_list in
385 let get_intervals tms =
386 let i_funs = map build_interval_fun tms in
387 map (fun f -> eval_interval_fun pp f [] []) i_funs in
388 let xx_ints = get_intervals xx_list and
389 zz_ints = get_intervals zz_list in
390 let xx_ineqs = map (CONJUNCT1 o ONCE_REWRITE_RULE[interval_arith]) xx_ints and
391 zz_ineqs = map (CONJUNCT2 o ONCE_REWRITE_RULE[interval_arith]) zz_ints in
392 let a_vals = map (lhand o concl) xx_ineqs and
393 b_vals = map (rand o concl) zz_ineqs in
394 let a_vars = mk_real_vars n "a" and
395 b_vars = mk_real_vars n "b" and
396 c_vars = mk_real_vars n "c" and
397 d_vars = mk_real_vars n "d" in
398 let th0 = (INST (zip xx_list c_vars) o INST (zip zz_list d_vars) o
399 INST (zip a_vals a_vars) o INST (zip b_vals b_vars))
400 subset_interval_thms_array.(n) in
401 itlist MY_PROVE_HYP (xx_ineqs @ zz_ineqs) th0,
402 (mk_list (a_vals, real_ty), mk_list (b_vals, real_ty));;
403
404
405
406 (* Given a term a < b, returns the theorem |- a - b < &0 ==> a < b *)
407 (* Also, deals with > and / *)
408 (* A user can provide additional rewrite theorems *)
409 let mk_standard_ineq =
410 let lemma_lt = REAL_ARITH `a < b <=> a - b < &0` and
411 lemma_le = REAL_ARITH `a <= b <=> a - b <= &0` and
412 lemma_imp = TAUT `(P <=> Q) ==> (Q ==> P)` in
413 fun thms tm ->
414 let th0 = (REWRITE_CONV([real_gt; real_ge; real_div] @ thms)
415 THENC DEPTH_CONV let_CONV) tm in
416 let rhs = rand (concl th0) in
417 let th1 = (ONCE_REWRITE_CONV[lemma_le] THENC
418 ONCE_REWRITE_CONV[lemma_lt] THENC
419 PURE_REWRITE_CONV[REAL_NEG_0; REAL_SUB_RZERO; REAL_SUB_LZERO]) rhs in
420 let th2 = TRANS th0 th1 in
421 let ineqs = striplist dest_disj (rand (concl th2)) in
422 let le_flags = map (can (dest_binop le_op_real)) ineqs in
423 if exists I le_flags then
424 let q_le_tms, q_lt_tms = unzip
425 (map2 (fun i b ->
426 let var = mk_var ("Q" ^ string_of_int i, real_ty) in
427 mk_binop (if b then le_op_real else lt_op_real) var `&0`,
428 mk_binop lt_op_real var `&0`)
429 (1 -- length le_flags) le_flags) in
430 let qs_le = end_itlist (curry mk_disj) q_le_tms and
431 qs_lt = end_itlist (curry mk_disj) q_lt_tms and
432 p_tm = `P:bool` in
433 (* |- (P <=> Q1 <= &0 \/ ...) ==> (Q1 < &0 \/ ... ==> P) *)
434 let q_th = MESON[REAL_LT_IMP_LE]
435 (mk_imp (mk_eq (p_tm, qs_le), mk_imp (qs_lt, p_tm))) in
436 (* |- Q1 < &0 \/ ... ==> P *)
437 MATCH_MP q_th th2
438 else
439 MATCH_MP lemma_imp th2;;
440
441 (* Converts a term in the form `x + y` into the term `\x:real^2. x$1 + x$2` *)
442 let expr_to_vector_fun =
443 let comp_op = `$` in
444 fun expr_tm ->
445 let vars = List.sort compare (frees expr_tm) in
446 let n = length vars in
447 let x_var = mk_var ("x", n_vector_type_array.(if n = 0 then 1 else n)) in
448 let x_tm = mk_icomb (comp_op, x_var) in
449 let vars2 = map (fun i -> mk_comb (x_tm, mk_small_numeral i)) (1--n) in
450 mk_abs (x_var, subst (zip vars2 vars) expr_tm),
451 (if n = 0 then mk_vector_list [x_var] else mk_vector_list vars);;
452
453 (* Converts a list of terms in the form [`x + y`; `z`]
454 into a list of terms [`\x:real^3. x$1 + x$2`; `\x:real^3. x$3` *)
455 let exprs_to_vector_fun =
456 let comp_op = `$` in
457 fun expr_tms ->
458 let vars = List.sort compare (unions (map frees expr_tms)) in
459 let n = length vars in
460 let x_var = mk_var ("x", n_vector_type_array.(if n = 0 then 1 else n)) in
461 let x_tm = mk_icomb (comp_op, x_var) in
462 let vars2 = map (fun i -> mk_comb (x_tm, mk_small_numeral i)) (1--n) in
463 map (fun tm -> mk_abs (x_var, subst (zip vars2 vars) tm)) expr_tms,
464 (if n = 0 then mk_vector_list [x_var] else mk_vector_list vars);;
465
466
467 (* Given an inequality `P x y`, variable names and the corresponding bounds,
468 yields `(x0 <= x /\ x <= x1) /\ (y0 <= y /\ y <= y1) ==> P x y` *)
469 let mk_ineq ineq_tm names dom_tm =
470 let lo_list = dest_list (fst dom_tm) and
471 hi_list = dest_list (snd dom_tm) in
472 let vars = map (fun name -> mk_var (name, real_ty)) names in
473 let lo_ineqs = map2 (fun tm1 tm2 -> mk_binop le_op_real tm1 tm2) lo_list vars and
474 hi_ineqs = map2 (fun tm1 tm2 -> mk_binop le_op_real tm1 tm2) vars hi_list in
475 let ineqs = map2 (fun tm1 tm2 -> mk_conj (tm1, tm2)) lo_ineqs hi_ineqs in
476 let cond = end_itlist (curry mk_conj) ineqs in
477 mk_imp (cond, ineq_tm);;
478
479
480 (* Reverts the effect of mk_ineq function *)
481 let dest_ineq ineq_tm =
482 if frees ineq_tm = [] then
483 ineq_tm, [], (real_empty_list, real_empty_list)
484 else
485 let tm0 = (rand o concl o PURE_REWRITE_CONV[IMP_IMP; GSYM CONJ_ASSOC]) ineq_tm in
486 let cond, ineq = dest_imp tm0 in
487 let conds = striplist dest_conj cond in
488 let ineqs = ref [] in
489 let decode_ineq tm =
490 let lhs, rhs = dest_binop le_op_real tm in
491 let lo_flag = (frees lhs = []) in
492 let name = (fst o dest_var) (if lo_flag then rhs else lhs) in
493 let val_ref =
494 try assoc name !ineqs
495 with Failure _ ->
496 let val_ref = ref (x_var_real, x_var_real) in
497 ineqs := ((name, val_ref) :: !ineqs); val_ref in
498 val_ref := if lo_flag then (lhs, snd !val_ref) else (fst !val_ref, rhs) in
499 let _ = map (fun tm ->
500 (try decode_ineq tm with Failure _ ->
501 failwith ("Bad variable bound inequality: "^string_of_term tm))) conds in
502 let names, bounds0 = unzip !ineqs in
503 let lo, hi = unzip (map (fun r -> !r) bounds0) in
504 let test_bounds bounds bound_name =
505 let _ = map2 (fun tm name -> if frees tm <> [] then
506 failwith (bound_name^" bound is not defined for "^name) else ())
507 bounds names in () in
508 let _ = test_bounds hi "Upper"; test_bounds lo "Lower" in
509 ineq, names, (mk_real_list lo, mk_real_list hi);;
510
511 (*********************************)
512
513 (* Normalizes a verification result *)
514 let normalize_result norm_flag v1 imp_th1 domain_sub_th pass_thm =
515 let th0 = REWRITE_RULE[m_cell_pass] pass_thm in
516 let n = (get_dim o fst o dest_forall o concl) th0 in
517 let th1 = SPEC v1 th0 in
518 let comp_thms = end_itlist CONJ (Array.to_list comp_thms_array.(n)) in
519 let th2 = UNDISCH_ALL (REWRITE_RULE[comp_thms] th1) in
520 let th3 = MP imp_th1 th2 in
521 let dom_th = (UNDISCH_ALL o SPEC v1 o REWRITE_RULE[SUBSET]) domain_sub_th in
522 let th4 = (DISCH_ALL o MY_PROVE_HYP dom_th) th3 in
523 let th5 = REWRITE_RULE[IN_INTERVAL; dimindex_array.(n);
524 gen_in_interval n; comp_thms] th4 in
525 if norm_flag then GEN_ALL th5 else th4;;
526
527
528 (* Verifies the given inequality *)
529 (* Returns the final theorem and verification statistics *)
530 let verify_ineq0 params0 norm_flag pp ineq_tm var_names (lo_tm, hi_tm) rewrite_thms =
531 let total_start = Unix.gettimeofday() in
532 let imp_th1 = mk_standard_ineq rewrite_thms ineq_tm in
533 let ineq_tm1 = (lhand o lhand o concl) imp_th1 in
534 if frees ineq_tm1 = [] then
535 let i_fun = build_interval_fun ineq_tm1 in
536 let th0 = eval_interval_fun pp i_fun [] [] in
537 let th1 = float_interval_lt0 th0 in
538 let total = Unix.gettimeofday() -. total_start in
539 MP imp_th1 th1,
540 {total_time = total; formal_verification_time = total; certificate = Certificate.dummy_stats}
541 else
542 let fun_tm, v1 = expr_to_vector_fun ineq_tm1 in
543 let vars = map (fst o dest_var) (dest_vector v1) in
544 let lo_list = dest_list lo_tm and
545 hi_list = dest_list hi_tm in
546 let bounds0 = zip var_names (zip lo_list hi_list) in
547 let bounds = itlist (fun name list -> assoc name bounds0 :: list) vars [] in
548 let xx, zz = unzip bounds in
549 let xx, zz = mk_real_list xx, mk_real_list zz in
550
551 let domain_sub_th, (xx1, zz1) = mk_float_domain pp (xx, zz) in
552 let n = (get_dim o fst o dest_abs) fun_tm in
553 let xx2 = Informal_taylor.convert_to_float_list pp true xx and
554 zz2 = Informal_taylor.convert_to_float_list pp false zz in
555 let xx_float = map float_of_float_tm (dest_list xx1) and
556 zz_float = map float_of_float_tm (dest_list zz1) in
557
558 let params = ref params0 in
559 let eval_fs, ti = mk_verification_functions params pp fun_tm in
560
561 let _ = !info_print_level < 1 || (report0 "Constructing a solution certificate... "; true) in
562 let opt0 = {
563 Informal_search.raw_intervals0 = !params.raw_intervals0;
564 Informal_search.max_width = 1e-10;
565 Informal_search.max_depth = 200;
566 Informal_search.pp = pp;
567 Informal_search.mono_depth = if !params.allow_derivatives then 200 else 0;
568 } in
569 let fs_inf = map (fun f -> f.Informal_verifier.f, f.Informal_verifier.taylor) [ti] in
570 let dom_inf = Informal_taylor.mk_m_center_domain pp xx2 zz2 in
571 let certificate = Informal_search.construct_certificate opt0 dom_inf fs_inf in
572
573 let stats = Certificate.result_stats certificate in
574 let _ = !info_print_level < 1 || (report0 " done\n"; true) in
575 let _ = !info_print_level < 1 || (Certificate.report_stats stats; true) in
576
577 let c1 = Certificate.transform_result xx_float zz_float certificate in
578 let start, finish, result =
579 if !params.adaptive_precision then
580 let _ = !info_print_level < 1 || (report0 "Informal verification... "; true) in
581 let c1p = Informal_verifier.m_verify_list pp 1 pp [ti] c1 xx2 zz2 in
582 let _ = !info_print_level < 1 || (report0 " done\n"; true) in
583
584 let _ = !info_print_level < 1 || (report0 "Formal verification... "; true) in
585 let start = Unix.gettimeofday() in
586 let result = m_p_verify_list n pp eval_fs c1p xx1 zz1 in
587 let finish = Unix.gettimeofday() in
588 let _ = !info_print_level < 1 || (report0 " done\n"; true) in
589 start, finish, result
590 else
591 let _ = !info_print_level < 1 || (report0 "Formal verification... "; true) in
592 let start = Unix.gettimeofday() in
593 let result = m_verify_list n pp eval_fs c1 xx1 zz1 in
594 let finish = Unix.gettimeofday() in
595 let _ = !info_print_level < 1 || (report0 " done\n"; true) in
596 start, finish, result in
597 normalize_result norm_flag v1 imp_th1 domain_sub_th result,
598 {total_time = finish -. total_start; formal_verification_time = finish -. start; certificate = stats};;
599
600
601 (*
602 (* A simple verification function which accepts
603 a list of rewrite theorems which are applied to the inequality
604 before verification *)
605 let verify_ineq_and_rewrite rewrite_thms params pp ineq_tm =
606 let ineq, vars, bounds = dest_ineq ineq_tm in
607 verify_ineq0 params true pp ineq vars bounds rewrite_thms;;
608
609
610 (* The simplest verification function *)
611 let verify_ineq = verify_ineq_and_rewrite [];;
612
613 *)
614
615 let normalize_disj_result norm_flag fun_tms v1 imp_th1 domain_sub_th pass_thm =
616 let fs, dom = dest_m_cell_pass (concl pass_thm) in
617 let fs2 = mk_list (fun_tms, type_of (hd fun_tms)) in
618 let append_th0 = MATCH_MP (ISPECL[fs; fs2; dom] M_CELL_LIST_PASS_APPEND) pass_thm in
619 let append_th1 = REWRITE_RULE[APPEND] append_th0 in
620 let th0 = REWRITE_RULE[m_cell_list_pass; ITLIST] append_th1 in
621 let n = (get_dim o fst o dest_forall o concl) th0 in
622 let th1 = SPEC v1 th0 in
623 let comp_thms = end_itlist CONJ (Array.to_list comp_thms_array.(n)) in
624 let th2 = REWRITE_RULE[comp_thms] th1 in
625 let r_tm0 = (rand o concl) th2 in
626 let r_tm1 = (lhand o concl) imp_th1 in
627 let imp_th = REAL_ARITH (mk_imp (r_tm0, r_tm1)) in
628 let th3 = MP imp_th (UNDISCH_ALL th2) in
629 let th4 = MP imp_th1 th3 in
630 let dom_th = (UNDISCH_ALL o SPEC v1 o REWRITE_RULE[SUBSET]) domain_sub_th in
631 let th5 = (DISCH_ALL o MY_PROVE_HYP dom_th) th4 in
632 let th6 = REWRITE_RULE[IN_INTERVAL; dimindex_array.(n); gen_in_interval n; comp_thms] th5 in
633 if norm_flag then GEN_ALL th6 else th5;;
634
635
636 let verify_disj_ineq0 params0 norm_flag pp ineq_tm var_names (lo_tm, hi_tm) rewrite_thms =
637 let total_start = Unix.gettimeofday() in
638 let imp_th1 = mk_standard_ineq rewrite_thms ineq_tm in
639 let ineq_tms = striplist dest_disj ((lhand o concl) imp_th1) in
640 if length ineq_tms = 1 then
641 verify_ineq0 params0 norm_flag pp ineq_tm var_names (lo_tm, hi_tm) rewrite_thms
642 else
643 let ineq_tms1 = map lhand ineq_tms in
644 let fun_tms, v1 = exprs_to_vector_fun ineq_tms1 in
645 let vars = map (fst o dest_var) (dest_vector v1) in
646 let lo_list = dest_list lo_tm and
647 hi_list = dest_list hi_tm in
648 let bounds0 = zip var_names (zip lo_list hi_list) in
649 let bounds = itlist (fun name list -> assoc name bounds0 :: list) vars [] in
650 let xx, zz = unzip bounds in
651 let xx, zz = mk_real_list xx, mk_real_list zz in
652
653 let domain_sub_th, (xx1, zz1) = mk_float_domain pp (xx, zz) in
654 let n = (get_dim o fst o dest_abs) (hd fun_tms) in
655 let xx2 = Informal_taylor.convert_to_float_list pp true xx and
656 zz2 = Informal_taylor.convert_to_float_list pp false zz in
657 let xx_float = map float_of_float_tm (dest_list xx1) and
658 zz_float = map float_of_float_tm (dest_list zz1) in
659
660 (* Issue warnings for unimplemented features *)
661 let _ = params0.mono_pass_flag = false || (report "WARNING: mono_pass_flag should be false"; true) in
662 let _ = params0.convex_flag = false || (report "WARNING: covex_flag should be false"; true) in
663 let _ = params0.allow_derivatives = false || (report "WARNING: allow_derivatives should be false"; true) in
664
665 let params = ref {params0 with
666 mono_pass_flag = false;
667 convex_flag = false;
668 allow_derivatives = false} in
669
670 let eval_fs_list, ti_list = unzip (map (mk_verification_functions params pp) fun_tms) in
671 let _ = !info_print_level < 1 || (report0 "Constructing a solution certificate... "; true) in
672 let opt0 = {
673 Informal_search.raw_intervals0 = !params.raw_intervals0;
674 Informal_search.max_width = 1e-10;
675 Informal_search.max_depth = 200;
676 Informal_search.pp = pp;
677 Informal_search.mono_depth = 0;
678 } in
679 let fs_inf = map (fun f -> f.Informal_verifier.f, f.Informal_verifier.taylor) ti_list in
680 let dom_inf = Informal_taylor.mk_m_center_domain pp xx2 zz2 in
681 let certificate = Informal_search.construct_certificate opt0 dom_inf fs_inf in
682
683 let stats = Certificate.result_stats certificate in
684 let _ = !info_print_level < 1 || (report0 " done\n"; true) in
685 let _ = !info_print_level < 1 || (Certificate.report_stats stats; true) in
686
687 let c1 = certificate in
688 let start, finish, result =
689 if !params.adaptive_precision then
690 let _ = !info_print_level < 1 || (report0 "Informal verification... "; true) in
691 let c1p, _ = Informal_verifier.m_verify_raw0 pp 1 pp ti_list c1 xx2 zz2 in
692 let _ = !info_print_level < 1 || (report0 " done\n"; true) in
693
694 let _ = !info_print_level < 1 || (report0 "Formal verification... "; true) in
695 let start = Unix.gettimeofday() in
696 let result = m_p_verify_disj_raw0 n pp eval_fs_list c1p xx1 zz1 in
697 let finish = Unix.gettimeofday() in
698 let _ = !info_print_level < 1 || (report0 " done\n"; true) in
699 start, finish, result
700 else
701 let _ = !info_print_level < 1 || (report0 "Formal verification... "; true) in
702 let start = Unix.gettimeofday() in
703 let result = m_verify_disj_raw0 n pp eval_fs_list c1 xx1 zz1 in
704 let finish = Unix.gettimeofday() in
705 let _ = !info_print_level < 1 || (report0 " done\n"; true) in
706 start, finish, result in
707 normalize_disj_result norm_flag fun_tms v1 imp_th1 domain_sub_th result,
708 {total_time = finish -. total_start; formal_verification_time = finish -. start; certificate = stats};;
709
710
711
712 (* A simple verification function which accepts
713 a list of rewrite theorems which are applied to the inequality
714 before verification *)
715 let verify_ineq_and_rewrite rewrite_thms params pp ineq_tm =
716 let ineq, vars, bounds = dest_ineq ineq_tm in
717 verify_disj_ineq0 params true pp ineq vars bounds rewrite_thms;;
718
719 (* The simplest verification function *)
720 let verify_ineq = verify_ineq_and_rewrite [REAL_POW_1; real_pow];;
721
722 end;;
723
724
725 (*
726 let h0 = new_definition `h0 = #1.26` and
727 lmfun = new_definition`lmfun h = if (h<=h0) then (h0 - h)/(h0 - &1) else &0` and
728 hplus = new_definition `hplus = #1.3254` and
729 marchal_quartic = new_definition `marchal_quartic h =
730 (sqrt(&2)-h)*(h- hplus )*(&9*(h pow 2) - &17*h + &3)/
731 ((sqrt(&2) - &1)* &5 *(hplus - &1))`;;
732
733
734 let lmfun_cond_le = (UNDISCH_ALL o prove)(`x <= h0 ==> lmfun x = (h0 - x) / (h0 - &1)`,
735 REWRITE_TAC[lmfun] THEN REAL_ARITH_TAC);;
736
737 let lmfun_cond_ge = (UNDISCH_ALL o prove)(`h0 <= x ==> lmfun x = &0`,
738 ONCE_REWRITE_TAC[REAL_ARITH `a <= b <=> ~(b <= a) \/ a = b`] THEN
739 STRIP_TAC THEN ASM_REWRITE_TAC[lmfun] THEN
740 REAL_ARITH_TAC);;
741
742 let eq_tm = `marchal_quartic x - lmfun x`;;
743 let eq_th1, eq_th2 =
744 let ths = [marchal_quartic; h0; hplus] in
745 REWRITE_CONV (lmfun_cond_le :: ths) eq_tm,
746 REWRITE_CONV (REAL_SUB_RZERO :: lmfun_cond_ge :: ths) eq_tm;;
747
748 let eq_tm1 = (rand o concl) eq_th1 and
749 eq_tm2 = (rand o concl) eq_th2;;
750
751 let ineq1_concl = mk_binary "real_lt" (eq_tm1, `&0`) and
752 ineq2_concl = mk_binary "real_lt" (`&0`, eq_tm1) and
753 ineq3_concl = mk_binary "real_lt" (`&0`, eq_tm2);;
754
755 (* A better approximation cannot be achieved directly *)
756 let bounds1 = `#1.2 <= x /\ x <= #1.2317544220903043901` and
757 bounds2 = `#1.2317544220903047 <= x /\ x <= #1.26` and
758 bounds3 = `#1.26 <= x /\ x <= #1.3`;;
759
760 let ineq1_tm = mk_imp (bounds1, ineq1_concl) and
761 ineq2_tm = mk_imp (bounds2, ineq2_concl) and
762 ineq3_tm = mk_imp (bounds3, ineq3_concl);;
763
764 open M_verifier_main;;
765
766 let ineq1_th, _ = verify_ineq {default_params with eps = 0.; allow_derivatives = true} 12 ineq1_tm;;
767 let ineq2_th, _ = verify_ineq {default_params with eps = 0.; allow_derivatives = true} 12 ineq2_tm;;
768 let ineq3_th, _ = verify_ineq {default_params with eps = 0.} 12 ineq3_tm;;
769
770
771
772 open M_verifier_main;;
773 let ineq_tm = `&0 <= x /\ x <= &1 /\ &0 <= y /\ y <= &1 ==> x * y < #0.6 \/ x < #1.5 \/ y < #0.8`;;
774 let ineq_tm = ineq2_tm;;
775 verify_ineq {default_params with allow_derivatives = true} 20 ineq_tm;;
776
777 let ineq, vars, bounds = dest_ineq ineq_tm;;
778
779 let params0 = default_params and
780 norm_flag = true and
781 pp = 5 and
782 ineq_tm = ineq and
783 var_names = vars and
784 lo_tm, hi_tm = bounds and
785 rewrite_thms = [];;
786 let pp = 20;;
787 let params0 = {params0 with eps = 0.};;
788 let total_start = Unix.gettimeofday();;
789
790 let eq_th1 = mk_standard_ineq rewrite_thms ineq_tm;;
791 let ineq_tms = striplist dest_disj ((rand o concl) eq_th1);;
792 let ineq_tms1 = map lhand ineq_tms;;
793
794 if length ineq_tms1 = 1 && frees (hd ineq_tms1) = [] then
795 let i_fun = build_interval_fun (hd ineq_tms1) in
796 let th0 = eval_interval_fun pp i_fun [] [] in
797 let th1 = float_interval_lt0 th0 in
798 let total = Unix.gettimeofday() -. total_start in
799 REWRITE_RULE[GSYM eq_th1] th1,
800 {total_time = total; formal_verification_time = total; certificate = Verifier.dummy_stats}
801 else
802 failwith "";;
803
804 let fun_tms, v1 = exprs_to_vector_fun ineq_tms1;;
805 let vars = map (fst o dest_var) (dest_vector v1);;
806 let lo_list = dest_list lo_tm and
807 hi_list = dest_list hi_tm;;
808 let bounds0 = zip var_names (zip lo_list hi_list);;
809 let bounds = itlist (fun name list -> assoc name bounds0 :: list) vars [];;
810 let xx, zz = unzip bounds;;
811 let xx, zz = mk_real_list xx, mk_real_list zz;;
812
813 let domain_sub_th, (xx1, zz1) = mk_float_domain pp (xx, zz);;
814 let n = (get_dim o fst o dest_abs) (hd fun_tms);;
815 let xx2 = Informal_taylor.convert_to_float_list pp true xx and
816 zz2 = Informal_taylor.convert_to_float_list pp false zz;;
817 let xx_float = map float_of_float_tm (dest_list xx1) and
818 zz_float = map float_of_float_tm (dest_list zz1);;
819
820 let params = ref params0;;
821 let eval_fs_list, tf_list, ti_list = unzip3 (map (mk_verification_functions params pp) fun_tms);;
822
823 let _ = !info_print_level < 1 || (report0 "Constructing a solution certificate... "; true);;
824 let opt0 = {
825 Verifier.min_flag = false;
826 Verifier.min_max = 0.0;
827 Verifier.allow_d = false;
828 Verifier.allow_convex_flag = false;
829 Verifier.mono_pass_flag = true;
830 Verifier.raw_interval_flag = params0.raw_intervals_flag;
831 Verifier.epsilon = params0.eps;
832 };;
833 let certificate = Verifier.run_test tf_list xx_float zz_float opt0;;
834 let stats = Verifier.result_stats certificate;;
835 let _ = !info_print_level < 1 || (report0 " done\n"; true);;
836 let _ = !info_print_level < 1 || (Verifier.report_stats stats; true);;
837
838 let c1 = certificate;;
839 let start, finish, result = 0,0,0;;
840 if !params.adaptive_precision then 1 else 0;;
841 let _ = !info_print_level < 1 || (report0 "Informal verification... "; true);;
842 let c1p, _ = Informal_verifier.m_verify_raw0 pp 1 pp ti_list c1 xx2 zz2;;
843 let _ = !info_print_level < 1 || (report0 " done\n"; true);;
844
845 let _ = !info_print_level < 1 || (report0 "Formal verification... "; true);;
846 let start = Unix.gettimeofday();;
847 let result = m_p_verify_disj_raw0 n pp eval_fs_list c1p xx1 zz1;;
848 let finish = Unix.gettimeofday();;
849 let _ = !info_print_level < 1 || (report0 " done\n"; true);;
850 start, finish, result;;
851 (*else*)
852 let _ = !info_print_level < 1 || (report0 "Formal verification... "; true);;
853 let start = Unix.gettimeofday();;
854 let result = m_verify_disj_raw0 n pp eval_fs_list c1 xx1 zz1;;
855 let finish = Unix.gettimeofday();;
856 let _ = !info_print_level < 1 || (report0 " done\n"; true) in
857 start, finish, result;;
858
859 normalize_disj_result norm_flag fun_tms v1 eq_th1 domain_sub_th result;;
860 {total_time = finish -. total_start; formal_verification_time = finish -. start; certificate = stats};;
861
862 *)