Debian Codegraph @

Formal_ineqs/list/list_float.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 (* 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;;