Common — library colibrilib.dom_modrw — module Key
9
module Key
10
use int.Int
11
use real.RealInfix
12
use real.Abs
13
use list.List
14
use option.Option
15
use colibrilib.ring.Atom
16
use colibrilib.stda.StdA as A
17
use colibrilib.q.Real as Real
18
use colibrilib.polynome.Assoc
19
use colibrilib.polynome.PT
20
use colibrilib.polynome.Lin
21
use colibrilib.polynome.ModRw
22
use colibrilib.product.Prod as P
23
use colibrilib.env.Env
24
use colibrilib.env.Interval
25
use colibrilib.env.Linear as L
26
use colibrilib.env.AbsProduct as AP
27
use colibrilib.spec.Opt
28
use colibrilib.spec.Test

The divisor: a constant |m|, or a node y with |den| = |y|

31
type
div
=
Cst
A.t |
Abs
Atom.t
32
33
function
dv
(m:Atom.t -> real) (v:div) : real =
34
match v with Cst c -> A.real c | Abs y -> m y end

(p, v) is a key of mod_e x den in the model m

37
predicate
is_key
(m:Atom.t -> real) (x den:Atom.t) (p:Lin.t) (v:div) =
38
m den <> 0.0 /\ abs (dv m v) = abs (m den) /\
39
Real.mod_e (m x) (m den) = Real.mod_e (eval m p) (dv m v)

The values of the atoms of l are integers

42
predicate
integers
(m:Atom.t -> real) (l:list binding) =
43
forall k. has k l -> Real.is_integer (m k)

The nodes a and b have the same absolute value

46
predicate
same_abs
(m:Atom.t -> real) (a b:Atom.t) = abs (m a) = abs (m b)

k is a key of mod_e x den in the model of d, reduced: a linear form in normal form, and for a constant divisor a constant of the polynomial in [0, |c|)

51
predicate
reduced_key
(d:env) (x den:Atom.t) (k:(Lin.t, div)) =
52
let p, v = k in
53
(live d -> is_key d.m x den p v) /\
54
match v with
55
| Cst c -> 0.0 <=. A.real p.cst <. A.real c
56
| Abs _ -> true
57
end

The atoms of l are integers

  Valid (31ms) (colibri2)
60
let rec
all_integer
(d:env) (l:list binding) : bool
61
variant { l }
62
ensures { decides_sound (live d -> integers d.m l) result }
63
= match l with
64
| Nil -> true
65
| Cons (k, _) r -> is_integer d k && all_integer d r
66
end

A node y with |den| = |y|: den = ±y, or the product |y|

  Valid (634ms) (colibri2)
69
let partial
abs_node
(d:env) (den:Atom.t) : Atom.t
70
ensures { live d -> same_abs d.m result den }
71
= let partial from_product () : Atom.t
72
ensures { live d -> same_abs d.m result den }
73
= match AP.get_repr d den with
74
| Some a -> (match P.is_one_node a with Some y -> y | None -> den end)
75
| None -> den
76
end
77
in
78
let y = match L.get_repr d den with
79
| Some q ->
80
match is_pm_node q with
81
| Some y -> if is_equal d y den then from_product () else y
82
| None -> from_product ()
83
end
84
| None -> from_product ()
85
end
86
in
87
find_def d y

The key of mod_e x den

  Valid (1.1s) (colibri2 18) (cvc4 7) (split_vc 12) (depth 3)
90
let partial
key
(d:env) (x den:Atom.t) : option (Lin.t, div)
91
ensures { when_some (reduced_key d x den) result }
92
= let p = match L.get_repr d x with
93
| Some p -> p
94
| None -> monome (A.of_int 1) (find_def d x)
95
end
96
in
97
match value d den with
98
| Some c ->
99
if not (A.equal c (A.of_int 0)) && all_integer d (atoms p) then begin
100
let p' = reduce_cst p c in
101
assert { live d -> integer_atoms p d.m };
102
let ac = A.abs c in
103
let lemma l () : unit
104
ensures { Real.mod_e (eval d.m p') (A.real c) = Real.mod_e (eval d.m p') (A.real ac) }
105
= mod_abs (eval d.m p') (A.real c) (A.real ac) in
106
assert { 0.0 <=. A.real p'.cst <. A.real ac };
107
assert { live d -> is_key d.m x den p' (Cst ac) };
108
assert { reduced_key d x den (p', Cst ac) };
109
Some (p', Cst ac)
110
end else None
111
| None ->
112
if is_not_zero d den then begin
113
let y = abs_node d den in
114
let p' = reduce_node p y in
115
let lemma l () : unit
116
requires { live d }
117
ensures { Real.mod_e (eval d.m p') (d.m den) = Real.mod_e (eval d.m p') (d.m y) }
118
= mod_abs (eval d.m p') (d.m den) (d.m y) in
119
let lemma k () : unit
120
requires { live d }
121
ensures { is_key d.m x den p' (Abs y) }
122
= assert { Real.mod_e (eval d.m p) (d.m den) = Real.mod_e (eval d.m p') (d.m den) } in
123
Some (p', Abs y)
124
end else None
125
end
126
127
end