Common — library colibrilib.bdd — module BDD
19
module BDD

Stay abstract

20
use set.Set
21
use int.Int
22
use list.List
23
use list.Mem
24
use list.Distinct
25
use CVar
26
use CCube
27
use bool.Bool
28
29
type
t
= abstract {
30
dom
: Set.set CVar.t;
31
v
: Set.set CCube.t;
32
}
33
34
function
get_cube
(b:t) : CCube.t

The variables of the BDD (Cudd.Bdd.support): exactly the variables the function depends on; dom is only an over–approximation

39
function
support
(a:t) : Set.set CVar.t
40
axiom
support_dom
: forall a. Set.subset (support a) a.dom
41
axiom
support_exact
: forall a x y.
42
(forall i. Set.mem i (support a) -> (Set.mem i x <-> Set.mem i y)) -> a.v x = a.v y
43
axiom
support_iff
: forall a x.
44
Set.mem x (support a) <-> exists c. a.v (Set.add x c) <> a.v (Set.remove x c)

A cube: true exactly on the valuations equal to get_cube on the support

47
predicate
is_cube
(b:t) = forall c. b.v c <-> Set.inter c (support b) = get_cube b

A cube of positive literals

50
predicate
is_support
(b:t) = is_cube b /\ get_cube b = support b
51
52
constant
dfalse
: t
53
axiom
false_def
: Set.empty = dfalse.dom /\ dfalse.v = Set.empty
54
val
dfalse
() : t ensures { result = dfalse }
55
56
val
dtrue
() : t ensures { result.dom = Set.empty /\ result.v = Set.all /\ get_cube result = Set.empty }
57
58
val
is_equal
(a:t) (b:t) : (result: bool, ghost c: CCube.t)
59
ensures { result = (forall c. a.v c = b.v c)}
60
ensures { not result ->
61
(Set.subset c (Set.union a.dom b.dom)) /\
62
a.v c <> b.v c }
63
64
val
is_inter_empty
(a:t) (b:t) : (result: bool, ghost c: CCube.t)
65
ensures { result = (forall c. not (a.v c /\ b.v c)) }
66
ensures { not result ->
67
((Set.subset c (Set.union a.dom b.dom)) /\
68
(a.v c /\ b.v c)) }
69
70
71
val
dand
(a b: t) : t
72
ensures { result.dom = Set.union a.dom b.dom }
73
ensures { result.v = Set.inter a.v b.v }

the conjunction of two cubes on disjoint variables is a cube

75
ensures { is_cube a -> is_cube b ->
76
Set.subset (get_cube a) (support a) -> Set.subset (get_cube b) (support b) ->
77
Set.inter (support a) (support b) = Set.empty ->
78
is_cube result /\ get_cube result = Set.union (get_cube a) (get_cube b) /\
79
support result = Set.union (support a) (support b) }
80
81
val
dor
(a b: t) : t
82
ensures { result.dom = Set.union a.dom b.dom }
83
ensures { result.v = Set.union a.v b.v }
84
85
val
dxor
(a b: t) : t
86
ensures { result.dom = Set.union a.dom b.dom }
87
ensures { result.v = (fun c -> xorb (a.v c) (b.v c)) }
89
90
(*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)))*)
91
92
function
update
(c:CCube.t) (s:CCube.t) (c':CCube.t) : CCube.t =
93
(fun i -> if s i then c' i else c i)
94
95
val
dexist
(s:t) (a: t) : t
96
requires { is_support s }
97
ensures { result.dom = Set.diff a.dom (support s) }
98
ensures { result.v = (fun c -> exists c'. a.v (update c (support s) c')) }
99
100
val
dforall
(s:t) (a: t) : t
101
requires { is_support s }
102
ensures { result.dom = Set.diff a.dom (support s) }
103
ensures { result.v = (fun c -> forall c'. a.v (update c (support s) c')) }
104
105
106
val
bdd_of_var
(v: CVar.t) : t
107
ensures { result.dom = Set.singleton v }
108
ensures { result.v = (fun c -> c v) }
109
ensures { get_cube result = Set.singleton v }

The negation of a variable (Cudd.Bdd.dnot of Cudd.Bdd.ithvar)

112
val
bdd_not_of_var
(v: CVar.t) : t
113
ensures { result.dom = Set.singleton v }
114
ensures { result.v = (fun c -> not (c v)) }
115
ensures { get_cube result = Set.empty }

The cube of the union of the supports (Cudd.Bdd.support_union)

118
val
support_union
(a b: t) : t
119
requires { is_support a /\ is_support b }
120
ensures { result.dom = Set.union a.dom b.dom }
121
ensures { is_support result }
122
ensures { support result = Set.union (support a) (support b) }
123
124
val
dnot
(a: t) : t
125
ensures { result.dom = a.dom }
126
ensures { result.v = Set.complement a.v }
127
128
val
ite
(x:CVar.t) (a:t) (b:t) : t
129
ensures { result.dom = Set.add x (Set.union a.dom b.dom) }
130
ensures { result.v = (fun c -> if Set.mem x c then a.v c else b.v c) }
131
132
val
cofactors
(x:CVar.t) (a: t) : (pos:t,neg:t)
133
ensures { pos.dom = Set.remove x a.dom }
134
ensures { neg.dom = Set.remove x a.dom }
135
ensures { pos.v = (fun c -> a.v (Set.add x c)) }
136
ensures { neg.v = (fun c -> a.v (Set.remove x c)) }
137
138
val
cofactor
(a:t) (b: t) : (cof:t)
139
requires { is_cube b }
140
ensures { cof.dom = Set.diff a.dom (support b) }
141
ensures { cof.v = (fun c -> a.v (Set.union (Set.diff c (support b)) (get_cube b))) }
142
143
val ghost function
invariant_outside_domain
(a:t) : unit
144
ensures { forall x y. (forall i. Set.mem i a.dom -> Set.mem i x = Set.mem i y) -> a.v x = a.v y }
145
146
val
compose
(x:CVar.t) (f:t) (a: t) : (res:t)
147
ensures { res.dom = Set.union f.dom (Set.remove x a.dom) }
148
ensures { res.v = (fun c -> a.v (Map.set c x (f.v c))) }

Number of nodes of the BDD, for termination

152
function
nb_nodes
(a:t) : int
153
axiom
nb_nodes_nonneg
: forall a. 0 <= nb_nodes a

The BDDs of Cudd are canonical: the number of nodes only depends on the function

157
axiom
nb_nodes_canon
: forall a b. a.v = b.v -> nb_nodes a = nb_nodes b
158
159
160
val
vars
(a:t) : list CVar.t
161
ensures { forall x. Mem.mem x result <-> Set.mem x (support a) }
162
ensures { Distinct.distinct result }
163
164
type
inspect
=
Bool
bool |
Ite
CVar.t t t

Top node of the BDD (Cudd.Bdd.inspect)

167
val
inspect
(a:t) : inspect
168
ensures { match result with
169
| Bool b -> a.v = (if b then Set.all else Set.empty) /\ support a = Set.empty
170
| Ite x th el ->
171
Set.mem x (support a) /\
172
Set.subset (support th) (Set.remove x (support a)) /\
173
Set.subset (support el) (Set.remove x (support a)) /\
174
Set.mem x a.dom /\
175
Set.subset th.dom (Set.remove x a.dom) /\
176
Set.subset el.dom (Set.remove x a.dom) /\
177
nb_nodes th < nb_nodes a /\ nb_nodes el < nb_nodes a /\
178
a.v = (fun c -> if Set.mem x c then th.v c else el.v c)
179
end }

a with the variable x set to b

182
function
upd
(a: Set.set CCube.t) (x: CVar.t) (b: bool) : Set.set CCube.t =
183
fun c' -> a (Map.set c' x b)
184
185
scope Vector
186
type
vector
= abstract {
187
mutable
removed
: Set.set CVar.t;
188
mutable
added
: Set.set CVar.t;
189
mutable
subst
: Set.set CCube.t -> Set.set CCube.t;
190
191
}
192
193
val
create
() : vector
194
ensures { result.removed = Set.empty }
195
ensures { result.added = Set.empty }
196
ensures { result.subst = (fun x -> x) }
197
198
199
val
add
(v:vector) (x:CVar.t) (f:t) : vector
200
requires { not (Set.mem x v.removed)}
201
ensures { result.removed = Set.add x v.removed }
202
ensures { result.added = Set.union v.added f.dom }
203
ensures { result.subst = (fun a -> (fun c -> v.subst (upd a x (f.v c)) c)) }
204
205
val
compose
(v:vector) (a: t) : (res:t)
206
ensures { res.dom = Set.union v.added (Set.diff a.dom v.removed) }
207
ensures { res.v = v.subst a.v }
208
end
209
210
211
end