Common — library colibrilib.models — module SortedMap

The maps of polynome.PT and product.PT: the sorted lists of bindings, for any value type, with their length as a Peano number (mach.peano): the length of a map is bounded by the number of steps of the program that built it, so cardinal can return an int63 (Peano.to_int63 is partial).

35
module SortedMap
36
use int.Int
37
use mach.int.Int63
38
use mach.peano.Peano as P
39
use mach.peano.Int63 as PI
40
use list.List
41
use list.Length
42
use option.Option
43
use colibrilib.ring.Atom
44
45
type
value
46
47
type
binding
= (Atom.t, value)
48
49
function
assoc
(k:Atom.t) (l:list binding) : option value =
50
match l with
51
| Nil -> None
52
| Cons (k', v) r -> if k = k' then Some v else assoc k r
53
end
54
55
predicate
has
(k:Atom.t) (l:list binding) = assoc k l <> None
56
57
predicate
above
(k:Atom.t) (l:list binding) = forall k'. has k' l -> lt k k'
58
59
predicate
sorted
(l:list binding) =
60
match l with
61
| Nil -> true
62
| Cons (k, _) r -> above k r /\ sorted r
63
end
64
65
type
t
= {
l
: list binding;
n
: P.t }
66
invariant { sorted l /\ n.P.v = length l } Valid (17ms) (colibri2)
67
by { l = Nil; n = P.zero }
68
69
function
bindings
(m:t) : list binding = m.l
70
Valid (17ms) (colibri2)
71
let ghost
above_trans
(k1 k2:Atom.t) (l:list binding) : unit
72
requires { lt k1 k2 }
73
requires { above k2 l }
74
ensures { above k1 l }
75
= assert { forall k. has k l -> lt k1 k by lt k2 k }
76
Valid (18ms) (colibri2)
77
let ghost
above_not_has
(k:Atom.t) (l:list binding) : unit
78
requires { above k l }
79
ensures { assoc k l = None }
80
= assert { not (lt k k) }

Cons (k, v) t if o = Some v, else t, and its length

  Valid (25ms) (colibri2)
83
let
cons_opt
(k:Atom.t) (o:option value) (t:list binding) (n:P.t)
84
: (list binding, P.t)
85
requires { sorted t /\ above k t }
86
requires { n.P.v = length t }
87
returns { (r, rn) ->
88
sorted r /\ rn.P.v = length r /\
89
assoc k r = o /\
90
(forall k'. k' <> k -> assoc k' r = assoc k' t) /\
91
(forall k'. has k' r -> k' = k \/ has k' t) }
92
= above_not_has k t;
93
match o with
94
| None -> t, n
95
| Some v -> Cons (k, v) t, P.succ n
96
end
97
Valid (13ms) (colibri2)
98
let
empty
() : t
99
ensures { bindings result = Nil }
100
= { l = Nil; n = P.zero }
101
Valid (13ms) (colibri2)
102
let
is_empty
(m:t) : bool
103
ensures { result <-> bindings m = Nil }
104
= match m.l with Nil -> true | _ -> false end
105
Valid (13ms) (colibri2)
106
let
singleton
(k:Atom.t) (v:value) : t
107
ensures { bindings result = Cons (k, v) Nil }
108
= { l = Cons (k, v) Nil; n = P.one }
109
Valid (15ms) (colibri2)
110
let rec
find
(k:Atom.t) (l:list binding) : option value
111
ensures { result = assoc k l }
112
variant { l }
113
= match l with
114
| Nil -> None
115
| Cons (k', v) r -> if Atom.equal k k' then Some v else find k r
116
end
117
Valid (13ms) (colibri2)
118
let
find_opt
(k:Atom.t) (m:t) : option value
119
ensures { result = assoc k (bindings m) }
120
= find k m.l
121
Valid (58ms) (colibri2)
122
let rec
rem
(k:Atom.t) (l:list binding) : list binding
123
requires { sorted l }
124
ensures { sorted result }
125
ensures { forall k'. assoc k' result = if k' = k then None else assoc k' l }
126
ensures { forall k'. has k' result -> has k' l }
127
ensures { length result = if has k l then length l - 1 else length l }
128
variant { l }
129
= match l with
130
| Nil -> Nil
131
| Cons (k', v) r ->
132
if Atom.equal k k' then begin above_not_has k r; r end
133
else Cons (k', v) (rem k r)
134
end
135
Valid (20ms) (colibri2)
136
let
remove
(k:Atom.t) (m:t) : t
137
ensures { forall k'. assoc k' (bindings result)
138
= if k' = k then None else assoc k' (bindings m) }
139
= match find k m.l with
140
| None -> { l = rem k m.l; n = m.n }
141
| Some _ -> { l = rem k m.l; n = P.pred m.n }
142
end
143
Valid (12ms) (colibri2)
144
let
cardinal
(m:t) : int
145
ensures { result = length (bindings m) }
146
= P.to_int m.n
147
Valid (22ms) (colibri2)
148
let partial
cardinal63
(m:t) : int63
149
ensures { to_int result = length (bindings m) }
150
= PI.to_int63 m.n
151
Valid (11ms) (colibri2)
152
let
to_list
(m:t) : list binding
153
ensures { result = bindings m }
154
= m.l
155
Valid (13ms) (colibri2)
156
let
some_binding
(m:t) : (Atom.t, value)
157
requires { bindings m <> Nil }
158
returns { (k, v) -> assoc k (bindings m) = Some v }
159
= match m.l with
160
| Nil -> absurd
161
| Cons (k, v) _ -> (k, v)
162
end
163
Valid (1.3s) (colibri2 31) (cvc5) (split_vc) (depth 1)
164
let rec
mrg
(f: Atom.t -> option value -> option value -> option value)
165
(l1 l2:list binding) : (list binding, P.t)
166
requires { sorted l1 /\ sorted l2 }
167
requires { forall k. f k None None = None }
168
returns { (r, rn) ->
169
sorted r /\ rn.P.v = length r /\
170
(forall k. has k r -> has k l1 \/ has k l2) /\
171
(forall k. assoc k r = f k (assoc k l1) (assoc k l2)) }
172
variant { l1, l2 }
173
= match l1, l2 with
174
| Nil, Nil -> Nil, P.zero
175
| Cons (k, a) r, Nil ->
176
let t, n = mrg f r Nil in cons_opt k (f k (Some a) None) t n
177
| Nil, Cons (k, b) r ->
178
let t, n = mrg f Nil r in cons_opt k (f k None (Some b)) t n
179
| Cons (k1, a) r1, Cons (k2, b) r2 ->
180
let c = Atom.compare k1 k2 in
181
if c < 0 then begin
182
above_trans k1 k2 r2;
183
above_not_has k1 l2;
184
let t, n = mrg f r1 l2 in cons_opt k1 (f k1 (Some a) None) t n
185
end else if c > 0 then begin
186
above_trans k2 k1 r1;
187
above_not_has k2 l1;
188
let t, n = mrg f l1 r2 in cons_opt k2 (f k2 None (Some b)) t n
189
end else begin
190
let t, n = mrg f r1 r2 in cons_opt k1 (f k1 (Some a) (Some b)) t n
191
end
192
end
193
Valid (15ms) (colibri2)
194
let
merge
(f: Atom.t -> option value -> option value -> option value) (m1 m2:t) : t
195
requires { forall k. f k None None = None }
196
ensures { forall k. assoc k (bindings result)
197
= f k (assoc k (bindings m1)) (assoc k (bindings m2)) }
198
= let r, n = mrg f m1.l m2.l in { l = r; n = n }
199
Valid (144ms) (cvc5)
200
let rec
ins
(k:Atom.t) (v:value) (l:list binding) : list binding
201
requires { sorted l }
202
ensures { sorted result }
203
ensures { forall k'. assoc k' result = if k' = k then Some v else assoc k' l }
204
ensures { forall k'. has k' result -> k' = k \/ has k' l }
205
ensures { length result = if has k l then length l else length l + 1 }
206
variant { l }
207
= match l with
208
| Nil -> Cons (k, v) Nil
209
| Cons (k', w) r ->
210
let c = Atom.compare k k' in
211
if c < 0 then begin above_trans k k' r; above_not_has k l; Cons (k, v) l end
212
else if c = 0 then begin above_not_has k r; Cons (k, v) r end
213
else Cons (k', w) (ins k v r)
214
end
215
Valid (21ms) (colibri2)
216
let
update
(k:Atom.t) (f: option value -> option value) (m:t) : t
217
ensures { forall k'. assoc k' (bindings result)
218
= if k' = k then f (assoc k (bindings m)) else assoc k' (bindings m) }
219
= let o = find k m.l in
220
match f o, o with
221
| None, None -> m
222
| None, Some _ -> { l = rem k m.l; n = P.pred m.n }
223
| Some v, None -> { l = ins k v m.l; n = P.succ m.n }
224
| Some v, Some _ -> { l = ins k v m.l; n = m.n }
225
end
226
Valid (325ms) (colibri2)
227
let rec
mp
(f: value -> value) (l:list binding) : list binding
228
requires { sorted l }
229
ensures { sorted result }
230
ensures { length result = length l }
231
ensures { forall k. has k result <-> has k l }
232
ensures { forall k. assoc k result = match assoc k l with
233
| None -> None | Some v -> Some (f v) end }
234
variant { l }
235
= match l with
236
| Nil -> Nil
237
| Cons (k, v) r -> Cons (k, f v) (mp f r)
238
end
239
Valid (18ms) (colibri2)
240
let
map
(f: value -> value) (m:t) : t
241
ensures { forall k. assoc k (bindings result) = match assoc k (bindings m) with
242
| None -> None | Some v -> Some (f v) end }
243
= { l = mp f m.l; n = m.n }
244
Valid (72ms) (colibri2)
245
let rec
flt
(f: Atom.t -> bool) (l:list binding) : (list binding, P.t)
246
requires { sorted l }
247
returns { (r, rn) ->
248
sorted r /\ rn.P.v = length r /\
249
(forall k. has k r -> has k l) /\
250
(forall k. assoc k r = if f k then assoc k l else None) }
251
variant { l }
252
= match l with
253
| Nil -> Nil, P.zero
254
| Cons (k, v) r ->
255
above_not_has k r;
256
let t, n = flt f r in
257
if f k then Cons (k, v) t, P.succ n else t, n
258
end
259
Valid (17ms) (colibri2)
260
let
filter
(f: Atom.t -> bool) (m:t) : t
261
ensures { forall k. assoc k (bindings result)
262
= if f k then assoc k (bindings m) else None }
263
= let r, n = flt f m.l in { l = r; n = n }
264
end