Common — library colibrilib.spec — module Sound

The shapes of the specifications of the abstract domains, as higher–order predicates: the review of an exported function only needs to read which shape, which membership and which operation.

mem x d is the membership of a value x in an abstract value d.

6
module Sound
7
use option.Option

Sound forward propagation of a unary operation: the image by f of a is in r

11
predicate
sound1
(mem: 'v -> 'd -> bool) (f: 'v -> 'v) (a r: 'd) =
12
forall x. mem x a -> mem (f x) r

Sound forward propagation of a binary operation: the image by f of a and b is in r

16
predicate
sound2
(mem: 'v -> 'd -> bool) (f: 'v -> 'v -> 'v) (a b r: 'd) =
17
forall x y. mem x a -> mem y b -> mem (f x y) r

Complete forward propagation of a unary operation: every element of r is the image by f of an element of a

21
predicate
complete1
(mem: 'v -> 'd -> bool) (f: 'v -> 'v) (a r: 'd) =
22
forall s. mem s r -> exists x. mem x a /\ s = f x

Complete forward propagation of a binary operation

25
predicate
complete2
(mem: 'v -> 'd -> bool) (f: 'v -> 'v -> 'v) (a b r: 'd) =
26
forall s. mem s r -> exists x y. mem x a /\ mem y b /\ s = f x y

Sound backward propagation of a unary operation: the x of a with f x in c are in r

30
predicate
back1
(mem: 'v -> 'd -> bool) (f: 'v -> 'v) (a c r: 'd) =
31
forall x. mem x a -> mem (f x) c -> mem x r

Sound backward propagation on the first argument of a binary operation: the x of a with f x y in c for a y of b are in r; None when there is no such x

36
predicate
back2
(mem: 'v -> 'd -> bool) (f: 'v -> 'v -> 'v) (a b c: 'd)
37
(r: option 'd) =
38
forall x y. mem x a -> mem y b -> mem (f x y) c ->
39
match r with None -> false | Some r -> mem x r end

Sound backward propagation of a unary operation without a domain for the argument: the x with f x in c are in r

43
predicate
preimage1
(mem: 'v -> 'd -> bool) (f: 'v -> 'v) (c r: 'd) =
44
forall x. mem (f x) c -> mem x r

As preimage1, None when there is no such x

47
predicate
preimage1_opt
(mem: 'v -> 'd -> bool) (f: 'v -> 'v) (c: 'd)
48
(r: option 'd) =
49
forall x. mem (f x) c -> match r with None -> false | Some r -> mem x r end

The x of a that satisfy p are in r; None when there is none

53
predicate
restrict
(mem: 'v -> 'd -> bool) (p: 'v -> bool) (a: 'd)
54
(r: option 'd) =
55
forall x. mem x a -> p x -> match r with None -> false | Some r -> mem x r end

As sound2, for the arguments that satisfy ok (a division by a nonzero number)

59
predicate
sound2_on
(mem: 'v -> 'd -> bool) (ok: 'v -> 'v -> bool)
60
(f: 'v -> 'v -> 'v) (a b r: 'd) =
61
forall x y. mem x a -> mem y b -> ok x y -> mem (f x y) r

The abstract value r is exactly the set p

64
predicate
exact
(mem: 'v -> 'd -> bool) (p: 'v -> bool) (r: 'd) =
65
forall x. mem x r <-> p x

r is exactly the set p, None when p is empty

68
predicate
exact_opt
(mem: 'v -> 'd -> bool) (p: 'v -> bool) (r: option 'd) =
69
forall x. p x <-> match r with None -> false | Some r -> mem x r end

The abstract value r contains the set p

72
predicate
includes
(mem: 'v -> 'd -> bool) (p: 'v -> bool) (r: 'd) =
73
forall x. p x -> mem x r

r is the smallest abstract value that contains a and b

76
predicate
join
(mem: 'v -> 'd -> bool) (a b r: 'd) =
77
(forall x. mem x a \/ mem x b -> mem x r) /\
78
(forall c. (forall x. mem x a -> mem x c) -> (forall x. mem x b -> mem x c) ->
79
forall x. mem x r -> mem x c)
80
end