Debian Codegraph @

Formal_ineqs/verifier/m_verifier_build.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 (* Auxiliary formal verification functions *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/arith/eval_interval.hl";;
14 needs "Formal_ineqs/arith/more_float.hl";;
15 needs "Formal_ineqs/taylor/m_taylor.hl";;
16 needs "Formal_ineqs/informal/informal_verifier.hl";;
17 needs "Formal_ineqs/verifier_options.hl";;
18 needs "Formal_ineqs/misc/misc_vars.hl";;
19
20
21 module M_verifier_build = struct
22
23 open Interval_arith;;
24 open Taylor_interval;;
25 open Multivariate_taylor;;
26
27 open More_float;;
28 open Eval_interval;;
29 open M_taylor;;
30
31 open Misc_vars;;
32 open Verifier_options;;
33
34 type verification_funs =
35 {
36 (* p_lin -> p_second -> domain_th -> taylor_th *)
37 taylor : int -> int -> thm -> thm;
38 (* pp -> lo -> hi -> interval_th *)
39 f : int -> term -> term -> thm;
40 (* i -> pp -> lo -> hi -> interval_th *)
41 df : int -> int -> term -> term -> thm;
42 (* i -> j -> pp -> lo -> hi -> interval_th *)
43 ddf : int -> int -> int -> term -> term -> thm;
44 (* lo -> hi -> diff2_th *)
45 diff2_f : term -> term -> thm;
46 };;
47
48
49 (**********************************)
50 (* mk_verification_functions *)
51
52 let mk_verification_functions_poly pp0 poly_tm =
53 let x_tm, body_tm = dest_abs poly_tm in
54 let new_f = poly_tm in
55 let n = get_dim x_tm in
56
57 let _ = !info_print_level <= 1 || (report0 (sprintf "Computing partial derivatives (%d)..." n); true) in
58 let partials = map (fun i ->
59 let _ = !info_print_level <= 1 || (report0 (sprintf " %d" i); true) in
60 gen_partial_poly i new_f) (1--n) in
61 let get_partial i eq_th =
62 let partial_i = gen_partial_poly i (rand (concl eq_th)) in
63 let pi = (rator o lhand o concl) partial_i in
64 REWRITE_RULE[GSYM partial2] (TRANS (AP_TERM pi eq_th) partial_i) in
65 let partials2 = map (fun j ->
66 let th = List.nth partials (j - 1) in
67 map (fun i ->
68 let _ = !info_print_level <= 1 || (report0 (sprintf " %d,%d" j i); true) in
69 get_partial i th) (1--j)) (1--n) in
70
71 let _ = !info_print_level <= 1 || (report0 " done\n"; true) in
72
73 let diff_th = gen_diff_poly new_f in
74 let lin_th = gen_lin_approx_poly_thm new_f diff_th partials in
75 let diff2_th = gen_diff2c_domain_poly new_f in
76 let second_th = gen_second_bounded_poly_thm new_f partials2 in
77
78 let replace_numeral i th =
79 let num_eq = (REWRITE_RULE[Arith_num.NUM_THM] o Arith_nat.NUMERAL_TO_NUM_CONV)
80 (mk_small_numeral i) in
81 GEN_REWRITE_RULE (LAND_CONV o RATOR_CONV o DEPTH_CONV) [num_eq] th in
82
83 let eval0 = mk_eval_function pp0 new_f in
84 let eval1 = map (fun i ->
85 let d_th = List.nth partials (i - 1) in
86 let eq_th = replace_numeral i d_th in
87 mk_eval_function_eq pp0 eq_th) (1--n) in
88
89 let eval2 = map (fun i ->
90 map (fun j ->
91 let d2_th = List.nth (List.nth partials2 (i - 1)) (j - 1) in
92 let eq_th' = replace_numeral i d2_th in
93 let eq_th = replace_numeral j eq_th' in
94 mk_eval_function_eq pp0 eq_th) (1--i)) (1--n) in
95
96 let diff2_f = eval_diff2_poly diff2_th in
97 let eval_f = eval_m_taylor pp0 diff2_th lin_th second_th in
98 {taylor = eval_f;
99 f = eval0;
100 df = (fun i -> List.nth eval1 (i - 1));
101 ddf = (fun i j -> List.nth (List.nth eval2 (j - 1)) (i - 1));
102 diff2_f = diff2_f;
103 }, Informal_verifier.mk_verification_functions_poly pp0 new_f partials partials2;;
104
105
106
107
108 end;;