library colibrilib.bdd — module BDDmodule BDD19
Stay abstract
use set.Set20use int.Int21use list.List22use list.Mem23use list.Distinct24use CVar25use CCube26use bool.Bool2728type t = abstract {29dom: Set.set CVar.t;30v: Set.set CCube.t;31}3233function get_cube (b:t) : CCube.t34
The variables of the BDD (Cudd.Bdd.support): exactly the variables the function depends on; dom is only an over–approximation
function support (a:t) : Set.set CVar.t39axiom support_dom: forall a. Set.subset (support a) a.dom40axiom support_exact: forall a x y.41(forall i. Set.mem i (support a) -> (Set.mem i x <-> Set.mem i y)) -> a.v x = a.v y42axiom support_iff: forall a x.43Set.mem x (support a) <-> exists c. a.v (Set.add x c) <> a.v (Set.remove x c)44
A cube: true exactly on the valuations equal to get_cube on the support
predicate is_cube (b:t) = forall c. b.v c <-> Set.inter c (support b) = get_cube b47
A cube of positive literals
predicate is_support (b:t) = is_cube b /\ get_cube b = support b5051constant dfalse: t52axiom false_def: Set.empty = dfalse.dom /\ dfalse.v = Set.empty53val dfalse () : t ensures { result = dfalse }5455val dtrue () : t ensures { result.dom = Set.empty /\ result.v = Set.all /\ get_cube result = Set.empty }5657val is_equal (a:t) (b:t) : (result: bool, ghost c: CCube.t)58ensures { result = (forall c. a.v c = b.v c)}59ensures { not result ->60(Set.subset c (Set.union a.dom b.dom)) /\61a.v c <> b.v c }6263val is_inter_empty (a:t) (b:t) : (result: bool, ghost c: CCube.t)64ensures { result = (forall c. not (a.v c /\ b.v c)) }65ensures { not result ->66((Set.subset c (Set.union a.dom b.dom)) /\67(a.v c /\ b.v c)) }686970val dand (a b: t) : t71ensures { result.dom = Set.union a.dom b.dom }72ensures { result.v = Set.inter a.v b.v }73
the conjunction of two cubes on disjoint variables is a cube
ensures { is_cube a -> is_cube b ->75Set.subset (get_cube a) (support a) -> Set.subset (get_cube b) (support b) ->76Set.inter (support a) (support b) = Set.empty ->77is_cube result /\ get_cube result = Set.union (get_cube a) (get_cube b) /\78support result = Set.union (support a) (support b) }7980val dor (a b: t) : t81ensures { result.dom = Set.union a.dom b.dom }82ensures { result.v = Set.union a.v b.v }8384val dxor (a b: t) : t85ensures { result.dom = Set.union a.dom b.dom }86ensures { result.v = (fun c -> xorb (a.v c) (b.v c)) }8789(*function update (c:CCube.t) (s:CCube.t) (c':CCube.t) : CCube.t = (Set.union (Set.diff c (Set.complement s)) (Set.diff c' (Set.complement s)))*)9091function update (c:CCube.t) (s:CCube.t) (c':CCube.t) : CCube.t =92(fun i -> if s i then c' i else c i)9394val dexist (s:t) (a: t) : t95requires { is_support s }96ensures { result.dom = Set.diff a.dom (support s) }97ensures { result.v = (fun c -> exists c'. a.v (update c (support s) c')) }9899val dforall (s:t) (a: t) : t100requires { is_support s }101ensures { result.dom = Set.diff a.dom (support s) }102ensures { result.v = (fun c -> forall c'. a.v (update c (support s) c')) }103104105val bdd_of_var (v: CVar.t) : t106ensures { result.dom = Set.singleton v }107ensures { result.v = (fun c -> c v) }108ensures { get_cube result = Set.singleton v }109
The negation of a variable (Cudd.Bdd.dnot of Cudd.Bdd.ithvar)
val bdd_not_of_var (v: CVar.t) : t112ensures { result.dom = Set.singleton v }113ensures { result.v = (fun c -> not (c v)) }114ensures { get_cube result = Set.empty }115
The cube of the union of the supports (Cudd.Bdd.support_union)
val support_union (a b: t) : t118requires { is_support a /\ is_support b }119ensures { result.dom = Set.union a.dom b.dom }120ensures { is_support result }121ensures { support result = Set.union (support a) (support b) }122123val dnot (a: t) : t124ensures { result.dom = a.dom }125ensures { result.v = Set.complement a.v }126127val ite (x:CVar.t) (a:t) (b:t) : t128ensures { result.dom = Set.add x (Set.union a.dom b.dom) }129ensures { result.v = (fun c -> if Set.mem x c then a.v c else b.v c) }130131val cofactors (x:CVar.t) (a: t) : (pos:t,neg:t)132ensures { pos.dom = Set.remove x a.dom }133ensures { neg.dom = Set.remove x a.dom }134ensures { pos.v = (fun c -> a.v (Set.add x c)) }135ensures { neg.v = (fun c -> a.v (Set.remove x c)) }136137val cofactor (a:t) (b: t) : (cof:t)138requires { is_cube b }139ensures { cof.dom = Set.diff a.dom (support b) }140ensures { cof.v = (fun c -> a.v (Set.union (Set.diff c (support b)) (get_cube b))) }141142val ghost function invariant_outside_domain (a:t) : unit143ensures { forall x y. (forall i. Set.mem i a.dom -> Set.mem i x = Set.mem i y) -> a.v x = a.v y }144145val compose (x:CVar.t) (f:t) (a: t) : (res:t)146ensures { res.dom = Set.union f.dom (Set.remove x a.dom) }147ensures { res.v = (fun c -> a.v (Map.set c x (f.v c))) }148
Number of nodes of the BDD, for termination
function nb_nodes (a:t) : int152axiom nb_nodes_nonneg: forall a. 0 <= nb_nodes a153
The BDDs of Cudd are canonical: the number of nodes only depends on the function
axiom nb_nodes_canon: forall a b. a.v = b.v -> nb_nodes a = nb_nodes b157158159val vars (a:t) : list CVar.t160ensures { forall x. Mem.mem x result <-> Set.mem x (support a) }161ensures { Distinct.distinct result }162163type inspect = Bool bool | Ite CVar.t t t164
Top node of the BDD (Cudd.Bdd.inspect)
val inspect (a:t) : inspect167ensures { match result with168| Bool b -> a.v = (if b then Set.all else Set.empty) /\ support a = Set.empty169| Ite x th el ->170Set.mem x (support a) /\171Set.subset (support th) (Set.remove x (support a)) /\172Set.subset (support el) (Set.remove x (support a)) /\173Set.mem x a.dom /\174Set.subset th.dom (Set.remove x a.dom) /\175Set.subset el.dom (Set.remove x a.dom) /\176nb_nodes th < nb_nodes a /\ nb_nodes el < nb_nodes a /\177a.v = (fun c -> if Set.mem x c then th.v c else el.v c)178end }179
a with the variable x set to b
function upd (a: Set.set CCube.t) (x: CVar.t) (b: bool) : Set.set CCube.t =182fun c' -> a (Map.set c' x b)183184scope Vector185type vector = abstract {186mutable removed: Set.set CVar.t;187mutable added: Set.set CVar.t;188mutable subst: Set.set CCube.t -> Set.set CCube.t;189190}191192val create () : vector193ensures { result.removed = Set.empty }194ensures { result.added = Set.empty }195ensures { result.subst = (fun x -> x) }196197198val add (v:vector) (x:CVar.t) (f:t) : vector199requires { not (Set.mem x v.removed)}200ensures { result.removed = Set.add x v.removed }201ensures { result.added = Set.union v.added f.dom }202ensures { result.subst = (fun a -> (fun c -> v.subst (upd a x (f.v c)) c)) }203204val compose (v:vector) (a: t) : (res:t)205ensures { res.dom = Set.union v.added (Set.diff a.dom v.removed) }206ensures { res.v = v.subst a.v }207end208209210end211