| 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 |
(* Special list conversions *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
needs "Formal_ineqs/arith/more_float.hl";; |
| 14 |
needs "Formal_ineqs/list/list_conversions.hl";; |
| 15 |
needs "Formal_ineqs/misc/misc_vars.hl";; |
| 16 |
|
| 17 |
|
| 18 |
module type List_float_sig = sig |
| 19 |
val list_sum : thm |
| 20 |
val list_sum2 : thm |
| 21 |
val error_mul_f2 : thm |
| 22 |
val error_mul_f1 : thm |
| 23 |
val list_sum_conv : (term -> thm) -> term -> thm |
| 24 |
val list_sum2_le_conv : int -> (int -> term -> term -> thm) -> term -> thm |
| 25 |
val error_mul_f2_le_conv : int -> term -> term -> thm |
| 26 |
val error_mul_f2_le_conv2 : int -> term -> term -> thm |
| 27 |
val error_mul_f1_le_conv : term -> int -> term -> term -> thm |
| 28 |
end;; |
| 29 |
|
| 30 |
|
| 31 |
module List_float : List_float_sig = struct |
| 32 |
|
| 33 |
open Misc_functions;; |
| 34 |
open Arith_nat;; |
| 35 |
open Arith_float;; |
| 36 |
open More_float;; |
| 37 |
open Float_theory;; |
| 38 |
open List_conversions;; |
| 39 |
open Misc_vars;; |
| 40 |
|
| 41 |
let MY_RULE_FLOAT = UNDISCH_ALL o NUMERALS_TO_NUM o |
| 42 |
PURE_REWRITE_RULE[FLOAT_OF_NUM; min_exp_def; GSYM IMP_IMP] o SPEC_ALL;; |
| 43 |
|
| 44 |
|
| 45 |
(****************************) |
| 46 |
(* new definitions *) |
| 47 |
|
| 48 |
let list_sum = new_definition `list_sum list f = ITLIST (\t1 t2. f t1 + t2) list (&0)`;; |
| 49 |
let list_sum2 = new_definition `list_sum2 f l1 l2 = ITLIST2 (\a b c. f a b + c) l1 l2 (&0)`;; |
| 50 |
|
| 51 |
let error_mul_f2 = new_definition `error_mul_f2 a int = a * iabs int`;; |
| 52 |
let error_mul_f1 = new_definition `error_mul_f1 w x list = x * list_sum2 error_mul_f2 w list`;; |
| 53 |
|
| 54 |
(*************************************) |
| 55 |
(* list_sum conversions *) |
| 56 |
|
| 57 |
let LIST_SUM_A_EMPTY = prove(`list_sum [] (f:A->real) = &0`, REWRITE_TAC[list_sum; ITLIST]) and |
| 58 |
LIST_SUM_A_H = prove(`list_sum [h:A] f = f h`, REWRITE_TAC[list_sum; ITLIST; REAL_ADD_RID]) and |
| 59 |
LIST_SUM_A_CONS = prove(`list_sum (CONS (h:A) t) f = f h + list_sum t f`, REWRITE_TAC[list_sum; ITLIST]);; |
| 60 |
|
| 61 |
|
| 62 |
let list_sum_conv f_conv tm = |
| 63 |
let ltm, f_tm = dest_comb tm in |
| 64 |
let list_tm = rand ltm in |
| 65 |
let list_ty = type_of list_tm in |
| 66 |
let f_ty = type_of f_tm in |
| 67 |
let ty = (hd o snd o dest_type) list_ty in |
| 68 |
let f_var = mk_var("f", f_ty) and |
| 69 |
h_var = mk_var("h", ty) and |
| 70 |
t_var = mk_var("t", list_ty) in |
| 71 |
let inst_t = INST[f_tm, f_var] o INST_TYPE[ty, aty] in |
| 72 |
let list_sum_h = inst_t LIST_SUM_A_H and |
| 73 |
list_sum_cons = inst_t LIST_SUM_A_CONS in |
| 74 |
|
| 75 |
let rec list_sum_conv_raw = fun h_tm t_tm -> |
| 76 |
if (is_comb t_tm) then |
| 77 |
let h_tm', t_tm' = dest_comb t_tm in |
| 78 |
let th0 = INST[h_tm, h_var; t_tm, t_var] list_sum_cons in |
| 79 |
let ltm, rtm = dest_comb(rand(concl th0)) in |
| 80 |
let plus_op, fh_tm = dest_comb ltm in |
| 81 |
let f_th = f_conv fh_tm in |
| 82 |
let th1 = list_sum_conv_raw (rand h_tm') t_tm' in |
| 83 |
let th2 = MK_COMB(AP_TERM plus_op f_th, th1) in |
| 84 |
TRANS th0 th2 |
| 85 |
else |
| 86 |
let th0 = INST[h_tm, h_var] list_sum_h in |
| 87 |
let f_th = f_conv (rand(concl th0)) in |
| 88 |
TRANS th0 f_th in |
| 89 |
|
| 90 |
if (is_comb list_tm) then |
| 91 |
let h_tm, t_tm = dest_comb list_tm in |
| 92 |
list_sum_conv_raw (rand h_tm) t_tm |
| 93 |
else |
| 94 |
inst_t LIST_SUM_A_EMPTY;; |
| 95 |
|
| 96 |
|
| 97 |
|
| 98 |
(*************************************) |
| 99 |
(* list_sum2 evaluation *) |
| 100 |
|
| 101 |
let LIST_SUM2_0_LE' = (MY_RULE_FLOAT o prove)(`list_sum2 (f:A->B->real) [] [] <= &0`, |
| 102 |
REWRITE_TAC[list_sum2; ITLIST2; REAL_LE_REFL]);; |
| 103 |
let LIST_SUM2_1_LE' = (MY_RULE_FLOAT o prove)(`f h1 h2 <= x ==> list_sum2 (f:A->B->real) [h1] [h2] <= x`, |
| 104 |
REWRITE_TAC[list_sum2; ITLIST2; REAL_ADD_RID]);; |
| 105 |
let LIST_SUM2_LE' = (MY_RULE_FLOAT o prove)(`f h1 h2 <= x /\ list_sum2 f t1 t2 <= y /\ x + y <= z ==> |
| 106 |
list_sum2 (f:A->B->real) (CONS h1 t1) (CONS h2 t2) <= z`, |
| 107 |
REWRITE_TAC[list_sum2; ITLIST2] THEN STRIP_TAC THEN |
| 108 |
MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `x + y:real` THEN |
| 109 |
ASM_SIMP_TAC[REAL_LE_ADD2]);; |
| 110 |
|
| 111 |
|
| 112 |
let list_sum2_le_conv pp f_le_conv tm = |
| 113 |
let ltm, list2_tm = dest_comb tm in |
| 114 |
let ltm2, list1_tm = dest_comb ltm in |
| 115 |
let f_tm = rand ltm2 in |
| 116 |
let list1_ty = type_of list1_tm and |
| 117 |
list2_ty = type_of list2_tm and |
| 118 |
f_ty = type_of f_tm in |
| 119 |
let ty1 = (hd o snd o dest_type) list1_ty and |
| 120 |
ty2 = (hd o snd o dest_type) list2_ty in |
| 121 |
let f_var = mk_var ("f", f_ty) and |
| 122 |
h1_var, t1_var = mk_var ("h1", ty1), mk_var ("t1", list1_ty) and |
| 123 |
h2_var, t2_var = mk_var ("h2", ty2), mk_var ("t2", list2_ty) in |
| 124 |
let inst_t = INST[f_tm, f_var] o INST_TYPE[ty1, aty; ty2, bty] in |
| 125 |
let list2_0, list2_1, list2_le = inst_t LIST_SUM2_0_LE', inst_t LIST_SUM2_1_LE', inst_t LIST_SUM2_LE' in |
| 126 |
|
| 127 |
let rec rec_conv = fun list1_tm list2_tm -> |
| 128 |
if (is_comb list1_tm) then |
| 129 |
let h1_tm, t1_tm = dest_cons list1_tm and |
| 130 |
h2_tm, t2_tm = dest_cons list2_tm in |
| 131 |
let f_le_th = f_le_conv pp h1_tm h2_tm in |
| 132 |
let x_tm = (rand o concl) f_le_th in |
| 133 |
let inst0 = INST[h1_tm, h1_var; h2_tm, h2_var; x_tm, x_var_real] in |
| 134 |
if is_comb t1_tm then |
| 135 |
let sum2_t_th = rec_conv t1_tm t2_tm in |
| 136 |
let y_tm = (rand o concl) sum2_t_th in |
| 137 |
let xy_th = float_add_hi pp x_tm y_tm in |
| 138 |
let z_tm = (rand o concl) xy_th in |
| 139 |
(MY_PROVE_HYP xy_th o MY_PROVE_HYP sum2_t_th o MY_PROVE_HYP f_le_th o |
| 140 |
INST[y_tm, y_var_real; z_tm, z_var_real; t1_tm, t1_var; t2_tm, t2_var] o |
| 141 |
inst0) list2_le |
| 142 |
else |
| 143 |
if is_comb t2_tm then failwith ("sum2_le_conv: t1 = []; t2 = "^string_of_term t2_tm) else |
| 144 |
(MY_PROVE_HYP f_le_th o inst0) list2_1 |
| 145 |
else |
| 146 |
if is_comb list2_tm then failwith ("sum2_le_conv: list1 = []; list2 = "^string_of_term list2_tm) else |
| 147 |
list2_0 in |
| 148 |
|
| 149 |
rec_conv list1_tm list2_tm;; |
| 150 |
|
| 151 |
|
| 152 |
|
| 153 |
(**************************) |
| 154 |
(* \a b c. a * iabs b + c *) |
| 155 |
|
| 156 |
let ERROR_MUL_F2' = (SYM o MY_RULE_FLOAT) error_mul_f2;; |
| 157 |
|
| 158 |
|
| 159 |
(* |- x = a, |- P x y -> P a y *) |
| 160 |
let rewrite_lhs eq_th th = |
| 161 |
let ltm, rhs = dest_comb (concl th) in |
| 162 |
let th0 = AP_THM (AP_TERM (rator ltm) eq_th) rhs in |
| 163 |
EQ_MP th0 th;; |
| 164 |
|
| 165 |
let error_mul_f2_le_conv pp tm1 tm2 = |
| 166 |
let eq_th = INST[tm1, a_var_real; tm2, int_var] ERROR_MUL_F2' in |
| 167 |
let iabs_th = float_iabs tm2 in |
| 168 |
let iabs_tm = (rand o concl) iabs_th in |
| 169 |
let mul_th = float_mul_hi pp tm1 iabs_tm in |
| 170 |
let th0 = AP_TERM (mk_comb (mul_op_real, tm1)) iabs_th in |
| 171 |
let th1 = AP_THM (AP_TERM le_op_real th0) (rand (concl mul_th)) in |
| 172 |
let le_th = EQ_MP (SYM th1) mul_th in |
| 173 |
rewrite_lhs eq_th le_th;; |
| 174 |
|
| 175 |
let ERROR_MUL_F2_LEMMA' = (MY_RULE_FLOAT o prove)(`iabs int = x /\ a * x <= y ==> error_mul_f2 a int <= y`, |
| 176 |
REWRITE_TAC[error_mul_f2] THEN STRIP_TAC THEN ASM_REWRITE_TAC[]);; |
| 177 |
|
| 178 |
let error_mul_f2_le_conv2 pp tm1 tm2 = |
| 179 |
let iabs_th = float_iabs tm2 in |
| 180 |
let x_tm = (rand o concl) iabs_th in |
| 181 |
let mul_th = float_mul_hi pp tm1 x_tm in |
| 182 |
let y_tm = (rand o concl) mul_th in |
| 183 |
(MY_PROVE_HYP iabs_th o MY_PROVE_HYP mul_th o |
| 184 |
INST[tm2, int_var; tm1, a_var_real; x_tm, x_var_real; y_tm, y_var_real]) ERROR_MUL_F2_LEMMA';; |
| 185 |
|
| 186 |
|
| 187 |
|
| 188 |
(**************************) |
| 189 |
(* \a b c. a * iabs b + c *) |
| 190 |
|
| 191 |
let ERROR_MUL_F1_LEMMA' = (MY_RULE_FLOAT o prove)(`x * list_sum2 error_mul_f2 w list <= z ==> |
| 192 |
error_mul_f1 w x list <= z`, REWRITE_TAC[error_mul_f1]);; |
| 193 |
|
| 194 |
let list_sum2_error2_const = `list_sum2 error_mul_f2` and |
| 195 |
w_var_list = `w:(real)list` and |
| 196 |
list_var = `list:(real#real)list`;; |
| 197 |
|
| 198 |
let error_mul_f1_le_conv w_tm pp x_tm list_tm = |
| 199 |
(* TODO: if x = 0 then do not need to compute the sum *) |
| 200 |
let sum2_tm = mk_binop list_sum2_error2_const w_tm list_tm in |
| 201 |
let sum2_le_th = list_sum2_le_conv pp error_mul_f2_le_conv2 sum2_tm in |
| 202 |
let ineq_th = mul_ineq_pos_const_hi pp x_tm sum2_le_th in |
| 203 |
let z_tm = (rand o concl) ineq_th in |
| 204 |
(MY_PROVE_HYP ineq_th o |
| 205 |
INST[x_tm, x_var_real; z_tm, z_var_real; w_tm, w_var_list; list_tm, list_var]) ERROR_MUL_F1_LEMMA';; |
| 206 |
|
| 207 |
|
| 208 |
end;; |