Common — library colibrilib.zinterval — module Zi
9
module Zi
10
use int.Int
11
use option.Option

lo <= z <= hi, None an infinite bound

14
type
t
= {
lo
: option int;
hi
: option int }
15
16
predicate
mem_lo
(z: int) (l: option int) =
17
match l with None -> true | Some k -> k <= z end
18
predicate
mem_hi
(z: int) (h: option int) =
19
match h with None -> true | Some k -> z <= k end
20
21
predicate
mem
(z: int) (i: t) = mem_lo z i.lo /\ mem_hi z i.hi
22
23
let function
mk
(lo hi: option int) : t = { lo = lo; hi = hi }

All the integers

26
let constant
top
: t = { lo = None; hi = None }
27
Valid (16ms) (colibri2)
28
let ghost
mem_top
(z: int) : unit
29
ensures { mem z top }
30
= ()

The meet

34
let function
max_lo
(a b: option int) : option int =
35
match a, b with
36
| None, x | x, None -> x
37
| Some x, Some y -> Some (if x <= y then y else x)
38
end
39
40
let function
min_hi
(a b: option int) : option int =
41
match a, b with
42
| None, x | x, None -> x
43
| Some x, Some y -> Some (if x <= y then x else y)
44
end
45
46
let function
inter
(a b: t) : t = { lo = max_lo a.lo b.lo; hi = min_hi a.hi b.hi }
47
Valid (63ms) (colibri2)
48
let ghost
mem_inter
(z: int) (a b: t) : unit
49
ensures { mem z (inter a b) <-> mem z a /\ mem z b }
50
= ()

The reverse: the interval of - z

54
let function
neg_o
(o: option int) : option int =
55
match o with None -> None | Some k -> Some (- k) end
56
57
let function
rev
(a: t) : t = { lo = neg_o a.hi; hi = neg_o a.lo }
58
Valid (30ms) (colibri2)
59
let ghost
mem_rev
(z: int) (a: t) : unit
60
ensures { mem (- z) (rev a) <-> mem z a }
61
= ()
62
Valid (15ms) (colibri2)
63
let ghost
rev_rev
(a: t) : unit
64
ensures { rev (rev a) = a }
65
= match a.lo with None -> () | Some _ -> () end;
66
match a.hi with None -> () | Some _ -> () end

The sum: x + y, x in a and y in b

70
let function
add_o
(a b: option int) : option int =
71
match a, b with
72
| Some x, Some y -> Some (x + y)
73
| _ -> None
74
end
75
76
let function
add
(a b: t) : t = { lo = add_o a.lo b.lo; hi = add_o a.hi b.hi }
77
Valid (33ms) (colibri2)
78
let ghost
mem_add
(x y: int) (a b: t) : unit
79
requires { mem x a /\ mem y b }
80
ensures { mem (x + y) (add a b) }
81
= ()

Emptiness, inclusion, equality

85
let function
is_empty
(a: t) : bool =
86
match a.lo, a.hi with
87
| Some l, Some h -> h < l
88
| _ -> false
89
end
90
Valid (29ms) (colibri2)
91
let ghost
is_empty_spec
(a: t) : unit
92
ensures { is_empty a <-> forall z. not mem z a }
93
= match a.lo, a.hi with
94
| Some l, Some _ -> assert { not is_empty a -> mem l a }
95
| Some l, None -> assert { mem l a }
96
| None, Some h -> assert { mem h a }
97
| None, None -> assert { mem 0 a }
98
end

The bound l is implied by l': every integer above l' is above l

102
let function
le_lo
(l l': option int) : bool =
103
match l, l' with
104
| None, _ -> true
105
| Some _, None -> false
106
| Some x, Some y -> x <= y
107
end
108
109
let function
ge_hi
(h h': option int) : bool =
110
match h, h' with
111
| None, _ -> true
112
| Some _, None -> false
113
| Some x, Some y -> y <= x
114
end

a is included in b

117
let function
incl
(a b: t) : bool =
118
is_empty a || (le_lo b.lo a.lo && ge_hi b.hi a.hi)

A member of a non–empty a at most k, when the lower bound of a is at most k

  Valid (18ms) (colibri2)
122
let ghost
low_wit
(a: t) (k: int) : int
123
requires { not is_empty a /\ mem_lo k a.lo }
124
ensures { mem result a /\ result <= k }
125
= match a.hi with
126
| Some h -> if h < k then (is_empty_spec a; h) else k
127
| None -> k
128
end
129
Valid (13ms) (colibri2)
130
let ghost
high_wit
(a: t) (k: int) : int
131
requires { not is_empty a /\ mem_hi k a.hi }
132
ensures { mem result a /\ k <= result }
133
= match a.lo with
134
| Some l -> if k < l then l else k
135
| None -> k
136
end
137
Valid (30ms) (colibri2 9) (cvc5) (split_vc 4) (depth 3)
138
let ghost
incl_spec
(a b: t) : unit
139
ensures { incl a b <-> forall z. mem z a -> mem z b }
140
= {proof…}
141
is_empty_spec a;
142
if not is_empty a && not (le_lo b.lo a.lo) then begin
143
match b.lo with
144
| Some l -> let w = low_wit a (l - 1) in assert { mem w a /\ not mem w b }
145
| None -> absurd
146
end
147
end;
148
if not is_empty a && not (ge_hi b.hi a.hi) then begin
149
match b.hi with
150
| Some h -> let w = high_wit a (h + 1) in assert { mem w a /\ not mem w b }
151
| None -> absurd
152
end
153
end
154
{qed}
155
156
let function
eq_o
(a b: option int) : bool =
157
match a, b with
158
| None, None -> true
159
| Some x, Some y -> x = y
160
| _ -> false
161
end
162
163
let function
equal
(a b: t) : bool = eq_o a.lo b.lo && eq_o a.hi b.hi
164
Valid (16ms) (colibri2)
165
let ghost
equal_spec
(a b: t) : unit
166
ensures { equal a b <-> a = b }
167
= ()
168
end