Common — library colibrilib.fp_conv — module Rules

The propagators

1460
module Rules
1461
use int.Int
1462
use int.Power
1463
use real.Truncate
1464
use list.List
1465
use option.Option
1466
use colibrilib.ring.Atom
1467
use colibrilib.fbin.Fp
1468
use colibrilib.fp_facts.Facts
1469
use colibrilib.fp.Ereal
1470
use colibrilib.fp_interval.Intervals
1471
use colibrilib.fp_interval.FpInterval
1472
use colibrilib.fp_interval.Rules as IR
1473
use colibrilib.fp_interval.Export as FE
1474
use real.RealInfix
1475
use real.FromInt
1476
use Env
1477
use RealConv
1478
use BvConv
1479
use colibrilib.dyadic.Dyadic as D
1480
use colibrilib.fp_dyadic.Rules as FD
1481
use colibrilib.pow2r.Pow2r
1482
use colibrilib.dv.Dv
1483
use int.EuclideanDivision as E
1484
use colibrilib.zinterval.Zi as Zi
1485
use RelDb as RD
1486
use Terms

The binary operations with a rounding mode

1489
type
bop
=
OAdd
|
OMul
|
ODiv

The binary operations on the reals

1492
type
rop
=
RAdd
|
RSub
|
RMul
1493
1494
function
rfun
(o: rop) (x y: real) : real =
1495
match o with RAdd -> x +. y | RSub -> x -. y | RMul -> x *. y end
1496
1497
function
fop
(o: bop) (md: mode) (x y: t) : t =
1498
match o with
1499
| OAdd -> fp_add md x y
1500
| OMul -> fp_mul md x y
1501
| ODiv -> fp_div md x y
1502
end

The unary operations with a rounding mode

1505
type
uop
=
USqrt
|
URti
1506
1507
function
fop1
(o: uop) (md: mode) (x: t) : t =
1508
match o with
1509
| USqrt -> fp_sqrt md x
1510
| URti -> fp_rti md x
1511
end

The comparisons (fp.geq and fp.gt are CLe and CLt with the arguments swapped)

1515
type
cop
=
CLe
|
CLt
|
CEq
1516
1517
predicate
fcmp
(o: cop) (x y: t) =
1518
match o with
1519
| CLe -> fp_le x y
1520
| CLt -> fp_lt x y
1521
| CEq -> fp_eq x y
1522
end

The predicates fp.isNaN, fp.isNormal, fp.isSubnormal, fp.isZero, fp.isInfinite, fp.isNegative, fp.isPositive and fp.isFinite

1527
type
ipred
=
INaN
|
INormal
|
ISubnormal
|
IZero
|
IInf
|
INeg
|
IPos
|
IFinite
1528
1529
predicate
fis
(o: ipred) (x: t) =
1530
match o with
1531
| INaN -> is_nan x
1532
| INormal -> is_normal x
1533
| ISubnormal -> is_subnormal x
1534
| IZero -> is_zero x
1535
| IInf -> is_inf x
1536
| INeg -> is_not_nan x /\ not (is_positive x)
1537
| IPos -> is_not_nan x /\ is_positive x
1538
| IFinite -> is_not_nan x /\ not (is_inf x)
1539
end

A propagator, for a term in the format fm:

1572
type
prop
=
1573
|
Bin
bop format Atom.t Atom.t Atom.t Atom.t
1574
|
Un
uop format Atom.t Atom.t Atom.t
1575
|
Cvt
format format Atom.t Atom.t Atom.t
1576
|
Abs
format Atom.t Atom.t
1577
|
Neg
Atom.t Atom.t
1578
|
Choice
Atom.t Atom.t Atom.t
1579
|
Cmp
cop format Atom.t Atom.t Atom.t
1580
|
Is
ipred format Atom.t Atom.t
1581
|
ToReal
format Atom.t Atom.t
1582
|
OfReal
format Atom.t Atom.t Atom.t
1583
|
OfBits
format Atom.t Atom.t bool
1584
|
ToRealIn
format Atom.t Atom.t int int
1585
|
ExactInt
format Atom.t Atom.t Atom.t
1586
|
ExactCvt
format format Atom.t Atom.t Atom.t Atom.t
1587
|
RBin
rop Atom.t Atom.t Atom.t
1588
|
RNeg
Atom.t Atom.t
1589
|
AddSelf
Atom.t Atom.t Atom.t Atom.t

AddSelf r a b t: r is t when a is b (r = a + b and t = 2 * a)

1592
|
NegInv
Atom.t Atom.t

NegInv r a: r = - a, as Neg: - (- b) is b, and - a = - c gives a = c

1595
|
AddOpp
format Atom.t Atom.t Atom.t Atom.t

AddOpp fm r m a b: r = a + b, as Bin OAdd: a + (- a) is a zero

1598
|
Rule
bop format Atom.t Atom.t Atom.t Atom.t

r = a o b, as Bin: the rules on the sign and the magnitude of the arguments (fp_interval.Rules)

1601
|
Rel
bop format Atom.t Atom.t Atom.t Atom.t

r = a o b, as Bin: the rules on the relations between a and b (a <= b), read from the comparison terms: a / b against 1, and (a + b) / 2 between a and b

1605
|
Mono
bop format Atom.t Atom.t Atom.t Atom.t bool

Mono o fm r m p q sw: r = p o q, as Bin; the monotonicity between r and the terms with the same operation, mode and argument a (q when sw or for the division, p otherwise)

The operators of the ground terms (view)

1611
type
builtin
=
1612
|
FpBin
bop format
1613
|
FpAdd
format

with the float 2 and the term 2 * a

1614
|
FpUn
uop format
1615
|
FpCvt
format format
1616
|
FpAbs
format
1617
|
FpNeg
1618
|
FpChoice
1619
|
FpCmp
cop format
1620
|
FpIs
ipred format
1621
|
FpToReal
format
1622
|
FpOfReal
format
1623
|
FpOfBits
format bool

to_fp of the integer of a bit–vector

1624
|
FpExactInt
format

the conversion of an integer, often exact

1625
|
FpRw

the term is another float term (a rewriting)

1626
|
FpToRealIn
format int int

fp.to_sbv, fp.to_ubv

1627
|
RealBin
rop
1628
|
RealNeg
1629
|
Other

The formats of the nodes, from their types

1632
predicate
wf
(p: prop) =
1633
match p with
1634
| Bin _ fm r _ a b | Rule _ fm r _ a b | Rel _ fm r _ a b | Mono _ fm r _ a b _ ->
1635
fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm
1636
| Un _ fm r _ a | Abs fm r a -> fmt_of r = fm /\ fmt_of a = fm
1637
| Cvt fm fm' r _ a -> fmt_of r = fm' /\ fmt_of a = fm
1638
| Neg r a | NegInv r a -> fmt_of r = fmt_of a
1639
| AddOpp fm r _ a b -> fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm
1640
| Choice r a b -> fmt_of r = fmt_of a /\ fmt_of b = fmt_of a
1641
| Cmp _ fm _ a b -> fmt_of a = fm /\ fmt_of b = fm
1642
| Is _ fm _ a -> fmt_of a = fm
1643
| ToReal fm _ a -> fmt_of a = fm
1644
| OfReal fm r _ _ -> fmt_of r = fm
1645
| OfBits fm r _ _ -> fmt_of r = fm
1646
| ToRealIn fm _ a _ _ -> fmt_of a = fm
1647
| ExactInt fm r _ _ -> fmt_of r = fm
1648
| ExactCvt fm fm' r a _ _ -> fmt_of r = fm' /\ fmt_of a = fm
1649
| RBin _ _ _ _ | RNeg _ _ | AddSelf _ _ _ _ -> true
1650
end

The meaning of the propagator in the model

1653
predicate
holds
(d: envp 'm) (p: prop) =
1654
match p with
1655
| Bin o fm r m a b | Rule o fm r m a b | Rel o fm r m a b | Mono o fm r m a b _ ->
1656
fmt (d.mf r) = fm /\ fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\
1657
d.mf r = fop o (d.mm m) (d.mf a) (d.mf b)
1658
| Un o fm r m a ->
1659
fmt (d.mf r) = fm /\ fmt (d.mf a) = fm /\ d.mf r = fop1 o (d.mm m) (d.mf a)
1660
| Cvt fm fm' r m a ->
1661
fmt (d.mf r) = fm' /\ fmt (d.mf a) = fm /\
1662
d.mf r = fp_convert fm' (d.mm m) (d.mf a)
1663
| Abs fm r a -> fmt (d.mf a) = fm /\ d.mf r = abs (d.mf a)
1664
| Neg r a | NegInv r a -> fmt (d.mf a) = fmt_of a /\ d.mf r = neg (d.mf a)
1665
| AddOpp fm r m a b ->
1666
fmt (d.mf r) = fm /\ fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\
1667
d.mf r = fp_add (d.mm m) (d.mf a) (d.mf b)
1668
| Choice r a b -> d.mf r = d.mf a \/ d.mf r = d.mf b
1669
| Cmp o fm r a b ->
1670
fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\ (d.mb r <-> fcmp o (d.mf a) (d.mf b))
1671
| Is o fm r a -> fmt (d.mf a) = fm /\ (d.mb r <-> fis o (d.mf a))
1672
| ToReal fm r a ->
1673
fmt (d.mf a) = fm /\
1674
(is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) -> d.mr r = to_real (d.mf a))
1675
| OfReal fm r m a -> d.mf r = round_x fm (d.mm m) (d.mr a)
1676
| OfBits fm r a _ ->
1677
exists b. d.mr a = from_int b /\ 0 <= b < 2 * half_bits fm /\ of_bits fm b (d.mf r)
1678
| ToRealIn fm r a lo hi ->
1679
fmt (d.mf a) = fm /\
1680
(is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) /\
1681
from_int lo <=. to_real (d.mf a) <=. from_int hi -> d.mr r = to_real (d.mf a))
1682
| ExactInt fm r a t ->
1683
(exists md. d.mf r = round_x fm md (d.mr a)) /\
1684
(exists n. d.mr a = from_int n) /\
1685
(is_not_nan (d.mf r) /\ not (is_inf (d.mf r)) -> d.mr t = to_real (d.mf r))
1686
| ExactCvt fm fm' r a tr ta ->
1687
fmt (d.mf a) = fm /\ (exists md. d.mf r = fp_convert fm' md (d.mf a)) /\
1688
(is_not_nan (d.mf r) /\ not (is_inf (d.mf r)) -> d.mr tr = to_real (d.mf r)) /\
1689
(is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) -> d.mr ta = to_real (d.mf a))
1690
| RBin o r a b -> d.mr r = rfun o (d.mr a) (d.mr b)
1691
| RNeg r a -> d.mr r = -. d.mr a
1692
| AddSelf r a b t -> d.mf a = d.mf b -> d.mf r = d.mf t
1693
end

The conversion of a finite float to a wider format is exact

  Valid (116ms) (colibri2)
1696
let ghost
convert_wider
(fm': format) (md: mode) (x: t) : unit
1697
requires { eb (fmt x) <= eb fm' /\ sb (fmt x) <= sb fm' }
1698
requires { is_not_nan x /\ not (is_inf x) }
1699
ensures { is_not_nan (fp_convert fm' md x) /\ not (is_inf (fp_convert fm' md x)) }
1700
ensures { to_real (fp_convert fm' md x) = to_real x }
1701
= {proof…}
1702
let y = widen_exact fm' x in
1703
let z = if is_positive y then false else true in
1704
assert { round_f fm' md z (ext y) = y };
1705
round_f_val fm' md (if is_positive x then false else true) z (ext x);
1706
assert { ext (fp_convert fm' md x) = ext x }
1707
{qed}

The conversion of an integer that is a float is exact

  Valid (675ms) (colibri2)
1710
let ghost
round_int_exact
(fm: format) (md: mode) (n: int) : unit
1711
requires { - power 2 (sb fm) <= n <= power 2 (sb fm) }
1712
requires { -. to_real (of_index fm (nb_sign fm - 2)) <=. from_int n <=.
1713
to_real (of_index fm (nb_sign fm - 2)) }
1714
ensures { to_real (round_x fm md (from_int n)) = from_int n }
1715
ensures { is_not_nan (round_x fm md (from_int n)) /\
1716
not (is_inf (round_x fm md (from_int n))) }
1717
= {proof…}
1718
let x = int_exact fm n in
1719
let z = if is_positive x then false else true in
1720
assert { round_f fm md z (ext x) = x };
1721
round_f_val fm md (from_int n <. 0.0) z (Fin (from_int n));
1722
assert { ext (round_x fm md (from_int n)) = Fin (from_int n) }
1723
{qed}

upd, or the contradiction for the empty domain

  Valid (24ms) (colibri2)
1726
let
upd_dom
(d: env) (n: Atom.t) (v: dom) : unit
1727
requires { live d -> mem (d.mf n) v }
1728
= match v.u with
1729
| Nil -> if v.nan then upd d n v else contradiction d
1730
| _ -> upd d n v
1731
end

The union of two optional domains, None for the empty one

  Valid (53ms) (colibri2)
1734
let
union_o
(ghost fm: format) (a b: option dom) : option dom
1735
requires { match a with Some v -> v.fm = fm | None -> true end }
1736
requires { match b with Some v -> v.fm = fm | None -> true end }
1737
ensures { match result with Some v -> v.fm = fm | None -> true end }
1738
ensures { forall x. (match a with Some v -> mem x v | None -> false end) \/
1739
(match b with Some v -> mem x v | None -> false end) ->
1740
match result with Some v -> mem x v | None -> false end }
1741
= match a, b with
1742
| None, o | o, None -> o
1743
| Some a, Some b -> Some (union fm a b)
1744
end

Forward

The results of o in the mode md

  Valid (41ms) (colibri2)
1749
let
fwd1
(ghost fm: format) (c: (t, t, t, t)) (o: bop) (md: mode) (va vb: dom) : dom
1750
requires { consts_ok fm c }
1751
requires { va.fm = fm /\ vb.fm = fm }
1752
ensures { result.fm = fm }
1753
ensures { forall x y. mem x va -> mem y vb -> mem (fop o md x y) result }
1754
= let (minf, pinf, nz, pz) = c in
1755
match o with
1756
| OAdd -> add_dom fm minf pinf md va vb
1757
| OMul -> mul_dom fm minf pinf nz pz md va vb
1758
| ODiv -> div_dom fm minf pinf nz pz md va vb
1759
end

In the mode, or in any mode when it is unknown

  Valid (956ms) (cvc4)
1762
let
fwd
(ghost fm: format) (c: (t, t, t, t)) (o: bop) (om: option mode) (va vb: dom)
1763
: dom
1764
requires { consts_ok fm c }
1765
requires { va.fm = fm /\ vb.fm = fm }
1766
ensures { result.fm = fm }
1767
ensures { forall md x y. (om = None \/ om = Some md) -> mem x va -> mem y vb ->
1768
mem (fop o md x y) result }
1769
= match om with
1770
| Some md -> fwd1 fm c o md va vb
1771
| None ->
1772
let r1 = fwd1 fm c o RNE va vb in
1773
let r2 = fwd1 fm c o RNA va vb in
1774
let r3 = fwd1 fm c o RTP va vb in
1775
let r4 = fwd1 fm c o RTN va vb in
1776
let r5 = fwd1 fm c o RTZ va vb in
1777
union fm r1 (union fm r2 (union fm r3 (union fm r4 r5)))
1778
end

Backward

The bounds of x when x + y is in the intervals l, any mode

  Valid (1.6s) (cvc5)
1783
let rec
bounds_u
(ghost fm: format) (l: list (t, t)) : option dom
1784
requires { fmt_u fm l }
1785
ensures { match result with
1786
| Some b -> b.fm = fm /\
1787
forall md x y. fmt x = fm -> fmt y = fm -> mem_u (fp_add md x y) l -> mem x b
1788
| None -> true
1789
end }
1790
variant { l }
1791
= match l with
1792
| Nil -> None
1793
| Cons (lo, hi) l' ->
1794
match add_bounds lo hi with
1795
| None -> None
1796
| Some (a, b) ->
1797
if is_nan a || is_nan b || not le_diff_zero a b then None
1798
else begin
1799
let h = interval fm a b in
1800
{proof…}
1801
let lemma pt (md: mode) (x y: t) : unit
1802
requires { fmt x = fm /\ fmt y = fm /\ in_iv (fp_add md x y) lo hi }
1803
ensures { mem x h }
1804
= add_special md x y in
1805
{qed}
1806
match l' with
1807
| Nil -> Some h
1808
| _ ->
1809
match bounds_u fm l' with
1810
| None -> None
1811
| Some r -> Some (union fm h r)
1812
end
1813
end
1814
end
1815
end
1816
end

The bounds of x when x + y is in r, any mode; None: no bound

  Valid (46ms) (colibri2)
1819
let
operand_bounds
(ghost fm: format) (r: dom) : option dom
1820
requires { r.fm = fm }
1821
ensures { match result with
1822
| Some b -> b.fm = fm /\
1823
forall md x y. fmt x = fm -> fmt y = fm -> mem (fp_add md x y) r -> mem x b
1824
| None -> true
1825
end }
1826
= if r.nan then None
1827
else match bounds_u fm r.u with
1828
| Some b -> Some b
1829
| None -> None
1830
end

The x of cur such that x + y is in r for some y of e, in the mode md (Fp_interval.Backward.add); None when there is none

  Valid (648ms) (cvc5)
1834
let
add_back
(ghost fm: format) (c: (t, t, t, t)) (md: mode) (r e cur: dom) : option dom
1835
requires { consts_ok fm c }
1836
requires { r.fm = fm /\ e.fm = fm /\ cur.fm = fm }
1837
ensures { match result with Some v -> v.fm = fm | None -> true end }
1838
ensures { forall x y. mem x cur -> mem y e -> mem (fp_add md x y) r ->
1839
match result with Some v -> mem x v | None -> false end }
1840
= let (minf, pinf, nz, pz) = c in
1841
let h = add_back_fin fm minf pinf nz pz md r e in
1842
let h = match operand_bounds fm r with
1843
| None -> Some h
1844
| Some b -> inter fm h b
1845
end in
1846
match h with
1847
| None -> None
1848
| Some h ->
1849
match inter fm h cur with
1850
| None -> None
1851
| Some h -> Some (add_shave fm minf pinf md r e h)
1852
end
1853
end

The arguments of cur such that o gives a result in r with an argument of e on the other side: x with o x y when snd is false, y with o x y when it is true; None when there is none

1858
predicate
back_ok
(o: bop) (md: mode) (snd: bool) (r e cur: dom) (res: option dom) =
1859
forall x y.
1860
if snd then mem x e -> mem y cur -> mem (fop o md x y) r ->
1861
match res with Some v -> mem y v | None -> false end
1862
else mem x cur -> mem y e -> mem (fop o md x y) r ->
1863
match res with Some v -> mem x v | None -> false end
1864
Valid (1.2s) (colibri2 19) (split_vc 2) (depth 2)
1865
let
back1
(ghost fm: format) (c: (t, t, t, t)) (o: bop) (md: mode) (snd: bool)
1866
(r e cur: dom) : option dom
1867
requires { consts_ok fm c }
1868
requires { r.fm = fm /\ e.fm = fm /\ cur.fm = fm }
1869
ensures { match result with Some v -> v.fm = fm | None -> true end }
1870
ensures { back_ok o md snd r e cur result }
1871
= let (minf, pinf, nz, pz) = c in
1872
match o with
1873
| OAdd ->
1874
{proof…}
1875
let lemma comm (x y: t) : unit
1876
requires { fmt x = fm /\ fmt y = fm } ensures { fp_add md x y = fp_add md y x }
1877
= add_comm md x y in
1878
{qed}
1879
add_back fm c md r e cur
1880
| OMul ->
1881
let v = mul_back fm minf pinf nz pz md r e in
1882
inter fm v cur
1883
| ODiv ->
1884
let v = if snd then div_back_den fm minf pinf nz pz md r e
1885
else div_back_num fm minf pinf nz pz md r e in
1886
inter fm v cur
1887
end

In the mode, or in any mode when it is unknown

  Valid (811ms) (colibri2 32) (cvc5) (split_vc 3) (depth 2)
1890
let
back
(ghost fm: format) (c: (t, t, t, t)) (o: bop) (om: option mode) (snd: bool)
1891
(r e cur: dom) : option dom
1892
requires { consts_ok fm c }
1893
requires { r.fm = fm /\ e.fm = fm /\ cur.fm = fm }
1894
ensures { match result with Some v -> v.fm = fm | None -> true end }
1895
ensures { forall md. (om = None \/ om = Some md) -> back_ok o md snd r e cur result }
1896
= match om with
1897
| Some md -> back1 fm c o md snd r e cur
1898
| None ->
1899
let r1 = back1 fm c o RNE snd r e cur in
1900
let r2 = back1 fm c o RNA snd r e cur in
1901
let r3 = back1 fm c o RTP snd r e cur in
1902
let r4 = back1 fm c o RTN snd r e cur in
1903
let r5 = back1 fm c o RTZ snd r e cur in
1904
let u45 = union_o fm r4 r5 in
1905
let u35 = union_o fm r3 u45 in
1906
let u25 = union_o fm r2 u35 in
1907
let u = union_o fm r1 u25 in
1908
{proof…}
1909
let lemma sub (a: option dom) (y: t) : unit
1910
requires { a = r1 \/ a = r2 \/ a = r3 \/ a = r4 \/ a = r5 }
1911
requires { match a with Some v -> mem y v | None -> false end }
1912
ensures { match u with Some v -> mem y v | None -> false end }
1913
= () in
1914
let lemma all (md: mode) : unit
1915
ensures { back_ok o md snd r e cur u }
1916
= match md with
1917
| RNE -> assert { back_ok o md snd r e cur r1 }
1918
| RNA -> assert { back_ok o md snd r e cur r2 }
1919
| RTP -> assert { back_ok o md snd r e cur r3 }
1920
| RTN -> assert { back_ok o md snd r e cur r4 }
1921
| RTZ -> assert { back_ok o md snd r e cur r5 }
1922
end in
1923
{qed}
1924
u
1925
end

Unary operations

  Valid (38ms) (colibri2)
1929
let
fwd_u1
(ghost fm: format) (c: (t, t, t, t)) (o: uop) (md: mode) (va: dom) : dom
1930
requires { consts_ok fm c }
1931
requires { va.fm = fm }
1932
ensures { result.fm = fm }
1933
ensures { forall x. mem x va -> mem (fop1 o md x) result }
1934
= let (_, _, nz, _) = c in
1935
match o with
1936
| USqrt -> sqrt_dom fm nz md va
1937
| URti -> rti_dom fm md va
1938
end
1939
Valid (558ms) (cvc5)
1940
let
fwd_u
(ghost fm: format) (c: (t, t, t, t)) (o: uop) (om: option mode) (va: dom)
1941
: dom
1942
requires { consts_ok fm c }
1943
requires { va.fm = fm }
1944
ensures { result.fm = fm }
1945
ensures { forall md x. (om = None \/ om = Some md) -> mem x va ->
1946
mem (fop1 o md x) result }
1947
= match om with
1948
| Some md -> fwd_u1 fm c o md va
1949
| None ->
1950
union fm (fwd_u1 fm c o RNE va) (union fm (fwd_u1 fm c o RNA va)
1951
(union fm (fwd_u1 fm c o RTP va)
1952
(union fm (fwd_u1 fm c o RTN va) (fwd_u1 fm c o RTZ va))))
1953
end
1954
1955
predicate
back_u_ok
(o: uop) (md: mode) (r cur: dom) (res: option dom) =
1956
forall x. mem x cur -> mem (fop1 o md x) r ->
1957
match res with Some v -> mem x v | None -> false end
1958
Valid (600ms) (colibri2)
1959
let
back_u1
(ghost fm: format) (c: (t, t, t, t)) (o: uop) (md: mode) (r cur: dom)
1960
: option dom
1961
requires { consts_ok fm c }
1962
requires { r.fm = fm /\ cur.fm = fm }
1963
ensures { match result with Some v -> v.fm = fm | None -> true end }
1964
ensures { back_u_ok o md r cur result }
1965
= let (minf, pinf, nz, pz) = c in
1966
let v = match o with
1967
| USqrt -> sqrt_back fm minf pinf nz pz md r
1968
| URti -> rti_back fm minf pinf md r
1969
end in
1970
inter fm v cur
1971
Valid (1.2s) (colibri2 19) (cvc5 4) (split_vc) (depth 1)
1972
let
back_u
(ghost fm: format) (c: (t, t, t, t)) (o: uop) (om: option mode) (r cur: dom)
1973
: option dom
1974
requires { consts_ok fm c }
1975
requires { r.fm = fm /\ cur.fm = fm }
1976
ensures { match result with Some v -> v.fm = fm | None -> true end }
1977
ensures { forall md. (om = None \/ om = Some md) -> back_u_ok o md r cur result }
1978
= match om with
1979
| Some md -> back_u1 fm c o md r cur
1980
| None ->
1981
let res = union_o fm (back_u1 fm c o RNE r cur)
1982
(union_o fm (back_u1 fm c o RNA r cur)
1983
(union_o fm (back_u1 fm c o RTP r cur)
1984
(union_o fm (back_u1 fm c o RTN r cur) (back_u1 fm c o RTZ r cur)))) in
1985
{proof…}
1986
let lemma pt (md: mode) : unit
1987
ensures { back_u_ok o md r cur res }
1988
= match md with
1989
| RNE -> () | RNA -> () | RTP -> () | RTN -> () | RTZ -> ()
1990
end in
1991
{qed}
1992
res
1993
end

Conversion between formats

  Valid (508ms) (cvc5)
1997
let
fwd_c
(ghost fm: format) (fm': format) (om: option mode) (va: dom) : dom
1998
requires { va.fm = fm }
1999
ensures { result.fm = fm' }
2000
ensures { forall md x. (om = None \/ om = Some md) -> mem x va ->
2001
mem (fp_convert fm' md x) result }
2002
= match om with
2003
| Some md -> convert_dom fm fm' md va
2004
| None ->
2005
union fm' (convert_dom fm fm' RNE va) (union fm' (convert_dom fm fm' RNA va)
2006
(union fm' (convert_dom fm fm' RTP va)
2007
(union fm' (convert_dom fm fm' RTN va) (convert_dom fm fm' RTZ va))))
2008
end
2009
2010
predicate
back_c_ok
(fm': format) (md: mode) (r cur: dom) (res: option dom) =
2011
forall x. mem x cur -> mem (fp_convert fm' md x) r ->
2012
match res with Some v -> mem x v | None -> false end
2013
Valid (369ms) (colibri2)
2014
let
back_c1
(fm fm': format) (c c': (t, t, t, t)) (md: mode) (r cur: dom)
2015
: option dom
2016
requires { consts_ok fm c /\ consts_ok fm' c' }
2017
requires { r.fm = fm' /\ cur.fm = fm }
2018
ensures { match result with Some v -> v.fm = fm | None -> true end }
2019
ensures { back_c_ok fm' md r cur result }
2020
= let (minf, pinf, _, _) = c in
2021
let (minf', pinf', _, _) = c' in
2022
inter fm (convert_back fm fm' minf pinf minf' pinf' md r) cur
2023
Valid (1.5s) (colibri2 21) (cvc5) (split_vc) (depth 1)
2024
let
back_c
(fm fm': format) (c c': (t, t, t, t)) (om: option mode) (r cur: dom)
2025
: option dom
2026
requires { consts_ok fm c /\ consts_ok fm' c' }
2027
requires { r.fm = fm' /\ cur.fm = fm }
2028
ensures { match result with Some v -> v.fm = fm | None -> true end }
2029
ensures { forall md. (om = None \/ om = Some md) -> back_c_ok fm' md r cur result }
2030
= match om with
2031
| Some md -> back_c1 fm fm' c c' md r cur
2032
| None ->
2033
union_o fm (back_c1 fm fm' c c' RNE r cur)
2034
(union_o fm (back_c1 fm fm' c c' RNA r cur)
2035
(union_o fm (back_c1 fm fm' c c' RTP r cur)
2036
(union_o fm (back_c1 fm fm' c c' RTN r cur) (back_c1 fm fm' c c' RTZ r cur))))
2037
end

The comparisons and the predicates

fcmp o with the arguments in this order, or swapped when rev

2042
predicate
fcmp_r
(o: cop) (rev: bool) (x y: t) =
2043
if rev then fcmp o y x else fcmp o x y

The other argument y of a comparison of value t, when x is in v; None when there is none

  Valid (502ms) (colibri2 46) (cvc4) (cvc5 2) (split_vc 4) (depth 3)
2047
let
cmp_back
(ghost fm: format) (c: (t, t, t, t)) (o: cop) (t rev: bool) (v: dom)
2048
: option dom
2049
requires { consts_ok fm c }
2050
requires { v.fm = fm }
2051
ensures { match result with Some r -> r.fm = fm | None -> true end }
2052
ensures { forall x y. mem x v -> fmt y = fm -> (t <-> fcmp_r o rev x y) ->
2053
match result with Some r -> mem y r | None -> false end }
2054
= let (minf, pinf, nz, pz) = c in
2055
match o, t, rev with
2056
| CLe, True, False -> cmp_true_le fm nz pz pinf v
2057
| CLe, True, True -> cmp_true_ge fm nz pz minf v
2058
| CLt, True, False -> cmp_true_lt fm nz pz pinf v
2059
| CLt, True, True -> cmp_true_gt fm nz pz minf v
2060
| CEq, True, _ -> cmp_true_eq fm nz pz v
2061
| CLe, False, False -> Some (cmp_false_le fm minf pinf nz pz v)
2062
| CLe, False, True -> Some (cmp_false_ge fm minf pinf nz pz v)
2063
| CLt, False, False -> Some (cmp_false_lt fm minf pinf nz pz v)
2064
| CLt, False, True -> Some (cmp_false_gt fm minf pinf nz pz v)
2065
| CEq, False, _ -> Some (cmp_false_eq fm minf pinf nz pz v)
2066
end

The floats of the format fm that satisfy o

  Valid (529ms) (colibri2 15) (cvc5 3) (split_vc) (depth 1)
2069
let
class_dom
(ghost fm: format) (c k: (t, t, t, t)) (o: ipred) : dom
2070
requires { consts_ok fm c /\ classes_ok fm k }
2071
ensures { result.fm = fm }
2072
ensures { forall v. mem v result <-> fmt v = fm /\ fis o v }
2073
= let (minf, pinf, nz, pz) = c in
2074
let (sf, sl, nf, nl) = k in
2075
match o with
2076
| INaN -> nan_dom fm
2077
| INormal -> normal fm (neg nl) (neg nf) nf nl
2078
| ISubnormal -> subnormal fm (neg sl) (neg sf) sf sl
2079
| IZero -> zeros fm nz pz
2080
| IInf -> infinites fm minf pinf
2081
| INeg -> negatives fm minf nz
2082
| IPos -> positives fm pz pinf
2083
| IFinite -> finites fm (neg nl) nl
2084
end

The dyadic domain (colibrilib/fp_dyadic.mlw)

ulp_min, ulp_max and sb of a format

  Valid (42ms) (colibri2)
2089
let
fmt_dy
(fm: format) : (int, int, int)
2090
ensures { let (u, v, p) = result in
2091
u = ulp_min fm /\ v = ulp_max fm /\ p = sb fm }
2092
= let eb = fmt_eb fm in
2093
let sb = fmt_sb fm in
2094
let u = 3 - pow2 (eb - 1) - sb in
2095
(u, u + pow2 eb - 3, sb)
2096
Valid (44ms) (colibri2) (cvc5) (split_vc) (depth 1)
2097
let ghost
abs_bound
(n e: int) : unit
2098
ensures { -. (from_int (if n < 0 then - n else n) *. pow2r e) <=. from_int n *. pow2r e
2099
<=. from_int (if n < 0 then - n else n) *. pow2r e }
2100
= {proof…}
2101
if n < 0 then assert { from_int (- n) *. pow2r e = -. (from_int n *. pow2r e) }
2102
{qed}

A valuation bound of the nonzero floats of [a, b], a and b finite

  Valid (536ms) (colibri2 11) (cvc5) (split_vc 4) (depth 2)
2106
let
iv_hi
(a b: t) : int
2107
requires { FD.finite a /\ FD.finite b }
2108
ensures { forall y. in_iv y a b -> to_real y <> 0.0 ->
2109
D.mem_hi (to_real y) (Some result) }
2110
= let (na, ea) = to_dyadic a in
2111
let (nb, eb) = to_dyadic b in
2112
let ha = D.log2_up na ea in
2113
let hb = D.log2_up nb eb in
2114
let h = if ha <= hb then hb else ha in
2115
{proof…}
2116
let lemma mem (y: t)
2117
requires { in_iv y a b /\ to_real y <> 0.0 }
2118
ensures { D.mem_hi (to_real y) (Some h) }
2119
= assert { to_real a <=. to_real y <=. to_real b };
2120
let ma = pure { from_int (if na < 0 then - na else na) *. pow2r ea } in
2121
let mb = pure { from_int (if nb < 0 then - nb else nb) *. pow2r eb } in
2122
abs_bound na ea;
2123
(* dead: such a `y` is below `2^(h+1)` *)
2124
if pure { D.fix (to_real y) (h + 1) } then [@smoke:dead] begin
2125
if pure { mb <=. ma } then begin
2126
assert { D.mem_hi (to_real y) (Some ha) };
2127
D.fix_mono (to_real y) (ha + 1) (h + 1);
2128
absurd
2129
end else begin
2130
assert { D.mem_hi (to_real y) (Some hb) };
2131
D.fix_mono (to_real y) (hb + 1) (h + 1);
2132
absurd
2133
end
2134
end in
2135
{qed}
2136
h

A valuation bound of the nonzero floats of a union of intervals

  Valid (319ms) (colibri2 20) (split_vc 9) (depth 4)
2139
let rec
union_hi
(ghost fm: format) (minf pinf: t) (l: list (t, t)) : option int
2140
requires { ok_u l /\ fmt_u fm l }
2141
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
2142
ensures { match result with
2143
| Some h -> forall y. mem_u y l -> to_real y <> 0.0 -> D.mem_hi (to_real y) (Some h)
2144
| None -> true end }
2145
variant { l }
2146
= match l with
2147
| Nil -> None
2148
| Cons (a, b) r ->
2149
if is_inf_f fm minf pinf a || is_inf_f fm minf pinf b then None
2150
else begin
2151
let h = iv_hi a b in
2152
match r with
2153
| Nil -> Some h
2154
| _ ->
2155
match union_hi fm minf pinf r with
2156
| None -> None
2157
| Some h' ->
2158
let k = if h <= h' then h' else h in
2159
{proof…}
2160
let lemma mem (y: t)
2161
requires { mem_u y l /\ to_real y <> 0.0 }
2162
ensures { D.mem_hi (to_real y) (Some k) }
2163
= if pure { D.fix (to_real y) (k + 1) } then begin
2164
if pure { in_iv y a b } then D.fix_mono (to_real y) (h + 1) (k + 1)
2165
else D.fix_mono (to_real y) (h' + 1) (k + 1)
2166
end in
2167
{qed}
2168
Some k
2169
end
2170
end
2171
end
2172
end

The dyadic domain of the floats of a domain: exact for one finite float (D.exact; lo = umax for a zero), else hi by the bounds of the intervals

  Valid (125ms) (colibri2 9) (split_vc) (depth 1)
2177
let
dom_dy
(ghost fm: format) (umax: int) (minf pinf: t) (v: dom) : D.t
2178
requires { v.fm = fm }
2179
requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }
2180
ensures { forall y. mem y v -> FD.fmem y result }
2181
= let gen () : D.t
2182
ensures { forall y. mem y v -> FD.fmem y result }
2183
= let h = union_hi fm minf pinf v.u in
2184
D.mk None h None in
2185
match v.u with
2186
| Cons (a, b) Nil ->
2187
if is_inf_f fm minf pinf a then gen ()
2188
else if le_diff_zero b a then begin
2189
let (n, e) = to_dyadic a in
2190
let r = D.exact n e umax in
2191
{proof…}
2192
let lemma mem (y: t)
2193
requires { mem y v /\ FD.finite y }
2194
ensures { D.mem (to_real y) r }
2195
= assert { ext a = Fin (to_real a) /\ ext y = Fin (to_real y) };
2196
assert { ele (ext a) (ext y) /\ ele (ext y) (ext b) /\ ele (ext b) (ext a) } in
2197
{qed}
2198
r
2199
end else gen ()
2200
| _ -> gen ()
2201
end

The dyadic domain of a float node, met with the one of its format and the one of its interval domain

  Valid (589ms) (cvc5)
2205
let
getd_f
(d: env) (n: Atom.t) (umin umax psb: int) (minf pinf: t) : D.t
2206
requires { live d -> umin = ulp_min (fmt (d.mf n)) /\ psb = sb (fmt (d.mf n)) }
2207
requires { let fm = fmt_of n in fmt minf = fm /\ fmt pinf = fm /\
2208
minf = minus_infinity fm /\ pinf = plus_infinity fm }
2209
ensures { live d -> FD.fmem (d.mf n) result }
2210
= let f = FD.float_dom umin psb in
2211
{proof…} if pure { live d } then FD.float_mem (d.mf n); {qed}
2212
let f = match get d n with
2213
| None -> f
2214
| Some v -> D.inter (dom_dy (fmt_of n) umax minf pinf v) f
2215
end in
2216
match getd d n with
2217
| None -> f
2218
| Some v -> D.inter v f
2219
end

The float node n is not a zero

  Valid (103ms) (cvc5)
2222
let
nonzero
(d: env) (fm: format) (n: Atom.t) : bool
2223
requires { fmt_of n = fm /\ (live d -> fmt (d.mf n) = fm) }
2224
ensures { result -> live d -> not is_zero (d.mf n) }
2225
= let (_, _, nz, pz) = consts fm in
2226
match get d n with
2227
| None -> false
2228
| Some v ->
2229
match inter fm v (zeros fm nz pz) with
2230
| None -> true
2231
| Some _ -> false
2232
end
2233
end

A finite sum or product: the operands are finite, the result is the rounding of the exact one

  Valid (618ms) (colibri2 10) (cvc5 6) (split_vc 2) (depth 2)
2237
let ghost
bin_finite
(o: bop) (md: mode) (x y: t) : unit
2238
requires { o <> ODiv /\ fmt x = fmt y /\ FD.finite (fop o md x y) }
2239
ensures { FD.finite x /\ FD.finite y }
2240
ensures { exists zn. fop o md x y = round_f (fmt x) md zn
2241
(Fin (if o = OAdd then to_real x +. to_real y else to_real x *. to_real y)) }
2242
= {proof…}
2243
match o with
2244
| OAdd ->
2245
assert { is_not_nan x /\ is_not_nan y /\ not opposite (ext x) (ext y) };
2246
assert { fp_add md x y = round_f (fmt x) md (add_zneg md x y) (eadd (ext x) (ext y)) };
2247
assert { eadd (ext x) (ext y) <> PInf /\ eadd (ext x) (ext y) <> MInf };
2248
assert { not is_infinity x /\ not is_infinity y };
2249
assert { ext x = Fin (to_real x) /\ ext y = Fin (to_real y) };
2250
assert { fop o md x y = round_f (fmt x) md (add_zneg md x y)
2251
(Fin (to_real x +. to_real y)) }
2252
| OMul ->
2253
assert { is_not_nan x /\ is_not_nan y };
2254
assert { not (is_zero x /\ is_infinity y) /\ not (is_infinity x /\ is_zero y) };
2255
assert { fp_mul md x y = round_f (fmt x) md (mul_zneg x y) (emul (ext x) (ext y)) };
2256
assert { emul (ext x) (ext y) <> PInf /\ emul (ext x) (ext y) <> MInf };
2257
assert { not is_infinity x /\ not is_infinity y };
2258
assert { ext x = Fin (to_real x) /\ ext y = Fin (to_real y) };
2259
assert { fop o md x y = round_f (fmt x) md (mul_zneg x y)
2260
(Fin (to_real x *. to_real y)) }
2261
| ODiv -> absurd
2262
end
2263
{qed}

A float that is not a zero has a nonzero real

  Valid (32ms) (colibri2)
2266
let ghost
nz_real
(x: t) : unit
2267
requires { FD.finite x /\ not is_zero x }
2268
ensures { to_real x <> 0.0 }
2269
= {proof…} assert { ext x = Fin (to_real x) } {qed}

A finite quotient: the dividend is finite; a finite divisor is nonzero and the quotient is the rounding of x (1/y); an infinite one gives a zero

  Valid (1.1s) (colibri2 4) (split_vc) (depth 1)
2274
let ghost
div_finite
(md: mode) (x y: t) : unit
2275
requires { fmt x = fmt y /\ FD.finite (fp_div md x y) }
2276
ensures { FD.finite x }
2277
ensures { FD.finite y -> to_real y <> 0.0 /\ exists zn. fp_div md x y =
2278
round_f (fmt x) md zn (Fin (to_real x *. (1.0 /. to_real y))) }
2279
ensures { not FD.finite y -> is_zero (fp_div md x y) }
2280
= {proof…}
2281
div_special md x y;
2282
if pure { FD.finite y } then
2283
assert { fp_div md x y = round_f (fmt x) md (mul_zneg x y)
2284
(Fin (to_real x *. (1.0 /. to_real y))) }
2285
{qed}

The floats of the dyadic domain of n: a finite nonzero float has lo <= hi and 2^lo <= |x| < 2^(hi+prec) (D.mag); the others are NaN, the infinities and the zeros

  Valid (1.2s) (colibri2 18) (cvc4) (cvc5 4) (split_vc) (depth 1)
2290
let
dyadic_iv
(d: env) (fm: format) (n: Atom.t) : unit
2291
requires { fmt_of n = fm /\ (live d -> fmt (d.mf n) = fm) }
2292
= let (umin, umax, psb) = fmt_dy fm in
2293
let (minf, pinf, nz, pz) = consts fm in
2294
let dn = getd_f d n umin umax psb minf pinf in
2295
let ex = union fm (union fm (nan_dom fm) (infinites fm minf pinf)) (zeros fm nz pz) in
2296
let empty = match dn.D.lo, dn.D.hi with Some l, Some h -> h < l | _ -> false end in
2297
let lo = match dn.D.lo with
2298
| Some l -> lo_of fm minf pinf false (a_pow2 l)
2299
| None -> lo_of fm minf pinf true (a_of_int 0)
2300
end in
2301
let hi = match dn.D.hi, dn.D.prec with
2302
| Some h, Some p -> if 0 <= p then hi_of fm minf pinf true (a_pow2 (h + p)) else pinf
2303
| _ -> pinf
2304
end in
2305
let pos = interval_o fm lo hi in
2306
let npos = neg_dom fm pos in
2307
let v = if empty then ex else union fm ex (union fm pos npos) in
2308
{proof…}
2309
let lemma sound () : unit
2310
requires { live d }
2311
ensures { mem (d.mf n) v }
2312
= let x = d.mf n in
2313
if pure { is_nan x \/ is_inf x \/ is_zero x } then ()
2314
else begin
2315
assert { ext x = Fin (to_real x) };
2316
D.mag (to_real x) dn;
2317
let ghost y = if pure { 0.0 <. to_real x } then x else neg x in
2318
assert { ext y = Fin (to_real y) /\ 0.0 <. to_real y };
2319
assert { le_dz lo y };
2320
lt_le y pinf;
2321
assert { le_dz y hi }
2322
end in
2323
{qed}
2324
upd_dom d n v

The dyadic domains of r = a / b, as the product a (1/b): D.inv knows 1/b when b is a power of 2 (up to the sign). Forward, the rounding of the domain of the product (an infinite b gives a zero, in every domain); backward, when r is finite and b too (known from the interval domain, or because r is nonzero), a = s b

  Valid (1.9s) (colibri2 37) (cvc5 3) (split_vc 3) (depth 2)
2331
let
dyadic_div
(d: env) (fm: format) (r m a b: Atom.t) : unit
2332
requires { fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm }
2333
requires { live d -> holds d (Bin ODiv fm r m a b) }
2334
= let (umin, umax, psb) = fmt_dy fm in
2335
let (minf, pinf, _, _) = consts fm in
2336
let da = getd_f d a umin umax psb minf pinf in
2337
let db = getd_f d b umin umax psb minf pinf in
2338
let s = D.mul da (D.inv db) in
2339
{proof…}
2340
let ghost x = d.mf a in
2341
let ghost y = d.mf b in
2342
let ghost z = d.mf r in
2343
let ghost sr = pure { to_real x *. (1.0 /. to_real y) } in
2344
let lemma exact () : unit
2345
requires { live d /\ FD.finite z /\ FD.finite y }
2346
ensures { FD.finite x /\ to_real y <> 0.0 /\ D.mem sr s }
2347
ensures { exists zn. z = round_f fm (d.mm m) zn (Fin sr) }
2348
= div_finite (d.mm m) x y in
2349
let lemma zero () : unit
2350
requires { live d /\ FD.finite z /\ not FD.finite y }
2351
ensures { to_real z = 0.0 }
2352
= div_finite (d.mm m) x y in
2353
{qed}
2354
let rf = FD.round_fwd fm umin umax psb s in
2355
{proof…} D.mem_zero rf; {qed}
2356
updd d r rf;
2357
match get d r with
2358
| None -> ()
2359
| Some vr ->
2360
if is_finite fm minf pinf vr then begin
2361
let rnz = nonzero d fm r in
2362
let bfin = match get d b with
2363
| None -> false | Some vb -> is_finite fm minf pinf vb end in
2364
if rnz || bfin then begin
2365
let dr = getd_f d r umin umax psb minf pinf in
2366
let ds = D.inter s (FD.round_back fm umin umax dr) in
2367
{proof…}
2368
let lemma back () : unit
2369
requires { live d /\ FD.finite x }
2370
ensures { D.mem sr ds /\ D.mem (to_real y) db /\ to_real x = sr *. to_real y }
2371
= assert { FD.finite z };
2372
if pure { FD.finite y } then begin
2373
exact ();
2374
assert { D.mem sr ds };
2375
assert { D.mem (to_real y) db }
2376
end else begin
2377
zero ();
2378
assert { is_zero z };
2379
assert { not rnz /\ not bfin };
2380
absurd
2381
end in
2382
{qed}
2383
updd d a (D.mul ds db)
2384
end
2385
end
2386
end;
2387
dyadic_iv d fm r; dyadic_iv d fm a

The dyadic domains of r = a + b and r = a * b: forward, the rounding of the domain of the exact result; backward, when r is finite, the exact result is in round_back of r, and the operands are s - b (Marre–Michel, D.sub) and s / b (D.mul_back)

  Valid (1.6s) (colibri2 32) (cvc4) (cvc5 5) (split_vc) (depth 1)
2393
let
dyadic_bin
(d: env) (o: bop) (fm: format) (r m a b: Atom.t) : unit
2394
requires { fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm }
2395
requires { live d -> holds d (Bin o fm r m a b) }
2396
= match o with
2397
| ODiv -> dyadic_div d fm r m a b
2398
| _ ->
2399
let (umin, umax, psb) = fmt_dy fm in
2400
let (minf, pinf, _, _) = consts fm in
2401
let da = getd_f d a umin umax psb minf pinf in
2402
let db = getd_f d b umin umax psb minf pinf in
2403
let anz = nonzero d fm a in
2404
let bnz = nonzero d fm b in
2405
let s = match o with OAdd -> D.add da db anz bnz | _ -> D.mul da db end in
2406
{proof…}
2407
let ghost x = d.mf a in
2408
let ghost y = d.mf b in
2409
let ghost z = d.mf r in
2410
let ghost sr = match o with
2411
| OAdd -> to_real x +. to_real y | _ -> to_real x *. to_real y end in
2412
let lemma exact () : unit
2413
requires { live d /\ FD.finite z }
2414
ensures { FD.finite x /\ FD.finite y /\ D.mem sr s }
2415
ensures { exists zn. z = round_f fm (d.mm m) zn (Fin sr) }
2416
= bin_finite o (d.mm m) x y;
2417
if bnz then nz_real y in
2418
{qed}
2419
updd d r (FD.round_fwd fm umin umax psb s);
2420
match get d r with
2421
| None -> ()
2422
| Some vr ->
2423
if is_finite fm minf pinf vr then begin
2424
let dr = getd_f d r umin umax psb minf pinf in
2425
let ds = D.inter s (FD.round_back fm umin umax dr) in
2426
let rnz = nonzero d fm r in
2427
match o with
2428
| OAdd ->
2429
{proof…} assert { live d -> to_real x = sr -. to_real y /\
2430
to_real y = sr -. to_real x }; {qed}
2431
updd d a (D.sub ds db rnz bnz);
2432
updd d b (D.sub ds da rnz anz)
2433
| _ ->
2434
{proof…} assert { live d -> sr = to_real y *. to_real x }; {qed}
2435
updd d a (D.mul_back da ds db bnz);
2436
updd d b (D.mul_back db ds da anz)
2437
end
2438
end
2439
end;
2440
dyadic_iv d fm r; dyadic_iv d fm a; dyadic_iv d fm b
2441
end

The dyadic domain of r = to_fp fm' a, a a float: to a wider format the conversion is exact, the domains are the same both ways; else the rounding of the domain of a

  Valid (2.8s) (colibri2 27) (cvc5 2) (split_vc 2) (depth 2)
2446
let
dyadic_cvt
(d: env) (fm fm': format) (r m a: Atom.t) : unit
2447
requires { fmt_of r = fm' /\ fmt_of a = fm }
2448
requires { live d -> holds d (Cvt fm fm' r m a) }
2449
= let (umin, umax, psb) = fmt_dy fm in
2450
let (umin', umax', psb') = fmt_dy fm' in
2451
let (minf, pinf, _, _) = consts fm in
2452
let (minf', pinf', _, _) = consts fm' in
2453
let da = getd_f d a umin umax psb minf pinf in
2454
{proof…}
2455
let ghost x = d.mf a in
2456
{qed}
2457
if fmt_eb fm <= fmt_eb fm' && fmt_sb fm <= fmt_sb fm' then begin
2458
{proof…}
2459
let lemma wide () : unit
2460
requires { live d /\ FD.finite x }
2461
ensures { FD.finite (d.mf r) /\ to_real (d.mf r) = to_real x }
2462
= convert_wider fm' (d.mm m) x in
2463
{qed}
2464
updd d r da;
2465
let dr = getd_f d r umin' umax' psb' minf' pinf' in
2466
{proof…}
2467
let lemma back () : unit
2468
requires { live d /\ FD.finite x }
2469
ensures { D.mem (to_real x) dr }
2470
= wide (); assert { FD.fmem (d.mf r) dr } in
2471
{qed}
2472
updd d a dr
2473
end else begin
2474
updd d r (FD.round_fwd fm' umin' umax' psb' da);
2476
(* backward, when the result is finite: the real of `a` is in `round_back` of the domain of `r` *)
2477
match get d r with
2478
| Some vr ->
2479
if is_finite fm' minf' pinf' vr then begin
2480
let dr = getd_f d r umin' umax' psb' minf' pinf' in
2481
updd d a (FD.round_back fm' umin' umax' dr)
2482
end
2483
| None -> ()
2484
end
2485
end;
2486
dyadic_iv d fm' r; dyadic_iv d fm a

The dyadic domain of the reals

An interval without 0

  Valid (316ms) (colibri2)
2491
let
riv_nz
(i: riv) : bool
2492
ensures { result -> forall x. rmem_iv x i -> x <> 0.0 }
2493
= let z = a_of_int 0 in
2494
match i with
2495
| RSing a -> not (a_eq a z)
2496
| RInter lo hi ->
2497
(match lo with
2498
| BInf -> false | BLarge a -> not (a_le a z) | BStrict a -> a_le z a end)
2499
|| (match hi with
2500
| BInf -> false | BLarge a -> not (a_le z a) | BStrict a -> a_le a z end)
2501
end

A union of intervals without 0

  Valid (44ms) (colibri2)
2504
let rec
rdom_nz
(l: rdom) : bool
2505
ensures { result -> forall x. rmem x l -> x <> 0.0 }
2506
variant { l }
2507
= match l with
2508
| Nil -> true
2509
| Cons i l' -> riv_nz i && rdom_nz l'
2510
end

The real of n is nonzero (its interval domain)

  Valid (45ms) (colibri2)
2513
let
rnonzero
(d: envp 'm) (n: Atom.t) : bool
2514
ensures { result -> live d -> d.mr n <> 0.0 }
2515
= match getr d n with None -> false | Some l -> rdom_nz l end

The dyadic domain of the reals of an interval domain: a dyadic singleton is exact

  Valid (64ms) (colibri2)
2519
let
rdom_dy
(l: rdom) : D.t
2520
ensures { forall x. rmem x l -> D.mem x result }
2521
= match l with
2522
| Cons (RSing a) Nil ->
2523
match a_dyadic a with
2524
| Some (n, e) -> D.exact n e 0
2525
| None -> D.top
2526
end
2527
| _ -> D.top
2528
end

The dyadic domain of a real node, met with the one read from its interval domain (its singletons and its congruence, D.congr)

  Valid (1.1s) (colibri2 2) (split_vc) (depth 1)
2532
let
getdr_r
(d: envp 'm) (n: Atom.t) : D.t
2533
ensures { live d -> D.mem (d.mr n) result }
2534
= let v = match getr d n with None -> D.top | Some l -> rdom_dy l end in
2535
let v = match getc d n with
2536
| NoCls -> v
2537
| Cls dv rm ->
2538
match a_dyadic dv, a_dyadic rm with
2539
| Some (dn, de), Some (rn, re) -> D.inter v (D.congr dn de rn re)
2540
| _ -> v
2541
end
2542
end in
2543
match getdr d n with None -> v | Some w -> D.inter v w end

The update of the dyadic domain of a real node, with its exponents bounded by 2^15 (D.clamp, beyond the exponents of binary128)

  Valid (35ms) (colibri2)
2547
let
upd_real
(d: env) (n: Atom.t) (v: D.t) : unit
2548
requires { live d -> D.mem (d.mr n) v }
2549
= upddr d n (D.clamp D.zbound v)

A real node has a dyadic domain: only the floats give one (by fp.to_real); the operations on the reals propagate it

  Valid (38ms) (colibri2)
2553
let
has_dy
(d: envp 'm) (n: Atom.t) : bool
2554
= match getdr d n with None -> false | Some _ -> true end

The intervals and the class of a dyadic domain

Tests of inclusion of the domains of the reals (sufficient)

  Valid (50ms) (colibri2)
2559
let
lo_in
(b c: bnd) : bool
2560
ensures { result -> forall x. rmem_lo x b -> rmem_lo x c }
2561
= match b, c with
2562
| _, BInf -> true
2563
| BInf, _ -> false
2564
| BLarge a, BLarge e | BStrict a, BLarge e | BStrict a, BStrict e -> a_le e a
2565
| BLarge a, BStrict e -> not (a_le a e)
2566
end
2567
Valid (37ms) (colibri2)
2568
let
hi_in
(b c: bnd) : bool
2569
ensures { result -> forall x. rmem_hi x b -> rmem_hi x c }
2570
= match b, c with
2571
| _, BInf -> true
2572
| BInf, _ -> false
2573
| BLarge a, BLarge e | BStrict a, BLarge e | BStrict a, BStrict e -> a_le a e
2574
| BLarge a, BStrict e -> not (a_le e a)
2575
end
2576
Valid (47ms) (colibri2)
2577
let
pt_in
(a: A.t) (j: riv) : bool
2578
ensures { result -> rmem_iv (A.real a) j }
2579
= match j with
2580
| RSing e -> a_eq a e
2581
| RInter lo hi ->
2582
(match lo with BInf -> true | BLarge e -> a_le e a | BStrict e -> not (a_le a e) end) &&
2583
(match hi with BInf -> true | BLarge e -> a_le a e | BStrict e -> not (a_le e a) end)
2584
end
2585
Valid (32ms) (colibri2)
2586
let
iv_in
(i j: riv) : bool
2587
ensures { result -> forall x. rmem_iv x i -> rmem_iv x j }
2588
= match i, j with
2589
| RSing a, _ -> pt_in a j
2590
| RInter lo hi, RInter lo' hi' -> lo_in lo lo' && hi_in hi hi'
2591
| RInter _ _, RSing _ -> false
2592
end
2593
Valid (49ms) (colibri2)
2594
let rec
iv_in_dom
(i: riv) (v: rdom) : bool
2595
ensures { result -> forall x. rmem_iv x i -> rmem x v }
2596
variant { v }
2597
= match v with
2598
| Nil -> false
2599
| Cons j v' -> iv_in i j || iv_in_dom i v'
2600
end
2601
Valid (51ms) (colibri2)
2602
let rec
dom_in
(w v: rdom) : bool
2603
ensures { result -> forall x. rmem x w -> rmem x v }
2604
variant { w }
2605
= match w with
2606
| Nil -> true
2607
| Cons i w' -> iv_in_dom i v && dom_in w' v
2608
end

n 2^e is a multiple of 2^l (sufficient)

  Valid (1.1s) (colibri2)
2611
let rec
fix_test
(n e l: int) : bool
2612
ensures { result -> D.fix (from_int n *. pow2r e) l }
2613
variant { if n < 0 then - n else n }
2614
= if n = 0 then begin {proof…} D.fix_zero l; {qed} true end
2615
else if l <= e then begin
2616
{proof…} dv_intro (from_int n *. pow2r e) (pow2r e) n; D.fix_mono (from_int n *. pow2r e) l e; {qed}
2617
true end
2618
else E.mod n 2 = 0 && fix_test (E.div n 2) (e + 1) l

The class rm + dv ℤ is in 2^l ℤ when rm and dv are multiples of 2^l

  Valid (39ms) (colibri2 6) (split_vc) (depth 1)
2622
let ghost
class_in
(rm dv: real) (l: int) : unit
2623
requires { D.fix rm l /\ D.fix dv l }
2624
ensures { forall x. (exists k: int. x = rm +. from_int k *. dv) -> D.fix x l }
2625
= {proof…}
2626
let lemma one (x: real) (k: int) : unit
2627
requires { x = rm +. from_int k *. dv }
2628
ensures { D.fix x l }
2629
= dv_intro (from_int k *. dv) dv k; dv_trans (from_int k *. dv) dv (pow2r l);
2630
D.fix_add rm (from_int k *. dv) l in
2631
()
2632
{qed}

The updates of the domain of the reals of n from its dyadic domain: the class 2^l ℤ (as (l, 2^l)), the intervals

2636
type
rivp
= {
rp_c
: option (int, A.t);
rp_v
: option rdom }
2637
2638
predicate
riv_sound
(al: bool) (mr: Atom.t -> real) (n: Atom.t) (p: rivp) =
2639
(match p.rp_c with
2640
| Some (l, q) -> A.real q = pow2r l /\
2641
(al -> exists k: int. mr n = 0.0 +. from_int k *. A.real q)
2642
| None -> true end) /\
2643
(match p.rp_v with Some v -> al -> rmem (mr n) v | None -> true end)

The updates change nothing

2646
predicate
riv_noop
(ri: Atom.t -> real -> bool) (n: Atom.t) (p: rivp) =
2647
(match p.rp_c with
2648
| Some (_, q) -> dropped q \/
2649
forall x. ri n x -> exists k: int. x = 0.0 +. from_int k *. A.real q
2650
| None -> true end) /\
2651
(match p.rp_v with Some v -> forall x. ri n x -> rmem x v | None -> true end)

The reals of the dyadic domain of n, as for the floats (dyadic_iv): a nonzero real has 2^lo <= |x| < 2^(hi+prec) (D.mag); no update without information. A finite lo is also the congruence class 2^lo ℤ of the interval domain

  Valid (523ms) (colibri2 6) (split_vc) (depth 1)
2657
let
riv_plan
(d: envp 'm) (n: Atom.t) : rivp
2658
ensures { riv_sound d.alive d.mr n result }
2659
= let dn = getdr_r d n in
2660
let z = a_of_int 0 in
2661
let empty = match dn.D.lo, dn.D.hi with Some l, Some h -> h < l | _ -> false end in
2662
let (plo, nhi) = match dn.D.lo with
2663
| Some l -> let p = a_pow2 l in (BLarge p, BLarge (a_neg p))
2664
| None -> (BStrict z, BStrict z)
2665
end in
2666
let (phi, nlo) = match dn.D.hi, dn.D.prec with
2667
| Some h, Some p ->
2668
if 0 <= p then begin
2669
let q = a_pow2 (h + p) in (BStrict q, BStrict (a_neg q))
2670
end else (BInf, BInf)
2671
| _ -> (BInf, BInf)
2672
end in
2674
(* the congruence: a finite `lo` is the class `2^lo ℤ` (not for `{0}`, known by the intervals) *)
2675
let c = match dn.D.lo with
2676
| Some l ->
2677
if not empty then begin
2678
let p = a_pow2 l in
2679
{proof…}
2680
let lemma c () : unit
2681
requires { live d }
2682
ensures { exists k: int. d.mr n = 0.0 +. from_int k *. A.real p }
2683
= let k = quot (d.mr n) (pow2r l) in
2684
assert { d.mr n = 0.0 +. from_int k *. A.real p } in
2685
{qed}
2686
Some (l, p)
2687
end else None
2688
| None -> None
2689
end in
2690
let info = empty || (match dn.D.lo with Some _ -> true | None -> false end)
2691
|| (match phi with BInf -> false | _ -> true end) in
2692
if info then begin
2693
let v = if empty then Cons (RSing z) Nil
2694
else Cons (RInter nlo nhi) (Cons (RSing z) (Cons (RInter plo phi) Nil)) in
2695
{proof…}
2696
let lemma sound () : unit
2697
requires { live d }
2698
ensures { rmem (d.mr n) v }
2699
= if pure { d.mr n <> 0.0 } then D.mag (d.mr n) dn in
2700
{qed}
2701
{ rp_c = c; rp_v = Some v }
2702
end else { rp_c = c; rp_v = None }

The class 2^l ℤ (q = 2^l) changes the domain of the reals of n

  Valid (413ms) (colibri2 6) (cvc5) (split_vc 2) (depth 2)
2706
let
class_changes
(d: envp 'm) (n: Atom.t) (l: int) (q: A.t) : bool
2707
requires { A.real q = pow2r l }
2708
ensures { not result -> dropped q \/
2709
forall x. d.ri n x -> exists k: int. x = 0.0 +. from_int k *. A.real q }
2710
= if c_dropped q then false else
2711
match getc d n with
2712
| NoCls -> true
2713
| Cls dv rm ->
2714
match a_dyadic dv, a_dyadic rm with
2715
| Some (n1, e1), Some (n2, e2) ->
2716
if fix_test n1 e1 l && fix_test n2 e2 l then begin
2717
{proof…}
2718
class_in (A.real rm) (A.real dv) l;
2719
assert { forall x. d.ri n x -> D.fix x l };
2720
let lemma conv (x: real) : unit
2721
requires { D.fix x l }
2722
ensures { exists k: int. x = 0.0 +. from_int k *. A.real q }
2723
= let k = quot x (pow2r l) in
2724
assert { x = 0.0 +. from_int k *. A.real q } in
2725
{qed}
2726
false end
2727
else true
2728
| _ -> true
2729
end
2730
end

Whether the updates change the domain of the reals of n

  Valid (305ms) (colibri2 3) (split_vc 2) (depth 2)
2733
let
riv_changes
(d: envp 'm) (n: Atom.t) (p: rivp) : bool
2734
requires { riv_sound d.alive d.mr n p }
2735
ensures { not result -> riv_noop d.ri n p }
2736
= let cc = match p.rp_c with
2737
| None -> false
2738
| Some (l, q) -> class_changes d n l q
2739
end in
2740
let cv = match p.rp_v with
2741
| None -> false
2742
| Some v -> match getr d n with None -> true | Some w -> not (dom_in w v) end
2743
end in
2744
cc || cv

The updates; nothing changes when they change nothing

  Valid (105ms) (colibri2)
2747
let
riv_apply
(d: env) (n: Atom.t) (p: rivp) : unit
2748
requires { riv_sound d.alive d.mr n p }
2749
ensures { riv_noop (old d.ri) n p -> d.ri = old d.ri /\ d.dy = old d.dy }
2750
= (match p.rp_c with Some (_, q) -> updc d n q (a_of_int 0) | None -> () end);
2751
match p.rp_v with Some v -> updr d n v | None -> () end
2752
Valid (33ms) (colibri2) (split_vc) (depth 1)
2753
let
dyadic_riv
(d: env) (n: Atom.t) : unit
2754
= riv_apply d n (riv_plan d n)

A plan of updates of the dyadic domains

The updates are computed on a read–only environment (envp 'm), so that the events check whether a step would change something (check) before it is scheduled.

The updates of a plan are sound (on the model, which the writes do not change)

2764
predicate
sound_l
(al: bool) (mr: Atom.t -> real) (l: list (Atom.t, D.t)) =
2765
match l with
2766
| Nil -> true
2767
| Cons (n, v) l' -> (al -> D.mem (mr n) v) /\ sound_l al mr l'
2768
end
2769
predicate
sound_plan
(d: envp 'm) (l: list (Atom.t, D.t)) = sound_l d.alive d.mr l

No update of a plan changes the dyadic domains dy

2772
predicate
noop_plan
(dy: Atom.t -> option D.t) (l: list (Atom.t, D.t)) =
2773
match l with
2774
| Nil -> true
2775
| Cons (n, v) l' -> dnoop (dy n) v /\ noop_plan dy l'
2776
end

Whether an update of a plan changes the dyadic domains

  Valid (36ms) (colibri2)
2779
let rec
changes
(d: envp 'm) (l: list (Atom.t, D.t)) : bool
2780
ensures { result <-> not noop_plan d.dy l }
2781
variant { l }
2782
= match l with
2783
| Nil -> false
2784
| Cons (n, v) l' ->
2785
(match getdr d n with
2786
| None -> not (D.deq v D.top)
2787
| Some w -> not (D.deq (D.inter w v) w)
2788
end) || changes d l'
2789
end

The updates of a plan, in order; nothing changes when none changes the dyadic domains

  Valid (41ms) (colibri2 5) (split_vc) (depth 1)
2793
let rec
apply
(d: env) (l: list (Atom.t, D.t)) : unit
2794
requires { sound_plan d l }
2795
ensures { noop_plan (old d.dy) l -> d.dy = old d.dy /\ d.ri = old d.ri }
2796
variant { l }
2797
= match l with
2798
| Nil -> ()
2799
| Cons (n, v) l' -> upddr d n v; apply d l'
2800
end

The dyadic domains of r = a + b, a - b, a * b, forward and backward (D.add, D.sub, D.mul, D.mul_back), clamped as in upd_real: the domains of a and b are stored (the class of the interval domain then wakes no more, wait_rdom_dy), then the one of r (met with its domain: dr), then the backward ones of a and b

  Valid (2.4s) (colibri2 8) (cvc5 2) (split_vc 4) (depth 3)
2808
let
rbin_plan
(d: envp 'm) (o: rop) (r a b: Atom.t) : list (Atom.t, D.t)
2809
requires { live d -> d.mr r = rfun o (d.mr a) (d.mr b) }
2810
ensures { sound_plan d result }
2811
= let da = getdr_r d a in
2812
let db = getdr_r d b in
2813
let anz = rnonzero d a in
2814
let bnz = rnonzero d b in
2815
let vr = match o with
2816
| RAdd -> D.add da db anz bnz
2817
| RSub -> D.sub da db anz bnz
2818
| RMul -> D.mul da db
2819
end in
2820
let dr = D.inter (getdr_r d r) (D.clamp D.zbound vr) in
2821
let rnz = rnonzero d r in
2822
let (va, vb) = match o with
2823
| RAdd ->
2824
{proof…} assert { live d -> d.mr a = d.mr r -. d.mr b /\
2825
d.mr b = d.mr r -. d.mr a }; {qed}
2826
(D.sub dr db rnz bnz, D.sub dr da rnz anz)
2827
| RSub ->
2828
{proof…} assert { live d -> d.mr a = d.mr r +. d.mr b /\
2829
d.mr b = d.mr a -. d.mr r }; {qed}
2830
(D.add dr db rnz bnz, D.sub da dr anz rnz)
2831
| RMul ->
2832
{proof…} assert { live d -> d.mr r = d.mr b *. d.mr a }; {qed}
2833
(D.mul_back da dr db bnz, D.mul_back db dr da anz)
2834
end in
2835
let c = D.clamp D.zbound in
2836
Cons (a, c da) (Cons (b, c db) (Cons (r, c vr) (Cons (a, c va) (Cons (b, c vb) Nil))))

Whether the step of r = a op b (dyadic_rbin) changes something: a node has a dyadic domain, and the plan changes a dyadic domain, or the updates of dyadic_riv change a domain of the reals. Read–only: the events call it. When the plan changes nothing, apply changes nothing, so the updates of dyadic_riv after it are the ones checked here

  Valid (35ms) (colibri2)
2844
let
rbin_check
(d: envp 'm) (o: rop) (r a b: Atom.t) : bool
2845
requires { live d -> d.mr r = rfun o (d.mr a) (d.mr b) }
2846
= (has_dy d a || has_dy d b || has_dy d r) &&
2847
(changes d (rbin_plan d o r a b) ||
2848
riv_changes d r (riv_plan d r) || riv_changes d a (riv_plan d a) ||
2849
riv_changes d b (riv_plan d b))

The step of r = a op b: the plan, then the intervals of the dyadic domains (dyadic_riv); nothing when it changes nothing (as rbin_check)

  Valid (32ms) (colibri2 5) (split_vc) (depth 1)
2854
let
dyadic_rbin
(d: env) (o: rop) (r a b: Atom.t) : unit
2855
requires { live d -> d.mr r = rfun o (d.mr a) (d.mr b) }
2856
= if has_dy d a || has_dy d b || has_dy d r then begin
2857
let l = rbin_plan d o r a b in
2858
if changes d l || riv_changes d r (riv_plan d r) ||
2859
riv_changes d a (riv_plan d a) || riv_changes d b (riv_plan d b)
2860
then begin
2861
apply d l;
2862
dyadic_riv d r; dyadic_riv d a; dyadic_riv d b
2863
end
2864
end

r = - a: the same domain

  Valid (51ms) (colibri2)
2867
let
dyadic_rneg
(d: env) (r a: Atom.t) : unit
2868
requires { live d -> d.mr r = -. d.mr a }
2869
= if has_dy d a || has_dy d r then begin
2870
let da = getdr_r d a in
2871
upd_real d a da;
2872
{proof…} if pure { live d } then D.neg_mem (d.mr a) da; {qed}
2873
upd_real d r da;
2874
let dr = getdr_r d r in
2875
{proof…} if pure { live d } then D.neg_mem (d.mr r) dr; {qed}
2876
upd_real d a dr;
2877
dyadic_riv d r; dyadic_riv d a
2878
end

r = fp.to_real a: the same domain, when a is finite (to r only when the interval domain says so: else the real is unspecified)

  Valid (590ms) (cvc5)
2882
let
dyadic_to_real
(d: env) (fm: format) (r a: Atom.t) : unit
2883
requires { fmt_of a = fm }
2884
requires { live d -> fmt (d.mf a) = fm /\
2885
(is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) -> d.mr r = to_real (d.mf a)) }
2886
= let (umin, umax, psb) = fmt_dy fm in
2887
let (minf, pinf, _, _) = consts fm in
2888
let da = getd_f d a umin umax psb minf pinf in
2889
match get d a with
2890
| Some va -> if is_finite fm minf pinf va then upd_real d r da
2891
| None -> ()
2892
end;
2893
updd d a (getdr_r d r);
2894
dyadic_iv d fm a;
2895
dyadic_riv d r

The dyadic domain of r = fp.roundToIntegral a: a finite result is the rounding of an integer (lo >= 0)

  Valid (112ms) (colibri2 8) (split_vc) (depth 1)
2899
let
dyadic_rti
(d: env) (fm: format) (r m a: Atom.t) : unit
2900
requires { fmt_of r = fm /\ fmt_of a = fm }
2901
requires { live d -> holds d (Un URti fm r m a) }
2902
= let (umin, umax, psb) = fmt_dy fm in
2903
let v = FD.round_fwd fm umin umax psb (D.mk (Some 0) None None) in
2904
{proof…}
2905
let lemma fin () : unit
2906
requires { live d /\ FD.finite (d.mf r) }
2907
ensures { D.mem (to_real (d.mf r)) v }
2908
= let x = d.mf a in
2909
match ext x with
2910
| Fin y ->
2911
let n = round_int (d.mm m) y in
2912
dv_intro (from_int n) (pow2r 0) n;
2913
assert { D.mem (from_int n) (D.mk (Some 0) None None) };
2914
assert { d.mf r = fp_rti (d.mm m) x };
2915
assert { d.mf r = round_f fm (d.mm m)
2916
(if is_positive x then false else true) (Fin (from_int n)) }
2917
| _ -> ()
2918
end in
2919
{qed}
2920
updd d r v;
2921
dyadic_iv d fm r

r = fp.to_real a when a is finite with its real in [lo, hi] (fp.to_sbv, fp.to_ubv): the domain of a to r, when the interval domain says so

  Valid (821ms) (cvc5)
2926
let
dyadic_to_real_in
(d: env) (fm: format) (r a: Atom.t) (lo hi: int) : unit
2927
requires { fmt_of a = fm }
2928
requires { live d -> holds d (ToRealIn fm r a lo hi) }
2929
= let (umin, umax, psb) = fmt_dy fm in
2930
let (minf, pinf, _, _) = consts fm in
2931
let da = getd_f d a umin umax psb minf pinf in
2932
match get d a with
2933
| None -> ()
2934
| Some va ->
2935
match to_real_fwd fm minf pinf va with
2936
| Some l -> if in_range lo hi l then begin upd_real d r da; dyadic_riv d r end
2937
| None -> ()
2938
end
2939
end

Symbolic rules (colibri)

x of format fm in va and y in vb: fp.eq x y is x = y. Both are positive, or both negative, or one is not a zero (colibri's fp_eq: the equality of the floats when the signs of zero are known)

  Valid (1.0s) (cvc5)
2946
let
fp_eq_merge
(fm: format) (c: (t, t, t, t)) (va vb: dom) : bool
2947
requires { consts_ok fm c }
2948
requires { va.fm = fm /\ vb.fm = fm }
2949
ensures { result -> forall x y. mem x va -> mem y vb -> fp_eq x y -> x = y }
2950
= let (minf, pinf, nz, pz) = c in
2951
let p = positives fm pz pinf in
2952
let n = negatives fm minf nz in
2953
let z = zeros fm nz pz in
2954
{proof…}
2955
let lemma zero_eq (x y: t) : unit
2956
requires { fmt x = fmt y /\ is_zero x /\ is_zero y /\ is_not_nan x /\ is_not_nan y }
2957
requires { is_positive x <-> is_positive y }
2958
ensures { x = y }
2959
= index_positive x; index_positive y; index_inj x; index_inj y in
2960
{qed}
2961
match is_distinct_or_included fm va z, is_distinct_or_included fm vb z with
2962
| (Disjoint, _) | (_, Disjoint) -> true
2963
| _ ->
2964
match is_distinct_or_included fm va p, is_distinct_or_included fm vb p with
2965
| (Included, Included) -> true
2966
| _ ->
2967
match is_distinct_or_included fm va n, is_distinct_or_included fm vb n with
2968
| (Included, Included) -> true
2969
| _ -> false
2970
end
2971
end
2972
end

x of format fm in va: abs x = x, x positive (colibri's abs_val_real)

  Valid (134ms) (cvc5)
2976
let
abs_id
(fm: format) (c: (t, t, t, t)) (va: dom) : bool
2977
requires { consts_ok fm c }
2978
requires { va.fm = fm }
2979
ensures { result -> forall x. mem x va -> abs x = x }
2980
= let (_, pinf, _, pz) = c in
2981
{proof…}
2982
let lemma pos_abs (x: t) : unit
2983
requires { is_not_nan x /\ is_positive x }
2984
ensures { abs x = x }
2985
= index_positive x; index_inj x; index_inj (abs x) in
2986
{qed}
2987
match is_distinct_or_included fm va (positives fm pz pinf) with
2988
| Included -> true
2989
| _ -> false
2990
end

x + (- x) and (- x) + x, x finite: +0, or –0 in RTN (IEEE 754 §6.3; colibri's fp_add_rnd on op_real1)

  Valid (760ms) (cvc4)
2994
let ghost
add_opp
(m: mode) (x nz pz: t) : unit
2995
requires { is_not_nan x /\ not (is_inf x) }
2996
requires { at_index (fmt x) nz (-1) /\ at_index (fmt x) pz 0 }
2997
ensures { fp_add m x (neg x) = (if m = RTN then nz else pz) }
2998
ensures { fp_add m (neg x) x = (if m = RTN then nz else pz) }
2999
= {proof…}
3000
index_positive x; index_positive (neg x);
3001
let r1 = fp_add m x (neg x) in
3002
let r2 = fp_add m (neg x) x in
3003
assert { is_zero r1 /\ is_zero r2 /\ fmt r1 = fmt x /\ fmt r2 = fmt x };
3004
index_positive r1; index_positive r2;
3005
index_inj r1; index_inj r2; index_inj nz; index_inj pz
3006
{qed}

x of format fm in va: x = - (abs x), x negative (colibri's abs_val_real)

  Valid (490ms) (cvc5)
3010
let
abs_opp
(fm: format) (c: (t, t, t, t)) (va: dom) : bool
3011
requires { consts_ok fm c }
3012
requires { va.fm = fm }
3013
ensures { result -> forall x. mem x va -> x = neg (abs x) }
3014
= let (minf, _, nz, _) = c in
3015
{proof…}
3016
let lemma neg_abs (x: t) : unit
3017
requires { is_not_nan x /\ not is_positive x }
3018
ensures { x = neg (abs x) }
3019
= index_positive x; index_inj x; index_inj (neg (abs x)) in
3020
{qed}
3021
match is_distinct_or_included fm va (negatives fm minf nz) with
3022
| Included -> true
3023
| _ -> false
3024
end

x + (- x) and (- x) + x, x infinite or NaN: NaN

The opposite of a NaN or an infinity

  Valid (105ms) (colibri2)
3028
let ghost
neg_special
(x: t) : unit
3029
ensures { is_nan (neg x) <-> is_nan x }
3030
ensures { is_inf (neg x) <-> is_inf x }
3031
= {proof…}
3032
if pure { is_not_nan x } then begin
3033
assert { is_plus_infinity (neg x) <-> is_minus_infinity x };
3034
assert { is_minus_infinity (neg x) <-> is_plus_infinity x }
3035
end
3036
{qed}

The opposite of a finite float

  Valid (57ms) (colibri2)
3039
let ghost
neg_fin
(x: t) : unit
3040
requires { is_not_nan x /\ not is_inf x }
3041
ensures { ext (neg x) = Fin (-. to_real x) /\ to_real (neg x) = -. to_real x }
3042
= {proof…}
3043
neg_special x;
3044
assert { ext x = Fin (to_real x) };
3045
assert { ext (neg x) = eneg (ext x) }
3046
{qed}
3047
Valid (113ms) (cvc4)
3048
let ghost
add_opp_nan
(m: mode) (x: t) : unit
3049
requires { is_nan x \/ is_inf x }
3050
ensures { is_nan (fp_add m x (neg x)) /\ is_nan (fp_add m (neg x) x) }
3051
= {proof…}
3052
if pure { is_not_nan x } then begin
3053
index_positive x; index_positive (neg x);
3054
assert { opposite (ext x) (ext (neg x)) /\ opposite (ext (neg x)) (ext x) }
3055
end
3056
{qed}

x - y, fp.eq x y: a zero, or NaN for x infinite (colibri: fp_eq1 then the zeros)

  Valid (590ms) (cvc5)
3060
let ghost
sub_eq
(m: mode) (x y: t) : unit
3061
requires { fp_eq x y }
3062
ensures { let r = fp_add m x (neg y) in
3063
fmt r = fmt x /\ (is_zero r \/ (is_inf x /\ is_nan r)) }
3064
= {proof…}
3065
if pure { is_not_nan x /\ x = y } then begin
3066
if pure { is_inf x } then begin
3067
index_positive x; index_positive (neg x);
3068
assert { opposite (ext x) (ext (neg x)) }
3069
end else begin
3070
index_positive x; index_positive (neg x);
3071
assert { ext (neg x) = eneg (ext x) };
3072
assert { eadd (ext x) (ext (neg x)) = Fin 0.0 }
3073
end
3074
end else begin
3075
assert { is_zero x /\ is_zero y /\ fmt x = fmt y };
3076
assert { ext (neg y) = eneg (ext y) };
3077
assert { eadd (ext x) (ext (neg y)) = Fin 0.0 }
3078
end
3079
{qed}

The domain of x - y for fp.eq x y, x in va

  Valid (514ms) (cvc5)
3082
let
sub_eq_dom
(fm: format) (c: (t, t, t, t)) (va: option dom) : dom
3083
requires { consts_ok fm c }
3084
requires { match va with Some v -> v.fm = fm | None -> true end }
3085
ensures { result.fm = fm }
3086
ensures { forall m x y. fmt x = fm -> fp_eq x y ->
3087
(match va with Some v -> mem x v | None -> true end) ->
3088
mem (fp_add m x (neg y)) result }
3089
= let (minf, pinf, nz, pz) = c in
3090
let z = zeros fm nz pz in
3091
{proof…}
3092
let lemma pt (m: mode) (x y: t) : unit
3093
requires { fmt x = fm /\ fp_eq x y }
3094
ensures { mem (fp_add m x (neg y)) z \/ is_nan (fp_add m x (neg y)) }
3095
ensures { fmt (fp_add m x (neg y)) = fm }
3096
ensures { is_not_nan x /\ not (is_inf x) -> mem (fp_add m x (neg y)) z }
3097
= sub_eq m x y in
3098
{qed}
3099
match va with
3100
| Some v -> if is_finite fm minf pinf v then z else union fm z (nan_dom fm)
3101
| None -> union fm z (nan_dom fm)
3102
end

The rules on fp.eq a b true: the terms a - b

  Valid (598ms) (colibri2 10) (cvc5) (split_vc) (depth 1)
3105
let rec
sub_eq_terms
(d: env) (fm: format) (a b: Atom.t) (l: list Atom.t) : unit
3106
requires { fmt_of a = fm }
3107
requires { live d -> fp_eq (d.mf a) (d.mf b) /\ fmt (d.mf a) = fm }
3108
requires { forall r. LM.mem r l -> live d ->
3109
exists md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) }
3110
variant { l }
3111
= match l with
3112
| Nil -> ()
3113
| Cons r t ->
3114
let v = sub_eq_dom fm (consts fm) (get d a) in
3115
{proof…}
3116
assert { LM.mem r l /\ forall x. LM.mem x t -> LM.mem x l };
3117
assert { live d -> exists md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) };
3118
assert { live d -> forall md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) ->
3119
mem (d.mf r) v };
3120
assert { live d -> mem (d.mf r) v };
3121
{qed}
3122
upd_dom d r v;
3123
sub_eq_terms d fm a b t
3124
end

The relations between the arguments

Read from the relation database (rel_le, rel_lt); colibri's div_real_ineqs_type (realarith.pl), and its contrapositive of the monotonicity: the domain of the result gives the relation.

The float 2 of the format fm

3133
predicate
is_two
(fm: format) (x: t) =
3134
fmt x = fm /\ is_not_nan x /\ ext x = Fin 2.0

The float 1 of the format fm

3137
predicate
is_one
(fm: format) (x: t) =
3138
fmt x = fm /\ is_not_nan x /\ ext x = Fin 1.0

The rounding of 1 is 1

  Valid (153ms) (colibri2)
3141
let ghost
one_exact
(fm: format) (m: mode) : unit
3142
ensures { is_one fm (round_f fm m false (Fin 1.0)) }
3143
ensures { is_positive (round_f fm m false (Fin 1.0)) }
3144
ensures { not is_zero (round_f fm m false (Fin 1.0)) }
3145
= {proof…}
3146
max_float_ge fm;
3147
assert { power 2 (eb fm) = 2 * power 2 (eb fm - 1) };
3148
assert { power 2 (eb fm - 1) = 2 * power 2 (eb fm - 2) };
3149
assert { 1 <= power 2 (eb fm - 2) };
3150
assert { ulp_max fm + sb fm - 1 = emax fm - 1 >= 0 };
3151
pow2r_le 0 (ulp_max fm + sb fm - 1);
3152
assert { pow2r 0 = 1.0 };
3153
assert { power 2 (sb fm) = 2 * power 2 (sb fm - 1) };
3154
assert { 1 <= power 2 (sb fm - 1) };
3155
let x = int_exact fm 1 in
3156
ext_sign x;
3157
assert { is_positive x };
3158
assert { round_f fm m (if is_positive x then false else true) (ext x) = x };
3159
assert { round_f fm m false (Fin 1.0) = x }
3160
{qed}

The float 2

  Valid (727ms) (colibri2)
3163
let ghost
two_exact
(fm: format) : unit
3164
ensures { is_two fm (round_f fm RNE false (Fin (from_int 2))) }
3165
= {proof…}
3166
max_float_ge fm;
3167
assert { power 2 (eb fm) = 2 * power 2 (eb fm - 1) };
3168
assert { power 2 (eb fm - 1) = 2 * power 2 (eb fm - 2) };
3169
assert { 1 <= power 2 (eb fm - 2) };
3170
assert { ulp_max fm + sb fm - 1 = emax fm - 1 >= 1 };
3171
pow2r_le 1 (ulp_max fm + sb fm - 1);
3172
assert { pow2r 1 = 2.0 };
3173
assert { power 2 (sb fm) = 2 * power 2 (sb fm - 1) };
3174
assert { 2 <= power 2 (sb fm - 1) };
3175
let x = int_exact fm 2 in
3176
ext_sign x;
3177
assert { is_positive x };
3178
assert { round_f fm RNE (if is_positive x then false else true) (ext x) = x };
3179
assert { round_f fm RNE false (Fin (from_int 2)) = x }
3180
{qed}

a / b against 1, on the extended reals

  Valid (650ms) (colibri2)
3183
let ghost
ediv_one
(a b: ereal) : unit
3184
requires { b <> Fin 0.0 }
3185
requires { not ((a = PInf \/ a = MInf) /\ (b = PInf \/ b = MInf)) }
3186
ensures { (ele a b /\ ele (Fin 0.0) b) \/ (ele b a /\ ele b (Fin 0.0)) ->
3187
ele (ediv a b) (Fin 1.0) }
3188
ensures { (ele b a /\ ele (Fin 0.0) b) \/ (ele a b /\ ele b (Fin 0.0)) ->
3189
ele (Fin 1.0) (ediv a b) }
3190
= {proof…}
3191
match a, b with
3192
| Fin u, Fin v ->
3193
assert { v <> 0.0 };
3194
assert { ediv a b = Fin (u *. (1.0 /. v)) };
3195
assert { u *. (1.0 /. v) -. 1.0 = (u -. v) /. v };
3196
if pure { v >. 0.0 } then begin
3197
assert { u <=. v -> (u -. v) /. v <=. 0.0 };
3198
assert { v <=. u -> (u -. v) /. v >=. 0.0 }
3199
end else begin
3200
assert { v <. 0.0 };
3201
assert { u <=. v -> (u -. v) /. v >=. 0.0 };
3202
assert { v <=. u -> (u -. v) /. v <=. 0.0 }
3203
end
3204
| MInf, Fin v ->
3205
assert { v <> 0.0 };
3206
if pure { v >. 0.0 } then assert { 1.0 /. v >. 0.0 }
3207
else assert { 1.0 /. v <. 0.0 }
3208
| PInf, Fin v ->
3209
assert { v <> 0.0 };
3210
if pure { v >. 0.0 } then assert { 1.0 /. v >. 0.0 }
3211
else assert { 1.0 /. v <. 0.0 }
3212
| _ -> ()
3213
end
3214
{qed}

x / y against 1, y neither NaN nor a zero: at most 1 when x <= y and y > 0, or y <= x and y < 0; at least 1 in the two other cases; or NaN (two infinities)

  Valid (420ms) (colibri2 11) (cvc4 2) (cvc5 2) (split_vc) (depth 1)
3219
let ghost
div_one
(m: mode) (x y o: t) : unit
3220
requires { fmt x = fmt y /\ is_one (fmt x) o /\ is_positive o /\ not is_zero o }
3221
requires { is_not_nan y /\ not is_zero y }
3222
ensures { let r = fp_div m x y in
3223
(fp_le x y /\ is_positive y \/ fp_le y x /\ not is_positive y) ->
3224
is_nan r \/ le_dz r o }
3225
ensures { let r = fp_div m x y in
3226
(fp_le y x /\ is_positive y \/ fp_le x y /\ not is_positive y) ->
3227
is_nan r \/ le_dz o r }
3228
= {proof…}
3229
let fm = fmt x in
3230
let r = fp_div m x y in
3231
if is_nan x then ()
3232
else if pure { is_infinity x /\ is_infinity y } then ()
3233
else begin
3234
ext_sign x; ext_sign y; ext_sign o;
3235
let z = mul_zneg x y in
3236
let e = ediv (ext x) (ext y) in
3237
assert { r = round_f fm m z e };
3238
assert { round_f fm m (if is_positive o then false else true) (ext o) = o };
3239
assert { round_f fm m false (ext o) = o };
3240
assert { fp_le x y -> ele (ext x) (ext y) };
3241
assert { fp_le y x -> ele (ext y) (ext x) };
3242
assert { not ((ext x = PInf \/ ext x = MInf) /\ (ext y = PInf \/ ext y = MInf)) };
3243
ediv_one (ext x) (ext y);
3244
if pure { ele e (ext o) } then
3245
assert { le_dz (round_f fm m z e) (round_f fm m false (ext o)) };
3246
if pure { ele (ext o) e } then
3247
assert { le_dz (round_f fm m false (ext o)) (round_f fm m z e) }
3248
end
3249
{qed}

2 x is a float when it is in the range of the format

  Valid (200ms) (colibri2 12) (cvc5) (split_vc 2) (depth 2)
3252
let ghost
double_exact
(m: mode) (z: bool) (x: t) : unit
3253
requires { is_not_nan x /\ not is_infinity x }
3254
requires { -. to_real (of_index (fmt x) (nb_sign (fmt x) - 2)) <=. 2.0 *. to_real x
3255
<=. to_real (of_index (fmt x) (nb_sign (fmt x) - 2)) }
3256
ensures { ext (round_f (fmt x) m z (Fin (2.0 *. to_real x))) = Fin (2.0 *. to_real x) }
3257
= {proof…}
3258
let fm = fmt x in
3259
let v = to_real x in
3260
float_dyadic x;
3261
D.fix_add v v (ulp_min fm);
3262
assert { v +. v = 2.0 *. v };
3263
assert { pow2r 1 = 2.0 };
3264
assert { D.flt 2.0 1 by 2.0 = from_int 1 *. pow2r 1 /\ - power 2 1 < 1 < power 2 1 };
3265
D.flt_mul_pow2 2.0 v (sb fm);
3266
let w = dyadic_exact fm (2.0 *. v) in
3267
let zw = if is_positive w then false else true in
3268
assert { round_f fm m zw (ext w) = w };
3269
round_f_val fm m z zw (Fin (2.0 *. v))
3270
{qed}

The largest finite float and its opposite

  Valid (1.4s) (colibri2)
3273
let ghost
max_facts
(fm: format) : unit
3274
ensures { let mx = of_index fm (nb_sign fm - 2) in
3275
is_not_nan mx /\ fmt mx = fm /\ not is_infinity mx /\
3276
ext mx = Fin (to_real mx) /\
3277
let nmx = of_index fm (1 - nb_sign fm) in
3278
is_not_nan nmx /\ fmt nmx = fm /\ ext nmx = Fin (-. to_real mx) /\
3279
(forall v. fmt v = fm -> is_not_nan v -> not is_infinity v ->
3280
le_dz nmx v /\ le_dz v mx) }
3281
= {proof…}
3282
let ghost n = nb_sign fm in
3283
assert { 3 <= n by power 2 (eb fm) >= 2 /\ power 2 (sb fm - 1) >= 1 };
3284
of_index_range fm (n - 2); of_index_range fm (1 - n);
3285
let mx = of_index fm (n - 2) in
3286
let nmx = of_index fm (1 - n) in
3287
assert { index (neg mx) = 1 - n };
3288
index_inj (neg mx);
3289
assert { nmx = neg mx };
3290
assert { ext nmx = eneg (ext mx) };
3291
let lemma pt (v: t) : unit
3292
requires { fmt v = fm /\ is_not_nan v /\ not is_infinity v }
3293
ensures { le_dz nmx v /\ le_dz v mx }
3294
= index_range v in
3295
()
3296
{qed}

2 lo is above -max when lo + lo is not –inf downwards, 2 hi below max when hi + hi is not +inf upwards

  Valid (662ms) (colibri2)
3300
let ghost
twice_lo
(lo: t) : unit
3301
requires { is_not_nan lo /\ not is_infinity lo }
3302
requires { not is_minus_infinity (fp_add rtn lo lo) }
3303
ensures { -. to_real (of_index (fmt lo) (nb_sign (fmt lo) - 2)) <=. 2.0 *. to_real lo }
3304
= {proof…}
3305
let fm = fmt lo in
3306
max_facts fm;
3307
let r = fp_add rtn lo lo in
3308
assert { not opposite (ext lo) (ext lo) };
3309
assert { r = round_f fm rtn (add_zneg rtn lo lo) (Fin (to_real lo +. to_real lo)) };
3310
assert { ele (ext r) (Fin (to_real lo +. to_real lo)) };
3311
assert { is_not_nan r /\ fmt r = fm };
3312
assert { not is_plus_infinity r };
3313
assert { le_dz (of_index fm (1 - nb_sign fm)) r };
3314
assert { ele (ext (of_index fm (1 - nb_sign fm))) (ext r) }
3315
{qed}
3316
Valid (84ms) (colibri2)
3317
let ghost
twice_hi
(hi: t) : unit
3318
requires { is_not_nan hi /\ not is_infinity hi }
3319
requires { not is_plus_infinity (fp_add rtp hi hi) }
3320
ensures { 2.0 *. to_real hi <=. to_real (of_index (fmt hi) (nb_sign (fmt hi) - 2)) }
3321
= {proof…}
3322
let fm = fmt hi in
3323
max_facts fm;
3324
let r = fp_add rtp hi hi in
3325
assert { not opposite (ext hi) (ext hi) };
3326
assert { r = round_f fm rtp (add_zneg rtp hi hi) (Fin (to_real hi +. to_real hi)) };
3327
assert { ele (Fin (to_real hi +. to_real hi)) (ext r) };
3328
assert { is_not_nan r /\ fmt r = fm };
3329
assert { not is_minus_infinity r };
3330
assert { le_dz r (of_index fm (nb_sign fm - 2)) };
3331
assert { ele (ext r) (ext (of_index fm (nb_sign fm - 2))) }
3332
{qed}

The average: x <= y in [lo, hi], where 2 lo and 2 hi are in the range of the format, then x <= (x + y) / 2 <= y, in every mode (colibri: average_1 of QF_FP/schanda/spark). Without the range, false in RTZ: x = y = max gives max / 2.

  Valid (684ms) (colibri2 39) (cvc4 3) (cvc5) (split_vc) (depth 1)
3338
let ghost
avg
(m1 m2: mode) (x y c lo hi: t) : unit
3339
requires { fmt y = fmt x /\ fmt lo = fmt x /\ fmt hi = fmt x /\ is_two (fmt x) c }
3340
requires { fp_le x y /\ le_dz lo x /\ le_dz y hi }
3341
requires { not is_minus_infinity (fp_add rtn lo lo) }
3342
requires { not is_plus_infinity (fp_add rtp hi hi) }
3343
ensures { let h = fp_div m2 (fp_add m1 x y) c in fp_le x h /\ fp_le h y }
3344
= {proof…}
3345
let fm = fmt x in
3346
add_special rtn lo lo; add_special rtp hi hi;
3347
assert { is_not_nan x /\ is_not_nan y /\ is_not_nan lo /\ is_not_nan hi };
3348
ext_sign x; ext_sign y;
3349
assert { ele (ext lo) (ext x) /\ ele (ext y) (ext hi) };
3350
assert { ele (ext x) (ext y) };
3351
assert { not is_minus_infinity lo /\ not is_plus_infinity hi };
3352
assert { ext hi <> PInf /\ ext lo <> MInf };
3353
assert { ext lo <> PInf /\ ext hi <> MInf };
3354
assert { not is_infinity lo /\ not is_infinity hi };
3355
assert { not is_infinity x /\ not is_infinity y };
3356
let vx = to_real x in
3357
let vy = to_real y in
3358
assert { ext x = Fin vx /\ ext y = Fin vy };
3359
assert { to_real lo <=. vx <=. vy <=. to_real hi };
3360
twice_lo lo; twice_hi hi;
3361
let zs = add_zneg m1 x y in
3362
double_exact m1 zs x; double_exact m1 zs y;
3363
let s = fp_add m1 x y in
3364
assert { s = round_f fm m1 zs (Fin (vx +. vy)) };
3365
round_f_ele fm m1 zs zs (Fin (2.0 *. vx)) (Fin (vx +. vy));
3366
round_f_ele fm m1 zs zs (Fin (vx +. vy)) (Fin (2.0 *. vy));
3367
assert { ele (Fin (2.0 *. vx)) (ext s) /\ ele (ext s) (Fin (2.0 *. vy)) };
3368
assert { is_not_nan s /\ fmt s = fm };
3369
assert { not is_infinity s };
3370
let vs = to_real s in
3371
assert { ext s = Fin vs /\ 2.0 *. vx <=. vs <=. 2.0 *. vy };
3372
ext_sign c;
3373
assert { not is_zero c /\ not is_infinity c /\ ext c = Fin 2.0 };
3374
let zh = mul_zneg s c in
3375
let e = ediv (ext s) (ext c) in
3376
assert { e = Fin (vs *. (1.0 /. 2.0)) };
3377
assert { vx <=. vs *. (1.0 /. 2.0) <=. vy };
3378
let h = fp_div m2 s c in
3379
assert { h = round_f fm m2 zh e };
3380
let zx = if is_positive x then false else true in
3381
let zy = if is_positive y then false else true in
3382
assert { round_f fm m2 zx (ext x) = x };
3383
assert { round_f fm m2 zy (ext y) = y };
3384
round_f_ele fm m2 zx zh (ext x) e;
3385
round_f_ele fm m2 zh zy e (ext y);
3386
assert { is_not_nan h /\ fmt h = fm };
3387
assert { ele (ext x) (ext h) /\ ele (ext h) (ext y) };
3388
if pure { is_zero x /\ is_zero h } then () else ele_le x h;
3389
if pure { is_zero h /\ is_zero y } then () else ele_le h y
3390
{qed}

The second half of the average: s finite between 2 x and 2 y gives x <= s / 2 <= y, in every mode

  Valid (730ms) (colibri2)
3394
let ghost
avg_half
(m2: mode) (x y c s: t) : unit
3395
requires { fmt y = fmt x /\ fmt s = fmt x /\ is_two (fmt x) c }
3396
requires { is_not_nan x /\ is_not_nan y /\ is_not_nan s /\ not is_infinity s }
3397
requires { not is_infinity x /\ not is_infinity y }
3398
requires { 2.0 *. to_real x <=. to_real s <=. 2.0 *. to_real y }
3399
ensures { let h = fp_div m2 s c in fp_le x h /\ fp_le h y }
3400
= {proof…}
3401
let fm = fmt x in
3402
ext_sign x; ext_sign y; ext_sign s; ext_sign c;
3403
let vx = to_real x in
3404
let vy = to_real y in
3405
let vs = to_real s in
3406
assert { ext x = Fin vx /\ ext y = Fin vy /\ ext s = Fin vs };
3407
assert { not is_zero c /\ not is_infinity c /\ ext c = Fin 2.0 };
3408
let zh = mul_zneg s c in
3409
let e = ediv (ext s) (ext c) in
3410
assert { e = Fin (vs *. (1.0 /. 2.0)) };
3411
assert { vx <=. vs *. (1.0 /. 2.0) <=. vy };
3412
let h = fp_div m2 s c in
3413
assert { h = round_f fm m2 zh e };
3414
let zx = if is_positive x then false else true in
3415
let zy = if is_positive y then false else true in
3416
assert { round_f fm m2 zx (ext x) = x };
3417
assert { round_f fm m2 zy (ext y) = y };
3418
round_f_ele fm m2 zx zh (ext x) e;
3419
round_f_ele fm m2 zh zy e (ext y);
3420
assert { is_not_nan h /\ fmt h = fm };
3421
assert { ele (ext x) (ext h) /\ ele (ext h) (ext y) };
3422
if pure { is_zero x /\ is_zero h } then () else ele_le x h;
3423
if pure { is_zero h /\ is_zero y } then () else ele_le h y
3424
{qed}

The average in round to nearest: x <= y and x + y finite give x <= (x + y) / 2 <= y, the division in any mode (colibri: average_2 of QF_FP/schanda/spark). 2 x and 2 y are in the range or beyond the sum (Intf.near_double).

  Valid (801ms) (colibri2 27) (cvc5) (split_vc) (depth 1)
3430
let ghost
avg_near
(m1 m2: mode) (x y c: t) : unit
3431
requires { m1 = RNE \/ m1 = RNA }
3432
requires { fmt y = fmt x /\ is_two (fmt x) c /\ fp_le x y }
3433
requires { is_not_nan (fp_add m1 x y) /\ not is_infinity (fp_add m1 x y) }
3434
ensures { let h = fp_div m2 (fp_add m1 x y) c in fp_le x h /\ fp_le h y }
3435
= {proof…}
3436
let fm = fmt x in
3437
max_facts fm;
3438
add_special m1 x y;
3439
assert { is_not_nan x /\ is_not_nan y };
3440
ext_sign x; ext_sign y;
3441
assert { ele (ext x) (ext y) };
3442
assert { not is_infinity x /\ not is_infinity y };
3443
let vx = to_real x in
3444
let vy = to_real y in
3445
assert { ext x = Fin vx /\ ext y = Fin vy /\ vx <=. vy };
3446
let mx = to_real (of_index fm (nb_sign fm - 2)) in
3447
let zs = add_zneg m1 x y in
3448
let s = fp_add m1 x y in
3449
assert { not opposite (ext x) (ext y) };
3450
assert { s = round_f fm m1 zs (Fin (vx +. vy)) };
3451
assert { fmt s = fm };
3452
let vs = to_real s in
3453
assert { ext s = Fin vs };
3454
assert { -. mx <=. vs <=. mx by le_dz (of_index fm (1 - nb_sign fm)) s /\ le_dz s (of_index fm (nb_sign fm - 2)) };
3455
near_double m1 zs x (vx +. vy);
3456
near_double m1 zs y (vx +. vy);
3457
if pure { -. mx <=. 2.0 *. vx } then begin
3458
double_exact m1 zs x;
3459
round_f_ele fm m1 zs zs (Fin (2.0 *. vx)) (Fin (vx +. vy))
3460
end;
3461
assert { 2.0 *. vx <=. vs };
3462
if pure { 2.0 *. vy <=. mx } then begin
3463
double_exact m1 zs y;
3464
round_f_ele fm m1 zs zs (Fin (vx +. vy)) (Fin (2.0 *. vy))
3465
end;
3466
assert { vs <=. 2.0 *. vy };
3467
avg_half m2 x y c s
3468
{qed}

The node c is the float 2: its domain is the singleton 2

  Valid (585ms) (cvc5)
3471
let
is_two_node
(d: envp 'm) (fm: format) (c: Atom.t) : bool
3472
requires { fmt_of c = fm }
3473
ensures { result -> live d -> is_two fm (d.mf c) }
3474
= match get d c with
3475
| None -> false
3476
| Some vc ->
3477
let (minf, pinf, _, _) = consts fm in
3478
if is_finite fm minf pinf vc then
3479
match is_singleton fm vc with
3480
| Sin v -> a_eq (to_a v) (a_of_int 2)
3481
| _ -> false
3482
end
3483
else false
3484
end

The domain of n has no NaN

  Valid (35ms) (colibri2)
3487
let
not_nan_dom
(d: envp 'm) (n: Atom.t) : bool
3488
ensures { result -> live d -> is_not_nan (d.mf n) }
3489
= match get d n with Some v -> not v.nan | None -> false end

The relation database

The index with the zeros merged orders the floats of a format that are not NaN as the comparisons of IEEE 754

  Valid (325ms) (colibri2)
3495
let ghost
zi_facts
(x y: t) : unit
3496
requires { is_not_nan x /\ is_not_nan y /\ fmt x = fmt y }
3497
ensures { fp_le x y <-> zi x <= zi y }
3498
ensures { fp_lt x y <-> zi x < zi y }
3499
ensures { fp_eq x y <-> zi x = zi y }
3500
= {proof…}
3501
assert { is_zero x <-> (index x = 0 \/ index x = -1) };
3502
assert { is_zero y <-> (index y = 0 \/ index y = -1) };
3503
assert { index x = index y -> x = y
3504
by of_index (fmt x) (index x) = x /\ of_index (fmt y) (index y) = y }
3505
{qed}

x <= y, x < y, y <= x, y < x, x == y

3508
let constant
z_le
: Zi.t = Zi.mk (Some 0) None
3509
let constant
z_lt
: Zi.t = Zi.mk (Some 1) None
3510
let constant
z_ge
: Zi.t = Zi.mk None (Some 0)
3511
let constant
z_gt
: Zi.t = Zi.mk None (Some (-1))
3512
let constant
z_eq
: Zi.t = Zi.mk (Some 0) (Some 0)

The relation of x and y when the comparison o of x and y is t

  Valid (105ms) (colibri2)
3516
let
cmp_rel
(o: cop) (t: bool) (ghost x y: t) : Zi.t
3517
ensures { fmt x = fmt y -> (fcmp o x y <-> t) -> relh result x y }
3518
= {proof…}
3519
if pure { is_not_nan x /\ is_not_nan y /\ fmt x = fmt y } then zi_facts x y;
3520
{qed}
3521
match o, t with
3522
| CLe, True -> z_le
3523
| CLe, False -> z_gt
3524
| CLt, True -> z_lt
3525
| CLt, False -> z_ge
3526
| CEq, True -> z_eq
3527
| CEq, False -> Zi.top
3528
end

The database says a <= b and the domains exclude NaN

  Valid (114ms) (colibri2)
3531
let
rel_le
(d: envp 'm) (fm: format) (a b: Atom.t) : bool
3532
ensures { result -> live d -> fmt (d.mf a) = fmt (d.mf b) -> fp_le (d.mf a) (d.mf b) }
3533
= let i = getrel d fm a b in
3534
let res = not_nan_dom d a && not_nan_dom d b && Zi.incl i z_le in
3535
{proof…}
3536
Zi.incl_spec i z_le;
3537
if pure { res /\ live d /\ fmt (d.mf a) = fmt (d.mf b) } then begin
3538
zi_facts (d.mf a) (d.mf b);
3539
assert { Zi.mem (zi (d.mf b) - zi (d.mf a)) z_le }
3540
end;
3541
{qed}
3542
res

The database says a < b and the domains exclude NaN

  Valid (101ms) (colibri2)
3545
let
rel_lt
(d: envp 'm) (fm: format) (a b: Atom.t) : bool
3546
ensures { result -> live d -> fmt (d.mf a) = fmt (d.mf b) -> fp_lt (d.mf a) (d.mf b) }
3547
= let i = getrel d fm a b in
3548
let res = not_nan_dom d a && not_nan_dom d b && Zi.incl i z_lt in
3549
{proof…}
3550
Zi.incl_spec i z_lt;
3551
if pure { res /\ live d /\ fmt (d.mf a) = fmt (d.mf b) } then begin
3552
zi_facts (d.mf a) (d.mf b);
3553
assert { Zi.mem (zi (d.mf b) - zi (d.mf a)) z_lt }
3554
end;
3555
{qed}
3556
res

The database says that a < b or b < a is known

  Valid (33ms) (colibri2)
3559
let
rel_strict
(d: envp 'm) (fm: format) (a b: Atom.t) : bool
3560
= let i = getrel d fm a b in
3561
Zi.incl i z_lt || Zi.incl i z_gt

The depth of the closure of the relations (colibri: delta_path, 4)

3564
let constant
rel_depth
: int = 2

An empty relation between two nodes that are not NaN

  Valid (68ms) (colibri2)
3567
let
rel_conflict
(d: env) (x y: Atom.t) (n: Zi.t) : unit
3568
requires { live d -> relh n (d.mf x) (d.mf y) }
3569
= if Zi.is_empty n && not_nan_dom d x && not_nan_dom d y then begin
3570
{proof…} Zi.is_empty_spec n; {qed}
3571
contradiction d
3572
end

Add i to the relation of x and y, and when it changes, compose it with the relations of y (through y, not NaN) and of x (through x), up to depth: the relation along a path is the sum of the relations of its edges, when the nodes of the path are not NaN

  Valid (535ms) (colibri2 28) (split_vc) (depth 1)
3578
let rec
write_rel
(d: env) (fm: format) (x y: Atom.t) (i: Zi.t) (depth: int) : unit
3579
requires { live d -> relh i (d.mf x) (d.mf y) }
3580
variant { depth }
3581
= match updrel d fm x y i with
3582
| None -> ()
3583
| Some n ->
3584
rel_conflict d x y n;
3585
if 0 < depth then begin
3586
(* `x -> y -> z` *)
3587
let rec via_y (l: list (Atom.t, Zi.t)) : unit
3588
requires { forall z j. LM.mem (z, j) l -> live d -> relh j (d.mf y) (d.mf z) }
3589
requires { live d -> relh n (d.mf x) (d.mf y) /\ is_not_nan (d.mf y) }
3590
variant { l }
3591
= match l with
3592
| Nil -> ()
3593
| Cons (z, j) t ->
3594
{proof…}
3595
assert { LM.mem (z, j) l /\ forall w. LM.mem w t -> LM.mem w l };
3596
if pure { live d /\ is_not_nan (d.mf x) /\ is_not_nan (d.mf z) } then
3597
Zi.mem_add (zi (d.mf y) - zi (d.mf x)) (zi (d.mf z) - zi (d.mf y)) n j;
3598
{qed}
3599
if not (is_equal d z x) then write_rel d fm x z (Zi.add n j) (depth - 1);
3600
via_y t
3601
end in
3602
(* `z -> x -> y` *)
3603
let rec via_x (l: list (Atom.t, Zi.t)) : unit
3604
requires { forall z j. LM.mem (z, j) l -> live d -> relh j (d.mf x) (d.mf z) }
3605
requires { live d -> relh n (d.mf x) (d.mf y) /\ is_not_nan (d.mf x) }
3606
variant { l }
3607
= match l with
3608
| Nil -> ()
3609
| Cons (z, j) t ->
3610
{proof…}
3611
assert { LM.mem (z, j) l /\ forall w. LM.mem w t -> LM.mem w l };
3612
if pure { live d /\ is_not_nan (d.mf y) /\ is_not_nan (d.mf z) } then begin
3613
Zi.mem_rev (zi (d.mf z) - zi (d.mf x)) j;
3614
Zi.mem_add (zi (d.mf x) - zi (d.mf z)) (zi (d.mf y) - zi (d.mf x)) (Zi.rev j) n
3615
end;
3616
{qed}
3617
if not (is_equal d z y) then write_rel d fm z y (Zi.add (Zi.rev j) n) (depth - 1);
3618
via_x t
3619
end in
3620
if not_nan_dom d y then via_y (RD.entries d y);
3621
if not_nan_dom d x then via_x (RD.entries d x)
3622
end
3623
end

An empty relation of a and b: one of them is NaN

  Valid (100ms) (colibri2)
3626
let
rel_check
(d: env) (fm: format) (a b: Atom.t) : unit
3627
requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm }
3628
= let i = getrel d fm a b in
3629
if Zi.is_empty i then begin
3630
{proof…}
3631
Zi.is_empty_spec i;
3632
assert { live d -> is_nan (d.mf a) \/ is_nan (d.mf b) };
3633
{qed}
3634
if not_nan_dom d a then upd_dom d b (nan_dom fm)
3635
else if not_nan_dom d b then upd_dom d a (nan_dom fm)
3636
end

a <= b in the database

  Valid (43ms) (colibri2)
3639
let
set_le
(d: env) (fm: format) (a b: Atom.t) : unit
3640
requires { fmt_of a = fm /\ fmt_of b = fm }
3641
requires { live d -> fmt (d.mf a) = fm /\ fp_le (d.mf a) (d.mf b) }
3642
= {proof…}
3643
if pure { live d } then begin
3644
assert { is_not_nan (d.mf a) /\ is_not_nan (d.mf b) /\ fmt (d.mf a) = fmt (d.mf b) };
3645
zi_facts (d.mf a) (d.mf b)
3646
end;
3647
{qed}
3648
write_rel d fm a b z_le rel_depth;
3649
rel_check d fm a b

a < b in the database

  Valid (28ms) (colibri2)
3652
let
set_lt
(d: env) (fm: format) (a b: Atom.t) : unit
3653
requires { fmt_of a = fm /\ fmt_of b = fm }
3654
requires { live d -> fmt (d.mf a) = fm /\ fp_lt (d.mf a) (d.mf b) }
3655
= {proof…}
3656
if pure { live d } then begin
3657
assert { is_not_nan (d.mf a) /\ is_not_nan (d.mf b) /\ fmt (d.mf a) = fmt (d.mf b) };
3658
zi_facts (d.mf a) (d.mf b)
3659
end;
3660
{qed}
3661
write_rel d fm a b z_lt rel_depth;
3662
rel_check d fm a b

a == b in the database

  Valid (50ms) (colibri2)
3665
let
set_eq
(d: env) (fm: format) (a b: Atom.t) : unit
3666
requires { fmt_of a = fm /\ fmt_of b = fm }
3667
requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\ fp_eq (d.mf a) (d.mf b) }
3668
= {proof…}
3669
if pure { live d /\ is_not_nan (d.mf a) /\ is_not_nan (d.mf b) } then zi_facts (d.mf a) (d.mf b);
3670
{qed}
3671
write_rel d fm a b z_eq rel_depth;
3672
rel_check d fm a b

The database says a == b and the domains exclude NaN

  Valid (489ms) (cvc5)
3675
let
rel_eq
(d: envp 'm) (fm: format) (a b: Atom.t) : bool
3676
ensures { result -> live d -> fmt (d.mf a) = fmt (d.mf b) -> fp_eq (d.mf a) (d.mf b) }
3677
= let i = getrel d fm a b in
3678
let res = not_nan_dom d a && not_nan_dom d b && Zi.incl i z_eq in
3679
{proof…}
3680
Zi.incl_spec i z_eq;
3681
if pure { res /\ live d /\ fmt (d.mf a) = fmt (d.mf b) } then begin
3682
zi_facts (d.mf a) (d.mf b);
3683
assert { Zi.mem (zi (d.mf b) - zi (d.mf a)) z_eq }
3684
end;
3685
{qed}
3686
res

The comparison r of a and b by the database, when it is not known: true when the relation implies it and the domains exclude NaN, false when the relation contradicts it

  Valid (1.1s) (cvc4)
3691
let
cmp_of_rel
(d: env) (o: cop) (fm: format) (r a b: Atom.t) : unit
3692
requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\
3693
(d.mb r <-> fcmp o (d.mf a) (d.mf b)) }
3694
= let i = getrel d fm a b in
3695
let nn = not_nan_dom d a && not_nan_dom d b in
3696
{proof…}
3697
Zi.incl_spec i z_le; Zi.incl_spec i z_lt; Zi.incl_spec i z_ge;
3698
Zi.incl_spec i z_gt; Zi.incl_spec i z_eq;
3699
if pure { live d } then begin
3700
if pure { is_not_nan (d.mf a) /\ is_not_nan (d.mf b) } then zi_facts (d.mf a) (d.mf b)
3701
else assert { not fp_le (d.mf a) (d.mf b) /\ not fp_lt (d.mf a) (d.mf b) /\
3702
not fp_eq (d.mf a) (d.mf b) }
3703
end;
3704
{qed}
3705
match o with
3706
| CLe ->
3707
if nn && Zi.incl i z_le then setb d r true
3708
else if Zi.incl i z_gt then setb d r false
3709
| CLt ->
3710
if nn && Zi.incl i z_lt then setb d r true
3711
else if Zi.incl i z_ge then setb d r false
3712
| CEq ->
3713
if nn && Zi.incl i z_eq then setb d r true
3714
else if Zi.incl i z_lt || Zi.incl i z_gt then setb d r false
3715
end

r = a / b: against 1 by the relation of a and b and the sign of b (div_one), and the contrapositive: r above (below) 1 gives the strict relation

  Valid (1.3s) (colibri2 100) (cvc5 44) (split_vc) (depth 1)
3720
let
rel_div
(d: env) (fm: format) (r a b: Atom.t) : unit
3721
requires { fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm }
3722
requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\
3723
exists md. d.mf r = fp_div md (d.mf a) (d.mf b) }
3724
= match get d b with
3725
| None -> ()
3726
| Some vb ->
3727
let (minf, pinf, nz, pz) = consts fm in
3728
let o = round_a fm RNE (a_of_int 1) in
3729
{proof…}
3730
one_exact fm RNE;
3731
assert { o = round_f fm RNE false (Fin 1.0) };
3732
{qed}
3733
let nonzero = match is_distinct_or_included fm vb (zeros fm nz pz) with
3734
| Disjoint -> true | _ -> false end in
3735
let posb = nonzero &&
3736
match is_distinct_or_included fm vb (positives fm pz pinf) with
3737
| Included -> true | _ -> false end in
3738
let negb = nonzero &&
3739
match is_distinct_or_included fm vb (negatives fm minf nz) with
3740
| Included -> true | _ -> false end in
3741
if posb || negb then begin
3742
let le_ab = rel_le d fm a b in
3743
let le_ba = rel_le d fm b a in
3744
let below = union fm (interval fm minf o) (nan_dom fm) in
3745
let above = union fm (interval fm o pinf) (nan_dom fm) in
3746
{proof…}
3747
if pure { live d } then begin
3748
let ghost md = any mode ensures { d.mf r = fp_div result (d.mf a) (d.mf b) } in
3749
div_one md (d.mf a) (d.mf b) o;
3750
assert { is_not_nan (d.mf b) /\ not is_zero (d.mf b) };
3751
assert { posb -> is_positive (d.mf b) };
3752
assert { negb -> not is_positive (d.mf b) };
3753
assert { fmt (d.mf r) = fm };
3754
if pure { is_not_nan (d.mf r) } then begin
3755
minf_le fm (d.mf r); le_pinf fm (d.mf r)
3756
end;
3757
assert { is_not_nan (d.mf r) -> le_dz minf (d.mf r) /\ le_dz (d.mf r) pinf };
3758
assert { is_not_nan (d.mf r) -> is_not_nan (d.mf a) };
3759
total_any (d.mf a) (d.mf b);
3760
total_any (d.mf b) (d.mf a);
3761
assert { is_not_nan (d.mf r) -> not le_dz (d.mf r) o ->
3762
(posb -> fp_lt (d.mf b) (d.mf a)) /\ (negb -> fp_lt (d.mf a) (d.mf b)) };
3763
assert { is_not_nan (d.mf r) -> not le_dz o (d.mf r) ->
3764
(posb -> fp_lt (d.mf a) (d.mf b)) /\ (negb -> fp_lt (d.mf b) (d.mf a)) }
3765
end;
3766
{qed}
3767
if (posb && le_ab) || (negb && le_ba) then upd_dom d r below;
3768
if (posb && le_ba) || (negb && le_ab) then upd_dom d r above;
3769
match get d r with
3770
| None -> ()
3771
| Some vr ->
3772
match is_distinct_or_included fm vr below with
3773
| Disjoint ->
3774
{proof…}
3775
assert { live d -> not mem (d.mf r) below };
3776
assert { live d -> is_not_nan (d.mf r) /\ not le_dz (d.mf r) o };
3777
{qed}
3778
if posb then set_lt d fm b a else set_lt d fm a b
3779
| _ -> ()
3780
end;
3781
match is_distinct_or_included fm vr above with
3782
| Disjoint ->
3783
{proof…}
3784
assert { live d -> not mem (d.mf r) above };
3785
assert { live d -> is_not_nan (d.mf r) /\ not le_dz o (d.mf r) };
3786
{qed}
3787
if posb then set_lt d fm a b else set_lt d fm b a
3788
| _ -> ()
3789
end
3790
end
3791
end
3792
end

Whether a step of rel_div may change something: a bound that is not in the domain of r yet, or a relation that is not known yet

  Valid (1.4s) (cvc5)
3796
let
div_useful
(d: envp 'm) (fm: format) (r a b: Atom.t) : bool
3797
requires { fmt_of r = fm /\ fmt_of b = fm }
3798
= match get d b, get d r with
3799
| Some vb, Some vr ->
3800
let (minf, pinf, nz, pz) = consts fm in
3801
let o = round_a fm RNE (a_of_int 1) in
3802
{proof…}
3803
one_exact fm RNE;
3804
assert { o = round_f fm RNE false (Fin 1.0) };
3805
{qed}
3806
let nonzero = match is_distinct_or_included fm vb (zeros fm nz pz) with
3807
| Disjoint -> true | _ -> false end in
3808
let posb = nonzero &&
3809
match is_distinct_or_included fm vb (positives fm pz pinf) with
3810
| Included -> true | _ -> false end in
3811
let negb = nonzero &&
3812
match is_distinct_or_included fm vb (negatives fm minf nz) with
3813
| Included -> true | _ -> false end in
3814
if posb || negb then begin
3815
let le_ab = rel_le d fm a b in
3816
let le_ba = rel_le d fm b a in
3817
let below = union fm (interval fm minf o) (nan_dom fm) in
3818
let above = union fm (interval fm o pinf) (nan_dom fm) in
3819
let cb = is_distinct_or_included fm vr below in
3820
let ca = is_distinct_or_included fm vr above in
3821
let nb = (posb && le_ab) || (negb && le_ba) in
3822
let na = (posb && le_ba) || (negb && le_ab) in
3823
(nb && match cb with Included -> false | _ -> true end) ||
3824
(na && match ca with Included -> false | _ -> true end) ||
3825
(not le_ab && not le_ba &&
3826
(match cb, ca with (Disjoint, _) | (_, Disjoint) -> true | _ -> false end) &&
3827
not (rel_strict d fm a b))
3828
end else false
3829
| _ -> false
3830
end

Whether a step of rel_avg may change something: a term r / c of the list whose relations with a and b are not known yet

  Valid (44ms) (colibri2)
3834
let rec
avg_useful
(d: envp 'm) (fm: format) (a b: Atom.t) (l: list (Atom.t, Atom.t)) : bool
3835
variant { l }
3836
= match l with
3837
| Nil -> false
3838
| Cons (h, _) t ->
3839
let ab = rel_le d fm a b in
3840
let ba = rel_le d fm b a in
3841
(ab && not (rel_le d fm a h && rel_le d fm h b)) ||
3842
(ba && not (rel_le d fm b h && rel_le d fm h a)) ||
3843
avg_useful d fm a b t
3844
end

r = x + y in the mode m, h = r / c, c the float 2: x <= h <= y when x <= y is known and, in round to nearest, the domain of r has no NaN and no infinity (avg_near), or in any mode, the domains bound 2 x and 2 y (avg)

  Valid (1.6s) (cvc5)
3850
let
avg_pair
(d: env) (fm: format) (r m x y h c: Atom.t) : unit
3851
requires { fmt_of x = fm /\ fmt_of y = fm /\ fmt_of r = fm /\ fmt_of h = fm }
3852
requires { live d -> fmt (d.mf x) = fm /\ fmt (d.mf y) = fm /\ is_two fm (d.mf c) /\
3853
d.mf r = fp_add (d.mm m) (d.mf x) (d.mf y) /\
3854
(exists md. d.mf h = fp_div md (d.mf r) (d.mf c)) }
3855
= if rel_le d fm x y then begin
3856
let (minf, pinf, _, _) = consts fm in
3857
let near = match mode d m with Some RNE | Some RNA -> true | _ -> false end in
3858
let fin = match get d r with
3859
| Some vr -> match to_real_fwd fm minf pinf vr with Some _ -> true | None -> false end
3860
| None -> false end in
3861
if near && fin then begin
3862
{proof…}
3863
if pure { live d } then begin
3864
let ghost m2 = any mode ensures { d.mf h = fp_div result (d.mf r) (d.mf c) } in
3865
assert { is_not_nan (d.mf r) /\ not is_infinity (d.mf r) };
3866
avg_near (d.mm m) m2 (d.mf x) (d.mf y) (d.mf c)
3867
end;
3868
{qed}
3869
set_le d fm x h;
3870
set_le d fm h y
3871
end else
3872
match get d x, get d y with
3873
| Some vx, Some vy ->
3874
match vx.u, vy.u with
3875
| Cons _ _, Cons _ _ ->
3876
let lo = first fm vx in
3877
let hi = last fm vy in
3878
let (minf, pinf, _, _) = consts fm in
3879
let l2 = add rtn lo lo in
3880
let h2 = add rtp hi hi in
3881
if not (le_diff_zero l2 minf) && not (le_diff_zero pinf h2) then begin
3882
{proof…}
3883
if pure { live d } then begin
3884
let ghost m1 = any mode ensures { d.mf r = fp_add result (d.mf x) (d.mf y) } in
3885
let ghost m2 = any mode ensures { d.mf h = fp_div result (d.mf r) (d.mf c) } in
3886
le_refl_any l2; le_refl_any h2;
3887
assert { is_not_nan (d.mf x) /\ is_not_nan (d.mf y) };
3888
assert { mem_u (d.mf x) vx.u /\ mem_u (d.mf y) vy.u };
3889
avg m1 m2 (d.mf x) (d.mf y) (d.mf c) lo hi
3890
end;
3891
{qed}
3892
set_le d fm x h;
3893
set_le d fm h y
3894
end
3895
| _ -> ()
3896
end
3897
| _ -> ()
3898
end
3899
end

r = a + b: the averages r / 2 of the list l (Env.divs)

  Valid (414ms) (colibri2 13) (cvc5 2) (split_vc) (depth 1)
3902
let rec
rel_avg
(d: env) (fm: format) (r m a b: Atom.t) (l: list (Atom.t, Atom.t)) : unit
3903
requires { fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm }
3904
requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\
3905
d.mf r = fp_add (d.mm m) (d.mf a) (d.mf b) }
3906
requires { forall h c. LM.mem (h, c) l -> fmt_of c = fmt_of r /\ fmt_of h = fmt_of r /\
3907
(live d -> exists md. d.mf h = fp_div md (d.mf r) (d.mf c)) }
3908
variant { l }
3909
= match l with
3910
| Nil -> ()
3911
| Cons (h, c) t ->
3912
{proof…}
3913
assert { LM.mem (h, c) l /\ forall x. LM.mem x t -> LM.mem x l };
3914
if pure { live d } then add_comm (d.mm m) (d.mf a) (d.mf b);
3915
{qed}
3916
if is_two_node d fm c then begin
3917
avg_pair d fm r m a b h c;
3918
avg_pair d fm r m b a h c
3919
end;
3920
rel_avg d fm r m a b t
3921
end

The monotonicity between two terms with a common argument

Marre, Bobot, Chihani, "Real Behavior of Floating Point Numbers" (SMT 2017): x <= y gives a + x <= a + y, and a * x, x / a in order by the sign of a; the contrapositive: the results strictly in order give the arguments strictly in order.

3930
let function
bk
(o: bop) : int = match o with OAdd -> 0 | OMul -> 1 | ODiv -> 2 end
3931
3932
predicate
mono_ok
(k: int) (a: t) =
3933
0 <= k <= 2 /\ (k = 0 \/ (is_not_nan a /\ (k = 1 \/ not is_zero a)))

Increasing in y (else decreasing)

3936
predicate
incr
(k: int) (a: t) = k = 0 \/ is_positive a

Two floats in the order of their values

  Valid (30ms) (colibri2)
3939
let ghost
fp_le_ext
(x y: t) : unit
3940
requires { fmt x = fmt y /\ is_not_nan x /\ is_not_nan y /\ ele (ext x) (ext y) }
3941
ensures { fp_le x y }
3942
= {proof…} if pure { is_zero x /\ is_zero y } then () else ele_le x y {qed}

The product by c is monotonic, by the sign of c

  Valid (629ms) (colibri2)
3945
let ghost
emul_mono
(c u v: ereal) : unit
3946
requires { ele u v }
3947
ensures { ele (Fin 0.0) c -> ele (emul c u) (emul c v) /\ ele (emul u c) (emul v c) }
3948
ensures { ele c (Fin 0.0) -> ele (emul c v) (emul c u) /\ ele (emul v c) (emul u c) }
3949
= {proof…}
3950
match c, u, v with
3951
| Fin z, Fin p, Fin q ->
3952
assert { z *. q -. z *. p = z *. (q -. p) };
3953
assert { p *. z = z *. p /\ q *. z = z *. q };
3954
if pure { z >=. 0.0 } then assert { z *. (q -. p) >=. 0.0 }
3955
else assert { z *. (q -. p) <=. 0.0 }
3956
| _ -> ()
3957
end
3958
{qed}

mop k md a y is not NaN: neither a nor y is NaN

  Valid (492ms) (cvc5)
3961
let ghost
mop_nan
(k: int) (md: mode) (a y: t) : unit
3962
requires { 0 <= k <= 2 }
3963
ensures { is_not_nan (mop k md a y) -> is_not_nan a /\ is_not_nan y }
3964
= ()

The monotonicity

  Valid (665ms) (colibri2 26) (cvc4) (cvc5 4) (split_vc) (depth 1)
3967
let ghost
mono
(k: int) (md: mode) (a x y: t) : unit
3968
requires { fmt x = fmt a /\ fmt y = fmt a /\ mono_ok k a }
3969
requires { fp_le x y }
3970
requires { is_not_nan (mop k md a x) /\ is_not_nan (mop k md a y) }
3971
ensures { incr k a -> fp_le (mop k md a x) (mop k md a y) }
3972
ensures { not incr k a -> fp_le (mop k md a y) (mop k md a x) }
3973
= {proof…}
3974
let fm = fmt a in
3975
let r1 = mop k md a x in
3976
let r2 = mop k md a y in
3977
mop_nan k md a x; mop_nan k md a y;
3978
ext_sign x; ext_sign y; ext_sign a;
3979
assert { ele (ext x) (ext y) };
3980
if k = 0 then begin
3981
assert { not opposite (ext a) (ext x) /\ not opposite (ext a) (ext y) };
3982
eadd_le2 (ext a) (ext a) (ext x) (ext y);
3983
assert { r1 = round_f fm md (add_zneg md a x) (eadd (ext a) (ext x)) };
3984
assert { r2 = round_f fm md (add_zneg md a y) (eadd (ext a) (ext y)) };
3985
round_f_ele fm md (add_zneg md a x) (add_zneg md a y) (eadd (ext a) (ext x)) (eadd (ext a) (ext y));
3986
fp_le_ext r1 r2
3987
end else if k = 1 then begin
3988
emul_mono (ext a) (ext x) (ext y);
3989
assert { r1 = round_f fm md (mul_zneg a x) (emul (ext a) (ext x)) };
3990
assert { r2 = round_f fm md (mul_zneg a y) (emul (ext a) (ext y)) };
3991
if is_positive a then begin
3992
round_f_ele fm md (mul_zneg a x) (mul_zneg a y) (emul (ext a) (ext x)) (emul (ext a) (ext y));
3993
fp_le_ext r1 r2
3994
end else begin
3995
round_f_ele fm md (mul_zneg a y) (mul_zneg a x) (emul (ext a) (ext y)) (emul (ext a) (ext x));
3996
fp_le_ext r2 r1
3997
end
3998
end else begin
3999
let c = einv (ext a) in
4000
assert { is_positive a -> ele (Fin 0.0) c };
4001
assert { not is_positive a -> ele c (Fin 0.0) };
4002
emul_mono c (ext x) (ext y);
4003
assert { r1 = round_f fm md (mul_zneg x a) (emul (ext x) c) };
4004
assert { r2 = round_f fm md (mul_zneg y a) (emul (ext y) c) };
4005
if is_positive a then begin
4006
round_f_ele fm md (mul_zneg x a) (mul_zneg y a) (emul (ext x) c) (emul (ext y) c);
4007
fp_le_ext r1 r2
4008
end else begin
4009
round_f_ele fm md (mul_zneg y a) (mul_zneg x a) (emul (ext y) c) (emul (ext x) c);
4010
fp_le_ext r2 r1
4011
end
4012
end
4013
{qed}

The contrapositive: the results strictly in order give the arguments strictly in order

  Valid (371ms) (colibri2)
4017
let ghost
mono_back
(k: int) (md: mode) (a x y: t) : unit
4018
requires { fmt x = fmt a /\ fmt y = fmt a /\ mono_ok k a }
4019
requires { fp_lt (mop k md a x) (mop k md a y) }
4020
ensures { incr k a -> fp_lt x y }
4021
ensures { not incr k a -> fp_lt y x }
4022
= {proof…}
4023
let r1 = mop k md a x in
4024
let r2 = mop k md a y in
4025
mop_nan k md a x; mop_nan k md a y;
4026
lt_not_le_any r1 r2;
4027
assert { not fp_le r2 r1 };
4028
total_any x y;
4029
index_inj x; index_inj y;
4030
if pure { incr k a } then begin
4031
if pure { not fp_lt x y } then begin
4032
assert { fp_le y x };
4033
mono k md a y x;
4034
absurd
4035
end
4036
end else begin
4037
if pure { not fp_lt y x } then begin
4038
assert { fp_le x y };
4039
mono k md a x y;
4040
absurd
4041
end
4042
end
4043
{qed}

The direction of the monotonicity of mop k in y, by the domain of a

  Valid (1.1s) (colibri2)
4047
let
mono_dir
(d: envp 'm) (k: int) (fm: format) (a: Atom.t) : option bool
4048
requires { fmt_of a = fm /\ 0 <= k <= 2 }
4049
ensures { match result with
4050
| Some i -> live d -> mono_ok k (d.mf a) /\ (i <-> incr k (d.mf a))
4051
| None -> true end }
4052
= if k = 0 then Some true
4053
else match get d a with
4054
| None -> None
4055
| Some va ->
4056
let (minf, pinf, nz, pz) = consts fm in
4057
let nonzero = k = 1 ||
4058
match is_distinct_or_included fm va (zeros fm nz pz) with
4059
| Disjoint -> true | _ -> false end in
4060
if not nonzero then None
4061
else match is_distinct_or_included fm va (positives fm pz pinf) with
4062
| Included -> Some true
4063
| _ ->
4064
match is_distinct_or_included fm va (negatives fm minf nz) with
4065
| Included -> Some false
4066
| _ -> None
4067
end
4068
end
4069
end

u <= v: the bounds of their domains (the zeros are equal), and the comparison terms that exist; no new term

  Valid (1.2s) (colibri2 78) (cvc4) (cvc5 6) (split_vc 3) (depth 3)
4073
let
le_pair
(d: env) (fm: format) (s1 s2: Atom.t) : unit
4074
requires { fmt_of s1 = fm /\ fmt_of s2 = fm }
4075
requires { live d -> fmt (d.mf s1) = fm /\ fp_le (d.mf s1) (d.mf s2) }
4076
= let (minf, pinf, nz, pz) = consts fm in
4077
{proof…}
4078
if pure { live d } then begin
4079
le_not_nan_any (d.mf s1) (d.mf s2);
4080
le_refl_any (d.mf s1); le_refl_any (d.mf s2);
4081
assert { is_not_nan (d.mf s1) /\ is_not_nan (d.mf s2) }
4082
end;
4083
{qed}
4084
match get d s1 with
4085
| Some vu ->
4086
match vu.u with
4087
| Cons _ _ ->
4088
let lo = first fm vu in
4089
let lo' = if is_zero_f fm nz pz lo then nz else lo in
4090
{proof…}
4091
if pure { live d } then begin
4092
assert { mem_u (d.mf s1) vu.u };
4093
assert { le_dz lo (d.mf s1) };
4094
index_range (d.mf s2);
4095
assert { index lo <= index (d.mf s1) };
4096
assert { index (d.mf s1) <= index (d.mf s2) \/
4097
(is_zero (d.mf s1) /\ is_zero (d.mf s2)) };
4098
assert { index lo' <= index (d.mf s2) };
4099
assert { le_dz lo' (d.mf s2) };
4100
assert { le_dz (d.mf s2) pinf }
4101
end;
4102
le_pinf fm lo';
4103
{qed}
4104
upd_dom d s2 (interval fm lo' pinf)
4105
| Nil -> ()
4106
end
4107
| None -> ()
4108
end;
4109
match get d s2 with
4110
| Some vv ->
4111
match vv.u with
4112
| Cons _ _ ->
4113
let hi = last fm vv in
4114
let hi' = if is_zero_f fm nz pz hi then pz else hi in
4115
{proof…}
4116
if pure { live d } then begin
4117
assert { mem_u (d.mf s2) vv.u };
4118
assert { le_dz (d.mf s2) hi };
4119
index_range (d.mf s1);
4120
assert { index (d.mf s2) <= index hi };
4121
assert { index (d.mf s1) <= index (d.mf s2) \/
4122
(is_zero (d.mf s1) /\ is_zero (d.mf s2)) };
4123
assert { index (d.mf s1) <= index hi' };
4124
assert { le_dz (d.mf s1) hi' };
4125
assert { le_dz minf (d.mf s1) }
4126
end;
4127
minf_le fm hi';
4128
{qed}
4129
upd_dom d s1 (interval fm minf hi')
4130
| Nil -> ()
4131
end
4132
| None -> ()
4133
end;
4134
set_le d fm s1 s2

u < v

  Valid (48ms) (colibri2 6) (split_vc 3) (depth 3)
4137
let
lt_pair
(d: env) (fm: format) (u v: Atom.t) : unit
4138
requires { fmt_of u = fm /\ fmt_of v = fm }
4139
requires { live d -> fmt (d.mf u) = fm /\ fp_lt (d.mf u) (d.mf v) }
4140
= {proof…} if pure { live d } then lt_le_any (d.mf u) (d.mf v); {qed}
4141
set_lt d fm u v;
4142
le_pair d fm u v

The pairs of r = mop k m a y with its siblings (r', x)

  Valid (950ms) (colibri2 525) (cvc4 18) (cvc5 88) (split_vc) (depth 1)
4145
let rec
mono_pairs
(d: env) (k: int) (fm: format) (r m a y: Atom.t) (i: bool)
4146
(l: list (Atom.t, Atom.t)) : unit
4147
requires { fmt_of r = fm /\ fmt_of y = fm /\ 0 <= k <= 2 }
4148
requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf y) = fm /\
4149
mono_ok k (d.mf a) /\ (i <-> incr k (d.mf a)) /\
4150
d.mf r = mop k (d.mm m) (d.mf a) (d.mf y) }
4151
requires { forall r' x. LM.mem (r', x) l -> fmt_of x = fm /\ fmt_of r' = fm /\
4152
(live d -> fmt (d.mf x) = fm /\ d.mf r' = mop k (d.mm m) (d.mf a) (d.mf x)) }
4153
variant { l }
4154
= match l with
4155
| Nil -> ()
4156
| Cons (r', x) t ->
4157
{proof…}
4158
assert { LM.mem (r', x) l /\ forall z. LM.mem z t -> LM.mem z l };
4159
assert { fmt_of x = fm /\ fmt_of r' = fm };
4160
let ghost md = d.mm m in
4161
let ghost fa = d.mf a in
4162
let ghost fx = d.mf x in
4163
let ghost fy = d.mf y in
4164
assert { live d -> fmt fa = fm /\ fmt fx = fm /\ fmt fy = fm /\ mono_ok k fa /\
4165
(i <-> incr k fa) /\ d.mf r = mop k md fa fy /\ d.mf r' = mop k md fa fx };
4166
{qed}
4167
if not_nan_dom d r && not_nan_dom d r' then begin
4168
if rel_le d fm x y then begin
4169
{proof…} if pure { live d } then mono k md fa fx fy; {qed}
4170
if i then le_pair d fm r' r else le_pair d fm r r'
4171
end;
4172
if rel_le d fm y x then begin
4173
{proof…} if pure { live d } then mono k md fa fy fx; {qed}
4174
if i then le_pair d fm r r' else le_pair d fm r' r
4175
end
4176
end;
4177
if rel_lt d fm r' r then begin
4178
{proof…} if pure { live d } then mono_back k md fa fx fy; {qed}
4179
if i then lt_pair d fm x y else lt_pair d fm y x
4180
end;
4181
if rel_lt d fm r r' then begin
4182
{proof…} if pure { live d } then mono_back k md fa fy fx; {qed}
4183
if i then lt_pair d fm y x else lt_pair d fm x y
4184
end;
4185
mono_pairs d k fm r m a y i t
4186
end

Whether a pair may give something: a relation known

  Valid (44ms) (colibri2)
4189
let rec
mono_useful
(d: envp 'm) (fm: format) (r y: Atom.t) (l: list (Atom.t, Atom.t)) : bool
4190
variant { l }
4191
= match l with
4192
| Nil -> false
4193
| Cons (r', x) t ->
4194
rel_le d fm x y || rel_le d fm y x || rel_lt d fm r' r ||
4195
rel_lt d fm r r' || mono_useful d fm r y t
4196
end

The common argument and the other one of Mono o fm r m p q sw

  Valid (17ms) (colibri2)
4199
let
mono_args
(o: bop) (p q: Atom.t) (sw: bool) : (Atom.t, Atom.t)
4200
ensures { let (a, y) = result in
4201
match o with
4202
| ODiv -> a = q /\ y = p
4203
| _ -> if sw then a = q /\ y = p else a = p /\ y = q
4204
end }
4205
= match o with ODiv -> (q, p) | _ -> if sw then (q, p) else (p, q) end

The rules on the sign and the magnitude

dsem dec v n: what the decision dec of fp_interval.Rules says of the result v and the argument n

4211
predicate
dsem
(dec: IR.decision) (v n: t) =
4212
match dec with
4213
| IR.DNone -> true
4214
| IR.DMerge -> v = n
4215
| IR.DEq -> fp_eq v n
4216
| IR.DLeB -> fp_le n v
4217
| IR.DLeR -> fp_le v n
4218
end

The decision of the rule of o on x in da and y in db: on fop o x y and y (x for the division); + and * commute

  Valid (639ms) (colibri2 4) (cvc5 2) (split_vc) (depth 1)
4222
let
decide
(o: bop) (fm: format) (da db: dom) : IR.decision
4223
ensures { forall md x y. FE.mem_at fm x da -> FE.mem_at fm y db ->
4224
match o with
4225
| ODiv -> dsem result (fop o md x y) x
4226
| _ -> fop o md y x = fop o md x y /\ dsem result (fop o md x y) y
4227
end }
4228
= try
4229
match o with
4230
| OAdd -> FE.add_rule fm da db
4231
| OMul ->
4232
match FE.mul_rule fm da db with IR.DEq -> IR.DNone | dec -> dec end
4233
| ODiv ->
4234
match FE.div_rule fm da db with IR.DEq -> IR.DNone | dec -> dec end
4235
end
4236
with FE.FormatMismatch -> IR.DNone
4237
end

The fact of the decision dec on the result r and the argument n

  Valid (165ms) (colibri2 7) (split_vc) (depth 1)
4240
let
act
(d: env) (fm: format) (dec: IR.decision) (r n: Atom.t) : unit
4241
requires { fmt_of r = fm /\ fmt_of n = fm }
4242
requires { live d -> fmt (d.mf r) = fm /\ fmt (d.mf n) = fm /\ dsem dec (d.mf r) (d.mf n) }
4243
= match dec with
4244
| IR.DNone -> ()
4245
| IR.DMerge -> mergef d n r
4246
| IR.DEq -> set_eq d fm n r
4247
| IR.DLeB -> set_le d fm n r
4248
| IR.DLeR -> set_le d fm r n
4249
end

x + x is 2 * x

  Valid (411ms) (colibri2)
4252
let lemma
add_self
(md: mode) (x c: t)
4253
requires { is_two (fmt x) c }
4254
ensures { fp_add md x x = fp_mul md c x }
4255
= {proof…}
4256
ext_sign c;
4257
assert { is_positive c /\ not is_zero c };
4258
assert { not is_infinity c };
4259
if is_nan x then ()
4260
else begin
4261
ext_sign x;
4262
assert { not opposite (ext x) (ext x) };
4263
assert { add_zneg md x x = mul_zneg c x };
4264
assert { eadd (ext x) (ext x) = emul (ext c) (ext x) };
4265
assert { not (is_zero c /\ is_infinity x) /\ not (is_infinity c /\ is_zero x) }
4266
end
4267
{qed}

Whether the step of p may change something, on a read–only environment (the events, before scheduling it): false only when it changes nothing (rbin_check)

  Valid (382ms) (colibri2 4) (split_vc) (depth 1)
4272
let
may_change
(d: envp 'm) (p: prop) : bool
4273
requires { wf p }
4274
requires { live d -> holds d p }
4275
= match p with
4276
| RBin o r a b -> rbin_check d o r a b
4277
| Rel ODiv fm r _ a b -> div_useful d fm r a b
4278
| Rel OAdd fm r _ a b -> avg_useful d fm a b (divs d fm r)
4279
| Cmp _ _ r _ _ -> match getb d r with None -> true | Some _ -> false end
4280
| Mono o fm r m p q sw ->
4281
let (a, y) = mono_args o p q sw in
4282
let k = bk o in
4283
match mono_dir d k fm a with
4284
| Some _ -> mono_useful d fm r y (sibs d k fm m a r)
4285
| None -> false
4286
end
4287
| _ -> true
4288
end

One step of propagation

The step of the propagator p; the result true stops it

  Valid (2.1s) (colibri2 682) (cvc5 75) (split_vc 33) (depth 5)
4293
let
run
(d: env) (p: prop) : bool
4294
requires { wf p }
4295
requires { live d -> holds d p }
4296
= match p with
4297
| Bin o fm r m a b ->
4298
let c = consts fm in
4299
let (minf, pinf, _, _) = c in
4300
let om = mode d m in
4301
(* forward *)
4302
match get d a, get d b with
4303
| Some va, Some vb -> upd_dom d r (fwd fm c o om va vb)
4304
| _ -> ()
4305
end;
4306
(* backward, when the domain of [r] is known *)
4307
match get d r with
4308
| None -> ()
4309
| Some vr ->
4310
let tp = top fm minf pinf in
4311
let va = match get d a with Some v -> v | None -> tp end in
4312
let vb = match get d b with Some v -> v | None -> tp end in
4313
{proof…}
4314
assert { live d -> (om = None \/ om = Some (d.mm m)) /\
4315
mem (d.mf r) vr /\ mem (d.mf a) va /\ mem (d.mf b) vb };
4316
{qed}
4317
let x = back fm c o om false vr vb va in
4318
{proof…}
4319
assert { live d -> back_ok o (d.mm m) false vr vb va x };
4320
assert { live d -> match x with Some v -> mem (d.mf a) v | None -> false end };
4321
{qed}
4322
match x with
4323
| None -> contradiction d
4324
| Some x -> upd_dom d a x
4325
end;
4326
let va = match get d a with Some v -> v | None -> tp end in
4327
let vb = match get d b with Some v -> v | None -> tp end in
4328
{proof…}
4329
assert { live d -> (om = None \/ om = Some (d.mm m)) /\
4330
mem (d.mf r) vr /\ mem (d.mf a) va /\ mem (d.mf b) vb };
4331
{qed}
4332
let y = back fm c o om true vr va vb in
4333
{proof…}
4334
assert { live d -> back_ok o (d.mm m) true vr va vb y };
4335
assert { live d -> match y with Some v -> mem (d.mf b) v | None -> false end };
4336
{qed}
4337
match y with
4338
| None -> contradiction d
4339
| Some y -> upd_dom d b y
4340
end
4341
end;
4342
dyadic_bin d o fm r m a b;
4343
false
4344
| Un o fm r m a ->
4345
let c = consts fm in
4346
let (minf, pinf, _, _) = c in
4347
let om = mode d m in
4348
match get d a with
4349
| Some va -> upd_dom d r (fwd_u fm c o om va)
4350
| None -> ()
4351
end;
4352
match get d r with
4353
| None -> ()
4354
| Some vr ->
4355
let va = match get d a with Some v -> v | None -> top fm minf pinf end in
4356
{proof…}
4357
assert { live d -> (om = None \/ om = Some (d.mm m)) /\
4358
mem (d.mf r) vr /\ mem (d.mf a) va };
4359
{qed}
4360
let x = back_u fm c o om vr va in
4361
{proof…}
4362
assert { live d -> back_u_ok o (d.mm m) vr va x };
4363
{qed}
4364
match x with
4365
| None -> contradiction d
4366
| Some x -> upd_dom d a x
4367
end
4368
end;
4369
match o with URti -> dyadic_rti d fm r m a | USqrt -> () end;
4370
false
4371
| Cvt fm fm' r m a ->
4372
let c = consts fm in
4373
let c' = consts fm' in
4374
let (minf, pinf, _, _) = c in
4375
let om = mode d m in
4376
match get d a with
4377
| Some va -> upd_dom d r (fwd_c fm fm' om va)
4378
| None -> ()
4379
end;
4380
match get d r with
4381
| None -> ()
4382
| Some vr ->
4383
let va = match get d a with Some v -> v | None -> top fm minf pinf end in
4384
{proof…}
4385
assert { live d -> (om = None \/ om = Some (d.mm m)) /\
4386
mem (d.mf r) vr /\ mem (d.mf a) va };
4387
{qed}
4388
let x = back_c fm fm' c c' om vr va in
4389
{proof…}
4390
assert { live d -> back_c_ok fm' (d.mm m) vr va x };
4391
{qed}
4392
match x with
4393
| None -> contradiction d
4394
| Some x -> upd_dom d a x
4395
end
4396
end;
4397
dyadic_cvt d fm fm' r m a;
4398
false
4399
| Abs fm r a ->
4400
let (_, pinf, _, pz) = consts fm in
4401
match get d a with
4402
| Some va -> upd_dom d r (abs_dom fm pz va)
4403
| None -> ()
4404
end;
4405
match get d r with
4406
| Some vr -> upd_dom d a (abs_back fm pz pinf vr)
4407
| None -> ()
4408
end;
4409
(* `abs a = a` for `a` positive, `a = - (abs a)` for `a` negative *)
4410
match get d a with
4411
| Some va ->
4412
if abs_id fm (consts fm) va then mergef d a r
4413
else if abs_opp fm (consts fm) va then begin
4414
let c = match negs d r with Some c -> c | None -> mk_neg d fm r end in
4415
{proof…} if pure { live d } then neg_neg (d.mf a); {qed}
4416
mergef d a c
4417
end
4418
| None -> ()
4419
end;
4420
false
4421
| Choice r a b ->
4422
match get d a, get d b with
4423
| Some va, Some vb -> upd_dom d r (union (fmt_of a) va vb)
4424
| _ -> ()
4425
end;
4426
false
4427
| Cmp o fm r a b ->
4428
let c = consts fm in
4429
let (minf, pinf, _, _) = c in
4430
match getb d r with
4431
| None -> cmp_of_rel d o fm r a b
4432
| Some t ->
4433
let va = match get d a with Some v -> v | None -> top fm minf pinf end in
4434
{proof…}
4435
assert { live d -> mem (d.mf a) va /\ fmt (d.mf b) = fm /\
4436
(t <-> fcmp_r o false (d.mf a) (d.mf b)) };
4437
{qed}
4438
match cmp_back fm c o t false va with
4439
| None -> contradiction d
4440
| Some x -> upd_dom d b x
4441
end;
4442
let vb = match get d b with Some v -> v | None -> top fm minf pinf end in
4443
match cmp_back fm c o t true vb with
4444
| None -> contradiction d
4445
| Some x -> upd_dom d a x
4446
end;
4447
(* the relation database *)
4448
write_rel d fm a b (cmp_rel o t (ghost d.mf a) (ghost d.mf b)) rel_depth;
4449
rel_check d fm a b;
4450
(* the database may contradict `t` (a false `fp.eq` writes nothing) *)
4451
cmp_of_rel d o fm r a b;
4452
(* `fp.eq a b` is `a = b` when the signs of zero cannot differ *)
4453
match o, t with
4454
| CEq, True ->
4455
match get d a, get d b with
4456
| Some va, Some vb -> if fp_eq_merge fm c va vb then mergef d a b
4457
| _ -> ()
4458
end;
4459
(* the terms `a - b` and `b - a` are zeros (or NaN) *)
4460
{proof…}
4461
assert { live d -> fp_eq (d.mf b) (d.mf a) };
4462
{qed}
4463
sub_eq_terms d fm a b (subs d fm a b);
4464
sub_eq_terms d fm b a (subs d fm b a)
4465
| _ -> ()
4466
end
4467
end;
4468
false
4469
| Is o fm r a ->
4470
let c = consts fm in
4471
let (minf, pinf, _, _) = c in
4472
let cd = class_dom fm c (classes fm) o in
4473
match getb d r with
4474
| Some True -> upd_dom d a cd
4475
| Some False ->
4476
match diff fm (top fm minf pinf) cd with
4477
| None -> contradiction d
4478
| Some x -> upd_dom d a x
4479
end
4480
| None ->
4481
match get d a with
4482
| None -> ()
4483
| Some va ->
4484
match is_distinct_or_included fm va cd with
4485
| Included -> setb d r true
4486
| Disjoint -> setb d r false
4487
| Uncomparable -> ()
4488
end
4489
end
4490
end;
4491
false
4492
| ToReal fm r a ->
4493
let (minf, pinf, _, _) = consts fm in
4494
match get d a with
4495
| None -> ()
4496
| Some va ->
4497
match to_real_fwd fm minf pinf va with
4498
| None -> ()
4499
| Some l -> updr_dom d r l
4500
end
4501
end;
4502
match getr d r with
4503
| None -> ()
4504
| Some vr ->
4505
let va = match get d a with Some v -> v | None -> top fm minf pinf end in
4506
match to_real_back fm minf pinf va vr with
4507
| None -> contradiction d
4508
| Some x -> upd_dom d a x
4509
end
4510
end;
4511
dyadic_to_real d fm r a;
4512
false
4513
| OfReal fm r m a ->
4514
let (minf, pinf, _, _) = consts fm in
4515
let om = mode d m in
4516
{proof…}
4517
assert { live d -> om = None \/ om = Some (d.mm m) };
4518
{qed}
4519
match getr d a with
4520
| None -> ()
4521
| Some l -> upd_dom d r (of_real_fwd fm minf pinf om l)
4522
end;
4523
match get d r with
4524
| None -> ()
4525
| Some vr ->
4526
match of_real_back fm om vr with
4527
| None -> ()
4528
| Some l -> updr_dom d a l
4529
end
4530
end;
4531
false
4532
| OfBits fm r a back ->
4533
match getr d a with
4534
| None -> ()
4535
| Some l -> upd_dom d r (of_bits_fwd fm l)
4536
end;
4537
if back then begin
4538
match get d r with
4539
| None -> ()
4540
| Some vr -> updr_dom d a (of_bits_back fm vr)
4541
end
4542
end;
4543
false
4544
| ToRealIn fm r a lo hi ->
4545
let (minf, pinf, _, _) = consts fm in
4546
match get d a with
4547
| None -> ()
4548
| Some va ->
4549
match to_real_fwd fm minf pinf va with
4550
| Some l -> if in_range lo hi l then updr_dom d r l
4551
| None -> ()
4552
end
4553
end;
4554
match getr d r with
4555
| None -> ()
4556
| Some vr ->
4557
let va = match get d a with Some v -> v | None -> top fm minf pinf end in
4558
let out = Cons (RInter BInf (BStrict (a_of_int lo)))
4559
(Cons (RInter (BStrict (a_of_int hi)) BInf) vr) in
4560
match to_real_back fm minf pinf va out with
4561
| None -> contradiction d
4562
| Some x -> upd_dom d a x
4563
end
4564
end;
4565
dyadic_to_real_in d fm r a lo hi;
4566
false
4567
| ExactInt fm r a t ->
4568
let (_, _, _, nl) = classes fm in
4569
let p = pow2 (fmt_sb fm) in
4570
let f = a_floor (to_a nl) in
4571
let b = if p <= f then p else f in
4572
match getr d a with
4573
| None -> false
4574
| Some l ->
4575
if in_range (- b) b l then begin
4576
{proof…}
4577
if pure { live d } then begin
4578
let ghost n = any int ensures { d.mr a = from_int result } in
4579
let ghost md = any mode ensures { d.mf r = round_x fm result (d.mr a) } in
4580
assert { - b <= n <= b };
4581
assert { nl = of_index fm (nb_sign fm - 2) };
4582
round_int_exact fm md n
4583
end;
4584
{qed}
4585
merge d t a; true
4586
end else begin
4588
(* exact when the integer is a float of `fm` (its dyadic domain) in the range of `fm` *)
4589
let (umin, _, psb) = fmt_dy fm in
4590
let da = D.inter (getdr_r d a) (D.mk (Some 0) None None) in
4591
{proof…}
4592
if pure { live d } then begin
4593
let ghost n = any int ensures { d.mr a = from_int result } in
4594
assert { pow2r 0 = 1.0 };
4595
dv_intro (d.mr a) (pow2r 0) n
4596
end;
4597
{qed}
4598
if in_range_a (to_a (neg nl)) (to_a nl) l && FD.is_exact umin psb da then begin
4599
{proof…}
4600
if pure { live d } then begin
4601
let ghost md = any mode ensures { d.mf r = round_x fm result (d.mr a) } in
4602
assert { nl = of_index fm (nb_sign fm - 2) };
4603
assert { umin = ulp_min fm /\ psb = sb fm };
4604
assert { D.mem (d.mr a) da };
4605
assert { D.fix (d.mr a) umin /\ D.flt (d.mr a) psb };
4606
max_facts fm; neg_fin nl;
4607
assert { -. to_real nl <=. d.mr a <=. to_real nl };
4608
FD.round_exact fm md (d.mr a <. 0.0) (d.mr a)
4609
end;
4610
{qed}
4611
merge d t a; true
4612
end else false
4613
end
4614
end
4615
| ExactCvt fm fm' r a tr ta ->
4616
if fmt_eb fm <= fmt_eb fm' && fmt_sb fm <= fmt_sb fm' then begin
4617
let (minf, pinf, _, _) = consts fm in
4618
match get d a with
4619
| None -> false
4620
| Some va ->
4621
match to_real_fwd fm minf pinf va with
4622
| None -> false
4623
| Some _ ->
4624
{proof…}
4625
if pure { live d } then begin
4626
let ghost md = any mode ensures { d.mf r = fp_convert fm' result (d.mf a) } in
4627
convert_wider fm' md (d.mf a)
4628
end;
4629
{qed}
4630
merge d tr ta; true
4631
end
4632
end
4633
end else begin
4635
(* narrowing: exact when the float is a float of `fm'` (its dyadic domain) in the range of `fm'` *)
4636
let (minf, pinf, _, _) = consts fm in
4637
let (umin, umax, psb) = fmt_dy fm in
4638
let (umin', _, psb') = fmt_dy fm' in
4639
let (_, _, _, nl') = classes fm' in
4640
match get d a with
4641
| None -> false
4642
| Some va ->
4643
match to_real_fwd fm minf pinf va with
4644
| None -> false
4645
| Some ra ->
4646
let m = to_a nl' in
4647
let ml = to_a (neg nl') in
4648
let da = getd_f d a umin umax psb minf pinf in
4649
if in_range_a ml m ra && FD.is_exact umin' psb' da then begin
4650
{proof…}
4651
if pure { live d } then begin
4652
let ghost x = d.mf a in
4653
let ghost md = any mode ensures { d.mf r = fp_convert fm' result x } in
4654
assert { nl' = of_index fm' (nb_sign fm' - 2) };
4655
assert { mem x va };
4656
assert { is_not_nan x /\ not (is_inf x) /\ rmem (to_real x) ra };
4657
assert { ext x = Fin (to_real x) };
4658
assert { FD.finite x };
4659
assert { D.mem (to_real x) da };
4660
assert { D.fix (to_real x) (ulp_min fm') /\ D.flt (to_real x) (sb fm') };
4661
assert { A.real ml <=. to_real x <=. A.real m };
4662
max_facts fm'; neg_fin nl';
4663
assert { ext (neg nl') = Fin (-. to_real nl') };
4664
assert { -. to_real nl' <=. to_real x <=. to_real nl' };
4665
FD.round_exact fm' md (if is_positive x then false else true) (to_real x);
4666
assert { d.mf r = round_f fm' md (if is_positive x then false else true) (Fin (to_real x)) }
4667
end;
4668
{qed}
4669
merge d tr ta; true
4670
end else false
4671
end
4672
end
4673
end
4674
| RBin o r a b -> dyadic_rbin d o r a b; false
4675
| RNeg r a -> dyadic_rneg d r a; false
4676
| AddSelf r a b t ->
4677
if is_equal d a b then begin register d t; mergef d r t; true end
4678
else false
4679
| NegInv r a ->
4680
(* `a = - b` gives `r = b` *)
4681
let s1 = match negs d a with
4682
| Some b -> {proof…} neg_neg (d.mf b); {qed} mergef d r b; true
4683
| None -> false
4684
end in
4685
(* `r = - c` gives `a = c` *)
4686
let s2 = match negs d r with
4687
| Some c -> {proof…} neg_neg (d.mf a); neg_neg (d.mf c); {qed} mergef d a c; true
4688
| None -> false
4689
end in
4690
(* the other terms `fp.neg` of the classes have their own propagator *)
4691
s1 && s2
4692
| AddOpp fm r m a b ->
4693
(* `a - c` with `fp.eq a c` true *)
4694
match negs d b with
4695
| Some c ->
4696
if rel_eq d fm a c then begin
4697
{proof…}
4698
assert { live d -> d.mf b = neg (d.mf c) /\ fp_eq (d.mf a) (d.mf c) };
4699
assert { live d -> d.mf r = fp_add (d.mm m) (d.mf a) (neg (d.mf c)) };
4700
{qed}
4701
let v = sub_eq_dom fm (consts fm) (get d a) in
4702
upd_dom d r v
4703
end
4704
| None -> ()
4705
end;
4706
match negs d a with
4707
| Some c ->
4708
if rel_eq d fm b c then begin
4709
{proof…}
4710
assert { live d -> d.mf a = neg (d.mf c) /\ fp_eq (d.mf b) (d.mf c) };
4711
if pure { live d } then add_comm (d.mm m) (d.mf a) (d.mf b);
4712
assert { live d -> d.mf r = fp_add (d.mm m) (d.mf b) (neg (d.mf c)) };
4713
{qed}
4714
let v = sub_eq_dom fm (consts fm) (get d b) in
4715
upd_dom d r v
4716
end
4717
| None -> ()
4718
end;
4719
let opp =
4720
match negs d b with
4721
| Some c -> is_equal d c a
4722
| None -> false
4723
end ||
4724
match negs d a with
4725
| Some c -> is_equal d c b
4726
| None -> false
4727
end in
4728
if opp then begin
4729
let (minf, pinf, nz, pz) = consts fm in
4730
let fin = match get d a with
4731
| Some va -> is_finite fm minf pinf va
4732
| None -> false
4733
end in
4734
{proof…}
4735
if pure { live d } then begin
4736
assert { d.mf b = neg (d.mf a) \/ d.mf a = neg (d.mf b) };
4737
neg_special (d.mf a); neg_special (d.mf b);
4738
if pure { is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) } then begin
4739
add_opp (d.mm m) (d.mf a) nz pz; add_opp (d.mm m) (d.mf b) nz pz
4740
end else begin
4741
add_opp_nan (d.mm m) (d.mf a); add_opp_nan (d.mm m) (d.mf b)
4742
end
4743
end;
4744
{qed}
4745
let (z, stop) = match mode d m with
4746
| Some RTN -> (singleton fm nz, true)
4747
| Some _ -> (singleton fm pz, true)
4748
| None -> (zeros fm nz pz, false)
4749
end in
4750
(* the domains of `a` and `b` then remove NaN from `r` *)
4751
upd_dom d r (if fin then z else union fm z (nan_dom fm));
4752
stop
4753
end
4754
else false
4755
| Mono o fm r m p q sw ->
4756
let (a, y) = mono_args o p q sw in
4757
let k = bk o in
4758
{proof…}
4759
if pure { live d } then begin
4760
match o with
4761
| OAdd -> add_comm (d.mm m) (d.mf p) (d.mf q)
4762
| OMul -> mul_comm (d.mm m) (d.mf p) (d.mf q)
4763
| ODiv -> ()
4764
end;
4765
assert { d.mf r = mop k (d.mm m) (d.mf a) (d.mf y) }
4766
end;
4767
{qed}
4768
match mono_dir d k fm a with
4769
| Some i -> mono_pairs d k fm r m a y i (sibs d k fm m a r)
4770
| None -> ()
4771
end;
4772
false
4773
| Rel o fm r m a b ->
4774
match o with
4775
| ODiv -> rel_div d fm r a b
4776
| OAdd -> rel_avg d fm r m a b (divs d fm r)
4777
| OMul -> ()
4778
end;
4779
false
4780
| Rule o fm r _ a b ->
4781
match get d a, get d b with
4782
| Some va, Some vb ->
4783
(* nothing when both are singletons (the domains then decide) *)
4784
match FE.is_singleton va, FE.is_singleton vb with
4785
| (No, _) | (_, No) ->
4786
match o with
4787
| ODiv -> act d fm (decide o fm va vb) r a
4788
| _ ->
4789
act d fm (decide o fm va vb) r b;
4790
act d fm (decide o fm vb va) r a
4791
end
4792
| _ -> ()
4793
end
4794
| _ -> ()
4795
end;
4796
false
4797
| Neg r a ->
4798
{proof…} if pure { live d } then neg_neg (d.mf a); {qed}
4799
match get d a with
4800
| Some va -> upd_dom d r (neg_dom (fmt_of a) va)
4801
| None -> ()
4802
end;
4803
match get d r with
4804
| Some vr -> upd_dom d a (neg_dom (fmt_of a) vr)
4805
| None -> ()
4806
end;
4807
false
4808
end

The registered propagators

The run has one model (the values of the nodes, model_of). The e–graph is backtracked: a decision (or an assumption) of a branch makes it live only if the model satisfies it, the backtracking restores the previous state. A propagator registered by Conv.convert in an environment d0 records its model and whether d0 is live (reg): it holds in the environments of that model when d0 is live (valid_at), from the facts read in d0, the semantics of the terms included (Conv.view). The daemons of colibri2 run it only while it is registered, on the branch of d0 or below, which has the same model and is live only if d0 is: the requires of run_reg and may_change_reg, trusted (assumed by the wiring of fp_conv_w.ml).

A propagator that holds in every live environment, of either access (the meaning of the terms)

4827
predicate
valid
(p: prop) =
4828
wf p /\ (forall d: env. live d -> holds d p) /\
4829
(forall d: envp ro. live d -> holds d p)

The model of an environment (colibrilib/env.mlw)

4832
function
model_of
(d: envp 'm) : model = d.model

A propagator that holds in the environments of the model m when l (the environment where it is registered is live)

4836
predicate
valid_at
(m: model) (l: bool) (p: prop) =
4837
wf p /\ (l -> (forall d: env. model_of d = m -> holds d p) /\
4838
(forall d: envp ro. model_of d = m -> holds d p))
4839
Valid (54ms) (colibri2)
4840
type
reg
= {
rp
: prop; ghost
rm
: model; ghost
rl
: bool }
4841
invariant { valid_at rm rl rp }
4842
by { rp = (let x = any Atom.t in Choice x x x); rm = any model; rl = false }

The propagator p, registered in d

  Valid (59ms) (colibri2)
4845
let
mk_reg
(d: env) (p: prop) : reg
4846
requires { valid_at (model_of d) (live d) p }
4847
ensures { result.rp = p /\ result.rm = model_of d /\ result.rl = live d }
4848
= { rp = p; rm = pure { model_of d }; rl = pure { live d } }
4849
Valid (41ms) (colibri2)
4850
let
run_reg
(d: env) (r: reg) : bool
4851
requires { model_of d = r.rm /\ (live d -> r.rl) }
4852
= run d r.rp
4853
Valid (53ms) (colibri2)
4854
let
may_change_reg
(d: envp ro) (r: reg) : bool
4855
requires { model_of d = r.rm /\ (live d -> r.rl) }
4856
= may_change d r.rp
4857
end