library colibrilib.sbdd — module VBDDmodule VBDD1
Implemented
use set.Set2use map.MapExt3use bool.Bool4use colibrilib.bdd.CVar5use colibrilib.bdd.CCube6use colibrilib.bdd.Var7use colibrilib.bdd.Key8use colibrilib.bdd.BDD9use int.Int10use list.List11use list.Mem12use list.Distinct13
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
scope Cube22type a = Set.set CVar.t23type b = Set.set Key.t24function to_ (x: a) : b = fun k -> Set.mem k keys /\ x (var_of_key k)25function of_ (y: b) : a = fun v -> y (key_of_var v)26end2728scope Value29type a = Set.set Cube.a30type b = Set.set Cube.b31function to_ (f: a) : b = fun c -> f (Cube.of_ c)32end3334function dom (x:t) : Cube.b = Cube.to_ x.b.BDD.dom35function v (x:t): Value.b = Value.to_ x.b.BDD.v36function get_cube (x:t) : Cube.b = Cube.to_ x.b.BDD.get_cube37function support (a:t) : Cube.b = Cube.to_ (BDD.support a.b)38
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
function merge (c: Cube.b) (w: Cube.a) : Cube.b =432fun k -> if Set.mem k keys then w (var_of_key k) else c k433
The substitution at c: the keys outside keys keep their value in c
g at the cube w on the keys, c elsewhere
function gm (g: Value.b) (c: Cube.b) : Value.a = fun w -> g (merge c w)438439function subst (v:vector) : Value.b -> Value.b =440fun g c -> BDD.Vector.subst v.vec (gm g c) (Cube.of_ c)441Valid (18ms) (colibri2)442let ghost merge_of (c: Cube.b) : unit443ensures { merge c (Cube.of_ c) = c }444= ()445Valid (35ms) (colibri2)446let ghost merge_set (c: Cube.b) (w: Cube.a) (x: Key.t) (b: bool) : unit447requires { Set.mem x keys }448ensures { merge c (Map.set w (var_of_key x) b) = Map.set (merge c w) x b }449= assert { forall k. Set.mem k keys -> var_of_key k = var_of_key x -> k = x }450Valid (74ms) (colibri2)451let create () : vector452ensures { result.removed = Set.empty }453ensures { result.added = Set.empty }454ensures { result.subst = (fun x -> x) } =455let r = { vec = BDD.Vector.create () } in456let lemma pt (g: Value.b) (c: Cube.b) : unit457ensures { subst r g c = g c }458= merge_of c; assert { gm g c (Cube.of_ c) = g c } in459assert { forall g. subst r g = g };460r461462function upd (a: Value.b) (x: Key.t) (b: bool) : Value.b =463fun c' -> a (Map.set c' x b)464465(* Add the substitution x := f to the vector. *) Valid (30ms) (colibri2 17) (split_vc) (depth 1)466let partial add (vv: vector) (x: Key.t) (f: t) : vector467requires { not (Set.mem x vv.removed) }468ensures { Set.mem x keys }469ensures { result.removed = Set.add x vv.removed }470ensures { result.added = Set.union vv.added f.dom }471ensures { result.subst = (fun a -> (fun c -> vv.subst (upd a x (f.v c)) c)) } =472let y = Var.of_key x in473let r = BDD.Vector.add vv.vec y f.b in474to_add x vv.vec.BDD.Vector.removed;475let res = { vec = r } in476let lemma pointwise (a: Value.b) (c: Cube.b) : unit477ensures { subst res a c = subst vv (upd a x (f.v c)) c }478=479let ghost fc = pure { f.b.BDD.v (Cube.of_ c) } in480assert { f.v c = fc };481let lemma pt (w: Cube.a) : unit482ensures { BDD.upd (gm a c) y fc w = gm (upd a x fc) c w }483= merge_set c w x fc in484assert { BDD.upd (gm a c) y fc = gm (upd a x fc) c };485assert { subst res a c = BDD.Vector.subst r (gm a c) (Cube.of_ c) };486assert { BDD.Vector.subst r (gm a c) (Cube.of_ c)487= BDD.Vector.subst vv.vec (BDD.upd (gm a c) y fc) (Cube.of_ c) };488assert { subst vv (upd a x fc) c = BDD.Vector.subst vv.vec (gm (upd a x fc) c) (Cube.of_ c) }489in490assert { forall a. subst res a = (fun c -> subst vv (upd a x (f.v c)) c) };491res492493(* Apply the substitution vector to a VBDD. *) Valid (39ms) (colibri2 10) (split_vc) (depth 1)494let compose (v: vector) (a: t) : t495ensures { result.dom = Set.union v.added (Set.diff a.dom v.removed) }496ensures { result.v = v.subst a.v } =497let r = BDD.Vector.compose v.vec a.b in498let res = { b = r } in499let lemma pointwise (c: Cube.b) : unit500ensures { res.v c = subst v a.v c }501=502let lemma pt (w: Cube.a) : unit503ensures { gm a.v c w = a.b.BDD.v w }504= v_keys a (Cube.of_ (merge c w)) w in505assert { gm a.v c = a.b.BDD.v };506assert { res.v c = r.BDD.v (Cube.of_ c) };507assert { subst v a.v c = BDD.Vector.subst v.vec (gm a.v c) (Cube.of_ c) }508in509assert { forall c. res.v c = subst v a.v c };510res511end512513Valid (35ms) (colibri2 4) (split_vc) (depth 1)514let lemma support_v (a:t) (x y: Cube.b) : unit515requires { forall i. Set.mem i a.dom -> Set.mem i x = Set.mem i y }516ensures { a.v x = a.v y }517=518BDD.invariant_outside_domain a.b;519assert { forall i. Set.mem i a.b.BDD.dom -> Set.mem (key_of_var i) a.dom };520assert { forall i. Set.mem i a.b.BDD.dom -> (Set.mem i (Cube.of_ x) <-> Set.mem i (Cube.of_ y)) };521assert { a.v x = a.b.BDD.v (Cube.of_ x) }522Valid (86ms) (cvc4)523lemma support_dom: forall a. Set.subset (support a) a.dom524Valid (30ms) (colibri2 5) (cvc4) (split_vc) (depth 1)525let lemma support_exact (a:t) (x y: Cube.b) : unit526requires { forall i. Set.mem i (support a) -> Set.mem i x = Set.mem i y }527ensures { a.v x = a.v y }528=529assert { forall i. Set.mem i (BDD.support a.b) -> Set.mem i a.b.BDD.dom };530assert { forall i. Set.mem i (BDD.support a.b) -> Set.mem (key_of_var i) (support a) };531assert { forall i. Set.mem i (BDD.support a.b) -> (Set.mem i (Cube.of_ x) <-> Set.mem i (Cube.of_ y)) };532BDD.support_exact a.b (Cube.of_ x) (Cube.of_ y);533assert { a.v x = a.b.BDD.v (Cube.of_ x) }534
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
550end