Common — library colibrilib.fp_interval — module Intervals

Sorted lists of disjoint intervals

9
module Intervals
10
use list.List
11
use list.Length
12
use int.Int
13
use colibrilib.fbin.Fp
14
use colibrilib.fp_facts.Facts

The floats of [a, b]

17
predicate
in_iv
(v: t) (a b: t) = le_dz a v /\ le_dz v b
18
19
predicate
mem_u
(v: t) (l: list (t, t)) =
20
match l with
21
| Nil -> false
22
| Cons (a, b) r -> in_iv v a b \/ mem_u v r
23
end

Sorted, disjoint, not NaN, not empty

26
predicate
ok_u
(l: list (t, t)) =
27
match l with
28
| Nil -> true
29
| Cons (a, b) r ->
30
is_not_nan a /\ is_not_nan b /\ le_dz a b /\
31
(match r with Nil -> true | Cons (a', _) _ -> lt_dz b a' end) /\
32
ok_u r
33
end

The bounds of l are floats of the format fm

36
predicate
fmt_u
(fm: format) (l: list (t, t)) =
37
match l with
38
| Nil -> true
39
| Cons (a, b) r -> fmt a = fm /\ fmt b = fm /\ fmt_u fm r
40
end

Every float of l is above x

43
predicate
above
(x: t) (l: list (t, t)) = forall v. mem_u v l -> lt_dz x v
44
Valid (24ms) (colibri2)
45
let rec ghost
sorted_above
(b: t) (l: list (t, t)) : unit
46
requires { ok_u l }
47
requires { match l with Nil -> true | Cons (a, _) _ -> lt_dz b a end }
48
ensures { above b l }
49
variant { l }
50
= {proof…} match l with
51
| Nil -> ()
52
| Cons (a, b') r ->
53
lt_le_trans_any b a b'; lt_le_any b b';
54
(match r with Nil -> () | Cons _ _ -> sorted_above b' r end);
55
let lemma pt (v: t) : unit
56
requires { mem_u v l }
57
ensures { lt_dz b v }
58
= lt_le_trans_any b a v; le_lt_trans_any b b' v in
59
()
60
end {qed}

The floats of a list are not NaN, and of the format of its bounds

  Valid (11ms) (colibri2)
63
let rec ghost
mem_u_not_nan
(v: t) (l: list (t, t)) : unit
64
requires { mem_u v l }
65
ensures { is_not_nan v }
66
ensures { forall fm. fmt_u fm l -> fmt v = fm }
67
variant { l }
68
= {proof…} match l with
69
| Nil -> ()
70
| Cons (a, b) r -> if pure { in_iv v a b } then () else mem_u_not_nan v r
71
end {qed}

The first float of a list is in it

  Valid (10ms) (colibri2)
74
let ghost
head_mem
(l: list (t, t)) : unit
75
requires { ok_u l }
76
ensures { match l with Nil -> true | Cons (a, _) _ -> mem_u a l end }
77
= {proof…} match l with
78
| Nil -> ()
79
| Cons (a, _) _ -> le_refl_any a
80
end {qed}

A list above x starts above x

  Valid (14ms) (colibri2)
83
let ghost
above_head
(x: t) (l: list (t, t)) : unit
84
requires { ok_u l /\ above x l }
85
ensures { match l with Nil -> true | Cons (a, _) _ -> lt_dz x a end }
86
= {proof…} head_mem l {qed}

Two overlapping intervals, the first starting first: their union is [a1, max b1 b2]

  Valid (63ms) (cvc4)
90
let ghost
merge
(a1 b1 a2 b2: t) : unit
91
requires { le_dz a1 a2 /\ le_dz a2 b2 /\ le_dz a1 b1 /\ not (lt_dz b1 a2) }
92
ensures { le_dz b1 b2 -> forall v. in_iv v a1 b2 <-> in_iv v a1 b1 \/ in_iv v a2 b2 }
93
ensures { not (le_dz b1 b2) -> forall v. in_iv v a1 b1 <-> in_iv v a1 b1 \/ in_iv v a2 b2 }
94
= {proof…}
95
le_not_nan_any a1 b1; le_not_nan_any a2 b2; total_any b1 b2; total_any b1 a2;
96
let lemma pt (v: t) : unit
97
ensures { le_dz b1 b2 -> (in_iv v a1 b2 <-> in_iv v a1 b1 \/ in_iv v a2 b2) }
98
ensures { not (le_dz b1 b2) -> (in_iv v a1 b1 <-> in_iv v a1 b1 \/ in_iv v a2 b2) }
99
= le_trans_any v b1 b2; le_trans_any a1 a2 v; lt_le_any b2 b1; le_trans_any v b2 b1;
100
le_not_nan_any a1 v; total_any v b1; total_any a2 v; lt_le_any b1 v; le_lt_trans_any b1 v a2 in
101
() {qed}

The union of two lists

  Valid (896ms) (colibri2 27) (cvc4) (cvc5 2) (split_vc 3) (depth 3)
104
let rec
union_u
(ghost fm: format) (l1 l2: list (t, t)) : list (t, t)
105
requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }
106
ensures { ok_u result /\ fmt_u fm result }
107
ensures { forall v. mem_u v result <-> mem_u v l1 \/ mem_u v l2 }
108
variant { length l1 + length l2 }
109
= match l1, l2 with
110
| Nil, l | l, Nil -> l
111
| Cons (a1, b1) d1, Cons (a2, b2) d2 ->
112
if lt_diff_zero b1 a2 then begin
113
let r = union_u fm d1 l2 in
114
{proof…} (match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);
115
sorted_above b1 l2; above_head b1 r; {qed}
116
Cons (a1, b1) r
117
end else if lt_diff_zero b2 a1 then begin
118
let r = union_u fm l1 d2 in
119
{proof…} (match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end);
120
sorted_above b2 l1; above_head b2 r; {qed}
121
Cons (a2, b2) r
122
end else if le_diff_zero a1 a2 then begin
123
{proof…} merge a1 b1 a2 b2; {qed}
124
if le_diff_zero b1 b2 then begin
125
{proof…} le_trans_any a1 a2 b2; {qed}
126
union_u fm d1 (Cons (a1, b2) d2)
127
end else
128
union_u fm l1 d2
129
end else begin
130
{proof…} le_not_nan_any a1 b1; le_not_nan_any a2 b2; total_any a1 a2; lt_le_any a2 a1;
131
merge a2 b2 a1 b1; {qed}
132
if le_diff_zero b2 b1 then begin
133
{proof…} le_trans_any a2 a1 b1; {qed}
134
union_u fm (Cons (a2, b1) d1) d2
135
end else
136
union_u fm d1 l2
137
end
138
end

The intersection of two lists

  Valid (1.2s) (colibri2 22) (cvc5 5) (split_vc) (depth 1)
141
let rec
inter_u
(ghost fm: format) (l1 l2: list (t, t)) : list (t, t)
142
requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }
143
ensures { ok_u result /\ fmt_u fm result }
144
ensures { forall v. mem_u v result <-> mem_u v l1 /\ mem_u v l2 }
145
variant { length l1 + length l2 }
146
= match l1, l2 with
147
| Nil, _ | _, Nil -> Nil
148
| Cons (a1, b1) d1, Cons (a2, b2) d2 ->
149
{proof…} le_not_nan_any a1 b1; le_not_nan_any a2 b2;
150
(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);
151
(match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end); {qed}
152
if lt_diff_zero b1 a2 then begin
153
{proof…} sorted_above b1 l2;
154
let lemma pt (v: t) : unit
155
ensures { in_iv v a1 b1 -> not (mem_u v l2) }
156
= lt_not_le_any b1 v in {qed}
157
inter_u fm d1 l2
158
end else if lt_diff_zero b2 a1 then begin
159
{proof…} sorted_above b2 l1;
160
let lemma pt (v: t) : unit
161
ensures { in_iv v a2 b2 -> not (mem_u v l1) }
162
= lt_not_le_any b2 v in {qed}
163
inter_u fm l1 d2
164
end else begin
165
let a = max_diff_zero a1 a2 in
166
{proof…} total_any b1 a2; total_any b2 a1; total_any b1 b2; {qed}
167
if le_diff_zero b2 b1 then begin
169
(* without `succ`: [a1, b1] stays whole, the next intervals of l2 start above b2 *)
170
let r = inter_u fm l1 d2 in
171
{proof…} above_head b2 r;
172
le_trans_any a1 a2 b2; le_trans_any a2 a1 b2;
173
let lemma pt (v: t) : unit
174
ensures { in_iv v a b2 <-> in_iv v a1 b1 /\ in_iv v a2 b2 }
175
= le_trans_any a1 a v; le_trans_any a2 a v; le_trans_any v b2 b1;
176
le_not_nan_any a1 v; total_any a1 a2; lt_le_any a2 a1 in
177
let lemma below (v: t) : unit
178
ensures { in_iv v a1 b1 /\ mem_u v d2 -> not (in_iv v a2 b2) }
179
= lt_not_le_any b2 v in {qed}
180
Cons (a, b2) r
181
end else begin
182
let r = inter_u fm d1 l2 in
183
{proof…} above_head b1 r; lt_le_any b1 b2;
184
le_trans_any a1 a2 b1; le_trans_any a2 a1 b1;
185
let lemma pt (v: t) : unit
186
ensures { in_iv v a b1 <-> in_iv v a1 b1 /\ in_iv v a2 b2 }
187
= le_trans_any a1 a v; le_trans_any a2 a v; le_trans_any v b1 b2;
188
le_not_nan_any a1 v; total_any a1 a2; lt_le_any a2 a1 in
189
let lemma below (v: t) : unit
190
ensures { in_iv v a2 b2 /\ mem_u v d1 -> not (in_iv v a1 b1) }
191
= lt_not_le_any b1 v in {qed}
192
Cons (a, b1) r
193
end
194
end
195
end

No float in both lists

  Valid (458ms) (colibri2 11) (cvc5 2) (split_vc) (depth 1)
198
let rec
is_distinct_u
(ghost fm: format) (l1 l2: list (t, t)) : bool
199
requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }
200
ensures { result <-> forall v. not (mem_u v l1 /\ mem_u v l2) }
201
variant { length l1 + length l2 }
202
= match l1, l2 with
203
| Nil, _ | _, Nil -> true
204
| Cons (a1, b1) d1, Cons (a2, b2) d2 ->
205
if lt_diff_zero b1 a2 then begin
206
{proof…} sorted_above b1 l2;
207
let lemma pt (v: t) : unit
208
ensures { in_iv v a1 b1 -> not (mem_u v l2) }
209
= lt_not_le_any b1 v in {qed}
210
is_distinct_u fm d1 l2
211
end else if lt_diff_zero b2 a1 then begin
212
{proof…} sorted_above b2 l1;
213
let lemma pt (v: t) : unit
214
ensures { in_iv v a2 b2 -> not (mem_u v l1) }
215
= lt_not_le_any b2 v in {qed}
216
is_distinct_u fm l1 d2
217
end else begin
218
{proof…} le_not_nan_any a1 b1; le_not_nan_any a2 b2;
219
let ghost a = max_diff_zero a1 a2 in
220
total_any b1 a2; total_any b2 a1; le_refl_any a;
221
le_trans_any a a1 b1; le_trans_any a a2 b2;
222
assert { in_iv a a1 b1 /\ in_iv a a2 b2 }; {qed}
223
false
224
end
225
end
226
227
predicate
incl_u
(l1 l2: list (t, t)) = forall v. mem_u v l1 -> mem_u v l2

Inclusion. When the interval of l1 goes beyond the one of l2, the rest of it starts at the successor: the next interval of l2 may start there (adjacent intervals).

  Valid (559ms) (colibri2 59) (cvc4 4) (cvc5 6) (split_vc 8) (depth 4)
232
let rec
is_included_u
(ghost fm: format) (l1 l2: list (t, t)) : bool
233
requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }
234
ensures { result <-> incl_u l1 l2 }
235
variant { length l1 + length l2 }
236
= match l1, l2 with
237
| Nil, _ -> true
238
| Cons _ _, Nil ->
239
{proof…} head_mem l1; assert { not incl_u l1 l2 }; {qed} false
240
| Cons (a1, b1) d1, Cons (a2, b2) d2 ->
241
{proof…} head_mem l1; le_not_nan_any a1 b1; le_not_nan_any a2 b2; {qed}
242
if lt_diff_zero b1 a2 then begin
243
{proof…} sorted_above b1 l2; lt_not_le_any b1 a1;
244
assert { not incl_u l1 l2 }; {qed}
245
false
246
end else if lt_diff_zero b2 a1 then begin
247
{proof…} sorted_above b2 l1;
248
let lemma pt (v: t) : unit
249
ensures { mem_u v l1 -> not (in_iv v a2 b2) }
250
= lt_not_le_any b2 v in
251
assert { incl_u l1 l2 <-> incl_u l1 d2 }; {qed}
252
is_included_u fm l1 d2
253
end else if le_diff_zero b2 b1 then begin
254
{proof…}
255
(match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end);
256
{qed}
257
if not (le_diff_zero a2 a1) then begin
258
{proof…} total a2 a1; lt_le_trans_any a1 a2 b2;
259
lt_not_le_any a1 a2;
260
assert { not (mem_u a1 d2) by forall v. mem_u v d2 -> lt_dz b2 v };
261
assert { not incl_u l1 l2 }; {qed}
262
false
263
end else if le_diff_zero b1 b2 then begin
264
{proof…}
265
(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);
266
let lemma pt (v: t) : unit
267
ensures { mem_u v d1 -> not (in_iv v a2 b2) /\ not (in_iv v a1 b1) }
268
= lt_not_le_any b1 v in
269
let lemma pt2 (v: t) : unit
270
ensures { in_iv v a1 b1 -> in_iv v a2 b2 }
271
= le_trans_any a2 a1 v; le_trans_any v b1 b2 in
272
let lemma dir1 (v: t) : unit
273
requires { incl_u l1 l2 /\ mem_u v d1 } ensures { mem_u v d2 }
274
= assert { mem_u v l1 } in
275
let lemma dir2 (v: t) : unit
276
requires { incl_u d1 d2 /\ mem_u v l1 } ensures { mem_u v l2 }
277
= () in
278
assert { incl_u l1 l2 <-> incl_u d1 d2 }; {qed}
279
is_included_u fm d1 d2
280
end else begin
281
{proof…}
282
total b1 b2; succ_gt b2; succ_least b2 b1;
283
let ghost s = succ_dz b2 in
284
(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);
285
let lemma pt (v: t) : unit
286
ensures { mem_u v d1 -> not (in_iv v a2 b2) /\ lt_dz b1 v }
287
= lt_not_le_any b1 v; le_lt_trans_any v b2 b1 in
288
let lemma pt_up (v: t) : unit
289
ensures { in_iv v s b1 -> in_iv v a1 b1 /\ not (in_iv v a2 b2) }
290
= lt_le_trans_any b2 s v; lt_not_le_any b2 v;
291
le_trans_any a1 b2 v; lt_le_any b2 v; total_any a1 b2 in
292
let lemma pt_split (v: t) : unit
293
ensures { in_iv v a1 b1 -> in_iv v a2 b2 \/ in_iv v s b1 }
294
= le_trans_any a2 a1 v; le_not_nan_any a1 v; total_any v b2;
295
if pure { in_iv v a1 b1 /\ lt_dz b2 v } then succ_least b2 v in
296
let lemma dir1 (v: t) : unit
297
requires { incl_u l1 l2 /\ mem_u v (Cons (s, b1) d1) }
298
ensures { mem_u v d2 }
299
= assert { mem_u v l1 /\ not (in_iv v a2 b2) } in
300
let lemma dir2 (v: t) : unit
301
requires { incl_u (Cons (s, b1) d1) d2 /\ mem_u v l1 }
302
ensures { mem_u v l2 }
303
= if pure { in_iv v a1 b1 } then begin
304
if pure { in_iv v s b1 } then assert { mem_u v d2 }
305
end else assert { mem_u v d2 } in
306
assert { incl_u l1 l2 <-> incl_u (Cons (s, b1) d1) d2 }; {qed}
307
is_included_u fm (Cons (succ_diff_zero b2, b1) d1) d2
308
end
309
end else begin
310
{proof…} total b2 b1; total a2 a1;
311
(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);
312
(match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end);
313
let lemma not_first () : unit
314
requires { not (le_dz a2 a1) } ensures { not (mem_u a1 l2) }
315
= lt_not_le_any a1 a2; lt_le_trans_any a1 a2 b2;
316
assert { forall v. mem_u v d2 -> lt_dz b2 v } in
317
let lemma dir1 (v: t) : unit
318
requires { incl_u l1 l2 /\ mem_u v d1 } ensures { mem_u v l2 }
319
= assert { mem_u v l1 } in
320
let lemma dir2 (v: t) : unit
321
requires { le_dz a2 a1 /\ incl_u d1 l2 /\ mem_u v l1 }
322
ensures { mem_u v l2 }
323
= () in
324
let lemma pt (v: t) : unit
325
ensures { in_iv v a1 b1 -> le_dz a2 a1 -> in_iv v a2 b2 }
326
= le_trans_any a2 a1 v; lt_le_any b1 b2; le_trans_any v b1 b2 in
327
assert { not (le_dz a2 a1) -> not incl_u l1 l2 };
328
assert { le_dz a2 a1 -> (incl_u l1 l2 <-> incl_u d1 l2) }; {qed}
329
le_diff_zero a2 a1 && is_included_u fm d1 l2
330
end
331
end
332
333
predicate
diff_spec
(r l1 l2: list (t, t)) =
334
forall v. mem_u v r <-> mem_u v l1 /\ not mem_u v l2

A list included in l is above everything l is above

  Valid (26ms) (colibri2)
337
let ghost
sub_above
(x: t) (r l: list (t, t)) : unit
338
requires { ok_u r /\ above x l /\ forall v. mem_u v r -> mem_u v l }
339
ensures { match r with Nil -> true | Cons (a, _) _ -> lt_dz x a end }
340
= {proof…} head_mem r {qed}

The difference. The parts of l1 that remain end at the predecessor of an interval of l2, or start at the successor of its end.

  Valid (1.4s) (colibri2 62) (cvc4) (cvc5 11) (split_vc 11) (depth 5)
344
let rec
diff_u
(ghost fm: format) (l1 l2: list (t, t)) : list (t, t)
345
requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }
346
ensures { ok_u result /\ fmt_u fm result /\ diff_spec result l1 l2 }
347
variant { length l1 + length l2 }
348
= match l1, l2 with
349
| Nil, _ -> Nil
350
| Cons _ _, Nil -> l1
351
| Cons (a1, b1) d1, Cons (a2, b2) d2 ->
352
{proof…} le_not_nan_any a1 b1; le_not_nan_any a2 b2;
353
(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);
354
(match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end);
355
{qed}
356
if lt_diff_zero b1 a2 then begin
357
let r = diff_u fm d1 l2 in
358
{proof…} sorted_above b1 l2; sub_above b1 r d1;
359
let lemma pt (v: t) : unit
360
ensures { in_iv v a1 b1 -> not (mem_u v l2) }
361
= lt_not_le_any b1 v in
362
let lemma pt2 (v: t) : unit
363
ensures { mem_u v d1 -> not (in_iv v a1 b1) }
364
= lt_not_le_any b1 v in
365
assert { diff_spec (Cons (a1, b1) r) l1 l2 }; {qed}
366
Cons (a1, b1) r
367
end else if lt_diff_zero b2 a1 then begin
368
{proof…} sorted_above b2 l1;
369
let lemma pt (v: t) : unit
370
ensures { mem_u v l1 -> not (in_iv v a2 b2) }
371
= lt_not_le_any b2 v in {qed}
372
diff_u fm l1 d2
373
end else begin
374
let r =
375
if le_diff_zero b2 b1 then begin
376
if le_diff_zero b1 b2 then begin
377
let r = diff_u fm d1 d2 in
378
{proof…}
379
let lemma pt (v: t) : unit
380
ensures { mem_u v d1 -> not (in_iv v a2 b2) /\ not (in_iv v a1 b1) }
381
= lt_not_le_any b1 v in
382
let lemma pt2 (v: t) : unit
383
ensures { mem_u v d2 -> not (in_iv v a1 b1) }
384
= lt_not_le_any b2 v in
385
assert { forall v. mem_u v r ->
386
mem_u v l1 /\ not mem_u v l2 /\ lt_dz b2 v };
387
assert { forall v. mem_u v l1 /\ not mem_u v l2 ->
388
(lt_dz v a2 \/ mem_u v r) };
389
{qed}
390
r
391
end else begin
392
{proof…} total b1 b2; succ_gt b2; succ_least b2 b1; {qed}
393
let l1' = Cons (succ_diff_zero b2, b1) d1 in
394
let r = diff_u fm l1' d2 in
395
{proof…}
396
let ghost s = succ_dz b2 in
397
let lemma pt (v: t) : unit
398
ensures { mem_u v d1 -> not (in_iv v a2 b2) /\ lt_dz b1 v }
399
= lt_not_le_any b1 v; le_lt_trans_any v b2 b1 in
400
let lemma pt_up (v: t) : unit
401
ensures { in_iv v s b1 -> in_iv v a1 b1 /\ not (in_iv v a2 b2) /\ lt_dz b2 v }
402
= lt_le_trans_any b2 s v; lt_not_le_any b2 v;
403
le_trans_any a1 b2 v; lt_le_any b2 v; total_any a1 b2 in
404
let lemma pt_split (v: t) : unit
405
ensures { in_iv v a1 b1 -> lt_dz v a2 \/ in_iv v a2 b2 \/ in_iv v s b1 }
406
= le_not_nan_any a1 v; total_any v b2; total_any a2 v;
407
if pure { in_iv v a1 b1 /\ lt_dz b2 v } then succ_least b2 v in
408
let lemma pt2 (v: t) : unit
409
ensures { mem_u v d2 -> lt_dz b2 v }
410
= () in
411
assert { forall v. mem_u v r ->
412
mem_u v l1 /\ not mem_u v l2 /\ lt_dz b2 v };
413
assert { forall v. mem_u v l1 /\ not mem_u v l2 ->
414
(lt_dz v a2 \/ mem_u v r) };
415
{qed}
416
r
417
end
418
end else begin
419
let r = diff_u fm d1 l2 in
420
{proof…} total b2 b1;
421
let lemma pt (v: t) : unit
422
ensures { mem_u v d1 -> lt_dz b1 v }
423
= () in
424
let lemma pt2 (v: t) : unit
425
ensures { in_iv v a1 b1 -> not (mem_u v d2) }
426
= lt_le_any b1 b2; le_lt_trans_any v b1 b2;
427
assert { forall w. mem_u w d2 -> lt_dz b2 w };
428
lt_not_le_any v b2 in
429
let lemma pt3 (v: t) : unit
430
ensures { in_iv v a1 b1 -> not (in_iv v a2 b2) -> lt_dz v a2 }
431
= le_not_nan_any a1 v; total_any a2 v; lt_le_any b1 b2;
432
le_trans_any v b1 b2 in
433
assert { forall v. mem_u v r ->
434
mem_u v l1 /\ not mem_u v l2 /\ lt_dz b1 v };
435
assert { forall v. mem_u v l1 /\ not mem_u v l2 ->
436
(lt_dz v a2 \/ mem_u v r) };
437
{qed}
438
r
439
end in
440
{proof…}
441
assert { forall v. mem_u v r -> lt_dz a2 v
442
by lt_dz b1 v \/ lt_dz b2 v };
443
{qed}
444
if lt_diff_zero a1 a2 then begin
445
{proof…}
446
pred_lt a2; pred_greatest a2 a1;
447
let ghost p = pred_dz a2 in
448
let lemma pt (v: t) : unit
449
requires { in_iv v a1 p }
450
ensures { mem_u v l1 /\ not mem_u v l2 /\ lt_dz v a2 }
451
= le_lt_trans v p a2; lt_not_le v a2;
452
lt_le_trans v a2 b2; lt_not_le v b2;
453
assert { not (mem_u v d2) by forall w. mem_u w d2 -> lt_dz b2 w
454
so (forall w. lt_dz b2 w -> w <> v) };
455
total_any v b1 in
456
let lemma pt2 (v: t) : unit
457
requires { mem_u v l1 /\ lt_dz v a2 }
458
ensures { in_iv v a1 p }
459
= pred_greatest a2 v; total_any b1 a2;
460
assert { not (mem_u v d1) by forall w. mem_u w d1 -> lt_dz b1 w };
461
lt_le_any v a2 in
462
assert { forall v. mem_u v r -> lt_dz p v by lt_dz p a2 /\ lt_dz a2 v };
463
(match r with Nil -> () | Cons _ _ -> head_mem r end);
464
{qed}
465
Cons (a1, pred_diff_zero a2) r
466
end else begin
467
{proof…} total a2 a1;
468
let lemma pt (v: t) : unit
469
ensures { mem_u v l1 -> not (lt_dz v a2) }
470
= assert { forall w. mem_u w d1 -> lt_dz b1 w };
471
le_trans_any a2 a1 v; lt_not_le_any v a2 in
472
{qed}
473
r
474
end
475
end
476
end
477
478
predicate
disj_u
(l1 l2: list (t, t)) = forall v. not (mem_u v l1 /\ mem_u v l2)
479
480
type
comparison
=
Uncomparable
|
Included
|
Disjoint

Included, disjoint or neither, for a non–empty l1

  Valid (590ms) (colibri2 16) (cvc4 2) (cvc5 5) (split_vc) (depth 1)
483
let rec
is_distinct_or_included_u
(ghost fm: format) (l1 l2: list (t, t)) : comparison
484
requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 /\ l1 <> Nil }
485
ensures { result = Included <-> incl_u l1 l2 }
486
ensures { result = Disjoint <-> disj_u l1 l2 }
487
variant { l2 }
488
= match l1, l2 with
489
| Nil, _ -> absurd
490
| Cons _ _, Nil -> {proof…} head_mem l1; {qed} Disjoint
491
| Cons (a1, b1) d1, Cons (a2, b2) d2 ->
492
{proof…} head_mem l1; le_not_nan_any a1 b1; le_not_nan_any a2 b2; {qed}
493
if lt_diff_zero b1 a2 then begin
494
{proof…} sorted_above b1 l2; lt_not_le_any b1 a1;
495
let lemma pt (v: t) : unit
496
ensures { in_iv v a1 b1 -> not (mem_u v l2) }
497
= lt_not_le_any b1 v in
498
assert { not incl_u l1 l2 };
499
assert { disj_u l1 l2 <-> disj_u d1 l2 }; {qed}
500
if is_distinct_u fm d1 l2 then Disjoint else Uncomparable
501
end else if lt_diff_zero b2 a1 then begin
502
{proof…} sorted_above b2 l1;
503
let lemma pt (v: t) : unit
504
ensures { mem_u v l1 -> not (in_iv v a2 b2) }
505
= lt_not_le_any b2 v in
506
assert { incl_u l1 l2 <-> incl_u l1 d2 };
507
assert { disj_u l1 l2 <-> disj_u l1 d2 }; {qed}
508
is_distinct_or_included_u fm l1 d2
509
end else begin
510
{proof…}
511
let ghost a = max_diff_zero a1 a2 in
512
total_any b1 a2; total_any b2 a1; le_refl_any a;
513
le_trans_any a a1 b1; le_trans_any a a2 b2;
514
assert { in_iv a a1 b1 /\ in_iv a a2 b2 };
515
assert { not disj_u l1 l2 }; {qed}
516
if is_included_u fm l1 l2 then Included else Uncomparable
517
end
518
end
519
end