library colibrilib.models — module BDDModelbdd.BDD: a BDD is a boolean function v of the valuations (the sets of true variables) that depends only on the finite set dom. The support is the set of the variables on which v depends, and the number of nodes is the number of variables of the support (the only property used is that inspect decreases it). The variables CVar.t stay abstract.
module BDDModel651use int.Int652use set.Set653use set.Cardinal654use list.List655use list.Mem as Mem656use list.Distinct657use bool.Bool658use map.Map659use map.MapExt660use colibrilib.bdd.CVar661use colibrilib.bdd.CCube662clone SetFacts as SF {… begin (* cloned colibrilib.models.SetFacts *) let ghost SF.inter_union (int63 -> bool) (int63 -> bool) (int63 -> bool) (int63 -> bool) (int63 -> bool) : unit let ghost SF.card_remove int63 (int63 -> bool) : unit end } with type a = CVar.t663
x and y give the same values to the variables of d
predicate agree (d: set CVar.t) (x y: CCube.t) =666forall i. mem i d -> (mem i x <-> mem i y)667
f depends only on the variables of d
predicate depends (f: set CCube.t) (d: set CVar.t) =670forall x y. agree d x y -> f x = f y671672type t = { ghost dom: set CVar.t; ghost v: set CCube.t; ghost cube: CCube.t }673invariant { is_finite dom /\ depends v dom } Valid (17ms) (colibri2)674by { dom = empty; v = empty; cube = empty }675676function get_cube (b:t) : CCube.t = b.cube677Valid (20ms) (colibri2)678let ghost dep (a:t) (x y:CCube.t) : unit679requires { agree a.dom x y }680ensures { a.v x = a.v y }681= ()682683function support (a:t) : set CVar.t =684fun x -> exists c. a.v (add x c) <> a.v (remove x c)685Valid (19ms) (colibri2)686let lemma support_iff (a:t) (x:CVar.t)687ensures { mem x (support a) <-> exists c. a.v (add x c) <> a.v (remove x c) }688= ()689Valid (793ms) (colibri2)690let lemma support_dom (a:t)691ensures { subset (support a) a.dom }692= assert { forall x c. not mem x a.dom -> agree a.dom (add x c) (remove x c) }693
cardinal_remove, from cardinal_add
Valid (18ms) (colibri2)let ghost card_remove (x:CVar.t) (s:set CVar.t) : unit696requires { is_finite s /\ mem x s }697ensures { cardinal (remove x s) = cardinal s - 1 }698= let r = remove x s in699assert { is_finite r };700assert { not mem x r };701assert { add x r == s };702assert { cardinal (add x r) = cardinal r + 1 }703
The differences of x and y in d
function diffs (d: set CVar.t) (x y: CCube.t) : set CVar.t =706fun i -> mem i d /\ (mem i x <-> not mem i y)707Valid (1.4s) (colibri2 15) (cvc4) (cvc5) (split_vc 3) (depth 2)708let rec lemma exact_n (a:t) (x y:CCube.t) (n:int)709requires { agree (support a) x y }710requires { n = cardinal (diffs a.dom x y) }711ensures { a.v x = a.v y }712variant { n }713= let d = diffs a.dom x y in714assert { is_finite d by subset d a.dom };715if n = 0 then begin716assert { is_empty d };717assert { agree a.dom x y }718end else begin719let i = pick d in720assert { mem i d };721assert { not mem i (support a) };722let x' = pure { if mem i y then add i x else remove i x } in723assert { a.v x' = a.v x by724a.v (add i x) = a.v (remove i x) /\725(x = add i x \/ x = remove i x)726by (mem i x -> add i x == x) /\ (not mem i x -> remove i x == x) };727assert { diffs a.dom x' y == remove i d };728card_remove i d;729exact_n a x' y (n - 1)730end731Valid (21ms) (colibri2)732let lemma support_exact (a:t) (x y:CCube.t)733ensures { (forall i. mem i (support a) -> (mem i x <-> mem i y)) -> a.v x = a.v y }734= if pure { agree (support a) x y } then exact_n a x y (cardinal (diffs a.dom x y))735736predicate is_cube (b:t) = forall c. b.v c <-> inter c (support b) = get_cube b737738predicate is_support (b:t) = is_cube b /\ get_cube b = support b739Valid (14ms) (colibri2)740let constant mfalse : t = { dom = empty; v = empty; cube = empty }741Valid (15ms) (colibri2)742lemma false_def: empty = mfalse.dom /\ mfalse.v = empty743Valid (16ms) (colibri2)744let mk_false () : t ensures { result = mfalse } = mfalse745Valid (22ms) (colibri2)746let dtrue () : t747ensures { result.dom = empty /\ result.v = all /\ get_cube result = empty }748= { dom = empty; v = all; cube = empty }749Valid (411ms) (colibri2 4) (cvc5) (split_vc) (depth 1)750let is_equal (a:t) (b:t) : (result: bool, ghost c: CCube.t)751ensures { result = (forall c. a.v c = b.v c) }752ensures { not result -> subset c (union a.dom b.dom) /\ a.v c <> b.v c }753= let ghost w = pure { forall c. a.v c = b.v c } in754let r = any bool ensures { result = w } in755let ghost c =756if r then empty else begin757let c0 = any CCube.t ensures { a.v result <> b.v result } in758let c = inter c0 (union a.dom b.dom) in759assert { agree a.dom c c0 /\ agree b.dom c c0 };760c761end in762r, c763Valid (363ms) (colibri2 4) (cvc5) (split_vc) (depth 1)764let is_inter_empty (a:t) (b:t) : (result: bool, ghost c: CCube.t)765ensures { result = (forall c. not (a.v c /\ b.v c)) }766ensures { not result -> subset c (union a.dom b.dom) /\ (a.v c /\ b.v c) }767= let ghost w = pure { forall c. not (a.v c /\ b.v c) } in768let r = any bool ensures { result = w } in769let ghost c =770if r then empty else begin771let c0 = any CCube.t ensures { a.v result /\ b.v result } in772let c = inter c0 (union a.dom b.dom) in773assert { agree a.dom c c0 /\ agree b.dom c c0 };774c775end in776r, c777
The conjunction of two cubes on disjoint variables
Valid (366ms) (colibri2 20) (cvc4 5) (split_vc 3) (depth 2)let ghost and_cube (a b:t) (f: set CCube.t)780requires { f = inter a.v b.v }781requires { is_cube a /\ is_cube b }782requires { subset (get_cube a) (support a) /\ subset (get_cube b) (support b) }783requires { inter (support a) (support b) = empty }784ensures { forall x. (exists c. f (add x c) <> f (remove x c))785<-> mem x (union (support a) (support b)) }786ensures { forall c. f c <-> inter c (union (support a) (support b))787= union (get_cube a) (get_cube b) }788= let sa = support a in let sb = support b in789let ga = get_cube a in let gb = get_cube b in790assert { forall i. not (mem i sa /\ mem i sb)791by not mem i (inter sa sb) };792let c0 = union ga gb in793assert { inter c0 sa == ga /\ inter c0 sb == gb };794assert { a.v c0 /\ b.v c0 };795let lemma inside (x:CVar.t)796requires { mem x (union sa sb) }797ensures { f (add x c0) <> f (remove x c0) }798= if pure { mem x sa } then begin799assert { not mem x gb };800if pure { mem x ga } then begin801assert { add x c0 == c0 };802assert { inter (remove x c0) sa <> ga by not mem x (inter (remove x c0) sa) }803end else begin804assert { remove x c0 == c0 };805assert { inter (add x c0) sa <> ga by mem x (inter (add x c0) sa) }806end807end else begin808assert { not mem x ga };809if pure { mem x gb } then begin810assert { add x c0 == c0 };811assert { inter (remove x c0) sb <> gb by not mem x (inter (remove x c0) sb) }812end else begin813assert { remove x c0 == c0 };814assert { inter (add x c0) sb <> gb by mem x (inter (add x c0) sb) }815end816end in817let lemma outside (x:CVar.t) (c:CCube.t)818requires { not mem x (union sa sb) }819ensures { f (add x c) = f (remove x c) }820= assert { a.v (add x c) = a.v (remove x c) };821assert { b.v (add x c) = b.v (remove x c) } in822let lemma eqv (c:CCube.t)823ensures { f c <-> inter c (union sa sb) = union ga gb }824= SF.inter_union c sa sb ga gb;825assert { a.v c <-> inter c sa = ga };826assert { b.v c <-> inter c sb = gb } in827()828Valid (315ms) (colibri2 8) (cvc4 3) (split_vc 2) (depth 2)829let dand (a b: t) : t830ensures { result.dom = union a.dom b.dom }831ensures { result.v = inter a.v b.v }832ensures { is_cube a -> is_cube b ->833subset (get_cube a) (support a) -> subset (get_cube b) (support b) ->834inter (support a) (support b) = empty ->835is_cube result /\ get_cube result = union (get_cube a) (get_cube b) /\836support result = union (support a) (support b) }837= assert { forall c1 c2. agree (union a.dom b.dom) c1 c2 ->838agree a.dom c1 c2 /\ agree b.dom c1 c2 };839let r = { dom = pure { union a.dom b.dom }; v = pure { inter a.v b.v };840cube = pure { union (get_cube a) (get_cube b) } } in841if pure { is_cube a /\ is_cube b /\842subset (get_cube a) (support a) /\ subset (get_cube b) (support b) /\843inter (support a) (support b) = empty } then begin844and_cube a b r.v;845assert { support r == union (support a) (support b) }846end;847r848Valid (781ms) (colibri2 3) (cvc4) (split_vc 2) (depth 2)849let dor (a b: t) : t850ensures { result.dom = union a.dom b.dom }851ensures { result.v = union a.v b.v }852= { dom = pure { union a.dom b.dom }; v = pure { union a.v b.v }; cube = empty }853Valid (831ms) (colibri2 2) (cvc4) (split_vc) (depth 1)854let dxor (a b: t) : t855ensures { result.dom = union a.dom b.dom }856ensures { result.v = (fun c -> xorb (a.v c) (b.v c)) }857= { dom = pure { union a.dom b.dom }; v = pure { fun c -> xorb (a.v c) (b.v c) };858cube = empty }859860function update (c:CCube.t) (s:CCube.t) (c':CCube.t) : CCube.t =861(fun i -> if s i then c' i else c i)862Valid (384ms) (colibri2 5) (cvc4 4) (split_vc 2) (depth 2)863let dexist (s:t) (a: t) : t864requires { is_support s }865ensures { result.dom = diff a.dom (support s) }866ensures { result.v = (fun c -> exists c'. a.v (update c (support s) c')) }867= let lemma pw (c1 c2 c':CCube.t)868requires { agree (diff a.dom (support s)) c1 c2 }869ensures { a.v (update c1 (support s) c') = a.v (update c2 (support s) c') }870= assert { agree a.dom (update c1 (support s) c') (update c2 (support s) c') };871dep a (update c1 (support s) c') (update c2 (support s) c') in872let ghost f = pure { fun c -> exists c'. a.v (update c (support s) c') } in873let lemma fd (c1 c2:CCube.t)874requires { agree (diff a.dom (support s)) c1 c2 }875ensures { f c1 = f c2 }876= assert { (exists c'. a.v (update c1 (support s) c')) <->877(exists c'. a.v (update c2 (support s) c')) } in878{ dom = pure { diff a.dom (support s) }; v = f; cube = empty }879Valid (384ms) (colibri2 5) (cvc4 4) (split_vc 2) (depth 2)880let dforall (s:t) (a: t) : t881requires { is_support s }882ensures { result.dom = diff a.dom (support s) }883ensures { result.v = (fun c -> forall c'. a.v (update c (support s) c')) }884= let lemma pw (c1 c2 c':CCube.t)885requires { agree (diff a.dom (support s)) c1 c2 }886ensures { a.v (update c1 (support s) c') = a.v (update c2 (support s) c') }887= assert { agree a.dom (update c1 (support s) c') (update c2 (support s) c') };888dep a (update c1 (support s) c') (update c2 (support s) c') in889let ghost f = pure { fun c -> forall c'. a.v (update c (support s) c') } in890let lemma fd (c1 c2:CCube.t)891requires { agree (diff a.dom (support s)) c1 c2 }892ensures { f c1 = f c2 }893= assert { (forall c'. a.v (update c1 (support s) c')) <->894(forall c'. a.v (update c2 (support s) c')) } in895{ dom = pure { diff a.dom (support s) }; v = f; cube = empty }896Valid (396ms) (colibri2 3) (cvc4) (split_vc) (depth 1)897let bdd_of_var (x: CVar.t) : t898ensures { result.dom = singleton x }899ensures { result.v = (fun c -> c x) }900ensures { get_cube result = singleton x }901= { dom = pure { singleton x }; v = pure { fun (c:CCube.t) -> c x }; cube = pure { singleton x } }902Valid (415ms) (colibri2 2) (cvc4 2) (split_vc) (depth 1)903let bdd_not_of_var (x: CVar.t) : t904ensures { result.dom = singleton x }905ensures { result.v = (fun c -> not (c x)) }906ensures { get_cube result = empty }907= { dom = pure { singleton x }; v = pure { fun (c:CCube.t) -> not (c x) }; cube = empty }908Valid (727ms) (colibri2 7) (cvc4 5) (split_vc 2) (depth 2)909let support_union (a b: t) : t910requires { is_support a /\ is_support b }911ensures { result.dom = union a.dom b.dom }912ensures { is_support result }913ensures { support result = union (support a) (support b) }914= let s = pure { union (support a) (support b) } in915assert { subset s (union a.dom b.dom) };916let r = { dom = pure { union a.dom b.dom }; v = pure { fun c -> subset s c };917cube = s } in918let lemma inside (x:CVar.t)919requires { mem x s }920ensures { r.v (add x s) <> r.v (remove x s) }921= assert { add x s == s } in922let lemma outside (x:CVar.t) (c:CCube.t)923requires { not mem x s }924ensures { r.v (add x c) = r.v (remove x c) }925= assert { subset s (add x c) <-> subset s (remove x c) } in926assert { support r == s };927assert { forall c. subset s c <-> inter c s == s };928r929Valid (142ms) (cvc4)930let dnot (a: t) : t931ensures { result.dom = a.dom }932ensures { result.v = complement a.v }933= { dom = a.dom; v = pure { complement a.v }; cube = empty }934Valid (46ms) (colibri2 7) (split_vc 2) (depth 2)935let ite (x:CVar.t) (a:t) (b:t) : t936ensures { result.dom = add x (union a.dom b.dom) }937ensures { result.v = (fun c -> if mem x c then a.v c else b.v c) }938= assert { forall c1 c2. agree (add x (union a.dom b.dom)) c1 c2 ->939(mem x c1 <-> mem x c2) /\ agree a.dom c1 c2 /\ agree b.dom c1 c2 };940{ dom = pure { add x (union a.dom b.dom) };941v = pure { fun c -> if mem x c then a.v c else b.v c }; cube = empty }942Valid (1.6s) (colibri2)943let cofactors (x:CVar.t) (a: t) : (pos:t, neg:t)944ensures { pos.dom = remove x a.dom }945ensures { neg.dom = remove x a.dom }946ensures { pos.v = (fun c -> a.v (add x c)) }947ensures { neg.v = (fun c -> a.v (remove x c)) }948= assert { forall c1 c2. agree (remove x a.dom) c1 c2 ->949agree a.dom (add x c1) (add x c2) /\950agree a.dom (remove x c1) (remove x c2) };951{ dom = pure { remove x a.dom }; v = pure { fun c -> a.v (add x c) }; cube = empty },952{ dom = pure { remove x a.dom }; v = pure { fun c -> a.v (remove x c) }; cube = empty }953Valid (85ms) (colibri2 4) (split_vc) (depth 1)954let cofactor (a:t) (b: t) : (cof:t)955requires { is_cube b }956ensures { cof.dom = diff a.dom (support b) }957ensures { cof.v = (fun c -> a.v (union (diff c (support b)) (get_cube b))) }958= assert { forall c1 c2. agree (diff a.dom (support b)) c1 c2 ->959agree a.dom (union (diff c1 (support b)) (get_cube b))960(union (diff c2 (support b)) (get_cube b)) };961{ dom = pure { diff a.dom (support b) };962v = pure { fun c -> a.v (union (diff c (support b)) (get_cube b)) }; cube = empty }963Valid (954ms) (cvc4)964let ghost function invariant_outside_domain (a:t) : unit965ensures { forall x y. (forall i. mem i a.dom -> mem i x = mem i y) -> a.v x = a.v y }966= ()967Valid (1.3s) (colibri2 8) (split_vc) (depth 1)968let compose (x:CVar.t) (f:t) (a: t) : (res:t)969ensures { res.dom = union f.dom (remove x a.dom) }970ensures { res.v = (fun c -> a.v (Map.set c x (f.v c))) }971= let lemma pw (c1 c2:CCube.t)972requires { agree (union f.dom (remove x a.dom)) c1 c2 }973ensures { a.v (Map.set c1 x (f.v c1)) = a.v (Map.set c2 x (f.v c2)) }974= assert { agree f.dom c1 c2 };975dep f c1 c2;976let b = f.v c1 in977assert { agree a.dom (Map.set c1 x b) (Map.set c2 x b) };978dep a (Map.set c1 x b) (Map.set c2 x b) in979{ dom = pure { union f.dom (remove x a.dom) };980v = pure { fun c -> a.v (Map.set c x (f.v c)) }; cube = empty }981982function nb_nodes (a:t) : int = cardinal (support a)983Valid (21ms) (colibri2)984lemma nb_nodes_nonneg: forall a. 0 <= nb_nodes a985Valid (358ms) (cvc4)986let lemma nb_nodes_canon (a b:t)987ensures { a.v = b.v -> nb_nodes a = nb_nodes b }988= if pure { a.v = b.v } then assert { support a == support b }989
The list of the elements of a finite set
Valid (63ms) (colibri2 6) (split_vc) (depth 1)let rec ghost enum (s: set CVar.t) : list CVar.t992requires { is_finite s }993ensures { forall x. Mem.mem x result <-> mem x s }994ensures { distinct result }995variant { cardinal s }996= if pure { is_empty s } then Nil997else begin998let x = pick s in999assert { mem x s };1000card_remove x s;1001let r = enum (remove x s) in1002Cons x r1003end1004Valid (352ms) (cvc4)1005let vars (a:t) : list CVar.t1006ensures { forall x. Mem.mem x result <-> mem x (support a) }1007ensures { distinct result }1008= let ghost l = enum (support a) in1009any list CVar.t ensures { result = l }10101011type inspect = Bool bool | Ite CVar.t t t1012
The support of a cofactor
Valid (369ms) (colibri2 3) (cvc4 2) (split_vc) (depth 1)let ghost cofactor_support (x:CVar.t) (a p:t) : unit1015requires { p.v = (fun c -> a.v (add x c)) \/ p.v = (fun c -> a.v (remove x c)) }1016ensures { subset (support p) (remove x (support a)) }1017= let lemma sub (y:CVar.t) (c:CCube.t)1018requires { p.v (add y c) <> p.v (remove y c) }1019ensures { y <> x /\ mem y (support a) }1020= assert { y <> x by y = x -> add x (add y c) == add x (remove y c)1021/\ remove x (add y c) == remove x (remove y c) };1022assert { add x (add y c) == add y (add x c)1023/\ add x (remove y c) == remove y (add x c) };1024assert { remove x (add y c) == add y (remove x c)1025/\ remove x (remove y c) == remove y (remove x c) } in1026()1027Valid (957ms) (colibri2 18) (cvc4 3) (cvc5) (split_vc 3) (depth 2)1028let inspect (a:t) : inspect1029ensures { match result with1030| Bool b -> a.v = (if b then all else empty) /\ support a = empty1031| Ite x th el ->1032mem x (support a) /\1033subset (support th) (remove x (support a)) /\1034subset (support el) (remove x (support a)) /\1035mem x a.dom /\1036subset th.dom (remove x a.dom) /\1037subset el.dom (remove x a.dom) /\1038nb_nodes th < nb_nodes a /\ nb_nodes el < nb_nodes a /\1039a.v = (fun c -> if mem x c then th.v c else el.v c)1040end }1041= let ghost w =1042if pure { is_empty (support a) } then begin1043let b = pure { a.v empty } in1044assert { support a == empty };1045assert { forall c. a.v c = a.v empty by agree (support a) c empty };1046assert { a.v == (if b then all else empty) };1047Bool b1048end else begin1049let x = pure { pick (support a) } in1050let th, el = cofactors x a in1051cofactor_support x a th;1052cofactor_support x a el;1053assert { is_finite (support a) by subset (support a) a.dom };1054card_remove x (support a);1055assert { a.v == (fun c -> if mem x c then th.v c else el.v c)1056by forall c. (mem x c -> add x c == c)1057/\ (not mem x c -> remove x c == c) };1058Ite x th el1059end in1060any inspect ensures { result = w }10611062function upd (a: set CCube.t) (x: CVar.t) (b: bool) : set CCube.t =1063fun c' -> a (Map.set c' x b)10641065scope Vector Valid (418ms) (cvc4)1066type vector = {1067ghost mutable removed: set CVar.t;1068ghost mutable added: set CVar.t;1069ghost mutable subst: set CCube.t -> set CCube.t;1070} invariant { is_finite added }1071invariant { forall f d. is_finite d -> depends f d ->1072depends (subst f) (union added (diff d removed)) }1073by { removed = empty; added = empty; subst = fun x -> x }1074Valid (88ms) (cvc4)1075let create () : vector1076ensures { result.removed = empty }1077ensures { result.added = empty }1078ensures { result.subst = (fun x -> x) }1079= { removed = empty; added = empty; subst = fun x -> x }1080Valid (354ms) (colibri2 10) (cvc4) (split_vc 2) (depth 2)1081let add (vec:vector) (x:CVar.t) (f:t) : vector1082ensures { result.removed = add x vec.removed }1083ensures { result.added = union vec.added f.dom }1084ensures { result.subst = (fun a -> (fun c -> vec.subst (upd a x (f.v c)) c)) }1085= let ghost s = pure { fun a -> (fun c -> vec.subst (upd a x (f.v c)) c) } in1086let lemma inv (g: set CCube.t) (d: set CVar.t) (c1 c2: CCube.t)1087requires { is_finite d /\ depends g d }1088requires { agree (union (union vec.added f.dom) (diff d (add x vec.removed))) c1 c2 }1089ensures { s g c1 = s g c2 }1090= let b = f.v c1 in1091assert { f.v c2 = b by agree f.dom c1 c2 };1092let h = upd g x b in1093assert { depends h (remove x d)1094by forall y z. agree (remove x d) y z ->1095agree d (Map.set y x b) (Map.set z x b) };1096assert { depends (vec.subst h) (union vec.added (diff (remove x d) vec.removed)) };1097assert { agree (union vec.added (diff (remove x d) vec.removed)) c1 c2 } in1098{ removed = pure { add x vec.removed }; added = pure { union vec.added f.dom };1099subst = s }1100Valid (29ms) (colibri2)1101let compose (vec:vector) (a: t) : (res:t)1102ensures { res.dom = union vec.added (diff a.dom vec.removed) }1103ensures { res.v = vec.subst a.v }1104= { dom = pure { union vec.added (diff a.dom vec.removed) }; v = pure { vec.subst a.v };1105cube = empty }1106end11071108clone colibrilib.bdd.BDD {… begin (* cloned colibrilib.bdd.BDD *) Valid (20ms) (colibri2) lemma BDD.support_dom Valid (21ms) (colibri2) lemma BDD.support_exact Valid (21ms) (colibri2) lemma BDD.support_iff predicate BDD.is_cube t predicate BDD.is_support t Valid (17ms) (colibri2) lemma BDD.false_def Valid (19ms) (colibri2) lemma BDD.nb_nodes_nonneg Valid (19ms) (colibri2) lemma BDD.nb_nodes_canon end } with1109type t = t, function get_cube = get_cube, function support = support,1110lemma support_dom, lemma support_exact, lemma support_iff,1111constant dfalse = mfalse, lemma false_def, val dfalse = mk_false,1112val dtrue = dtrue, val is_equal = is_equal,1113val is_inter_empty = is_inter_empty, val dand = dand, val dor = dor,1114val dxor = dxor, val dexist = dexist, val dforall = dforall,1115val bdd_of_var = bdd_of_var, val bdd_not_of_var = bdd_not_of_var,1116val support_union = support_union, val dnot = dnot, val ite = ite,1117val cofactors = cofactors, val cofactor = cofactor,1118val invariant_outside_domain = invariant_outside_domain,1119val compose = compose, function nb_nodes = nb_nodes,1120function update = update, function upd = upd,1121lemma nb_nodes_nonneg, lemma nb_nodes_canon,1122val vars = vars, type inspect = inspect, val inspect = inspect,1123type Vector.vector = Vector.vector, val Vector.create = Vector.create,1124val Vector.add = Vector.add, val Vector.compose = Vector.compose1125end1126