Common — library colibrilib.dom_ring — module Env

The environment of the ring, trusted: the tables of colibri2 (backtrackable, see colibrilib/env.mlw), the product nodes, and the other domains.

17
module Env
18
use int.Int
19
use real.RealInfix
20
use list.List
21
use list.Mem
22
use option.Option
23
use colibrilib.ring.Atom
24
use colibrilib.ring.Mono
25
use colibrilib.stda.StdA as A
26
use colibrilib.ring.Export as R
27
use colibrilib.polynome.Lin as L
28
use colibrilib.env.Env
29
use colibrilib.spec.Opt

p is a normal form of the node n in the model of d

32
predicate
is_nf
(d:env) (n:Atom.t) (p:R.t) = live d -> d.m n = R.eval d.m p

The option --lra-no-ring is not given

35
val
use_ring
(d:env) : bool

The option --lra-ring-max-terms

38
val
max_terms
(d:env) : int

Monomial.node: the product node of the monomial m (a node that is not registered, never in the input: its value is the product)

42
val
product_node
(m:mono) : Atom.t
43
ensures { forall d: env. live d -> d.m result = evalm d.m m }

The node n has the value of the monomial m in every model

46
predicate
is_monomial
(n:Atom.t) (m:mono) =
47
forall d: env. live d -> d.m n = evalm d.m m

Monomial.monomial: the monomial of a product node

50
val
monomial
(n:Atom.t) : option mono
51
ensures { when_some (is_monomial n) result }

The normal forms: find_nf d n is the normal form of n

54
val
find_nf
(d:env) (n:Atom.t) : option R.t
55
ensures { when_some (is_nf d n) result }
56
57
val
set_nf
(d:env) (n:Atom.t) (p:R.t) : unit
58
writes { d.state }
59
requires { is_nf d n p }
60
61
val
remove_nf
(d:env) (n:Atom.t) : unit
62
writes { d.state }

The equality of two normal forms (only to avoid useless work)

65
val
same
(p q:R.t) : bool

n uses x in its normal form; the first time, the changes of the linear form of x call Export.changed d x

69
val
add_used
(d:env) (x n:Atom.t) : unit
70
writes { d.state }

The nodes that use x

73
val
used
(d:env) (x:Atom.t) : list Atom.t

The changes of the linear form of the product node call Export.solve_product d pm

77
val
watch_product
(d:env) (pm:Atom.t) : unit
78
writes { d.state }

Dom_polynome.assume_equality

81
val
assume_linear
(d:env) (n:Atom.t) (l:L.t) : unit
82
writes { d.state }
83
requires { live d -> d.m n = L.eval d.m l }

l is the linear form x itself (only to avoid useless work)

86
val
is_self
(l:L.t) (x:Atom.t) : bool

The ring is used only after the first product: before, the definitions wait

90
val
active
(d:env) : bool
91
val
activate
(d:env) : unit
92
writes { d.state }

The operations of the ring

95
type
op
=
Add
|
Sub
|
Neg
|
Mul
|
Div

The interpretation of the operations (a division by zero is not interpreted)

99
predicate
meaning
(m:Atom.t -> real) (o:op) (r:Atom.t) (l:list Atom.t) =
100
match o, l with
101
| Add, Cons a (Cons b Nil) -> m r = m a +. m b
102
| Sub, Cons a (Cons b Nil) -> m r = m a -. m b
103
| Neg, Cons a Nil -> m r = -. m a
104
| Mul, Cons a (Cons b Nil) -> m r = m a *. m b
105
| Div, Cons num (Cons den Nil) -> m den <> 0.0 -> m r *. m den = m num
106
| _ -> true
107
end

A ground term (Ground.t) and its node

110
type
ground
111
function
gnode
(g:ground) : Atom.t
112
113
val
node
(g:ground) : Atom.t
114
ensures { result = gnode g }

g has the meaning of the operation and arguments v in every model

117
predicate
interprets
(g:ground) (v:(op, list Atom.t)) =
118
let o, l = v in forall d: env. live d -> meaning d.m o (gnode g) l

The operation and the arguments of a ground term: a ground term has the value of its interpretation in every model

122
val
view
(g:ground) : option (op, list Atom.t)
123
ensures { when_some (interprets g) result }

The terms waiting for the activation

126
val
push_waiting
(d:env) (g:ground) : unit
127
writes { d.state }
128
val
waiting
(d:env) : list ground

The differences r = a - b waiting for the activation

131
val
push_sub
(d:env) (r a b:Atom.t) : unit
132
writes { d.state }
133
requires { live d -> d.m r = d.m a -. d.m b }
134
val
waiting_subs
(d:env) : list (Atom.t, Atom.t, Atom.t)
135
ensures { live d -> forall r a b. mem (r, a, b) result -> d.m r = d.m a -. d.m b }

The factorization

n = k * g * q, with g a product of atoms and q the normal form of a node m (up to a constant), is given to Dom_product.

The normal forms already seen

143
val
table_mem
(d:env) (p:R.t) : bool
144
val
table_add
(d:env) (p:R.t) (n:Atom.t) : unit
145
writes { d.state }

v = (n, c): n = c * q in the model of d, with c not zero

148
predicate
is_monic
(d:env) (q:R.t) (v:(Atom.t, A.t)) =
149
let n, c = v in
150
A.real c <> 0.0 /\ (live d -> d.m n = A.real c *. R.eval d.m q)

The monic forms: n = c * q

153
val
find_monic
(d:env) (q:R.t) : option (Atom.t, A.t)
154
ensures { when_some (is_monic d q) result }
155
156
val
set_monic
(d:env) (q:R.t) (n:Atom.t) (c:A.t) : unit
157
writes { d.state }
158
requires { A.real c <> 0.0 }
159
requires { live d -> d.m n = A.real c *. R.eval d.m q }

The factorizations waiting for a node of normal form q: n = k * g * q

163
predicate
pending_ok
(m:Atom.t -> real) (q:R.t) (l:list (Atom.t, A.t, mono)) =
164
forall n k g. mem (n, k, g) l -> m n = A.real k *. evalm m g *. R.eval m q
165
166
val
find_pending
(d:env) (q:R.t) : list (Atom.t, A.t, mono)
167
ensures { live d -> pending_ok d.m q result }
168
169
val
set_pending
(d:env) (q:R.t) (l:list (Atom.t, A.t, mono)) : unit
170
writes { d.state }
171
requires { live d -> pending_ok d.m q l }
172
173
val
remove_pending
(d:env) (q:R.t) : unit
174
writes { d.state }

n = k * g, given to Dom_product (sign and absolute value)

177
val
product
(d:env) (n:Atom.t) (k:A.t) (g:mono) : unit
178
writes { d.state }
179
requires { live d -> d.m n = A.real k *. evalm d.m g }
180
end