Common — library colibrilib.sbdd — module VBDD
1
module VBDD

Implemented

2
use set.Set
3
use map.MapExt
4
use bool.Bool
5
use colibrilib.bdd.CVar
6
use colibrilib.bdd.CCube
7
use colibrilib.bdd.Var
8
use colibrilib.bdd.Key
9
use colibrilib.bdd.BDD
10
use int.Int
11
use list.List
12
use list.Mem
13
use list.Distinct

A BDD on the variables of the keys of the prophecy Var.keys

    Valid (12ms) (colibri2)
16
type
t
= {
17
b
: BDD.t;
18
} invariant { forall y. Set.mem y b.BDD.dom -> Set.mem (key_of_var y) keys }
19
by { b = BDD.dfalse () }

The cubes of variables as cubes of keys: on keys only

22
scope Cube
23
type
a
= Set.set CVar.t
24
type
b
= Set.set Key.t
25
function
to_
(x: a) : b = fun k -> Set.mem k keys /\ x (var_of_key k)
26
function
of_
(y: b) : a = fun v -> y (key_of_var v)
27
end
28
29
scope Value
30
type
a
= Set.set Cube.a
31
type
b
= Set.set Cube.b
32
function
to_
(f: a) : b = fun c -> f (Cube.of_ c)
33
end
34
35
function
dom
(x:t) : Cube.b = Cube.to_ x.b.BDD.dom
36
function
v
(x:t): Value.b = Value.to_ x.b.BDD.v
37
function
get_cube
(x:t) : Cube.b = Cube.to_ x.b.BDD.get_cube
38
function
support
(a:t) : Cube.b = Cube.to_ (BDD.support a.b)

x only reads the variables of the keys

    Valid (27ms) (colibri2)
41
let ghost
v_keys
(x: t) (w1 w2: Cube.a) : unit
42
requires { forall y. Set.mem (key_of_var y) keys -> (Set.mem y w1 <-> Set.mem y w2) }
43
ensures { x.b.BDD.v w1 = x.b.BDD.v w2 }
44
= BDD.invariant_outside_domain x.b
45
Valid (26ms) (colibri2)
46
let ghost
v_of_to
(x: t) (w: Cube.a) : unit
47
ensures { x.b.BDD.v (Cube.of_ (Cube.to_ w)) = x.b.BDD.v w }
48
= v_keys x (Cube.of_ (Cube.to_ w)) w
49
Valid (324ms) (cvc4)
50
lemma
to_union
: forall x y: Cube.a. Cube.to_ (Set.union x y) = Set.union (Cube.to_ x) (Cube.to_ y) Valid (656ms) (cvc4)
51
lemma
to_diff
: forall x y: Cube.a. Cube.to_ (Set.diff x y) = Set.diff (Cube.to_ x) (Cube.to_ y) Valid (16ms) (colibri2)
52
lemma
to_empty
: Cube.to_ (Set.empty: Cube.a) = (Set.empty: Cube.b) Valid (17ms) (colibri2 4) (split_vc) (depth 1)
53
let lemma
to_subset
(x y: Cube.a) : unit
54
requires { Set.subset x y }
55
ensures { Set.subset (Cube.to_ x) (Cube.to_ y) }
56
= assert { forall k. Set.mem k (Cube.to_ x) -> Set.mem k keys /\ Set.mem (var_of_key k) x };
57
assert { forall k. Set.mem k keys -> Set.mem (var_of_key k) y -> Set.mem k (Cube.to_ y) };
58
assert { forall k. Set.mem k (Cube.to_ x) -> Set.mem k (Cube.to_ y) }
59
Valid (35ms) (cvc4)
60
let ghost
to_add
(x: Key.t) (d: Cube.a) : unit
61
requires { Set.mem x keys }
62
ensures { Cube.to_ (Set.add (var_of_key x) d) = Set.add x (Cube.to_ d) }
63
= assert { forall k. Set.mem k keys -> var_of_key k = var_of_key x -> k = x }
64
Valid (37ms) (cvc4)
65
let ghost
to_remove
(x: Key.t) (d: Cube.a) : unit
66
requires { Set.mem x keys }
67
ensures { Cube.to_ (Set.remove (var_of_key x) d) = Set.remove x (Cube.to_ d) }
68
= assert { forall k. Set.mem k keys -> var_of_key k = var_of_key x -> k = x }
69
Valid (14ms) (colibri2)
70
let ghost
to_singleton
(x: Key.t) : unit
71
requires { Set.mem x keys }
72
ensures { Cube.to_ (Set.singleton (var_of_key x)) = Set.singleton x }
73
= to_add x Set.empty
74
Valid (21ms) (colibri2)
75
let ghost
of_add
(x: Key.t) (c: Cube.b) : unit
76
requires { Set.mem x keys }
77
ensures { Cube.of_ (Set.add x c) = Set.add (var_of_key x) (Cube.of_ c) }
78
= assert { forall y. key_of_var y = x -> y = var_of_key x }
79
Valid (22ms) (colibri2)
80
let ghost
of_remove
(x: Key.t) (c: Cube.b) : unit
81
requires { Set.mem x keys }
82
ensures { Cube.of_ (Set.remove x c) = Set.remove (var_of_key x) (Cube.of_ c) }
83
= assert { forall y. key_of_var y = x -> y = var_of_key x }
84
Valid (20ms) (colibri2)
85
let ghost
of_map_set
(c: Cube.b) (x: Key.t) (b: bool) : unit
86
requires { Set.mem x keys }
87
ensures { Cube.of_ (Map.set c x b) = Map.set (Cube.of_ c) (var_of_key x) b }
88
= assert { forall y. key_of_var y = x -> y = var_of_key x }

The cubes of the domain of a BDD come back

    Valid (401ms) (cvc4 3) (split_vc) (depth 1)
91
let ghost
of_to_dom
(x: t) : unit
92
ensures { Cube.of_ x.dom = x.b.BDD.dom }
93
ensures { Cube.of_ (support x) = BDD.support x.b }
94
= assert { forall y. Set.mem y (BDD.support x.b) -> Set.mem y x.b.BDD.dom }
95
Valid (4.4s) (colibri2 4) (cvc4) (split_vc) (depth 1)
96
let
dand
(x y: t) : t
97
ensures { result.dom = Set.union x.dom y.dom }
98
ensures { result.v = Set.inter x.v y.v }
99
ensures { BDD.is_cube x.b -> BDD.is_cube y.b ->
100
Set.subset (BDD.get_cube x.b) (BDD.support x.b) ->
101
Set.subset (BDD.get_cube y.b) (BDD.support y.b) ->
102
Set.inter (BDD.support x.b) (BDD.support y.b) = Set.empty ->
103
BDD.is_cube result.b /\
104
BDD.get_cube result.b = Set.union (BDD.get_cube x.b) (BDD.get_cube y.b) /\
105
BDD.support result.b = Set.union (BDD.support x.b) (BDD.support y.b) } =
106
let res = { b = BDD.dand x.b y.b } in
107
assert { forall c. Set.mem c res.v <-> Set.mem c (Set.inter x.v y.v) };
108
res
109
Valid (764ms) (cvc4)
110
let
dor
(x y: t) : t
111
ensures { result.dom = Set.union x.dom y.dom }
112
ensures { result.v = Set.union x.v y.v } =
113
{ b = BDD.dor x.b y.b }
114
115
(* From OCaml module Var: a variable viewed as a BDD (Var.bdd). *) Valid (70ms) (colibri2 17) (cvc4 2) (split_vc 2) (depth 2)
116
let partial
bdd_of_var
(v: Key.t) : t
117
ensures { Set.mem v keys }
118
ensures { result.dom = Set.singleton v }
119
ensures { result.v = (fun c -> c v) }
120
ensures { support result = Set.singleton v }
121
ensures { BDD.is_support result.b }
122
=
123
let x = Var.of_key v in
124
let r = BDD.bdd_of_var x in
125
let lemma supp (y: CVar.t) : unit
126
ensures { Set.mem y (BDD.support r) <-> y = x }
127
= if pure { y = x } then assert { r.BDD.v (Set.add y Set.empty) <> r.BDD.v (Set.remove y Set.empty) }
128
in
129
assert { forall y. Set.mem y (Set.singleton x) <-> y = x };
130
assert { forall y. (BDD.support r) y = (Set.singleton x) y
131
by (Set.mem y (BDD.support r) <-> Set.mem y (Set.singleton x)) };
132
assert { MapExt.(==) (BDD.support r) (Set.singleton x) };
133
assert { BDD.support r = Set.singleton x };
134
let lemma cube (c: CCube.t) : unit
135
ensures { r.BDD.v c <-> Set.inter c (BDD.support r) = BDD.get_cube r }
136
= if Set.mem x c then assert { forall y. Set.mem y (Set.inter c (Set.singleton x)) <-> Set.mem y (Set.singleton x) }
137
else assert { not (Set.mem x (Set.inter c (Set.singleton x))) }
138
in
139
to_singleton v;
140
assert { Cube.to_ (BDD.support r) = Set.singleton v };
141
{ b = r }
142
143
(* From OCaml module Var: negation of a variable (Var.bdd_not). *) Valid (335ms) (colibri2 11) (cvc4 8) (split_vc 2) (depth 2)
144
let partial
bdd_not
(v: Key.t) : t
145
ensures { Set.mem v keys }
146
ensures { result.dom = Set.singleton v }
147
ensures { result.v = (fun c -> not (c v)) }
148
ensures { support result = Set.singleton v }
149
ensures { BDD.is_cube result.b /\ BDD.get_cube result.b = Set.empty }
150
=
151
let x = Var.of_key v in
152
let r = BDD.bdd_not_of_var x in
153
let lemma supp (y: CVar.t) : unit
154
ensures { Set.mem y (BDD.support r) <-> y = x }
155
= if pure { y = x } then assert { r.BDD.v (Set.add y Set.empty) <> r.BDD.v (Set.remove y Set.empty) }
156
in
157
assert { forall y. Set.mem y (Set.singleton x) <-> y = x };
158
assert { forall y. (BDD.support r) y = (Set.singleton x) y
159
by (Set.mem y (BDD.support r) <-> Set.mem y (Set.singleton x)) };
160
assert { MapExt.(==) (BDD.support r) (Set.singleton x) };
161
assert { BDD.support r = Set.singleton x };
162
let lemma cube (c: CCube.t) : unit
163
ensures { r.BDD.v c <-> Set.inter c (BDD.support r) = BDD.get_cube r }
164
= if Set.mem x c then assert { Set.mem x (Set.inter c (Set.singleton x)) }
165
else assert { forall y. not (Set.mem y (Set.inter c (Set.singleton x))) }
166
in
167
to_singleton v;
168
assert { Cube.to_ (BDD.support r) = Set.singleton v };
169
{ b = r }
170
171
(* From OCaml module BDD: false BDD (dom empty, v empty). *) Valid (60ms) (colibri2)
172
let
tfalse
() : t
173
ensures { result.dom = Set.empty }
174
ensures { result.v = Set.empty } =
175
{ b = BDD.dfalse () }
176
177
(* From OCaml module BDD: true BDD (dom empty, v all). *) Valid (630ms) (colibri2)
178
let
ttrue
() : t
179
ensures { result.dom = Set.empty }
180
ensures { result.v = Set.all }
181
ensures { support result = Set.empty }
182
ensures { BDD.is_support result.b }
183
=
184
let r = BDD.dtrue () in
185
assert { BDD.support r = Set.empty };
186
assert { forall c. Set.inter c (BDD.support r) = Set.empty };
187
{ b = r }
188
189
(* Cudd.Bdd.support_union *) Valid (228ms) (cvc4)
190
let
support_union
(x y: t) : t
191
requires { BDD.is_support x.b /\ BDD.is_support y.b }
192
ensures { result.dom = Set.union x.dom y.dom }
193
ensures { support result = Set.union (support x) (support y) }
194
ensures { BDD.is_support result.b }
195
= { b = BDD.support_union x.b y.b }
196
197
(* From OCaml module BDD: equality of BDDs (pointwise on satisfying cubes). *) Valid (30ms) (colibri2 5) (split_vc 2) (depth 2)
198
let
is_equal
(x y: t) : (result: bool, ghost c: Cube.b)
199
ensures { result = (forall c. x.v c = y.v c) }
200
ensures { not result ->
201
(Set.subset c (Set.union x.dom y.dom)) /\ x.v c <> y.v c } =
202
let (r, ghost w) = BDD.is_equal x.b y.b in
203
let ghost c = Cube.to_ w in
204
v_of_to x w; v_of_to y w;
205
let lemma all (w': Cube.a) : unit
206
requires { forall c. x.v c = y.v c }
207
ensures { x.b.BDD.v w' = y.b.BDD.v w' }
208
= v_of_to x w'; v_of_to y w'; assert { x.v (Cube.to_ w') = y.v (Cube.to_ w') }
209
in
210
(r, c)
211
212
(* From OCaml module BDD: emptiness of the intersection of two BDDs. *) Valid (50ms) (colibri2 6) (split_vc 2) (depth 2)
213
let
is_inter_empty
(x y: t) : (result: bool, ghost c: Cube.b)
214
ensures { result = (forall c. not (x.v c /\ y.v c)) }
215
ensures { not result ->
216
((Set.subset c (Set.union x.dom y.dom)) /\ (x.v c /\ y.v c)) } =
217
let (r, ghost w) = BDD.is_inter_empty x.b y.b in
218
let ghost c = Cube.to_ w in
219
v_of_to x w; v_of_to y w;
220
let lemma all (w': Cube.a) : unit
221
requires { forall c. not (x.v c /\ y.v c) }
222
ensures { not (x.b.BDD.v w' /\ y.b.BDD.v w') }
223
= v_of_to x w'; v_of_to y w'; assert { not (x.v (Cube.to_ w') /\ y.v (Cube.to_ w')) }
224
in
225
(r, c)
226
227
(* Exclusive union of two BDDs. *) Valid (548ms) (colibri2)
228
let
dxor
(x y: t) : t
229
ensures { result.dom = Set.union x.dom y.dom }
230
ensures { result.v = (fun c -> xorb (x.v c) (y.v c)) } =
231
let res = { b = BDD.dxor x.b y.b } in
232
let lemma pointwise (c: Cube.b) : unit
233
ensures { res.v c = xorb (x.v c) (y.v c) }
234
= assert { res.v c = res.b.BDD.v (Cube.of_ c) }
235
in
236
res
237
238
function
update
(c:Cube.b) (s:Cube.b) (c':Cube.b) : Cube.b =
239
(fun i -> if s i then c' i else c i)

update read by a BDD

    Valid (39ms) (colibri2)
242
let ghost
v_update
(x s: t) (c c': Cube.b) : unit
243
ensures { x.v (update c (support s) c')
244
= x.b.BDD.v (BDD.update (Cube.of_ c) (BDD.support s.b) (Cube.of_ c')) }
245
= v_keys x (Cube.of_ (update c (support s) c')) (BDD.update (Cube.of_ c) (BDD.support s.b) (Cube.of_ c'))
246
Valid (40ms) (colibri2)
247
let ghost
v_update_to
(x s: t) (c: Cube.b) (w: Cube.a) : unit
248
ensures { x.b.BDD.v (BDD.update (Cube.of_ c) (BDD.support s.b) (Cube.of_ (Cube.to_ w)))
249
= x.b.BDD.v (BDD.update (Cube.of_ c) (BDD.support s.b) w) }
250
= v_keys x (BDD.update (Cube.of_ c) (BDD.support s.b) (Cube.of_ (Cube.to_ w)))
251
(BDD.update (Cube.of_ c) (BDD.support s.b) w)
252
253
(* Existential quantification over the support of s. *) Valid (368ms) (colibri2 5) (cvc4 3) (split_vc) (depth 1)
254
let
dexist
(s x: t) : t
255
requires { BDD.is_support s.b }
256
ensures { result.dom = Set.diff x.dom (support s) }
257
ensures { result.v = (fun c -> exists c'. x.v (update c (support s) c')) } =
258
let r = BDD.dexist s.b x.b in
259
of_to_dom s;
260
let res = { b = r } in
261
let lemma pointwise (c: Cube.b) : unit
262
ensures { res.v c <-> exists c'. x.v (update c (support s) c') }
263
=
264
let lemma l1 (c': Cube.b) : unit
265
ensures { x.v (update c (support s) c')
266
= x.b.BDD.v (BDD.update (Cube.of_ c) (BDD.support s.b) (Cube.of_ c')) }
267
= v_update x s c c' in
268
let lemma l2 (w: Cube.a) : unit
269
requires { x.b.BDD.v (BDD.update (Cube.of_ c) (BDD.support s.b) w) }
270
ensures { x.v (update c (support s) (Cube.to_ w)) }
271
= v_update_to x s c w; v_update x s c (Cube.to_ w) in
272
assert { res.v c = r.BDD.v (Cube.of_ c) }
273
in
274
res
275
276
(* Universal quantification over the support of s. *) Valid (318ms) (colibri2 7) (cvc4) (split_vc) (depth 1)
277
let
dforall
(s x: t) : t
278
requires { BDD.is_support s.b }
279
ensures { result.dom = Set.diff x.dom (support s) }
280
ensures { result.v = (fun c -> forall c'. x.v (update c (support s) c')) } =
281
let r = BDD.dforall s.b x.b in
282
of_to_dom s;
283
let res = { b = r } in
284
let lemma pointwise (c: Cube.b) : unit
285
ensures { res.v c <-> forall c'. x.v (update c (support s) c') }
286
=
287
let lemma l1 (c': Cube.b) : unit
288
ensures { x.v (update c (support s) c')
289
= x.b.BDD.v (BDD.update (Cube.of_ c) (BDD.support s.b) (Cube.of_ c')) }
290
= v_update x s c c' in
291
let lemma l2 (w: Cube.a) : unit
292
requires { x.v (update c (support s) (Cube.to_ w)) }
293
ensures { x.b.BDD.v (BDD.update (Cube.of_ c) (BDD.support s.b) w) }
294
= v_update_to x s c w; v_update x s c (Cube.to_ w) in
295
assert { res.v c = r.BDD.v (Cube.of_ c) }
296
in
297
res
298
299
(* Negation of a VBDD. *) Valid (870ms) (colibri2 2) (cvc4) (split_vc) (depth 1)
300
let
dnot
(a: t) : t
301
ensures { result.dom = a.dom }
302
ensures { result.v = Set.complement a.v } =
303
{ b = BDD.dnot a.b }
304
305
(* If-then-else: returns a when x is true, b when x is false. *) Valid (390ms) (colibri2)
306
let partial
ite
(x: Key.t) (aa bb: t) : t
307
ensures { Set.mem x keys }
308
ensures { result.dom = Set.add x (Set.union aa.dom bb.dom) }
309
ensures { result.v = (fun c -> if Set.mem x c then aa.v c else bb.v c) } =
310
let y = Var.of_key x in
311
to_add x (Set.union aa.b.BDD.dom bb.b.BDD.dom);
312
{ b = BDD.ite y aa.b bb.b }

ite for a key of the prophecy, in ghost code (without of_key)

    Valid (372ms) (colibri2)
315
let ghost
ite_g
(x: Key.t) (aa bb: t) : t
316
requires { Set.mem x keys }
317
ensures { result.dom = Set.add x (Set.union aa.dom bb.dom) }
318
ensures { result.v = (fun c -> if Set.mem x c then aa.v c else bb.v c) } =
319
let y = pure { var_of_key x } in
320
to_add x (Set.union aa.b.BDD.dom bb.b.BDD.dom);
321
{ b = BDD.ite y aa.b bb.b }
322
323
function
nb_nodes
(a:t) : int = BDD.nb_nodes a.b
324
Valid (847ms) (colibri2)
325
let rec
keys_of
(l: list CVar.t) : list Key.t
326
requires { forall x. Mem.mem x l -> Set.mem (key_of_var x) keys }
327
variant { l }
328
ensures { forall k. Mem.mem k result <-> (Set.mem k keys /\ Mem.mem (var_of_key k) l) }
329
ensures { Distinct.distinct l -> Distinct.distinct result }
330
= match l with
331
| Nil -> Nil
332
| Cons x l -> Cons (Var.to_key x) (keys_of l)
333
end
334
335
(* Var.vars *) Valid (650ms) (cvc4)
336
let
vars
(a:t) : list Key.t
337
ensures { forall k. Mem.mem k result <-> Set.mem k (support a) }
338
ensures { Distinct.distinct result }
339
= keys_of (BDD.vars a.b)
340
341
type
inspect
=
Bool
bool |
Ite
Key.t t t
342
343
(* Top node of the BDD (Var.inspect). *) Valid (366ms) (colibri2 22) (cvc4) (split_vc 7) (depth 3)
344
let
inspect
(a:t) : inspect
345
ensures { match result with
346
| Bool b -> a.v = (if b then Set.all else Set.empty) /\ support a = Set.empty
347
| Ite x th el ->
348
Set.mem x (support a) /\
349
Set.subset (support th) (Set.remove x (support a)) /\
350
Set.subset (support el) (Set.remove x (support a)) /\
351
Set.mem x a.dom /\
352
Set.subset th.dom (Set.remove x a.dom) /\
353
Set.subset el.dom (Set.remove x a.dom) /\
354
0 <= nb_nodes th < nb_nodes a /\ 0 <= nb_nodes el < nb_nodes a /\
355
a.v = (fun c -> if Set.mem x c then th.v c else el.v c)
356
end }
357
=
358
match BDD.inspect a.b with
359
| BDD.Bool b -> Bool b
360
| BDD.Ite x th el ->
361
let k = Var.to_key x in
362
assert { var_of_key k = x };
363
to_remove k (BDD.support a.b);
364
to_remove k a.b.BDD.dom;
365
Ite k { b = th } { b = el }
366
end
367
368
(* Boolean cofactors of a with respect to variable x. *) Valid (1.5s) (colibri2)
369
let partial
cofactors
(x: Key.t) (a: t) : (t, t)
370
returns { (p, n) ->
371
Set.mem x keys /\
372
p.dom = Set.remove x a.dom /\
373
n.dom = Set.remove x a.dom /\
374
p.v = (fun c -> a.v (Set.add x c)) /\
375
n.v = (fun c -> a.v (Set.remove x c)) } =
376
let y = Var.of_key x in
377
let (p, n) = BDD.cofactors y a.b in
378
to_remove x a.b.BDD.dom;
379
let lemma pt (c: Cube.b) : unit
380
ensures { Cube.of_ (Set.add x c) = Set.add y (Cube.of_ c) }
381
ensures { Cube.of_ (Set.remove x c) = Set.remove y (Cube.of_ c) }
382
= of_add x c; of_remove x c in
383
({ b = p }, { b = n })
384
385
(* Cofactor of a with respect to cube b. *) Valid (1.6s) (colibri2)
386
let
cofactor
(a cb: t) : t
387
requires { BDD.is_cube cb.b }
388
ensures { result.dom = Set.diff a.dom (support cb) }
389
ensures { result.v = (fun c -> a.v (Set.union (Set.diff c (support cb)) (get_cube cb))) } =
390
let r = BDD.cofactor a.b cb.b in
391
let res = { b = r } in
392
let lemma pt (c: Cube.b) : unit
393
ensures { res.v c = a.v (Set.union (Set.diff c (support cb)) (get_cube cb)) }
394
= v_keys a (Cube.of_ (Set.union (Set.diff c (support cb)) (get_cube cb)))
395
(Set.union (Set.diff (Cube.of_ c) (BDD.support cb.b)) (BDD.get_cube cb.b))
396
in
397
res
398
399
(* Substitute variable x with the function f in a. *) Valid (27ms) (colibri2 9) (split_vc) (depth 1)
400
let partial
compose
(x: Key.t) (f a: t) : t
401
ensures { Set.mem x keys }
402
ensures { result.dom = Set.union f.dom (Set.remove x a.dom) }
403
ensures { result.v = (fun c -> a.v (Map.set c x (f.v c))) } =
404
let y = Var.of_key x in
405
let r = BDD.compose y f.b a.b in
406
to_remove x a.b.BDD.dom;
407
let res = { b = r } in
408
let lemma pt (c: Cube.b) : unit
409
ensures { res.v c = a.v (Map.set c x (f.v c)) }
410
=
411
of_map_set c x (pure { f.v c });
412
assert { f.v c = f.b.BDD.v (Cube.of_ c) };
413
assert { res.v c = r.BDD.v (Cube.of_ c) }
414
in
415
res
416
417
scope Vector

A vector of substitutions on the variables of the keys

        Valid (22ms) (colibri2)
419
type
vector
= {
420
vec
: BDD.Vector.vector;
421
} invariant { forall y. Set.mem y vec.BDD.Vector.added -> Set.mem (key_of_var y) keys }
422
invariant { forall y. Set.mem y vec.BDD.Vector.removed -> Set.mem (key_of_var y) keys }
423
by { vec = BDD.Vector.create () }
424
425
function
removed
(v:vector) : Cube.b =
426
Cube.to_ v.vec.BDD.Vector.removed
427
428
function
added
(v:vector) : Cube.b =
429
Cube.to_ v.vec.BDD.Vector.added

The cube w on the keys, c elsewhere

432
function
merge
(c: Cube.b) (w: Cube.a) : Cube.b =
433
fun k -> if Set.mem k keys then w (var_of_key k) else c k

The substitution at c: the keys outside keys keep their value in c

g at the cube w on the keys, c elsewhere

438
function
gm
(g: Value.b) (c: Cube.b) : Value.a = fun w -> g (merge c w)
439
440
function
subst
(v:vector) : Value.b -> Value.b =
441
fun g c -> BDD.Vector.subst v.vec (gm g c) (Cube.of_ c)
442
Valid (18ms) (colibri2)
443
let ghost
merge_of
(c: Cube.b) : unit
444
ensures { merge c (Cube.of_ c) = c }
445
= ()
446
Valid (35ms) (colibri2)
447
let ghost
merge_set
(c: Cube.b) (w: Cube.a) (x: Key.t) (b: bool) : unit
448
requires { Set.mem x keys }
449
ensures { merge c (Map.set w (var_of_key x) b) = Map.set (merge c w) x b }
450
= assert { forall k. Set.mem k keys -> var_of_key k = var_of_key x -> k = x }
451
Valid (74ms) (colibri2)
452
let
create
() : vector
453
ensures { result.removed = Set.empty }
454
ensures { result.added = Set.empty }
455
ensures { result.subst = (fun x -> x) } =
456
let r = { vec = BDD.Vector.create () } in
457
let lemma pt (g: Value.b) (c: Cube.b) : unit
458
ensures { subst r g c = g c }
459
= merge_of c; assert { gm g c (Cube.of_ c) = g c } in
460
assert { forall g. subst r g = g };
461
r
462
463
function
upd
(a: Value.b) (x: Key.t) (b: bool) : Value.b =
464
fun c' -> a (Map.set c' x b)
465
466
(* Add the substitution x := f to the vector. *) Valid (30ms) (colibri2 17) (split_vc) (depth 1)
467
let partial
add
(vv: vector) (x: Key.t) (f: t) : vector
468
requires { not (Set.mem x vv.removed) }
469
ensures { Set.mem x keys }
470
ensures { result.removed = Set.add x vv.removed }
471
ensures { result.added = Set.union vv.added f.dom }
472
ensures { result.subst = (fun a -> (fun c -> vv.subst (upd a x (f.v c)) c)) } =
473
let y = Var.of_key x in
474
let r = BDD.Vector.add vv.vec y f.b in
475
to_add x vv.vec.BDD.Vector.removed;
476
let res = { vec = r } in
477
let lemma pointwise (a: Value.b) (c: Cube.b) : unit
478
ensures { subst res a c = subst vv (upd a x (f.v c)) c }
479
=
480
let ghost fc = pure { f.b.BDD.v (Cube.of_ c) } in
481
assert { f.v c = fc };
482
let lemma pt (w: Cube.a) : unit
483
ensures { BDD.upd (gm a c) y fc w = gm (upd a x fc) c w }
484
= merge_set c w x fc in
485
assert { BDD.upd (gm a c) y fc = gm (upd a x fc) c };
486
assert { subst res a c = BDD.Vector.subst r (gm a c) (Cube.of_ c) };
487
assert { BDD.Vector.subst r (gm a c) (Cube.of_ c)
488
= BDD.Vector.subst vv.vec (BDD.upd (gm a c) y fc) (Cube.of_ c) };
489
assert { subst vv (upd a x fc) c = BDD.Vector.subst vv.vec (gm (upd a x fc) c) (Cube.of_ c) }
490
in
491
assert { forall a. subst res a = (fun c -> subst vv (upd a x (f.v c)) c) };
492
res
493
494
(* Apply the substitution vector to a VBDD. *) Valid (39ms) (colibri2 10) (split_vc) (depth 1)
495
let
compose
(v: vector) (a: t) : t
496
ensures { result.dom = Set.union v.added (Set.diff a.dom v.removed) }
497
ensures { result.v = v.subst a.v } =
498
let r = BDD.Vector.compose v.vec a.b in
499
let res = { b = r } in
500
let lemma pointwise (c: Cube.b) : unit
501
ensures { res.v c = subst v a.v c }
502
=
503
let lemma pt (w: Cube.a) : unit
504
ensures { gm a.v c w = a.b.BDD.v w }
505
= v_keys a (Cube.of_ (merge c w)) w in
506
assert { gm a.v c = a.b.BDD.v };
507
assert { res.v c = r.BDD.v (Cube.of_ c) };
508
assert { subst v a.v c = BDD.Vector.subst v.vec (gm a.v c) (Cube.of_ c) }
509
in
510
assert { forall c. res.v c = subst v a.v c };
511
res
512
end
513
514
Valid (35ms) (colibri2 4) (split_vc) (depth 1)
515
let lemma
support_v
(a:t) (x y: Cube.b) : unit
516
requires { forall i. Set.mem i a.dom -> Set.mem i x = Set.mem i y }
517
ensures { a.v x = a.v y }
518
=
519
BDD.invariant_outside_domain a.b;
520
assert { forall i. Set.mem i a.b.BDD.dom -> Set.mem (key_of_var i) a.dom };
521
assert { forall i. Set.mem i a.b.BDD.dom -> (Set.mem i (Cube.of_ x) <-> Set.mem i (Cube.of_ y)) };
522
assert { a.v x = a.b.BDD.v (Cube.of_ x) }
523
Valid (86ms) (cvc4)
524
lemma
support_dom
: forall a. Set.subset (support a) a.dom
525
Valid (30ms) (colibri2 5) (cvc4) (split_vc) (depth 1)
526
let lemma
support_exact
(a:t) (x y: Cube.b) : unit
527
requires { forall i. Set.mem i (support a) -> Set.mem i x = Set.mem i y }
528
ensures { a.v x = a.v y }
529
=
530
assert { forall i. Set.mem i (BDD.support a.b) -> Set.mem i a.b.BDD.dom };
531
assert { forall i. Set.mem i (BDD.support a.b) -> Set.mem (key_of_var i) (support a) };
532
assert { forall i. Set.mem i (BDD.support a.b) -> (Set.mem i (Cube.of_ x) <-> Set.mem i (Cube.of_ y)) };
533
BDD.support_exact a.b (Cube.of_ x) (Cube.of_ y);
534
assert { a.v x = a.b.BDD.v (Cube.of_ x) }

A variable of the support changes the value

    Valid (356ms) (cvc4)
537
let lemma
support_dep
(a:t) (k: Key.t) : unit
538
requires { Set.mem k (support a) }
539
ensures { exists c. a.v (Set.add k c) <> a.v (Set.remove k c) }
540
=
541
let x = pure { var_of_key k } in
542
assert { Set.mem x (BDD.support a.b) };
543
let ghost c0 = any CCube.t
544
ensures { a.b.BDD.v (Set.add x result) <> a.b.BDD.v (Set.remove x result) } in
545
of_add k (Cube.to_ c0); of_remove k (Cube.to_ c0);
546
v_keys a (Set.add x (Cube.of_ (Cube.to_ c0))) (Set.add x c0);
547
v_keys a (Set.remove x (Cube.of_ (Cube.to_ c0))) (Set.remove x c0);
548
assert { a.v (Set.add k (Cube.to_ c0)) <> a.v (Set.remove k (Cube.to_ c0)) }
549
550
end