Common — library colibrilib.union — module Union
1
module Union
2
use int.Int
3
use bool.Bool
4
use option.Option
5
use colibrilib.bound.Bound
6
use real.RealInfix
7
8
scope Make
9
use colibrilib.stda.StdA as Q
10
use colibrilib.q.Real as Real
11
use real.Square
12
13
14
type
t''
=
15
|
Sin
Q.t t''
16
|
Chg
Q.t Bound.t t''
17
|
Inf
18
19
type
t'
=
20
|
On
t''
21
|
Off
t''
22
23
function
on
(x:t') : bool = match x with On _ -> True | Off _ -> False end
24
function
in_
(x:t') : t'' = match x with On a | Off a -> a end
25
26
function
length'
(l:t'') : int =
27
match l with
28
| Sin _ l ->
29
length' l + 1
30
| Chg _ _ l ->
31
length' l + 1
32
| Inf -> 0
33
end
34
Valid (16ms) (cvc5)
35
let rec lemma
pos_length'
(l:t'')
36
ensures { length' l >= 0 } =
37
match l with
38
| Sin _ l -> pos_length' l
39
| Chg _ _ l ->
40
pos_length' l
41
| Inf -> ()
42
end
43
44
function
length
(l:t') : int =
45
match l with
46
| On l ->
47
length' l + 1
48
| Off l ->
49
length' l
50
end
51
52
type
infr
=
53
|
R
real
54
|
I
(* positive or negative infinity depending of the side *)
55
56
predicate
lt_sup
(r1:infr) (r2:infr) =
57
match r1,r2 with
58
| R r1, R r2 -> r1 <. r2
59
| I, _ -> false
60
| _, I -> true
61
end
62
63
predicate
le_sup
(r1:infr) (r2:infr) =
64
match r1,r2 with
65
| R r1, R r2 -> r1 <=. r2
66
| I, I -> true
67
| I, _ -> false
68
| _, I -> true
69
end
70
71
use real.MinMax
72
73
function
min_sup
(r1:infr) (r2:infr) : infr =
74
match r1,r2 with
75
| R r1, R r2 -> R (min r1 r2)
76
| I, I -> I
77
| I, _ -> r2
78
| _, I -> r1
79
end
80
81
predicate
r1_lt_sup
(r1:real) (r2:infr) =
82
match r2 with
83
| R r2 -> r1 <. r2
84
| I -> true
85
end
86
87
function
bound
(l:t'') : infr =
88
match l with
89
| Sin q _ -> R q
90
| Chg q _ _ -> R q
91
| Inf -> I
92
end
93
94
predicate
lt_bound'
(x:real) (l:t'') =
95
r1_lt_sup x (bound l)
96
97
predicate
lt_bound
(x:real) (l:t') =
98
match l with
99
| On l -> lt_bound' x l
100
| Off l -> lt_bound' x l
101
end
102
103
predicate
le_bound'
(x:real) (l:t'') =
104
match l with
105
| Sin q _ ->
106
x <=. q
107
| Chg q _ _ ->
108
x <=. q
109
| Inf -> true
110
end
111
112
predicate
le_bound
(x:real) (l:t') =
113
match l with
114
| On l -> le_bound' x l
115
| Off l -> le_bound' x l
116
end
117
118
119
predicate
le_infr
(r1:infr) (r2:infr) =
120
match r1,r2 with
121
| R r1, R r2 -> r1 <=. r2
122
| I, _ -> true
123
| _, I -> true
124
end
125
126
predicate
lt_infr
(r1:infr) (r2:infr) =
127
match r1,r2 with
128
| R r1, R r2 -> r1 <. r2
129
| I, _ -> true
130
| _, I -> true
131
end
132
133
predicate
le_sup_infr
(r1:infr) (r2:infr) =
134
match r1,r2 with
135
| _, I -> true
136
| R r1, R r2 -> r1 <=. r2
137
| I, R _ -> false
138
end
139
140
141
function
infr_bound'
(r2:t'') : infr =
142
match r2 with
143
| Sin r1 _ | Chg r1 _ _ -> R r1
144
| Inf -> I
145
end
146
147
function
infr_bound
(r2:t') : infr =
148
match r2 with
149
| On a | Off a -> infr_bound' a
150
end
151
152
use real.MinMax
153
154
function
le_min_sup_infr
(r1:infr) (r2:infr) : infr =
155
match r1,r2 with
156
| I, I -> I
157
| R r1, R r2 -> R (min r1 r2)
158
| R _, I -> r1
159
| I, R _ -> r2
160
end
161
162
predicate
lt_infr_bound'
(r1:infr) (r2:t'') =
163
lt_infr r1 (infr_bound' r2)
164
165
predicate
le_infr_bound'
(r1:infr) (r2:t'') =
166
le_infr r1 (infr_bound' r2)
167
168
predicate
le_infr_bound
(r1:infr) (r2:t') =
169
match r2 with
170
| On _ -> r1 = I
171
| Off r2 -> le_infr_bound' r1 r2
172
end
173
174
175
predicate
in_infr
(r1:infr) (r:real) (r2:infr) =
176
le_infr r1 (R r) /\ le_infr (R r) r2
177
178
179
predicate
ordered'
(l:t'') =
180
match l with
181
| Sin q l ->
182
lt_bound' q l /\
183
ordered' l
184
| Chg q _ l ->
185
lt_bound' q l /\
186
ordered' l
187
| Inf -> true
188
end
189
190
predicate
ordered
(l:t') =
191
match l with
192
| On l -> ordered' l
193
| Off l -> ordered' l
194
end
195
Valid (17ms) (cvc5)
196
type
t
= {
a
: t' }
197
invariant { ordered a }
198
invariant {
199
a <> Off Inf
200
}
201
by { a = On Inf }
202
203
predicate
cmp
(x:real) (b:Bound.t) (y:real) =
204
match b with
205
| Bound.Large -> x <=. y
206
| Bound.Strict -> x <. y
207
end
208
209
predicate
mem_on
(x:real) (l:t'') =
210
match l with
211
| Sin q l ->
212
x <. q \/ (q <. x /\ mem_on x l)
213
| Chg q b l ->
214
not (cmp q b x) \/ (cmp q b x /\ not (mem_on x l))
215
| Inf -> true
216
end
217
218
predicate
mem_if
(if_:bool) (x:real) (l:t'') =
219
match l with
220
| Sin q l ->
221
if q <. x then mem_if if_ x l else (if if_ then x <. q else x = q)
222
| Chg q b l ->
223
if cmp q b x then mem_if (notb if_) x l else if_
224
| Inf -> if_
225
end
226
Valid (25ms) (cvc5)
227
let rec ghost
mem_if_def
(if_:bool) (x:real) (l:t'')
228
ensures { mem_if if_ x l <-> if if_ then mem_on x l else not (mem_on x l) }
229
variant { l } =
230
match l with
231
| Sin _ l -> mem_if_def if_ x l
232
| Chg _ _ l -> mem_if_def (not if_) x l
233
| Inf -> ()
234
end
235
236
predicate
mem
(x:real) (l:t') =
237
match l with
238
| On l ->
239
mem_if True x l
240
| Off l ->
241
mem_if False x l
242
end

The membership in an abstract value, for the shapes of spec.Sound

245
predicate
memt
(x:real) (u:t) = mem x u.a
246
247
use colibrilib.spec.Sound
248
use colibrilib.spec.Opt
249
use colibrilib.spec.Test
250
Valid (325ms) (cvc5)
251
let ghost
not_bottom'
(if_:bool) (l:t'') : real
252
requires { ordered' l }
253
requires { l = Inf -> if_ }
254
ensures { mem_if if_ result l } =
255
if if_ then
256
match l with
257
| (Sin q _) -> (Q.real q-.1.)
258
| (Chg q _ _) -> (Q.real q-.1.) (* Must be before *)
259
| Inf -> 0.
260
end
261
else
262
match l with
263
| (Sin q _) -> Q.real q
264
| (Chg q _ (Sin q' _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)
265
| (Chg q _ (Chg q' _ _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)
266
| (Chg q _ Inf) -> (Q.real q+.1.)
267
| Inf -> absurd
268
end
269
270
Valid (25ms) (cvc5)
271
let ghost
lt_bound_exists
(if_:bool) (l:t'') : real
272
requires { ordered' l }
273
ensures { if_ <-> mem_if if_ result l }
274
ensures { lt_bound' result l }
275
=
276
match l with
277
| (Sin q _) -> (Q.real q-.1.)
278
| (Chg q _ _) -> (Q.real q-.1.) (* Must be before *)
279
| Inf -> 0.
280
end
281
282
Valid (366ms) (cvc5)
283
let ghost
not_bottom_after'
(before:real) (if_:bool) (l:t'') : real
284
requires { ordered' l }
285
requires { lt_bound' before l }
286
requires { l = Inf -> if_ }
287
ensures { mem_if if_ result l }
288
ensures { before <. result } =
289
if if_ then
290
match l with
291
| (Sin q _) -> (Q.real q*.0.5+.before*.0.5)
292
| (Chg q _ _) -> (Q.real q*.0.5+.before*.0.5)
293
| Inf -> before +. 1.
294
end
295
else
296
match l with
297
| (Sin q _) -> Q.real q
298
| (Chg q _ (Sin q' _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)
299
| (Chg q _ (Chg q' _ _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)
300
| (Chg q _ Inf) -> (Q.real q+.1.)
301
| Inf -> absurd
302
end
303
Valid (26ms) (cvc5)
304
let ghost
not_bottom_before'
(before:real) (if_:bool) (l:t'') : real
305
requires { lt_bound' before l }
306
ensures { forall x. before <=. x <=. result -> (if_ <-> mem_if if_ x l) }
307
ensures { before <. result } =
308
match l with
309
| (Sin q _) -> (Q.real q*.0.5+.before*.0.5)
310
| (Chg q _ _) -> (Q.real q*.0.5+.before*.0.5)
311
| Inf -> before +. 1.
312
end
313
Valid (19ms) (cvc5)
314
let ghost
not_bottom_a
(l:t') : real
315
requires { ordered l }
316
requires { not (l = Off Inf) }
317
ensures { mem result l } =
318
match l with
319
| Off l -> not_bottom' False l
320
| On l -> not_bottom' True l
321
end
322
Valid (19ms) (cvc5)
323
let ghost
not_bottom
(l:t) : real
324
ensures { mem result l.a } =
325
not_bottom_a l.a
326
Valid (27ms) (cvc5)
327
let ghost
lt_bound_is_mem
(if_:bool) (q:real) (l:t'')
328
requires { lt_bound' q l }
329
ensures { forall r. r <=. q -> (if_ <-> mem_if if_ r l)}
330
=
331
match l with
332
| Sin _ _ -> ()
333
| Chg _ _ _ -> ()
334
| Inf -> ()
335
end
336
Valid (45ms) (colibri2 2) (cvc5 5) (split_vc 2) (depth 2)
337
let ghost
not_mem_is_le_bound'
(if_:bool) (q:real) (l:t'')
338
requires { ordered' l }
339
requires { forall x. x <. q -> (if_ <-> mem_if if_ x l) }
340
ensures { le_bound' q l} =
341
match l with
342
| Sin a _ -> assert { not if_ <-> mem_if if_ a l }
343
| Chg a Strict l' ->
344
if pure { a <. q } then
345
let a' = not_bottom_before' (Q.real a) (not if_) l' in
346
let b = pure { a*.0.5+.(min a' q)*.0.5 } in
347
assert { (not if_ <-> mem_if if_ b l) };
348
absurd
349
| Chg a Large _ -> assert { (not if_) <-> (mem_if if_ a l) }
350
| Inf -> ()
351
end
352
Valid (351ms) (cvc5)
353
let ghost
not_mem_is_le_bound
(if_:bool) (q:real) (l:t')
354
requires { ordered l }
355
requires { forall x. x <. q -> (if_ <-> mem x l) }
356
ensures { le_bound q l}
357
ensures { l.on = if_ } =
358
let b = (lt_bound_exists l.on l.in_) in
359
lt_bound_is_mem l.on b l.in_;
360
let a = min b (q-.1.) in
361
assert { l.on <-> mem a l };
362
not_mem_is_le_bound' l.on q l.in_
363
364
Valid (411ms) (cvc5)
365
let
singleton
(q:Q.t) : t
366
ensures { exact memt (fun (x:real) -> x = q) result }
367
=
368
{ a = Off (Sin q Inf) }
369
Valid (190ms) (colibri2 16) (cvc4 10) (split_vc 4) (depth 3)
370
let
is_singleton
(u:t) : (option Q.t, ghost real, ghost real)
371
ensures {
372
let (o,x1,x2) = result in
373
match o with
374
| Some q -> forall x:real. mem x u.a <-> x = q
375
| None -> x1 <> x2 /\ mem x1 u.a /\ mem x2 u.a
376
end
377
} =
378
match u.a with
379
| Off (Sin q Inf) -> (Some q,ghost 0.,ghost 1.)
380
| Off (Sin q (Sin q' _)) -> (None,ghost Q.real q,ghost Q.real q')
381
| Off (Sin _ (Chg q _ on)) ->
382
match on with
383
| Sin q' _ -> (None,ghost (Q.real q*.0.3+.Q.real q'*.0.7),
384
ghost (Q.real q*.0.7+.Q.real q'*.0.3))
385
| Chg q' _ _ -> (None,ghost(Q.real q*.0.3+.Q.real q'*.0.7),
386
ghost(Q.real q*.0.7+.Q.real q'*.0.3))
387
| Inf -> (None,ghost(Q.real q+.1.),ghost(Q.real q+.2.))
388
end
389
| Off (Chg q _ on) ->
390
match on with
391
| Sin q' _ -> (None,ghost (Q.real q*.0.3+.Q.real q'*.0.7),
392
ghost (Q.real q*.0.7+.Q.real q'*.0.3))
393
| Chg q' _ _ -> (None,ghost(Q.real q*.0.3+.Q.real q'*.0.7),
394
ghost(Q.real q*.0.7+.Q.real q'*.0.3))
395
| Inf -> (None,ghost(Q.real q+.1.),ghost(Q.real q+.2.))
396
end
397
| On (Sin q _) -> (None, ghost (Q.real q-.1.), ghost (Q.real q-.2.))
398
| On (Chg q _ _) -> (None, ghost (Q.real q-.1.), ghost (Q.real q-.2.))
399
| On Inf -> (None, ghost 0., ghost 1.)
400
| Off Inf -> absurd
401
end
402
403
use colibrilib.q.Ord as Ord
404
Valid (24ms) (cvc5)
405
let
min_bound_sup
v1 b1 v2 b2: (v3:Q.t,b3:Bound.t)
406
ensures { forall q. (cmp q b1 v1 /\ cmp q b2 v2) <-> cmp q b3 v3 }
407
ensures { (v3 <=. v1) } ensures { (v3 <=. v2) }
408
ensures { v3 = v1 || v3 = v2 }
409
ensures { b1 = Large -> b2 = Large -> b3 = Large }
410
=
411
match Q.compare v1 v2, b1, b2 with
412
| Ord.Eq, Large, Large -> (v1,Large)
413
| Ord.Eq, _ ,_ -> (v1,Strict)
414
| Ord.Lt, _, _ -> (v1,b1)
415
| Ord.Gt, _ ,_ -> (v2,b2)
416
end
417
Valid (28ms) (cvc5)
418
let
min_bound_inf
v1 b1 v2 b2: (v3:Q.t,b3:Bound.t)
419
ensures { forall q. (cmp v1 b1 q \/ cmp v2 b2 q) <-> cmp v3 b3 q }
420
ensures { (v3 <=. v1) } ensures { (v3 <=. v2) }
421
ensures { v3 = v1 || v3 = v2 }
422
ensures { b1 = Large -> b2 = Large -> b3 = Large }
423
=
424
match Q.compare v1 v2, b1, b2 with
425
| Ord.Eq, Strict, Strict -> (v1,Strict)
426
| Ord.Eq, _, _ -> (v1,Large)
427
| Ord.Lt, _, _ -> (v1,b1)
428
| Ord.Gt, _, _ -> (v2,b2)
429
end
430
431
use real.MinMax
432
Valid (26ms) (cvc5)
433
let
max_bound_sup
v1 b1 v2 b2: (v3:Q.t,b3:Bound.t)
434
ensures { forall q. (cmp q b1 v1 \/ cmp q b2 v2) <-> cmp q b3 v3 }
435
ensures { (v1 <=. v3) } ensures { (v2 <=. v3) }
436
ensures { max v1 v2 = v3 }
437
ensures { b1 = Large -> b2 = Large -> b3 = Large }
438
=
439
match Q.compare v1 v2, b1, b2 with
440
| Ord.Eq, Strict, Strict -> (v1,Strict)
441
| Ord.Eq, _, _ -> (v1,Large)
442
| Ord.Lt, _, _ -> (v2,b2)
443
| Ord.Gt, _, _ -> (v1,b1)
444
end
445
Valid (23ms) (cvc5)
446
let
max_bound_inf
v1 b1 v2 b2: (v3:Q.t,b3:Bound.t)
447
ensures { forall q. (cmp v1 b1 q /\ cmp v2 b2 q) <-> cmp v3 b3 q }
448
ensures { (v1 <=. v3) } ensures { (v2 <=. v3) }
449
ensures { v3 = v1 || v3 = v2 }
450
ensures { b1 = Large -> b2 = Large -> b3 = Large }
451
=
452
match Q.compare v1 v2, b1, b2 with
453
| Ord.Eq, Large, Large -> (v1,Large)
454
| Ord.Eq, _, _ -> (v1,Strict)
455
| Ord.Lt, _, _ -> (v2,b2)
456
| Ord.Gt, _, _ -> (v1,b1)
457
end
458
Valid (2.0s) (colibri2 71) (cvc4 9) (cvc5 85) (split_vc 29) (depth 5)
459
let rec
inter'
(ifu:bool) (ifv:bool) (u:t'') (v:t'') : t''
460
requires { ordered' u }
461
requires { ordered' v }
462
ensures { ordered' result }
463
ensures {
464
forall x:real. (mem_if ifu x u /\ mem_if ifv x v) <-> mem_if (andb ifu ifv) x result
465
}
466
ensures { le_sup (min_sup (bound u) (bound v)) (bound result) }
467
variant { length' u + length' v } =
468
match u, v with
469
| u, Inf -> if ifv then u else Inf
470
| Inf, v -> if ifu then v else Inf
471
| Sin qu lu, Sin qv lv ->
472
match Q.compare qu qv with
473
| Ord.Eq -> let l = inter' ifu ifv lu lv in if xorb ifu ifv then l else Sin qu l
474
| Ord.Lt ->
475
let l = inter' ifu ifv lu v in
476
if ifv then Sin qu l else l
477
| Ord.Gt ->
478
let l = inter' ifu ifv u lv in
479
if ifu then Sin qv l else l
480
end
481
| Chg qu bu lu, Chg qv bv lv ->
482
match Q.compare qu qv with
483
| Ord.Eq ->
485
(* lt_bound_is_mem ifv qu lv; lt_bound_is_mem ifu qu lu; *)
486
let l = inter' (notb ifu) (notb ifv) lu lv in
487
match bu, bv with
488
| Large, Large | Strict, Strict -> if xorb ifu ifv then l else Chg qu bu l
489
| Large, Strict ->
490
match ifu, ifv with
491
| True, True -> Chg qu Large l
492
| False, False -> Chg qu Strict l
493
| True, False -> l
494
| False, True -> Sin qu l
495
end
496
| Strict, Large ->
497
match ifv, ifu with
498
| True, True -> Chg qu Large l
499
| False, False -> Chg qu Strict l
500
| True, False -> l
501
| False, True -> Sin qu l
502
end
503
end
504
| Ord.Lt -> let l = (inter' (notb ifu) ifv lu v) in if ifv then Chg qu bu l else l
505
| Ord.Gt -> let l = (inter' ifu (notb ifv) u lv) in if ifu then Chg qv bv l else l
506
end
507
| Sin qu lu, Chg qv bv lv ->
508
match Q.compare qu qv with
509
| Ord.Eq ->
510
let l = inter' ifu (notb ifv) lu lv in
511
if ifu then
512
Chg qu (if ifv then Large else Strict) l
513
else
514
match ifv, bv with
515
| False, Large | True, Strict -> Sin qu l
516
| _ -> l
517
end
518
| Ord.Lt ->
519
let l = inter' ifu ifv lu v in if ifv then Sin qu l else l
520
| Ord.Gt ->
521
let l = inter' ifu (notb ifv) u lv in if ifu then Chg qv bv l else l
522
end
523
| Chg qu bu lu, Sin qv lv ->
524
match Q.compare qu qv with
525
| Ord.Eq ->
526
let l = inter' (notb ifu) ifv lu lv in
527
if ifv then
528
Chg qv (if ifu then Large else Strict) l
529
else
530
match ifu, bu with
531
| False, Large | True, Strict -> Sin qv l
532
| _ -> l
533
end
534
| Ord.Lt ->
535
let l = inter' (notb ifu) ifv lu v in if ifv then Chg qu bu l else l
536
| Ord.Gt ->
537
let l = inter' ifu ifv u lv in if ifu then Sin qv l else l
538
end
539
end
540
541
Valid (701ms) (colibri2 19) (split_vc) (depth 1)
542
let
inter
(u:t) (v:t) : option t
543
ensures { exact_opt memt (fun (x:real) -> memt x u /\ memt x v) result }
544
ensures {
545
match result with
546
| None -> true
547
| Some w ->
548
le_sup_infr (le_min_sup_infr (infr_bound u.a) (infr_bound v.a)) (infr_bound w.a)
549
end
550
}
551
=
552
let mk_off_option (l:t'') : option t
553
requires { ordered' l }
554
ensures {
555
forall x:real. mem_if False x l <->
556
match result with
557
| None -> false
558
| Some w -> mem x w.a
559
end
560
}
561
ensures {
562
match result with
563
| None -> true
564
| Some w -> (infr_bound' l) = (infr_bound w.a)
565
end
566
}
567
=
568
match l with
569
| Inf -> None
570
| l -> Some { a = Off l }
571
end
572
in
573
match u.a,v.a with
574
| On u, On v -> Some { a = On (inter' True True u v) }
575
| On u, Off v -> mk_off_option (inter' True False u v)
576
| Off u, On v -> mk_off_option (inter' False True u v)
577
| Off u, Off v -> mk_off_option (inter' False False u v)
578
end
579
Valid (3.2s) (colibri2 64) (cvc5 71) (split_vc 23) (depth 5)
580
let rec
union'
(ifu:bool) (ifv:bool) (u:t'') (v:t'') : t''
581
requires { ordered' u }
582
requires { ordered' v }
583
ensures { ordered' result }
584
ensures {
585
forall x:real. (mem_if ifu x u \/ mem_if ifv x v) <-> mem_if (orb ifu ifv) x result
586
}
587
ensures { le_sup (min_sup (bound u) (bound v)) (bound result) }
588
variant { length' u + length' v } =
589
match u, v with
590
| u, Inf -> if ifv then Inf else u
591
| Inf, v -> if ifu then Inf else v
592
| Sin qu lu, Sin qv lv ->
593
match Q.compare qu qv with
594
| Ord.Eq -> let l = union' ifu ifv lu lv in if xorb ifu ifv then l else Sin qu l
595
| Ord.Lt ->
596
let l = union' ifu ifv lu v in
597
if ifv then l else Sin qu l
598
| Ord.Gt ->
599
let l = union' ifu ifv u lv in
600
if ifu then l else Sin qv l
601
end
602
| Chg qu bu lu, Chg qv bv lv ->
603
match Q.compare qu qv with
604
| Ord.Eq ->
605
let l = union' (notb ifu) (notb ifv) lu lv in
606
match bu, bv with
607
| Large, Large | Strict, Strict -> if xorb ifu ifv then l else Chg qu bu l
608
| Large, Strict ->
609
match ifu, ifv with
610
| True, True -> Chg qu Strict l
611
| False, False -> Chg qu Large l
612
| True, False -> Sin qu l
613
| False, True -> l
614
end
615
| Strict, Large ->
616
match ifv, ifu with
617
| True, True -> Chg qu Strict l
618
| False, False -> Chg qu Large l
619
| True, False -> Sin qu l
620
| False, True -> l
621
end
622
end
623
| Ord.Lt -> let l = (union' (notb ifu) ifv lu v) in if ifv then l else Chg qu bu l
624
| Ord.Gt -> let l = (union' ifu (notb ifv) u lv) in if ifu then l else Chg qv bv l
625
end
626
| Sin qu lu, Chg qv bv lv ->
627
match Q.compare qu qv with
628
| Ord.Eq ->
629
let l = union' ifu (notb ifv) lu lv in
630
if ifu then
631
match ifv, bv with
632
| False, Large | True, Strict -> l
633
| _ -> Sin qu l
634
end
635
else
636
Chg qu (if ifv then Strict else Large) l
637
| Ord.Lt ->
638
let l = union' ifu ifv lu v in if ifv then l else Sin qu l
639
| Ord.Gt ->
640
let l = union' ifu (notb ifv) u lv in if ifu then l else Chg qv bv l
641
end
642
| Chg qu bu lu, Sin qv lv ->
643
match Q.compare qu qv with
644
| Ord.Eq ->
645
let l = union' (notb ifu) ifv lu lv in
646
if ifv then
647
match ifu, bu with
648
| False, Large | True, Strict -> l
649
| False, Strict | True, Large -> Sin qv l
650
end
651
else
652
Chg qv (if ifu then Strict else Large) l
653
| Ord.Lt ->
654
let l = union' (notb ifu) ifv lu v in if ifv then l else Chg qu bu l
655
| Ord.Gt ->
656
let l = union' ifu ifv u lv in if ifu then l else Sin qv l
657
end
658
end
659
Valid (368ms) (cvc5)
660
let
union_a
(u:t') (v:t') : t'
661
requires { ordered u }
662
requires { ordered v }
663
ensures { ordered result }
664
ensures {
665
forall x:real. (mem x u \/ mem x v) <-> mem x result
666
} =
667
match u,v with
668
| On u, On v -> On (union' True True u v)
669
| On u, Off v -> On (union' True False u v)
670
| Off u, On v -> On (union' False True u v)
671
| Off u, Off v -> Off (union' False False u v)
672
end
673
674
Valid (394ms) (cvc5)
675
let
union
(u:t) (v:t) : t
676
ensures { exact memt (fun (x:real) -> memt x u \/ memt x v) result } =
677
let w = union_a u.a v.a in
678
let ghost x = not_bottom u in
679
assert { mem x w };
680
{ a = w }
681
682
683
let
cmp
(x:Q.t) (b:Bound.t) (y:Q.t) =
684
match b with
685
| Bound.Large -> Q.le x y
686
| Bound.Strict -> Q.lt x y
687
end
688
689
Valid (335ms) (cvc5)
690
let
mem
(x:Q.t) (l:t)
691
ensures { decides (memt x.Q.real l) result }
692
=
693
let rec mem' (if_:bool) (x:Q.t) (l:t'')
694
requires { ordered' l }
695
ensures { result = mem_if if_ x.Q.real l }
696
variant { length' l }
697
=
698
match l with
699
| Sin q l ->
700
match Q.compare x q with
701
| Ord.Eq -> notb if_
702
| Ord.Lt -> if_
703
| Ord.Gt -> mem' if_ x l
704
end
705
| Chg q b l ->
706
if cmp q b x then mem' (notb if_) x l
707
else if_
708
| Inf -> if_
709
end
710
in
711
match l.a with
712
| On l ->
713
mem' True x l
714
| Off l ->
715
mem' False x l
716
end
717
Valid (777ms) (colibri2 5) (cvc5 16) (split_vc 2) (depth 2)
718
let
except
l x
719
ensures {
720
match result with
721
| Some res -> forall q. (mem q l.a /\ q <> x.Q.real) <-> mem q res.a
722
| None -> forall q. mem q l.a <-> q = x.Q.real
723
end
724
}
725
=
726
let rec except' (if_:bool) (x:Q.t) (l:t'') : t''
727
requires { ordered' l }
728
ensures { ordered' result }
729
ensures { le_sup (min_sup (R x) (bound l)) (bound result) }
730
ensures { forall q. (mem_if if_ q l /\ q <> x.Q.real) <-> mem_if if_ q result }
731
variant { length' l }
732
=
733
match l with
734
| Sin q l' ->
735
lt_bound_is_mem if_ (Q.real q) l';
736
match Q.compare x q with
737
| Ord.Eq -> if if_ then l else l'
738
| Ord.Lt -> if if_ then Sin x l else l
739
| Ord.Gt -> Sin q (except' if_ x l')
740
end
741
| Chg q bv l' ->
742
match Q.compare x q with
743
| Ord.Eq -> lt_bound_is_mem if_ (Q.real q) l'; Chg q (if if_ then Large else Strict) l'
744
| Ord.Lt -> if if_ then Sin x l else l
745
| Ord.Gt -> Chg q bv (except' (notb if_) x l')
746
end
747
| Inf -> if if_ then Sin x Inf else Inf
748
end
749
in
750
match l.a with
751
| On l ->
752
Some { a = On (except' True x l) }
753
| Off l ->
754
match except' False x l with
755
| Inf ->
756
let ghost v = not_bottom' False l in
757
assert { v = x };
758
None
759
| l' -> Some { a = Off l' }
760
end
761
end
762
763
Valid (144ms) (colibri2 8) (split_vc) (depth 1)
764
let
complement
l
765
ensures { exact_opt memt (fun (x:real) -> not (memt x l)) result } =
766
let rec lemma complement' (if_:bool) (l:t'') : unit
767
ensures { forall q. not (mem_if if_ q l) <-> mem_if (not if_) q l }
768
variant { l }
769
=
770
match l with
771
| Sin _ l' -> complement' if_ l'
772
| Chg _ _ l' -> (complement' (notb if_) l')
773
| Inf -> ()
774
end
775
in
776
match l.a with
777
| On Inf -> None
778
| On l ->
779
Some { a = Off l }
780
| Off l ->
781
Some { a = On l }
782
end
783
784
785
let function
add_bound
b1 b2 =
786
match b1, b2 with
787
| Large, Large -> Large
788
| Large, Strict -> Strict
789
| Strict, Large -> Strict
790
| Strict, Strict -> Strict
791
end
792
793
let function
both_strict
b1 b2 =
794
match b1, b2 with
795
| Strict, Strict -> Strict
796
| Large, Strict -> Large
797
| Strict, Large -> Large
798
| Large, Large -> Large
799
end
800
801
802
use real.MinMax
803
804
let
bound_compare
test if1 if2 b1 b2 =
805
match (b1, b2) with
806
| Large, Large -> test if1 if2
807
| Strict, Large -> test (notb if1) if2
808
| Large, Strict -> test if1 (notb if2)
809
| Strict, Strict -> test (notb if1) (notb if2)
810
end
811
Valid (1.6s) (colibri2 10) (cvc5 61) (split_vc 3) (depth 3)
812
let rec
for_all
test t1 t2
813
ensures { result -> (forall q. test (mem q t1.a) (mem q t2.a)) }
814
=
815
let rec aux test if1 if2 t1 t2
816
requires { ordered' t1 }
817
requires { ordered' t2 }
818
requires { test if1 if2 }
819
ensures { result -> (forall q1. test (mem_if if1 q1 t1) (mem_if if2 q1 t2)) }
820
variant { length' t1 + length' t2 }
821
=
822
match (t1, t2) with
823
| Inf, Inf -> test if1 if2
824
| _, Inf -> test (notb if1) if2
825
| Inf, _ -> test if1 (notb if2)
826
| Sin q1 l1, Sin q2 l2 ->
827
match Q.compare q1 q2 with
828
| Ord.Lt -> test (notb if1) if2 && aux test if1 if2 l1 t2
829
| Ord.Gt -> test if1 (notb if2) && aux test if1 if2 t1 l2
830
| Ord.Eq -> test (notb if1) (notb if2) && aux test if1 if2 l1 l2
831
end
832
| Sin q1 l1, Chg q2 b2 l2 ->
833
match Q.compare q1 q2 with
834
| Ord.Lt -> test (notb if1) if2 && aux test if1 if2 l1 t2
835
| Ord.Gt -> test if1 (notb if2) && test if1 (notb if2) && aux test if1 (notb if2) t1 l2
836
| Ord.Eq -> bound_compare test (notb if1) (notb if2) Large b2 && test if1 (notb if2) && aux test if1 (notb if2) l1 l2
837
end
838
| Chg q1 b1 l1, Sin q2 l2 ->
839
match Q.compare q1 q2 with
840
| Ord.Lt -> test (notb if1) if2 && test (notb if1) if2 && aux test (notb if1) if2 l1 t2
841
| Ord.Gt -> test if1 (notb if2) && test if1 if2 && aux test if1 if2 t1 l2
842
| Ord.Eq -> bound_compare test (notb if1) (notb if2) b1 Large && test (notb if1) if2 && aux test (notb if1) if2 l1 l2
843
end
844
| Chg q1 b1 l1, Chg q2 b2 l2 ->
845
match Q.compare q1 q2 with
846
| Ord.Lt -> test (notb if1) if2 && aux test (notb if1) if2 l1 t2
847
| Ord.Gt -> test if1 (notb if2) && aux test if1 (notb if2) t1 l2
848
| Ord.Eq -> bound_compare test (notb if1) (notb if2) b1 b2 && test (notb if1) (notb if2) && aux test (notb if1) (notb if2) l1 l2
849
end
850
end
851
in
852
match (t1.a, t2.a) with
853
| On on1, On on2 ->
854
test True True && aux test True True on1 on2
855
| On on1, Off off2 ->
856
test True False && aux test True False on1 off2
857
| Off off1, On on2 ->
858
test False True && aux test False True off1 on2
859
| Off off1, Off off2 ->
860
test False False && aux test False False off1 off2
861
end
862
Valid (32ms) (cvc5)
863
let rec
distinct
t1 t2
864
ensures { result -> (forall q. not ((mem q t1.a) /\ (mem q t2.a))) }
865
=
866
let nand x y = notb (andb x y) in
867
for_all nand t1 t2
868
869
let function
impb
b1 b2 =
870
match b1, b2 with
871
| True, False -> False
872
| _ -> True
873
end
874
Valid (32ms) (cvc5)
875
let rec
is_included
t1 t2
876
ensures { result -> (forall q. (mem q t1.a) -> (mem q t2.a)) }
877
=
878
for_all impb t1 t2
879
Valid (37ms) (cvc5)
880
let
gt
(q:Q.t)
881
ensures { exact memt (fun (x:real) -> q <. x) result }
882
= { a = Off (Chg q Strict Inf) }
883
Valid (414ms) (cvc5)
884
let
lt
(q:Q.t)
885
ensures { exact memt (fun (x:real) -> x <. q) result }
886
= { a = On (Chg q Large Inf) }
887
Valid (40ms) (cvc5)
888
let
ge
(q:Q.t)
889
ensures { exact memt (fun (x:real) -> q <=. x) result }
890
ensures { R q = infr_bound result.a }
891
= { a = Off (Chg q Large Inf) }
892
Valid (33ms) (cvc5)
893
let
le
(q:Q.t)
894
ensures { exact memt (fun (x:real) -> x <=. q) result }
895
= { a = On (Chg q Strict Inf) }
896
Valid (146ms) (colibri2 4) (cvc5 21) (split_vc) (depth 1)
897
let
le'
(u:t)
898
ensures { sound_rel memt (<=.) u result }
899
=
900
let rec aux if_ u
901
requires { u <> Inf }
902
requires { ordered' u }
903
ensures { ordered' result }
904
ensures { forall q. mem_if if_ q u -> forall q'. q' <=. q -> mem_if True q' result }
905
variant { u }
906
=
907
match u with
908
| Sin q Inf -> if if_ then Inf else Chg q Strict Inf
909
| Chg q b Inf -> if if_ then Chg q b Inf else Inf
910
| Sin q u -> let _ = not_bottom_after' (Q.real q) if_ u in aux if_ u
911
| Chg q _ u -> let _ = not_bottom_after' (Q.real q) (notb if_) u in aux (notb if_) u
912
| Inf -> Inf
913
end
914
in
915
match u.a with
916
| On Inf -> { a = On Inf }
917
| On on -> { a = On (aux True on) }
918
| Off off -> { a = On (aux False off) }
919
end
920
Valid (302ms) (colibri2)
921
let rec
mem_max'
if_ u: option (Q.t,Bound.t)
922
requires { u <> Inf }
923
requires { ordered' u }
924
ensures { match result with
925
| None -> true
926
| Some (r,_) -> forall q. lt_bound' q u -> q <.r
927
end }
928
ensures { match result with
929
| None -> true
930
| Some (r,b) -> forall q. mem_if if_ q u -> cmp q b r
931
end }
932
variant { u }
933
=
934
match u with
935
| Sin q Inf -> if if_ then None else Some (q,Large)
936
| Chg q b Inf -> if if_ then Some (q,inv_bound b) else None
937
| Sin _ u -> mem_max' if_ u
938
| Chg _ _ u -> mem_max' (notb if_) u
939
| Inf -> None
940
end

v is an upper bound of u

943
predicate
is_upper
(u:t) (v:(Q.t,Bound.t)) =
944
let (r,b) = v in forall q. mem q u.a -> cmp q b r
945
Valid (406ms) (cvc5)
946
let
mem_max
u
947
ensures { when_some (is_upper u) result }
948
=
949
match u.a with
950
| On Inf -> None
951
| On a -> mem_max' True a
952
| Off a -> mem_max' False a
953
end
954
Valid (38ms) (cvc5)
955
let
mem_min
(u:t): option (Q.t,Bound.t)
956
ensures { forall q. mem q u.a ->
957
match result with
958
| None -> true
959
| Some (r,b) -> cmp r b q
960
end
961
}
962
=
963
match u.a with
964
| On _ -> None
965
| Off (Sin q _) -> Some (q,Large)
966
| Off (Chg q b _) -> Some (q,b)
967
| _ -> absurd
968
end
969
970
971
Valid (187ms) (colibri2 4) (cvc5 21) (split_vc) (depth 1)
972
let
lt'
(u:t)
973
ensures { sound_rel memt (<.) u result }
974
=
975
let rec aux if_ u
976
requires { u <> Inf }
977
requires { ordered' u }
978
ensures { ordered' result }
979
ensures { forall q. mem_if if_ q u -> forall q'. q' <. q -> mem_if True q' result }
980
variant { u }
981
=
982
match u with
983
| Sin q Inf -> if if_ then Inf else Chg q Large Inf
984
| Chg q _ Inf -> if if_ then Chg q Large Inf else Inf
985
| Sin q u -> let _ = not_bottom_after' (Q.real q) if_ u in aux if_ u
986
| Chg q _ u -> let _ = not_bottom_after' (Q.real q) (notb if_) u in aux (notb if_) u
987
| Inf -> Inf
988
end
989
in
990
match u.a with
991
| On Inf -> { a = On Inf }
992
| On on -> { a = On (aux True on) }
993
| Off off -> { a = On (aux False off) }
994
end
995
Valid (405ms) (colibri2)
996
let
gt'
(u:t)
997
ensures { sound_rel memt (>.) u result }
998
=
999
match u.a with
1000
| On _ -> { a = On Inf }
1001
| Off (Sin q _) -> { a = Off (Chg q Strict Inf) }
1002
| Off (Chg q _ _) -> { a = Off (Chg q Strict Inf) }
1003
| _ -> absurd
1004
end
1005
Valid (399ms) (colibri2)
1006
let
ge'
(u:t)
1007
ensures { sound_rel memt (>=.) u result }
1008
=
1009
match u.a with
1010
| On _ -> { a = On Inf }
1011
| Off (Sin q _) -> { a = Off (Chg q Large Inf) }
1012
| Off (Chg q b _) -> { a = Off (Chg q b Inf) }
1013
| _ -> absurd
1014
end
1015
1016
scope IsComparable
1017
type
is_comparable
=
Gt
|
Lt
|
Ge
|
Le
|
Eq
|
Uncomparable
1018
Valid (275ms) (colibri2)
1019
let rec
is_lt'
(if_:bool) (t1:t'') (q:Q.t)
1020
ensures { match result with
1021
| Lt -> forall q1. mem_if if_ q1 t1 -> cmp q1 Strict q
1022
| Le -> forall q1. mem_if if_ q1 t1 -> cmp q1 Large q
1023
| Uncomparable -> true
1024
| Eq | Gt | Ge -> false
1025
end }
1026
variant { t1 }
1027
=
1028
match t1, if_ with
1029
| Sin _ Inf, True -> Uncomparable
1030
| Chg _ _ Inf, False -> Uncomparable
1031
| Sin q1 l1, _ ->
1032
match Q.compare q1 q, l1 with
1033
| Ord.Lt, Inf -> Lt
1034
| Ord.Eq, Inf -> Le
1035
| Ord.Eq, _ -> Uncomparable
1036
| Ord.Lt , _ -> is_lt' if_ l1 q
1037
| Ord.Gt, _ -> Uncomparable
1038
end
1039
| Chg q1 b1 l1, _ ->
1040
match Q.compare q1 q, b1, l1 with
1041
| Ord.Lt, _, Inf -> Lt
1042
| Ord.Eq, Large, Inf -> Lt
1043
| Ord.Eq, Strict, Inf -> Le
1044
| Ord.Eq, _, _ -> Uncomparable
1045
| Ord.Lt , _,_ -> is_lt' (notb if_) l1 q
1046
| Ord.Gt, _, _ -> Uncomparable
1047
end
1048
| Inf, True -> Uncomparable
1049
| Inf, False -> Lt
1050
end
1105
1106
(* let rec is_comparable_q' (start:bool) (if_:bool) (t1:t'') (q:Q.t) ensures { match result with | Lt -> forall q1. mem_if if_ q1 t1 -> cmp q1 Strict q | Le -> false | Uncomparable -> not start | Eq -> mem_if if_ q t1 | Gt -> start /\ forall q1. mem_if if_ q1 t1 -> cmp q Strict q1 | Ge -> false end } variant { t1 } = match t1, if_ with | Sin q1 Inf, True -> match Q.compare q1 q with | Ord.Eq -> Uncomparable | Ord.Gt | Ord.Lt -> Eq end | Chg _ _ Inf, False -> Uncomparable | Sin q1 l1, _ -> match Q.compare q1 q, l1 with | Ord.Lt, Inf -> Lt | Ord.Eq, Inf -> Le | Ord.Eq, _ -> Uncomparable | Ord.Lt , _ -> is_comparable_q' False if_ l1 q | Ord.Gt, _ -> Uncomparable end | Chg q1 b1 l1, _ -> match Q.compare q1 q, b1, l1 with | Ord.Lt, _, Inf -> Lt | Ord.Eq, Large, Inf -> Lt | Ord.Eq, Strict, Inf -> Le | Ord.Eq, _, _ -> Uncomparable | Ord.Lt , _,_ -> is_comparable_q' False (notb if_) l1 q | Ord.Gt, _, _ -> Uncomparable end | Inf, True -> Uncomparable | Inf, False -> Lt end let rec is_comparable_q (l:t) (q:Q.t) ensures { match result with | Lt -> forall q1. mem q1 l.a -> cmp q1 Strict q | Le -> false | Uncomparable -> true | Eq -> mem q1 l.a | Gt -> forall q1. mem q1 t1.a -> cmp q Strict q1 | Ge -> false end } = in match t1.on with | On l -> is_comparable_q' True True l q | Off l -> is_comparable_q' True False l q end *)
1107
Valid (1.0s) (colibri2 5) (cvc5 120) (split_vc 2) (depth 2)
1108
let
is_comparable
(t1:t) (t2:t)
1109
ensures { match result with
1110
| Gt -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 >. q2
1111
| Lt -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 <. q2
1112
| Ge -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 >=. q2
1113
| Le -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 <=. q2
1114
| Eq -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 = q2
1115
| Uncomparable -> true
1116
end }
1117
=
1118
match t1.a, t2.a with
1119
| On _, On _ -> Uncomparable
1120
| On l1, Off l2 ->
1121
let q2,b2 = match l2 with
1122
| Sin q2 _ -> q2, Large
1123
| Chg q2 b2 _ -> q2, b2
1124
| _ -> absurd
1125
end
1126
in
1127
match is_lt' True l1 q2, b2 with
1128
| Lt, _ -> Lt
1129
| Le, Strict -> Lt
1130
| Le, Large -> Le
1131
| Uncomparable, _ -> Uncomparable
1132
| _ -> absurd
1133
end
1134
| Off l1, On l2 ->
1135
let q1,b1 = match l1 with
1136
| Sin q1 _ -> q1, Large
1137
| Chg q1 b1 _ -> q1, b1
1138
| _ -> absurd
1139
end
1140
in
1141
match is_lt' True l2 q1, b1 with
1142
| Lt, _ -> Gt
1143
| Le, Strict -> Gt
1144
| Le, Large -> Ge
1145
| Uncomparable, _ -> Uncomparable
1146
| _ -> absurd
1147
end
1148
| Off l1, Off l2 ->
1149
let q1,b1 = match l1 with
1150
| Sin q1 _ -> q1, Large
1151
| Chg q1 b1 _ -> q1, b1
1152
| _ -> absurd
1153
end
1154
in
1155
let q2,b2 = match l2 with
1156
| Sin q2 _ -> q2, Large
1157
| Chg q2 b2 _ -> q2, b2
1158
| _ -> absurd
1159
end
1160
in
1161
match Q.compare q1 q2 with
1162
| Ord.Eq -> match is_lt' False l1 q2, b2, is_lt' False l2 q1, b1 with
1163
| Lt, _, _, _ ->
1164
let ghost w1 = not_bottom' False l1 in
1165
assert { cmp w1 Strict q2 };
1166
absurd
1167
| _, _, Lt, _ ->
1168
let ghost w2 = not_bottom' False l2 in
1169
assert { cmp w2 Strict q1 };
1170
absurd
1171
| Le, _, Le, _ -> Eq
1172
| Le, Strict, _, _ -> Lt
1173
| Le, Large, _, _ -> Le
1174
| Uncomparable, _, Le, Large -> Ge
1175
| Uncomparable, _, Le, Strict -> Gt
1176
| Uncomparable, _, Uncomparable, _ -> Uncomparable
1177
| _ -> absurd
1178
end
1179
| Ord.Lt ->
1180
match is_lt' False l1 q2, b2 with
1181
| Lt, _ -> Lt
1182
| Le, Strict -> Lt
1183
| Le, Large -> Le
1184
| Uncomparable, _ -> Uncomparable
1185
| _ -> absurd
1186
end
1187
| Ord.Gt ->
1188
match is_lt' False l2 q1, b1 with
1189
| Lt, _ -> Gt
1190
| Le, Strict -> Gt
1191
| Le, Large -> Ge
1192
| Uncomparable, _ -> Uncomparable
1193
| _ -> absurd
1194
end
1195
end
1196
end
1197
end
1198
1199
type
convex_hull
= (option (Q.t,Bound.t),option (Q.t,Bound.t))
1200
1201
predicate
in_hull_sup
(q':real) (b2:(option (Q.t,Bound.t))) =
1202
match b2 with
1203
| None -> true
1204
| Some (q,b) -> cmp q' b q
1205
end
1206
1207
predicate
in_hull
(q':real) (x:convex_hull) =
1208
let (b1,b2) = x in
1209
match b1 with
1210
| None -> true
1211
| Some (q,b) -> cmp q b q'
1212
end /\ in_hull_sup q' b2
1213
1214
Valid (246ms) (colibri2)
1215
let
from_convex_hull
x : option t
1216
ensures { includes_opt memt (fun (q:real) -> in_hull q x) result }
1217
=
1218
match x with
1219
| None, None -> Some { a = On Inf }
1220
| None, Some (q,b) -> Some { a = On (Chg q (inv_bound b) Inf) }
1221
| Some (q,b), None -> Some { a = Off (Chg q b Inf) }
1222
| Some (q1,b1), Some (q2,b2) ->
1223
match Q.compare q1 q2, b1, b2 with
1224
| Ord.Eq, Large, Large -> Some { a = Off (Sin q1 Inf) }
1225
| Ord.Eq, _, _ -> None
1226
| Ord.Lt, _, _ -> Some { a = Off (Chg q1 b1 (Chg q2 (inv_bound b2) Inf)) }
1227
| Ord.Gt, _, _ -> None
1228
end
1229
end
1230
Valid (301ms) (colibri2 3) (cvc5 22) (split_vc) (depth 1)
1231
let
get_convex_hull
x : convex_hull
1232
ensures { includes in_hull (fun (q:real) -> memt q x) result }
1233
=
1234
let rec get_last_on x =
1235
requires { ordered' x }
1236
ensures { forall q'. mem_if True q' x -> in_hull_sup q' result }
1237
variant { x }
1238
match x with
1239
| Sin _ on -> get_last_on on
1240
| Chg q b Inf -> Some (q, inv_bound b)
1241
| Chg _ _ off -> let _w = not_bottom' False off in get_last_off off
1242
| Inf -> None
1243
end
1244
with get_last_off x
1245
requires { x <> Inf }
1246
requires { ordered' x }
1247
ensures { forall q'. mem_if False q' x -> in_hull_sup q' result }
1248
variant { x }
1249
=
1250
match x with
1251
| Sin q Inf -> Some (q, Large)
1252
| Sin _ off -> let _w = not_bottom' False off in get_last_off off
1253
| Chg _ _ on -> get_last_on on
1254
| Inf -> absurd
1255
end
1256
in
1257
match x.a with
1258
| On on -> (None, get_last_on on)
1259
| Off off ->
1260
match off with
1261
| Sin q Inf -> (Some (q,Bound.Large), Some (q,Large))
1262
| Sin q off -> let _w = not_bottom' False off in (Some (q,Large), get_last_off off)
1263
| Chg q b on -> (Some (q,b), get_last_on on)
1264
| Inf -> absurd
1265
end
1266
end
1267
1268
scope Increasing

footprint, the bounds are in the definition bounds

1270
predicate
foot_if
(r1:infr) (r2:infr) (l:t'') =
1271
match l with
1272
| Sin q l -> le_infr r1 (R q) /\ le_infr (R q) r2 /\ foot_if r1 r2 l
1273
| Chg q _ l -> le_infr r1 (R q) /\ le_infr (R q) r2 /\ foot_if r1 r2 l
1274
| Inf -> r2 = I
1275
end
1276
1277
predicate
foot
(r1:infr) (r2:infr) (l:t') =
1278
match l with
1279
| On l -> r1 = I /\ foot_if r1 r2 l
1280
| Off l -> foot_if r1 r2 l
1281
end
1282
Valid (383ms) (cvc5)
1283
let rec lemma
foot_if_inf
(l:t'') : unit
1284
ensures { foot_if I I l } =
1285
match l with
1286
| Sin _ l | Chg _ _ l -> foot_if_inf l
1287
| Inf -> ()
1288
end
1296
1297
(* predicate foot_if (if_:bool) (x:real) (l:t'') = match l with | Sin q l -> if q <. x then foot_if if_ x l else (if if_ then x <=. q else x = q) | Chg q b l -> if q <. x then foot_if (notb if_) x l else (q = x \/ if_) | Inf -> if_ end *)
1298
1299
scope Unary Valid (18ms) (cvc5)
1300
type
siop
= {
1301
ghost
minr
: infr;
1302
ghost
maxr
: infr;
1303
ghost
ur
: real -> real;
1304
uq
: Q.t -> Q.t;
1305
}
1306
invariant { forall v: Q.t. in_infr minr v maxr -> ur v = uq v }
1307
by { minr = I; maxr = I; ur = (fun x -> x); uq = (fun q -> q); }
1308
1309
predicate
in_siop
(op:siop) (r:real) =
1310
in_infr op.minr r op.maxr

unary stricly increasing

1313
predicate
si1
(op: siop) =
1314
(forall v v' [op.ur v,op.ur v']. v <. v' -> op.ur v <. op.ur v')
1315
Valid (323ms) (cvc4)
1316
let rec
op_si1_cst'
(op: siop) (ghost if_) (l:t'') : t''
1317
requires { ordered' l }
1318
requires { si1 op }
1319
requires { foot_if op.minr op.maxr l }
1320
ensures { ordered' result }
1321
ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur q) result) }
1322
ensures { forall q. ((mem_if if_ q l) -> mem_if if_ (op.ur q) result) }
1323
variant { length' l }
1324
=
1325
match l with
1326
| Sin q l' -> Sin (op.uq q) (op_si1_cst' op if_ l')
1327
| Chg q bv l' ->
1328
Chg (op.uq q) bv (op_si1_cst' op (notb if_) l')
1329
| Inf -> Inf
1330
end
1331
Valid (290ms) (colibri2 15) (split_vc) (depth 1)
1332
let lemma
mem_is_in_foot
l min max q =
1333
requires { foot min max l }
1334
requires { mem q l }
1335
ensures { in_infr min q max }
1336
let rec ghost aux l if_ (min max:infr) (q:real) =
1337
requires { foot_if min max l }
1338
requires { mem_if if_ q l }
1339
ensures { le_infr (R q) max }
1340
variant { l }
1341
match l with
1342
| Sin _ l -> if pure { mem_if if_ q l } then aux l if_ min max q
1343
| Chg _ _ l -> if pure { mem_if (notb if_) q l } then aux l (notb if_) min max q
1344
| Inf -> ()
1345
end
1346
in
1347
match l with
1348
| On l-> aux l True min max q
1349
| Off Inf -> absurd
1350
| Off (Sin _ l) -> if pure { mem_if False q l } then aux l False min max q
1351
| Off (Chg _ _ l) -> aux l True min max q
1352
end
1353
Valid (90ms) (colibri2)
1354
let
op_si1_cst
(op: siop) l
1355
requires { si1 op }
1356
requires { foot op.minr op.maxr l.a }
1357
ensures { sound1 memt op.ur l result }
1358
=
1359
match l.a with
1360
| On Inf ->
1361
{ a = On Inf }
1362
| On l' ->
1363
{ a = On (op_si1_cst' op True l') }
1364
| Off Inf -> absurd
1365
| Off l' ->
1366
let _ = not_bottom l in
1367
{ a = Off (op_si1_cst' op False l') }
1368
end
1369
Valid (52ms) (colibri2 6) (cvc4 2) (cvc5) (split_vc) (depth 1)
1370
let
test__inv_sub
(min_pos:Q.t) l
1371
requires { 0. <. min_pos }
1372
requires { foot (R min_pos) I l.a }
1373
ensures { forall q. (mem q l.a) -> mem (-. (1. /. q)) result.a }
1374
=
1375
let function fur (x:real) = pure { if (Q.real min_pos) <=. x then (-. (1. /. x)) else (-. (1. /. (Q.real min_pos)) +. (x -. (Q.real min_pos))) } in
1376
let fuq (x:Q.t) ensures { min_pos <=. x -> result = fur x } =
1377
if Q.le min_pos x then (Q.sub (Q.of_int 0) (Q.div (Q.of_int 1) x)) else Q.of_int 0
1378
in
1379
let lemma inc (v v':real)
1380
requires { v <. v' }
1381
ensures { fur v <. fur v' }
1382
= if Q.real min_pos <=. v then assert { 1. /. v' <. 1. /. v }
1383
else if Q.real min_pos <. v' then assert { 1. /. v' <. 1. /. Q.real min_pos }
1384
in
1385
let op = { minr = (R (Q.real min_pos)); maxr = I; ur = fur; uq = fuq } in
1386
op_si1_cst op l

unary stricly decreasing

1389
predicate
sd1
(op: siop) =
1390
(forall v v' [op.ur v,op.ur v']. v <. v' -> op.ur v' <. op.ur v)
1391
1392
predicate
first_bound'
(x:real) (l:t'') =
1393
match l with
1394
| Sin q _ -> x = q
1395
| Chg q _ _ -> x = q
1396
| Inf -> true
1397
end
1398
Valid (28ms) (cvc5)
1399
let ghost
smaller_first_bound
(x:real) (y:real) (m:t'')
1400
requires { x <. y }
1401
requires { first_bound' y m }
1402
requires { ordered' m }
1403
ensures { lt_bound' x m }
1404
= ()
1405
1406
predicate
mem_if_not_top
(if_:bool) (x:real) (l:t'') =
1407
match l with
1408
| Sin q l ->
1409
if q <. x then mem_if if_ x l else (if if_ then false else x = q)
1410
| Chg q b l ->
1411
if cmp q b x then mem_if (notb if_) x l else (if if_ then x = q else false)
1412
| Inf -> false
1413
end
1414
1415
1416
predicate
is_bound'
(x:real) (l:t'') =
1417
match l with
1418
| Sin q l ->
1419
x = q \/ is_bound' x l
1420
| Chg q _ l ->
1421
x = q \/ is_bound' x l
1422
| Inf -> False
1423
end
1424
1425
predicate
is_bound
(x:real) (l:t') =
1426
match l with
1427
| On l -> is_bound' x l
1428
| Off l -> is_bound' x l
1429
end
1430
1431
Valid (3.7s) (colibri2 5) (cvc4 2) (cvc5 32) (split_vc 4) (depth 2)
1432
let rec
op_sd1_cst'
(op: siop) (l:t'') (acc:t'') if_ (ghost curr:real) : t
1433
requires { sd1 op }
1434
requires { ordered' l }
1435
requires { ordered' acc }
1436
requires { foot_if op.minr op.maxr l }
1437
requires { lt_bound' curr l }
1438
requires { first_bound' (op.ur curr) acc }
1439
requires { not if_ -> l = Inf -> acc <> Inf }
1440
ensures { forall q. curr <. q -> mem_if if_ q l -> mem (op.ur q) result.a }
1441
ensures { forall q. mem_if_not_top if_ q acc -> mem q result.a }
1442
ensures { forall q. is_bound q result.a -> (is_bound' q acc \/ (exists q'. (q = op.ur q' /\ is_bound' q' l))) }
1443
variant { length' l }
1444
=
1445
match l with
1446
| Sin q l' ->
1447
smaller_first_bound pure {op.ur q} pure {op.ur curr} acc;
1448
op_sd1_cst' op l' (Sin (op.uq q) acc) if_ (Q.real q)
1449
| Chg q bv l' ->
1450
assert { forall p. cmp q bv p = cmp (op.ur p) bv (op.ur q) };
1451
smaller_first_bound pure {op.ur q} pure {op.ur curr} acc;
1452
op_sd1_cst' op l' (Chg (op.uq q) (inv_bound bv) acc) (notb if_) (Q.real q)
1453
| Inf -> if if_ then { a = On acc } else begin
1454
{ a = Off acc }
1455
end
1456
end
1457
Valid (583ms) (colibri2 2) (cvc5 31) (split_vc 2) (depth 2)
1458
let
op_sd1_cst
(op: siop) l
1459
requires { sd1 op }
1460
requires { foot op.minr op.maxr l.a }
1461
ensures { sound1 memt op.ur l result }
1462
=
1463
match l.a with
1464
| On (Sin q l') -> op_sd1_cst' op l' (Sin (op.uq q) Inf) True (Q.real q)
1465
| On (Chg q bv l') -> op_sd1_cst' op l' (Chg (op.uq q) (inv_bound bv) Inf) False (Q.real q)
1466
| On Inf -> {a=On Inf}
1467
| Off l' ->
1468
let ghost curr = match l' with
1469
| Sin q _ | Chg q _ _ -> let ghost r = (Q.real q) -. 1. in smaller_first_bound r (Q.real q) l'; r
1470
| Inf -> 0.
1471
end
1472
in
1473
op_sd1_cst' op l' Inf False curr
1474
end
1475
Valid (81ms) (colibri2)
1476
let
neg
l
1477
ensures { sound1 memt (fun (x:real) -> -. x) l result }
1478
=
1479
let negq (x:Q.t) ensures { result = -. x } = Q.sub (Q.of_int 0) x in
1480
let op = { ur = (fun x -> -.x); uq = negq; minr = I; maxr = I } in
1481
op_sd1_cst op l
1482
Valid (62ms) (colibri2 2) (cvc5 7) (split_vc) (depth 1)
1483
let
mult_cst
c l
1484
ensures { sound1 memt (fun (x:real) -> c *. x) l result }
1485
=
1486
let fq (x:Q.t) ensures { result = c *. x } = Q.mul c x in
1487
let ghost function fr (x:real) = (Q.real c) *. x in
1488
let op = { minr = I; maxr = I; ur = fr; uq = fq } in
1489
match Q.compare (Q.of_int 0) c with
1490
| Ord.Eq -> singleton (Q.of_int 0)
1491
| Ord.Lt -> op_si1_cst op l
1492
| Ord.Gt ->
1493
let lemma op_sd1_aux (v v' : real) : unit
1494
requires { v <. v' }
1495
ensures { op.ur v' <. op.ur v } =
1496
assert { fr v' <. fr v }
1497
in
1498
op_sd1_cst op l
1499
end
1500
1501
end
1502
1503
type
presence
=
1504
|
Near
t''
1505
|
Far
t''
1506
1507
predicate
mem_presence
(c:real) (q:real) (p:presence) =
1508
match p with
1509
| Near l -> cmp c Strict q /\ mem_if True q l
1510
| Far l -> cmp c Strict q /\ mem_if False q l
1511
end
1512
1513
predicate
ordered_presence
(c:real) (p:presence) =
1514
match p with
1515
| Near l -> lt_bound' c l /\ ordered' l
1516
| Far l -> lt_bound' c l /\ ordered' l
1517
end
1518
Valid (33ms) (cvc5)
1519
let lemma
mem_ordered_presence_is_gt
(c:real) (q:real) (p:presence) =
1520
requires { mem_presence c q p }
1521
requires { ordered_presence c p }
1522
ensures { c <. q }
1523
match p with
1524
| Near _ -> ()
1525
| Far l -> lt_bound_is_mem False c l
1526
end
1527
Valid (483ms) (colibri2 8) (cvc5) (split_vc 2) (depth 2)
1528
let
pos_union_is_presence
(r:Q.t) (l:t'') : presence
1529
requires { ordered' l}
1530
requires { forall q. mem_if False q l -> r <. q }
1531
ensures { ordered_presence r result }
1532
ensures { forall q. mem_if False q l -> mem_presence r q result } =
1533
match l with
1534
| Sin q _ -> assert { mem_if False q l }; Far l
1535
| Chg q b l' ->
1536
match Q.compare r q with
1537
| Ord.Eq ->
1538
assert { b = Large -> mem_if False r l };
1539
assert { b = Strict }; Near l'
1540
| x ->
1541
let ghost p =
1542
let v = match l' with
1543
| Sin q' _ -> pure { Q.real q' }
1544
| Chg q' _ _ -> pure { Q.real q' }
1545
| Inf -> pure { q +. 1. }
1546
end
1547
in
1548
pure { 0.5 *. q +. 0.5 *. (min r v) }
1549
in
1550
assert { x = Ord.Gt -> (mem_if False p l /\ p <. r)};
1551
assert { x = Ord.Lt };
1552
Far l
1553
end
1554
| Inf -> Far Inf
1555
end
1556
Valid (34ms) (cvc5)
1557
let ghost
not_bottom_presence
(c:real) (l:presence) : real
1558
requires { ordered_presence c l }
1559
requires { not (l = Far Inf) }
1560
ensures { mem_presence c result l } =
1561
match l with
1562
| Far l -> not_bottom_after' c False l
1563
| Near l -> not_bottom_after' c True l
1564
end
1565
Valid (101ms) (colibri2)
1566
let
presence_to_t
(c:Q.t) (t:presence) : option t
1567
requires { ordered_presence c t }
1568
ensures { forall x. mem_presence c x t <-> match result with None -> false | Some r -> mem x r.a end } =
1569
match t with
1570
| Far Inf -> None
1571
| Far x -> Some { a = Off x }
1572
| Near x -> Some { a = Off (Chg c Strict x) }
1573
end
1574
1575
Valid (1.9s) (colibri2 9) (cvc4 5) (cvc5 29) (split_vc 8) (depth 3)
1576
let rec
split_at'
if_ l acc (ghost current : real) (ghost orig: t) : (p1:presence,b:bool,p2:presence) =
1577
requires { ordered' l }
1578
requires { ordered' acc }
1579
requires { lt_bound' 0. acc }
1580
requires { lt_bound' current l }
1581
requires { current <. 0. }
1582
requires { Unary.first_bound' (-. current) acc }
1583
requires { forall q. (mem q orig.a) -> if current <. q then mem_if if_ q l else mem_if if_ (-. q) acc }
1584
requires { forall q. -. current <=. q -> mem_if if_ q acc -> mem (-. q) orig.a }
1585
requires { forall q. current <. q -> mem_if if_ q l -> mem q orig.a }
1586
ensures { ordered_presence 0. p1 }
1587
ensures { ordered_presence 0. p2 }
1588
ensures { forall q. (mem q orig.a) -> (if 0. <. q then mem_presence 0. q p2 else if 0. = q then b else mem_presence 0. (-. q) p1) }
1589
ensures { forall q. mem_presence 0. q p1 -> mem (-. q) orig.a }
1590
ensures { forall q. mem_presence 0. q p2 -> mem q orig.a }
1591
ensures { b -> mem 0. orig.a }
1592
variant { length' l }
1593
match l with
1594
| Sin q l' ->
1595
match Q.compare q (Q.of_int 0) with
1596
| Ord.Eq ->
1597
let llt = if if_ then Near acc else Far acc in
1598
let lgt = if if_ then Near l' else Far l' in
1599
(llt,notb if_,lgt)
1600
| Ord.Lt ->
1601
Unary.smaller_first_bound pure {-. q} pure {-. current} acc;
1602
split_at' if_ l' (Sin (Q.sub (Q.of_int 0) q) acc) (Q.real q) orig
1603
| Ord.Gt ->
1604
1605
let llt = if if_ then Near acc else Far acc in
1606
let lgt = if if_ then Near l else Far l in
1607
(llt,if_,lgt)
1608
end
1609
| Chg q bv l' ->
1610
match Q.compare q (Q.of_int 0) with
1611
| Ord.Eq ->
1612
let llt = if if_ then Near acc else Far acc in
1613
let lgt = if if_ then Far l' else Near l' in
1614
let b = match bv with
1615
| Large -> notb if_
1616
| Strict -> if_
1617
end in
1618
(llt,b,lgt)
1619
| Ord.Lt ->
1620
Unary.smaller_first_bound pure {-. q} pure {-. current} acc;
1621
split_at' (notb if_) l' (Chg (Q.sub (Q.of_int 0) q) (inv_bound bv) acc) (Q.real q) orig
1622
| Ord.Gt ->
1623
let llt = if if_ then Near acc else Far acc in
1624
let lgt = if if_ then Near l else Far l in
1625
1626
(llt,if_,lgt)
1627
end
1628
| Inf ->
1629
let llt = if if_ then Near acc else Far acc in
1630
let lgt = if if_ then Near l else Far l in
1631
(llt,if_,lgt)
1632
end
1633
Valid (78ms) (colibri2)
1634
let rec ghost
first_bound_is_foot_if
(x:real) (q:real) l =
1635
requires { x <=. q }
1636
requires { Unary.first_bound' q l }
1637
requires { ordered' l }
1638
ensures { foot_if (R x) I l }
1639
variant { l }
1640
match l with
1641
| Sin _ ((Sin q _ | Chg q _ _) as l) -> first_bound_is_foot_if x (Q.real q) l
1642
| Chg _ _ ((Sin q _ | Chg q _ _) as l) -> first_bound_is_foot_if x (Q.real q) l
1643
| Sin _ Inf -> ()
1644
| Chg _ _ Inf -> ()
1645
| Inf -> ()
1646
end
1647
1648
Valid (83ms) (colibri2)
1649
let rec ghost
lt_bound_is_foot_if
(x:real) (q:real) l =
1650
requires { x <=. q }
1651
requires { lt_bound' q l }
1652
requires { ordered' l }
1653
ensures { foot_if (R x) I l }
1654
variant { l }
1655
match l with
1656
| Sin _ l -> lt_bound_is_foot_if x q l
1657
| Chg _ _ l -> lt_bound_is_foot_if x q l
1658
| Sin _ Inf -> ()
1659
| Chg _ _ Inf -> ()
1660
| Inf -> ()
1661
end
1662
1663
Valid (1.4s) (colibri2 58) (cvc4 5) (cvc5) (split_vc) (depth 1)
1664
let
split_at
(l:t) : (p1:presence,b:bool,p2:presence) =
1665
ensures { ordered_presence 0. p1 }
1666
ensures { ordered_presence 0. p2 }
1667
ensures { forall q. (mem q l.a) -> (if 0. <. q then mem_presence 0. q p2 else if 0. = q then b else mem_presence 0. (-. q) p1) }
1668
match l.a with
1669
| On l' ->
1670
match l' with
1671
| Sin q _ | Chg q _ _ ->
1672
if Q.le q (Q.of_int 0) then
1673
let ghost r = (Q.real q) -. 1. in Unary.smaller_first_bound r (Q.real q) l';
1674
split_at' True l' Inf r l
1675
else (
1676
Unary.smaller_first_bound 0.0 (Q.real q) l';
1677
Near Inf, True, Near l'
1678
)
1679
| Inf -> Near Inf, True, Near Inf
1680
end
1681
| Off l' ->
1682
match l' with
1683
| Sin q _ | Chg q _ _ ->
1684
if Q.le q (Q.of_int 0) then
1685
let ghost r = (Q.real q) -. 1. in Unary.smaller_first_bound r (Q.real q) l';
1686
split_at' False l' Inf r l
1687
else (
1688
Unary.smaller_first_bound 0.0 (Q.real q) l';
1689
Far Inf, False, Far l'
1690
)
1691
| Inf -> absurd
1692
end
1693
end
1694
1695
use real.Abs
1696
Valid (1.1s) (colibri2)
1697
let
union_bzero
(bzero:bool) (if_:bool) (l:t'')
1698
requires { ordered' l }
1699
requires { lt_bound' 0. l }
1700
ensures { ordered' result }
1701
ensures { forall q. 0. <. q -> mem_if if_ q l -> mem_if False q result }
1702
ensures { bzero <-> mem_if False 0. result }
1703
=
1704
let zero = Q.of_int 0 in
1705
if if_ then
1706
let b = (if bzero then Large else Strict) in
1707
Chg zero b l
1708
else
1709
if bzero then Sin zero l else l
1710
1711
let function
open_presence
(l:presence) =
1712
match l with
1713
| Far l -> False, l
1714
| Near l -> True, l
1715
end
1716
Valid (1.4s) (colibri2 8) (cvc4) (cvc5 3) (split_vc) (depth 1)
1717
let
abs_forward
(l:t) : t
1718
ensures { sound1 memt (fun (x:real) -> abs x) l result }
1719
=
1720
let neg,b,pos = split_at l in
1721
let ghost w = not_bottom l in
1722
let if_neg, neg = open_presence neg in
1723
let if_pos, pos = open_presence pos in
1724
let u = union' if_neg if_pos neg pos in
1725
assert { forall r. r <. 0. -> mem r l.a -> mem_if (orb if_neg if_pos) (-. r) u };
1726
assert { 0. <. w -> mem_if (orb if_neg if_pos) w u };
1727
let u' = union_bzero b (orb if_neg if_pos) u in
1728
assert { mem_if False (abs w) u' };
1729
let result = { a = Off u'} in
1730
assert { forall r. r >. 0. -> mem r l.a -> mem (abs r) result.a };
1731
assert { forall r. r = 0. -> mem r l.a -> mem (abs r) result.a };
1732
result
1733
Valid (33ms) (cvc5)
1734
let
abs_backward
(l:t) : t
1735
ensures { preimage1 memt (fun (x:real) -> abs x) l result }
1736
=
1737
union (Unary.neg l) l
1738
1739
scope Binary
1740
Valid (30ms) (cvc5)
1741
type
siop
= {
1742
ghost
minr
: infr;
1743
ghost
maxr
: infr;
1744
ghost
ur
: real -> real -> real;
1745
uq
: Q.t -> Q.t -> Q.t;
1746
}
1747
invariant { forall u v: Q.t. in_infr minr u maxr -> in_infr minr v maxr -> ur u v = uq u v }
1748
by { minr = I; maxr = I; ur = (fun x _ -> x); uq = (fun q _ -> q); }
1749
1750
predicate
in_siop
(op:siop) (r:real) =
1751
in_infr op.minr r op.maxr

stricly increasing

1754
predicate
si
(op:siop) =
1755
(forall u v v' [op.ur u v, op.ur u v']. v <. v' -> op.ur u v <. op.ur u v') /\
1756
(forall u u' v [op.ur u v, op.ur u' v]. u <. u' -> op.ur u v <. op.ur u' v)
1757
Valid (927ms) (cvc4)
1758
let rec
op_si_cst'
(op:siop) (x:Q.t) (l:t'') : t''
1759
requires { ordered' l }
1760
requires { si op }
1761
requires { in_siop op x }
1762
requires { foot_if op.minr op.maxr l }
1763
ensures { ordered' result }
1764
ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur x q) result) }
1765
ensures { forall if_ q. (mem_if if_ q l) <-> mem_if if_ (op.ur x q) result }
1766
variant { length' l }
1767
=
1768
match l with
1769
| Sin q l' -> Sin (op.uq x q) (op_si_cst' op x l')
1770
| Chg q bv l' ->
1771
assert { forall p. cmp q bv p = cmp (op.uq x q) bv (op.ur x p) };
1772
Chg (op.uq x q) bv (op_si_cst' op x l')
1773
| Inf -> Inf
1774
end
1775
1776
Valid (74ms) (cvc5)
1777
let
op_si_cst
(op: siop) l x
1778
requires { si op }
1779
requires { in_siop op x }
1780
requires { foot op.minr op.maxr l.a }
1781
ensures {
1782
forall q. (mem q l.a) <-> mem (op.ur x q) result.a
1783
}
1784
=
1785
match l.a with
1786
| On l ->
1787
{ a = On (op_si_cst' op x l) }
1788
| Off l ->
1789
let v = not_bottom' False l in
1790
let l = (op_si_cst' op x l) in
1791
assert { mem_if False (op.ur x v) l };
1792
{ a = Off l }
1793
end
1794
Valid (143ms) (colibri2)
1795
let
add_cst
l x
1796
ensures {
1797
forall q. (mem q l.a) <-> mem (x+.q) result.a
1798
}
1799
=
1800
let op = { minr = I; maxr = I; ur = (+.); uq = Q.add } in
1801
op_si_cst op l x
1802
1803
Valid (54ms) (cvc5)
1804
lemma
si_le
: forall op [si op]. si op -> (
1805
(forall u v v' [op.ur u v,op.ur u v']. v <=. v' -> op.ur u v <=. op.ur u v') /\
1806
(forall u u' v [op.ur u v, op.ur u' v]. u <=. u' -> op.ur u v <=. op.ur u' v)
1807
)
1808
Valid (361ms) (cvc5)
1809
lemma
si_cmp1
: forall op [si op]. si op -> (
1810
(forall u v v' b. cmp v b v' -> cmp (op.ur u v) b (op.ur u v')) /\
1811
(forall u u' v b. cmp u b u' -> cmp (op.ur u v) b (op.ur u' v))
1812
)
1813
Valid (391ms) (cvc5 2) (split_vc) (depth 1)
1814
lemma
si_cmp2
: forall op[si op]. si op -> (
1815
(forall u v b u' v' b'. cmp u b v -> cmp u' b' v' -> cmp (op.ur u u') (add_bound b b') (op.ur v v')) /\
1816
(forall u v b u' v' b'. (not (cmp u b v)) -> (not (cmp u' b' v')) -> (not (cmp (op.ur u u') (both_strict b b') (op.ur v v'))))
1817
)
1818
Valid (570ms) (colibri2 4) (cvc4) (cvc5 20) (split_vc 2) (depth 2)
1819
let rec
op_si_interval_on
(op: siop) (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t) (l:t'') : (result:t'')
1820
requires { si op }
1821
requires { (u <. v) }
1822
requires { ordered' l }
1823
requires { in_siop op u }
1824
requires { in_siop op v }
1825
requires { foot_if op.minr op.maxr l }
1826
ensures { ordered' result }
1827
ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur u q) result) }
1828
ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur v q) result) }
1829
ensures { forall q q'. (mem_if True q l /\ cmp u bu q' /\ not (cmp v bv q')) -> mem_if True (op.ur q' q) result }
1830
variant { length' l }
1831
=
1832
match l with
1833
| Sin _ l' ->
1834
assert { forall q'. mem_if True q' l -> mem_if True q' l'};
1835
op_si_interval_on op bu u v bv l'
1836
| Chg qs bq l' ->
1837
lt_bound_is_mem True (Q.real qs) l';
1838
let br = both_strict bq bv in
1839
let r = op.uq v qs in
1840
let res = op_si_interval_off_remain op bu u v bv r br (Q.real qs) l' in
1841
res
1842
| Inf -> Inf
1843
end
1844
Valid (378ms) (colibri2 20) (cvc4) (cvc5 2) (split_vc 2) (depth 2)
1845
with
op_si_interval_off
(op: siop) (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t) (l:t'') : (result:t'')
1846
requires { si op }
1847
requires { (u <. v) }
1848
requires { ordered' l }
1849
requires { in_siop op u }
1850
requires { in_siop op v }
1851
requires { foot_if op.minr op.maxr l }
1852
ensures { ordered' result }
1853
ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur u q) result) }
1854
ensures { forall q q'. (mem_if False q l /\ cmp u bu q' /\ (not (cmp v bv q'))) -> mem_if False (op.ur q' q) result }
1855
variant { length' l }
1856
=
1857
match l with
1858
| Sin qs l' ->
1859
lt_bound_is_mem False (Q.real qs) l';
1860
let r = op.uq v qs in
1861
let res = (op_si_interval_off_remain op bu u v bv r bv (Q.real qs) l') in
1862
let res = Chg (op.uq u qs) bu res in
1863
res
1864
| Chg qs b l' ->
1865
let bbu = add_bound b bu in
1866
let res0 = (op_si_interval_on op bu u v bv l') in
1867
let res = Chg (op.uq u qs) bbu res0 in
1868
res
1869
| Inf -> Inf
1870
end
1871
Valid (757ms) (colibri2 5) (cvc4 8) (cvc5 23) (split_vc 6) (depth 3)
1872
with
op_si_interval_off_remain
(op: siop) (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t) (r:Q.t) (br:Bound.t) (ghost rv:real) (l:t'') : (result:t'')
1873
requires { si op }
1874
requires { (u <. v) }
1875
requires { op.ur v rv = r }
1876
requires { lt_bound' rv l }
1877
requires { br = Strict -> bv = Strict }
1878
requires { in_siop op u }
1879
requires { in_siop op v }
1880
requires { foot_if op.minr op.maxr l }
1881
requires { ordered' l }
1882
ensures { ordered' result }
1883
ensures { forall q. (q <. r) -> (lt_bound' q result) }
1884
ensures { forall q q'. (mem_if False q l /\ cmp u bu q' /\ not (cmp v bv q')) -> mem_if True (op.ur q' q) result }
1885
ensures { forall q. not (cmp r br q) -> mem_if True q result }
1886
variant { length' l }
1887
=
1888
match l with
1889
| Sin qs l' ->
1890
lt_bound_is_mem False (Q.real qs) l';
1891
let qu = (op.uq u qs) in
1892
let r' = (op.uq v qs) in
1893
let res = (op_si_interval_off_remain op bu u v bv r' bv (Q.real qs) l') in
1894
match Q.compare r qu with
1895
| Ord.Lt ->
1896
1897
let res = Chg r br (Chg qu bu res) in
1898
res
1899
| Ord.Gt ->
1900
res
1901
| Ord.Eq ->
1902
match br, bu with
1903
| Large, Strict ->
1904
let res = Sin qu res in
1905
res
1906
| _ ->
1907
res
1908
end
1909
end
1910
| Chg qs b l' ->
1911
let qu = (op.uq u qs) in
1912
let bbu = add_bound b bu in
1913
let res = (op_si_interval_on op bu u v bv l') in
1914
match Q.compare r qu with
1915
| Ord.Lt ->
1916
let res2 = Chg r br (Chg qu bbu res) in
1917
res2
1918
| Ord.Gt ->
1919
let lemma smaller_true (q:Q.t) =
1920
requires { not (cmp r br q) }
1921
ensures { mem_if True q res }
1922
lt_bound_is_mem True (Q.real q) res
1923
in
1924
res
1925
| Ord.Eq ->
1926
match br, bbu with
1927
| Large, Strict ->
1928
let res = Sin qu res in
1929
res
1930
| _ ->
1931
res
1932
end
1933
end
1934
| Inf ->
1935
Chg r br Inf
1936
end
1937
Valid (33ms) (cvc5)
1938
let
op_si_interval'
(op: siop) if_ l (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t): (result:t'')
1939
requires { si op }
1940
requires { (u <. v) }
1941
requires { ordered' l }
1942
requires { in_siop op u }
1943
requires { in_siop op v }
1944
requires { foot_if op.minr op.maxr l }
1945
ensures { ordered' result }
1946
ensures {
1947
forall q q'. (mem_if if_ q l /\ cmp u bu q' /\ (not cmp v bv q')) -> mem_if if_ (op.ur q' q) result
1948
}
1949
ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur u q) result) }
1950
=
1951
if if_ then op_si_interval_on op bu u v bv l else op_si_interval_off op bu u v bv l
1952
1953
Valid (157ms) (cvc4)
1954
let
op_si_interval
(op: siop) l (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t): (result:t)
1955
requires { si op }
1956
requires { (u <. v) }
1957
requires { in_siop op u }
1958
requires { in_siop op v }
1959
requires { foot op.minr op.maxr l.a }
1960
ensures {
1961
forall q q'. (mem q l.a /\ cmp u bu q' /\ (not cmp v bv q')) -> mem (op.ur q' q) result.a
1962
}
1963
=
1964
match l.a with
1965
| On l ->
1966
let res = op_si_interval_on op bu u v bv l in
1967
{ a = On res }
1968
| Off l ->
1969
let w = not_bottom' False l in
1970
let l = (op_si_interval_off op bu u v bv l) in
1971
assert { mem_if False (op.ur (u*.0.5+.v*.0.5) w) l };
1972
{ a = Off l }
1973
end
1974
1975
1976
1977
Valid (385ms) (colibri2 6) (cvc4) (cvc5 18) (split_vc 3) (depth 2)
1978
let rec
op_si_minus_inf
(op: siop) (if_:bool) (v: Q.t) (bv:Bound.t) l: (result:t'')
1979
requires { si op }
1980
requires { ordered' l }
1981
requires { in_siop op v }
1982
requires { foot_if op.minr op.maxr l }
1983
ensures { ordered' result }
1984
ensures {
1985
forall q q'. ((not cmp v bv q) /\ mem_if if_ q' l) -> mem_if True (op.ur q q') result
1986
}
1987
ensures { forall q'' q' q. lt_bound' q l -> (not cmp v bv q') -> q'' <=. q -> mem_if True (op.ur q' q'') result }
1988
variant { length' l } =
1989
match l with
1990
| Sin qs Inf -> if if_ then Inf else Chg (op.uq v qs) bv Inf
1991
| Sin _ l' -> op_si_minus_inf op if_ v bv l'
1992
| Chg qs bs Inf -> if if_ then Chg (op.uq v qs) (add_bound bv bs) Inf else Inf
1993
| Chg _ _ l' -> op_si_minus_inf op (notb if_) v bv l'
1994
| Inf -> Inf
1995
end
1996
Valid (767ms) (colibri2 4) (cvc5 51) (split_vc 3) (depth 2)
1997
let rec
op_si_on
(op: siop) (if2:bool) (u:Q.t) (bu:Bound.t) (l1:t'') (l2:t'') : (result:t'')
1998
requires { si op }
1999
requires { lt_bound' u l1 }
2000
requires { in_siop op u }
2001
requires { foot_if op.minr op.maxr l1 }
2002
requires { foot_if op.minr op.maxr l2 }
2003
requires { ordered' l1 }
2004
requires { ordered' l2 }
2005
ensures { ordered' result }
2006
ensures { forall q q'. ((cmp u bu q /\ mem_if True q l1) /\ mem_if if2 q' l2) -> mem_if if2 (op.ur q q') result }
2007
ensures {
2008
forall q. lt_bound' q l2 -> lt_bound' (op.ur u q) result
2009
}
2010
variant { length' l1 }
2011
=
2012
match l1 with
2013
| Sin qs l1' ->
2014
let res1 = op_si_interval' op if2 l2 bu u qs Large in
2015
let res2 = op_si_on op if2 qs Strict l1' l2 in
2016
let res = union' if2 if2 res1 res2 in
2017
assert { forall q. (mem_if if2 q res1 \/ mem_if if2 q res2) -> mem_if if2 q res };
2018
res
2019
| Chg qs bq Inf ->
2020
op_si_interval' op if2 l2 bu u qs bq
2021
| Chg qs bq l1' ->
2022
let res1 = op_si_interval' op if2 l2 bu u qs bq in
2023
let res2 = op_si_off op if2 l1' l2 in
2024
let res = union' if2 if2 res1 res2 in
2025
assert { forall q. (mem_if if2 q res1 \/ mem_if if2 q res2) -> mem_if if2 q res };
2026
assert { forall q. (cmp q (inv_bound bq) qs \/ mem_if False q l1') -> mem_if True q l1 };
2027
res
2028
| Inf -> if if2 then Inf else
2029
match l2 with
2030
| Sin q2 _ -> Chg (op.uq u q2) bu Inf
2031
| Chg q2 b2 _ -> Chg (op.uq u q2) (add_bound bu b2) Inf
2032
| Inf -> Inf
2033
end
2034
end
2035
Valid (757ms) (colibri2 4) (cvc5 28) (split_vc 2) (depth 2)
2036
with
op_si_off
(op : siop) if2 (l1:t'') (l2:t'') : (result:t'')
2037
requires { si op }
2038
requires { foot_if op.minr op.maxr l1 }
2039
requires { foot_if op.minr op.maxr l2 }
2040
requires { ordered' l1 }
2041
requires { ordered' l2 }
2042
requires { l1 <> Inf }
2043
ensures { ordered' result }
2044
ensures { forall q q'. (mem_if False q l1 /\ mem_if if2 q' l2) -> mem_if if2 (op.ur q q') result }
2045
ensures {
2046
forall q q'.
2047
(lt_bound' q l1) -> (lt_bound' q' l2) ->
2048
(lt_bound' (op.ur q q') result )
2049
}
2050
variant { length' l1 }
2051
=
2052
match l1 with
2053
| Sin qs Inf -> op_si_cst' op qs l2
2054
| Sin qs l1' ->
2055
let res1 = op_si_cst' op qs l2 in
2056
let res2 = op_si_off op if2 l1' l2 in
2057
let res = union' if2 if2 res1 res2 in
2058
assert { forall q. (mem_if if2 q res1 \/ mem_if if2 q res2) -> mem_if if2 q res };
2059
res
2060
| Chg qs b l1' ->
2061
op_si_on op if2 qs b l1' l2
2062
| Inf -> absurd
2063
end
2064
2065
Valid (200ms) (colibri2 71) (cvc4 2) (split_vc 2) (depth 2)
2066
let
op_si
(op : siop) u v: (result:t)
2067
requires { si op }
2068
requires { foot op.minr op.maxr u.a }
2069
requires { foot op.minr op.maxr v.a }
2070
ensures { sound2 memt op.ur u v result }
2071
=
2072
let op_si_on' (op : siop) (if2:bool) l1 l2: (result:t'')
2073
requires { si op }
2074
requires { foot_if op.minr op.maxr l1 }
2075
requires { foot_if op.minr op.maxr l2 }
2076
requires { ordered' l1 }
2077
requires { ordered' l2 }
2078
ensures { ordered' result }
2079
ensures {
2080
forall q q'. (mem_if True q l1 /\ mem_if if2 q' l2) -> mem_if True (op.ur q q') result
2081
}
2082
=
2083
match l1 with
2084
| Sin qs l1' ->
2085
let res1 = op_si_minus_inf op if2 qs Large l2 in
2086
let res2 = op_si_on op if2 qs Strict l1' l2 in
2087
let res = union' True if2 res1 res2 in
2088
assert { forall q. (mem_if True q res1 \/ mem_if if2 q res2) -> mem_if True q res };
2089
assert { forall q. (cmp q Strict qs \/ (cmp qs Strict q /\ mem_if True q l1')) -> mem_if True q l1 };
2090
res
2091
| Chg qs bq Inf ->
2092
op_si_minus_inf op if2 qs bq l2
2093
| Chg qs bq l1' ->
2094
let res1 = op_si_minus_inf op if2 qs bq l2 in
2095
let res2 = op_si_off op if2 l1' l2 in
2096
let res = union' True if2 res1 res2 in
2097
assert { forall q. (mem_if True q res1 \/ mem_if if2 q res2) -> mem_if True q res };
2098
res
2099
| Inf -> Inf
2100
end
2101
in
2102
match u.a,v.a with
2103
| On u, On v -> { a = On (op_si_on' op True u v) }
2104
| On u, Off v -> { a = On (op_si_on' op False u v) }
2105
| Off u, On v -> { a = On (op_si_off op True u v) }
2106
| Off u, Off v ->
2107
let w = (op_si_off op False u v) in
2108
let ghost ux = not_bottom' False u in
2109
let ghost vx = not_bottom' False v in
2110
assert { mem_if False (op.ur ux vx) w };
2111
{ a = Off w }
2112
end
2113
Valid (151ms) (colibri2)
2114
let
add
u v: (result:t)
2115
ensures { sound2 memt (fun (x y:real) -> x +. y) u v result } =
2116
let op = { minr = I; maxr = I; ur = (+.); uq = Q.add } in
2117
op_si op u v
2118
2119
2120
2121
2122
Valid (315ms) (colibri2)
2123
let rec
find_max
if_ l : option (Bound.t,Q.t) =
2124
requires { ordered' l }
2125
requires { l = Inf -> if_ }
2126
ensures { match result with
2127
| None -> true
2128
| Some (b,m) -> forall q. mem_if if_ q l -> cmp q b m
2129
end }
2130
ensures { match result with
2131
| None -> true
2132
| Some (_,m) -> forall q. lt_bound' q l -> q <. m
2133
end }
2134
variant { l }
2135
match l with
2136
| Sin q Inf -> if if_ then None else Some (Large,q)
2137
| Sin _ l -> find_max if_ l
2138
| Chg q bv Inf -> if if_ then Some (inv_bound bv, q) else None
2139
| Chg _ _ l -> find_max (notb if_) l
2140
| Inf -> None
2141
end
2142
Valid (138ms) (colibri2)
2143
let ghost
compat_mul_lt
(x1 x2 y:real) =
2144
requires { x1 <. x2 }
2145
requires { 0. <. y }
2146
ensures { x1 *. y <. x2 *. y } ()
2147
Valid (190ms) (colibri2)
2148
let ghost
compat_mul_lt2
x1 (b:Bound.t) x2 y1 (c:Bound.t) y2 =
2149
requires { cmp x1 b x2 }
2150
requires { cmp y1 c y2 }
2151
requires { 0. <. x1 }
2152
requires { 0. <. y1 }
2153
ensures { cmp (x1 *. y1) (add_bound b c) (x2 *. y2) }
2154
(if pure { x1 = x2 } then () else
2155
compat_mul_lt x1 x2 y1);
2156
(if pure { y1 = y2 } then () else
2157
compat_mul_lt y1 y2 x2)
2158
Valid (97ms) (colibri2)
2159
let
hd_on
w : (q:Q.t,b:Bound.t,l:t'') =
2160
requires { w <> Inf }
2161
requires { ordered' w }
2162
requires { lt_bound' 0.0 w }
2163
ensures { ordered' l }
2164
ensures { lt_bound' (q *. 0.5) l }
2165
ensures { lt_bound' 0.0 l }
2166
ensures { 0.0 <. q }
2167
ensures { forall q'. mem_if True q' w -> (cmp q' b q \/ mem_if False q' l) }
2168
match w with
2169
| Inf -> absurd
2170
| Sin q l -> q, Strict, Chg q Strict l
2171
| Chg q bv l -> q, (inv_bound bv), l
2172
end
2173
Valid (404ms) (colibri2 74) (cvc5 35) (split_vc 2) (depth 2)
2174
let
mul_off
w x =
2175
requires { ordered' w }
2176
requires { ordered' x }
2177
requires { lt_bound' 0. w }
2178
requires { lt_bound' 0. x }
2179
(* ensures { lt_bound' (-1.) result } *)
2180
ensures { ordered' result }
2181
ensures {
2182
forall q q'. (mem_if False q w /\ mem_if False q' x) -> mem_if False (q*.q') result
2183
}
2184
match w, x with
2185
| Inf, _ | _, Inf -> Inf
2186
| (Sin q1 _ | Chg q1 _ _), (Sin q2 _ | Chg q2 _ _) ->
2187
let ghost m = min (Q.real q1) (Q.real q2) in
2188
let ghost ur' x y = match m <=. x, m <=. y with
2189
| True, True -> x *. y
2190
| False, True -> x -. m +. m *. y
2191
| True, False -> y -. m +. m *. x
2192
| False, False -> x -. m +. y -. m +. m *. m
2193
end
2194
in
2195
let op = { minr = R m; maxr = I; ur = ur'; uq = Q.mul } in
2196
assert { 0. <. m };
2197
let lemma inc2 (u v v':real)
2198
requires { v <. v' }
2199
ensures { op.ur u v <. op.ur u v' }
2200
= if m <=. u then begin
2201
if m <=. v then assert { u *. v <. u *. v' }
2202
else if m <=. v' then assert { m *. u <=. u *. v' }
2203
end else begin
2204
if m <=. v then assert { m *. v <. m *. v' }
2205
else if m <=. v' then begin
2206
assert { m *. v' -. m *. m = m *. (v' -. m) };
2207
assert { 0. <=. m *. (v' -. m) }
2208
end
2209
end
2210
in
2211
let lemma inc1 (u u' v:real)
2212
requires { u <. u' }
2213
ensures { op.ur u v <. op.ur u' v }
2214
= if m <=. v then begin
2215
if m <=. u then assert { u *. v <. u' *. v }
2216
else if m <=. u' then assert { m *. v <=. u' *. v }
2217
end else begin
2218
if m <=. u then assert { m *. u <. m *. u' }
2219
else if m <=. u' then assert { m *. m <=. m *. u' }
2220
end
2221
in
2222
first_bound_is_foot_if m (Q.real q1) w;
2223
first_bound_is_foot_if m (Q.real q2) x;
2224
op_si_off op False w x
2225
end
2226
Valid (225ms) (colibri2)
2227
let
mul_near_zero
if_w w xq xb =
2228
requires { ordered' w }
2229
requires { lt_bound' 0.0 w }
2230
requires { w <> Inf }
2231
requires { 0. <. xq }
2232
ensures { ordered' result }
2233
ensures { lt_bound' (-1.) result }
2234
ensures { forall q q'. 0. <. q -> mem_if if_w q w -> 0. <. q' -> cmp q' xb xq -> mem_if False (q *. q') result }
2235
match find_max if_w w with
2236
| None -> Chg (Q.of_int 0) Strict Inf
2237
| Some (wmb,wm) ->
2238
let lemma cmp_mul q q' =
2239
requires { 0. <. q }
2240
requires { cmp q wmb wm }
2241
requires { 0. <. q' }
2242
requires { cmp q' xb xq }
2243
ensures { 0. <. (q *. q') }
2244
ensures { cmp (q *. q') (add_bound wmb xb) (wm *. xq) }
2245
compat_mul_lt2 q wmb (Q.real wm) q' xb (Q.real xq)
2246
in
2247
Chg (Q.of_int 0) Strict (Chg (Q.mul wm xq) (inv_bound (add_bound wmb xb)) Inf)
2248
end
2249
Valid (368ms) (cvc4 3) (cvc5 66) (split_vc 2) (depth 2)
2250
let
mul_aux
w x =
2251
requires { ordered_presence 0. w }
2252
requires { ordered_presence 0. x }
2253
ensures { ordered' result }
2254
ensures { forall q,q'. mem_presence 0. q w -> mem_presence 0. q' x -> mem_if False (q *. q') result }
2255
match w, x with
2256
| Far Inf, _ | _, Far Inf -> Inf
2257
| Near Inf, _ | _, Near Inf -> Chg (Q.of_int 0) Strict Inf
2258
| Near w, Near x ->
2259
let (wq,wb,wl) = hd_on w in
2260
let (xq,xb,xl) = hd_on x in
2261
let l1 = mul_near_zero True w xq xb in
2262
let l2 = mul_near_zero True x wq wb in
2263
let l3 = mul_off wl xl in
2264
union' False False (union' False False l1 l2) l3
2265
| Far w, Far x -> mul_off w x
2266
| Near w, Far x | Far x, Near w ->
2267
let (wq,wb,wl) = hd_on w in
2268
let l2 = mul_near_zero False x wq wb in
2269
let l3 = mul_off wl x in
2270
union' False False l2 l3
2271
end
2272
Valid (590ms) (cvc4)
2273
let
neg'
l : t
2274
requires { ordered' l }
2275
requires { l <> Inf }
2276
ensures { forall q. (mem_if False q l) -> mem (-. q) result.a }
2277
=
2278
let negq (x:Q.t) ensures { result = -. x } = Q.sub (Q.of_int 0) x in
2279
let ghost c = pure { match l with Inf -> 0. | Sin q _ | Chg q _ _ -> q -. 1. end } in
2280
let op = Unary.{ ur = (fun x -> -.x); uq = negq; minr = I; maxr = I } in
2281
Unary.op_sd1_cst' op l Inf False c
2282
2283
Valid (1.2s) (colibri2 27) (cvc4 4) (cvc5 7) (split_vc 2) (depth 2)
2284
let
mul
u v: (result:t)
2285
ensures { sound2 memt (fun x y -> x *. y) u v result } =
2286
let uinf, zu, upos = split_at u in
2287
let vinf, zv, vpos = split_at v in
2288
let u1 = (union' False False (mul_aux uinf vinf) (mul_aux upos vpos)) in
2289
let u2 = (union' False False (mul_aux uinf vpos) (mul_aux upos vinf)) in
2290
let z = { a = Off (Sin (Q.of_int 0) Inf) } in
2291
let lemma prod_in (x y:real)
2292
requires { memt x u /\ memt y v }
2293
ensures { 0. <. x *. y -> mem_if False (x *. y) u1 }
2294
ensures { x *. y <. 0. -> mem_if False (-. (x *. y)) u2 }
2295
ensures { x *. y = 0. -> orb zu zv }
2296
= if 0. <. x then begin
2297
if 0. <. y then assert { 0. <. x *. y /\ mem_if False (x *. y) u1 }
2298
else if y <. 0. then begin
2299
assert { x *. (-. y) = -. (x *. y) /\ x *. y <. 0. };
2300
assert { mem_if False (x *. (-. y)) u2 }
2301
end
2302
end else if x <. 0. then begin
2303
if 0. <. y then begin
2304
assert { (-. x) *. y = -. (x *. y) /\ x *. y <. 0. };
2305
assert { mem_if False ((-. x) *. y) u2 }
2306
end else if y <. 0. then begin
2307
assert { (-. x) *. (-. y) = x *. y /\ 0. <. x *. y };
2308
assert { mem_if False ((-. x) *. (-. y)) u1 }
2309
end
2310
end
2311
in
2312
match u1, u2 with
2313
| Inf, Inf ->
2314
let ghost eu = not_bottom u in
2315
let ghost ev = not_bottom v in
2321
(* assert { (uinf = (Far Inf) \/ vinf = (Far Inf)) /\ (upos = (Far Inf) \/ vpos = (Far Inf)) }; assert { (uinf = (Far Inf) \/ vpos = (Far Inf)) /\ (upos = (Far Inf) \/ vinf = (Far Inf)) }; assert { uinf = (Far Inf) -> upos = (Far Inf) -> eu = 0. }; assert { vinf = (Far Inf) -> vpos = (Far Inf) -> ev = 0. }; assert { uinf = (Far Inf) -> upos = (Far Inf) -> zu }; assert { vinf = (Far Inf) -> vpos = (Far Inf) -> zv }; *)
2322
assert { eu = 0. \/ ev = 0. };
2323
assert { orb zu zv }; z
2324
| Inf, u2 -> let u2 = (neg' u2) in if orb zu zv then union u2 z else u2
2325
| u1, Inf -> let u1 = { a = Off u1 } in if orb zu zv then union u1 z else u1
2326
| u1, u2 -> let u1 = {a = Off u1} in let u2 = neg' u2 in let r = union u1 u2 in if orb zu zv then union r z else r
2327
end
2328
Valid (161ms) (cvc4)
2329
lemma
inv_anti_monotonic
: forall q r. 0. <. q -> q <. r -> (1. /. r) <. (1. /. q)
2330
2331
Valid (410ms) (colibri2 14) (cvc5 30) (split_vc) (depth 1)
2332
let
inv_pos_off
wl (ghost wq:real) =
2333
requires { ordered' wl }
2334
(* requires { ordered' acc } *)
2335
requires { 0. <. wq }
2336
requires { lt_bound' wq wl }
2337
(* requires { Unary.first_bound' (1. /. wq) acc } *)
2338
ensures { forall q. mem_if False q wl -> mem_if False (1. /. q) result }
2339
(* ensures { forall q. mem_if False q result -> 0. <. q } *)
2340
(* ensures { forall q. Unary.mem_if_not_top False q acc -> mem_if False q result } *)
2341
ensures { ordered' result }
2342
match wl with
2343
| Inf -> Inf
2344
| _ ->
2345
let function ur' r =
2346
if r <=. wq then (-. r) +. wq +. (1. /. wq) else 1. /. r
2347
in
2348
let uq' (q:Q.t) =
2349
ensures { wq <=. q -> result = ur' q }
2350
if Q.equal q (Q.of_int 0) then q else Q.div (Q.of_int 1) q
2351
in
2352
lt_bound_is_foot_if wq wq wl;
2353
let op = Unary.{
2354
uq = uq';
2355
ur = ur';
2356
minr = R wq; maxr = I;
2357
} in
2358
let lemma sdop v v' =
2359
requires { v <. v' }
2360
ensures { op.Unary.ur v' <. op.Unary.ur v }
2361
match v <=. wq, v' <=. wq with
2362
| True, True -> ()
2363
| True, False -> assert { 1. /. v' <. 1. /. wq }
2364
| False, True -> absurd
2365
| False, False -> assert { 1. /. v' <. 1. /. v }
2366
end
2367
in
2368
let v = Unary.op_sd1_cst' op wl Inf False wq in
2369
match v.a with
2370
| Off v -> v
2371
| On v' ->
2372
let rec ghost pos_bound l =
2373
requires { ordered' l }
2374
requires { lt_bound' 0. l }
2375
ensures { forall q. Unary.is_bound' q l -> 0. <. q }
2376
variant { l }
2377
match l with
2378
| Sin _ l -> pos_bound l
2379
| Chg _ _ l -> pos_bound l
2380
| Inf -> ()
2381
end
2382
in
2383
let rec ghost bound_pos l =
2384
requires { forall q. Unary.is_bound' q l -> 0. <. q }
2385
ensures { lt_bound' 0. l }
2386
variant { l }
2387
match l with
2388
| Sin q l' -> assert { Unary.is_bound' q l }; assert { forall q'. Unary.is_bound' q' l' -> Unary.is_bound' q' l }; bound_pos l'
2389
| Chg q _ l' -> assert { Unary.is_bound' q l }; assert { forall q'. Unary.is_bound' q' l' -> Unary.is_bound' q' l }; bound_pos l'
2390
| Inf -> ()
2391
end
2392
in
2393
pos_bound wl;
2394
assert { forall q. Unary.is_bound' q v' -> Unary.is_bound q v.a };
2395
assert { forall q. Unary.is_bound' q v' -> (exists q'. (q = ur' q' /\ Unary.is_bound' q' wl)) };
2396
assert { forall q. Unary.is_bound' q v' -> (exists q'. (q = ur' q' /\ 0. <. q')) };
2397
assert { forall q. Unary.is_bound' q v' -> 0. <. q };
2398
bound_pos v';
2399
Chg (Q.of_int 0) Strict v'
2400
end
2401
end
2402
Valid (345ms) (colibri2) (cvc4) (cvc5 13) (split_vc) (depth 1)
2403
let
inv_pos
u =
2404
requires { ordered_presence 0. u }
2405
ensures { forall q. mem_presence 0. q u -> mem_if False (1. /. q) result }
2406
(* ensures { forall q. mem_if False q result -> 0. <. q } *)
2407
ensures { ordered' result }
2408
match u with
2409
| Near Inf -> Chg (Q.of_int 0) Strict Inf
2410
| Near w ->
2411
let (wq,wb,wl) = hd_on w in
2412
let wq' = Q.div (Q.of_int 1) wq in
2413
let acc = Chg wq' wb Inf in
2414
assert { forall q. cmp 0. Strict q -> cmp q wb wq -> mem_if False (1. /. q) acc };
2415
let acc' = inv_pos_off wl (Q.real wq *. 0.5) in
2416
union' False False acc acc'
2417
| Far w ->
2418
let ghost wq = pure { match w with Inf -> 0.5 | Sin q _ | Chg q _ _ -> q *. 0.5 end } in
2419
inv_pos_off w wq
2420
end
2421
Valid (968ms) (colibri2 16) (cvc4 2) (split_vc 3) (depth 3)
2422
let
inv
(u:t): (result:t)
2423
ensures { sound1 memt (fun (x:real) -> 1. /. x) u result }
2424
=
2425
let uinf, zu, upos = split_at u in
2426
if zu then let x = { a = On Inf } in x
2427
else
2428
let uinf = inv_pos uinf in
2429
let upos = inv_pos upos in
2431
(* let negq (x:Q.t) ensures { result = -. x } = Q.sub (Q.of_int 0) x in let op = { ur = (fun x -> -.x); uq = negq; minr = I; maxr = I } in *)
2432
match upos, uinf with
2433
| Inf, Inf ->
2434
let ghost eu = not_bottom u in
2435
assert { eu = eu };
2436
absurd
2437
| Inf, u2 -> Unary.neg { a = Off u2 }
2438
| u1, Inf -> { a = Off u1 }
2439
| u1, u2 -> union (Unary.neg { a = Off u2 }) { a = Off u1 }
2440
end
2441
Valid (401ms) (colibri2 5) (cvc5 2) (split_vc 2) (depth 2)
2442
let
div
u v : t =
2443
ensures { sound2 memt (fun (x y:real) -> x /. y) u v result }
2444
if mem (Q.of_int 0) v then let x = { a = On Inf } in x
2445
else begin
2446
let v' = inv v in
2447
let r = mul u v' in
2448
let lemma m (q q':real)
2449
requires { mem q u.a }
2450
requires { mem q' v.a }
2451
ensures { mem (q /. q') r.a }
2452
= assert { mem (1. /. q') v'.a };
2453
assert { q /. q' = q *. (1. /. q') } in
2454
r
2455
end
2456
end
2457
end
2458
2459
scope NonIncreasing Valid (34ms) (cvc5)
2460
type
unary
= {
2461
uq
: Q.t -> Q.t;
2462
ghost
ur
: real -> real;
2463
(* uq_left: Q.t -> (Bound.t,Q.t); *)
2464
(* uq_right: Q.t -> (Bound.t,Q.t); *)
2465
(* ghost ur_left: real -> Bound.t; *)
2466
(* ghost ur_right: real -> Bound.t; *)
2467
}
2468
invariant { forall v:Q.t. (ur v) = (uq v) }
2469
by {
2470
ur = (fun r -> r);
2471
uq = (fun q -> q);
2472
(* uq = (fun q -> Strict,q,Strict); *)
2473
(* ur_left = (fun _ -> Strict); *)
2474
(* ur_right = (fun _ -> Strict); *)
2475
}

unary non–strict increasing

2478
predicate
nsi1
(op:unary) =
2479
(forall v v' [op.ur v,op.ur v']. v <. v' -> (op.ur v) <=. (op.ur v'))
2480
Valid (307ms) (cvc5)
2481
lemma
nsi1_cmp
: forall op[nsi1 op]. nsi1 op ->
2482
(forall v v' b. cmp v b v' -> cmp (op.ur v) Large (op.ur v'))
2483
Valid (958ms) (colibri2 5) (cvc4) (cvc5 32) (split_vc 3) (depth 2)
2484
let rec
op_nsi1_sin
start (ghost rstart:real) if_ op (l:t'') : t''
2485
requires { ordered' l }
2486
requires { nsi1 op }
2487
requires { lt_bound' rstart l }
2488
requires { op.ur rstart = start }
2489
ensures { ordered' result }
2490
ensures { forall q. q <. start -> (lt_bound' q result) }
2491
ensures { forall q. (mem_if if_ q l) -> rstart <=. q -> mem_if False (op.ur q) result }
2492
ensures { mem_if False start result }
2493
variant { length' l }
2494
=
2495
match l with
2496
| Sin q l' ->
2497
let qop = (op.uq q) in
2498
if Q.equal start qop
2499
then op_nsi1_sin start rstart if_ op l'
2500
else if if_
2501
then begin
2502
Chg start Large (op_nsi1_wait if_ op l')
2503
end
2504
else Sin start (op_nsi1_sin qop (Q.real q) if_ op l')
2505
| Chg q _ l' ->
2506
(* assert { forall p. cmp q bv p = cmp (op.ur q) Large (op.ur p) };*)
2507
let qop = (op.uq q) in
2508
if Q.equal start qop then op_nsi1_sin start rstart (notb if_) op l'
2509
else if if_ then
2510
Chg start Large (op_nsi1_inter qop (Q.real q) op l')
2511
else
2512
Sin start (op_nsi1_sin qop (Q.real q) (notb if_) op l')
2513
| Inf -> if if_ then Chg start Large Inf else Sin start Inf
2514
end Valid (878ms) (colibri2 24) (split_vc) (depth 1)
2515
with
op_nsi1_inter
stop (ghost rstop:real) op (l:t'') : t''
2516
requires { ordered' l }
2517
requires { nsi1 op }
2518
requires { lt_bound' rstop l }
2519
requires { op.ur rstop = stop }
2520
ensures { ordered' result }
2521
ensures { forall q. q <. stop -> (lt_bound' q result) }
2522
ensures { forall q. (mem_if False q l) -> mem_if True (op.ur q) result }
2523
ensures { forall q. q <=. stop -> mem_if True q result }
2524
variant { length' l }
2525
=
2526
match l with
2527
| Sin q l' ->
2528
let qop = (op.uq q) in
2529
if Q.equal stop qop
2530
then op_nsi1_inter stop (Q.real q) op l'
2531
else
2532
Chg stop Strict (op_nsi1_sin qop (Q.real q) False op l')
2533
| Chg q _ l' ->
2534
(* assert { forall p. cmp q bv p = cmp (op.ur q) Large (op.ur p) };*)
2535
let qop = (op.uq q) in
2536
if Q.equal stop qop then begin
2537
let r = op_nsi1_wait True op l' in
2538
let lemma aux q' =
2539
requires { q' <. stop }
2540
ensures { mem_if True q' r }
2541
lt_bound_is_mem True q' r;
2542
in
2543
r
2544
end
2545
else
2546
Chg stop Strict (op_nsi1_sin qop (Q.real q) True op l')
2547
| Inf -> Chg stop Strict Inf
2548
end Valid (547ms) (colibri2)
2549
with
op_nsi1_wait
if_ op (l:t'') : t''
2550
requires { ordered' l }
2551
requires { nsi1 op }
2552
ensures { ordered' result }
2553
ensures { forall q q'. (lt_bound' q l) -> q' <. op.ur q -> (lt_bound' q' result) }
2554
ensures { forall q. (mem_if if_ q l) -> mem_if if_ (op.ur q) result }
2555
variant { length' l }
2556
=
2557
match l with
2558
| Sin q l' ->
2559
let qop = (op.uq q) in
2560
if if_ then op_nsi1_wait if_ op l'
2561
else op_nsi1_sin qop (Q.real q) False op l'
2562
| Chg q _ l' ->
2563
(*assert { forall p. cmp q bv p = cmp (op.ur q) Large (op.ur p) };*)
2564
let qop = (op.uq q) in
2565
if if_ then op_nsi1_inter qop (Q.real q) op l'
2566
else op_nsi1_sin qop (Q.real q) True op l'
2567
| Inf -> Inf
2568
end
2569
2570
2571
Valid (56ms) (colibri2)
2572
let
op_nsi1
(op:unary) l
2573
requires { nsi1 op }
2574
ensures { sound1 memt op.ur l result }
2575
=
2576
match l.a with
2577
| On l ->
2578
{ a = On (op_nsi1_wait True op l) }
2579
| Off l ->
2580
let v = not_bottom' False l in
2581
let l = (op_nsi1_wait False op l) in
2582
assert { mem_if False (op.ur v) l };
2583
{ a = Off l }
2584
end
2585
2586
use real.Truncate
2587
use real.FromInt
2588
Valid (54ms) (colibri2)
2589
let
ceil
l =
2590
ensures { sound1 memt (fun (x:real) -> from_int (ceil x)) l result }
2591
let qceil x = Q.of_bigint (Q.ceil_z x) in
2592
let ghost rceil x = from_int (ceil x) in
2593
let op = { uq = qceil; ur = rceil } in
2594
op_nsi1 op l
2595
Valid (49ms) (colibri2)
2596
let
floor
l =
2597
ensures { sound1 memt (fun (x:real) -> from_int (floor x)) l result }
2598
let qfloor x = Q.of_bigint (Q.floor_z x) in
2599
let ghost rfloor x = from_int (floor x) in
2600
let op = { uq = qfloor; ur = rfloor } in
2601
op_nsi1 op l
2602
Valid (63ms) (colibri2)
2603
let
truncate
l =
2604
ensures { sound1 memt (fun (x:real) -> from_int (truncate x)) l result }
2605
let q x = Q.of_bigint (Q.truncate_z x) in
2606
let ghost r x = from_int (truncate x) in
2607
let op = { uq = q; ur = r } in
2608
op_nsi1 op l
2609
2610
2611
use real.MinMax
2612
Valid (69ms) (cvc5)
2613
let
relu
l =
2614
ensures { sound1 memt (fun (x:real) -> max 0. x) l result }
2615
let zero = Q.of_int 0 in
2616
let qrelu x = if Q.le zero x then x else zero in
2617
let ghost rrelu x = max 0. x in
2618
let op = { uq = qrelu; ur = rrelu } in
2619
op_nsi1 op l
2620
2621
end
2622
2623
2624
use list.List
2625
2626
scope Map
2627
type
qbound
=
2628
|
BInf
2629
|
BLarge
Q.t
2630
|
BStrict
Q.t
2631
2632
predicate
cmp_inf_qbound
(qb:qbound) (r:real) =
2633
match qb with
2634
| BInf -> true
2635
| BLarge q -> Q.real q <=. r
2636
| BStrict q -> Q.real q <. r
2637
end
2638
2639
predicate
cmp_sup_qbound
(r:real) (qb:qbound) =
2640
match qb with
2641
| BInf -> true
2642
| BLarge q -> Q.real q >=. r
2643
| BStrict q -> Q.real q >. r
2644
end
2645
2646
2647
type
interval
=
2648
|
Singleton
Q.t
2649
|
Inter
qbound qbound
2650
Valid (26ms) (cvc5)
2651
type
input_interval
= {
i
: interval }
2652
invariant { match i with Inter (BLarge q1|BStrict q1) (BLarge q2|BStrict q2) -> q1 <=. q2 | _ -> true end }
2653
by { i = Inter BInf BInf }
2654
2655
type
res_interval
= list interval
2656
2657
predicate
mem_interval
(r:real) (i:interval) =
2658
match i with
2659
| Singleton q -> Q.real q = r
2660
| Inter qb1 qb2 ->
2661
cmp_inf_qbound qb1 r /\ cmp_sup_qbound r qb2
2662
end
2663
2664
predicate
mem_res_interval
(r:real) (i:res_interval) =
2665
match i with
2666
| Nil -> false
2667
| Cons i1 l -> mem_interval r i1 \/ mem_res_interval r l
2668
end
2669
2670
let function
qbound_of_bound
q b =
2671
match b with
2672
| Strict -> BStrict q
2673
| Large -> BLarge q
2674
end
2675
2676
Valid (31ms) (cvc5)
2677
let function
bound_of_qbound
b =
2678
requires { b <> BInf }
2679
match b with
2680
| BStrict q -> (Strict,q)
2681
| BLarge q -> (Large,q)
2682
| BInf -> absurd
2683
end
2684
2685
Valid (1.3s) (colibri2)
2686
let
convert_interval
(i:interval) : t'
2687
ensures { forall r. mem_interval r i <-> mem r result }
2688
ensures { ordered result }
2689
=
2690
match i with
2691
| Singleton q -> Off (Sin q Inf)
2692
| Inter BInf BInf -> On Inf
2693
| Inter BInf bq ->
2694
let (b,q) = bound_of_qbound bq in On (Chg q (inv_bound b) Inf)
2695
| Inter bq BInf ->
2696
let (b,q) = bound_of_qbound bq in Off (Chg q b Inf)
2697
| Inter bq1 bq2 ->
2698
let (b1,q1) = bound_of_qbound bq1 in
2699
let (b2,q2) = bound_of_qbound bq2 in
2700
match Q.compare q1 q2, b1, b2 with
2701
| Ord.Eq, Large, Large -> Off (Sin q1 Inf)
2702
| Ord.Lt, _, _ -> Off (Chg q1 b1 (Chg q2 (inv_bound b2) Inf))
2703
| _ -> Off Inf
2704
end
2705
end
2706
Valid (66ms) (cvc5)
2707
let rec
convert_res_interval
(i:res_interval) : t'
2708
ensures { forall r. mem_res_interval r i <-> mem r result }
2709
ensures { ordered result }
2710
variant { i }
2711
=
2712
match i with
2713
| Nil -> Off Inf
2714
| Cons i1 Nil -> (convert_interval i1)
2715
| Cons i2 l -> (union_a (convert_interval i2) (convert_res_interval l))
2716
end
2717
Valid (67ms) (colibri2)
2718
type
fmap
= {
2719
f
: input_interval -> input_interval -> res_interval;
2720
ghost
fr
: real -> real-> real;
2721
}
2722
invariant { forall i1 i2 r1 r2. mem_interval r1 i1.i -> mem_interval r2 i2.i -> mem_res_interval (fr r1 r2) (f i1 i2) }
2723
by { f = (fun x _ -> Cons x.i Nil); fr = (fun i _ -> i) }
2724
2725
predicate
qlt_bound'
(q:qbound) (l:t'') =
2726
match q with
2727
| BInf -> true
2728
| BLarge q | BStrict q -> lt_bound' q l
2729
end
2730
Valid (363ms) (colibri2 5) (cvc4 5) (cvc5 57) (split_vc 3) (depth 2)
2731
let
map
(fm:fmap) (l1:t) (l2:t) : t
2732
ensures { sound2 memt fm.fr l1 l2 result }
2733
=
2734
let rec map_cst_left_on (i1:input_interval) (q2:qbound) (l2:t'') : t'
2735
requires { ordered' l2 }
2736
requires { qlt_bound' q2 l2 }
2737
ensures { forall r1 r2. mem_interval r1 i1.i -> cmp_inf_qbound q2 r2 -> mem_if True r2 l2 -> mem (fm.fr r1 r2) result }
2738
ensures { ordered result }
2739
variant { l2 }
2740
=
2741
match l2 with
2742
| Inf ->
2743
let u = fm.f i1 {i=Inter q2 BInf} in
2744
(convert_res_interval u)
2745
| Sin q l2 ->
2746
let q3 = (BStrict q) in
2747
let u = fm.f i1 {i=Inter q2 q3} in
2748
union_a (convert_res_interval u) (map_cst_left_on i1 q3 l2)
2749
| Chg q b l2 ->
2750
let u = fm.f i1 {i=Inter q2 (qbound_of_bound q (inv_bound b))} in
2751
union_a (convert_res_interval u) (map_cst_left_off i1 l2)
2752
end
2753
with map_cst_left_off (i1:input_interval) (l2:t'') : t'
2754
requires { ordered' l2 }
2755
ensures { forall r1 r2. mem_interval r1 i1.i -> mem_if False r2 l2 -> mem (fm.fr r1 r2) result }
2756
ensures { ordered result }
2757
variant { l2 }
2758
=
2759
match l2 with
2760
| Inf -> Off Inf
2761
| Sin q l2 ->
2762
let u = fm.f i1 {i=Singleton q} in
2763
union_a (convert_res_interval u) (map_cst_left_off i1 l2)
2764
| Chg q b l2 ->
2765
map_cst_left_on i1 (qbound_of_bound q b) l2
2766
end
2767
in
2768
let map_cst_left (i1:input_interval) (l2:t) : t'
2769
ensures { forall r1 r2. mem_interval r1 i1.i -> mem r2 l2.a -> mem (fm.fr r1 r2) result }
2770
ensures { ordered result }
2771
=
2772
match l2.a with
2773
| On l2 -> map_cst_left_on i1 BInf l2
2774
| Off l2 -> map_cst_left_off i1 l2
2775
end
2776
in
2777
let rec map_cst_on (q1:qbound) (l1:t'') (l2:t) : t'
2778
requires { ordered' l1 }
2779
requires { qlt_bound' q1 l1 }
2780
ensures { forall r1 r2. cmp_inf_qbound q1 r1 -> mem_if True r1 l1 -> mem r2 l2.a -> mem (fm.fr r1 r2) result }
2781
ensures { ordered result }
2782
variant { l1 }
2783
=
2784
match l1 with
2785
| Inf -> map_cst_left {i=Inter q1 BInf} l2
2786
| Sin q l1' ->
2787
let q2 = (BStrict q) in
2788
let u1 = map_cst_left {i=Inter q1 q2} l2 in
2789
let u2 = map_cst_on q2 l1' l2 in
2790
union_a u1 u2
2791
| Chg q b l1' ->
2792
let u1 = map_cst_left {i=Inter q1 (qbound_of_bound q (inv_bound b))} l2 in
2793
let u2 = map_cst_off l1' l2 in
2794
union_a u1 u2
2795
end
2796
with map_cst_off (l1:t'') (l2:t) : t'
2797
requires { ordered' l1 }
2798
ensures { forall r1 r2. mem_if False r1 l1 -> mem r2 l2.a -> mem (fm.fr r1 r2) result }
2799
ensures { ordered result }
2800
variant { l1 }
2801
=
2802
match l1 with
2803
| Inf -> Off Inf
2804
| Sin q l1' ->
2805
let u1 = map_cst_left {i=Singleton q} l2 in
2806
let u2 = map_cst_off l1' l2 in
2807
union_a u1 u2
2808
| Chg q b l1' -> map_cst_on (qbound_of_bound q b) l1' l2
2809
end
2810
in
2811
let ghost r1 = not_bottom l1 in
2812
let ghost r2 = not_bottom l2 in
2813
match l1.a with
2814
| On l1 ->
2815
let m = map_cst_on BInf l1 l2 in
2816
assert { mem (fm.fr r1 r2) m };
2817
{ a = m }
2818
| Off l1 ->
2819
let m = map_cst_off l1 l2 in
2820
assert { mem (fm.fr r1 r2) m };
2821
{ a = m }
2822
end
2823
2824
scope UnaryFold Valid (40ms) (cvc5)
2825
type
fmap
'a = {
2826
f
: interval -> 'a;
2827
union
: 'a -> 'a -> 'a;
2828
ghost
inv
: real -> 'a -> bool;
2829
}
2830
invariant { forall i1 r1. mem_interval r1 i1 -> inv r1 (f i1) }
2831
invariant { forall a1 a2. forall r. (inv r a1 \/ inv r a2) -> inv r (union a1 a2) }
2832
by (
2833
let v = any 'a ensures { result = result } in
2834
{ f = (fun _ -> v); inv = (fun _ _ -> true); union = (fun x _ -> x) })
2835
Valid (1.4s) (colibri2 2) (cvc5 15) (split_vc) (depth 1)
2836
let
map
(fm:fmap 'a) (l1:t) : 'a
2837
ensures { forall r1. mem r1 l1.a -> fm.inv r1 result }
2838
=
2839
let rec map_cst_left_on (q2:qbound) (l2:t'') : 'a
2840
requires { ordered' l2 }
2841
ensures { forall r2. cmp_inf_qbound q2 r2 -> mem_if True r2 l2 -> fm.inv r2 result }
2842
variant { l2 }
2843
=
2844
match l2 with
2845
| Inf ->
2846
fm.f (Inter q2 BInf)
2847
| Sin q l2 ->
2848
let q3 = (BStrict q) in
2849
let u = fm.f (Inter q2 q3) in
2850
fm.union u (map_cst_left_on q3 l2)
2851
| Chg q b l2 ->
2852
let u = fm.f (Inter q2 (qbound_of_bound q (inv_bound b))) in
2853
match l2 with
2854
| Inf -> u
2855
| _ -> fm.union u (map_cst_left_off l2)
2856
end
2857
end
2858
with map_cst_left_off (l2:t'') : 'a
2859
requires { ordered' l2 }
2860
requires { l2 <> Inf }
2861
ensures { forall r2. mem_if False r2 l2 -> fm.inv r2 result }
2862
variant { l2 }
2863
=
2864
match l2 with
2865
| Inf -> absurd
2866
| Sin q Inf -> fm.f (Singleton q)
2867
| Sin q l2 ->
2868
let u = fm.f (Singleton q) in
2869
fm.union u (map_cst_left_off l2)
2870
| Chg q b l2 ->
2871
map_cst_left_on (qbound_of_bound q b) l2
2872
end
2873
in
2874
match l1.a with
2875
| On l1 ->
2876
map_cst_left_on BInf l1
2877
| Off l1 ->
2878
map_cst_left_off l1
2879
end
2880
2881
end
2882
2883
scope Unary Valid (379ms) (cvc5)
2884
type
fmap
= {
2885
f
: interval -> res_interval;
2886
ghost
fr
: real -> real;
2887
}
2888
invariant { forall i1 r1. mem_interval r1 i1 -> mem_res_interval (fr r1) (f i1) }
2889
invariant { forall i1. f i1 <> Nil }
2890
by { f = (fun i -> Cons i Nil); fr = (fun i -> i) }
2891
Valid (25ms) (colibri2)
2892
type
t'_ordered
= {
u
: t' }
2893
invariant { ordered u }
2894
by { u = On Inf }
2895
Valid (155ms) (cvc4)
2896
let
map
(fm:fmap) (l1:t) : t
2897
ensures { sound1 memt fm.fr l1 result }
2898
=
2899
let predicate inv (r:real) (u':t'_ordered) = pure { mem (fm.fr r) u'.u } in
2900
let f i =
2901
ensures { forall r1. mem_interval r1 i -> inv r1 result }
2902
{u=convert_res_interval (fm.f i)}
2903
in
2904
let union x y =
2905
ensures { forall r1. (inv r1 x \/ inv r1 y) -> inv r1 result }
2906
{u=union_a x.u y.u}
2907
in
2908
let fmap' = { UnaryFold.f = f;
2909
UnaryFold.union = union;
2910
UnaryFold.inv = inv;
2911
}
2912
in
2913
let ghost r1 = not_bottom l1 in
2914
let m = UnaryFold.map fmap' l1 in
2915
assert { mem (fm.fr r1) m.u };
2916
{ a = m.u }
2917
end
2918
2919
2920
end
2921
Valid (408ms) (colibri2)
2922
let ghost
not_bottom_lt_bound
(q':real) (if_:bool) (l:t'') : real
2923
requires { ordered' l }
2924
requires { lt_bound' q' l }
2925
requires { l = Inf -> if_ }
2926
ensures { mem_if if_ result l }
2927
ensures { q' <. result }
2928
=
2929
if if_ then
2930
match l with
2931
| (Sin q _) -> (Q.real q*.0.5+.q'*.0.5)
2932
| (Chg q _ _) -> (Q.real q*.0.5+.q'*.0.5)
2933
| Inf -> q' +. 1.
2934
end
2935
else
2936
match l with
2937
| (Sin q _) -> Q.real q
2938
| (Chg q _ (Sin q' _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)
2939
| (Chg q _ (Chg q' _ _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)
2940
| (Chg q _ Inf) -> (Q.real q+.1.)
2941
| Inf -> absurd
2942
end

Square

2946
use real.Square
2947
Valid (1.2s) (colibri2 22) (cvc4 4) (cvc5 21) (split_vc) (depth 1)
2948
let
square_backward
l
2949
ensures { preimage1_opt memt (fun (x:real) -> sqr x) l result }
2950
=
2951
let _,zb,pos = Increasing.split_at l in
2952
match zb, pos with
2953
| False, Increasing.Far Inf -> None
2954
| True, Increasing.Far Inf -> Some (singleton (Q.of_int 0))
2955
| _ ->
2956
let ghost function sqrt' (x:real) = if x <. 0. then x else sqrt x in
2957
let function sqrtq (v:Q.t) : Q.t ensures { result = sqrt' v } =
2958
if Q.lt v (Q.of_int 0) then v else Q.sqrt v in
2959
let lemma sqrt_op (v: Q.t)
2960
requires { in_infr (R 0.) v I }
2961
ensures { sqrt' v = sqrtq v } =
2962
()
2963
in
2964
let if_pos,pos = Increasing.open_presence pos in
2965
let _ = not_bottom_lt_bound 0. if_pos pos in
2966
let op = Increasing.{ Unary.minr = R 0.;
2967
Unary.maxr = I;
2968
Unary.ur = sqrt';
2969
Unary.uq = sqrtq } in
2970
Increasing.lt_bound_is_foot_if 0. 0. pos;
2971
let r = Increasing.Unary.op_si1_cst' op if_pos pos in
2972
assert { forall q. 0. <. q -> (mem (sqr q) l.a) -> mem_if if_pos q r };
2973
let r = { a = Off (Increasing.union_bzero zb if_pos r) } in
2974
assert { forall q. 0. <=. q -> (mem (sqr q) l.a) -> mem q r.a };
2975
let rn = Increasing.Unary.neg r in
2976
assert { forall q. mem q r.a -> mem (-. q) rn.a };
2977
assert { forall q. q <. 0. -> (mem (sqr q) l.a) -> mem (-. q) r.a
2978
by sqr (-. q) = sqr q };
2979
let res = union rn r in
2980
assert { forall q. mem q res.a <-> (mem q rn.a \/ mem q r.a) };
2981
assert { forall q. (mem (sqr q) l.a) -> mem q res.a
2982
by q <. 0. -> mem q rn.a by -. (-. q) = q };
2983
Some res
2984
end
2985
2986
use real.FromInt
2987
Valid (4.5s) (colibri2 5) (split_vc 3) (depth 3)
2988
let
ceilb
q b : Q.t
2989
ensures { Real.is_integer (Q.real result) }
2990
ensures { cmp q b result }
2991
ensures { forall r. cmp q b r -> r <. result -> not (Real.is_integer r) }
2992
=
2993
match b with
2994
| Large -> Q.of_bigint (Q.ceil_z q)
2995
| Strict -> if Q.is_integer q then (Q.add q (Q.of_int 1)) else Q.of_bigint (Q.ceil_z q)
2996
end
2997
Valid (123ms) (colibri2)
2998
let
floorb
q b : Q.t
2999
ensures { Real.is_integer (Q.real result) }
3000
ensures { cmp result b q }
3001
ensures { forall r. cmp r b q -> result <. r -> not (Real.is_integer r) }
3002
=
3003
match b with
3004
| Large -> Q.of_bigint (Q.floor_z q)
3005
| Strict -> if Q.is_integer q then (Q.sub q (Q.of_int 1)) else Q.of_bigint (Q.floor_z q)
3006
end
3007
Valid (161ms) (cvc4)
3008
type
reducer
= {
3009
ghost
red_min
: infr;
3010
ghost
red_is_in
: real -> bool;
3011
red_is_integer
: Q.t -> bool;
3012
red_floorb
: Q.t -> Bound.t -> Q.t;
3013
red_ceilb
: Q.t -> Bound.t -> Q.t;
3014
}
3015
invariant { forall q. red_is_integer q <-> red_is_in q }
3016
invariant { forall q b. (lt_infr red_min (R (Q.real q))) -> red_is_in (red_floorb q b) }
3017
invariant { forall q b. (le_infr red_min (R (Q.real q))) -> red_is_in (red_ceilb q b) }
3018
invariant { forall q b. (lt_infr red_min (R (Q.real q))) -> cmp (red_floorb q b) b q }
3019
invariant { forall q b. (le_infr red_min (R (Q.real q))) -> cmp q b (red_ceilb q b) }
3020
invariant { forall q:Q.t.forall b r. (lt_infr red_min (R (Q.real q))) -> cmp r b q -> (red_floorb q b) <. r -> not (red_is_in r) }
3021
invariant { forall q:Q.t.forall b r. (le_infr red_min (R (Q.real q))) -> cmp q b r -> r <. (red_ceilb q b) -> not (red_is_in r) }
3022
by { red_is_in = pure { Real.is_integer }; red_is_integer = Q.is_integer; red_floorb = floorb; red_ceilb = ceilb; red_min = I }
3023
Valid (7.8s) (colibri2 63) (cvc4 2) (cvc5 13) (split_vc 5) (depth 2)
3024
let
reduce_generic
(op:reducer) (num:t) : option t
3025
requires { le_infr_bound op.red_min num.a }
3026
ensures { restrict memt op.red_is_in num result } =
3027
let add_on start q l
3028
requires { ordered' l }
3029
requires { lt_bound' q l }
3030
requires { le_bound' start l }
3031
ensures { ordered' result }
3032
ensures { forall r. start <=. r <=. q -> mem_if False r result }
3033
ensures { forall r. mem_if False r l -> mem_if False r result }
3034
ensures { le_bound' start result }
3035
=
3036
match Q.compare q start with
3037
| Ord.Lt -> l
3038
| Ord.Eq -> Sin start l
3039
| Ord.Gt -> Chg start Large (Chg q Strict l)
3040
end
3041
in
3042
let rec aux_on (op:reducer) (ghost b:Bound.t) (ghost before: real) (start:Q.t) (num:t''): t''
3043
requires { lt_infr_bound' op.red_min num }
3044
requires { ordered' num }
3045
requires { lt_bound' before num }
3046
requires { cmp before b start }
3047
requires { forall r. cmp before b r -> r <. start -> not (op.red_is_in r) }
3048
requires { op.red_is_in start }
3049
ensures { forall n. start <=. n -> mem_if True n num -> op.red_is_in n
3050
-> mem_if False n result }
3051
ensures { le_bound' start result }
3052
ensures { ordered' result }
3053
variant {num}
3054
= match num with
3055
| Sin q l ->
3056
let qf = op.red_floorb q Strict in
3057
let qc = op.red_ceilb q Strict in
3058
assert { start <=. qc };
3059
assert { forall x. qf <. x -> x <. q -> not (op.red_is_in x) };
3060
assert { forall x. q <. x -> x <. qc -> not (op.red_is_in x) };
3061
assert { forall x. qf <. x <=. qc -> op.red_is_in x -> (x = q \/ x = qc)};
3062
if pure { qf <. start } then begin
3063
assert { op.red_is_in start };
3064
assert { qf <. start <=. qc };
3065
assert { Q.real start = Q.real q \/ Q.real start = Q.real qc }
3066
end;
3067
let l' = aux_on op Strict (Q.real q) qc l in
3068
assert { forall n. start <=. n -> mem_if True n num -> op.red_is_in n -> (mem_if True n l \/ start <=. n <=. qf) };
3069
add_on start qf l'
3070
| Chg q b l ->
3071
let qf = op.red_floorb q (Bound.inv_bound b) in
3072
assert { forall x. qf <. x -> x <. q -> not (op.red_is_in x) };
3073
let l' = aux_off op l in
3074
add_on start qf l'
3075
| Inf -> Chg start Large Inf
3076
end
3077
with aux_off (op:reducer) (num:t'') : t''
3078
requires { le_infr_bound' op.red_min num }
3079
requires { ordered' num }
3080
ensures { forall n. mem_if False n num -> op.red_is_in n -> mem_if False n result }
3081
ensures { ordered' result }
3082
ensures { forall q. lt_bound' q num -> lt_bound' q result }
3083
ensures { forall before q. lt_bound' before num -> (forall r. before <. r <. q -> not (op.red_is_in r))
3084
-> le_bound' q result }
3085
variant {num}
3086
=
3087
match num with
3088
| Sin q l -> if op.red_is_integer q then Sin q (aux_off op l) else aux_off op l
3089
| Chg q b l ->
3090
let q' = op.red_ceilb q b in
3091
aux_on op b (Q.real q) q' l
3092
| Inf -> Inf
3093
end
3094
in
3095
let rec aux_on_inf (op:reducer) (num:t'') : t''
3096
requires { lt_infr_bound' op.red_min num }
3097
requires { ordered' num }
3098
ensures { forall n. mem_if True n num -> op.red_is_in n -> mem_if True n result }
3099
ensures { ordered' result }
3100
= match num with
3101
| Sin q num' ->
3102
let qf = op.red_floorb q Strict in
3103
let qc = op.red_ceilb q Strict in
3104
assert { forall x. qf <. x -> x <. q -> not (op.red_is_in x) };
3105
assert { forall x. q <. x -> x <. qc -> not (op.red_is_in x) };
3106
Chg qf Strict (aux_on op Strict (Q.real q) qc num')
3107
| Chg q b l ->
3108
let qf = op.red_floorb q (Bound.inv_bound b) in
3109
Chg qf Strict (aux_off op l)
3110
| Inf -> Inf
3111
end
3112
in
3113
match num.a with
3114
| On u -> Some { a = On (aux_on_inf op u) }
3115
| Off u -> (match aux_off op u with Inf -> None | u -> Some {a=Off u} end)
3116
end
3117
Valid (1.6s) (colibri2)
3118
let
reduce_integers
(l:t) : option t
3119
ensures { restrict memt (fun (x:real) -> Real.is_integer x) l result } =
3120
reduce_generic
3121
{ red_is_in = pure { Real.is_integer }; red_is_integer = Q.is_integer; red_floorb = floorb; red_ceilb = ceilb; red_min = I; }
3122
l
3123
3124
3125
scope ED
3126
use real.Abs
3127
Valid (342ms) (cvc5)
3128
lemma
div_mod_e
: forall a b. b <> 0. -> a = b *. (from_int (Real.div_e a b)) +. (Real.mod_e a b) Valid (355ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
3129
let lemma
mod_e
(a b:real)
3130
requires { b <> 0. }
3131
ensures { 0. <=. (Real.mod_e a b) <. abs b }
3132
= if b >. 0. then begin
3133
assert { let d = from_int (Real.div_e a b) in d <=. a /. b <. d +. 1. };
3134
assert { let d = from_int (Real.div_e a b) in b *. d <=. a <. b *. d +. b }
3135
end else begin
3136
assert { let d = from_int (Real.div_e a b) in d -. 1. <. a /. b <=. d };
3137
assert { let d = from_int (Real.div_e a b) in b *. d <=. a <. b *. d -. b }
3138
end
3139
3140
function
div_e_real
(x :real) (y:real) : real = from_int (Real.div_e x y)
3141
Valid (1.0s) (colibri2) (cvc4 2) (cvc5 10) (split_vc) (depth 1)
3142
let ghost
div_real_monotonies
() : unit
3143
ensures { forall xm xM ym yM. 0. <. xm <=. xM -> 0. <. ym <=. yM ->
3144
0. <=. div_e_real xm yM <=. div_e_real xM ym }
3145
ensures { forall xm xM ym yM. xm <=. 0. <=. xM -> 0. <. ym <=. yM ->
3146
div_e_real xm ym <=. 0. <=. div_e_real xM ym }
3147
ensures { forall xm xM ym yM. xm <=. xM <. 0. -> 0. <. ym <=. yM ->
3148
div_e_real xm ym <=. div_e_real xM yM <. 0. }
3149
ensures { forall xm xM ym yM. 0. <. xm <=. xM -> ym <=. yM <. 0. ->
3150
div_e_real xM yM <=. div_e_real xm ym <=. 0. }
3151
ensures { forall xm xM ym yM. xm <=. 0. <=. xM -> ym <=. yM <. 0. ->
3152
div_e_real xM yM <=. 0. <=. div_e_real xm yM }
3153
ensures { forall xm xM ym yM. xm <=. xM <. 0. -> ym <=. yM <. 0. ->
3154
0. <. div_e_real xM ym <=. div_e_real xm yM } =

Proof

3156
assert { forall xm xM ym yM. 0. <. xm <=. xM -> 0. <. ym <=. yM -> 0 <= Real.div_e xm yM <= Real.div_e xM ym };
3157
assert { forall xm xM ym yM. xm <=. 0. <=. xM -> 0. <. ym <=. yM -> Real.div_e xm ym <= 0 <= Real.div_e xM ym };
3158
assert { forall xm xM ym yM. xm <=. xM <. 0. -> 0. <. ym <=. yM -> Real.div_e xm ym <= Real.div_e xM yM < 0 };
3159
assert { forall x x' y. y <. 0. -> x <=. x' -> Real.div_e x y >= Real.div_e x' y };
3160
assert { forall xm xM ym yM. 0. <. xm <=. xM -> ym <=. yM <. 0. -> Real.div_e xM yM <= Real.div_e xm ym <= 0 };
3161
assert { forall xm xM ym yM. xm <=. 0. <=. xM -> ym <=. yM <. 0. -> Real.div_e xM yM <= 0 <= Real.div_e xm yM };
3162
assert { forall xm xM ym yM. xm <=. xM <. 0. -> ym <=. yM <. 0. -> 0 < Real.div_e xM ym <= Real.div_e xm yM }

QED

3165
use real.Truncate
3166
use real.FromInt
3167
Valid (107ms) (cvc5)
3168
let ghost
div_e_real_is_ceil_floor
(): unit
3169
ensures { forall n d. d <> 0. ->
3170
let r = n /. d in
3171
let r = if d <. 0. then from_int (ceil r) else from_int (floor r) in
3172
div_e_real n d = r } =
3173
assert {
3174
forall n d. d <> 0. ->
3175
let r = n /. d in
3176
let r = if d <. 0. then (ceil r) else (floor r) in
3177
Real.div_e n d = r }
3178
3179
use real.Abs
3180
Valid (295ms) (cvc4)
3181
let ghost
uniq_div_e_real
(num:real) (den:real) (div:int) (mod:real) : unit
3182
requires { num = (from_int div)*.den +. mod }
3183
requires { 0. <=. mod <. abs den }
3184
ensures { Real.div_e num den = div }
3185
ensures { Real.mod_e num den = mod }
3186
= ()
3187
3188
Valid (160ms) (cvc5)
3189
let
compare_interval
(r:Q.t) (x:Map.input_interval) : Ord.t
3190
ensures { match result with
3191
| Ord.Eq -> Map.mem_interval r x.Map.i
3192
| Ord.Lt -> forall s. Map.mem_interval s x.Map.i -> r <. s
3193
| Ord.Gt -> forall s. Map.mem_interval s x.Map.i -> s <. r
3194
end }
3195
=
3196
Map.(match x.i with
3197
| Singleton q -> Q.compare r q
3198
| Inter qb1 qb2 ->
3199
if (match qb1 with BInf -> True | BLarge q -> Q.le q r
3200
| BStrict q -> (Q.lt q r) end) then
3201
if (match qb2 with BInf -> True | BLarge q -> Q.le r q
3202
| BStrict q -> (Q.lt r q) end) then Ord.Eq else Ord.Gt
3203
else Ord.Lt
3204
end)
3205
3206
(* Same as compare_interval but BStrict is considered as BLarge *)
3207
let function
near_r
(r:Q.t) (x:Map.input_interval) : Ord.t
3208
=
3209
Map.(match x.i with
3210
| Singleton q -> Q.compare r q
3211
| Inter qb1 qb2 ->
3212
if (match qb1 with BInf -> True | (BLarge q|BStrict q) -> (Q.le q r) end) then
3213
if (match qb2 with BInf -> True | (BLarge q | BStrict q) -> Q.le r q
3214
end) then Ord.Eq else Ord.Gt
3215
else Ord.Lt
3216
end)
3217
3218
let function
get_min
(x:Map.input_interval) : Map.qbound =
3219
match x.Map.i with
3220
| Map.Singleton q -> Map.BLarge q
3221
| Map.Inter q _ -> q
3222
end
3223
3224
let function
get_max
(x:Map.input_interval) : Map.qbound =
3225
match x.Map.i with
3226
| Map.Singleton q -> Map.BLarge q
3227
| Map.Inter _ q -> q
3228
end
3229
3230
Valid (2.2s) (colibri2 5) (cvc5 20) (split_vc 3) (depth 3)
3231
let
fmap_div
() : Map.fmap
3232
ensures { result.Map.fr = div_e_real }
3233
=
3234
Map.(
3235
let zero = (Q.of_int 0) in
3236
let fi (x:input_interval) (y:input_interval) : res_interval
3237
ensures { forall r1 r2. mem_interval r1 x.i -> mem_interval r2 y.i -> mem_res_interval (div_e_real r1 r2) result}
3238
=
3239
Map.(
3240
div_real_monotonies ();
3241
let x_for_rmin,y_for_rmin,x_for_rmax,y_for_rmax =
3242
match near_r zero y with
3243
| Ord.Eq -> BInf,BInf,BInf,BInf
3244
| Ord.Lt -> (* y positive *)
3245
let ymin = get_min y in
3246
let ymax = get_max y in
3247
let y_for_rmin, y_for_rmax =
3248
match near_r zero x with
3249
| Ord.Lt -> ymax,ymin
3250
| Ord.Eq -> ymin,ymin
3251
| Ord.Gt -> ymin,ymax
3252
end
3253
in
3254
get_min x,y_for_rmin,get_max x,y_for_rmax
3255
| Ord.Gt -> (* y negative *)
3256
let ymin = get_min y in
3257
let ymax = get_max y in
3258
let y_for_rmin, y_for_rmax =
3259
match near_r zero x with
3260
| Ord.Lt -> ymax,ymin
3261
| Ord.Eq -> ymax,ymax
3262
| Ord.Gt -> ymin,ymax
3263
end
3264
in
3265
get_max x,y_for_rmin,get_min x,y_for_rmax
3266
end in
3267
let rmin = match x_for_rmin, y_for_rmin with
3268
| BInf, _ -> BInf
3269
| _, BInf -> BLarge zero
3270
| (BLarge x|BStrict x),(BLarge y|BStrict y) ->
3271
BLarge (Q.div_e x y)
3272
end
3273
in
3274
let rmax = match x_for_rmax, y_for_rmax with
3275
| BInf, _ -> BInf
3276
| _, BInf -> BLarge zero
3277
| (BLarge x|BStrict x),(BLarge y|BStrict y) ->
3278
BLarge (Q.div_e x y)
3279
end
3280
in
3281
Cons (Inter rmin rmax) Nil
3282
)
3283
in
3284
{ fr = div_e_real; f = fi })
3285
Valid (68ms) (cvc5)
3286
let
div_e_forward_bak
(l1 l2:t) : t
3287
ensures { forall r1 r2. mem r1 l1.a -> mem r2 l2.a -> mem (div_e_real r1 r2) result.a } =
3288
Map.map (fmap_div ()) l1 l2
3289
3290
Valid (1.7s) (colibri2 75) (cvc4 9) (cvc5 23) (split_vc 10) (depth 3)
3291
let
div_e_forward
(l1 l2:t) : t
3292
ensures { sound2 memt div_e_real l1 l2 result } =
3293
div_e_real_is_ceil_floor ();
3294
let neg2,b2,pos2 = Increasing.split_at l2 in
3295
if b2 then { a = On Inf }
3296
else
3297
let _ = not_bottom l2 in
3298
match neg2,pos2 with
3299
| Increasing.Far Inf, Increasing.Far Inf -> absurd
3300
| Increasing.Far Inf, _ ->
3301
let pos2 = { a = Off (Increasing.Binary.inv_pos pos2) } in
3302
assert { forall x. mem x l2.a -> mem (1. /. x) pos2.a };
3303
let p = Increasing.Binary.mul l1 pos2 in
3304
let r = NonIncreasing.floor p in
3305
let lemma m (r1 r2:real)
3306
requires { mem r1 l1.a }
3307
requires { mem r2 l2.a }
3308
ensures { mem (div_e_real r1 r2) r.a }
3309
= assert { 0. <. r2 };
3310
assert { mem (r1 *. (1. /. r2)) p.a };
3311
assert { r1 /. r2 = r1 *. (1. /. r2) } in
3312
r
3313
| _, Increasing.Far Inf ->
3314
let neg2 = Increasing.Binary.neg' (Increasing.Binary.inv_pos neg2) in
3315
assert { forall x. mem x l2.a -> x <. 0. };
3316
assert { forall x. x <. 0. -> -. (1. /. (-. x)) = 1. /. x };
3317
assert { forall x. mem x l2.a -> mem (1. /. x) neg2.a };
3318
let p = Increasing.Binary.mul l1 neg2 in
3319
let r = NonIncreasing.ceil p in
3320
let lemma m (r1 r2:real)
3321
requires { mem r1 l1.a }
3322
requires { mem r2 l2.a }
3323
ensures { mem (div_e_real r1 r2) r.a }
3324
= assert { r2 <. 0. };
3325
assert { mem (r1 *. (1. /. r2)) p.a };
3326
assert { r1 /. r2 = r1 *. (1. /. r2) } in
3327
r
3328
| _ ->
3329
let _ = Increasing.not_bottom_presence 0. pos2 in
3330
let _ = Increasing.not_bottom_presence 0. neg2 in
3331
let pos2 = { a = Off (Increasing.Binary.inv_pos pos2) } in
3332
let neg2 = Increasing.Binary.neg' (Increasing.Binary.inv_pos neg2) in
3333
assert { forall q q'. q' <> 0. -> q /. q' = q *. (1./.q') };
3334
assert { forall x. mem x l2.a -> (if x <. 0. then mem (1. /. x) neg2.a else mem (1. /. x) pos2.a) };
3335
let neg2 = (Increasing.Binary.mul l1 neg2) in
3336
let neg2 = (NonIncreasing.ceil neg2) in
3337
let pos2 = (NonIncreasing.floor (Increasing.Binary.mul l1 pos2)) in
3338
assert { forall y x. mem y l1.a -> mem x l2.a -> (if x <. 0. then mem (from_int (ceil (y /. x))) neg2.a else mem (from_int (floor (y /. x))) pos2.a) };
3339
union neg2 pos2
3340
end
3341
3342
3343
3344
Valid (1.9s) (colibri2 16) (cvc4 6) (cvc5 48) (split_vc 7) (depth 4)
3345
let
mod_e_forward
(l1 l2:t) : t
3346
ensures { sound2 memt (fun (x y:real) -> Real.mod_e x y) l1 l2 result } =
3347
let zero = (Q.of_int 0) in
3348
if mem zero l2 then { a = On Inf }
3349
else
3350
let _ = not_bottom l2 in
3351
match l2.a with
3352
| Off (Sin m Inf) ->
3353
let m = Q.abs m in
3354
let function fr (x:real) = pure { Real.mod_e x m } in
3355
let f (i:Map.interval) : list Map.interval
3356
ensures { forall r. Map.mem_interval r i -> Map.mem_res_interval (fr r) result }
3357
ensures { result <> Nil }
3358
=
3359
match i with
3360
| Map.Singleton r -> Cons (Map.Singleton (Q.mod_e r m)) Nil
3361
| Map.Inter Map.BInf _ | Map.Inter _ Map.BInf ->
3362
Cons (Map.Inter (Map.BLarge (Q.of_int 0)) (Map.BStrict m)) Nil
3363
| Map.Inter ((Map.BLarge rmin | Map.BStrict rmin) as bmin)
3364
((Map.BLarge rmax | Map.BStrict rmax) as bmax) ->
3365
let rmin_mod = match bmin with
3366
| Map.BInf -> absurd
3367
| Map.BLarge b -> Map.BLarge (Q.mod_e b m)
3368
| Map.BStrict b -> Map.BStrict (Q.mod_e b m)
3369
end
3370
in
3371
let rmax_mod = match bmax with
3372
| Map.BInf -> absurd
3373
| Map.BLarge b -> Map.BLarge (Q.mod_e b m)
3374
| Map.BStrict b -> Map.BStrict (Q.mod_e b m)
3375
end
3376
in
3377
let rmin_div = Q.div_e rmin m in
3378
let rmax_div = Q.div_e rmax m in
3379
div_real_monotonies ();
3380
if Q.equal rmin_div rmax_div then
3381
Cons (Map.Inter rmin_mod rmax_mod) Nil
3382
else if Q.equal (Q.add rmin_div (Q.of_int 1)) rmax_div
3383
then
3384
Cons (Map.Inter rmin_mod (Map.BStrict m))
3385
(Cons (Map.Inter (Map.BLarge (Q.of_int 0)) rmax_mod) Nil)
3386
else
3387
Cons (Map.Inter (Map.BLarge (Q.of_int 0)) (Map.BStrict m)) Nil
3388
end
3389
in
3390
let f = { Map.Unary.f = f; Map.Unary.fr = fr } in
3391
Map.Unary.map f l1
3392
| _ ->
3393
match mem_min l2,mem_max l2 with
3394
| None, _ | _, None -> (ge zero)
3395
| Some (m,b), Some (m',b') ->
3396
let m = Q.abs m in
3397
let m' = Q.abs m' in
3398
let (m,b) = max_bound_sup m b m' b' in
3399
assert { forall r2. mem r2 l2.a -> cmp (abs r2) b m };
3400
{ a = Off (Chg (Q.of_int 0) Large (Chg m Large Inf))}
3401
end
3402
end
3403
Valid (1.5s) (colibri2 4) (cvc4 4) (cvc5 25) (split_vc 2) (depth 2)
3404
let
mod_e_backward_num
(num:t) (denl:t) (modl:t) : option t
3405
ensures { back2 memt (fun (x y:real) -> Real.mod_e x y) num denl modl result } =
3406
match denl.a, modl.a with
3407
| Off (Sin den Inf), Off (Sin mod Inf) ->

Only singleton in den and mod for now

3408
if Q.equal den (Q.of_int 0) then Some num
3409
else if notb (andb ((Q.le (Q.of_int 0) mod)) ((Q.lt mod (Q.abs den)))) then None
3410
else
3411
let ghost den_sign = pure { if den <. 0. then -1 else 1 } in
3412
let predicate mod_is_in (num:real) =
3413
pure { mod = Real.mod_e num den }
3414
in
3415
let mod_is_integer (num:Q.t)
3416
ensures { mod_is_in num <-> result }
3417
=
3418
(Q.equal (Q.mod_e num den) mod)
3419
in
3420
let mod_floorb (num:Q.t) (b:Bound.t) : Q.t
3421
ensures { mod_is_in result }
3422
ensures { cmp result b num }
3423
ensures { forall r. cmp r b num -> result <. r -> not (mod_is_in r) }
3424
=
3425
let mod_e = Q.mod_e num den in
3426
(* num = (div_e num den)*den + (mod_e num den) *)
3427
(* num - mod_e num den + mod = (div_e num den)*den + mod *)
3428
let (r,div) = match Q.compare mod mod_e with
3429
| Ord.Eq -> match b with
3430
| Large -> num, pure {Real.div_e (Q.real num) (Q.real den)}
3431
| Strict -> (Q.sub num (Q.abs den)), pure {Real.div_e (Q.real num) (Q.real den) - den_sign }
3432
end
3433
| Ord.Lt -> (Q.add (Q.sub num mod_e) mod),pure {Real.div_e (Q.real num) (Q.real den) }
3434
| Ord.Gt -> (Q.sub (Q.add (Q.sub num mod_e) mod) (Q.abs den)),
3435
pure {Real.div_e (Q.real num) (Q.real den) - den_sign}
3436
end in
3437
uniq_div_e_real (Q.real r) (Q.real den) div (Q.real mod);
3438
r
3439
in
3440
let mod_ceilb (num:Q.t) (b:Bound.t) : Q.t
3441
ensures { mod_is_in result }
3442
ensures { cmp num b result }
3443
ensures { forall r. cmp num b r -> r <. result -> not (mod_is_in r) }
3444
=
3445
let mod_e = Q.mod_e num den in
3446
let (r,div) = match Q.compare mod mod_e with
3447
| Ord.Eq -> match b with
3448
| Large -> num, pure {Real.div_e (Q.real num) (Q.real den)}
3449
| Strict -> (Q.add num (Q.abs den)), pure {Real.div_e (Q.real num) (Q.real den) + den_sign}
3450
end
3451
| Ord.Lt -> (Q.add (Q.add (Q.sub num mod_e) mod) (Q.abs den)),
3452
pure {Real.div_e (Q.real num) (Q.real den) + den_sign}
3453
| Ord.Gt -> (Q.add (Q.sub num mod_e) mod),pure {Real.div_e (Q.real num) (Q.real den) }
3454
end in
3455
uniq_div_e_real (Q.real r) (Q.real den) div (Q.real mod);
3456
let lemma no_other (q:real)
3457
requires { cmp num b q } requires { q <. r }
3458
ensures { Real.mod_e q den <> mod } =
3459
let mod_q_aux = pure { q-.num+.mod_e } in
3460
let div_q = pure { if mod_q_aux <. abs (Q.real den) then Real.div_e (Q.real num) (Q.real den) else div } in
3461
let mod_q = pure { if mod_q_aux <. abs den then mod_q_aux else mod_q_aux -. abs den } in
3462
assert { if mod_q_aux <. abs den then mod_q <> mod
3463
else mod_q <. mod };
3464
uniq_div_e_real q (Q.real den) div_q mod_q;
3465
in
3466
r
3467
in
3468
let op =
3469
{ red_is_in = mod_is_in; red_is_integer = mod_is_integer;
3470
red_floorb = mod_floorb; red_ceilb = mod_ceilb; red_min = I;}
3471
in
3472
assert { forall d n. mem (Real.mod_e n d) modl.a -> (Real.mod_e n d) = mod };
3473
assert { forall d n. mem d denl.a -> mem (Real.mod_e n d) modl.a -> Real.mod_e n den = mod };
3474
assert { forall d n. mem d denl.a -> mem (Real.mod_e n d) modl.a -> op.red_is_in n };
3475
reduce_generic op num
3476
| _ -> Some num
3477
end
3478
3479
function
div_t_real
(a b:real) : real = from_int (Real.div_t a b)
3480
Valid (1.7s) (colibri2)
3481
let
div_t_forward
(l1 l2:t) : t
3482
ensures { sound2 memt div_t_real l1 l2 result } =
3483
NonIncreasing.truncate (Increasing.Binary.div l1 l2)
3484
Valid (955ms) (cvc4)
3485
lemma
mod_t
: forall a b. b <> 0. -> (-. abs b) <. (Real.mod_t a b) <. abs b
3486
Valid (487ms) (cvc4)
3487
let ghost
uniq_div_t_real
(num:real) (den:real) (div:int) (mod:real) : unit
3488
requires { num = (from_int div)*.den +. mod }
3489
requires { if num <. 0. then -. (abs den) <. mod <=. 0. else 0. <=. mod <. abs den }
3490
ensures { Real.mod_t num den = mod } = ()
3491
Valid (267ms) (cvc4)
3492
let ghost
mod_t_nonneg
(x den:real) : unit
3493
requires { den <> 0. }
3494
requires { 0. <=. x }
3495
ensures { 0. <=. Real.mod_t x den <. abs den }
3496
= ()
3497
Valid (1.2s) (colibri2) (cvc4) (cvc5) (split_vc) (depth 1)
3498
let ghost
mod_t_neg
(n d:real) : unit
3499
requires { d <> 0. }
3500
ensures { Real.mod_t (-. n) d = -. Real.mod_t n d }
3501
= assert { (-. n) /. d = -. (n /. d) };
3502
assert { Truncate.truncate (-. (n /. d)) = - Truncate.truncate (n /. d) }
3503
Valid (32ms) (colibri2)
3504
let ghost
mod_t_nonpos
(x den:real) : unit
3505
requires { den <> 0. }
3506
requires { x <=. 0. }
3507
ensures { -. abs den <. Real.mod_t x den <=. 0. }
3508
= mod_t_neg (-. x) den; mod_t_nonneg (-. x) den
3509
Valid (33ms) (colibri2)
3510
let ghost
mod_t_le
(x den:real) : unit
3511
requires { 0. <=. x }
3512
ensures { Real.mod_t x den <=. x }
3513
= if pure { den <> 0. } then mod_t_nonneg x den
3514
Valid (1.1s) (cvc4)
3515
let ghost
mod_t_period
(x y den:real) : unit
3516
requires { den <> 0. }
3517
requires { x <. y <. x +. abs den }
3518
ensures { Real.mod_t x den <> Real.mod_t y den }
3519
= let ghost k = pure { Real.div_t y den - Real.div_t x den } in
3520
assert { Real.mod_t x den = Real.mod_t y den -> y -. x = from_int k *. den };
3521
assert { k = 0 \/ k >= 1 \/ k <= -1 };
3522
assert { k >= 1 -> abs (from_int k *. den) >=. abs den };
3523
assert { k <= -1 -> abs (from_int k *. den) >=. abs den }
3524
3525
(* The Euclidean Definition of the Functions div and mod RAYMOND T. BOUTE *) Valid (1.1s) (colibri2) (cvc4 3) (cvc5 9) (split_vc) (depth 1)
3526
let ghost
div_t_real_monotonies
() : unit
3527
ensures { forall xm xM ym yM. 0. <. xm <=. xM -> 0. <. ym <=. yM ->
3528
0. <=. div_t_real xm yM <=. div_t_real xM ym }
3529
ensures { forall xm xM ym yM. xm <=. 0. <=. xM -> 0. <. ym <=. yM ->
3530
div_t_real xm ym <=. 0. <=. div_t_real xM ym }
3531
ensures { forall xm xM ym yM. xm <=. xM <. 0. -> 0. <. ym <=. yM ->
3532
div_t_real xm ym <=. div_t_real xM yM <=. 0. }
3533
ensures { forall xm xM ym yM. 0. <. xm <=. xM -> ym <=. yM <. 0. ->
3534
div_t_real xM yM <=. div_t_real xm ym <=. 0. }
3535
ensures { forall xm xM ym yM. xm <=. 0. <=. xM -> ym <=. yM <. 0. ->
3536
div_t_real xM yM <=. 0. <=. div_t_real xm yM }
3537
ensures { forall xm xM ym yM. xm <=. xM <. 0. -> ym <=. yM <. 0. ->
3538
0. <=. div_t_real xM ym <=. div_t_real xm yM } =

Proof

3540
assert { forall xm xM ym yM. 0. <. xm <=. xM -> 0. <. ym <=. yM -> 0 <= Real.div_t xm yM <= Real.div_t xM ym };
3541
assert { forall xm xM ym yM. xm <=. 0. <=. xM -> 0. <. ym <=. yM -> Real.div_t xm ym <= 0 <= Real.div_t xM ym };
3542
assert { forall xm xM ym yM. xm <=. xM <. 0. -> 0. <. ym <=. yM -> Real.div_t xm ym <= Real.div_t xM yM <= 0 };
3543
assert { forall x x' y. y <. 0. -> x <=. x' -> Real.div_t x y >= Real.div_t x' y };
3544
assert { forall xm xM ym yM. 0. <. xm <=. xM -> ym <=. yM <. 0. -> Real.div_t xM yM <= Real.div_t xm ym <= 0 };
3545
assert { forall xm xM ym yM. xm <=. 0. <=. xM -> ym <=. yM <. 0. -> Real.div_t xM yM <= 0 <= Real.div_t xm yM };
3546
assert { forall xm xM ym yM. xm <=. xM <. 0. -> ym <=. yM <. 0. -> 0 <= Real.div_t xM ym <= Real.div_t xm yM }

QED

The cases of mod_t_forward where the interval spans two periods, apart so that the or–patterns of the bounds do not duplicate them

    Valid (853ms) (colibri2 11) (cvc5) (split_vc) (depth 1)
3552
let ghost
mod_t_two_neg
(rmin rmax m mid:real) : unit
3553
requires { 0. <. m }
3554
requires { rmin <. 0. }
3555
requires { rmax <. 0. }
3556
requires { from_int (Real.div_t rmax m) = from_int (Real.div_t rmin m) +. 1. }
3557
requires { mid = from_int (Real.div_t rmin m) *. m }
3558
ensures { Real.mod_t rmax m <=. 0. }
3559
ensures { Real.mod_t rmin m <=. 0. }
3560
ensures { rmin <=. mid <. rmax }
3561
ensures { Real.mod_t mid m = 0. }
3562
ensures { forall q. mid <. q <. rmax -> -. m <. Real.mod_t q m <. Real.mod_t rmax m }
3563
ensures { forall q. rmin <. q <=. mid -> Real.mod_t rmin m <. Real.mod_t q m <=. 0. }
3564
= div_t_real_monotonies ();
3565
assert { Real.mod_t rmax m <=. 0. };
3566
assert { Real.mod_t rmin m <=. 0. };
3567
assert { rmin <=. mid <. rmax };
3568
assert { Real.mod_t mid m = 0. };
3569
assert { forall q. mid <. q <. rmax -> -. m <. Real.mod_t q m <. Real.mod_t rmax m };
3570
assert { forall q. rmin <. q <=. mid -> Real.mod_t rmin m <. Real.mod_t q m <=. 0. };
3571
()
3572
Valid (1.2s) (colibri2 13) (cvc4 2) (cvc5) (split_vc) (depth 1)
3573
let ghost
mod_t_two_pos
(rmin rmax m mid:real) : unit
3574
requires { 0. <. m }
3575
requires { 0. <=. rmin }
3576
requires { 0. <=. rmax }
3577
requires { from_int (Real.div_t rmax m) = from_int (Real.div_t rmin m) +. 1. }
3578
requires { mid = from_int (Real.div_t rmax m) *. m }
3579
ensures { 0. <=. Real.mod_t rmax m }
3580
ensures { 0. <=. Real.mod_t rmin m }
3581
ensures { rmin <. mid <=. rmax }
3582
ensures { Real.mod_t mid m = 0. }
3583
ensures { forall q. mid <=. q <. rmax -> 0. <=. Real.mod_t q m <. Real.mod_t rmax m }
3584
ensures { forall q. rmin <. q <. mid ->
3585
from_int (Real.div_t rmin m) <=. q /. m <. from_int (Real.div_t rmin m) +. 1. }
3586
ensures { forall q. rmin <. q <. mid -> Real.div_t q m = Real.div_t rmin m }
3587
ensures { forall q. rmin <. q <. mid -> Real.mod_t rmin m <. Real.mod_t q m <. m }
3588
= div_t_real_monotonies ();
3589
assert { 0. <=. Real.mod_t rmax m };
3590
assert { 0. <=. Real.mod_t rmin m };
3591
assert { rmin <. mid <=. rmax };
3592
assert { Real.mod_t mid m = 0. };
3593
assert { forall q. mid <=. q <. rmax -> 0. <=. Real.mod_t q m <. Real.mod_t rmax m };
3594
assert { forall q. rmin <. q <. mid ->
3595
from_int (Real.div_t rmin m) <=. q /. m <. from_int (Real.div_t rmin m) +. 1. };
3596
assert { forall q. rmin <. q <. mid -> Real.div_t q m = Real.div_t rmin m };
3597
assert { forall q. rmin <. q <. mid -> Real.mod_t rmin m <. Real.mod_t q m <. m };
3598
()
3599
Valid (550ms) (colibri2 12) (cvc4 2) (split_vc) (depth 1)
3600
let ghost
mod_t_two_zero
(rmin rmax m mid:real) : unit
3601
requires { 0. <. m }
3602
requires { rmin <. 0. }
3603
requires { 0. <=. rmax }
3604
requires { from_int (Real.div_t rmin m) = 0. }
3605
requires { from_int (Real.div_t rmax m) = from_int (Real.div_t rmin m) +. 1. }
3606
requires { mid = from_int (Real.div_t rmax m) *. m }
3607
ensures { 0. <=. Real.mod_t rmax m }
3608
ensures { Real.mod_t rmin m <=. 0. }
3609
ensures { rmin <. mid <=. rmax }
3610
ensures { Real.mod_t mid m = 0. }
3611
ensures { forall q. mid <=. q <. rmax -> Real.mod_t rmin m <. 0. <=. Real.mod_t q m <. Real.mod_t rmax m <. m }
3612
ensures { forall q. rmin <. q <. mid -> Real.mod_t rmin m <. Real.mod_t q m <. m }
3613
ensures { forall q. rmin <. q <. rmax -> Real.mod_t rmin m <. Real.mod_t q m <. m }
3614
= div_t_real_monotonies ();
3615
assert { 0. <=. Real.mod_t rmax m };
3616
assert { Real.mod_t rmin m <=. 0. };
3617
assert { rmin <. mid <=. rmax };
3618
assert { Real.mod_t mid m = 0. };
3619
assert { forall q. mid <=. q <. rmax -> Real.mod_t rmin m <. 0. <=. Real.mod_t q m <. Real.mod_t rmax m <. m };
3620
assert { forall q. rmin <. q <. mid -> Real.mod_t rmin m <. Real.mod_t q m <. m };
3621
assert { forall q. rmin <. q <. rmax -> Real.mod_t rmin m <. Real.mod_t q m <. m };
3622
()
3623
Valid (588ms) (colibri2 12) (cvc4 2) (split_vc) (depth 1)
3624
let ghost
mod_t_two_cross
(rmin rmax m mid:real) : unit
3625
requires { 0. <. m }
3626
requires { rmin <. 0. }
3627
requires { 0. <=. rmax }
3628
requires { from_int (Real.div_t rmin m) <> 0. }
3629
requires { from_int (Real.div_t rmax m) = from_int (Real.div_t rmin m) +. 1. }
3630
requires { mid = from_int (Real.div_t rmin m) *. m }
3631
ensures { 0. <=. Real.mod_t rmax m }
3632
ensures { Real.mod_t rmin m <=. 0. }
3633
ensures { rmin <=. mid <. rmax }
3634
ensures { Real.mod_t mid m = 0. }
3635
ensures { forall q. mid <. q <. rmax -> -. m <. Real.mod_t q m <. Real.mod_t rmax m }
3636
ensures { forall q. rmin <. q <=. mid -> -. m <. Real.mod_t rmin m <. Real.mod_t q m <=. 0. <=. Real.mod_t rmax m }
3637
ensures { forall q. rmin <. q <. rmax -> -. m <. Real.mod_t q m <=. Real.mod_t rmax m }
3638
= div_t_real_monotonies ();
3639
assert { 0. <=. Real.mod_t rmax m };
3640
assert { Real.mod_t rmin m <=. 0. };
3641
assert { rmin <=. mid <. rmax };
3642
assert { Real.mod_t mid m = 0. };
3643
assert { forall q. mid <. q <. rmax -> -. m <. Real.mod_t q m <. Real.mod_t rmax m };
3644
assert { forall q. rmin <. q <=. mid -> -. m <. Real.mod_t rmin m <. Real.mod_t q m <=. 0. <=. Real.mod_t rmax m };
3645
assert { forall q. rmin <. q <. rmax -> -. m <. Real.mod_t q m <=. Real.mod_t rmax m };
3646
()
3647
Valid (1.9s) (colibri2 166) (cvc4 60) (cvc5 13) (split_vc 19) (depth 5)
3648
let
mod_t_forward
(l1 l2:t) : t
3649
ensures { sound2 memt (fun (x y:real) -> Real.mod_t x y) l1 l2 result } =
3650
let zero = (Q.of_int 0) in
3651
if mem zero l2 then { a = On Inf }
3652
else
3653
let _ = not_bottom l2 in
3654
match l2.a with
3655
| Off (Sin m Inf) ->
3656
let function fr (x:real) = pure { Real.mod_t x m } in
3657
let m0 = m in
3658
let m = Q.abs m in
3659
let all = Cons (Map.Inter (Map.BStrict ((Q.sub zero m))) (Map.BStrict m)) Nil in
3660
let all_pos = Cons (Map.Inter (Map.BLarge zero) (Map.BStrict m)) Nil in
3661
let all_neg = Cons (Map.Inter (Map.BStrict ((Q.sub zero m))) (Map.BLarge zero)) Nil in
3662
let f (i:Map.interval) : list Map.interval
3663
ensures { forall r. Map.mem_interval r i -> Map.mem_res_interval (fr r) result }
3664
ensures { result <> Nil }
3665
=
3666
match i with
3667
| Map.Singleton r -> Cons (Map.Singleton (Q.mod_t r m)) Nil
3668
| Map.Inter Map.BInf Map.BInf -> all
3669
| Map.Inter Map.BInf (Map.BLarge r | Map.BStrict r) ->
3670
if Q.lt zero r then all else all_neg
3671
| Map.Inter (Map.BLarge r | Map.BStrict r) Map.BInf ->
3672
if Q.lt r zero then all else all_pos
3673
| Map.Inter ((Map.BLarge rmin | Map.BStrict rmin) as bmin)
3674
((Map.BLarge rmax | Map.BStrict rmax) as bmax) ->
3675
let rmin_mod = match bmin with
3676
| Map.BInf -> absurd
3677
| Map.BLarge b -> Map.BLarge (Q.mod_t b m)
3678
| Map.BStrict b -> Map.BStrict (Q.mod_t b m)
3679
end
3680
in
3681
let rmax_mod = match bmax with
3682
| Map.BInf -> absurd
3683
| Map.BLarge b -> Map.BLarge (Q.mod_t b m)
3684
| Map.BStrict b -> Map.BStrict (Q.mod_t b m)
3685
end
3686
in
3687
let rmin_div = Q.div_t rmin m in
3688
let rmax_div = Q.div_t rmax m in
3689
div_t_real_monotonies ();
3690
assert { forall x. Real.mod_t x m = Real.mod_t x m0 };
3691
if Q.equal rmin_div rmax_div then
3692
Cons (Map.Inter rmin_mod rmax_mod) Nil
3693
else if Q.equal (Q.add rmin_div (Q.of_int 1)) rmax_div
3694
then
3695
match (Q.lt rmin zero), (Q.lt rmax zero) with
3696
| True, True ->
3697
let mid = pure { rmin_div *. m } in
3698
mod_t_two_neg (pure { Q.real rmin }) (pure { Q.real rmax }) (pure { Q.real m }) mid;
3699
Cons (Map.Inter rmin_mod (Map.BLarge zero))
3700
(Cons (Map.Inter (Map.BStrict (Q.sub zero m)) rmax_mod) Nil)
3701
| False, False ->
3702
let mid = pure { rmax_div *. m } in
3703
mod_t_two_pos (pure { Q.real rmin }) (pure { Q.real rmax }) (pure { Q.real m }) mid;
3704
Cons (Map.Inter rmin_mod (Map.BStrict m))
3705
(Cons (Map.Inter (Map.BLarge (Q.of_int 0)) rmax_mod) Nil)
3706
| False, True -> absurd
3707
| True, False ->
3708
assert { rmin <=. 0. <=. rmax };
3709
if Q.equal rmin_div zero then (
3710
let mid = pure { rmax_div *. m } in
3711
mod_t_two_zero (pure { Q.real rmin }) (pure { Q.real rmax }) (pure { Q.real m }) mid;
3712
Cons (Map.Inter (Map.BLarge (Q.mod_t rmin m)) (Map.BStrict m)) Nil
3713
)
3714
else (
3715
let mid = pure { rmin_div *. m } in
3716
mod_t_two_cross (pure { Q.real rmin }) (pure { Q.real rmax }) (pure { Q.real m }) mid;
3717
Cons (Map.Inter (Map.BStrict ((Q.sub zero m))) (Map.BLarge (Q.mod_t rmax m))) Nil
3718
)
3719
end
3720
else if Q.le zero rmin then begin
3721
let lemma lem (x:real) requires { rmin <=. x } ensures { 0. <=. fr x <. m } = mod_t_nonneg x (Q.real m0) in
3722
all_pos end
3723
else if Q.le rmax zero then begin
3724
let lemma lem (x:real) requires { x <=. rmax } ensures { -. m <. fr x <=. 0. } = mod_t_nonpos x (Q.real m0) in
3725
all_neg end
3726
else begin
3727
assert { forall x. -. m <. fr x <. m };
3728
all end
3729
end
3730
in
3731
let f = { Map.Unary.f = f; Map.Unary.fr = fr } in
3732
Map.Unary.map f l1
3733
| _ ->
3734
match mem_min l2,mem_max l2 with
3735
| None, _ | _, None -> { a = On Inf }
3736
| Some (m,b), Some (m',b') ->
3737
let m = Q.abs m in
3738
let m' = Q.abs m' in
3739
let (m,b) = max_bound_sup m b m' b' in
3740
assert { forall r2. mem r2 l2.a -> cmp (abs r2) b m };
3741
{ a = Off (Chg (Q.sub zero m) Strict (Chg m Large Inf))}
3742
end
3743
end
3760
3761
(* let mod_t_forward (l1 l2:t) : t ensures { forall r1 r2. mem r1 l1.a -> mem r2 l2.a -> mem (Real.mod_t r1 r2) result.a } = let zero = (Q.of_int 0) in if mem zero l2 then { a = On Inf } else let _ = not_bottom l2 in match mem_min l2,mem_max l2 with | None, _ | _, None -> { a = On Inf } | Some (m0,b0), Some (m1,b1) -> let m0' = Q.abs m0 in let m1' = Q.abs m1 in let (m,b) = max_bound_sup m0' b0 m1' b1 in assert { forall r2. mem r2 l2.a -> cmp r2 b m }; assert { forall r2. cmp (-. m0') b0 r2 -> cmp (-. m1') b1 r2 -> cmp (-. m) b r2 }; assert { forall r2. mem r2 l2.a -> cmp (-. m) b r2 }; { a = Off (Chg (Q.sub zero m) b (Chg m (inv_bound b) Inf)) } end *)
3762
Valid (1.8s) (colibri2 66) (cvc4 9) (cvc5 38) (split_vc 28) (depth 4)
3763
let
mod_t_backward_num
(num:t) (denl:t) (modl:t) : option t
3764
ensures { back2 memt (fun (x y:real) -> Real.mod_t x y) num denl modl result } =
3765
match denl.a, modl.a with
3766
| Off (Sin den Inf), Off (Sin mod Inf) ->
3767
let zero = Q.of_int 0 in
3768
let f_pos mod (num:t) =
3769
requires { 0. <=. mod }
3770
requires { (le_infr_bound (R mod) num.a) }
3771
ensures { forall n d. mem n num.a -> mem d denl.a -> (Real.mod_t n d) = mod -> match result with None -> false | Some r -> mem n r.a end }
3772
(* Only singleton in den and mod for now *)
3773
if Q.equal den zero then Some num
3774
else if notb (andb ((Q.le (Q.sub zero (Q.abs den)) mod)) ((Q.lt mod (Q.abs den)))) then None
3775
else
3776
let ghost den_sign = if (Q.real den <. 0.) then (-1:int) else (1:int) in
3777
assert { from_int den_sign = abs den /. den };
3778
let ghost mod_min = R (Q.real mod) in
3779
let predicate mod_is_in (num:real) =
3780
pure { mod = Real.mod_t num den }
3781
in
3782
let mod_is_integer (num:Q.t)
3783
ensures { mod_is_in num <-> result }
3784
=
3785
(Q.equal (Q.mod_t num den) mod)
3786
in
3787
let mod_floorb (num:Q.t) (b:Bound.t) : Q.t
3788
ensures { (lt_infr mod_min (R num)) -> mod_is_in result }
3789
ensures { (lt_infr mod_min (R num)) -> cmp result b num }
3790
ensures { forall r. (lt_infr mod_min (R num)) -> cmp r b num -> result <. r -> not (mod_is_in r) }
3791
=
3792
let mod_t = Q.mod_t num den in
3793
if pure { 0. <=. num } then mod_t_nonneg (Q.real num) (Q.real den);
3794
(* num = (div_t num den)*den + (mod_t num den) *)
3795
let r,div =(
3796
(* num = (div_e num den)*den + (mod_e num den) *)
3797
(* num - mod_e num den + mod = (div_e num den)*den + mod *)
3798
match Q.compare mod mod_t with
3799
| Ord.Eq -> match b with
3800
| Large -> num, pure {Real.div_t (Q.real num) (Q.real den)}
3801
| Strict -> (Q.sub num (Q.abs den)), pure {Real.div_t (Q.real num) (Q.real den) - den_sign }
3802
end
3803
| Ord.Lt -> (Q.add (Q.sub num mod_t) mod),pure {Real.div_t (Q.real num) (Q.real den) }
3804
| Ord.Gt -> (Q.sub (Q.add (Q.sub num mod_t) mod) (Q.abs den)),
3805
pure {Real.div_t (Q.real num) (Q.real den) - den_sign}
3806
end) in
3807
if pure {mod <. num} then begin
3808
uniq_div_t_real (Q.real r) (Q.real den) div (Q.real mod)
3809
end;
3810
let lemma no_other (r':real)
3811
requires { mod <. num /\ r <. r' /\ cmp r' b num }
3812
ensures { not (mod_is_in r') } = mod_t_period (Q.real r) r' (Q.real den) in
3813
r
3814
in
3815
let mod_ceilb (num:Q.t) (b:Bound.t) : Q.t
3816
ensures { (le_infr mod_min (R num)) -> mod_is_in result }
3817
ensures { (le_infr mod_min (R num)) -> cmp num b result }
3818
ensures { forall r. (le_infr mod_min (R num)) -> cmp num b r -> r <. result -> not (mod_is_in r) }
3819
=
3820
let mod_t = Q.mod_t num den in
3821
if pure { 0. <=. num } then mod_t_nonneg (Q.real num) (Q.real den);
3822
let (r,div) = match Q.compare mod mod_t with
3823
| Ord.Eq -> match b with
3824
| Large -> num, pure {Real.div_t (Q.real num) (Q.real den)}
3825
| Strict -> (Q.add num (Q.abs den)), pure {Real.div_t (Q.real num) (Q.real den) + den_sign}
3826
end
3827
| Ord.Lt -> (Q.add (Q.add (Q.sub num mod_t) mod) (Q.abs den)),
3828
pure {Real.div_t (Q.real num) (Q.real den) + den_sign}
3829
| Ord.Gt ->
3830
let lemma no_other (r:real)
3831
requires { mod <=. num }
3832
requires { num <=. r <. num -. mod_t +. mod }
3833
ensures { mod_t <=. Real.mod_t r den <. mod } =
3834
let mod_r = pure { r-.num+.mod_t } in
3835
uniq_div_t_real r (Q.real den) pure {Real.div_t (Q.real num) (Q.real den)} mod_r;
3836
in
3837
(Q.add (Q.sub num mod_t) mod),pure {Real.div_t (Q.real num) (Q.real den) }
3838
end in
3839
if pure {mod <=. num} then begin
3840
uniq_div_t_real (Q.real r) (Q.real den) div (Q.real mod);
3841
end;
3842
let lemma no_other (r':real)
3843
requires { mod <=. num /\ r' <. r /\ cmp num b r' }
3844
ensures { not (mod_is_in r') } = mod_t_period r' (Q.real r) (Q.real den) in
3845
r
3846
in
3847
let op =
3848
{ red_is_in = mod_is_in; red_is_integer = mod_is_integer;
3849
red_floorb = mod_floorb; red_ceilb = mod_ceilb; red_min = mod_min }
3850
in
3853
(* assert { forall d n. mem (Real.mod_t n d) modl.a -> (Real.mod_t n d) = mod }; assert { forall d n. mem d denl.a -> mem (Real.mod_t n d) modl.a -> Real.mod_t n den = mod }; assert { forall d n. mem d denl.a -> mem (Real.mod_t n d) modl.a -> op.red_is_in n }; *)
3854
reduce_generic op num
3855
in
3856
let neg,b,pos = Increasing.split_at num in
3857
let aux_neg () : option t
3858
requires { mod <=. 0. }
3859
ensures { forall n d. Increasing.mem_presence 0. (-. n) neg -> mem d denl.a -> (Real.mod_t n d) = mod -> match result with None -> false | Some r -> mem n r.a end }
3860
=
3861
match Increasing.presence_to_t zero neg with
3862
| None -> None
3863
| Some neg2 ->
3864
let mod' = (Q.abs mod) in
3865
let lemma ge_n (n d:real) requires { n <=. 0. }
3866
ensures { n <=. Real.mod_t n d } =
3867
if pure { d <> 0. } then begin mod_t_neg n d; mod_t_le (-. n) d end in
3868
match inter (ge mod') neg2 with
3869
| None -> None
3870
| Some neg3 ->
3871
assert { forall x:real. mem x neg3.a <-> (Q.real mod' <=. x /\ mem x neg2.a) };
3872
not_mem_is_le_bound False (Q.real mod') neg3.a;
3873
assert { forall n d. Increasing.mem_presence 0. (-. n) neg -> mem d denl.a -> (Real.mod_t n d) = mod -> mem (-. n) neg3.a };
3874
let lemma mn (n d:real) requires { d <> 0. }
3875
ensures { Real.mod_t (-.n) d = -. Real.mod_t n d } = mod_t_neg n d in
3876
match f_pos mod' neg3 with
3877
| None -> None
3878
| Some neg4 ->
3879
Some (Increasing.Unary.neg neg4)
3880
end
3881
end
3882
end
3883
in
3884
let aux_pos () : option t
3885
requires { 0. <=. mod }
3886
ensures { forall n d. Increasing.mem_presence 0. n pos -> mem d denl.a -> (Real.mod_t n d) = mod -> match result with None -> false | Some r -> mem n r.a end }
3887
=
3888
match Increasing.presence_to_t zero pos with
3889
| None -> None
3890
| Some neg2 ->
3891
let mod' = mod in
3892
let lemma le_n (n d:real) requires { 0. <=. n }
3893
ensures { Real.mod_t n d <=. n } = mod_t_le n d in
3894
match inter (ge mod') neg2 with
3895
| None -> None
3896
| Some neg3 ->
3897
assert { forall x:real. mem x neg3.a <-> (Q.real mod' <=. x /\ mem x neg2.a) };
3898
not_mem_is_le_bound False (Q.real mod') neg3.a;
3899
assert { forall n d. Increasing.mem_presence 0. n pos -> mem d denl.a -> (Real.mod_t n d) = mod -> mem n neg3.a };
3900
f_pos mod' neg3
3901
end
3902
end
3903
in
3904
match Q.compare zero mod with
3905
| Ord.Eq -> match aux_neg (), aux_pos () with
3906
| Some neg, Some pos -> Some (let u = union neg pos in if b then union (singleton zero) u else u)
3907
| Some neg, None -> Some (let u = neg in if b then union (singleton zero) u else u)
3908
| None, Some pos -> Some (let u = pos in if b then union (singleton zero) u else u)
3909
| None, None -> if b then Some (singleton zero) else None
3910
end
3911
| Ord.Lt ->
3912
assert { forall n d. mem n num.a -> mem d denl.a -> mem (Real.mod_t n d) modl.a -> (Real.mod_t n d) = mod };
3913
assert { forall n d. d <> 0. -> (Real.mod_t n d) >. 0. -> n >. 0. };
3914
assert { forall n. mem n num.a -> (Real.mod_t n den) = mod -> n >. 0. };
3915
assert { forall n d. mem n num.a -> mem d denl.a -> mem (Real.mod_t n d) modl.a -> Increasing.mem_presence 0. n pos };
3916
aux_pos ()
3917
| Ord.Gt ->
3918
assert { forall n d. mem n num.a -> mem d denl.a -> mem (Real.mod_t n d) modl.a -> (Real.mod_t n d) = mod };
3919
assert { forall n d. d <> 0. -> (Real.mod_t n d) <. 0. -> n <. 0. };
3920
assert { forall n. mem n num.a -> (Real.mod_t n den) = mod -> n <. 0. };
3921
assert { forall n d. mem n num.a -> mem d denl.a -> mem (Real.mod_t n d) modl.a -> Increasing.mem_presence 0. (-. n) neg };
3922
aux_neg ()
3923
end
3924
| _ -> Some num
3925
end
3926
3927
3928
function
div_f_real
(a b:real) : real = from_int (Real.div_f a b)
3929
Valid (169ms) (colibri2)
3930
let
div_f_forward
(l1 l2:t) : t
3931
ensures { sound2 memt div_f_real l1 l2 result } =
3932
NonIncreasing.floor (Increasing.Binary.div l1 l2)
3933
Valid (503ms) (cvc4)
3934
lemma
mod_f
: forall a b. b <> 0. -> (-. abs b) <. (Real.mod_f a b) <. abs b
3935
Valid (861ms) (cvc4)
3936
let ghost
uniq_div_f_real
(num:real) (den:real) (div:int) (mod:real) : unit
3937
requires { num = (from_int div)*.den +. mod }
3938
requires { if den <. 0. then den <. mod <=. 0. else 0. <=. mod <. den }
3939
ensures { Real.mod_f num den = mod } = ()
3940
Valid (384ms) (colibri2 9) (cvc4 2) (cvc5 8) (split_vc 3) (depth 3)
3941
let
mod_f_forward
(l1 l2:t) : t
3942
ensures { sound2 memt (fun (x y:real) -> Real.mod_f x y) l1 l2 result } =
3943
let zero = (Q.of_int 0) in
3944
if mem zero l2 then { a = On Inf }
3945
else
3946
let _ = not_bottom l2 in
3947
match mem_min l2,mem_max l2 with
3948
| None, _ | _, None -> { a = On Inf }
3949
| Some (m0,b0), Some (m1,b1) ->
3950
let m0' = Q.abs m0 in
3951
let m1' = Q.abs m1 in
3952
let (m,b) = max_bound_sup m0' b0 m1' b1 in
3953
assert { forall r2. mem r2 l2.a -> cmp r2 b m };
3954
assert { forall r2. mem r2 l2.a -> cmp (-. r2) b0 m0' };
3955
assert { forall r2. mem r2 l2.a -> cmp (-. r2) b m };
3956
assert { forall r2. mem r2 l2.a -> cmp (-. m) b r2 };
3957
{ a = Off (Chg (Q.sub zero m) b (Chg m (inv_bound b) Inf)) }
3958
end
3959
Valid (3.5s) (colibri2 8) (cvc4 11) (cvc5 20) (split_vc 9) (depth 4)
3960
let
mod_f_backward_num
(num:t) (denl:t) (modl:t) : option t
3961
ensures { back2 memt (fun (x y:real) -> Real.mod_f x y) num denl modl result } =
3962
match denl.a, modl.a with
3963
| Off (Sin den Inf), Off (Sin mod Inf) ->
3964
let zero = Q.of_int 0 in
3965
(* Only singleton in den and mod for now *)
3966
if Q.equal den zero then Some num
3967
else
3968
let inside = if Q.lt den zero then (andb ((Q.lt den mod)) ((Q.le mod zero))) else (andb ((Q.le zero mod)) ((Q.lt mod den))) in
3969
if not inside then None
3970
else
3971
let ghost den_sign = if (Q.real den <. 0.) then (-1:int) else (1:int) in
3972
assert { from_int den_sign = abs den /. den };
3973
let ghost mod_min = I in
3974
let predicate mod_is_in (num:real) =
3975
pure { mod = Real.mod_f num den }
3976
in
3977
let mod_is_integer (num:Q.t)
3978
ensures { mod_is_in num <-> result }
3979
=
3980
(Q.equal (Q.mod_f num den) mod)
3981
in
3982
let mod_floorb (num:Q.t) (b:Bound.t) : Q.t
3983
ensures { (lt_infr mod_min (R num)) -> mod_is_in result }
3984
ensures { (lt_infr mod_min (R num)) -> cmp result b num }
3985
ensures { forall r. (lt_infr mod_min (R num)) -> cmp r b num -> result <. r -> not (mod_is_in r) }
3986
=
3987
let mod_f = Q.mod_f num den in
3988
(* num = (div_f num den)*den + (mod_f num den) *)
3989
let r,div =(
3990
(* num = (div_e num den)*den + (mod_e num den) *)
3991
(* num - mod_e num den + mod = (div_e num den)*den + mod *)
3992
match Q.compare mod mod_f with
3993
| Ord.Eq -> match b with
3994
| Large -> num, pure {Real.div_f (Q.real num) (Q.real den)}
3995
| Strict -> (Q.sub num (Q.abs den)), pure {Real.div_f num den - den_sign }
3996
end
3997
| Ord.Lt -> (Q.add (Q.sub num mod_f) mod),pure {Real.div_f num den }
3998
| Ord.Gt -> (Q.sub (Q.add (Q.sub num mod_f) mod) (Q.abs den)),
3999
pure {Real.div_f num den - den_sign}
4000
end) in
4001
uniq_div_f_real (Q.real r) (Q.real den) div (Q.real mod);
4002
r
4003
in
4004
let mod_ceilb (num:Q.t) (b:Bound.t) : Q.t
4005
ensures { (le_infr mod_min (R num)) -> mod_is_in result }
4006
ensures { (le_infr mod_min (R num)) -> cmp num b result }
4007
ensures { forall r. (le_infr mod_min (R num)) -> cmp num b r -> r <. result -> not (mod_is_in r) }
4008
=
4009
let mod_f = Q.mod_f num den in
4010
let (r,div) = match Q.compare mod mod_f with
4011
| Ord.Eq -> match b with
4012
| Large -> num, pure {Real.div_f num den}
4013
| Strict -> (Q.add num (Q.abs den)), pure {Real.div_f num den + den_sign}
4014
end
4015
| Ord.Lt -> (Q.add (Q.add (Q.sub num mod_f) mod) (Q.abs den)),
4016
pure {Real.div_f num den + den_sign}
4017
| Ord.Gt ->
4018
let lemma no_other (r:real)
4019
requires { mod <=. num }
4020
requires { num <=. r <. num -. mod_f +. mod }
4021
ensures { mod_f <=. Real.mod_f r den <. mod } =
4022
let mod_r = pure { r-.num+.mod_f } in
4023
uniq_div_f_real r (Q.real den) pure {Real.div_f num den} mod_r;
4024
in
4025
(Q.add (Q.sub num mod_f) mod),pure {Real.div_f num den }
4026
end in
4027
uniq_div_f_real (Q.real r) (Q.real den) div (Q.real mod);
4028
r
4029
in
4030
let op =
4031
{ red_is_in = mod_is_in; red_is_integer = mod_is_integer;
4032
red_floorb = mod_floorb; red_ceilb = mod_ceilb; red_min = mod_min }
4033
in
4034
reduce_generic op num
4035
| _ -> Some num
4036
end
4037
4038
4039
end
4040
4041
end
4042
end