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