Debian Codegraph @

Formal_ineqs/verifier/m_verifier.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 (* Formal verification functions *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/taylor/m_taylor.hl";;
14 needs "Formal_ineqs/verifier/certificate.hl";;
15 needs "Formal_ineqs/misc/misc_vars.hl";;
16 needs "Formal_ineqs/verifier_options.hl";;
17 needs "Formal_ineqs/verifier/m_verifier_build.hl";;
18
19 module M_verifier = struct
20
21 open Ssreflect;;
22 open Ssrfun;;
23 open Ssrbool;;
24 open Ssrnat;;
25 open Interval_arith;;
26 open Taylor_interval;;
27 open Multivariate_taylor;;
28 open Misc_functions;;
29 open Arith_float;;
30 open M_taylor;;
31 open Misc_vars;;
32 open Verifier_options;;
33 open M_verifier_build;;
34 open Certificate;;
35
36
37 let mk_real_vars n name = map (fun i -> mk_var (sprintf "%s%d" name i, real_ty)) (1--n);;
38
39 (*************************************)
40
41 let BOUNDED_INTERVAL_ARITH_IMP_HI' = (MY_RULE o prove)
42 (`(!x. x IN interval [domain] ==> interval_arith (f x) (lo, hi)) ==>
43 (!x. x IN interval [domain] ==> f x <= hi)`, SIMP_TAC[interval_arith]);;
44
45 let BOUNDED_INTERVAL_ARITH_IMP_LO' = (MY_RULE o prove)
46 (`(!x. x IN interval [domain] ==> interval_arith (f x) (lo, hi)) ==>
47 (!x. x IN interval [domain] ==> lo <= f x)`, SIMP_TAC[interval_arith]);;
48
49
50 let eval_interval_arith_hi n bound_th =
51 let tm0 = (snd o dest_forall o concl) bound_th in
52 let int_tm, concl_tm = dest_comb tm0 in
53 let domain_tm = (rand o rator o rand o rand o rand) int_tm in
54 let ltm, bounds_tm = dest_interval_arith concl_tm in
55 let f_tm, (lo_tm, hi_tm) = rator ltm, dest_pair bounds_tm in
56 let f_var = mk_var ("f", type_of f_tm) and
57 domain_var = mk_var ("domain", type_of domain_tm) in
58 (MY_PROVE_HYP bound_th o
59 INST[f_tm, f_var; domain_tm, domain_var; hi_tm, hi_var_real; lo_tm, lo_var_real] o
60 inst_first_type_var n_type_array.(n)) BOUNDED_INTERVAL_ARITH_IMP_HI';;
61
62
63 let eval_interval_arith_lo n bound_th =
64 let tm0 = (snd o dest_forall o concl) bound_th in
65 let int_tm, concl_tm = dest_comb tm0 in
66 let domain_tm = (rand o rator o rand o rand o rand) int_tm in
67 let ltm, bounds_tm = dest_interval_arith concl_tm in
68 let f_tm, (lo_tm, hi_tm) = rator ltm, dest_pair bounds_tm in
69 let f_var = mk_var ("f", type_of f_tm) and
70 domain_var = mk_var ("domain", type_of domain_tm) in
71 (MY_PROVE_HYP bound_th o
72 INST[f_tm, f_var; domain_tm, domain_var; hi_tm, hi_var_real; lo_tm, lo_var_real] o
73 inst_first_type_var n_type_array.(n)) BOUNDED_INTERVAL_ARITH_IMP_LO';;
74
75
76
77 (*************************************)
78 (* subdomains *)
79
80 let eval_subset_trans =
81 let SUBSET_TRANS' = MY_RULE SUBSET_TRANS in
82 fun st_th tu_th ->
83 let ltm, t_tm = dest_comb (concl st_th) in
84 let s_tm = rand ltm and
85 u_tm = rand (concl tu_th) in
86 let ty = (hd o snd o dest_type o type_of) s_tm and
87 s_var = mk_var ("s", type_of s_tm) and
88 t_var = mk_var ("t", type_of t_tm) and
89 u_var = mk_var ("u", type_of u_tm) in
90 (MY_PROVE_HYP st_th o MY_PROVE_HYP tu_th o
91 INST[s_tm, s_var; t_tm, t_var; u_tm, u_var] o inst_first_type_var ty) SUBSET_TRANS';;
92
93 let eval_subset_refl =
94 let SUBSET_REFL' = MY_RULE SUBSET_REFL in
95 fun s_tm ->
96 let ty = (hd o snd o dest_type o type_of) s_tm and
97 s_var = mk_var ("s", type_of s_tm) in
98 (INST[s_tm, s_var] o inst_first_type_var ty) SUBSET_REFL';;
99
100
101
102 let SUBSET_INTERVAL_IMP = prove(`!a b c d. (!i. i IN 1..dimindex (:N) ==> a$i <= c$i /\ d$i <= b$i) ==>
103 interval [c:real^N,d] SUBSET interval [a,b]`,
104 SIMP_TAC[SUBSET_INTERVAL; GSYM IN_NUMSEG]);;
105
106
107 let gen_subset_interval_lemma n =
108 let a_vars = mk_real_vars n "a" and
109 b_vars = mk_real_vars n "b" and
110 c_vars = mk_real_vars n "c" and
111 d_vars = mk_real_vars n "d" in
112
113 let a_tm = mk_vector_list a_vars and
114 b_tm = mk_vector_list b_vars and
115 c_tm = mk_vector_list c_vars and
116 d_tm = mk_vector_list d_vars in
117
118 let th0 = (SPEC_ALL o ISPECL [a_tm; b_tm; c_tm; d_tm]) SUBSET_INTERVAL_IMP in
119 let th1 = REWRITE_RULE[dimindex_array.(n); IN_NUMSEG; gen_in_interval n; ARITH] th0 in
120 let th2 = REWRITE_RULE (Array.to_list comp_thms_array.(n)) th1 in
121 MY_RULE th2;;
122
123
124 let subset_interval_thms_array = Array.init (max_dim + 1)
125 (fun n -> if n < 1 then TRUTH else gen_subset_interval_lemma n);;
126
127
128
129 let m_subset_interval n a_tm b_tm c_tm d_tm =
130 let a_vars = mk_real_vars n "a" and
131 b_vars = mk_real_vars n "b" and
132 c_vars = mk_real_vars n "c" and
133 d_vars = mk_real_vars n "d" in
134
135 let a_s = dest_vector a_tm and
136 b_s = dest_vector b_tm and
137 c_s = dest_vector c_tm and
138 d_s = dest_vector d_tm in
139
140 let th0 = (INST (zip a_s a_vars) o INST (zip b_s b_vars) o
141 INST (zip c_s c_vars) o INST (zip d_s d_vars)) subset_interval_thms_array.(n) in
142 let prove_le tm =
143 let ltm, rtm = dest_binop le_op_real tm in
144 EQT_ELIM (float_le ltm rtm) in
145 let hyp_ths = map prove_le (hyp th0) in
146 itlist (fun hyp_th th -> MY_PROVE_HYP hyp_th th) hyp_ths th0;;
147
148
149 (*************************************)
150
151 let M_RESTRICT_RIGHT_LEMMA = prove(`!j x z y w u y' w'. m_cell_domain (x:real^N,z) y w /\
152 (!i. i IN 1..dimindex (:N) ==> ~(i = j) ==>
153 u$i = x$i /\ y'$i = y$i /\ w'$i = w$i) /\
154 u$j = z$j /\ y'$j = z$j /\ w'$j = &0 ==>
155 m_cell_domain (u,z) y' w' /\ interval [u,z] SUBSET interval [x,z]`,
156 REWRITE_TAC[m_cell_domain; SUBSET_INTERVAL; GSYM IN_NUMSEG] THEN REPEAT GEN_TAC THEN STRIP_TAC THEN
157 CONJ_TAC THENL
158 [
159 GEN_TAC THEN DISCH_TAC THEN
160 ASM_CASES_TAC `i = j:num` THENL
161 [
162 ASM_REWRITE_TAC[REAL_LE_REFL; REAL_SUB_REFL; real_max];
163 ALL_TAC
164 ] THEN
165 REPEAT (FIRST_ASSUM (new_rewrite [] []) THEN ASM_REWRITE_TAC[]);
166 ALL_TAC
167 ] THEN
168 DISCH_TAC THEN GEN_TAC THEN DISCH_TAC THEN
169 ASM_CASES_TAC `i = j:num` THENL
170 [
171 ASM_REWRITE_TAC[REAL_LE_REFL] THEN
172 REPEAT (FIRST_X_ASSUM (MP_TAC o SPEC `j:num`)) THEN
173 POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN
174 ASM_REWRITE_TAC[] THEN REAL_ARITH_TAC;
175 ALL_TAC
176 ] THEN
177 REPEAT (FIRST_ASSUM (new_rewrite [] [])) THEN ASM_REWRITE_TAC[REAL_LE_REFL]);;
178
179
180
181 let M_RESTRICT_LEFT_LEMMA = prove(`!j x z y w u y' w'. m_cell_domain (x:real^N,z) y w /\
182 (!i. i IN 1..dimindex (:N) ==> ~(i = j) ==>
183 u$i = z$i /\ y'$i = y$i /\ w'$i = w$i) /\
184 u$j = x$j /\ y'$j = x$j /\ w'$j = &0 ==>
185 m_cell_domain (x,u) y' w' /\ interval [x,u] SUBSET interval [x,z]`,
186 REWRITE_TAC[m_cell_domain; SUBSET_INTERVAL; GSYM IN_NUMSEG] THEN REPEAT GEN_TAC THEN STRIP_TAC THEN
187 CONJ_TAC THENL
188 [
189 GEN_TAC THEN DISCH_TAC THEN
190 ASM_CASES_TAC `i = j:num` THENL
191 [
192 ASM_REWRITE_TAC[REAL_LE_REFL; REAL_SUB_REFL; real_max];
193 ALL_TAC
194 ] THEN
195 REPEAT (FIRST_ASSUM (new_rewrite [] []) THEN ASM_REWRITE_TAC[]);
196 ALL_TAC
197 ] THEN
198 DISCH_TAC THEN GEN_TAC THEN DISCH_TAC THEN
199 ASM_CASES_TAC `i = j:num` THENL
200 [
201 ASM_REWRITE_TAC[REAL_LE_REFL] THEN
202 REPEAT (FIRST_X_ASSUM (MP_TAC o SPEC `j:num`)) THEN
203 POP_ASSUM (fun th -> REWRITE_TAC[SYM th]) THEN
204 ASM_REWRITE_TAC[] THEN REAL_ARITH_TAC;
205 ALL_TAC
206 ] THEN
207 REPEAT (FIRST_ASSUM (new_rewrite [] [])) THEN ASM_REWRITE_TAC[REAL_LE_REFL]);;
208
209
210 let gen_restrict_lemma n j left_flag =
211 let xs = mk_real_vars n "x" and
212 zs = mk_real_vars n "z" and
213 ys = mk_real_vars n "y" and
214 ws = mk_real_vars n "w" and
215 j_tm = mk_small_numeral j in
216 let a, b = if left_flag then zs, xs else xs, zs in
217 let x_tm = mk_vector_list xs and
218 z_tm = mk_vector_list zs and
219 y_tm = mk_vector_list ys and
220 w_tm = mk_vector_list ws and
221 u_tm = mk_vector_list (map (fun i -> List.nth (if i = j then b else a) (i - 1)) (1--n)) and
222 y'_tm = mk_vector_list (map (fun i -> List.nth (if i = j then b else ys) (i - 1)) (1--n)) and
223 w'_tm = mk_vector_list (map (fun i -> if i = j then `&0` else List.nth ws (i - 1)) (1--n)) in
224
225 let th0 = (SPEC_ALL o ISPECL [j_tm; x_tm; z_tm; y_tm; w_tm; u_tm; y'_tm; w'_tm])
226 (if left_flag then M_RESTRICT_LEFT_LEMMA else M_RESTRICT_RIGHT_LEMMA) in
227 let th1 = REWRITE_RULE[dimindex_array.(n); IN_NUMSEG; gen_in_interval n; ARITH] th0 in
228 let th2 = REWRITE_RULE (Array.to_list comp_thms_array.(n)) th1 in
229 MY_RULE_FLOAT th2;;
230
231
232 let left_restrict_thms_array = Array.init (max_dim + 1)
233 (fun n -> Array.init (n + 1)
234 (fun j -> if j < 1 then TRUTH else gen_restrict_lemma n j true));;
235
236
237 let right_restrict_thms_array = Array.init (max_dim + 1)
238 (fun n -> Array.init (n + 1)
239 (fun j -> if j < 1 then TRUTH else gen_restrict_lemma n j false));;
240
241
242
243
244 (******************************)
245 (* m_cell_pass *)
246
247 let m_cell_pass = new_definition `m_cell_pass f domain <=> (!x. x IN interval [domain] ==> f x < &0)`;;
248
249 let m_cell_list_pass = new_definition `m_cell_list_pass fs domain <=>
250 (!x:real^N. x IN interval [domain] ==> ITLIST (\f r. f x < &0 \/ r) fs F)`;;
251
252 let dest_m_cell_pass pass_tm =
253 let ltm, domain = dest_comb pass_tm in
254 rand ltm, domain;;
255
256 let dest_m_cell_list_pass pass_tm =
257 let ltm, domain = dest_comb pass_tm in
258 dest_list (rand ltm), domain;;
259
260
261 (*********************************)
262
263 let M_CELL_PASS_EQ_LIST_PASS1 = prove(`m_cell_pass f domain <=> m_cell_list_pass [f] domain`,
264 REWRITE_TAC[m_cell_pass; m_cell_list_pass; ITLIST]);;
265
266 let M_CELL_PASS_IMP_LIST_PASS1 = prove(`m_cell_pass f domain ==> m_cell_list_pass [f] domain`,
267 REWRITE_TAC[M_CELL_PASS_EQ_LIST_PASS1]);;
268
269 let M_CELL_PASS_LEMMA = prove(`(!x. x IN interval [domain] ==> f x <= hi) /\ (hi < &0 <=> T) ==>
270 m_cell_pass f domain`,
271 REWRITE_TAC[m_cell_pass] THEN REPEAT STRIP_TAC THEN
272 MATCH_MP_TAC REAL_LET_TRANS THEN
273 EXISTS_TAC `hi:real` THEN ASM_REWRITE_TAC[] THEN
274 FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);;
275
276 let M_CELL_LIST_PASS1_LEMMA = prove(`(!x. x IN interval [domain] ==> f x <= hi) /\ (hi < &0 <=> T) ==>
277 m_cell_list_pass [f] domain`,
278 DISCH_THEN (MP_TAC o MATCH_MP M_CELL_PASS_LEMMA) THEN
279 REWRITE_TAC[M_CELL_PASS_EQ_LIST_PASS1]);;
280
281
282 let M_CELL_PASS_LEMMA' = MY_RULE M_CELL_PASS_LEMMA and
283 M_CELL_LIST_PASS1_LEMMA' = MY_RULE M_CELL_LIST_PASS1_LEMMA;;
284
285 let M_CELL_PASS_INTERVAL_LEMMA' = (MY_RULE o prove)
286 (`(!x. x IN interval [domain] ==> interval_arith (f x) (lo, hi)) /\ hi < &0 ==> m_cell_pass f domain`,
287 REWRITE_TAC[interval_arith] THEN STRIP_TAC THEN MATCH_MP_TAC M_CELL_PASS_LEMMA THEN
288 ASM_SIMP_TAC[]);;
289
290 let M_CELL_LIST_PASS1_INTERVAL_LEMMA' = (MY_RULE o prove)
291 (`(!x. x IN interval [domain] ==> interval_arith (f x) (lo, hi)) /\ hi < &0 ==> m_cell_list_pass [f] domain`,
292 REWRITE_TAC[interval_arith] THEN STRIP_TAC THEN MATCH_MP_TAC M_CELL_LIST_PASS1_LEMMA THEN
293 ASM_SIMP_TAC[]);;
294
295
296 (* m_cell_pass with taylor_interval *)
297 let m_taylor_cell_pass n pp m_taylor_th =
298 let upper_th = eval_m_taylor_upper_bound n pp m_taylor_th in
299 let tm0 = (snd o dest_forall o concl) upper_th in
300 let int_tm, concl_tm = dest_comb tm0 in
301 let domain_tm = (rand o rator o rand o rand o rand) int_tm in
302 let ltm, hi_tm = dest_comb concl_tm in
303 let f_tm = (rator o rand) ltm in
304 let f_var = mk_var ("f", type_of f_tm) and
305 domain_var = mk_var ("domain", type_of domain_tm) in
306
307 let hi_lt0_th = float_lt0 hi_tm in
308 if (fst o dest_const o rand o concl) hi_lt0_th = "F" then
309 failwith "m_taylor_cell_pass: hi < &0 <=> F"
310 else
311 (MY_PROVE_HYP upper_th o MY_PROVE_HYP hi_lt0_th o
312 INST[f_tm, f_var; domain_tm, domain_var; hi_tm, hi_var_real] o
313 inst_first_type_var n_type_array.(n)) M_CELL_PASS_LEMMA';;
314
315 let m_taylor_cell_list_pass n pp m_taylor_th =
316 let upper_th = eval_m_taylor_upper_bound n pp m_taylor_th in
317 let tm0 = (snd o dest_forall o concl) upper_th in
318 let int_tm, concl_tm = dest_comb tm0 in
319 let domain_tm = (rand o rator o rand o rand o rand) int_tm in
320 let ltm, hi_tm = dest_comb concl_tm in
321 let f_tm = (rator o rand) ltm in
322 let f_var = mk_var ("f", type_of f_tm) and
323 domain_var = mk_var ("domain", type_of domain_tm) in
324
325 let hi_lt0_th = float_lt0 hi_tm in
326 if (fst o dest_const o rand o concl) hi_lt0_th = "F" then
327 failwith "m_taylor_cell_list_pass: hi < &0 <=> F"
328 else
329 (MY_PROVE_HYP upper_th o MY_PROVE_HYP hi_lt0_th o
330 INST[f_tm, f_var; domain_tm, domain_var; hi_tm, hi_var_real] o
331 inst_first_type_var n_type_array.(n)) M_CELL_LIST_PASS1_LEMMA';;
332
333
334 (* m_cell_pass with a raw interval *)
335 let m_taylor_cell_pass0 n bound_th =
336 let tm0 = (snd o dest_forall o concl) bound_th in
337 let int_tm, concl_tm = dest_comb tm0 in
338 let domain_tm = (rand o rator o rand o rand o rand) int_tm in
339 let ltm, bounds_tm = dest_interval_arith concl_tm in
340 let f_tm, (lo_tm, hi_tm) = rator ltm, dest_pair bounds_tm in
341 let f_var = mk_var ("f", type_of f_tm) and
342 domain_var = mk_var ("domain", type_of domain_tm) in
343 let hi_lt0_th = try EQT_ELIM (float_lt0 hi_tm) with Failure _ -> failwith "m_taylor_cell_pass0" in
344 (MY_PROVE_HYP bound_th o MY_PROVE_HYP hi_lt0_th o
345 INST[f_tm, f_var; domain_tm, domain_var; hi_tm, hi_var_real; lo_tm, lo_var_real] o
346 inst_first_type_var n_type_array.(n)) M_CELL_PASS_INTERVAL_LEMMA';;
347
348 let m_taylor_cell_list_pass0 n bound_th =
349 let tm0 = (snd o dest_forall o concl) bound_th in
350 let int_tm, concl_tm = dest_comb tm0 in
351 let domain_tm = (rand o rator o rand o rand o rand) int_tm in
352 let ltm, bounds_tm = dest_interval_arith concl_tm in
353 let f_tm, (lo_tm, hi_tm) = rator ltm, dest_pair bounds_tm in
354 let f_var = mk_var ("f", type_of f_tm) and
355 domain_var = mk_var ("domain", type_of domain_tm) in
356 let hi_lt0_th = try EQT_ELIM (float_lt0 hi_tm) with Failure _ -> failwith "m_taylor_cell_list_pass0" in
357 (MY_PROVE_HYP bound_th o MY_PROVE_HYP hi_lt0_th o
358 INST[f_tm, f_var; domain_tm, domain_var; hi_tm, hi_var_real; lo_tm, lo_var_real] o
359 inst_first_type_var n_type_array.(n)) M_CELL_LIST_PASS1_INTERVAL_LEMMA';;
360
361
362
363 (**********************)
364
365 let M_CELL_PASS_SUBDOMAIN' = (MY_RULE o prove)(`interval [domain2] SUBSET interval [domain] /\
366 m_cell_pass f domain ==> m_cell_pass f domain2`,
367 REWRITE_TAC[m_cell_pass; SUBSET] THEN REPEAT STRIP_TAC THEN ASM_SIMP_TAC[]);;
368
369 let M_CELL_LIST_PASS_SUBDOMAIN' = (MY_RULE o prove)(`interval [domain2] SUBSET interval [domain] /\
370 m_cell_list_pass fs domain ==> m_cell_list_pass fs domain2`,
371 REWRITE_TAC[m_cell_list_pass; SUBSET] THEN REPEAT STRIP_TAC THEN ASM_SIMP_TAC[]);;
372
373
374 let m_cell_pass_subdomain domain2_tm pass_th =
375 let f_tm, domain_tm = dest_m_cell_pass (concl pass_th) in
376 let f_var = mk_var ("f", type_of f_tm) and
377 domain_var = mk_var ("domain", type_of domain_tm) and
378 domain2_var = mk_var ("domain2", type_of domain2_tm) in
379 let a, b = dest_pair domain_tm and
380 c, d = dest_pair domain2_tm in
381 let n = get_dim a in
382 let sub_th = m_subset_interval n a b c d in
383 (MY_PROVE_HYP sub_th o MY_PROVE_HYP pass_th o
384 INST[domain_tm, domain_var; domain2_tm, domain2_var; f_tm, f_var] o
385 inst_first_type_var n_type_array.(n)) M_CELL_PASS_SUBDOMAIN';;
386
387
388 let m_cell_list_pass_subdomain domain2_tm pass_th =
389 let fs_tm, domain_tm = dest_m_cell_pass (concl pass_th) in
390 let fs_var = mk_var ("fs", type_of fs_tm) and
391 domain_var = mk_var ("domain", type_of domain_tm) and
392 domain2_var = mk_var ("domain2", type_of domain2_tm) in
393 let a, b = dest_pair domain_tm and
394 c, d = dest_pair domain2_tm in
395 let n = get_dim a in
396 let sub_th = m_subset_interval n a b c d in
397 (MY_PROVE_HYP sub_th o MY_PROVE_HYP pass_th o
398 INST[domain_tm, domain_var; domain2_tm, domain2_var; fs_tm, fs_var] o
399 inst_first_type_var n_type_array.(n)) M_CELL_LIST_PASS_SUBDOMAIN';;
400
401
402
403
404
405 (******************************)
406
407 let GLUE_LEMMA = prove(`!j x z v u P Q.
408 (!i. 1 <= i /\ i <= dimindex (:N) ==> ~(i = j) ==>
409 u$i = x$i /\ v$i = z$i) ==>
410 v$j = u$j ==>
411 (!p. p IN interval [x,v] ==> P p) ==>
412 (!p. p IN interval [u,z] ==> Q p) ==>
413 (!p. p IN interval [x,z:real^N] ==> P p \/ Q p)`,
414 REWRITE_TAC[IN_INTERVAL] THEN REPEAT GEN_TAC THEN
415 move ["eq1"; "eq_vu"; "cell1"; "cell2"; "y"; "ineq"] THEN
416 ASM_CASES_TAC `(y:real^N)$j <= (v:real^N)$j` THENL
417 [
418 DISJ1_TAC THEN REMOVE_THEN "cell1" MATCH_MP_TAC THEN GEN_TAC THEN DISCH_TAC THEN
419 USE_THEN "ineq" (new_rewrite [] []) THEN ASM_REWRITE_TAC[] THEN
420 ASM_CASES_TAC `i = j:num` THENL
421 [
422 REPLICATE_TAC 3 (POP_ASSUM MP_TAC) THEN SIMP_TAC[];
423 ALL_TAC
424 ] THEN
425 USE_THEN "eq1" (new_rewrite [] []) THEN ASM_REWRITE_TAC[] THEN
426 USE_THEN "ineq" (new_rewrite [] []) THEN ASM_REWRITE_TAC[];
427 ALL_TAC
428 ] THEN
429
430 POP_ASSUM (ASSUME_TAC o MATCH_MP (REAL_ARITH `~(a <= b) ==> b <= a:real`)) THEN
431 DISJ2_TAC THEN REMOVE_THEN "cell2" MATCH_MP_TAC THEN GEN_TAC THEN DISCH_TAC THEN
432 USE_THEN "ineq" (new_rewrite [] []) THEN ASM_REWRITE_TAC[] THEN
433 ASM_CASES_TAC `i = j:num` THENL
434 [
435 ASM_REWRITE_TAC[] THEN USE_THEN "eq_vu" (fun th -> REWRITE_TAC[SYM th]) THEN
436 REPLICATE_TAC 3 (POP_ASSUM MP_TAC) THEN SIMP_TAC[];
437 ALL_TAC
438 ] THEN
439 USE_THEN "eq1" (new_rewrite [] []) THEN ASM_REWRITE_TAC[] THEN
440 USE_THEN "ineq" (new_rewrite [] []) THEN ASM_REWRITE_TAC[]);;
441
442 let M_CELL_PASS_GLUE_LEMMA = prove(`!j x z v u f.
443 (!i. 1 <= i /\ i <= dimindex (:N) ==> ~(i = j) ==>
444 u$i = x$i /\ v$i = z$i) ==>
445 v$j = u$j ==>
446 m_cell_pass f (x,v) ==>
447 m_cell_pass f (u,z) ==>
448 m_cell_pass f (x,z:real^N)`,
449 REPEAT GEN_TAC THEN REWRITE_TAC[m_cell_pass] THEN
450 DISCH_THEN (MP_TAC o MATCH_MP GLUE_LEMMA) THEN
451 DISCH_THEN (MP_TAC o SPECL [`\x:real^N. f x < &0`; `\x:real^N. f x < &0`]) THEN
452 REWRITE_TAC[]);;
453
454 let ITLIST_DISJ_APPEND = prove(`!P l1 l2. ITLIST (\a r. P a \/ r) (APPEND l1 l2) F
455 <=> ITLIST (\a r. P a \/ r) l1 F \/ ITLIST (\a r. P a \/ r) l2 F`,
456 GEN_TAC THEN LIST_INDUCT_TAC THEN LIST_INDUCT_TAC THEN REWRITE_TAC[APPEND; ITLIST; APPEND_NIL] THEN
457 ASM_REWRITE_TAC[ITLIST; DISJ_ACI]);;
458
459 let M_CELL_LIST_PASS_GLUE_LEMMA = prove(`!j x z v u fs1 fs2.
460 (!i. 1 <= i /\ i <= dimindex (:N) ==> ~(i = j) ==>
461 u$i = x$i /\ v$i = z$i) ==>
462 v$j = u$j ==>
463 m_cell_list_pass fs1 (x,v) ==>
464 m_cell_list_pass fs2 (u,z) ==>
465 m_cell_list_pass (APPEND fs1 fs2) (x,z:real^N)`,
466 REPEAT GEN_TAC THEN REWRITE_TAC[m_cell_list_pass; ITLIST_DISJ_APPEND] THEN
467 apply_tac GLUE_LEMMA);;
468
469
470 let gen_glue_lemma n j =
471 let mk_vars name = map (fun i -> mk_var (sprintf "%s%d" name i, real_ty)) (1--n) in
472 let xs = mk_vars "x" and
473 zs = mk_vars "z" and
474 t_var = mk_var ("t", real_ty) and
475 j_tm = mk_small_numeral j in
476 let x_tm = mk_vector_list xs and
477 z_tm = mk_vector_list zs and
478 v_tm = mk_vector_list (map (fun i -> if i = j then t_var else List.nth zs (i - 1)) (1--n)) and
479 u_tm = mk_vector_list (map (fun i -> if i = j then t_var else List.nth xs (i - 1)) (1--n)) in
480 let gen_th lemma =
481 let th0 = (SPEC_ALL o ISPECL [j_tm; x_tm; z_tm; v_tm; u_tm]) lemma in
482 let th1 = REWRITE_RULE[dimindex_array.(n); gen_in_interval n; ARITH] th0 in
483 let th2 = REWRITE_RULE (Array.to_list comp_thms_array.(n)) th1 in
484 MY_RULE th2 in
485 gen_th M_CELL_PASS_GLUE_LEMMA, gen_th M_CELL_LIST_PASS_GLUE_LEMMA;;
486
487
488 let glue_thms_array = Array.init (max_dim + 1)
489 (fun n -> Array.init (n + 1)
490 (fun j -> if j < 1 then TRUTH, TRUTH else gen_glue_lemma n j));;
491
492
493 (***************************************)
494 (* m_cell_list_pass reduction *)
495
496 let CELL_LIST_PASS_ACC_INTRO = prove(`m_cell_list_pass fs1 domain <=> m_cell_list_pass (APPEND fs1 []) domain`,
497 REWRITE_TAC[APPEND_NIL]);;
498
499 let CELL_LIST_PASS_ACC_ELIM = SYM CELL_LIST_PASS_ACC_INTRO;;
500
501 let CELL_LIST_PASS_ACC_REV = prove(`m_cell_list_pass (APPEND acc (CONS h fs2)) domain
502 <=> m_cell_list_pass (APPEND (CONS h acc) fs2) domain`,
503 REWRITE_TAC[m_cell_list_pass; ITLIST_DISJ_APPEND; ITLIST; DISJ_ACI]);;
504
505 let CELL_LIST_PASS_NIL1 = prove(`m_cell_list_pass (APPEND (APPEND [] fs2) acc) domain
506 <=> m_cell_list_pass (APPEND fs2 acc) domain`,
507 REWRITE_TAC[APPEND]);;
508
509 let CELL_LIST_PASS_NIL2 = prove(`m_cell_list_pass (APPEND (APPEND fs1 []) acc) domain
510 <=> m_cell_list_pass (APPEND fs1 acc) domain`,
511 REWRITE_TAC[APPEND_NIL]);;
512
513 let CELL_LIST_PASS_SAME_HD = prove(`m_cell_list_pass (APPEND (APPEND (CONS h fs1) (CONS h fs2)) acc) domain
514 <=> m_cell_list_pass (APPEND (APPEND fs1 fs2) (CONS h acc)) domain`,
515 REWRITE_TAC[m_cell_list_pass; ITLIST_DISJ_APPEND; ITLIST; DISJ_ACI]);;
516
517 let CELL_LIST_PASS_MOVE1 = prove(`m_cell_list_pass (APPEND (APPEND (CONS h fs1) fs2) acc) domain
518 <=> m_cell_list_pass (APPEND (APPEND fs1 fs2) (CONS h acc)) domain`,
519 REWRITE_TAC[m_cell_list_pass; ITLIST_DISJ_APPEND; ITLIST; DISJ_ACI]);;
520
521 let CELL_LIST_PASS_MOVE2 = prove(`m_cell_list_pass (APPEND (APPEND fs1 (CONS h fs2)) acc) domain
522 <=> m_cell_list_pass (APPEND (APPEND fs1 fs2) (CONS h acc)) domain`,
523 REWRITE_TAC[m_cell_list_pass; ITLIST_DISJ_APPEND; ITLIST; DISJ_ACI]);;
524
525 (* pass_th should be in the form |- m_cell_list_pass (APPEND fs1 fs2) dom *)
526 let merge_m_cell_list_pass n pass_th =
527 let append_tm, dom_tm = dest_m_cell_pass (concl pass_th) in
528 let list_ty = type_of append_tm in
529 let dom_var = mk_var ("domain", type_of dom_tm) and
530 fs1_var = mk_var ("fs1", list_ty) and
531 fs2_var = mk_var ("fs2", list_ty) and
532 acc_var = mk_var ("acc", list_ty) and
533 h_var = mk_var ("h", (hd o snd o dest_type) list_ty) in
534 let acc_intro, acc_elim, acc_rev, pass_nil1, pass_nil2, same_hd, pass_move1, pass_move2 =
535 let r = inst_first_type_var n_type_array.(n) in
536 r CELL_LIST_PASS_ACC_INTRO,
537 r CELL_LIST_PASS_ACC_ELIM,
538 r CELL_LIST_PASS_ACC_REV,
539 r CELL_LIST_PASS_NIL1,
540 r CELL_LIST_PASS_NIL2,
541 r CELL_LIST_PASS_SAME_HD,
542 r CELL_LIST_PASS_MOVE1,
543 r CELL_LIST_PASS_MOVE2 in
544
545 (* Reverses the result list to preserve ordering *)
546 let rec rev_acc th =
547 let ltm, s_tm = (dest_comb o rand o rator o concl) th in
548 let acc_tm = rand ltm in
549 if is_comb s_tm then
550 let h_tm, fs2_tm = dest_binary "CONS" s_tm in
551 let th1 = INST[h_tm, h_var; fs2_tm, fs2_var; acc_tm, acc_var; dom_tm, dom_var] acc_rev in
552 let th2 = EQ_MP th1 th in
553 rev_acc th2
554 else
555 let th1 = INST[acc_tm, fs1_var; dom_tm, dom_var] acc_elim in
556 EQ_MP th1 th in
557
558 (* Computes a merged list *)
559 let rec merge_append th =
560 let ltm, acc_tm = (dest_comb o rand o rator o concl) th in
561 let fs1_tm, fs2_tm = dest_binary "APPEND" (rand ltm) in
562 if not (is_comb fs1_tm) then
563 let th1 = INST[fs2_tm, fs2_var; acc_tm, acc_var; dom_tm, dom_var] pass_nil1 in
564 EQ_MP th1 th
565 else if not (is_comb fs2_tm) then
566 let th1 = INST[fs1_tm, fs1_var; acc_tm, acc_var; dom_tm, dom_var] pass_nil2 in
567 EQ_MP th1 th
568 else
569 let h1_tm, t1_tm = dest_binary "CONS" fs1_tm and
570 h2_tm, t2_tm = dest_binary "CONS" fs2_tm in
571 let th1 =
572 match (compare h1_tm h2_tm) with
573 | -1 -> INST[h1_tm, h_var; t1_tm, fs1_var; fs2_tm, fs2_var; acc_tm, acc_var; dom_tm, dom_var] pass_move1
574 | 1 -> INST[h2_tm, h_var; t2_tm, fs2_var; fs1_tm, fs1_var; acc_tm, acc_var; dom_tm, dom_var] pass_move2
575 | _ -> INST[h1_tm, h_var; t1_tm, fs1_var; t2_tm, fs2_var; acc_tm, acc_var; dom_tm, dom_var] same_hd in
576 let th2 = EQ_MP th1 th in
577 merge_append th2 in
578
579 let th0 = EQ_MP (INST[append_tm, fs1_var; dom_tm, dom_var] acc_intro) pass_th in
580 let th1 = merge_append th0 in
581 rev_acc th1;;
582
583
584 (***************************************)
585
586 let M_CELL_SUP = prove(`!f x z. lift o f continuous_on interval [x,z:real^N] /\ m_cell_pass f (x,z) ==>
587 ?a. a < &0 /\ !y. y IN interval [x,z] ==> f y <= a`,
588 REWRITE_TAC[m_cell_pass] THEN REPEAT STRIP_TAC THEN
589 ASM_CASES_TAC `interval [x:real^N,z] = {}` THENL
590 [
591 EXISTS_TAC `-- &1` THEN ASM_REWRITE_TAC[NOT_IN_EMPTY] THEN REAL_ARITH_TAC;
592 ALL_TAC
593 ] THEN
594 MP_TAC (SPECL [`f:real^N->real`; `interval [x,z:real^N]`] CONTINUOUS_ATTAINS_SUP) THEN
595 ASM_REWRITE_TAC[COMPACT_INTERVAL] THEN
596 DISCH_THEN (X_CHOOSE_THEN `y:real^N` STRIP_ASSUME_TAC) THEN
597 EXISTS_TAC `(f:real^N->real) y` THEN ASM_REWRITE_TAC[] THEN
598 FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);;
599
600
601 let DIFF2_DOMAIN_IMP_CONTINUOUS_ON = prove(`!(f:real^N->real) domain. diff2_domain domain f ==>
602 lift o f continuous_on interval [domain]`,
603 REWRITE_TAC[diff2_domain] THEN REPEAT STRIP_TAC THEN
604 MATCH_MP_TAC CONTINUOUS_AT_IMP_CONTINUOUS_ON THEN REPEAT STRIP_TAC THEN
605 MATCH_MP_TAC DIFFERENTIABLE_IMP_CONTINUOUS_AT THEN
606 MATCH_MP_TAC diff2_imp_diff THEN
607 ASM_SIMP_TAC[]);;
608
609
610
611 let M_CELL_INCREASING_PASS_LEMMA = prove(`!j x z u domain lo f.
612 interval [x,z] SUBSET interval [domain] ==>
613 diff2c_domain domain f ==>
614 (!i. i IN 1..dimindex (:N) ==> ~(i = j) ==> u$i = x$i) ==>
615 u$j = z$j ==>
616 &0 <= lo ==>
617 (!y. y IN interval [domain] ==> lo <= partial j f y) ==>
618 m_cell_pass f (u,z) ==>
619 m_cell_pass f (x,z:real^N)`,
620 REWRITE_TAC[SUBSET] THEN REPEAT STRIP_TAC THEN REWRITE_TAC[m_cell_pass] THEN
621 X_GEN_TAC `y:real^N` THEN
622 ASM_CASES_TAC `~(!i. i IN 1..dimindex (:N) ==> (x:real^N)$i <= (z:real^N)$i)` THENL
623 [
624 POP_ASSUM MP_TAC THEN REWRITE_TAC[NOT_FORALL_THM; NOT_IMP; IN_INTERVAL; GSYM IN_NUMSEG] THEN
625 DISCH_THEN (CHOOSE_THEN STRIP_ASSUME_TAC) THEN
626 DISCH_THEN (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
627 POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
628 ALL_TAC
629 ] THEN
630 POP_ASSUM MP_TAC THEN REWRITE_TAC[negbK] THEN DISCH_TAC THEN
631 SUBGOAL_THEN `diff2_domain domain (f:real^N->real)` ASSUME_TAC THENL
632 [
633 UNDISCH_TAC `diff2c_domain domain (f:real^N->real)` THEN
634 SIMP_TAC[diff2_domain; diff2c_domain; diff2c];
635 ALL_TAC
636 ] THEN
637 MP_TAC (SPECL [`f:real^N->real`; `u:real^N`; `z:real^N`] M_CELL_SUP) THEN
638 ANTS_TAC THENL
639 [
640 ASM_REWRITE_TAC[] THEN
641 MATCH_MP_TAC DIFF2_DOMAIN_IMP_CONTINUOUS_ON THEN
642 UNDISCH_TAC `diff2_domain domain (f:real^N->real)` THEN
643 REWRITE_TAC[diff2_domain] THEN REPEAT STRIP_TAC THEN
644 REPEAT (FIRST_X_ASSUM MATCH_MP_TAC) THEN
645 POP_ASSUM MP_TAC THEN
646 REWRITE_TAC[IN_INTERVAL] THEN DISCH_TAC THEN GEN_TAC THEN DISCH_TAC THEN
647 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
648 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[IN_NUMSEG] THEN
649 ASM_CASES_TAC `i = j:num` THENL [ ASM_REWRITE_TAC[] THEN REAL_ARITH_TAC; ALL_TAC] THEN
650 FIRST_X_ASSUM (new_rewrite [] []) THEN ASM_REWRITE_TAC[IN_NUMSEG];
651 ALL_TAC
652 ] THEN
653 DISCH_THEN (CHOOSE_THEN STRIP_ASSUME_TAC) THEN DISCH_TAC THEN
654 MP_TAC (SPECL [`f:real^N->real`; `j:num`; `u:real^N`; `x:real^N`; `z:real^N`; `a:real`] partial_increasing_right) THEN
655 ASM_REWRITE_TAC[] THEN
656 ANTS_TAC THENL
657 [
658 REPEAT STRIP_TAC THEN
659 MATCH_MP_TAC diff2_imp_diff THEN
660 UNDISCH_TAC `diff2_domain domain (f:real^N->real)` THEN REWRITE_TAC[diff2_domain] THEN
661 DISCH_THEN MATCH_MP_TAC THEN
662 FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[];
663 ALL_TAC
664 ] THEN
665 ANTS_TAC THENL
666 [
667 REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN
668 EXISTS_TAC `lo:real` THEN ASM_REWRITE_TAC[] THEN
669 REPEAT (FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);
670 ALL_TAC
671 ] THEN
672 DISCH_TAC THEN MATCH_MP_TAC REAL_LET_TRANS THEN
673 EXISTS_TAC `a:real` THEN ASM_REWRITE_TAC[] THEN
674 FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);;
675
676
677
678 let M_CELL_DECREASING_PASS_LEMMA = prove(`!j x z u domain hi f.
679 interval [x,z] SUBSET interval [domain] ==>
680 diff2c_domain domain f ==>
681 (!i. i IN 1..dimindex (:N) ==> ~(i = j) ==> u$i = z$i) ==>
682 u$j = x$j ==>
683 hi <= &0 ==>
684 (!y. y IN interval [domain] ==> partial j f y <= hi) ==>
685 m_cell_pass f (x,u) ==>
686 m_cell_pass f (x,z:real^N)`,
687 REWRITE_TAC[SUBSET] THEN REPEAT STRIP_TAC THEN REWRITE_TAC[m_cell_pass] THEN X_GEN_TAC `y:real^N` THEN
688 ASM_CASES_TAC `~(!i. i IN 1..dimindex (:N) ==> (x:real^N)$i <= (z:real^N)$i)` THENL
689 [
690 POP_ASSUM MP_TAC THEN REWRITE_TAC[NOT_FORALL_THM; NOT_IMP; IN_INTERVAL; GSYM IN_NUMSEG] THEN
691 DISCH_THEN (CHOOSE_THEN STRIP_ASSUME_TAC) THEN
692 DISCH_THEN (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
693 POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
694 ALL_TAC
695 ] THEN
696 POP_ASSUM MP_TAC THEN REWRITE_TAC[negbK] THEN DISCH_TAC THEN
697 SUBGOAL_THEN `diff2_domain domain (f:real^N->real)` ASSUME_TAC THENL
698 [
699 UNDISCH_TAC `diff2c_domain domain (f:real^N->real)` THEN
700 SIMP_TAC[diff2_domain; diff2c_domain; diff2c];
701 ALL_TAC
702 ] THEN
703 MP_TAC (SPECL [`f:real^N->real`; `x:real^N`; `u:real^N`] M_CELL_SUP) THEN
704 ANTS_TAC THENL
705 [
706 ASM_REWRITE_TAC[] THEN
707 MATCH_MP_TAC DIFF2_DOMAIN_IMP_CONTINUOUS_ON THEN
708 UNDISCH_TAC `diff2_domain domain (f:real^N->real)` THEN
709 REWRITE_TAC[diff2_domain] THEN REPEAT STRIP_TAC THEN
710 REPEAT (FIRST_X_ASSUM MATCH_MP_TAC) THEN
711 POP_ASSUM MP_TAC THEN
712 REWRITE_TAC[IN_INTERVAL] THEN DISCH_TAC THEN GEN_TAC THEN DISCH_TAC THEN
713 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
714 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[IN_NUMSEG] THEN
715 ASM_CASES_TAC `i = j:num` THENL [ ASM_REWRITE_TAC[] THEN REAL_ARITH_TAC; ALL_TAC] THEN
716 FIRST_X_ASSUM (new_rewrite [] []) THEN ASM_REWRITE_TAC[IN_NUMSEG];
717 ALL_TAC
718 ] THEN
719 DISCH_THEN (CHOOSE_THEN STRIP_ASSUME_TAC) THEN DISCH_TAC THEN
720 MP_TAC (SPECL [`f:real^N->real`; `j:num`; `u:real^N`; `x:real^N`; `z:real^N`; `a:real`] partial_decreasing_left) THEN
721 ASM_REWRITE_TAC[] THEN
722 ANTS_TAC THENL
723 [
724 REPEAT STRIP_TAC THEN
725 MATCH_MP_TAC diff2_imp_diff THEN
726 UNDISCH_TAC `diff2_domain domain (f:real^N->real)` THEN REWRITE_TAC[diff2_domain] THEN
727 DISCH_THEN MATCH_MP_TAC THEN ASM_REWRITE_TAC[] THEN
728 FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[];
729 ALL_TAC
730 ] THEN
731 ANTS_TAC THENL
732 [
733 REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN
734 EXISTS_TAC `hi:real` THEN ASM_REWRITE_TAC[] THEN
735 REPEAT (FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);
736 ALL_TAC
737 ] THEN
738 DISCH_TAC THEN MATCH_MP_TAC REAL_LET_TRANS THEN
739 EXISTS_TAC `a:real` THEN ASM_REWRITE_TAC[] THEN
740 FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);;
741
742
743
744 let M_CELL_CONVEX_PASS_LEMMA = prove(`!j x z u v lo f.
745 diff2c_domain (x,z) f ==>
746 (!i. i IN 1..dimindex (:N) ==> ~(i = j) ==> u$i = z$i /\ v$i = x$i) ==>
747 u$j = x$j ==> v$j = z$j ==>
748 &0 <= lo ==>
749 (!y. y IN interval [x,z] ==> lo <= partial2 j j f y) ==>
750 m_cell_pass f (x,u) ==>
751 m_cell_pass f (v,z) ==>
752 m_cell_pass f (x:real^N,z)`,
753 REPEAT STRIP_TAC THEN REWRITE_TAC[m_cell_pass] THEN
754 X_GEN_TAC `y:real^N` THEN DISCH_TAC THEN
755 SUBGOAL_THEN `!i. i IN 1..dimindex (:N) ==> (x:real^N)$i <= (z:real^N)$i` ASSUME_TAC THENL
756 [
757 POP_ASSUM MP_TAC THEN REWRITE_TAC[IN_INTERVAL] THEN REPEAT STRIP_TAC THEN
758 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `(y:real^N)$i` THEN
759 FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[GSYM IN_NUMSEG];
760 ALL_TAC
761 ] THEN
762 SUBGOAL_THEN `diff2_domain (x,z) (f:real^N->real)` ASSUME_TAC THENL
763 [
764 UNDISCH_TAC `diff2c_domain (x,z) (f:real^N->real)` THEN
765 SIMP_TAC[diff2_domain; diff2c_domain; diff2c];
766 ALL_TAC
767 ] THEN
768 MP_TAC (SPECL [`f:real^N->real`; `v:real^N`; `z:real^N`] M_CELL_SUP) THEN
769 ANTS_TAC THENL
770 [
771 ASM_REWRITE_TAC[] THEN
772 MATCH_MP_TAC DIFF2_DOMAIN_IMP_CONTINUOUS_ON THEN
773 UNDISCH_TAC `diff2_domain (x,z) (f:real^N->real)` THEN
774 REWRITE_TAC[diff2_domain] THEN REPEAT STRIP_TAC THEN
775 FIRST_X_ASSUM MATCH_MP_TAC THEN
776 POP_ASSUM MP_TAC THEN
777 REWRITE_TAC[IN_INTERVAL] THEN DISCH_TAC THEN GEN_TAC THEN DISCH_TAC THEN
778 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
779 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[IN_NUMSEG] THEN
780 ASM_CASES_TAC `i = j:num` THENL [ ASM_REWRITE_TAC[] THEN REAL_ARITH_TAC; ALL_TAC] THEN
781 FIRST_X_ASSUM (new_rewrite [] []) THEN ASM_REWRITE_TAC[IN_NUMSEG];
782 ALL_TAC
783 ] THEN
784 DISCH_THEN (CHOOSE_THEN STRIP_ASSUME_TAC) THEN
785
786 MP_TAC (SPECL [`f:real^N->real`; `x:real^N`; `u:real^N`] M_CELL_SUP) THEN
787 ANTS_TAC THENL
788 [
789 ASM_REWRITE_TAC[] THEN
790 MATCH_MP_TAC DIFF2_DOMAIN_IMP_CONTINUOUS_ON THEN
791 UNDISCH_TAC `diff2_domain (x,z) (f:real^N->real)` THEN
792 REWRITE_TAC[diff2_domain] THEN REPEAT STRIP_TAC THEN
793 FIRST_X_ASSUM MATCH_MP_TAC THEN
794 POP_ASSUM MP_TAC THEN
795 REWRITE_TAC[IN_INTERVAL] THEN DISCH_TAC THEN GEN_TAC THEN DISCH_TAC THEN
796 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
797 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[IN_NUMSEG] THEN
798 ASM_CASES_TAC `i = j:num` THENL [ ASM_REWRITE_TAC[] THEN REAL_ARITH_TAC; ALL_TAC] THEN
799 FIRST_X_ASSUM (new_rewrite [] []) THEN ASM_REWRITE_TAC[IN_NUMSEG];
800 ALL_TAC
801 ] THEN
802 DISCH_THEN (CHOOSE_THEN STRIP_ASSUME_TAC) THEN
803
804 MP_TAC (SPECL [`f:real^N->real`; `j:num`; `x:real^N`; `z:real^N`; `u:real^N`; `v:real^N`; `max a a'`] partial_convex_max) THEN
805 ASM_REWRITE_TAC[] THEN
806 ANTS_TAC THENL
807 [
808 REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN
809 EXISTS_TAC `lo:real` THEN ASM_REWRITE_TAC[] THEN
810 REPEAT (FIRST_X_ASSUM MATCH_MP_TAC THEN ASM_REWRITE_TAC[]);
811 ALL_TAC
812 ] THEN
813 ANTS_TAC THENL
814 [
815 REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN
816 EXISTS_TAC `a':real` THEN
817 ASM_SIMP_TAC[] THEN REAL_ARITH_TAC;
818 ALL_TAC
819 ] THEN
820 ANTS_TAC THENL
821 [
822 REPEAT STRIP_TAC THEN MATCH_MP_TAC REAL_LE_TRANS THEN
823 EXISTS_TAC `a:real` THEN
824 ASM_SIMP_TAC[] THEN REAL_ARITH_TAC;
825 ALL_TAC
826 ] THEN
827
828 DISCH_TAC THEN MATCH_MP_TAC REAL_LET_TRANS THEN
829 EXISTS_TAC `max a a'` THEN
830 ASM_SIMP_TAC[] THEN
831 ASM_REAL_ARITH_TAC);;
832
833
834 (*********************)
835
836 let ITLIST_DISJ_EXISTS = prove(`!P l. ITLIST (\x r. P x \/ r) l F <=> ?x:A. MEM x l /\ P x`,
837 GEN_TAC THEN LIST_INDUCT_TAC THEN ASM_REWRITE_TAC[ITLIST; MEM] THEN EQ_TAC THENL [
838 STRIP_TAC THENL [EXISTS_TAC `h:A`; EXISTS_TAC `x:A`] THEN ASM_REWRITE_TAC[];
839 ALL_TAC;
840 ] THEN
841 DISCH_THEN (CHOOSE_THEN STRIP_ASSUME_TAC) THENL [
842 POP_ASSUM MP_TAC THEN POP_ASSUM (fun th -> SIMP_TAC[SYM th]);
843 DISJ2_TAC THEN EXISTS_TAC `x:A` THEN ASM_REWRITE_TAC[]
844 ]);;
845
846 let M_CELL_LIST_PASS_ALT = prove(`!fs domain. m_cell_list_pass fs domain <=>
847 (!y:real^N. y IN interval [domain] ==> ?f. MEM f fs /\ f y < &0)`,
848 REWRITE_TAC[m_cell_list_pass; ITLIST_DISJ_EXISTS]);;
849
850 let M_CELL_LIST_PASS_APPEND = prove(`!fs fs2 domain. m_cell_list_pass fs domain
851 ==> m_cell_list_pass (APPEND fs fs2) domain`,
852 MESON_TAC[M_CELL_LIST_PASS_ALT; MEM_APPEND]);;
853
854 let ONE_POINT_INTERVAL = prove(`!x:real^N. interval [x,x] = {x}`,
855 GEN_TAC THEN REWRITE_TAC[EXTENSION; IN_SING; IN_INTERVAL] THEN X_GEN_TAC `y:real^N` THEN
856 EQ_TAC THEN SIMP_TAC[REAL_LE_REFL] THEN
857 DISCH_TAC THEN ONCE_REWRITE_TAC[GSYM LAMBDA_ETA] THEN
858 REWRITE_TAC[GSYM LAMBDA_UNIQUE] THEN GEN_TAC THEN DISCH_TAC THEN
859 ASM_SIMP_TAC[LAMBDA_BETA] THEN
860 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
861 ARITH_TAC);;
862
863
864 let M_CELL_LIST_INCREASING_PASS_LEMMA = prove(`!j x z u domain fs.
865 interval [x,z] SUBSET interval [domain] ==>
866 (!i. i IN 1..dimindex (:N) ==> ~(i = j) ==> u$i = x$i) ==>
867 u$j = z$j ==>
868 ALL (\f. diff2c_domain domain f /\
869 (!y. y IN interval [domain] ==> &0 <= partial j f y)) fs ==>
870 m_cell_list_pass fs (u,z) ==>
871 m_cell_list_pass fs (x,z:real^N)`,
872 REWRITE_TAC[SUBSET; M_CELL_LIST_PASS_ALT] THEN REPEAT STRIP_TAC THEN
873 ABBREV_TAC `(xx:real^N) = lambda i. if i = j then (x:real^N)$i else (y:real^N)$i` THEN
874 ABBREV_TAC `(zz:real^N) = lambda i. if i = j then (z:real^N)$i else (y:real^N)$i` THEN
875
876 SUBGOAL_THEN `interval [xx:real^N,zz] SUBSET interval [domain]` ASSUME_TAC THENL [
877 MATCH_MP_TAC SUBSET_TRANS THEN EXISTS_TAC `interval [x:real^N,z]` THEN ASM_REWRITE_TAC[SUBSET] THEN
878 REWRITE_TAC[IN_INTERVAL] THEN X_GEN_TAC `t:real^N` THEN DISCH_THEN (LABEL_TAC "in1") THEN
879 GEN_TAC THEN DISCH_TAC THEN
880 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
881 EXPAND_TAC "xx" THEN EXPAND_TAC "zz" THEN ASM_SIMP_TAC[LAMBDA_BETA] THEN
882 COND_CASES_TAC THEN ASM_REWRITE_TAC[] THEN
883 UNDISCH_TAC `y IN interval[x:real^N,z]` THEN REWRITE_TAC[IN_INTERVAL] THEN
884 DISCH_THEN (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
885 ARITH_TAC;
886 ALL_TAC
887 ] THEN
888
889 SUBGOAL_THEN `y IN interval [xx:real^N,zz]` ASSUME_TAC THENL [
890 REWRITE_TAC[IN_INTERVAL] THEN GEN_TAC THEN DISCH_TAC THEN
891 EXPAND_TAC "xx" THEN EXPAND_TAC "zz" THEN ASM_SIMP_TAC[LAMBDA_BETA] THEN
892 COND_CASES_TAC THEN ASM_REWRITE_TAC[REAL_LE_REFL] THEN
893 UNDISCH_TAC `y IN interval[x:real^N,z]` THEN REWRITE_TAC[IN_INTERVAL] THEN
894 DISCH_THEN (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[];
895 ALL_TAC
896 ] THEN
897
898 FIRST_X_ASSUM (MP_TAC o SPEC `zz:real^N`) THEN ANTS_TAC THENL [
899 REWRITE_TAC[IN_INTERVAL] THEN GEN_TAC THEN DISCH_TAC THEN
900 EXPAND_TAC "zz" THEN ASM_SIMP_TAC[LAMBDA_BETA] THEN
901 COND_CASES_TAC THEN ASM_REWRITE_TAC[REAL_LE_REFL] THEN
902 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[IN_NUMSEG] THEN
903 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
904 UNDISCH_TAC `y IN interval[x:real^N,z]` THEN REWRITE_TAC[IN_INTERVAL] THEN
905 DISCH_THEN (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[];
906 ALL_TAC
907 ] THEN
908
909 DISCH_THEN (CHOOSE_THEN ASSUME_TAC) THEN EXISTS_TAC (`f:real^N->real`) THEN ASM_REWRITE_TAC[] THEN
910 FIRST_X_ASSUM (MP_TAC o (fun th -> if is_binary "ALL" (concl th) then th else failwith "")) THEN
911 REWRITE_TAC[GSYM ALL_MEM] THEN DISCH_THEN (MP_TAC o SPEC `f:real^N->real`) THEN ASM_REWRITE_TAC[] THEN
912 STRIP_TAC THEN
913 MP_TAC (SPECL [`j:num`; `xx:real^N`; `zz:real^N`; `zz:real^N`; `domain:real^N#real^N`; `&0`; `f:real^N->real`] M_CELL_INCREASING_PASS_LEMMA) THEN
914 ASM_REWRITE_TAC[REAL_LE_REFL; m_cell_pass] THEN ANTS_TAC THENL [
915 REWRITE_TAC[IN_NUMSEG] THEN GEN_TAC THEN DISCH_TAC THEN
916 EXPAND_TAC "xx" THEN EXPAND_TAC "zz" THEN ASM_SIMP_TAC[LAMBDA_BETA];
917 ALL_TAC
918 ] THEN
919 ASM_SIMP_TAC[ONE_POINT_INTERVAL; IN_SING]);;
920
921
922
923 let M_CELL_LIST_DECREASING_PASS_LEMMA = prove(`!j x z u domain fs.
924 interval [x,z] SUBSET interval [domain] ==>
925 (!i. i IN 1..dimindex (:N) ==> ~(i = j) ==> u$i = z$i) ==>
926 u$j = x$j ==>
927 ALL (\f. diff2c_domain domain f /\
928 (!y. y IN interval [domain] ==> partial j f y <= &0)) fs ==>
929 m_cell_list_pass fs (x,u) ==>
930 m_cell_list_pass fs (x,z:real^N)`,
931 REWRITE_TAC[SUBSET; M_CELL_LIST_PASS_ALT] THEN REPEAT STRIP_TAC THEN
932 ABBREV_TAC `(xx:real^N) = lambda i. if i = j then (x:real^N)$i else (y:real^N)$i` THEN
933 ABBREV_TAC `(zz:real^N) = lambda i. if i = j then (z:real^N)$i else (y:real^N)$i` THEN
934 SUBGOAL_THEN `interval [xx:real^N,zz] SUBSET interval [domain]` ASSUME_TAC THENL [
935 MATCH_MP_TAC SUBSET_TRANS THEN EXISTS_TAC `interval [x:real^N,z]` THEN ASM_REWRITE_TAC[SUBSET] THEN
936 REWRITE_TAC[IN_INTERVAL] THEN X_GEN_TAC `t:real^N` THEN DISCH_THEN (LABEL_TAC "in1") THEN
937 GEN_TAC THEN DISCH_TAC THEN
938 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
939 EXPAND_TAC "xx" THEN EXPAND_TAC "zz" THEN ASM_SIMP_TAC[LAMBDA_BETA] THEN
940 COND_CASES_TAC THEN ASM_REWRITE_TAC[] THEN
941 UNDISCH_TAC `y IN interval[x:real^N,z]` THEN REWRITE_TAC[IN_INTERVAL] THEN
942 DISCH_THEN (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[] THEN
943 ARITH_TAC;
944 ALL_TAC
945 ] THEN
946 SUBGOAL_THEN `y IN interval [xx:real^N,zz]` ASSUME_TAC THENL [
947 REWRITE_TAC[IN_INTERVAL] THEN GEN_TAC THEN DISCH_TAC THEN
948 EXPAND_TAC "xx" THEN EXPAND_TAC "zz" THEN ASM_SIMP_TAC[LAMBDA_BETA] THEN
949 COND_CASES_TAC THEN ASM_REWRITE_TAC[REAL_LE_REFL] THEN
950 UNDISCH_TAC `y IN interval[x:real^N,z]` THEN REWRITE_TAC[IN_INTERVAL] THEN
951 DISCH_THEN (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[];
952 ALL_TAC
953 ] THEN
954 FIRST_X_ASSUM (MP_TAC o SPEC `xx:real^N`) THEN ANTS_TAC THENL [
955 REWRITE_TAC[IN_INTERVAL] THEN GEN_TAC THEN DISCH_TAC THEN
956 EXPAND_TAC "xx" THEN ASM_SIMP_TAC[LAMBDA_BETA] THEN
957 COND_CASES_TAC THEN ASM_REWRITE_TAC[REAL_LE_REFL] THEN
958 FIRST_X_ASSUM (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[IN_NUMSEG] THEN
959 DISCH_THEN (fun th -> REWRITE_TAC[th]) THEN
960 UNDISCH_TAC `y IN interval[x:real^N,z]` THEN REWRITE_TAC[IN_INTERVAL] THEN
961 DISCH_THEN (MP_TAC o SPEC `i:num`) THEN ASM_REWRITE_TAC[];
962 ALL_TAC
963 ] THEN
964 DISCH_THEN (CHOOSE_THEN ASSUME_TAC) THEN EXISTS_TAC (`f:real^N->real`) THEN ASM_REWRITE_TAC[] THEN
965 FIRST_X_ASSUM (MP_TAC o (fun th -> if is_binary "ALL" (concl th) then th else failwith "")) THEN
966 REWRITE_TAC[GSYM ALL_MEM] THEN DISCH_THEN (MP_TAC o SPEC `f:real^N->real`) THEN ASM_REWRITE_TAC[] THEN
967 STRIP_TAC THEN
968 MP_TAC (SPECL [`j:num`; `xx:real^N`; `zz:real^N`; `xx:real^N`; `domain:real^N#real^N`; `&0`; `f:real^N->real`] M_CELL_DECREASING_PASS_LEMMA) THEN
969 ASM_REWRITE_TAC[REAL_LE_REFL; m_cell_pass] THEN ANTS_TAC THENL [
970 REWRITE_TAC[IN_NUMSEG] THEN GEN_TAC THEN DISCH_TAC THEN
971 EXPAND_TAC "xx" THEN EXPAND_TAC "zz" THEN ASM_SIMP_TAC[LAMBDA_BETA];
972 ALL_TAC
973 ] THEN
974 ASM_SIMP_TAC[ONE_POINT_INTERVAL; IN_SING]);;
975
976
977
978 (*********************)
979
980 let ZERO_EQ_ZERO_CONST = prove(`0 = _0`, REWRITE_TAC[NUMERAL]);;
981
982 let gen_increasing_lemma n j =
983 let mk_vars name = map (fun i -> mk_var (sprintf "%s%d" name i, real_ty)) (1--n) in
984 let xs = mk_vars "x" and
985 zs = mk_vars "z" and
986 j_tm = mk_small_numeral j in
987 let x_tm = mk_vector_list xs and
988 z_tm = mk_vector_list zs and
989 u_tm = mk_vector_list (map (fun i -> List.nth (if i = j then zs else xs) (i - 1)) (1--n)) in
990 let th0 = (SPEC_ALL o ISPECL [j_tm; x_tm; z_tm; u_tm]) M_CELL_INCREASING_PASS_LEMMA in
991 let th1 = REWRITE_RULE[dimindex_array.(n); IN_NUMSEG; gen_in_interval n; ARITH] th0 in
992 let th2 = REWRITE_RULE (Array.to_list comp_thms_array.(n)) th1 in
993 let th3 = MY_RULE_NUM th2 in
994 (UNDISCH_ALL o ONCE_REWRITE_RULE[GSYM ZERO_EQ_ZERO_CONST] o DISCH (last (hyp th3))) th3;;
995
996
997 let gen_mono_lemma0 th =
998 let h2 = List.nth (hyp th) 1 in
999 let domain_tm = (lhand o rand o lhand) h2 in
1000 let domain_var = mk_var ("domain", type_of domain_tm) in
1001 (UNDISCH_ALL o REWRITE_RULE[SUBSET_REFL] o DISCH_ALL o INST[domain_tm, domain_var]) th;;
1002
1003 let incr_gen_thms_array = Array.init (max_dim + 1)
1004 (fun n -> Array.init (n + 1)
1005 (fun j -> if j < 1 then TRUTH else gen_increasing_lemma n j));;
1006
1007 let incr_thms_array = Array.init (max_dim + 1)
1008 (fun n -> Array.init (n + 1)
1009 (fun j -> if j < 1 then TRUTH else gen_mono_lemma0 incr_gen_thms_array.(n).(j)));;
1010
1011
1012
1013 let gen_decreasing_lemma n j =
1014 let mk_vars name = map (fun i -> mk_var (sprintf "%s%d" name i, real_ty)) (1--n) in
1015 let xs = mk_vars "x" and
1016 zs = mk_vars "z" and
1017 j_tm = mk_small_numeral j in
1018 let x_tm = mk_vector_list xs and
1019 z_tm = mk_vector_list zs and
1020 u_tm = mk_vector_list (map (fun i -> List.nth (if i = j then xs else zs) (i - 1)) (1--n)) in
1021 let th0 = (SPEC_ALL o ISPECL [j_tm; x_tm; z_tm; u_tm]) M_CELL_DECREASING_PASS_LEMMA in
1022 let th1 = REWRITE_RULE[dimindex_array.(n); IN_NUMSEG; gen_in_interval n; ARITH] th0 in
1023 let th2 = REWRITE_RULE (Array.to_list comp_thms_array.(n)) th1 in
1024 let th3 = MY_RULE_NUM th2 in
1025 (UNDISCH_ALL o ONCE_REWRITE_RULE[GSYM ZERO_EQ_ZERO_CONST] o DISCH (last (hyp th3))) th3;;
1026
1027
1028 let decr_gen_thms_array = Array.init (max_dim + 1)
1029 (fun n -> Array.init (n + 1)
1030 (fun j -> if j < 1 then TRUTH else gen_decreasing_lemma n j));;
1031
1032 let decr_thms_array = Array.init (max_dim + 1)
1033 (fun n -> Array.init (n + 1)
1034 (fun j -> if j < 1 then TRUTH else gen_mono_lemma0 decr_gen_thms_array.(n).(j)));;
1035
1036
1037 (****************************************)
1038
1039 let gen_convex_max_lemma n j =
1040 let xs = mk_real_vars n "x" and
1041 zs = mk_real_vars n "z" and
1042 j_tm = mk_small_numeral j in
1043 let x_tm = mk_vector_list xs and
1044 z_tm = mk_vector_list zs and
1045 u_tm = mk_vector_list (map (fun i -> List.nth (if i = j then xs else zs) (i - 1)) (1--n)) and
1046 v_tm = mk_vector_list (map (fun i -> List.nth (if i = j then zs else xs) (i - 1)) (1--n)) in
1047 let th0 = (SPEC_ALL o ISPECL [j_tm; x_tm; z_tm; u_tm; v_tm]) M_CELL_CONVEX_PASS_LEMMA in
1048 let th1 = REWRITE_RULE[dimindex_array.(n); IN_NUMSEG; gen_in_interval n; ARITH] th0 in
1049 let th2 = REWRITE_RULE (Array.to_list comp_thms_array.(n)) th1 in
1050 let th3 = MY_RULE_NUM th2 in
1051 (UNDISCH_ALL o ONCE_REWRITE_RULE[GSYM ZERO_EQ_ZERO_CONST] o DISCH (last (hyp th3))) th3;;
1052
1053
1054 let convex_thms_array = Array.init (max_dim + 1)
1055 (fun n -> Array.init (n + 1)
1056 (fun j -> if j < 1 then TRUTH else gen_convex_max_lemma n j));;
1057
1058
1059
1060 (******************************************)
1061
1062 let m_glue_cells n j pass_th1 pass_th2 =
1063 let f_tm, domain1 = dest_m_cell_pass (concl pass_th1) and
1064 domain2 = rand (concl pass_th2) in
1065 let x1, z1 = dest_pair domain1 and
1066 x2, z2 = dest_pair domain2 in
1067
1068 let x1s = dest_vector x1 and
1069 x2s = dest_vector x2 and
1070 z2s = dest_vector z2 in
1071
1072 let x_vars = map (fun i -> x_vars_array.(i)) (1--n) and
1073 z_vars = map (fun i -> z_vars_array.(i)) (1--n) and
1074 f_var = mk_var ("f", type_of f_tm) and
1075 t_tm = List.nth x2s (j - 1) in
1076
1077 let th0 = (INST[t_tm, t_var_real; f_tm, f_var] o
1078 INST (zip z2s z_vars) o INST (zip x1s x_vars)) (fst glue_thms_array.(n).(j)) in
1079 (MY_PROVE_HYP pass_th1 o MY_PROVE_HYP pass_th2) th0;;
1080
1081
1082 let m_glue_cells_list n j pass_th1 pass_th2 =
1083 let fs1_tm, domain1 = dest_m_cell_pass (concl pass_th1) and
1084 fs2_tm, domain2 = dest_m_cell_pass (concl pass_th2) in
1085 let x1, z1 = dest_pair domain1 and
1086 x2, z2 = dest_pair domain2 in
1087
1088 let x1s = dest_vector x1 and
1089 x2s = dest_vector x2 and
1090 z2s = dest_vector z2 in
1091
1092 let x_vars = map (fun i -> x_vars_array.(i)) (1--n) and
1093 z_vars = map (fun i -> z_vars_array.(i)) (1--n) and
1094 fs1_var = mk_var ("fs1", type_of fs1_tm) and
1095 fs2_var = mk_var ("fs2", type_of fs2_tm) and
1096 t_tm = List.nth x2s (j - 1) in
1097
1098 let th0 = (INST[t_tm, t_var_real; fs1_tm, fs1_var; fs2_tm, fs2_var] o
1099 INST (zip z2s z_vars) o INST (zip x1s x_vars)) (snd glue_thms_array.(n).(j)) in
1100 (MY_PROVE_HYP pass_th1 o MY_PROVE_HYP pass_th2) th0;;
1101
1102
1103 (**********************)
1104
1105 let m_mono_pass_gen n j decr_flag diff2_th partial_mono_th sub_th pass_th =
1106 let f_tm, domain0 = dest_m_cell_pass (concl pass_th) and
1107 domain = (rand o rator o concl) diff2_th and
1108 xv, zv = (dest_pair o lhand o rand o lhand o concl) sub_th and
1109 bound_tm = ((if decr_flag then rand else lhand) o rand o snd o dest_forall o concl) partial_mono_th in
1110
1111 let xs = dest_vector xv and
1112 zs = dest_vector zv in
1113
1114 let x_vars = map (fun i -> x_vars_array.(i)) (1--n) and
1115 z_vars = map (fun i -> z_vars_array.(i)) (1--n) and
1116 domain_var = mk_var ("domain", type_of domain) and
1117 f_var = mk_var ("f", type_of f_tm) and
1118 bound_var = mk_var ((if decr_flag then "hi" else "lo"), real_ty) in
1119
1120 let le_th0 = (if decr_flag then float_le0 else float_ge0) bound_tm in
1121 let le_th = try EQT_ELIM le_th0 with Failure _ ->
1122 failwith (sprintf "m_mono_pass_gen: j = %d, th = %s" j (string_of_thm le_th0)) in
1123
1124 let th0 = (INST[f_tm, f_var; bound_tm, bound_var; domain, domain_var] o
1125 INST (zip xs x_vars) o INST (zip zs z_vars))
1126 (if decr_flag then decr_gen_thms_array.(n).(j) else incr_gen_thms_array.(n).(j)) in
1127 (MY_PROVE_HYP le_th o MY_PROVE_HYP pass_th o MY_PROVE_HYP diff2_th o
1128 MY_PROVE_HYP sub_th o MY_PROVE_HYP partial_mono_th) th0;;
1129
1130
1131
1132 (* m_incr_pass *)
1133 let m_incr_pass n pp j m_taylor_th pass_th0 =
1134 let _, diff2_th, _, _ = dest_m_taylor_thms n m_taylor_th in
1135 let partial_bound = eval_m_taylor_partial_lower n pp j m_taylor_th in
1136
1137 let f_tm, domain0 = dest_m_cell_pass (concl pass_th0) and
1138 domain = (rand o rator o concl) diff2_th and
1139 lo_tm = (lhand o rand o snd o dest_forall o concl) partial_bound in
1140 let lo_ge0_th = EQT_ELIM (float_ge0 lo_tm) in
1141
1142 let x_tm, z_tm = dest_pair domain in
1143 let xs = dest_vector x_tm and
1144 zs = dest_vector z_tm in
1145
1146 let x_vars = map (fun i -> x_vars_array.(i)) (1--n) and
1147 z_vars = map (fun i -> z_vars_array.(i)) (1--n) and
1148 f_var = mk_var ("f", type_of f_tm) in
1149 let th0 = (INST[f_tm, f_var; lo_tm, lo_var_real] o
1150 INST (zip zs z_vars) o INST (zip xs x_vars)) incr_thms_array.(n).(j) in
1151 (MY_PROVE_HYP lo_ge0_th o MY_PROVE_HYP pass_th0 o
1152 MY_PROVE_HYP diff2_th o MY_PROVE_HYP partial_bound) th0;;
1153
1154
1155 (* m_decr_pass *)
1156 let m_decr_pass n pp j m_taylor_th pass_th0 =
1157 let _, diff2_th, _, _ = dest_m_taylor_thms n m_taylor_th in
1158 let partial_bound = eval_m_taylor_partial_upper n pp j m_taylor_th in
1159
1160 let f_tm, domain0 = dest_m_cell_pass (concl pass_th0) and
1161 domain = (rand o rator o concl) diff2_th and
1162 hi_tm = (rand o rand o snd o dest_forall o concl) partial_bound in
1163 let hi_le0_th = EQT_ELIM (float_le0 hi_tm) in
1164
1165 let x_tm, z_tm = dest_pair domain in
1166 let xs = dest_vector x_tm and
1167 zs = dest_vector z_tm in
1168
1169 let x_vars = map (fun i -> x_vars_array.(i)) (1--n) and
1170 z_vars = map (fun i -> z_vars_array.(i)) (1--n) and
1171 f_var = mk_var ("f", type_of f_tm) in
1172 let th0 = (INST[f_tm, f_var; hi_tm, hi_var_real] o
1173 INST (zip zs z_vars) o INST (zip xs x_vars)) decr_thms_array.(n).(j) in
1174 (MY_PROVE_HYP hi_le0_th o MY_PROVE_HYP pass_th0 o
1175 MY_PROVE_HYP diff2_th o MY_PROVE_HYP partial_bound) th0;;
1176
1177 (*************************)
1178
1179 (* m_convex_pass *)
1180 let m_convex_pass n j diff2_th partial2_bound_th pass1_th pass2_th =
1181 let f_tm, domain1 = dest_m_cell_pass (concl pass1_th) and
1182 _, domain2 = dest_m_cell_pass (concl pass2_th) in
1183 let x_tm, _ = dest_pair domain1 and
1184 _, z_tm = dest_pair domain2 and
1185 bound_tm = (lhand o rand o snd o dest_forall o concl) partial2_bound_th in
1186
1187 let xs = dest_vector x_tm and
1188 zs = dest_vector z_tm in
1189
1190 let x_vars = map (fun i -> x_vars_array.(i)) (1--n) and
1191 z_vars = map (fun i -> z_vars_array.(i)) (1--n) and
1192 f_var = mk_var ("f", type_of f_tm) in
1193
1194 let le_th0 = float_ge0 bound_tm in
1195 let le_th =
1196 try EQT_ELIM le_th0 with Failure _ -> failwith ("m_convex_pass: "^string_of_thm le_th0) in
1197
1198 let th0 = (INST[f_tm, f_var; bound_tm, lo_var_real] o
1199 INST (zip xs x_vars) o INST (zip zs z_vars)) convex_thms_array.(n).(j) in
1200 (MY_PROVE_HYP le_th o MY_PROVE_HYP pass1_th o MY_PROVE_HYP pass2_th o
1201 MY_PROVE_HYP diff2_th o MY_PROVE_HYP partial2_bound_th) th0;;
1202
1203
1204
1205
1206 (***********************)
1207
1208 (* split_domain *)
1209
1210 let split_domain n pp j domain_th =
1211 let domain_tm, y_tm, _ = dest_m_cell_domain (concl domain_th) in
1212 let x_tm, z_tm = dest_pair domain_tm in
1213 let xs = dest_vector x_tm and
1214 zs = dest_vector z_tm and
1215 t = List.nth (dest_vector y_tm) (j - 1) in
1216
1217 let vv = map (fun i -> if i = j then t else List.nth zs (i - 1)) (1--n) and
1218 uu = map (fun i -> if i = j then t else List.nth xs (i - 1)) (1--n) in
1219
1220 let domain1_th = mk_m_center_domain n pp (rand x_tm) (mk_list (vv, real_ty)) and
1221 domain2_th = mk_m_center_domain n pp (mk_list (uu, real_ty)) (rand z_tm) in
1222 domain1_th, domain2_th;;
1223
1224
1225 (* restrict_domain *)
1226
1227 let restrict_domain n j left_flag domain_th =
1228 let domain_tm, y_tm, w_tm = dest_m_cell_domain (concl domain_th) in
1229 let x_tm, z_tm = dest_pair domain_tm in
1230 let xs = dest_vector x_tm and
1231 zs = dest_vector z_tm and
1232 ys = dest_vector y_tm and
1233 ws = dest_vector w_tm in
1234
1235 let th0 = (INST (zip xs (mk_real_vars n "x")) o INST (zip zs (mk_real_vars n "z")) o
1236 INST (zip ys (mk_real_vars n "y")) o INST (zip ws (mk_real_vars n "w")))
1237 (if left_flag then left_restrict_thms_array.(n).(j) else right_restrict_thms_array.(n).(j)) in
1238 let ths = CONJUNCTS (MY_PROVE_HYP domain_th th0) in
1239 hd ths, hd (tl ths);;
1240
1241
1242
1243
1244 (****************************************)
1245
1246 let m_verify_raw (report_start, total_size) n pp fs certificate domain_th0 th_list =
1247 let r_size = result_size certificate in
1248 let r_size2 = float_of_int (if total_size > 0 then total_size else (if r_size > 0 then r_size else 1)) in
1249 let k = ref 0 in
1250 let kk = ref report_start in
1251 let last_report = ref (int_of_float (float_of_int !kk /. r_size2 *. 100.0)) in
1252
1253 let rec rec_verify =
1254 let rec apply_trans sub_ths th0 acc =
1255 match sub_ths with
1256 | [] -> rev acc
1257 | th :: ths ->
1258 let th' = eval_subset_trans th th0 in
1259 apply_trans ths th' (th' :: acc) in
1260
1261 let rec mk_domains mono th0 acc =
1262 match mono with
1263 | [] -> rev acc
1264 | m :: ms ->
1265 let j, flag = m.variable, m.decr_flag in
1266 let ths = restrict_domain n j flag th0 in
1267 mk_domains ms (fst ths) (ths :: acc) in
1268
1269 let verify_mono mono domain_th certificate =
1270 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1271 let xx, zz = dest_pair domain in
1272 let df0_flags = itlist (fun m b -> m.df0_flag && b) mono true in
1273 let _ = !info_print_level < 2 || (report (sprintf "df0_flags = %b" df0_flags); true) in
1274 let taylor_th, diff2_th =
1275 if df0_flags then
1276 TRUTH, fs.diff2_f xx zz
1277 else
1278 let t_th = fs.taylor pp pp domain_th in
1279 let _, d_th, _, _ = dest_m_taylor_thms n t_th in
1280 t_th, d_th in
1281
1282 let domain_ths = mk_domains mono domain_th [] in
1283 (* let domains = domain_th :: map fst (butlast domain_ths) in *)
1284
1285 (* let gen_mono (m, domain_th) = *)
1286 let gen_mono m =
1287 if m.df0_flag then
1288 if m.decr_flag then
1289 eval_interval_arith_hi n (fs.df m.variable pp xx zz)
1290 else
1291 eval_interval_arith_lo n (fs.df m.variable pp xx zz)
1292 else
1293 if m.decr_flag then
1294 eval_m_taylor_partial_upper n pp m.variable taylor_th
1295 else
1296 eval_m_taylor_partial_lower n pp m.variable taylor_th in
1297
1298 (* let mono_ths = map gen_mono (zip mono domains) in *)
1299 let mono_ths = map gen_mono mono in
1300 let pass_th0 = rec_verify ((fst o last) domain_ths) certificate in
1301 let sub_th0 = (eval_subset_refl o rand o concl o snd o hd) domain_ths in
1302 let sub_ths = apply_trans (sub_th0 :: map snd (butlast domain_ths)) sub_th0 [] in
1303 let th = rev_itlist (fun ((m, mono_th), sub_th) pass_th ->
1304 let j, flag = m.variable, m.decr_flag in
1305 m_mono_pass_gen n j flag diff2_th mono_th sub_th pass_th)
1306 (rev (zip (zip mono mono_ths) sub_ths)) pass_th0 in
1307 if hyp th <> [] then failwith ("hyp <> []: "^string_of_thm th) else th in
1308
1309
1310
1311 fun domain_th certificate ->
1312 match certificate with
1313 | Result_mono (mono, r1) ->
1314 let _ = !info_print_level < 2 ||
1315 (let mono_strs =
1316 map (fun m -> sprintf "%s%d (%b)" (if m.decr_flag then "-" else "")
1317 m.variable m.df0_flag) mono in
1318 report (sprintf "Mono: [%s]" (String.concat ";" mono_strs)); true) in
1319 verify_mono mono domain_th r1
1320
1321 | Result_pass (_, f0_flag) ->
1322 let _ = k := !k + 1 in
1323 let _ = !info_print_level < 2 ||
1324 (report (sprintf "Verifying: %d/%d (f0_flag = %b)" !k r_size f0_flag); true) in
1325 let _ = !info_print_level < 1 ||
1326 (let r = int_of_float (float_of_int !kk /. r_size2 *. 100.0) in
1327 let _ = if r <> !last_report then (last_report := r; report0 (sprintf "%d " r)) else () in true) in
1328 if f0_flag then
1329 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1330 let xx, zz = dest_pair domain in
1331 m_taylor_cell_pass0 n (fs.f pp xx zz)
1332 else
1333 let taylor_th = fs.taylor pp pp domain_th in
1334 m_taylor_cell_pass n pp taylor_th
1335
1336 | Result_glue (i, convex_flag, r1, r2) ->
1337 let domain1_th, domain2_th =
1338 if convex_flag then
1339 let d1, _ = restrict_domain n (i + 1) true domain_th in
1340 let d2, _ = restrict_domain n (i + 1) false domain_th in
1341 d1, d2
1342 else
1343 split_domain n pp (i + 1) domain_th in
1344 let th1 = rec_verify domain1_th r1 in
1345 let th2 = rec_verify domain2_th r2 in
1346 if convex_flag then
1347 let _ = !info_print_level < 2 || (report (sprintf "GlueConvex: %d" (i + 1)); true) in
1348 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1349 let xx, zz = dest_pair domain in
1350 let diff2_th = fs.diff2_f xx zz in
1351 let partial2_th = fs.ddf (i + 1) (i + 1) pp xx zz in
1352 let lo_partial2_th = eval_interval_arith_lo n partial2_th in
1353 m_convex_pass n (i + 1) diff2_th lo_partial2_th th1 th2
1354 else
1355 m_glue_cells n (i + 1) th1 th2
1356
1357 | Result_pass_ref i ->
1358 let _ = !info_print_level < 2 || (report (sprintf "Ref: %d" i); true) in
1359 if i > 0 then
1360 List.nth th_list (i - 1)
1361 else
1362 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1363 let pass_th = List.nth th_list (-i - 1) in
1364 m_cell_pass_subdomain domain pass_th
1365
1366 | _ -> failwith "False result" in
1367
1368 rec_verify domain_th0 certificate;;
1369
1370
1371 (*****************)
1372
1373
1374 let m_verify_raw0 n pp fs certificate xx zz =
1375 m_verify_raw (0, 0) n pp fs certificate (mk_m_center_domain n pp xx zz) [];;
1376
1377
1378
1379 let m_verify_list n pp fs certificate_list xx zz =
1380 let domain_hash = Hashtbl.create (length certificate_list * 10) in
1381 let mem, find, add = Hashtbl.mem domain_hash,
1382 Hashtbl.find domain_hash, Hashtbl.add domain_hash in
1383
1384 let get_m_cell_domain n pp domain0 path =
1385 let rec get_rec domain_th path hash =
1386 match path with
1387 | [] -> domain_th
1388 | (s, j) :: ps ->
1389 let hash' = hash^s^(string_of_int j) in
1390 if mem hash' then
1391 get_rec (find hash') ps hash'
1392 else
1393 if s = "l" || s = "r" then
1394 let domain1_th, domain2_th = split_domain n pp j domain_th in
1395 let hash1 = hash^"l"^(string_of_int j) and
1396 hash2 = hash^"r"^(string_of_int j) in
1397 let _ = add hash1 domain1_th; add hash2 domain2_th in
1398 if s = "l" then
1399 get_rec domain1_th ps hash'
1400 else
1401 get_rec domain2_th ps hash'
1402 else
1403 let l_flag = (s = "ml") in
1404 let domain_th', _ = restrict_domain n j l_flag domain_th in
1405 let _ = add hash' domain_th' in
1406 get_rec domain_th' ps hash' in
1407 get_rec domain0 path "" in
1408
1409 let domain_th0 = mk_m_center_domain n pp xx zz in
1410 let size = length certificate_list in
1411 let k = ref 0 in
1412 let kk = ref 0 in
1413 let total_size = end_itlist (+) (map (result_size o snd) certificate_list) in
1414
1415 let rec rec_verify certificate_list th_list =
1416 match certificate_list with
1417 | [] -> last th_list
1418 | (path, certificate) :: cs ->
1419 let _ = k := !k + 1 in
1420 let _ = !info_print_level < 2 || (report (sprintf "List: %d/%d" !k size); true) in
1421 let domain_th = get_m_cell_domain n pp domain_th0 path in
1422 let th = m_verify_raw (!kk, total_size) n pp fs certificate domain_th th_list in
1423 let _ = kk := !kk + result_size certificate in
1424 rec_verify cs (th_list @ [th]) in
1425 rec_verify certificate_list [];;
1426
1427
1428 (***************************)
1429 (* Verification based on a p_result_tree *)
1430
1431 let m_p_verify_raw (report_start, total_size) n p_split fs certificate domain_th0 th_list =
1432 let r_size = p_result_size certificate in
1433 let r_size2 = float_of_int (if total_size > 0 then total_size else (if r_size > 0 then r_size else 1)) in
1434 let k = ref 0 in
1435 let kk = ref report_start in
1436 let last_report = ref (int_of_float (float_of_int !kk /. r_size2 *. 100.0)) in
1437
1438 let rec rec_verify =
1439 let rec apply_trans sub_ths th0 acc =
1440 match sub_ths with
1441 | [] -> rev acc
1442 | th :: ths ->
1443 let th' = eval_subset_trans th th0 in
1444 apply_trans ths th' (th' :: acc) in
1445
1446 let rec mk_domains mono th0 acc =
1447 match mono with
1448 | [] -> rev acc
1449 | m :: ms ->
1450 let j, flag = m.variable, m.decr_flag in
1451 let ths = restrict_domain n j flag th0 in
1452 mk_domains ms (fst ths) (ths :: acc) in
1453
1454 let verify_mono p_stat mono domain_th certificate =
1455 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1456 let xx, zz = dest_pair domain in
1457 let df0_flags = itlist (fun m b -> m.df0_flag && b) mono true in
1458 let _ = !info_print_level < 2 || (report (sprintf "df0_flags = %b" df0_flags); true) in
1459 let taylor_th, diff2_th =
1460 if df0_flags then
1461 TRUTH, fs.diff2_f xx zz
1462 else
1463 let t_th = fs.taylor p_stat.pp p_stat.pp domain_th in
1464 let _, d_th, _, _ = dest_m_taylor_thms n t_th in
1465 t_th, d_th in
1466
1467 let domain_ths = mk_domains mono domain_th [] in
1468 let gen_mono m =
1469 if m.df0_flag then
1470 if m.decr_flag then
1471 eval_interval_arith_hi n (fs.df m.variable p_stat.pp xx zz)
1472 else
1473 eval_interval_arith_lo n (fs.df m.variable p_stat.pp xx zz)
1474 else
1475 if m.decr_flag then
1476 eval_m_taylor_partial_upper n p_stat.pp m.variable taylor_th
1477 else
1478 eval_m_taylor_partial_lower n p_stat.pp m.variable taylor_th in
1479 let mono_ths = map gen_mono mono in
1480 let pass_th0 = rec_verify ((fst o last) domain_ths) certificate in
1481 let sub_th0 = (eval_subset_refl o rand o concl o snd o hd) domain_ths in
1482 let sub_ths = apply_trans (sub_th0 :: map snd (butlast domain_ths)) sub_th0 [] in
1483 let th = rev_itlist (fun ((m, mono_th), sub_th) pass_th ->
1484 let j, flag = m.variable, m.decr_flag in
1485 m_mono_pass_gen n j flag diff2_th mono_th sub_th pass_th)
1486 (rev (zip (zip mono mono_ths) sub_ths)) pass_th0 in
1487 if hyp th <> [] then failwith ("hyp <> []: "^string_of_thm th) else th in
1488
1489
1490
1491 fun domain_th certificate ->
1492 match certificate with
1493 | P_result_mono (p_stat, mono, r1) ->
1494 let _ = !info_print_level < 2 ||
1495 (let mono_strs =
1496 map (fun m -> sprintf "%s%d (%b)" (if m.decr_flag then "-" else "")
1497 m.variable m.df0_flag) mono in
1498 report (sprintf "Mono: [%s]" (String.concat ";" mono_strs)); true) in
1499 verify_mono p_stat mono domain_th r1
1500
1501 | P_result_pass (p_stat, _, f0_flag) ->
1502 let _ = k := !k + 1; kk := !kk + 1 in
1503 let _ = !info_print_level < 2 ||
1504 (report (sprintf "Verifying: %d/%d (f0_flag = %b)" !k r_size f0_flag); true) in
1505 let _ = !info_print_level <> 1 ||
1506 (let r = int_of_float (float_of_int !kk /. r_size2 *. 100.0) in
1507 let _ = if r <> !last_report then (last_report := r; report0 (sprintf "%d " r)) else () in true) in
1508 if f0_flag then
1509 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1510 let xx, zz = dest_pair domain in
1511 m_taylor_cell_pass0 n (fs.f p_stat.pp xx zz)
1512 else
1513 let taylor_th = fs.taylor p_stat.pp p_stat.pp domain_th in
1514 m_taylor_cell_pass n p_stat.pp taylor_th
1515
1516 | P_result_glue (p_stat, i, convex_flag, r1, r2) ->
1517 let domain1_th, domain2_th =
1518 if convex_flag then
1519 let d1, _ = restrict_domain n (i + 1) true domain_th in
1520 let d2, _ = restrict_domain n (i + 1) false domain_th in
1521 d1, d2
1522 else
1523 split_domain n p_split (i + 1) domain_th in
1524 let th1 = rec_verify domain1_th r1 in
1525 let th2 = rec_verify domain2_th r2 in
1526 if convex_flag then
1527 let _ = !info_print_level < 2 || (report (sprintf "GlueConvex: %d" (i + 1)); true) in
1528 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1529 let xx, zz = dest_pair domain in
1530 let diff2_th = fs.diff2_f xx zz in
1531 let partial2_th = fs.ddf (i + 1) (i + 1) p_stat.pp xx zz in
1532 let lo_partial2_th = eval_interval_arith_lo n partial2_th in
1533 m_convex_pass n (i + 1) diff2_th lo_partial2_th th1 th2
1534 else
1535 m_glue_cells n (i + 1) th1 th2
1536
1537 | P_result_ref i ->
1538 let _ = !info_print_level < 2 || (report (sprintf "Ref: %d" i); true) in
1539 if i > 0 then
1540 List.nth th_list (i - 1)
1541 else
1542 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1543 let pass_th = List.nth th_list (-i - 1) in
1544 m_cell_pass_subdomain domain pass_th in
1545
1546 rec_verify domain_th0 certificate;;
1547
1548 (*****************)
1549
1550 let m_p_verify_raw0 n p_split fs certificate xx zz =
1551 m_p_verify_raw (0, 0) n p_split fs certificate (mk_m_center_domain n p_split xx zz) [];;
1552
1553
1554
1555 let m_p_verify_list n p_split fs certificate_list xx zz =
1556 let domain_hash = Hashtbl.create (length certificate_list * 10) in
1557 let mem, find, add = Hashtbl.mem domain_hash,
1558 Hashtbl.find domain_hash, Hashtbl.add domain_hash in
1559
1560 let get_m_cell_domain n pp domain0 path =
1561 let rec get_rec domain_th path hash =
1562 match path with
1563 | [] -> domain_th
1564 | (s, j) :: ps ->
1565 let hash' = hash^s^(string_of_int j) in
1566 if mem hash' then
1567 get_rec (find hash') ps hash'
1568 else
1569 if s = "l" || s = "r" then
1570 let domain1_th, domain2_th = split_domain n pp j domain_th in
1571 let hash1 = hash^"l"^(string_of_int j) and
1572 hash2 = hash^"r"^(string_of_int j) in
1573 let _ = add hash1 domain1_th; add hash2 domain2_th in
1574 if s = "l" then
1575 get_rec domain1_th ps hash'
1576 else
1577 get_rec domain2_th ps hash'
1578 else
1579 let l_flag = (s = "ml") in
1580 let domain_th', _ = restrict_domain n j l_flag domain_th in
1581 let _ = add hash' domain_th' in
1582 get_rec domain_th' ps hash' in
1583 get_rec domain0 path "" in
1584
1585 let domain_th0 = mk_m_center_domain n p_split xx zz in
1586 let size = length certificate_list in
1587 let k = ref 0 in
1588 let kk = ref 0 in
1589 let total_size = end_itlist (+) (map (p_result_size o snd) certificate_list) in
1590
1591 let rec rec_verify certificate_list th_list =
1592 match certificate_list with
1593 | [] -> last th_list
1594 | (path, certificate) :: cs ->
1595 let _ = k := !k + 1 in
1596 let _ = !info_print_level < 2 || (report (sprintf "List: %d/%d" !k size); true) in
1597 let domain_th = get_m_cell_domain n p_split domain_th0 path in
1598 let th = m_p_verify_raw (!kk, total_size) n p_split fs certificate domain_th th_list in
1599 let _ = kk := !kk + p_result_size certificate in
1600 rec_verify cs (th_list @ [th]) in
1601 rec_verify certificate_list [];;
1602
1603
1604 (*************************************)
1605 (* disjunctions *)
1606
1607
1608 let m_verify_disj_raw (report_start, total_size) n pp fs_list certificate domain_th0 th_list =
1609 let r_size = result_size certificate in
1610 let r_size2 = float_of_int (if total_size > 0 then total_size else (if r_size > 0 then r_size else 1)) in
1611 let k = ref 0 in
1612 let kk = ref report_start in
1613 let last_report = ref (int_of_float (float_of_int !kk /. r_size2 *. 100.0)) in
1614
1615 let rec rec_verify =
1616 let rec apply_trans sub_ths th0 acc =
1617 match sub_ths with
1618 | [] -> rev acc
1619 | th :: ths ->
1620 let th' = eval_subset_trans th th0 in
1621 apply_trans ths th' (th' :: acc) in
1622
1623 let rec mk_domains mono th0 acc =
1624 match mono with
1625 | [] -> rev acc
1626 | m :: ms ->
1627 let j, flag = m.variable, m.decr_flag in
1628 let ths = restrict_domain n j flag th0 in
1629 mk_domains ms (fst ths) (ths :: acc) in
1630 (*
1631 let verify_mono mono domain_th certificate =
1632 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1633 let xx, zz = dest_pair domain in
1634 let df0_flags = itlist (fun m b -> m.df0_flag && b) mono true in
1635 let _ = !info_print_level < 2 || (report (sprintf "df0_flags = %b" df0_flags); true) in
1636 let taylor_th, diff2_th =
1637 if df0_flags then
1638 TRUTH, fs.diff2_f xx zz
1639 else
1640 let t_th = fs.taylor pp pp domain_th in
1641 let _, d_th, _, _ = dest_m_taylor_thms n t_th in
1642 t_th, d_th in
1643
1644 let domain_ths = mk_domains mono domain_th [] in
1645 (* let domains = domain_th :: map fst (butlast domain_ths) in *)
1646
1647 (* let gen_mono (m, domain_th) = *)
1648 let gen_mono m =
1649 if m.df0_flag then
1650 if m.decr_flag then
1651 eval_interval_arith_hi n (fs.df m.variable pp xx zz)
1652 else
1653 eval_interval_arith_lo n (fs.df m.variable pp xx zz)
1654 else
1655 if m.decr_flag then
1656 eval_m_taylor_partial_upper n pp m.variable taylor_th
1657 else
1658 eval_m_taylor_partial_lower n pp m.variable taylor_th in
1659
1660 (* let mono_ths = map gen_mono (zip mono domains) in *)
1661 let mono_ths = map gen_mono mono in
1662 let pass_th0 = rec_verify ((fst o last) domain_ths) certificate in
1663 let sub_th0 = (eval_subset_refl o rand o concl o snd o hd) domain_ths in
1664 let sub_ths = apply_trans (sub_th0 :: map snd (butlast domain_ths)) sub_th0 [] in
1665 let th = rev_itlist (fun ((m, mono_th), sub_th) pass_th ->
1666 let j, flag = m.variable, m.decr_flag in
1667 m_mono_pass_gen n j flag diff2_th mono_th sub_th pass_th)
1668 (rev (zip (zip mono mono_ths) sub_ths)) pass_th0 in
1669 if hyp th <> [] then failwith ("hyp <> []: "^string_of_thm th) else th in
1670 *)
1671
1672
1673 fun domain_th certificate ->
1674 match certificate with
1675 | Result_mono (mono, r1) ->
1676 failwith "Mono: not implemented"
1677 (*
1678 let _ = !info_print_level < 2 ||
1679 (let mono_strs =
1680 map (fun m -> sprintf "%s%d (%b)" (if m.decr_flag then "-" else "")
1681 m.variable m.df0_flag) mono in
1682 report (sprintf "Mono: [%s]" (String.concat ";" mono_strs)); true) in
1683 verify_mono mono domain_th r1
1684 *)
1685
1686 | Result_pass (j, f0_flag) ->
1687 let _ = k := !k + 1 in
1688 let _ = !info_print_level < 2 ||
1689 (report (sprintf "Verifying: %d/%d (f0_flag = %b)" !k r_size f0_flag); true) in
1690 let _ = !info_print_level < 1 ||
1691 (let r = int_of_float (float_of_int !kk /. r_size2 *. 100.0) in
1692 let _ = if r <> !last_report then (last_report := r; report0 (sprintf "%d " r)) else () in true) in
1693
1694 let fs = List.nth fs_list j in
1695 if f0_flag then
1696 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1697 let xx, zz = dest_pair domain in
1698 m_taylor_cell_list_pass0 n (fs.f pp xx zz)
1699 else
1700 let taylor_th = fs.taylor pp pp domain_th in
1701 m_taylor_cell_list_pass n pp taylor_th
1702
1703 | Result_glue (i, convex_flag, r1, r2) ->
1704 let domain1_th, domain2_th =
1705 if convex_flag then
1706 let d1, _ = restrict_domain n (i + 1) true domain_th in
1707 let d2, _ = restrict_domain n (i + 1) false domain_th in
1708 d1, d2
1709 else
1710 split_domain n pp (i + 1) domain_th in
1711 let th1 = rec_verify domain1_th r1 in
1712 let th2 = rec_verify domain2_th r2 in
1713 if convex_flag then
1714 failwith "convexity: not implemented"
1715 (*
1716 let _ = !info_print_level < 2 || (report (sprintf "GlueConvex: %d" (i + 1)); true) in
1717 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1718 let xx, zz = dest_pair domain in
1719 let diff2_th = fs.diff2_f xx zz in
1720 let partial2_th = fs.ddf (i + 1) (i + 1) pp xx zz in
1721 let lo_partial2_th = eval_interval_arith_lo n partial2_th in
1722 m_convex_pass n (i + 1) diff2_th lo_partial2_th th1 th2
1723 *)
1724 else
1725 let th0 = m_glue_cells_list n (i + 1) th1 th2 in
1726 merge_m_cell_list_pass n th0
1727
1728 | Result_pass_ref i ->
1729 let _ = !info_print_level < 2 || (report (sprintf "Ref: %d" i); true) in
1730 if i > 0 then
1731 List.nth th_list (i - 1)
1732 else
1733 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1734 let pass_th = List.nth th_list (-i - 1) in
1735 m_cell_list_pass_subdomain domain pass_th
1736
1737 | _ -> failwith "False result" in
1738
1739 rec_verify domain_th0 certificate;;
1740
1741
1742 (*****************)
1743
1744 let m_verify_disj_raw0 n pp fs_list certificate xx zz =
1745 m_verify_disj_raw (0, 0) n pp fs_list certificate (mk_m_center_domain n pp xx zz) [];;
1746
1747
1748 (******************************)
1749 (* m_p_verify_disj *)
1750
1751 let m_p_verify_disj_raw (report_start, total_size) n p_split fs_list certificate domain_th0 th_list =
1752 let r_size = p_result_size certificate in
1753 let r_size2 = float_of_int (if total_size > 0 then total_size else (if r_size > 0 then r_size else 1)) in
1754 let k = ref 0 in
1755 let kk = ref report_start in
1756 let last_report = ref (int_of_float (float_of_int !kk /. r_size2 *. 100.0)) in
1757
1758 let rec rec_verify =
1759 fun domain_th certificate ->
1760 match certificate with
1761 | P_result_mono (p_stat, mono, r1) ->
1762 failwith "Mono: not implemented"
1763
1764 | P_result_pass (p_stat, j, f0_flag) ->
1765 let _ = k := !k + 1; kk := !kk + 1 in
1766 let _ = !info_print_level < 2 ||
1767 (report (sprintf "Verifying: %d/%d (f0_flag = %b)" !k r_size f0_flag); true) in
1768 let _ = !info_print_level <> 1 ||
1769 (let r = int_of_float (float_of_int !kk /. r_size2 *. 100.0) in
1770 let _ = if r <> !last_report then (last_report := r; report0 (sprintf "%d " r)) else () in true) in
1771 let fs = List.nth fs_list j in
1772 if f0_flag then
1773 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1774 let xx, zz = dest_pair domain in
1775 m_taylor_cell_list_pass0 n (fs.f p_stat.pp xx zz)
1776 else
1777 let taylor_th = fs.taylor p_stat.pp p_stat.pp domain_th in
1778 m_taylor_cell_list_pass n p_stat.pp taylor_th
1779
1780 | P_result_glue (p_stat, i, convex_flag, r1, r2) ->
1781 let domain1_th, domain2_th =
1782 if convex_flag then
1783 let d1, _ = restrict_domain n (i + 1) true domain_th in
1784 let d2, _ = restrict_domain n (i + 1) false domain_th in
1785 d1, d2
1786 else
1787 split_domain n p_split (i + 1) domain_th in
1788 let th1 = rec_verify domain1_th r1 in
1789 let th2 = rec_verify domain2_th r2 in
1790 if convex_flag then
1791 failwith "convexity: not implemented"
1792 else
1793 let th0 = m_glue_cells_list n (i + 1) th1 th2 in
1794 merge_m_cell_list_pass n th0
1795
1796 | P_result_ref i ->
1797 let _ = !info_print_level < 2 || (report (sprintf "Ref: %d" i); true) in
1798 if i > 0 then
1799 List.nth th_list (i - 1)
1800 else
1801 let domain, _, _ = (dest_m_cell_domain o concl) domain_th in
1802 let pass_th = List.nth th_list (-i - 1) in
1803 m_cell_list_pass_subdomain domain pass_th
1804
1805 | _ -> failwith "False result"
1806 in
1807 rec_verify domain_th0 certificate;;
1808
1809 (******************)
1810 let m_p_verify_disj_raw0 n p_split fs_list certificate xx zz =
1811 m_p_verify_disj_raw (0, 0) n p_split fs_list certificate (mk_m_center_domain n p_split xx zz) [];;
1812
1813
1814 end;;
1815
1816 (*
1817 m_verify_list_raw0 2 pp [formal_f1; formal_f2] cert xx_float_tm zz_float_tm;;
1818 *)