Common — library colibrilib.fp_conv — module Env
17
module Env
18
use int.Int
19
use int.Power
20
use option.Option
21
use colibrilib.ring.Atom
22
use colibrilib.fp.Ereal
23
use colibrilib.fbin.Fp
24
use colibrilib.fp_interval.Intervals
25
use colibrilib.fp_interval.FpInterval
26
use real.RealInfix
27
use list.List
28
use list.Mem as LM
29
use real.FromInt
30
use real.Truncate
31
use colibrilib.stda.StdA as A
32
use colibrilib.dyadic.Dyadic as D
33
use colibrilib.fp_dyadic.Rules as FD
34
use colibrilib.pow2r.Pow2r
35
use colibrilib.zinterval.Zi as Zi
36
use colibrilib.stdq.StdQ as Q
37
use colibrilib.zarith.Zbit as Zbit
38
use colibrilib.zbit.ZbitInt
39
use colibrilib.stdq.QBits as QB
40
use int.Abs as IA
41
use colibrilib.fp_interval.Export as IE

The generic environment of colibrilib/env.mlw: the model is immutable, one model for the run; alive is mutable (the backtracking of colibri2 changes it, no function here does); the writes change only the state of the propagation (writes { d.state }). This module gives the view of the floats of the model and of the state.

49
use export colibrilib.env.State
50
use export colibrilib.env.RealValue

The values of the float nodes, of the rounding mode nodes and of the Boolean nodes in a model

54
function
float_value
(md: model) (n: Atom.t) : Fp.t
55
function
mode_value
(md: model) (n: Atom.t) : mode
56
function
bool_value
(md: model) (n: Atom.t) : bool

The dyadic domain of each node (Dom_dyadic.dom), and the set of the values that the domain of the reals of each node (Dom_interval.dom: intervals and congruence) allows, in a state

61
function
dyadic_dom
(s: state) (n: Atom.t) : option D.t
62
function
real_dom
(s: state) (n: Atom.t) (x: real) : bool

The views of d

65
function
mf
(d: envp 'm) : Atom.t -> Fp.t = float_value d.model
66
function
mm
(d: envp 'm) : Atom.t -> mode = mode_value d.model
67
function
mb
(d: envp 'm) : Atom.t -> bool = bool_value d.model
68
function
mr
(d: envp 'm) : Atom.t -> real = real_value d.model
69
function
dy
(d: envp 'm) : Atom.t -> option D.t = dyadic_dom d.state
70
function
ri
(d: envp 'm) : Atom.t -> real -> bool = real_dom d.state

The update of a dyadic domain w by v changes nothing: the meet of Dom.Lattice.upd_dom is w, or v is the top, not set (Fp_conv_env.upddr)

75
predicate
dnoop
(w: option D.t) (v: D.t) =
76
match w with None -> v = D.top | Some w -> D.meet w v = w end

The format of the type of a float node: it does not depend on the model

80
function
fmt_of
(n:Atom.t) : format

Egraph.register

83
val
register
(d:env) (n:Atom.t) : unit
84
writes { d.state }

Egraph.get_dom of the domain of the floats (Dom_interval.dom)

87
val
get
(d: envp 'm) (n:Atom.t) : option dom
88
ensures { match result with
89
| Some v -> v.fm = fmt_of n /\ (live d -> mem (d.mf n) v)
90
| None -> true
91
end }

Dom_interval.upd_dom: the intersection with the domain of n; it raises Egraph.Contradiction when it is empty, so only when d is not live (the branches that are not live are not modelled)

96
val
upd
(d:env) (n:Atom.t) (v:dom) : unit
97
requires { live d -> mem (d.mf n) v }
98
writes { d.state }

Rounding_mode.get

101
val
mode
(d: envp 'm) (n:Atom.t) : option mode
102
ensures { match result with
103
| Some md -> live d -> d.mm n = md
104
| None -> true
105
end }

Boolean.is: the value of a Boolean node, when it is known

108
val
getb
(d: envp 'm) (n:Atom.t) : option bool
109
ensures { match result with
110
| Some b -> live d -> d.mb n = b
111
| None -> true
112
end }

Boolean.set_bool

115
val
setb
(d:env) (n:Atom.t) (b:bool) : unit
116
requires { live d -> d.mb n = b }
117
writes { d.state }

The domain of the reals

A union of intervals with algebraic bounds (Dom_interval.D.t): the empty list is the empty domain.

123
type
bnd
=
BInf
|
BLarge
A.t |
BStrict
A.t
124
type
riv
=
RSing
A.t |
RInter
bnd bnd
125
type
rdom
= list riv
126
127
predicate
rmem_lo
(x: real) (b: bnd) =
128
match b with BInf -> true | BLarge a -> A.real a <=. x | BStrict a -> A.real a <. x end
129
predicate
rmem_hi
(x: real) (b: bnd) =
130
match b with BInf -> true | BLarge a -> x <=. A.real a | BStrict a -> x <. A.real a end
131
predicate
rmem_iv
(x: real) (i: riv) =
132
match i with
133
| RSing a -> x = A.real a
134
| RInter lo hi -> rmem_lo x lo /\ rmem_hi x hi
135
end
136
predicate
rmem
(x: real) (l: rdom) =
137
match l with Nil -> false | Cons i l' -> rmem_iv x i \/ rmem x l' end

Egraph.get_dom of the domain of the reals (Dom_interval.dom)

140
val
getr
(d: envp 'm) (n:Atom.t) : option rdom
141
ensures { match result with
142
| Some v -> (live d -> rmem (d.mr n) v) /\ forall x. d.ri n x -> rmem x v
143
| None -> true
144
end }

The congruence part of Dom_interval.dom (Union.t.c, the class rem + div ℤ of colibrilib/congruence.mlw), as Cls div rem (NoCls: none; not an option of a pair: the provers did not get its components in the proof of RealDom.getc): every node of sort Int has Cls 1 0 (converter.ml, bounds_of_type)

151
type
ocls
=
NoCls
|
Cls
A.t A.t
152
153
val
getc
(d: envp 'm) (n:Atom.t) : ocls
154
ensures { match result with
155
| Cls dv rm ->
156
(live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv) /\
157
forall x. d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv
158
| NoCls -> true
159
end }

The class rem + div ℤ of the domain of n, for RealDom.getc

  Valid (47ms) (colibri2)
162
let
mk_cls
(ghost d: envp 'm) (ghost n: Atom.t) (dv rm: A.t) : ocls
163
requires { live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv }
164
requires { forall x. d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv }
165
ensures { match result with
166
| Cls dv rm ->
167
(live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv) /\
168
forall x. d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv
169
| NoCls -> true
170
end }
171
= Cls dv rm

The classes rem + div ℤ that updc drops: div not rational, or of more than 256 bits (numerator or denominator in lowest terms): the classes 2^-1074 ℤ of the doubles slow the LRA theory down (colibri/sat/propLnExp3.smt2: 1.2s without them, 7s with them)

177
predicate
dropped
(dv: A.t) =
178
forall q: Q.t. A.real dv = Q.real q ->
179
power 2 256 <= IA.abs (Q.num q) \/ power 2 256 <= Q.den q
180
Valid (58ms) (colibri2)
181
let
c_dropped
(dv: A.t) : bool
182
ensures { result <-> dropped dv }
183
= match A.view dv with
184
| A.Irr -> true
185
| A.Rat q ->
186
{proof…}
187
let lemma uniq (q': Q.t) : unit
188
requires { A.real dv = Q.real q' } ensures { q' = q }
189
= Q.equal_is_eq q' q in
190
{qed}
191
QB.big 256 q
192
end

Dom_interval.upd_dom of the class rem + div ℤ (Union.of_congruence); nothing when div is not rational

196
val
updc
(d:env) (n:Atom.t) (dv rm: A.t) : unit
197
requires { live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv }
198
writes { d.state }
199
ensures { (dropped dv \/
200
forall x. old d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv) ->
201
d.ri = old d.ri /\ d.dy = old d.dy }

Dom_interval.upd_dom: the intersection with the domain of n

204
val
updr
(d:env) (n:Atom.t) (v:rdom) : unit
205
requires { live d -> rmem (d.mr n) v }
206
writes { d.state }
207
ensures { (forall x. old d.ri n x -> rmem x v) -> d.ri = old d.ri /\ d.dy = old d.dy }

Egraph.merge of two real nodes

210
val
merge
(d:env) (a b:Atom.t) : unit
211
requires { live d -> d.mr a = d.mr b }
212
writes { d.state }

Egraph.is_equal of two nodes: equal in the model, of one sort

215
val
is_equal
(d: envp 'm) (a b: Atom.t) : bool
216
ensures { result -> fmt_of a = fmt_of b }
217
ensures { result -> live d -> d.mf a = d.mf b /\ d.mm a = d.mm b }

The operation of the terms of the kind k: fp.add (0), fp.mul (1), fp.div (2), fp.neg (3, of x alone)

221
function
kop
(k: int) (md: mode) (x y: t) : t =
222
if k = 0 then fp_add md x y else if k = 1 then fp_mul md x y
223
else if k = 2 then fp_div md x y else neg x

A term r = kop k m x y of the e–graph (m and y are x for fp.neg), as Conv.view reads it: same format, the value of its interpretation

228
predicate
kterm
(d: envp 'm) (k: int) (t: (Atom.t, Atom.t, Atom.t, Atom.t)) =
229
let (r, m, x, y) = t in
230
fmt_of r = fmt_of x /\ fmt_of y = fmt_of x /\
231
(live d -> fmt (d.mf r) = fmt_of r /\ fmt (d.mf x) = fmt_of x /\
232
fmt (d.mf y) = fmt_of y /\ d.mf r = kop k (d.mm m) (d.mf x) (d.mf y))

The terms of the kind k among the parents of the class of a (the Info domain of the theory of quantifiers); which ones is only a matter of completeness

237
val
kparents
(d: envp 'm) (k: int) (a: Atom.t) : list (Atom.t, Atom.t, Atom.t, Atom.t)
238
ensures { forall t. LM.mem t result -> kterm d k t }

The terms of the kind k in the class of a (its applications in the Info domain)

242
val
kapps
(d: envp 'm) (k: int) (a: Atom.t) : list (Atom.t, Atom.t, Atom.t, Atom.t)
243
ensures { forall t. LM.mem t result -> kterm d k t }

The relation database (agents/design/ordering-relations.md,

step B)

For two float nodes x and y of one format, an interval of zi y - zi x, zi the index with the two zeros merged: the order of the comparisons of IEEE 754 (Rules.zi_facts). It holds when neither is NaN. Implemented, with the same specifications, in RelDb.

252
function
zi
(x: t) : int = if index x < 0 then index x + 1 else index x
253
254
predicate
relh
(i: Zi.t) (x y: t) =
255
is_not_nan x -> is_not_nan y -> Zi.mem (zi y - zi x) i

What the database knows of x and y, of format fm (Zi.top if nothing)

259
val
getrel
(d: envp 'm) (fm: format) (x y: Atom.t) : Zi.t
260
ensures { live d -> relh result (d.mf x) (d.mf y) }

Add i to the relation of x and y, of format fm: when it changes, the propagators registered on the pair (Conv.wait_rel) and the Mono of the terms around x and y (Conv.wait_mono) are scheduled, and the result is the new relation

266
val
updrel
(d: env) (fm: format) (x y: Atom.t) (i: Zi.t) : option Zi.t
267
requires { live d -> relh i (d.mf x) (d.mf y) }
268
writes { d.state }
269
ensures { d.ri = old d.ri /\ d.dy = old d.dy }
270
ensures { match result with Some n -> live d -> relh n (d.mf x) (d.mf y) | None -> true end }

The operations monotonic in y for a fixed a: a + y (k = 0), a * y (k = 1), y / a (k = 2)

274
function
mop
(k: int) (md: mode) (a y: t) : t =
275
if k = 0 then fp_add md a y else if k = 1 then fp_mul md a y else fp_div md y a

The node of the term fp.neg a, a of format fm, registered

278
val
mk_neg
(d: env) (fm: format) (a: Atom.t) : Atom.t
279
ensures { live d -> d.mf result = neg (d.mf a) }
280
ensures { fmt_of result = fmt_of a }
281
writes { d.state }

Egraph.merge of two float nodes

284
val
mergef
(d:env) (a b:Atom.t) : unit
285
requires { live d -> d.mf a = d.mf b }
286
writes { d.state }

Egraph.get_dom of the dyadic domain (Dom_dyadic.dom): on a float node, the powers of 2 dividing its real when it is finite (colibrilib/fp_dyadic.mlw)

291
val
getd
(d: envp 'm) (n:Atom.t) : option D.t
292
ensures { result = d.dy n }
293
ensures { match result with
294
| Some v -> live d -> FD.fmem (d.mf n) v
295
| None -> true
296
end }

Dom_dyadic.upd_dom: the meet with the domain of n

299
val
updd
(d:env) (n:Atom.t) (v:D.t) : unit
300
requires { live d -> FD.fmem (d.mf n) v }
301
writes { d.state }

The dyadic domain of a real node (Dom_dyadic.dom too): the powers of 2 dividing its real

305
val
getdr
(d: envp 'm) (n:Atom.t) : option D.t
306
ensures { result = d.dy n }
307
ensures { match result with
308
| Some v -> live d -> D.mem (d.mr n) v
309
| None -> true
310
end }
311
312
val
upddr
(d:env) (n:Atom.t) (v:D.t) : unit
313
requires { live d -> D.mem (d.mr n) v }
314
writes { d.state }
315
ensures { dnoop (old d.dy n) v -> d.dy = old d.dy /\ d.ri = old d.ri }

2^k

  Valid (71ms) (colibri2)
318
let
a_pow2
(k: int) : A.t
319
ensures { A.real result = pow2r k }
320
= if 0 <= k then begin
321
{proof…} Zbit.lsl_mul 1 k; {qed}
322
A.of_bigint (lsl_int 1 k)
323
end else begin
324
{proof…} Zbit.lsl_mul 1 (-k); assert { 0 < power 2 (-k) }; {qed}
325
A.div (A.of_bigint 1) (A.of_bigint (lsl_int 1 (-k)))
326
end

The rounding of the real a in a mode, a zero being negative when a < 0. A rational is rounded exactly (Intf.of_q). An irrational a is bracketed by [n/2^k, (n+1)/2^k], n = floor (a 2^k) (A.round_down_to, no test of rationality), with k growing by 64 bits until the two ends round to the same float (Intf.round_bracket). The rounding boundaries (the floats, their midpoints, the overflow threshold) are multiples of half the least positive float, 2^-(emax + sb - 2): at that precision, a, being strictly between the two ends, rounds as any real between them (Intf.round_between); the loop is bounded.

  Valid (1.8s) (colibri2)
338
let
round_a
(fm: format) (m: mode) (a: A.t) : t
339
ensures { result = round_f fm m (A.real a <. 0.0) (Fin (A.real a)) }
340
= match A.view a with
341
| A.Rat q ->
342
let (n, d) = QB.num_den q in
343
{proof…}
344
assert { n < 0 <-> A.real a <. 0.0 };
345
{qed}
346
Fp.of_q fm m (n < 0) n d
347
| A.Irr ->
348
let kmax = lsl_int 1 (eb_v fm - 1) + sb_v fm - 2 in
349
{proof…} Zbit.lsl_mul 1 (eb fm - 1); {qed}
350
let rec bracket (k: int) : t
351
requires { 0 <= k }
352
variant { kmax - k }
353
ensures { result = round_f fm m (A.real a <. 0.0) (Fin (A.real a)) }
354
= let k = if k > kmax then kmax else k in
355
let p = lsl_int 1 k in
356
{proof…} Zbit.lsl_mul 1 k; assert { 0 < p }; {qed}
357
let qp = Q.of_bigint p in
358
let r = A.round_down_to a (Q.div (Q.of_bigint 1) qp) in
359
let n = Q.floor_z (Q.mul r qp) in
360
{proof…}
361
assert { Q.real r *. from_int p = from_int n };
362
assert { from_int n /. from_int p <=. A.real a <=.
363
from_int (n + 1) /. from_int p };
364
{qed}
365
if k = kmax then begin
366
{proof…}
367
let ghost qn = Q.div (Q.of_bigint n) (Q.of_bigint p) in
368
assert { A.real a <> Q.real qn };
369
assert { from_int n /. from_int (power 2 k) <. A.real a };
370
{qed}
371
Fp.round_between fm m n k
372
end else
373
match Fp.round_bracket fm m n p (n + 1) p with
374
| Some x -> x
375
| None -> bracket (k + 64)
376
end
377
in
378
bracket (sb_v fm - 1)
379
end

The float of the format fm that is the rounding up (resp. down) of the real a, a zero being negative when a < 0

  Valid (58ms) (colibri2)
383
let
ceil_f
(fm: format) (a: A.t) : t
384
ensures { result = round_f fm RTP (A.real a <. 0.0) (Fin (A.real a)) }
385
= round_a fm RTP a Valid (51ms) (colibri2)
386
let
floor_f
(fm: format) (a: A.t) : t
387
ensures { result = round_f fm RTN (A.real a <. 0.0) (Fin (A.real a)) }
388
= round_a fm RTN a

The value of a finite float, from its significand and exponent

  Valid (59ms) (colibri2)
391
let
to_a
(x: t) : A.t
392
requires { is_not_nan x /\ not (is_inf x) }
393
ensures { A.real result = to_real x }
394
= let (n, e) = to_dyadic x in
395
A.mul (A.of_bigint n) (a_pow2 e)
396
Valid (44ms) (colibri2)
397
let
a_eq
(a b: A.t) : bool
398
ensures { result <-> A.real a = A.real b }
399
= A.equal a b

The least (resp. greatest) finite float above (resp. below) a real r, strictly when strict, from the rounding f of r up (resp. down) and exact, whether f is finite of value r (Intf.float_lo, proved in fbin.mlw)

  Valid (111ms) (colibri2)
405
let
float_lo
(f: t) (strict exact: bool) : t
406
ensures { fmt result = fmt f }
407
ensures { forall r. f = round_f (fmt f) RTP (r <. 0.0) (Fin r) ->
408
(exact <-> is_not_nan f /\ not (is_inf f) /\ to_real f = r) ->
409
forall v. fmt v = fmt f -> is_not_nan v -> not (is_inf v) ->
410
(if strict then r <. to_real v else r <=. to_real v) -> le_dz result v }
411
= Fp.float_lo f strict exact Valid (113ms) (colibri2)
412
let
float_hi
(f: t) (strict exact: bool) : t
413
ensures { fmt result = fmt f }
414
ensures { forall r. f = round_f (fmt f) RTN (r <. 0.0) (Fin r) ->
415
(exact <-> is_not_nan f /\ not (is_inf f) /\ to_real f = r) ->
416
forall v. fmt v = fmt f -> is_not_nan v -> not (is_inf v) ->
417
(if strict then to_real v <. r else to_real v <=. r) -> le_dz v result }
418
= Fp.float_hi f strict exact

The bit–vectors

The integer nodes of the bit–vectors (bv2nat, RealValue.bv_to_int of the LRA theory) are real nodes.

The widths of the format (mw + 1 and ew of F)

  Valid (47ms) (colibri2)
426
let
fmt_eb
(fm: format) : int
427
ensures { result = eb fm }
428
= eb_v fm Valid (51ms) (colibri2)
429
let
fmt_sb
(fm: format) : int
430
ensures { result = sb fm }
431
= sb_v fm

The index of a float, and the float of an index

  Valid (46ms) (colibri2)
434
let
index_f
(x: t) : int
435
requires { is_not_nan x }
436
ensures { result = index x }
437
= index_v x Valid (46ms) (colibri2)
438
let
of_index_f
(fm: format) (i: int) : t
439
requires { - nb_sign fm <= i < nb_sign fm }
440
ensures { result = of_index fm i }
441
= of_index_v fm i
442
Valid (44ms) (colibri2)
443
let
a_of_int
(i: int) : A.t
444
ensures { A.real result = from_int i }
445
= A.of_bigint i Valid (43ms) (colibri2)
446
let
a_neg
(a: A.t) : A.t
447
ensures { A.real result = -. A.real a }
448
= A.neg a

A rational n / 2^k of A as (n, -k)

  Valid (65ms) (colibri2)
451
let
a_dyadic
(a: A.t) : option (int, int)
452
ensures { match result with
453
| Some (n, e) -> A.real a = from_int n *. pow2r e
454
| None -> true end }
455
= match A.view a with
456
| A.Irr -> None
457
| A.Rat q -> QB.dyadic q
458
end Valid (41ms) (colibri2)
459
let
a_ceil
(a: A.t) : int
460
ensures { result = ceil (A.real a) }
461
= A.ceil_z a Valid (38ms) (colibri2)
462
let
a_floor
(a: A.t) : int
463
ensures { result = floor (A.real a) }
464
= A.floor_z a Valid (42ms) (colibri2)
465
let
a_le
(a b: A.t) : bool
466
ensures { result <-> A.real a <=. A.real b }
467
= A.le a b

The special floats of a format: –inf, +inf, –0, +0 (F.get_special_values)

471
predicate
consts_ok
(fm: format) (c: (t, t, t, t)) =
472
let (minf, pinf, nz, pz) = c in
473
fmt minf = fm /\ fmt pinf = fm /\ fmt nz = fm /\ fmt pz = fm /\
474
specials4 fm minf pinf nz pz
475
Valid (370ms) (colibri2)
476
let
consts
(fm: format) : (t, t, t, t)
477
ensures { consts_ok fm result }
478
= {proof…} FpInterval.format_facts fm (); {qed}
479
(IE.minf fm, IE.pinf fm, IE.at_i fm (-1), IE.at_i fm 0)

The bounds of the positive subnormals and normals of a format: the first and the last subnormal, the first and the last normal (F.get_special_values)

484
predicate
classes_ok
(fm: format) (c: (t, t, t, t)) =
485
let (sf, sl, nf, nl) = c in
486
at_index fm sf 1 /\ at_index fm sl (power 2 (sb fm - 1) - 1) /\
487
at_index fm nf (power 2 (sb fm - 1)) /\ at_index fm nl (nb_sign fm - 2)
488
Valid (370ms) (colibri2)
489
let
classes
(fm: format) : (t, t, t, t)
490
ensures { classes_ok fm result }
491
= {proof…} FpInterval.format_facts fm (); {qed}
492
let h = binade_v fm in
493
(IE.at_i fm 1, IE.at_i fm (h - 1), IE.at_i fm h, IE.at_i fm (nb_sign_v fm - 2))

The bounds of x when x + y rounds into [lo, hi], in any mode (Intf.add_bounds, proved in fbin.mlw, AddBound)

  Valid (364ms) (colibri2 2) (split_vc) (depth 1)
497
let
add_bounds
(lo hi: t) : option (t, t)
498
ensures { match result with
499
| Some (a, b) -> fmt a = fmt lo /\ fmt b = fmt lo /\
500
forall m x y. fmt x = fmt lo -> fmt y = fmt lo ->
501
le_dz lo (fp_add m x y) -> le_dz (fp_add m x y) hi ->
502
le_dz a x /\ le_dz x b
503
| None -> true
504
end }
505
= {proof…}
506
assert { forall m x y [fp_add m x y]. fp_add m x y = fp_add_i m x y };
507
{qed}
508
Fp.add_bounds lo hi
509
end