Common — library colibrilib.models — module BDDModel

bdd.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.

651
module BDDModel
652
use int.Int
653
use set.Set
654
use set.Cardinal
655
use list.List
656
use list.Mem as Mem
657
use list.Distinct
658
use bool.Bool
659
use map.Map
660
use map.MapExt
661
use colibrilib.bdd.CVar
662
use colibrilib.bdd.CCube
663
clone 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.t

x and y give the same values to the variables of d

666
predicate
agree
(d: set CVar.t) (x y: CCube.t) =
667
forall i. mem i d -> (mem i x <-> mem i y)

f depends only on the variables of d

670
predicate
depends
(f: set CCube.t) (d: set CVar.t) =
671
forall x y. agree d x y -> f x = f y
672
673
type
t
= { ghost
dom
: set CVar.t; ghost
v
: set CCube.t; ghost
cube
: CCube.t }
674
invariant { is_finite dom /\ depends v dom } Valid (17ms) (colibri2)
675
by { dom = empty; v = empty; cube = empty }
676
677
function
get_cube
(b:t) : CCube.t = b.cube
678
Valid (20ms) (colibri2)
679
let ghost
dep
(a:t) (x y:CCube.t) : unit
680
requires { agree a.dom x y }
681
ensures { a.v x = a.v y }
682
= ()
683
684
function
support
(a:t) : set CVar.t =
685
fun x -> exists c. a.v (add x c) <> a.v (remove x c)
686
Valid (19ms) (colibri2)
687
let lemma
support_iff
(a:t) (x:CVar.t)
688
ensures { mem x (support a) <-> exists c. a.v (add x c) <> a.v (remove x c) }
689
= ()
690
Valid (793ms) (colibri2)
691
let lemma
support_dom
(a:t)
692
ensures { subset (support a) a.dom }
693
= assert { forall x c. not mem x a.dom -> agree a.dom (add x c) (remove x c) }

cardinal_remove, from cardinal_add

  Valid (18ms) (colibri2)
696
let ghost
card_remove
(x:CVar.t) (s:set CVar.t) : unit
697
requires { is_finite s /\ mem x s }
698
ensures { cardinal (remove x s) = cardinal s - 1 }
699
= let r = remove x s in
700
assert { is_finite r };
701
assert { not mem x r };
702
assert { add x r == s };
703
assert { cardinal (add x r) = cardinal r + 1 }

The differences of x and y in d

706
function
diffs
(d: set CVar.t) (x y: CCube.t) : set CVar.t =
707
fun i -> mem i d /\ (mem i x <-> not mem i y)
708
Valid (1.4s) (colibri2 15) (cvc4) (cvc5) (split_vc 3) (depth 2)
709
let rec lemma
exact_n
(a:t) (x y:CCube.t) (n:int)
710
requires { agree (support a) x y }
711
requires { n = cardinal (diffs a.dom x y) }
712
ensures { a.v x = a.v y }
713
variant { n }
714
= let d = diffs a.dom x y in
715
assert { is_finite d by subset d a.dom };
716
if n = 0 then begin
717
assert { is_empty d };
718
assert { agree a.dom x y }
719
end else begin
720
let i = pick d in
721
assert { mem i d };
722
assert { not mem i (support a) };
723
let x' = pure { if mem i y then add i x else remove i x } in
724
assert { a.v x' = a.v x by
725
a.v (add i x) = a.v (remove i x) /\
726
(x = add i x \/ x = remove i x)
727
by (mem i x -> add i x == x) /\ (not mem i x -> remove i x == x) };
728
assert { diffs a.dom x' y == remove i d };
729
card_remove i d;
730
exact_n a x' y (n - 1)
731
end
732
Valid (21ms) (colibri2)
733
let lemma
support_exact
(a:t) (x y:CCube.t)
734
ensures { (forall i. mem i (support a) -> (mem i x <-> mem i y)) -> a.v x = a.v y }
735
= if pure { agree (support a) x y } then exact_n a x y (cardinal (diffs a.dom x y))
736
737
predicate
is_cube
(b:t) = forall c. b.v c <-> inter c (support b) = get_cube b
738
739
predicate
is_support
(b:t) = is_cube b /\ get_cube b = support b
740
Valid (14ms) (colibri2)
741
let constant
mfalse
: t = { dom = empty; v = empty; cube = empty }
742
Valid (15ms) (colibri2)
743
lemma
false_def
: empty = mfalse.dom /\ mfalse.v = empty
744
Valid (16ms) (colibri2)
745
let
mk_false
() : t ensures { result = mfalse } = mfalse
746
Valid (22ms) (colibri2)
747
let
dtrue
() : t
748
ensures { result.dom = empty /\ result.v = all /\ get_cube result = empty }
749
= { dom = empty; v = all; cube = empty }
750
Valid (411ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
751
let
is_equal
(a:t) (b:t) : (result: bool, ghost c: CCube.t)
752
ensures { result = (forall c. a.v c = b.v c) }
753
ensures { not result -> subset c (union a.dom b.dom) /\ a.v c <> b.v c }
754
= let ghost w = pure { forall c. a.v c = b.v c } in
755
let r = any bool ensures { result = w } in
756
let ghost c =
757
if r then empty else begin
758
let c0 = any CCube.t ensures { a.v result <> b.v result } in
759
let c = inter c0 (union a.dom b.dom) in
760
assert { agree a.dom c c0 /\ agree b.dom c c0 };
761
c
762
end in
763
r, c
764
Valid (363ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
765
let
is_inter_empty
(a:t) (b:t) : (result: bool, ghost c: CCube.t)
766
ensures { result = (forall c. not (a.v c /\ b.v c)) }
767
ensures { not result -> subset c (union a.dom b.dom) /\ (a.v c /\ b.v c) }
768
= let ghost w = pure { forall c. not (a.v c /\ b.v c) } in
769
let r = any bool ensures { result = w } in
770
let ghost c =
771
if r then empty else begin
772
let c0 = any CCube.t ensures { a.v result /\ b.v result } in
773
let c = inter c0 (union a.dom b.dom) in
774
assert { agree a.dom c c0 /\ agree b.dom c c0 };
775
c
776
end in
777
r, c

The conjunction of two cubes on disjoint variables

  Valid (366ms) (colibri2 20) (cvc4 5) (split_vc 3) (depth 2)
780
let ghost
and_cube
(a b:t) (f: set CCube.t)
781
requires { f = inter a.v b.v }
782
requires { is_cube a /\ is_cube b }
783
requires { subset (get_cube a) (support a) /\ subset (get_cube b) (support b) }
784
requires { inter (support a) (support b) = empty }
785
ensures { forall x. (exists c. f (add x c) <> f (remove x c))
786
<-> mem x (union (support a) (support b)) }
787
ensures { forall c. f c <-> inter c (union (support a) (support b))
788
= union (get_cube a) (get_cube b) }
789
= let sa = support a in let sb = support b in
790
let ga = get_cube a in let gb = get_cube b in
791
assert { forall i. not (mem i sa /\ mem i sb)
792
by not mem i (inter sa sb) };
793
let c0 = union ga gb in
794
assert { inter c0 sa == ga /\ inter c0 sb == gb };
795
assert { a.v c0 /\ b.v c0 };
796
let lemma inside (x:CVar.t)
797
requires { mem x (union sa sb) }
798
ensures { f (add x c0) <> f (remove x c0) }
799
= if pure { mem x sa } then begin
800
assert { not mem x gb };
801
if pure { mem x ga } then begin
802
assert { add x c0 == c0 };
803
assert { inter (remove x c0) sa <> ga by not mem x (inter (remove x c0) sa) }
804
end else begin
805
assert { remove x c0 == c0 };
806
assert { inter (add x c0) sa <> ga by mem x (inter (add x c0) sa) }
807
end
808
end else begin
809
assert { not mem x ga };
810
if pure { mem x gb } then begin
811
assert { add x c0 == c0 };
812
assert { inter (remove x c0) sb <> gb by not mem x (inter (remove x c0) sb) }
813
end else begin
814
assert { remove x c0 == c0 };
815
assert { inter (add x c0) sb <> gb by mem x (inter (add x c0) sb) }
816
end
817
end in
818
let lemma outside (x:CVar.t) (c:CCube.t)
819
requires { not mem x (union sa sb) }
820
ensures { f (add x c) = f (remove x c) }
821
= assert { a.v (add x c) = a.v (remove x c) };
822
assert { b.v (add x c) = b.v (remove x c) } in
823
let lemma eqv (c:CCube.t)
824
ensures { f c <-> inter c (union sa sb) = union ga gb }
825
= SF.inter_union c sa sb ga gb;
826
assert { a.v c <-> inter c sa = ga };
827
assert { b.v c <-> inter c sb = gb } in
828
()
829
Valid (315ms) (colibri2 8) (cvc4 3) (split_vc 2) (depth 2)
830
let
dand
(a b: t) : t
831
ensures { result.dom = union a.dom b.dom }
832
ensures { result.v = inter a.v b.v }
833
ensures { is_cube a -> is_cube b ->
834
subset (get_cube a) (support a) -> subset (get_cube b) (support b) ->
835
inter (support a) (support b) = empty ->
836
is_cube result /\ get_cube result = union (get_cube a) (get_cube b) /\
837
support result = union (support a) (support b) }
838
= assert { forall c1 c2. agree (union a.dom b.dom) c1 c2 ->
839
agree a.dom c1 c2 /\ agree b.dom c1 c2 };
840
let r = { dom = pure { union a.dom b.dom }; v = pure { inter a.v b.v };
841
cube = pure { union (get_cube a) (get_cube b) } } in
842
if pure { is_cube a /\ is_cube b /\
843
subset (get_cube a) (support a) /\ subset (get_cube b) (support b) /\
844
inter (support a) (support b) = empty } then begin
845
and_cube a b r.v;
846
assert { support r == union (support a) (support b) }
847
end;
848
r
849
Valid (781ms) (colibri2 3) (cvc4) (split_vc 2) (depth 2)
850
let
dor
(a b: t) : t
851
ensures { result.dom = union a.dom b.dom }
852
ensures { result.v = union a.v b.v }
853
= { dom = pure { union a.dom b.dom }; v = pure { union a.v b.v }; cube = empty }
854
Valid (831ms) (colibri2 2) (cvc4) (split_vc) (depth 1)
855
let
dxor
(a b: t) : t
856
ensures { result.dom = union a.dom b.dom }
857
ensures { result.v = (fun c -> xorb (a.v c) (b.v c)) }
858
= { dom = pure { union a.dom b.dom }; v = pure { fun c -> xorb (a.v c) (b.v c) };
859
cube = empty }
860
861
function
update
(c:CCube.t) (s:CCube.t) (c':CCube.t) : CCube.t =
862
(fun i -> if s i then c' i else c i)
863
Valid (384ms) (colibri2 5) (cvc4 4) (split_vc 2) (depth 2)
864
let
dexist
(s:t) (a: t) : t
865
requires { is_support s }
866
ensures { result.dom = diff a.dom (support s) }
867
ensures { result.v = (fun c -> exists c'. a.v (update c (support s) c')) }
868
= let lemma pw (c1 c2 c':CCube.t)
869
requires { agree (diff a.dom (support s)) c1 c2 }
870
ensures { a.v (update c1 (support s) c') = a.v (update c2 (support s) c') }
871
= assert { agree a.dom (update c1 (support s) c') (update c2 (support s) c') };
872
dep a (update c1 (support s) c') (update c2 (support s) c') in
873
let ghost f = pure { fun c -> exists c'. a.v (update c (support s) c') } in
874
let lemma fd (c1 c2:CCube.t)
875
requires { agree (diff a.dom (support s)) c1 c2 }
876
ensures { f c1 = f c2 }
877
= assert { (exists c'. a.v (update c1 (support s) c')) <->
878
(exists c'. a.v (update c2 (support s) c')) } in
879
{ dom = pure { diff a.dom (support s) }; v = f; cube = empty }
880
Valid (384ms) (colibri2 5) (cvc4 4) (split_vc 2) (depth 2)
881
let
dforall
(s:t) (a: t) : t
882
requires { is_support s }
883
ensures { result.dom = diff a.dom (support s) }
884
ensures { result.v = (fun c -> forall c'. a.v (update c (support s) c')) }
885
= let lemma pw (c1 c2 c':CCube.t)
886
requires { agree (diff a.dom (support s)) c1 c2 }
887
ensures { a.v (update c1 (support s) c') = a.v (update c2 (support s) c') }
888
= assert { agree a.dom (update c1 (support s) c') (update c2 (support s) c') };
889
dep a (update c1 (support s) c') (update c2 (support s) c') in
890
let ghost f = pure { fun c -> forall c'. a.v (update c (support s) c') } in
891
let lemma fd (c1 c2:CCube.t)
892
requires { agree (diff a.dom (support s)) c1 c2 }
893
ensures { f c1 = f c2 }
894
= assert { (forall c'. a.v (update c1 (support s) c')) <->
895
(forall c'. a.v (update c2 (support s) c')) } in
896
{ dom = pure { diff a.dom (support s) }; v = f; cube = empty }
897
Valid (396ms) (colibri2 3) (cvc4) (split_vc) (depth 1)
898
let
bdd_of_var
(x: CVar.t) : t
899
ensures { result.dom = singleton x }
900
ensures { result.v = (fun c -> c x) }
901
ensures { get_cube result = singleton x }
902
= { dom = pure { singleton x }; v = pure { fun (c:CCube.t) -> c x }; cube = pure { singleton x } }
903
Valid (415ms) (colibri2 2) (cvc4 2) (split_vc) (depth 1)
904
let
bdd_not_of_var
(x: CVar.t) : t
905
ensures { result.dom = singleton x }
906
ensures { result.v = (fun c -> not (c x)) }
907
ensures { get_cube result = empty }
908
= { dom = pure { singleton x }; v = pure { fun (c:CCube.t) -> not (c x) }; cube = empty }
909
Valid (727ms) (colibri2 7) (cvc4 5) (split_vc 2) (depth 2)
910
let
support_union
(a b: t) : t
911
requires { is_support a /\ is_support b }
912
ensures { result.dom = union a.dom b.dom }
913
ensures { is_support result }
914
ensures { support result = union (support a) (support b) }
915
= let s = pure { union (support a) (support b) } in
916
assert { subset s (union a.dom b.dom) };
917
let r = { dom = pure { union a.dom b.dom }; v = pure { fun c -> subset s c };
918
cube = s } in
919
let lemma inside (x:CVar.t)
920
requires { mem x s }
921
ensures { r.v (add x s) <> r.v (remove x s) }
922
= assert { add x s == s } in
923
let lemma outside (x:CVar.t) (c:CCube.t)
924
requires { not mem x s }
925
ensures { r.v (add x c) = r.v (remove x c) }
926
= assert { subset s (add x c) <-> subset s (remove x c) } in
927
assert { support r == s };
928
assert { forall c. subset s c <-> inter c s == s };
929
r
930
Valid (142ms) (cvc4)
931
let
dnot
(a: t) : t
932
ensures { result.dom = a.dom }
933
ensures { result.v = complement a.v }
934
= { dom = a.dom; v = pure { complement a.v }; cube = empty }
935
Valid (46ms) (colibri2 7) (split_vc 2) (depth 2)
936
let
ite
(x:CVar.t) (a:t) (b:t) : t
937
ensures { result.dom = add x (union a.dom b.dom) }
938
ensures { result.v = (fun c -> if mem x c then a.v c else b.v c) }
939
= assert { forall c1 c2. agree (add x (union a.dom b.dom)) c1 c2 ->
940
(mem x c1 <-> mem x c2) /\ agree a.dom c1 c2 /\ agree b.dom c1 c2 };
941
{ dom = pure { add x (union a.dom b.dom) };
942
v = pure { fun c -> if mem x c then a.v c else b.v c }; cube = empty }
943
Valid (1.6s) (colibri2)
944
let
cofactors
(x:CVar.t) (a: t) : (pos:t, neg:t)
945
ensures { pos.dom = remove x a.dom }
946
ensures { neg.dom = remove x a.dom }
947
ensures { pos.v = (fun c -> a.v (add x c)) }
948
ensures { neg.v = (fun c -> a.v (remove x c)) }
949
= assert { forall c1 c2. agree (remove x a.dom) c1 c2 ->
950
agree a.dom (add x c1) (add x c2) /\
951
agree a.dom (remove x c1) (remove x c2) };
952
{ dom = pure { remove x a.dom }; v = pure { fun c -> a.v (add x c) }; cube = empty },
953
{ dom = pure { remove x a.dom }; v = pure { fun c -> a.v (remove x c) }; cube = empty }
954
Valid (85ms) (colibri2 4) (split_vc) (depth 1)
955
let
cofactor
(a:t) (b: t) : (cof:t)
956
requires { is_cube b }
957
ensures { cof.dom = diff a.dom (support b) }
958
ensures { cof.v = (fun c -> a.v (union (diff c (support b)) (get_cube b))) }
959
= assert { forall c1 c2. agree (diff a.dom (support b)) c1 c2 ->
960
agree a.dom (union (diff c1 (support b)) (get_cube b))
961
(union (diff c2 (support b)) (get_cube b)) };
962
{ dom = pure { diff a.dom (support b) };
963
v = pure { fun c -> a.v (union (diff c (support b)) (get_cube b)) }; cube = empty }
964
Valid (954ms) (cvc4)
965
let ghost function
invariant_outside_domain
(a:t) : unit
966
ensures { forall x y. (forall i. mem i a.dom -> mem i x = mem i y) -> a.v x = a.v y }
967
= ()
968
Valid (1.3s) (colibri2 8) (split_vc) (depth 1)
969
let
compose
(x:CVar.t) (f:t) (a: t) : (res:t)
970
ensures { res.dom = union f.dom (remove x a.dom) }
971
ensures { res.v = (fun c -> a.v (Map.set c x (f.v c))) }
972
= let lemma pw (c1 c2:CCube.t)
973
requires { agree (union f.dom (remove x a.dom)) c1 c2 }
974
ensures { a.v (Map.set c1 x (f.v c1)) = a.v (Map.set c2 x (f.v c2)) }
975
= assert { agree f.dom c1 c2 };
976
dep f c1 c2;
977
let b = f.v c1 in
978
assert { agree a.dom (Map.set c1 x b) (Map.set c2 x b) };
979
dep a (Map.set c1 x b) (Map.set c2 x b) in
980
{ dom = pure { union f.dom (remove x a.dom) };
981
v = pure { fun c -> a.v (Map.set c x (f.v c)) }; cube = empty }
982
983
function
nb_nodes
(a:t) : int = cardinal (support a)
984
Valid (21ms) (colibri2)
985
lemma
nb_nodes_nonneg
: forall a. 0 <= nb_nodes a
986
Valid (358ms) (cvc4)
987
let lemma
nb_nodes_canon
(a b:t)
988
ensures { a.v = b.v -> nb_nodes a = nb_nodes b }
989
= if pure { a.v = b.v } then assert { support a == support b }

The list of the elements of a finite set

  Valid (63ms) (colibri2 6) (split_vc) (depth 1)
992
let rec ghost
enum
(s: set CVar.t) : list CVar.t
993
requires { is_finite s }
994
ensures { forall x. Mem.mem x result <-> mem x s }
995
ensures { distinct result }
996
variant { cardinal s }
997
= if pure { is_empty s } then Nil
998
else begin
999
let x = pick s in
1000
assert { mem x s };
1001
card_remove x s;
1002
let r = enum (remove x s) in
1003
Cons x r
1004
end
1005
Valid (352ms) (cvc4)
1006
let
vars
(a:t) : list CVar.t
1007
ensures { forall x. Mem.mem x result <-> mem x (support a) }
1008
ensures { distinct result }
1009
= let ghost l = enum (support a) in
1010
any list CVar.t ensures { result = l }
1011
1012
type
inspect
=
Bool
bool |
Ite
CVar.t t t

The support of a cofactor

  Valid (369ms) (colibri2 3) (cvc4 2) (split_vc) (depth 1)
1015
let ghost
cofactor_support
(x:CVar.t) (a p:t) : unit
1016
requires { p.v = (fun c -> a.v (add x c)) \/ p.v = (fun c -> a.v (remove x c)) }
1017
ensures { subset (support p) (remove x (support a)) }
1018
= let lemma sub (y:CVar.t) (c:CCube.t)
1019
requires { p.v (add y c) <> p.v (remove y c) }
1020
ensures { y <> x /\ mem y (support a) }
1021
= assert { y <> x by y = x -> add x (add y c) == add x (remove y c)
1022
/\ remove x (add y c) == remove x (remove y c) };
1023
assert { add x (add y c) == add y (add x c)
1024
/\ add x (remove y c) == remove y (add x c) };
1025
assert { remove x (add y c) == add y (remove x c)
1026
/\ remove x (remove y c) == remove y (remove x c) } in
1027
()
1028
Valid (957ms) (colibri2 18) (cvc4 3) (cvc5) (split_vc 3) (depth 2)
1029
let
inspect
(a:t) : inspect
1030
ensures { match result with
1031
| Bool b -> a.v = (if b then all else empty) /\ support a = empty
1032
| Ite x th el ->
1033
mem x (support a) /\
1034
subset (support th) (remove x (support a)) /\
1035
subset (support el) (remove x (support a)) /\
1036
mem x a.dom /\
1037
subset th.dom (remove x a.dom) /\
1038
subset el.dom (remove x a.dom) /\
1039
nb_nodes th < nb_nodes a /\ nb_nodes el < nb_nodes a /\
1040
a.v = (fun c -> if mem x c then th.v c else el.v c)
1041
end }
1042
= let ghost w =
1043
if pure { is_empty (support a) } then begin
1044
let b = pure { a.v empty } in
1045
assert { support a == empty };
1046
assert { forall c. a.v c = a.v empty by agree (support a) c empty };
1047
assert { a.v == (if b then all else empty) };
1048
Bool b
1049
end else begin
1050
let x = pure { pick (support a) } in
1051
let th, el = cofactors x a in
1052
cofactor_support x a th;
1053
cofactor_support x a el;
1054
assert { is_finite (support a) by subset (support a) a.dom };
1055
card_remove x (support a);
1056
assert { a.v == (fun c -> if mem x c then th.v c else el.v c)
1057
by forall c. (mem x c -> add x c == c)
1058
/\ (not mem x c -> remove x c == c) };
1059
Ite x th el
1060
end in
1061
any inspect ensures { result = w }
1062
1063
function
upd
(a: set CCube.t) (x: CVar.t) (b: bool) : set CCube.t =
1064
fun c' -> a (Map.set c' x b)
1065
1066
scope Vector Valid (418ms) (cvc4)
1067
type
vector
= {
1068
ghost mutable
removed
: set CVar.t;
1069
ghost mutable
added
: set CVar.t;
1070
ghost mutable
subst
: set CCube.t -> set CCube.t;
1071
} invariant { is_finite added }
1072
invariant { forall f d. is_finite d -> depends f d ->
1073
depends (subst f) (union added (diff d removed)) }
1074
by { removed = empty; added = empty; subst = fun x -> x }
1075
Valid (88ms) (cvc4)
1076
let
create
() : vector
1077
ensures { result.removed = empty }
1078
ensures { result.added = empty }
1079
ensures { result.subst = (fun x -> x) }
1080
= { removed = empty; added = empty; subst = fun x -> x }
1081
Valid (354ms) (colibri2 10) (cvc4) (split_vc 2) (depth 2)
1082
let
add
(vec:vector) (x:CVar.t) (f:t) : vector
1083
ensures { result.removed = add x vec.removed }
1084
ensures { result.added = union vec.added f.dom }
1085
ensures { result.subst = (fun a -> (fun c -> vec.subst (upd a x (f.v c)) c)) }
1086
= let ghost s = pure { fun a -> (fun c -> vec.subst (upd a x (f.v c)) c) } in
1087
let lemma inv (g: set CCube.t) (d: set CVar.t) (c1 c2: CCube.t)
1088
requires { is_finite d /\ depends g d }
1089
requires { agree (union (union vec.added f.dom) (diff d (add x vec.removed))) c1 c2 }
1090
ensures { s g c1 = s g c2 }
1091
= let b = f.v c1 in
1092
assert { f.v c2 = b by agree f.dom c1 c2 };
1093
let h = upd g x b in
1094
assert { depends h (remove x d)
1095
by forall y z. agree (remove x d) y z ->
1096
agree d (Map.set y x b) (Map.set z x b) };
1097
assert { depends (vec.subst h) (union vec.added (diff (remove x d) vec.removed)) };
1098
assert { agree (union vec.added (diff (remove x d) vec.removed)) c1 c2 } in
1099
{ removed = pure { add x vec.removed }; added = pure { union vec.added f.dom };
1100
subst = s }
1101
Valid (29ms) (colibri2)
1102
let
compose
(vec:vector) (a: t) : (res:t)
1103
ensures { res.dom = union vec.added (diff a.dom vec.removed) }
1104
ensures { res.v = vec.subst a.v }
1105
= { dom = pure { union vec.added (diff a.dom vec.removed) }; v = pure { vec.subst a.v };
1106
cube = empty }
1107
end
1108
1109
clone 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
}
with
1110
type t = t, function get_cube = get_cube, function support = support,
1111
lemma support_dom, lemma support_exact, lemma support_iff,
1112
constant dfalse = mfalse, lemma false_def, val dfalse = mk_false,
1113
val dtrue = dtrue, val is_equal = is_equal,
1114
val is_inter_empty = is_inter_empty, val dand = dand, val dor = dor,
1115
val dxor = dxor, val dexist = dexist, val dforall = dforall,
1116
val bdd_of_var = bdd_of_var, val bdd_not_of_var = bdd_not_of_var,
1117
val support_union = support_union, val dnot = dnot, val ite = ite,
1118
val cofactors = cofactors, val cofactor = cofactor,
1119
val invariant_outside_domain = invariant_outside_domain,
1120
val compose = compose, function nb_nodes = nb_nodes,
1121
function update = update, function upd = upd,
1122
lemma nb_nodes_nonneg, lemma nb_nodes_canon,
1123
val vars = vars, type inspect = inspect, val inspect = inspect,
1124
type Vector.vector = Vector.vector, val Vector.create = Vector.create,
1125
val Vector.add = Vector.add, val Vector.compose = Vector.compose
1126
end