library colibrilib.fp_conv — module Rulesmodule Rules1460use int.Int1461use int.Power1462use real.Truncate1463use list.List1464use option.Option1465use colibrilib.ring.Atom1466use colibrilib.fbin.Fp1467use colibrilib.fp_facts.Facts1468use colibrilib.fp.Ereal1469use colibrilib.fp_interval.Intervals1470use colibrilib.fp_interval.FpInterval1471use colibrilib.fp_interval.Rules as IR1472use colibrilib.fp_interval.Export as FE1473use real.RealInfix1474use real.FromInt1475use Env1476use RealConv1477use BvConv1478use colibrilib.dyadic.Dyadic as D1479use colibrilib.fp_dyadic.Rules as FD1480use colibrilib.pow2r.Pow2r1481use colibrilib.dv.Dv1482use int.EuclideanDivision as E1483use colibrilib.zinterval.Zi as Zi1484use RelDb as RD1485use Terms1486
The binary operations with a rounding mode
type bop = OAdd | OMul | ODiv1489
The binary operations on the reals
type rop = RAdd | RSub | RMul14921493function rfun (o: rop) (x y: real) : real =1494match o with RAdd -> x +. y | RSub -> x -. y | RMul -> x *. y end14951496function fop (o: bop) (md: mode) (x y: t) : t =1497match o with1498| OAdd -> fp_add md x y1499| OMul -> fp_mul md x y1500| ODiv -> fp_div md x y1501end1502
The unary operations with a rounding mode
type uop = USqrt | URti15051506function fop1 (o: uop) (md: mode) (x: t) : t =1507match o with1508| USqrt -> fp_sqrt md x1509| URti -> fp_rti md x1510end1511
The comparisons (fp.geq and fp.gt are CLe and CLt with the arguments swapped)
type cop = CLe | CLt | CEq15151516predicate fcmp (o: cop) (x y: t) =1517match o with1518| CLe -> fp_le x y1519| CLt -> fp_lt x y1520| CEq -> fp_eq x y1521end1522
The predicates fp.isNaN, fp.isNormal, fp.isSubnormal, fp.isZero, fp.isInfinite, fp.isNegative, fp.isPositive and fp.isFinite
type ipred = INaN | INormal | ISubnormal | IZero | IInf | INeg | IPos | IFinite15271528predicate fis (o: ipred) (x: t) =1529match o with1530| INaN -> is_nan x1531| INormal -> is_normal x1532| ISubnormal -> is_subnormal x1533| IZero -> is_zero x1534| IInf -> is_inf x1535| INeg -> is_not_nan x /\ not (is_positive x)1536| IPos -> is_not_nan x /\ is_positive x1537| IFinite -> is_not_nan x /\ not (is_inf x)1538end1539
A propagator, for a term in the format fm:
Bin o fm r m a b: r = o m a b (fp.add, fp.mul, fp.div);Un o fm r m a: r = o m a (fp.sqrt, fp.roundToIntegral);Cvt fm fm' r m a: r is the conversion of a to the format fm' (to_fp of a float);Abs fm r a: r = fp.abs a; Neg r a: r = fp.neg a;Choice r a b: r = a or r = b (fp.min, fp.max: SMT–LIB leaves the result of -0 and +0 unspecified);Cmp o fm r a b: the Boolean r is o a b;Is o fm r a: the Boolean r is o a;ToReal fm r a: the real r is fp.to_real a, when a is finite (unspecified otherwise);OfReal fm r m a: r is to_fp of the real a in the format fm;OfBits fm r a back: r is the float of the encoding a, the integer node of a bit–vector (to_fp of a bit–vector); the domain of a is updated only when back;ToRealIn fm r a lo hi: the real r is fp.to_real a when a is finite and its real in [lo, hi] (fp.to_sbv and fp.to_ubv, with a the rounding to an integral float and r the integer node of the result);ExactInt fm r a t: r is to_fp of the integer a in some mode and the real t is fp.to_real r when r is finite (to_fp_signed and to_fp_unsigned): t is merged with a when the conversion is exact;ExactCvt fm fm' r a tr ta: r is to_fp of the float a in some mode, tr and ta are fp.to_real r and fp.to_real a: they are merged when the format fm' is wider and a is finite;RBin o r a b, RNeg r a: the real r is a + b, a - b, a * b, - a (the terms of the LRA theory, for the dyadic domain of the reals)type prop =1572| Bin bop format Atom.t Atom.t Atom.t Atom.t1573| Un uop format Atom.t Atom.t Atom.t1574| Cvt format format Atom.t Atom.t Atom.t1575| Abs format Atom.t Atom.t1576| Neg Atom.t Atom.t1577| Choice Atom.t Atom.t Atom.t1578| Cmp cop format Atom.t Atom.t Atom.t1579| Is ipred format Atom.t Atom.t1580| ToReal format Atom.t Atom.t1581| OfReal format Atom.t Atom.t Atom.t1582| OfBits format Atom.t Atom.t bool1583| ToRealIn format Atom.t Atom.t int int1584| ExactInt format Atom.t Atom.t Atom.t1585| ExactCvt format format Atom.t Atom.t Atom.t Atom.t1586| RBin rop Atom.t Atom.t Atom.t1587| RNeg Atom.t Atom.t1588| AddSelf Atom.t Atom.t Atom.t Atom.t1589
AddSelf r a b t: r is t when a is b (r = a + b and t = 2 * a)
| NegInv Atom.t Atom.t1592
NegInv r a: r = - a, as Neg: - (- b) is b, and - a = - c gives a = c
| AddOpp format Atom.t Atom.t Atom.t Atom.t1595
AddOpp fm r m a b: r = a + b, as Bin OAdd: a + (- a) is a zero
| Rule bop format Atom.t Atom.t Atom.t Atom.t1598
r = a o b, as Bin: the rules on the sign and the magnitude of the arguments (fp_interval.Rules)
| Rel bop format Atom.t Atom.t Atom.t Atom.t1601
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
| Mono bop format Atom.t Atom.t Atom.t Atom.t bool1605
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)
type builtin =1611| FpBin bop format1612| FpAdd format1613
with the float 2 and the term 2 * a
| FpUn uop format1614| FpCvt format format1615| FpAbs format1616| FpNeg1617| FpChoice1618| FpCmp cop format1619| FpIs ipred format1620| FpToReal format1621| FpOfReal format1622| FpOfBits format bool1623
to_fp of the integer of a bit–vector
| FpExactInt format1624
the conversion of an integer, often exact
| FpRw1625
the term is another float term (a rewriting)
| FpToRealIn format int int1626
fp.to_sbv, fp.to_ubv
| RealBin rop1627| RealNeg1628| Other1629
The formats of the nodes, from their types
predicate wf (p: prop) =1632match p with1633| Bin _ fm r _ a b | Rule _ fm r _ a b | Rel _ fm r _ a b | Mono _ fm r _ a b _ ->1634fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm1635| Un _ fm r _ a | Abs fm r a -> fmt_of r = fm /\ fmt_of a = fm1636| Cvt fm fm' r _ a -> fmt_of r = fm' /\ fmt_of a = fm1637| Neg r a | NegInv r a -> fmt_of r = fmt_of a1638| AddOpp fm r _ a b -> fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm1639| Choice r a b -> fmt_of r = fmt_of a /\ fmt_of b = fmt_of a1640| Cmp _ fm _ a b -> fmt_of a = fm /\ fmt_of b = fm1641| Is _ fm _ a -> fmt_of a = fm1642| ToReal fm _ a -> fmt_of a = fm1643| OfReal fm r _ _ -> fmt_of r = fm1644| OfBits fm r _ _ -> fmt_of r = fm1645| ToRealIn fm _ a _ _ -> fmt_of a = fm1646| ExactInt fm r _ _ -> fmt_of r = fm1647| ExactCvt fm fm' r a _ _ -> fmt_of r = fm' /\ fmt_of a = fm1648| RBin _ _ _ _ | RNeg _ _ | AddSelf _ _ _ _ -> true1649end1650
The meaning of the propagator in the model
predicate holds (d: envp 'm) (p: prop) =1653match p with1654| 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 _ ->1655fmt (d.mf r) = fm /\ fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\1656d.mf r = fop o (d.mm m) (d.mf a) (d.mf b)1657| Un o fm r m a ->1658fmt (d.mf r) = fm /\ fmt (d.mf a) = fm /\ d.mf r = fop1 o (d.mm m) (d.mf a)1659| Cvt fm fm' r m a ->1660fmt (d.mf r) = fm' /\ fmt (d.mf a) = fm /\1661d.mf r = fp_convert fm' (d.mm m) (d.mf a)1662| Abs fm r a -> fmt (d.mf a) = fm /\ d.mf r = abs (d.mf a)1663| Neg r a | NegInv r a -> fmt (d.mf a) = fmt_of a /\ d.mf r = neg (d.mf a)1664| AddOpp fm r m a b ->1665fmt (d.mf r) = fm /\ fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\1666d.mf r = fp_add (d.mm m) (d.mf a) (d.mf b)1667| Choice r a b -> d.mf r = d.mf a \/ d.mf r = d.mf b1668| Cmp o fm r a b ->1669fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\ (d.mb r <-> fcmp o (d.mf a) (d.mf b))1670| Is o fm r a -> fmt (d.mf a) = fm /\ (d.mb r <-> fis o (d.mf a))1671| ToReal fm r a ->1672fmt (d.mf a) = fm /\1673(is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) -> d.mr r = to_real (d.mf a))1674| OfReal fm r m a -> d.mf r = round_x fm (d.mm m) (d.mr a)1675| OfBits fm r a _ ->1676exists b. d.mr a = from_int b /\ 0 <= b < 2 * half_bits fm /\ of_bits fm b (d.mf r)1677| ToRealIn fm r a lo hi ->1678fmt (d.mf a) = fm /\1679(is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) /\1680from_int lo <=. to_real (d.mf a) <=. from_int hi -> d.mr r = to_real (d.mf a))1681| ExactInt fm r a t ->1682(exists md. d.mf r = round_x fm md (d.mr a)) /\1683(exists n. d.mr a = from_int n) /\1684(is_not_nan (d.mf r) /\ not (is_inf (d.mf r)) -> d.mr t = to_real (d.mf r))1685| ExactCvt fm fm' r a tr ta ->1686fmt (d.mf a) = fm /\ (exists md. d.mf r = fp_convert fm' md (d.mf a)) /\1687(is_not_nan (d.mf r) /\ not (is_inf (d.mf r)) -> d.mr tr = to_real (d.mf r)) /\1688(is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) -> d.mr ta = to_real (d.mf a))1689| RBin o r a b -> d.mr r = rfun o (d.mr a) (d.mr b)1690| RNeg r a -> d.mr r = -. d.mr a1691| AddSelf r a b t -> d.mf a = d.mf b -> d.mf r = d.mf t1692end1693
The conversion of a finite float to a wider format is exact
Valid (116ms) (colibri2)let ghost convert_wider (fm': format) (md: mode) (x: t) : unit1696requires { eb (fmt x) <= eb fm' /\ sb (fmt x) <= sb fm' }1697requires { is_not_nan x /\ not (is_inf x) }1698ensures { is_not_nan (fp_convert fm' md x) /\ not (is_inf (fp_convert fm' md x)) }1699ensures { to_real (fp_convert fm' md x) = to_real x }1700= {proof…}1701let y = widen_exact fm' x in1702let z = if is_positive y then false else true in1703assert { round_f fm' md z (ext y) = y };1704round_f_val fm' md (if is_positive x then false else true) z (ext x);1705assert { ext (fp_convert fm' md x) = ext x }1706{qed}1707
The conversion of an integer that is a float is exact
Valid (675ms) (colibri2)let ghost round_int_exact (fm: format) (md: mode) (n: int) : unit1710requires { - power 2 (sb fm) <= n <= power 2 (sb fm) }1711requires { -. to_real (of_index fm (nb_sign fm - 2)) <=. from_int n <=.1712to_real (of_index fm (nb_sign fm - 2)) }1713ensures { to_real (round_x fm md (from_int n)) = from_int n }1714ensures { is_not_nan (round_x fm md (from_int n)) /\1715not (is_inf (round_x fm md (from_int n))) }1716= {proof…}1717let x = int_exact fm n in1718let z = if is_positive x then false else true in1719assert { round_f fm md z (ext x) = x };1720round_f_val fm md (from_int n <. 0.0) z (Fin (from_int n));1721assert { ext (round_x fm md (from_int n)) = Fin (from_int n) }1722{qed}1723
upd, or the contradiction for the empty domain
Valid (24ms) (colibri2)let upd_dom (d: env) (n: Atom.t) (v: dom) : unit1726requires { live d -> mem (d.mf n) v }1727= match v.u with1728| Nil -> if v.nan then upd d n v else contradiction d1729| _ -> upd d n v1730end1731
The union of two optional domains, None for the empty one
Valid (53ms) (colibri2)let union_o (ghost fm: format) (a b: option dom) : option dom1734requires { match a with Some v -> v.fm = fm | None -> true end }1735requires { match b with Some v -> v.fm = fm | None -> true end }1736ensures { match result with Some v -> v.fm = fm | None -> true end }1737ensures { forall x. (match a with Some v -> mem x v | None -> false end) \/1738(match b with Some v -> mem x v | None -> false end) ->1739match result with Some v -> mem x v | None -> false end }1740= match a, b with1741| None, o | o, None -> o1742| Some a, Some b -> Some (union fm a b)1743end1744
The results of o in the mode md
Valid (41ms) (colibri2)let fwd1 (ghost fm: format) (c: (t, t, t, t)) (o: bop) (md: mode) (va vb: dom) : dom1749requires { consts_ok fm c }1750requires { va.fm = fm /\ vb.fm = fm }1751ensures { result.fm = fm }1752ensures { forall x y. mem x va -> mem y vb -> mem (fop o md x y) result }1753= let (minf, pinf, nz, pz) = c in1754match o with1755| OAdd -> add_dom fm minf pinf md va vb1756| OMul -> mul_dom fm minf pinf nz pz md va vb1757| ODiv -> div_dom fm minf pinf nz pz md va vb1758end1759
In the mode, or in any mode when it is unknown
Valid (956ms) (cvc4)let fwd (ghost fm: format) (c: (t, t, t, t)) (o: bop) (om: option mode) (va vb: dom)1762: dom1763requires { consts_ok fm c }1764requires { va.fm = fm /\ vb.fm = fm }1765ensures { result.fm = fm }1766ensures { forall md x y. (om = None \/ om = Some md) -> mem x va -> mem y vb ->1767mem (fop o md x y) result }1768= match om with1769| Some md -> fwd1 fm c o md va vb1770| None ->1771let r1 = fwd1 fm c o RNE va vb in1772let r2 = fwd1 fm c o RNA va vb in1773let r3 = fwd1 fm c o RTP va vb in1774let r4 = fwd1 fm c o RTN va vb in1775let r5 = fwd1 fm c o RTZ va vb in1776union fm r1 (union fm r2 (union fm r3 (union fm r4 r5)))1777end1778
The bounds of x when x + y is in the intervals l, any mode
Valid (1.6s) (cvc5)let rec bounds_u (ghost fm: format) (l: list (t, t)) : option dom1783requires { fmt_u fm l }1784ensures { match result with1785| Some b -> b.fm = fm /\1786forall md x y. fmt x = fm -> fmt y = fm -> mem_u (fp_add md x y) l -> mem x b1787| None -> true1788end }1789variant { l }1790= match l with1791| Nil -> None1792| Cons (lo, hi) l' ->1793match add_bounds lo hi with1794| None -> None1795| Some (a, b) ->1796if is_nan a || is_nan b || not le_diff_zero a b then None1797else begin1798let h = interval fm a b in1799{proof…}1800let lemma pt (md: mode) (x y: t) : unit1801requires { fmt x = fm /\ fmt y = fm /\ in_iv (fp_add md x y) lo hi }1802ensures { mem x h }1803= add_special md x y in1804{qed}1805match l' with1806| Nil -> Some h1807| _ ->1808match bounds_u fm l' with1809| None -> None1810| Some r -> Some (union fm h r)1811end1812end1813end1814end1815end1816
The bounds of x when x + y is in r, any mode; None: no bound
Valid (46ms) (colibri2)let operand_bounds (ghost fm: format) (r: dom) : option dom1819requires { r.fm = fm }1820ensures { match result with1821| Some b -> b.fm = fm /\1822forall md x y. fmt x = fm -> fmt y = fm -> mem (fp_add md x y) r -> mem x b1823| None -> true1824end }1825= if r.nan then None1826else match bounds_u fm r.u with1827| Some b -> Some b1828| None -> None1829end1830
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)let add_back (ghost fm: format) (c: (t, t, t, t)) (md: mode) (r e cur: dom) : option dom1834requires { consts_ok fm c }1835requires { r.fm = fm /\ e.fm = fm /\ cur.fm = fm }1836ensures { match result with Some v -> v.fm = fm | None -> true end }1837ensures { forall x y. mem x cur -> mem y e -> mem (fp_add md x y) r ->1838match result with Some v -> mem x v | None -> false end }1839= let (minf, pinf, nz, pz) = c in1840let h = add_back_fin fm minf pinf nz pz md r e in1841let h = match operand_bounds fm r with1842| None -> Some h1843| Some b -> inter fm h b1844end in1845match h with1846| None -> None1847| Some h ->1848match inter fm h cur with1849| None -> None1850| Some h -> Some (add_shave fm minf pinf md r e h)1851end1852end1853
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
predicate back_ok (o: bop) (md: mode) (snd: bool) (r e cur: dom) (res: option dom) =1858forall x y.1859if snd then mem x e -> mem y cur -> mem (fop o md x y) r ->1860match res with Some v -> mem y v | None -> false end1861else mem x cur -> mem y e -> mem (fop o md x y) r ->1862match res with Some v -> mem x v | None -> false end1863Valid (1.2s) (colibri2 19) (split_vc 2) (depth 2)1864let back1 (ghost fm: format) (c: (t, t, t, t)) (o: bop) (md: mode) (snd: bool)1865(r e cur: dom) : option dom1866requires { consts_ok fm c }1867requires { r.fm = fm /\ e.fm = fm /\ cur.fm = fm }1868ensures { match result with Some v -> v.fm = fm | None -> true end }1869ensures { back_ok o md snd r e cur result }1870= let (minf, pinf, nz, pz) = c in1871match o with1872| OAdd ->1873{proof…}1874let lemma comm (x y: t) : unit1875requires { fmt x = fm /\ fmt y = fm } ensures { fp_add md x y = fp_add md y x }1876= add_comm md x y in1877{qed}1878add_back fm c md r e cur1879| OMul ->1880let v = mul_back fm minf pinf nz pz md r e in1881inter fm v cur1882| ODiv ->1883let v = if snd then div_back_den fm minf pinf nz pz md r e1884else div_back_num fm minf pinf nz pz md r e in1885inter fm v cur1886end1887
In the mode, or in any mode when it is unknown
Valid (811ms) (colibri2 32) (cvc5) (split_vc 3) (depth 2)let back (ghost fm: format) (c: (t, t, t, t)) (o: bop) (om: option mode) (snd: bool)1890(r e cur: dom) : option dom1891requires { consts_ok fm c }1892requires { r.fm = fm /\ e.fm = fm /\ cur.fm = fm }1893ensures { match result with Some v -> v.fm = fm | None -> true end }1894ensures { forall md. (om = None \/ om = Some md) -> back_ok o md snd r e cur result }1895= match om with1896| Some md -> back1 fm c o md snd r e cur1897| None ->1898let r1 = back1 fm c o RNE snd r e cur in1899let r2 = back1 fm c o RNA snd r e cur in1900let r3 = back1 fm c o RTP snd r e cur in1901let r4 = back1 fm c o RTN snd r e cur in1902let r5 = back1 fm c o RTZ snd r e cur in1903let u45 = union_o fm r4 r5 in1904let u35 = union_o fm r3 u45 in1905let u25 = union_o fm r2 u35 in1906let u = union_o fm r1 u25 in1907{proof…}1908let lemma sub (a: option dom) (y: t) : unit1909requires { a = r1 \/ a = r2 \/ a = r3 \/ a = r4 \/ a = r5 }1910requires { match a with Some v -> mem y v | None -> false end }1911ensures { match u with Some v -> mem y v | None -> false end }1912= () in1913let lemma all (md: mode) : unit1914ensures { back_ok o md snd r e cur u }1915= match md with1916| RNE -> assert { back_ok o md snd r e cur r1 }1917| RNA -> assert { back_ok o md snd r e cur r2 }1918| RTP -> assert { back_ok o md snd r e cur r3 }1919| RTN -> assert { back_ok o md snd r e cur r4 }1920| RTZ -> assert { back_ok o md snd r e cur r5 }1921end in1922{qed}1923u1924end1925
Valid (38ms) (colibri2)let fwd_u1 (ghost fm: format) (c: (t, t, t, t)) (o: uop) (md: mode) (va: dom) : dom1929requires { consts_ok fm c }1930requires { va.fm = fm }1931ensures { result.fm = fm }1932ensures { forall x. mem x va -> mem (fop1 o md x) result }1933= let (_, _, nz, _) = c in1934match o with1935| USqrt -> sqrt_dom fm nz md va1936| URti -> rti_dom fm md va1937end1938Valid (558ms) (cvc5)1939let fwd_u (ghost fm: format) (c: (t, t, t, t)) (o: uop) (om: option mode) (va: dom)1940: dom1941requires { consts_ok fm c }1942requires { va.fm = fm }1943ensures { result.fm = fm }1944ensures { forall md x. (om = None \/ om = Some md) -> mem x va ->1945mem (fop1 o md x) result }1946= match om with1947| Some md -> fwd_u1 fm c o md va1948| None ->1949union fm (fwd_u1 fm c o RNE va) (union fm (fwd_u1 fm c o RNA va)1950(union fm (fwd_u1 fm c o RTP va)1951(union fm (fwd_u1 fm c o RTN va) (fwd_u1 fm c o RTZ va))))1952end19531954predicate back_u_ok (o: uop) (md: mode) (r cur: dom) (res: option dom) =1955forall x. mem x cur -> mem (fop1 o md x) r ->1956match res with Some v -> mem x v | None -> false end1957Valid (600ms) (colibri2)1958let back_u1 (ghost fm: format) (c: (t, t, t, t)) (o: uop) (md: mode) (r cur: dom)1959: option dom1960requires { consts_ok fm c }1961requires { r.fm = fm /\ cur.fm = fm }1962ensures { match result with Some v -> v.fm = fm | None -> true end }1963ensures { back_u_ok o md r cur result }1964= let (minf, pinf, nz, pz) = c in1965let v = match o with1966| USqrt -> sqrt_back fm minf pinf nz pz md r1967| URti -> rti_back fm minf pinf md r1968end in1969inter fm v cur1970Valid (1.2s) (colibri2 19) (cvc5 4) (split_vc) (depth 1)1971let back_u (ghost fm: format) (c: (t, t, t, t)) (o: uop) (om: option mode) (r cur: dom)1972: option dom1973requires { consts_ok fm c }1974requires { r.fm = fm /\ cur.fm = fm }1975ensures { match result with Some v -> v.fm = fm | None -> true end }1976ensures { forall md. (om = None \/ om = Some md) -> back_u_ok o md r cur result }1977= match om with1978| Some md -> back_u1 fm c o md r cur1979| None ->1980let res = union_o fm (back_u1 fm c o RNE r cur)1981(union_o fm (back_u1 fm c o RNA r cur)1982(union_o fm (back_u1 fm c o RTP r cur)1983(union_o fm (back_u1 fm c o RTN r cur) (back_u1 fm c o RTZ r cur)))) in1984{proof…}1985let lemma pt (md: mode) : unit1986ensures { back_u_ok o md r cur res }1987= match md with1988| RNE -> () | RNA -> () | RTP -> () | RTN -> () | RTZ -> ()1989end in1990{qed}1991res1992end1993
Valid (508ms) (cvc5)let fwd_c (ghost fm: format) (fm': format) (om: option mode) (va: dom) : dom1997requires { va.fm = fm }1998ensures { result.fm = fm' }1999ensures { forall md x. (om = None \/ om = Some md) -> mem x va ->2000mem (fp_convert fm' md x) result }2001= match om with2002| Some md -> convert_dom fm fm' md va2003| None ->2004union fm' (convert_dom fm fm' RNE va) (union fm' (convert_dom fm fm' RNA va)2005(union fm' (convert_dom fm fm' RTP va)2006(union fm' (convert_dom fm fm' RTN va) (convert_dom fm fm' RTZ va))))2007end20082009predicate back_c_ok (fm': format) (md: mode) (r cur: dom) (res: option dom) =2010forall x. mem x cur -> mem (fp_convert fm' md x) r ->2011match res with Some v -> mem x v | None -> false end2012Valid (369ms) (colibri2)2013let back_c1 (fm fm': format) (c c': (t, t, t, t)) (md: mode) (r cur: dom)2014: option dom2015requires { consts_ok fm c /\ consts_ok fm' c' }2016requires { r.fm = fm' /\ cur.fm = fm }2017ensures { match result with Some v -> v.fm = fm | None -> true end }2018ensures { back_c_ok fm' md r cur result }2019= let (minf, pinf, _, _) = c in2020let (minf', pinf', _, _) = c' in2021inter fm (convert_back fm fm' minf pinf minf' pinf' md r) cur2022Valid (1.5s) (colibri2 21) (cvc5) (split_vc) (depth 1)2023let back_c (fm fm': format) (c c': (t, t, t, t)) (om: option mode) (r cur: dom)2024: option dom2025requires { consts_ok fm c /\ consts_ok fm' c' }2026requires { r.fm = fm' /\ cur.fm = fm }2027ensures { match result with Some v -> v.fm = fm | None -> true end }2028ensures { forall md. (om = None \/ om = Some md) -> back_c_ok fm' md r cur result }2029= match om with2030| Some md -> back_c1 fm fm' c c' md r cur2031| None ->2032union_o fm (back_c1 fm fm' c c' RNE r cur)2033(union_o fm (back_c1 fm fm' c c' RNA r cur)2034(union_o fm (back_c1 fm fm' c c' RTP r cur)2035(union_o fm (back_c1 fm fm' c c' RTN r cur) (back_c1 fm fm' c c' RTZ r cur))))2036end2037
fcmp o with the arguments in this order, or swapped when rev
predicate fcmp_r (o: cop) (rev: bool) (x y: t) =2042if rev then fcmp o y x else fcmp o x y2043
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)let cmp_back (ghost fm: format) (c: (t, t, t, t)) (o: cop) (t rev: bool) (v: dom)2047: option dom2048requires { consts_ok fm c }2049requires { v.fm = fm }2050ensures { match result with Some r -> r.fm = fm | None -> true end }2051ensures { forall x y. mem x v -> fmt y = fm -> (t <-> fcmp_r o rev x y) ->2052match result with Some r -> mem y r | None -> false end }2053= let (minf, pinf, nz, pz) = c in2054match o, t, rev with2055| CLe, True, False -> cmp_true_le fm nz pz pinf v2056| CLe, True, True -> cmp_true_ge fm nz pz minf v2057| CLt, True, False -> cmp_true_lt fm nz pz pinf v2058| CLt, True, True -> cmp_true_gt fm nz pz minf v2059| CEq, True, _ -> cmp_true_eq fm nz pz v2060| CLe, False, False -> Some (cmp_false_le fm minf pinf nz pz v)2061| CLe, False, True -> Some (cmp_false_ge fm minf pinf nz pz v)2062| CLt, False, False -> Some (cmp_false_lt fm minf pinf nz pz v)2063| CLt, False, True -> Some (cmp_false_gt fm minf pinf nz pz v)2064| CEq, False, _ -> Some (cmp_false_eq fm minf pinf nz pz v)2065end2066
The floats of the format fm that satisfy o
Valid (529ms) (colibri2 15) (cvc5 3) (split_vc) (depth 1)let class_dom (ghost fm: format) (c k: (t, t, t, t)) (o: ipred) : dom2069requires { consts_ok fm c /\ classes_ok fm k }2070ensures { result.fm = fm }2071ensures { forall v. mem v result <-> fmt v = fm /\ fis o v }2072= let (minf, pinf, nz, pz) = c in2073let (sf, sl, nf, nl) = k in2074match o with2075| INaN -> nan_dom fm2076| INormal -> normal fm (neg nl) (neg nf) nf nl2077| ISubnormal -> subnormal fm (neg sl) (neg sf) sf sl2078| IZero -> zeros fm nz pz2079| IInf -> infinites fm minf pinf2080| INeg -> negatives fm minf nz2081| IPos -> positives fm pz pinf2082| IFinite -> finites fm (neg nl) nl2083end2084
colibrilib/fp_dyadic.mlw)ulp_min, ulp_max and sb of a format
Valid (42ms) (colibri2)let fmt_dy (fm: format) : (int, int, int)2089ensures { let (u, v, p) = result in2090u = ulp_min fm /\ v = ulp_max fm /\ p = sb fm }2091= let eb = fmt_eb fm in2092let sb = fmt_sb fm in2093let u = 3 - pow2 (eb - 1) - sb in2094(u, u + pow2 eb - 3, sb)2095Valid (44ms) (colibri2) (cvc5) (split_vc) (depth 1)2096let ghost abs_bound (n e: int) : unit2097ensures { -. (from_int (if n < 0 then - n else n) *. pow2r e) <=. from_int n *. pow2r e2098<=. from_int (if n < 0 then - n else n) *. pow2r e }2099= {proof…}2100if n < 0 then assert { from_int (- n) *. pow2r e = -. (from_int n *. pow2r e) }2101{qed}2102
A valuation bound of the nonzero floats of [a, b], a and b finite
Valid (536ms) (colibri2 11) (cvc5) (split_vc 4) (depth 2)let iv_hi (a b: t) : int2106requires { FD.finite a /\ FD.finite b }2107ensures { forall y. in_iv y a b -> to_real y <> 0.0 ->2108D.mem_hi (to_real y) (Some result) }2109= let (na, ea) = to_dyadic a in2110let (nb, eb) = to_dyadic b in2111let ha = D.log2_up na ea in2112let hb = D.log2_up nb eb in2113let h = if ha <= hb then hb else ha in2114{proof…}2115let lemma mem (y: t)2116requires { in_iv y a b /\ to_real y <> 0.0 }2117ensures { D.mem_hi (to_real y) (Some h) }2118= assert { to_real a <=. to_real y <=. to_real b };2119let ma = pure { from_int (if na < 0 then - na else na) *. pow2r ea } in2120let mb = pure { from_int (if nb < 0 then - nb else nb) *. pow2r eb } in2121abs_bound na ea;2122(* dead: such a `y` is below `2^(h+1)` *)2123if pure { D.fix (to_real y) (h + 1) } then [@smoke:dead] begin2124if pure { mb <=. ma } then begin2125assert { D.mem_hi (to_real y) (Some ha) };2126D.fix_mono (to_real y) (ha + 1) (h + 1);2127absurd2128end else begin2129assert { D.mem_hi (to_real y) (Some hb) };2130D.fix_mono (to_real y) (hb + 1) (h + 1);2131absurd2132end2133end in2134{qed}2135h2136
A valuation bound of the nonzero floats of a union of intervals
Valid (319ms) (colibri2 20) (split_vc 9) (depth 4)let rec union_hi (ghost fm: format) (minf pinf: t) (l: list (t, t)) : option int2139requires { ok_u l /\ fmt_u fm l }2140requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }2141ensures { match result with2142| Some h -> forall y. mem_u y l -> to_real y <> 0.0 -> D.mem_hi (to_real y) (Some h)2143| None -> true end }2144variant { l }2145= match l with2146| Nil -> None2147| Cons (a, b) r ->2148if is_inf_f fm minf pinf a || is_inf_f fm minf pinf b then None2149else begin2150let h = iv_hi a b in2151match r with2152| Nil -> Some h2153| _ ->2154match union_hi fm minf pinf r with2155| None -> None2156| Some h' ->2157let k = if h <= h' then h' else h in2158{proof…}2159let lemma mem (y: t)2160requires { mem_u y l /\ to_real y <> 0.0 }2161ensures { D.mem_hi (to_real y) (Some k) }2162= if pure { D.fix (to_real y) (k + 1) } then begin2163if pure { in_iv y a b } then D.fix_mono (to_real y) (h + 1) (k + 1)2164else D.fix_mono (to_real y) (h' + 1) (k + 1)2165end in2166{qed}2167Some k2168end2169end2170end2171end2172
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)let dom_dy (ghost fm: format) (umax: int) (minf pinf: t) (v: dom) : D.t2177requires { v.fm = fm }2178requires { fmt minf = fm /\ fmt pinf = fm /\ minf = minus_infinity fm /\ pinf = plus_infinity fm }2179ensures { forall y. mem y v -> FD.fmem y result }2180= let gen () : D.t2181ensures { forall y. mem y v -> FD.fmem y result }2182= let h = union_hi fm minf pinf v.u in2183D.mk None h None in2184match v.u with2185| Cons (a, b) Nil ->2186if is_inf_f fm minf pinf a then gen ()2187else if le_diff_zero b a then begin2188let (n, e) = to_dyadic a in2189let r = D.exact n e umax in2190{proof…}2191let lemma mem (y: t)2192requires { mem y v /\ FD.finite y }2193ensures { D.mem (to_real y) r }2194= assert { ext a = Fin (to_real a) /\ ext y = Fin (to_real y) };2195assert { ele (ext a) (ext y) /\ ele (ext y) (ext b) /\ ele (ext b) (ext a) } in2196{qed}2197r2198end else gen ()2199| _ -> gen ()2200end2201
The dyadic domain of a float node, met with the one of its format and the one of its interval domain
Valid (589ms) (cvc5)let getd_f (d: env) (n: Atom.t) (umin umax psb: int) (minf pinf: t) : D.t2205requires { live d -> umin = ulp_min (fmt (d.mf n)) /\ psb = sb (fmt (d.mf n)) }2206requires { let fm = fmt_of n in fmt minf = fm /\ fmt pinf = fm /\2207minf = minus_infinity fm /\ pinf = plus_infinity fm }2208ensures { live d -> FD.fmem (d.mf n) result }2209= let f = FD.float_dom umin psb in2210{proof…} if pure { live d } then FD.float_mem (d.mf n); {qed}2211let f = match get d n with2212| None -> f2213| Some v -> D.inter (dom_dy (fmt_of n) umax minf pinf v) f2214end in2215match getd d n with2216| None -> f2217| Some v -> D.inter v f2218end2219
The float node n is not a zero
Valid (103ms) (cvc5)let nonzero (d: env) (fm: format) (n: Atom.t) : bool2222requires { fmt_of n = fm /\ (live d -> fmt (d.mf n) = fm) }2223ensures { result -> live d -> not is_zero (d.mf n) }2224= let (_, _, nz, pz) = consts fm in2225match get d n with2226| None -> false2227| Some v ->2228match inter fm v (zeros fm nz pz) with2229| None -> true2230| Some _ -> false2231end2232end2233
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)let ghost bin_finite (o: bop) (md: mode) (x y: t) : unit2237requires { o <> ODiv /\ fmt x = fmt y /\ FD.finite (fop o md x y) }2238ensures { FD.finite x /\ FD.finite y }2239ensures { exists zn. fop o md x y = round_f (fmt x) md zn2240(Fin (if o = OAdd then to_real x +. to_real y else to_real x *. to_real y)) }2241= {proof…}2242match o with2243| OAdd ->2244assert { is_not_nan x /\ is_not_nan y /\ not opposite (ext x) (ext y) };2245assert { fp_add md x y = round_f (fmt x) md (add_zneg md x y) (eadd (ext x) (ext y)) };2246assert { eadd (ext x) (ext y) <> PInf /\ eadd (ext x) (ext y) <> MInf };2247assert { not is_infinity x /\ not is_infinity y };2248assert { ext x = Fin (to_real x) /\ ext y = Fin (to_real y) };2249assert { fop o md x y = round_f (fmt x) md (add_zneg md x y)2250(Fin (to_real x +. to_real y)) }2251| OMul ->2252assert { is_not_nan x /\ is_not_nan y };2253assert { not (is_zero x /\ is_infinity y) /\ not (is_infinity x /\ is_zero y) };2254assert { fp_mul md x y = round_f (fmt x) md (mul_zneg x y) (emul (ext x) (ext y)) };2255assert { emul (ext x) (ext y) <> PInf /\ emul (ext x) (ext y) <> MInf };2256assert { not is_infinity x /\ not is_infinity y };2257assert { ext x = Fin (to_real x) /\ ext y = Fin (to_real y) };2258assert { fop o md x y = round_f (fmt x) md (mul_zneg x y)2259(Fin (to_real x *. to_real y)) }2260| ODiv -> absurd2261end2262{qed}2263
A float that is not a zero has a nonzero real
Valid (32ms) (colibri2)let ghost nz_real (x: t) : unit2266requires { FD.finite x /\ not is_zero x }2267ensures { to_real x <> 0.0 }2268= {proof…} assert { ext x = Fin (to_real x) } {qed}2269
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)let ghost div_finite (md: mode) (x y: t) : unit2274requires { fmt x = fmt y /\ FD.finite (fp_div md x y) }2275ensures { FD.finite x }2276ensures { FD.finite y -> to_real y <> 0.0 /\ exists zn. fp_div md x y =2277round_f (fmt x) md zn (Fin (to_real x *. (1.0 /. to_real y))) }2278ensures { not FD.finite y -> is_zero (fp_div md x y) }2279= {proof…}2280div_special md x y;2281if pure { FD.finite y } then2282assert { fp_div md x y = round_f (fmt x) md (mul_zneg x y)2283(Fin (to_real x *. (1.0 /. to_real y))) }2284{qed}2285
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)let dyadic_iv (d: env) (fm: format) (n: Atom.t) : unit2290requires { fmt_of n = fm /\ (live d -> fmt (d.mf n) = fm) }2291= let (umin, umax, psb) = fmt_dy fm in2292let (minf, pinf, nz, pz) = consts fm in2293let dn = getd_f d n umin umax psb minf pinf in2294let ex = union fm (union fm (nan_dom fm) (infinites fm minf pinf)) (zeros fm nz pz) in2295let empty = match dn.D.lo, dn.D.hi with Some l, Some h -> h < l | _ -> false end in2296let lo = match dn.D.lo with2297| Some l -> lo_of fm minf pinf false (a_pow2 l)2298| None -> lo_of fm minf pinf true (a_of_int 0)2299end in2300let hi = match dn.D.hi, dn.D.prec with2301| Some h, Some p -> if 0 <= p then hi_of fm minf pinf true (a_pow2 (h + p)) else pinf2302| _ -> pinf2303end in2304let pos = interval_o fm lo hi in2305let npos = neg_dom fm pos in2306let v = if empty then ex else union fm ex (union fm pos npos) in2307{proof…}2308let lemma sound () : unit2309requires { live d }2310ensures { mem (d.mf n) v }2311= let x = d.mf n in2312if pure { is_nan x \/ is_inf x \/ is_zero x } then ()2313else begin2314assert { ext x = Fin (to_real x) };2315D.mag (to_real x) dn;2316let ghost y = if pure { 0.0 <. to_real x } then x else neg x in2317assert { ext y = Fin (to_real y) /\ 0.0 <. to_real y };2318assert { le_dz lo y };2319lt_le y pinf;2320assert { le_dz y hi }2321end in2322{qed}2323upd_dom d n v2324
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)let dyadic_div (d: env) (fm: format) (r m a b: Atom.t) : unit2331requires { fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm }2332requires { live d -> holds d (Bin ODiv fm r m a b) }2333= let (umin, umax, psb) = fmt_dy fm in2334let (minf, pinf, _, _) = consts fm in2335let da = getd_f d a umin umax psb minf pinf in2336let db = getd_f d b umin umax psb minf pinf in2337let s = D.mul da (D.inv db) in2338{proof…}2339let ghost x = d.mf a in2340let ghost y = d.mf b in2341let ghost z = d.mf r in2342let ghost sr = pure { to_real x *. (1.0 /. to_real y) } in2343let lemma exact () : unit2344requires { live d /\ FD.finite z /\ FD.finite y }2345ensures { FD.finite x /\ to_real y <> 0.0 /\ D.mem sr s }2346ensures { exists zn. z = round_f fm (d.mm m) zn (Fin sr) }2347= div_finite (d.mm m) x y in2348let lemma zero () : unit2349requires { live d /\ FD.finite z /\ not FD.finite y }2350ensures { to_real z = 0.0 }2351= div_finite (d.mm m) x y in2352{qed}2353let rf = FD.round_fwd fm umin umax psb s in2354{proof…} D.mem_zero rf; {qed}2355updd d r rf;2356match get d r with2357| None -> ()2358| Some vr ->2359if is_finite fm minf pinf vr then begin2360let rnz = nonzero d fm r in2361let bfin = match get d b with2362| None -> false | Some vb -> is_finite fm minf pinf vb end in2363if rnz || bfin then begin2364let dr = getd_f d r umin umax psb minf pinf in2365let ds = D.inter s (FD.round_back fm umin umax dr) in2366{proof…}2367let lemma back () : unit2368requires { live d /\ FD.finite x }2369ensures { D.mem sr ds /\ D.mem (to_real y) db /\ to_real x = sr *. to_real y }2370= assert { FD.finite z };2371if pure { FD.finite y } then begin2372exact ();2373assert { D.mem sr ds };2374assert { D.mem (to_real y) db }2375end else begin2376zero ();2377assert { is_zero z };2378assert { not rnz /\ not bfin };2379absurd2380end in2381{qed}2382updd d a (D.mul ds db)2383end2384end2385end;2386dyadic_iv d fm r; dyadic_iv d fm a2387
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)let dyadic_bin (d: env) (o: bop) (fm: format) (r m a b: Atom.t) : unit2393requires { fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm }2394requires { live d -> holds d (Bin o fm r m a b) }2395= match o with2396| ODiv -> dyadic_div d fm r m a b2397| _ ->2398let (umin, umax, psb) = fmt_dy fm in2399let (minf, pinf, _, _) = consts fm in2400let da = getd_f d a umin umax psb minf pinf in2401let db = getd_f d b umin umax psb minf pinf in2402let anz = nonzero d fm a in2403let bnz = nonzero d fm b in2404let s = match o with OAdd -> D.add da db anz bnz | _ -> D.mul da db end in2405{proof…}2406let ghost x = d.mf a in2407let ghost y = d.mf b in2408let ghost z = d.mf r in2409let ghost sr = match o with2410| OAdd -> to_real x +. to_real y | _ -> to_real x *. to_real y end in2411let lemma exact () : unit2412requires { live d /\ FD.finite z }2413ensures { FD.finite x /\ FD.finite y /\ D.mem sr s }2414ensures { exists zn. z = round_f fm (d.mm m) zn (Fin sr) }2415= bin_finite o (d.mm m) x y;2416if bnz then nz_real y in2417{qed}2418updd d r (FD.round_fwd fm umin umax psb s);2419match get d r with2420| None -> ()2421| Some vr ->2422if is_finite fm minf pinf vr then begin2423let dr = getd_f d r umin umax psb minf pinf in2424let ds = D.inter s (FD.round_back fm umin umax dr) in2425let rnz = nonzero d fm r in2426match o with2427| OAdd ->2428{proof…} assert { live d -> to_real x = sr -. to_real y /\2429to_real y = sr -. to_real x }; {qed}2430updd d a (D.sub ds db rnz bnz);2431updd d b (D.sub ds da rnz anz)2432| _ ->2433{proof…} assert { live d -> sr = to_real y *. to_real x }; {qed}2434updd d a (D.mul_back da ds db bnz);2435updd d b (D.mul_back db ds da anz)2436end2437end2438end;2439dyadic_iv d fm r; dyadic_iv d fm a; dyadic_iv d fm b2440end2441
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)let dyadic_cvt (d: env) (fm fm': format) (r m a: Atom.t) : unit2446requires { fmt_of r = fm' /\ fmt_of a = fm }2447requires { live d -> holds d (Cvt fm fm' r m a) }2448= let (umin, umax, psb) = fmt_dy fm in2449let (umin', umax', psb') = fmt_dy fm' in2450let (minf, pinf, _, _) = consts fm in2451let (minf', pinf', _, _) = consts fm' in2452let da = getd_f d a umin umax psb minf pinf in2453{proof…}2454let ghost x = d.mf a in2455{qed}2456if fmt_eb fm <= fmt_eb fm' && fmt_sb fm <= fmt_sb fm' then begin2457{proof…}2458let lemma wide () : unit2459requires { live d /\ FD.finite x }2460ensures { FD.finite (d.mf r) /\ to_real (d.mf r) = to_real x }2461= convert_wider fm' (d.mm m) x in2462{qed}2463updd d r da;2464let dr = getd_f d r umin' umax' psb' minf' pinf' in2465{proof…}2466let lemma back () : unit2467requires { live d /\ FD.finite x }2468ensures { D.mem (to_real x) dr }2469= wide (); assert { FD.fmem (d.mf r) dr } in2470{qed}2471updd d a dr2472end else begin2473updd d r (FD.round_fwd fm' umin' umax' psb' da);2474(* backward, when the result is finite: the real of `a` is in `round_back` of the domain of `r` *)2476match get d r with2477| Some vr ->2478if is_finite fm' minf' pinf' vr then begin2479let dr = getd_f d r umin' umax' psb' minf' pinf' in2480updd d a (FD.round_back fm' umin' umax' dr)2481end2482| None -> ()2483end2484end;2485dyadic_iv d fm' r; dyadic_iv d fm a2486
An interval without 0
Valid (316ms) (colibri2)let riv_nz (i: riv) : bool2491ensures { result -> forall x. rmem_iv x i -> x <> 0.0 }2492= let z = a_of_int 0 in2493match i with2494| RSing a -> not (a_eq a z)2495| RInter lo hi ->2496(match lo with2497| BInf -> false | BLarge a -> not (a_le a z) | BStrict a -> a_le z a end)2498|| (match hi with2499| BInf -> false | BLarge a -> not (a_le z a) | BStrict a -> a_le a z end)2500end2501
A union of intervals without 0
Valid (44ms) (colibri2)let rec rdom_nz (l: rdom) : bool2504ensures { result -> forall x. rmem x l -> x <> 0.0 }2505variant { l }2506= match l with2507| Nil -> true2508| Cons i l' -> riv_nz i && rdom_nz l'2509end2510
The real of n is nonzero (its interval domain)
Valid (45ms) (colibri2)let rnonzero (d: envp 'm) (n: Atom.t) : bool2513ensures { result -> live d -> d.mr n <> 0.0 }2514= match getr d n with None -> false | Some l -> rdom_nz l end2515
The dyadic domain of the reals of an interval domain: a dyadic singleton is exact
Valid (64ms) (colibri2)let rdom_dy (l: rdom) : D.t2519ensures { forall x. rmem x l -> D.mem x result }2520= match l with2521| Cons (RSing a) Nil ->2522match a_dyadic a with2523| Some (n, e) -> D.exact n e 02524| None -> D.top2525end2526| _ -> D.top2527end2528
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)let getdr_r (d: envp 'm) (n: Atom.t) : D.t2532ensures { live d -> D.mem (d.mr n) result }2533= let v = match getr d n with None -> D.top | Some l -> rdom_dy l end in2534let v = match getc d n with2535| NoCls -> v2536| Cls dv rm ->2537match a_dyadic dv, a_dyadic rm with2538| Some (dn, de), Some (rn, re) -> D.inter v (D.congr dn de rn re)2539| _ -> v2540end2541end in2542match getdr d n with None -> v | Some w -> D.inter v w end2543
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)let upd_real (d: env) (n: Atom.t) (v: D.t) : unit2547requires { live d -> D.mem (d.mr n) v }2548= upddr d n (D.clamp D.zbound v)2549
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)let has_dy (d: envp 'm) (n: Atom.t) : bool2553= match getdr d n with None -> false | Some _ -> true end2554
Tests of inclusion of the domains of the reals (sufficient)
Valid (50ms) (colibri2)let lo_in (b c: bnd) : bool2559ensures { result -> forall x. rmem_lo x b -> rmem_lo x c }2560= match b, c with2561| _, BInf -> true2562| BInf, _ -> false2563| BLarge a, BLarge e | BStrict a, BLarge e | BStrict a, BStrict e -> a_le e a2564| BLarge a, BStrict e -> not (a_le a e)2565end2566Valid (37ms) (colibri2)2567let hi_in (b c: bnd) : bool2568ensures { result -> forall x. rmem_hi x b -> rmem_hi x c }2569= match b, c with2570| _, BInf -> true2571| BInf, _ -> false2572| BLarge a, BLarge e | BStrict a, BLarge e | BStrict a, BStrict e -> a_le a e2573| BLarge a, BStrict e -> not (a_le e a)2574end2575Valid (47ms) (colibri2)2576let pt_in (a: A.t) (j: riv) : bool2577ensures { result -> rmem_iv (A.real a) j }2578= match j with2579| RSing e -> a_eq a e2580| RInter lo hi ->2581(match lo with BInf -> true | BLarge e -> a_le e a | BStrict e -> not (a_le a e) end) &&2582(match hi with BInf -> true | BLarge e -> a_le a e | BStrict e -> not (a_le e a) end)2583end2584Valid (32ms) (colibri2)2585let iv_in (i j: riv) : bool2586ensures { result -> forall x. rmem_iv x i -> rmem_iv x j }2587= match i, j with2588| RSing a, _ -> pt_in a j2589| RInter lo hi, RInter lo' hi' -> lo_in lo lo' && hi_in hi hi'2590| RInter _ _, RSing _ -> false2591end2592Valid (49ms) (colibri2)2593let rec iv_in_dom (i: riv) (v: rdom) : bool2594ensures { result -> forall x. rmem_iv x i -> rmem x v }2595variant { v }2596= match v with2597| Nil -> false2598| Cons j v' -> iv_in i j || iv_in_dom i v'2599end2600Valid (51ms) (colibri2)2601let rec dom_in (w v: rdom) : bool2602ensures { result -> forall x. rmem x w -> rmem x v }2603variant { w }2604= match w with2605| Nil -> true2606| Cons i w' -> iv_in_dom i v && dom_in w' v2607end2608
n 2^e is a multiple of 2^l (sufficient)
Valid (1.1s) (colibri2)let rec fix_test (n e l: int) : bool2611ensures { result -> D.fix (from_int n *. pow2r e) l }2612variant { if n < 0 then - n else n }2613= if n = 0 then begin {proof…} D.fix_zero l; {qed} true end2614else if l <= e then begin2615{proof…} dv_intro (from_int n *. pow2r e) (pow2r e) n; D.fix_mono (from_int n *. pow2r e) l e; {qed}2616true end2617else E.mod n 2 = 0 && fix_test (E.div n 2) (e + 1) l2618
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)let ghost class_in (rm dv: real) (l: int) : unit2622requires { D.fix rm l /\ D.fix dv l }2623ensures { forall x. (exists k: int. x = rm +. from_int k *. dv) -> D.fix x l }2624= {proof…}2625let lemma one (x: real) (k: int) : unit2626requires { x = rm +. from_int k *. dv }2627ensures { D.fix x l }2628= dv_intro (from_int k *. dv) dv k; dv_trans (from_int k *. dv) dv (pow2r l);2629D.fix_add rm (from_int k *. dv) l in2630()2631{qed}2632
The updates of the domain of the reals of n from its dyadic domain: the class 2^l ℤ (as (l, 2^l)), the intervals
type rivp = { rp_c: option (int, A.t); rp_v: option rdom }26362637predicate riv_sound (al: bool) (mr: Atom.t -> real) (n: Atom.t) (p: rivp) =2638(match p.rp_c with2639| Some (l, q) -> A.real q = pow2r l /\2640(al -> exists k: int. mr n = 0.0 +. from_int k *. A.real q)2641| None -> true end) /\2642(match p.rp_v with Some v -> al -> rmem (mr n) v | None -> true end)2643
The updates change nothing
predicate riv_noop (ri: Atom.t -> real -> bool) (n: Atom.t) (p: rivp) =2646(match p.rp_c with2647| Some (_, q) -> dropped q \/2648forall x. ri n x -> exists k: int. x = 0.0 +. from_int k *. A.real q2649| None -> true end) /\2650(match p.rp_v with Some v -> forall x. ri n x -> rmem x v | None -> true end)2651
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)let riv_plan (d: envp 'm) (n: Atom.t) : rivp2657ensures { riv_sound d.alive d.mr n result }2658= let dn = getdr_r d n in2659let z = a_of_int 0 in2660let empty = match dn.D.lo, dn.D.hi with Some l, Some h -> h < l | _ -> false end in2661let (plo, nhi) = match dn.D.lo with2662| Some l -> let p = a_pow2 l in (BLarge p, BLarge (a_neg p))2663| None -> (BStrict z, BStrict z)2664end in2665let (phi, nlo) = match dn.D.hi, dn.D.prec with2666| Some h, Some p ->2667if 0 <= p then begin2668let q = a_pow2 (h + p) in (BStrict q, BStrict (a_neg q))2669end else (BInf, BInf)2670| _ -> (BInf, BInf)2671end in2672(* the congruence: a finite `lo` is the class `2^lo ℤ` (not for `{0}`, known by the intervals) *)2674let c = match dn.D.lo with2675| Some l ->2676if not empty then begin2677let p = a_pow2 l in2678{proof…}2679let lemma c () : unit2680requires { live d }2681ensures { exists k: int. d.mr n = 0.0 +. from_int k *. A.real p }2682= let k = quot (d.mr n) (pow2r l) in2683assert { d.mr n = 0.0 +. from_int k *. A.real p } in2684{qed}2685Some (l, p)2686end else None2687| None -> None2688end in2689let info = empty || (match dn.D.lo with Some _ -> true | None -> false end)2690|| (match phi with BInf -> false | _ -> true end) in2691if info then begin2692let v = if empty then Cons (RSing z) Nil2693else Cons (RInter nlo nhi) (Cons (RSing z) (Cons (RInter plo phi) Nil)) in2694{proof…}2695let lemma sound () : unit2696requires { live d }2697ensures { rmem (d.mr n) v }2698= if pure { d.mr n <> 0.0 } then D.mag (d.mr n) dn in2699{qed}2700{ rp_c = c; rp_v = Some v }2701end else { rp_c = c; rp_v = None }2702
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)let class_changes (d: envp 'm) (n: Atom.t) (l: int) (q: A.t) : bool2706requires { A.real q = pow2r l }2707ensures { not result -> dropped q \/2708forall x. d.ri n x -> exists k: int. x = 0.0 +. from_int k *. A.real q }2709= if c_dropped q then false else2710match getc d n with2711| NoCls -> true2712| Cls dv rm ->2713match a_dyadic dv, a_dyadic rm with2714| Some (n1, e1), Some (n2, e2) ->2715if fix_test n1 e1 l && fix_test n2 e2 l then begin2716{proof…}2717class_in (A.real rm) (A.real dv) l;2718assert { forall x. d.ri n x -> D.fix x l };2719let lemma conv (x: real) : unit2720requires { D.fix x l }2721ensures { exists k: int. x = 0.0 +. from_int k *. A.real q }2722= let k = quot x (pow2r l) in2723assert { x = 0.0 +. from_int k *. A.real q } in2724{qed}2725false end2726else true2727| _ -> true2728end2729end2730
Whether the updates change the domain of the reals of n
Valid (305ms) (colibri2 3) (split_vc 2) (depth 2)let riv_changes (d: envp 'm) (n: Atom.t) (p: rivp) : bool2733requires { riv_sound d.alive d.mr n p }2734ensures { not result -> riv_noop d.ri n p }2735= let cc = match p.rp_c with2736| None -> false2737| Some (l, q) -> class_changes d n l q2738end in2739let cv = match p.rp_v with2740| None -> false2741| Some v -> match getr d n with None -> true | Some w -> not (dom_in w v) end2742end in2743cc || cv2744
The updates; nothing changes when they change nothing
Valid (105ms) (colibri2)let riv_apply (d: env) (n: Atom.t) (p: rivp) : unit2747requires { riv_sound d.alive d.mr n p }2748ensures { riv_noop (old d.ri) n p -> d.ri = old d.ri /\ d.dy = old d.dy }2749= (match p.rp_c with Some (_, q) -> updc d n q (a_of_int 0) | None -> () end);2750match p.rp_v with Some v -> updr d n v | None -> () end2751Valid (33ms) (colibri2) (split_vc) (depth 1)2752let dyadic_riv (d: env) (n: Atom.t) : unit2753= riv_apply d n (riv_plan d n)2754
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)
predicate sound_l (al: bool) (mr: Atom.t -> real) (l: list (Atom.t, D.t)) =2764match l with2765| Nil -> true2766| Cons (n, v) l' -> (al -> D.mem (mr n) v) /\ sound_l al mr l'2767end2768predicate sound_plan (d: envp 'm) (l: list (Atom.t, D.t)) = sound_l d.alive d.mr l2769
No update of a plan changes the dyadic domains dy
predicate noop_plan (dy: Atom.t -> option D.t) (l: list (Atom.t, D.t)) =2772match l with2773| Nil -> true2774| Cons (n, v) l' -> dnoop (dy n) v /\ noop_plan dy l'2775end2776
Whether an update of a plan changes the dyadic domains
Valid (36ms) (colibri2)let rec changes (d: envp 'm) (l: list (Atom.t, D.t)) : bool2779ensures { result <-> not noop_plan d.dy l }2780variant { l }2781= match l with2782| Nil -> false2783| Cons (n, v) l' ->2784(match getdr d n with2785| None -> not (D.deq v D.top)2786| Some w -> not (D.deq (D.inter w v) w)2787end) || changes d l'2788end2789
The updates of a plan, in order; nothing changes when none changes the dyadic domains
Valid (41ms) (colibri2 5) (split_vc) (depth 1)let rec apply (d: env) (l: list (Atom.t, D.t)) : unit2793requires { sound_plan d l }2794ensures { noop_plan (old d.dy) l -> d.dy = old d.dy /\ d.ri = old d.ri }2795variant { l }2796= match l with2797| Nil -> ()2798| Cons (n, v) l' -> upddr d n v; apply d l'2799end2800
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)let rbin_plan (d: envp 'm) (o: rop) (r a b: Atom.t) : list (Atom.t, D.t)2808requires { live d -> d.mr r = rfun o (d.mr a) (d.mr b) }2809ensures { sound_plan d result }2810= let da = getdr_r d a in2811let db = getdr_r d b in2812let anz = rnonzero d a in2813let bnz = rnonzero d b in2814let vr = match o with2815| RAdd -> D.add da db anz bnz2816| RSub -> D.sub da db anz bnz2817| RMul -> D.mul da db2818end in2819let dr = D.inter (getdr_r d r) (D.clamp D.zbound vr) in2820let rnz = rnonzero d r in2821let (va, vb) = match o with2822| RAdd ->2823{proof…} assert { live d -> d.mr a = d.mr r -. d.mr b /\2824d.mr b = d.mr r -. d.mr a }; {qed}2825(D.sub dr db rnz bnz, D.sub dr da rnz anz)2826| RSub ->2827{proof…} assert { live d -> d.mr a = d.mr r +. d.mr b /\2828d.mr b = d.mr a -. d.mr r }; {qed}2829(D.add dr db rnz bnz, D.sub da dr anz rnz)2830| RMul ->2831{proof…} assert { live d -> d.mr r = d.mr b *. d.mr a }; {qed}2832(D.mul_back da dr db bnz, D.mul_back db dr da anz)2833end in2834let c = D.clamp D.zbound in2835Cons (a, c da) (Cons (b, c db) (Cons (r, c vr) (Cons (a, c va) (Cons (b, c vb) Nil))))2836
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)let rbin_check (d: envp 'm) (o: rop) (r a b: Atom.t) : bool2844requires { live d -> d.mr r = rfun o (d.mr a) (d.mr b) }2845= (has_dy d a || has_dy d b || has_dy d r) &&2846(changes d (rbin_plan d o r a b) ||2847riv_changes d r (riv_plan d r) || riv_changes d a (riv_plan d a) ||2848riv_changes d b (riv_plan d b))2849
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)let dyadic_rbin (d: env) (o: rop) (r a b: Atom.t) : unit2854requires { live d -> d.mr r = rfun o (d.mr a) (d.mr b) }2855= if has_dy d a || has_dy d b || has_dy d r then begin2856let l = rbin_plan d o r a b in2857if changes d l || riv_changes d r (riv_plan d r) ||2858riv_changes d a (riv_plan d a) || riv_changes d b (riv_plan d b)2859then begin2860apply d l;2861dyadic_riv d r; dyadic_riv d a; dyadic_riv d b2862end2863end2864
r = - a: the same domain
Valid (51ms) (colibri2)let dyadic_rneg (d: env) (r a: Atom.t) : unit2867requires { live d -> d.mr r = -. d.mr a }2868= if has_dy d a || has_dy d r then begin2869let da = getdr_r d a in2870upd_real d a da;2871{proof…} if pure { live d } then D.neg_mem (d.mr a) da; {qed}2872upd_real d r da;2873let dr = getdr_r d r in2874{proof…} if pure { live d } then D.neg_mem (d.mr r) dr; {qed}2875upd_real d a dr;2876dyadic_riv d r; dyadic_riv d a2877end2878
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)let dyadic_to_real (d: env) (fm: format) (r a: Atom.t) : unit2882requires { fmt_of a = fm }2883requires { live d -> fmt (d.mf a) = fm /\2884(is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) -> d.mr r = to_real (d.mf a)) }2885= let (umin, umax, psb) = fmt_dy fm in2886let (minf, pinf, _, _) = consts fm in2887let da = getd_f d a umin umax psb minf pinf in2888match get d a with2889| Some va -> if is_finite fm minf pinf va then upd_real d r da2890| None -> ()2891end;2892updd d a (getdr_r d r);2893dyadic_iv d fm a;2894dyadic_riv d r2895
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)let dyadic_rti (d: env) (fm: format) (r m a: Atom.t) : unit2899requires { fmt_of r = fm /\ fmt_of a = fm }2900requires { live d -> holds d (Un URti fm r m a) }2901= let (umin, umax, psb) = fmt_dy fm in2902let v = FD.round_fwd fm umin umax psb (D.mk (Some 0) None None) in2903{proof…}2904let lemma fin () : unit2905requires { live d /\ FD.finite (d.mf r) }2906ensures { D.mem (to_real (d.mf r)) v }2907= let x = d.mf a in2908match ext x with2909| Fin y ->2910let n = round_int (d.mm m) y in2911dv_intro (from_int n) (pow2r 0) n;2912assert { D.mem (from_int n) (D.mk (Some 0) None None) };2913assert { d.mf r = fp_rti (d.mm m) x };2914assert { d.mf r = round_f fm (d.mm m)2915(if is_positive x then false else true) (Fin (from_int n)) }2916| _ -> ()2917end in2918{qed}2919updd d r v;2920dyadic_iv d fm r2921
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)let dyadic_to_real_in (d: env) (fm: format) (r a: Atom.t) (lo hi: int) : unit2926requires { fmt_of a = fm }2927requires { live d -> holds d (ToRealIn fm r a lo hi) }2928= let (umin, umax, psb) = fmt_dy fm in2929let (minf, pinf, _, _) = consts fm in2930let da = getd_f d a umin umax psb minf pinf in2931match get d a with2932| None -> ()2933| Some va ->2934match to_real_fwd fm minf pinf va with2935| Some l -> if in_range lo hi l then begin upd_real d r da; dyadic_riv d r end2936| None -> ()2937end2938end2939
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)let fp_eq_merge (fm: format) (c: (t, t, t, t)) (va vb: dom) : bool2946requires { consts_ok fm c }2947requires { va.fm = fm /\ vb.fm = fm }2948ensures { result -> forall x y. mem x va -> mem y vb -> fp_eq x y -> x = y }2949= let (minf, pinf, nz, pz) = c in2950let p = positives fm pz pinf in2951let n = negatives fm minf nz in2952let z = zeros fm nz pz in2953{proof…}2954let lemma zero_eq (x y: t) : unit2955requires { fmt x = fmt y /\ is_zero x /\ is_zero y /\ is_not_nan x /\ is_not_nan y }2956requires { is_positive x <-> is_positive y }2957ensures { x = y }2958= index_positive x; index_positive y; index_inj x; index_inj y in2959{qed}2960match is_distinct_or_included fm va z, is_distinct_or_included fm vb z with2961| (Disjoint, _) | (_, Disjoint) -> true2962| _ ->2963match is_distinct_or_included fm va p, is_distinct_or_included fm vb p with2964| (Included, Included) -> true2965| _ ->2966match is_distinct_or_included fm va n, is_distinct_or_included fm vb n with2967| (Included, Included) -> true2968| _ -> false2969end2970end2971end2972
x of format fm in va: abs x = x, x positive (colibri's abs_val_real)
Valid (134ms) (cvc5)let abs_id (fm: format) (c: (t, t, t, t)) (va: dom) : bool2976requires { consts_ok fm c }2977requires { va.fm = fm }2978ensures { result -> forall x. mem x va -> abs x = x }2979= let (_, pinf, _, pz) = c in2980{proof…}2981let lemma pos_abs (x: t) : unit2982requires { is_not_nan x /\ is_positive x }2983ensures { abs x = x }2984= index_positive x; index_inj x; index_inj (abs x) in2985{qed}2986match is_distinct_or_included fm va (positives fm pz pinf) with2987| Included -> true2988| _ -> false2989end2990
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)let ghost add_opp (m: mode) (x nz pz: t) : unit2994requires { is_not_nan x /\ not (is_inf x) }2995requires { at_index (fmt x) nz (-1) /\ at_index (fmt x) pz 0 }2996ensures { fp_add m x (neg x) = (if m = RTN then nz else pz) }2997ensures { fp_add m (neg x) x = (if m = RTN then nz else pz) }2998= {proof…}2999index_positive x; index_positive (neg x);3000let r1 = fp_add m x (neg x) in3001let r2 = fp_add m (neg x) x in3002assert { is_zero r1 /\ is_zero r2 /\ fmt r1 = fmt x /\ fmt r2 = fmt x };3003index_positive r1; index_positive r2;3004index_inj r1; index_inj r2; index_inj nz; index_inj pz3005{qed}3006
x of format fm in va: x = - (abs x), x negative (colibri's abs_val_real)
Valid (490ms) (cvc5)let abs_opp (fm: format) (c: (t, t, t, t)) (va: dom) : bool3010requires { consts_ok fm c }3011requires { va.fm = fm }3012ensures { result -> forall x. mem x va -> x = neg (abs x) }3013= let (minf, _, nz, _) = c in3014{proof…}3015let lemma neg_abs (x: t) : unit3016requires { is_not_nan x /\ not is_positive x }3017ensures { x = neg (abs x) }3018= index_positive x; index_inj x; index_inj (neg (abs x)) in3019{qed}3020match is_distinct_or_included fm va (negatives fm minf nz) with3021| Included -> true3022| _ -> false3023end3024
x + (- x) and (- x) + x, x infinite or NaN: NaN
The opposite of a NaN or an infinity
Valid (105ms) (colibri2)let ghost neg_special (x: t) : unit3028ensures { is_nan (neg x) <-> is_nan x }3029ensures { is_inf (neg x) <-> is_inf x }3030= {proof…}3031if pure { is_not_nan x } then begin3032assert { is_plus_infinity (neg x) <-> is_minus_infinity x };3033assert { is_minus_infinity (neg x) <-> is_plus_infinity x }3034end3035{qed}3036
The opposite of a finite float
Valid (57ms) (colibri2)let ghost neg_fin (x: t) : unit3039requires { is_not_nan x /\ not is_inf x }3040ensures { ext (neg x) = Fin (-. to_real x) /\ to_real (neg x) = -. to_real x }3041= {proof…}3042neg_special x;3043assert { ext x = Fin (to_real x) };3044assert { ext (neg x) = eneg (ext x) }3045{qed}3046Valid (113ms) (cvc4)3047let ghost add_opp_nan (m: mode) (x: t) : unit3048requires { is_nan x \/ is_inf x }3049ensures { is_nan (fp_add m x (neg x)) /\ is_nan (fp_add m (neg x) x) }3050= {proof…}3051if pure { is_not_nan x } then begin3052index_positive x; index_positive (neg x);3053assert { opposite (ext x) (ext (neg x)) /\ opposite (ext (neg x)) (ext x) }3054end3055{qed}3056
x - y, fp.eq x y: a zero, or NaN for x infinite (colibri: fp_eq1 then the zeros)
Valid (590ms) (cvc5)let ghost sub_eq (m: mode) (x y: t) : unit3060requires { fp_eq x y }3061ensures { let r = fp_add m x (neg y) in3062fmt r = fmt x /\ (is_zero r \/ (is_inf x /\ is_nan r)) }3063= {proof…}3064if pure { is_not_nan x /\ x = y } then begin3065if pure { is_inf x } then begin3066index_positive x; index_positive (neg x);3067assert { opposite (ext x) (ext (neg x)) }3068end else begin3069index_positive x; index_positive (neg x);3070assert { ext (neg x) = eneg (ext x) };3071assert { eadd (ext x) (ext (neg x)) = Fin 0.0 }3072end3073end else begin3074assert { is_zero x /\ is_zero y /\ fmt x = fmt y };3075assert { ext (neg y) = eneg (ext y) };3076assert { eadd (ext x) (ext (neg y)) = Fin 0.0 }3077end3078{qed}3079
The domain of x - y for fp.eq x y, x in va
Valid (514ms) (cvc5)let sub_eq_dom (fm: format) (c: (t, t, t, t)) (va: option dom) : dom3082requires { consts_ok fm c }3083requires { match va with Some v -> v.fm = fm | None -> true end }3084ensures { result.fm = fm }3085ensures { forall m x y. fmt x = fm -> fp_eq x y ->3086(match va with Some v -> mem x v | None -> true end) ->3087mem (fp_add m x (neg y)) result }3088= let (minf, pinf, nz, pz) = c in3089let z = zeros fm nz pz in3090{proof…}3091let lemma pt (m: mode) (x y: t) : unit3092requires { fmt x = fm /\ fp_eq x y }3093ensures { mem (fp_add m x (neg y)) z \/ is_nan (fp_add m x (neg y)) }3094ensures { fmt (fp_add m x (neg y)) = fm }3095ensures { is_not_nan x /\ not (is_inf x) -> mem (fp_add m x (neg y)) z }3096= sub_eq m x y in3097{qed}3098match va with3099| Some v -> if is_finite fm minf pinf v then z else union fm z (nan_dom fm)3100| None -> union fm z (nan_dom fm)3101end3102
The rules on fp.eq a b true: the terms a - b
Valid (598ms) (colibri2 10) (cvc5) (split_vc) (depth 1)let rec sub_eq_terms (d: env) (fm: format) (a b: Atom.t) (l: list Atom.t) : unit3105requires { fmt_of a = fm }3106requires { live d -> fp_eq (d.mf a) (d.mf b) /\ fmt (d.mf a) = fm }3107requires { forall r. LM.mem r l -> live d ->3108exists md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) }3109variant { l }3110= match l with3111| Nil -> ()3112| Cons r t ->3113let v = sub_eq_dom fm (consts fm) (get d a) in3114{proof…}3115assert { LM.mem r l /\ forall x. LM.mem x t -> LM.mem x l };3116assert { live d -> exists md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) };3117assert { live d -> forall md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) ->3118mem (d.mf r) v };3119assert { live d -> mem (d.mf r) v };3120{qed}3121upd_dom d r v;3122sub_eq_terms d fm a b t3123end3124
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
predicate is_two (fm: format) (x: t) =3133fmt x = fm /\ is_not_nan x /\ ext x = Fin 2.03134
The float 1 of the format fm
predicate is_one (fm: format) (x: t) =3137fmt x = fm /\ is_not_nan x /\ ext x = Fin 1.03138
The rounding of 1 is 1
Valid (153ms) (colibri2)let ghost one_exact (fm: format) (m: mode) : unit3141ensures { is_one fm (round_f fm m false (Fin 1.0)) }3142ensures { is_positive (round_f fm m false (Fin 1.0)) }3143ensures { not is_zero (round_f fm m false (Fin 1.0)) }3144= {proof…}3145max_float_ge fm;3146assert { power 2 (eb fm) = 2 * power 2 (eb fm - 1) };3147assert { power 2 (eb fm - 1) = 2 * power 2 (eb fm - 2) };3148assert { 1 <= power 2 (eb fm - 2) };3149assert { ulp_max fm + sb fm - 1 = emax fm - 1 >= 0 };3150pow2r_le 0 (ulp_max fm + sb fm - 1);3151assert { pow2r 0 = 1.0 };3152assert { power 2 (sb fm) = 2 * power 2 (sb fm - 1) };3153assert { 1 <= power 2 (sb fm - 1) };3154let x = int_exact fm 1 in3155ext_sign x;3156assert { is_positive x };3157assert { round_f fm m (if is_positive x then false else true) (ext x) = x };3158assert { round_f fm m false (Fin 1.0) = x }3159{qed}3160
The float 2
Valid (727ms) (colibri2)let ghost two_exact (fm: format) : unit3163ensures { is_two fm (round_f fm RNE false (Fin (from_int 2))) }3164= {proof…}3165max_float_ge fm;3166assert { power 2 (eb fm) = 2 * power 2 (eb fm - 1) };3167assert { power 2 (eb fm - 1) = 2 * power 2 (eb fm - 2) };3168assert { 1 <= power 2 (eb fm - 2) };3169assert { ulp_max fm + sb fm - 1 = emax fm - 1 >= 1 };3170pow2r_le 1 (ulp_max fm + sb fm - 1);3171assert { pow2r 1 = 2.0 };3172assert { power 2 (sb fm) = 2 * power 2 (sb fm - 1) };3173assert { 2 <= power 2 (sb fm - 1) };3174let x = int_exact fm 2 in3175ext_sign x;3176assert { is_positive x };3177assert { round_f fm RNE (if is_positive x then false else true) (ext x) = x };3178assert { round_f fm RNE false (Fin (from_int 2)) = x }3179{qed}3180
a / b against 1, on the extended reals
Valid (650ms) (colibri2)let ghost ediv_one (a b: ereal) : unit3183requires { b <> Fin 0.0 }3184requires { not ((a = PInf \/ a = MInf) /\ (b = PInf \/ b = MInf)) }3185ensures { (ele a b /\ ele (Fin 0.0) b) \/ (ele b a /\ ele b (Fin 0.0)) ->3186ele (ediv a b) (Fin 1.0) }3187ensures { (ele b a /\ ele (Fin 0.0) b) \/ (ele a b /\ ele b (Fin 0.0)) ->3188ele (Fin 1.0) (ediv a b) }3189= {proof…}3190match a, b with3191| Fin u, Fin v ->3192assert { v <> 0.0 };3193assert { ediv a b = Fin (u *. (1.0 /. v)) };3194assert { u *. (1.0 /. v) -. 1.0 = (u -. v) /. v };3195if pure { v >. 0.0 } then begin3196assert { u <=. v -> (u -. v) /. v <=. 0.0 };3197assert { v <=. u -> (u -. v) /. v >=. 0.0 }3198end else begin3199assert { v <. 0.0 };3200assert { u <=. v -> (u -. v) /. v >=. 0.0 };3201assert { v <=. u -> (u -. v) /. v <=. 0.0 }3202end3203| MInf, Fin v ->3204assert { v <> 0.0 };3205if pure { v >. 0.0 } then assert { 1.0 /. v >. 0.0 }3206else assert { 1.0 /. v <. 0.0 }3207| PInf, Fin v ->3208assert { v <> 0.0 };3209if pure { v >. 0.0 } then assert { 1.0 /. v >. 0.0 }3210else assert { 1.0 /. v <. 0.0 }3211| _ -> ()3212end3213{qed}3214
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)let ghost div_one (m: mode) (x y o: t) : unit3219requires { fmt x = fmt y /\ is_one (fmt x) o /\ is_positive o /\ not is_zero o }3220requires { is_not_nan y /\ not is_zero y }3221ensures { let r = fp_div m x y in3222(fp_le x y /\ is_positive y \/ fp_le y x /\ not is_positive y) ->3223is_nan r \/ le_dz r o }3224ensures { let r = fp_div m x y in3225(fp_le y x /\ is_positive y \/ fp_le x y /\ not is_positive y) ->3226is_nan r \/ le_dz o r }3227= {proof…}3228let fm = fmt x in3229let r = fp_div m x y in3230if is_nan x then ()3231else if pure { is_infinity x /\ is_infinity y } then ()3232else begin3233ext_sign x; ext_sign y; ext_sign o;3234let z = mul_zneg x y in3235let e = ediv (ext x) (ext y) in3236assert { r = round_f fm m z e };3237assert { round_f fm m (if is_positive o then false else true) (ext o) = o };3238assert { round_f fm m false (ext o) = o };3239assert { fp_le x y -> ele (ext x) (ext y) };3240assert { fp_le y x -> ele (ext y) (ext x) };3241assert { not ((ext x = PInf \/ ext x = MInf) /\ (ext y = PInf \/ ext y = MInf)) };3242ediv_one (ext x) (ext y);3243if pure { ele e (ext o) } then3244assert { le_dz (round_f fm m z e) (round_f fm m false (ext o)) };3245if pure { ele (ext o) e } then3246assert { le_dz (round_f fm m false (ext o)) (round_f fm m z e) }3247end3248{qed}3249
2 x is a float when it is in the range of the format
Valid (200ms) (colibri2 12) (cvc5) (split_vc 2) (depth 2)let ghost double_exact (m: mode) (z: bool) (x: t) : unit3252requires { is_not_nan x /\ not is_infinity x }3253requires { -. to_real (of_index (fmt x) (nb_sign (fmt x) - 2)) <=. 2.0 *. to_real x3254<=. to_real (of_index (fmt x) (nb_sign (fmt x) - 2)) }3255ensures { ext (round_f (fmt x) m z (Fin (2.0 *. to_real x))) = Fin (2.0 *. to_real x) }3256= {proof…}3257let fm = fmt x in3258let v = to_real x in3259float_dyadic x;3260D.fix_add v v (ulp_min fm);3261assert { v +. v = 2.0 *. v };3262assert { pow2r 1 = 2.0 };3263assert { D.flt 2.0 1 by 2.0 = from_int 1 *. pow2r 1 /\ - power 2 1 < 1 < power 2 1 };3264D.flt_mul_pow2 2.0 v (sb fm);3265let w = dyadic_exact fm (2.0 *. v) in3266let zw = if is_positive w then false else true in3267assert { round_f fm m zw (ext w) = w };3268round_f_val fm m z zw (Fin (2.0 *. v))3269{qed}3270
The largest finite float and its opposite
Valid (1.4s) (colibri2)let ghost max_facts (fm: format) : unit3273ensures { let mx = of_index fm (nb_sign fm - 2) in3274is_not_nan mx /\ fmt mx = fm /\ not is_infinity mx /\3275ext mx = Fin (to_real mx) /\3276let nmx = of_index fm (1 - nb_sign fm) in3277is_not_nan nmx /\ fmt nmx = fm /\ ext nmx = Fin (-. to_real mx) /\3278(forall v. fmt v = fm -> is_not_nan v -> not is_infinity v ->3279le_dz nmx v /\ le_dz v mx) }3280= {proof…}3281let ghost n = nb_sign fm in3282assert { 3 <= n by power 2 (eb fm) >= 2 /\ power 2 (sb fm - 1) >= 1 };3283of_index_range fm (n - 2); of_index_range fm (1 - n);3284let mx = of_index fm (n - 2) in3285let nmx = of_index fm (1 - n) in3286assert { index (neg mx) = 1 - n };3287index_inj (neg mx);3288assert { nmx = neg mx };3289assert { ext nmx = eneg (ext mx) };3290let lemma pt (v: t) : unit3291requires { fmt v = fm /\ is_not_nan v /\ not is_infinity v }3292ensures { le_dz nmx v /\ le_dz v mx }3293= index_range v in3294()3295{qed}3296
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)let ghost twice_lo (lo: t) : unit3300requires { is_not_nan lo /\ not is_infinity lo }3301requires { not is_minus_infinity (fp_add rtn lo lo) }3302ensures { -. to_real (of_index (fmt lo) (nb_sign (fmt lo) - 2)) <=. 2.0 *. to_real lo }3303= {proof…}3304let fm = fmt lo in3305max_facts fm;3306let r = fp_add rtn lo lo in3307assert { not opposite (ext lo) (ext lo) };3308assert { r = round_f fm rtn (add_zneg rtn lo lo) (Fin (to_real lo +. to_real lo)) };3309assert { ele (ext r) (Fin (to_real lo +. to_real lo)) };3310assert { is_not_nan r /\ fmt r = fm };3311assert { not is_plus_infinity r };3312assert { le_dz (of_index fm (1 - nb_sign fm)) r };3313assert { ele (ext (of_index fm (1 - nb_sign fm))) (ext r) }3314{qed}3315Valid (84ms) (colibri2)3316let ghost twice_hi (hi: t) : unit3317requires { is_not_nan hi /\ not is_infinity hi }3318requires { not is_plus_infinity (fp_add rtp hi hi) }3319ensures { 2.0 *. to_real hi <=. to_real (of_index (fmt hi) (nb_sign (fmt hi) - 2)) }3320= {proof…}3321let fm = fmt hi in3322max_facts fm;3323let r = fp_add rtp hi hi in3324assert { not opposite (ext hi) (ext hi) };3325assert { r = round_f fm rtp (add_zneg rtp hi hi) (Fin (to_real hi +. to_real hi)) };3326assert { ele (Fin (to_real hi +. to_real hi)) (ext r) };3327assert { is_not_nan r /\ fmt r = fm };3328assert { not is_minus_infinity r };3329assert { le_dz r (of_index fm (nb_sign fm - 2)) };3330assert { ele (ext r) (ext (of_index fm (nb_sign fm - 2))) }3331{qed}3332
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)let ghost avg (m1 m2: mode) (x y c lo hi: t) : unit3338requires { fmt y = fmt x /\ fmt lo = fmt x /\ fmt hi = fmt x /\ is_two (fmt x) c }3339requires { fp_le x y /\ le_dz lo x /\ le_dz y hi }3340requires { not is_minus_infinity (fp_add rtn lo lo) }3341requires { not is_plus_infinity (fp_add rtp hi hi) }3342ensures { let h = fp_div m2 (fp_add m1 x y) c in fp_le x h /\ fp_le h y }3343= {proof…}3344let fm = fmt x in3345add_special rtn lo lo; add_special rtp hi hi;3346assert { is_not_nan x /\ is_not_nan y /\ is_not_nan lo /\ is_not_nan hi };3347ext_sign x; ext_sign y;3348assert { ele (ext lo) (ext x) /\ ele (ext y) (ext hi) };3349assert { ele (ext x) (ext y) };3350assert { not is_minus_infinity lo /\ not is_plus_infinity hi };3351assert { ext hi <> PInf /\ ext lo <> MInf };3352assert { ext lo <> PInf /\ ext hi <> MInf };3353assert { not is_infinity lo /\ not is_infinity hi };3354assert { not is_infinity x /\ not is_infinity y };3355let vx = to_real x in3356let vy = to_real y in3357assert { ext x = Fin vx /\ ext y = Fin vy };3358assert { to_real lo <=. vx <=. vy <=. to_real hi };3359twice_lo lo; twice_hi hi;3360let zs = add_zneg m1 x y in3361double_exact m1 zs x; double_exact m1 zs y;3362let s = fp_add m1 x y in3363assert { s = round_f fm m1 zs (Fin (vx +. vy)) };3364round_f_ele fm m1 zs zs (Fin (2.0 *. vx)) (Fin (vx +. vy));3365round_f_ele fm m1 zs zs (Fin (vx +. vy)) (Fin (2.0 *. vy));3366assert { ele (Fin (2.0 *. vx)) (ext s) /\ ele (ext s) (Fin (2.0 *. vy)) };3367assert { is_not_nan s /\ fmt s = fm };3368assert { not is_infinity s };3369let vs = to_real s in3370assert { ext s = Fin vs /\ 2.0 *. vx <=. vs <=. 2.0 *. vy };3371ext_sign c;3372assert { not is_zero c /\ not is_infinity c /\ ext c = Fin 2.0 };3373let zh = mul_zneg s c in3374let e = ediv (ext s) (ext c) in3375assert { e = Fin (vs *. (1.0 /. 2.0)) };3376assert { vx <=. vs *. (1.0 /. 2.0) <=. vy };3377let h = fp_div m2 s c in3378assert { h = round_f fm m2 zh e };3379let zx = if is_positive x then false else true in3380let zy = if is_positive y then false else true in3381assert { round_f fm m2 zx (ext x) = x };3382assert { round_f fm m2 zy (ext y) = y };3383round_f_ele fm m2 zx zh (ext x) e;3384round_f_ele fm m2 zh zy e (ext y);3385assert { is_not_nan h /\ fmt h = fm };3386assert { ele (ext x) (ext h) /\ ele (ext h) (ext y) };3387if pure { is_zero x /\ is_zero h } then () else ele_le x h;3388if pure { is_zero h /\ is_zero y } then () else ele_le h y3389{qed}3390
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)let ghost avg_half (m2: mode) (x y c s: t) : unit3394requires { fmt y = fmt x /\ fmt s = fmt x /\ is_two (fmt x) c }3395requires { is_not_nan x /\ is_not_nan y /\ is_not_nan s /\ not is_infinity s }3396requires { not is_infinity x /\ not is_infinity y }3397requires { 2.0 *. to_real x <=. to_real s <=. 2.0 *. to_real y }3398ensures { let h = fp_div m2 s c in fp_le x h /\ fp_le h y }3399= {proof…}3400let fm = fmt x in3401ext_sign x; ext_sign y; ext_sign s; ext_sign c;3402let vx = to_real x in3403let vy = to_real y in3404let vs = to_real s in3405assert { ext x = Fin vx /\ ext y = Fin vy /\ ext s = Fin vs };3406assert { not is_zero c /\ not is_infinity c /\ ext c = Fin 2.0 };3407let zh = mul_zneg s c in3408let e = ediv (ext s) (ext c) in3409assert { e = Fin (vs *. (1.0 /. 2.0)) };3410assert { vx <=. vs *. (1.0 /. 2.0) <=. vy };3411let h = fp_div m2 s c in3412assert { h = round_f fm m2 zh e };3413let zx = if is_positive x then false else true in3414let zy = if is_positive y then false else true in3415assert { round_f fm m2 zx (ext x) = x };3416assert { round_f fm m2 zy (ext y) = y };3417round_f_ele fm m2 zx zh (ext x) e;3418round_f_ele fm m2 zh zy e (ext y);3419assert { is_not_nan h /\ fmt h = fm };3420assert { ele (ext x) (ext h) /\ ele (ext h) (ext y) };3421if pure { is_zero x /\ is_zero h } then () else ele_le x h;3422if pure { is_zero h /\ is_zero y } then () else ele_le h y3423{qed}3424
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)let ghost avg_near (m1 m2: mode) (x y c: t) : unit3430requires { m1 = RNE \/ m1 = RNA }3431requires { fmt y = fmt x /\ is_two (fmt x) c /\ fp_le x y }3432requires { is_not_nan (fp_add m1 x y) /\ not is_infinity (fp_add m1 x y) }3433ensures { let h = fp_div m2 (fp_add m1 x y) c in fp_le x h /\ fp_le h y }3434= {proof…}3435let fm = fmt x in3436max_facts fm;3437add_special m1 x y;3438assert { is_not_nan x /\ is_not_nan y };3439ext_sign x; ext_sign y;3440assert { ele (ext x) (ext y) };3441assert { not is_infinity x /\ not is_infinity y };3442let vx = to_real x in3443let vy = to_real y in3444assert { ext x = Fin vx /\ ext y = Fin vy /\ vx <=. vy };3445let mx = to_real (of_index fm (nb_sign fm - 2)) in3446let zs = add_zneg m1 x y in3447let s = fp_add m1 x y in3448assert { not opposite (ext x) (ext y) };3449assert { s = round_f fm m1 zs (Fin (vx +. vy)) };3450assert { fmt s = fm };3451let vs = to_real s in3452assert { ext s = Fin vs };3453assert { -. mx <=. vs <=. mx by le_dz (of_index fm (1 - nb_sign fm)) s /\ le_dz s (of_index fm (nb_sign fm - 2)) };3454near_double m1 zs x (vx +. vy);3455near_double m1 zs y (vx +. vy);3456if pure { -. mx <=. 2.0 *. vx } then begin3457double_exact m1 zs x;3458round_f_ele fm m1 zs zs (Fin (2.0 *. vx)) (Fin (vx +. vy))3459end;3460assert { 2.0 *. vx <=. vs };3461if pure { 2.0 *. vy <=. mx } then begin3462double_exact m1 zs y;3463round_f_ele fm m1 zs zs (Fin (vx +. vy)) (Fin (2.0 *. vy))3464end;3465assert { vs <=. 2.0 *. vy };3466avg_half m2 x y c s3467{qed}3468
The node c is the float 2: its domain is the singleton 2
Valid (585ms) (cvc5)let is_two_node (d: envp 'm) (fm: format) (c: Atom.t) : bool3471requires { fmt_of c = fm }3472ensures { result -> live d -> is_two fm (d.mf c) }3473= match get d c with3474| None -> false3475| Some vc ->3476let (minf, pinf, _, _) = consts fm in3477if is_finite fm minf pinf vc then3478match is_singleton fm vc with3479| Sin v -> a_eq (to_a v) (a_of_int 2)3480| _ -> false3481end3482else false3483end3484
The domain of n has no NaN
Valid (35ms) (colibri2)let not_nan_dom (d: envp 'm) (n: Atom.t) : bool3487ensures { result -> live d -> is_not_nan (d.mf n) }3488= match get d n with Some v -> not v.nan | None -> false end3489
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)let ghost zi_facts (x y: t) : unit3495requires { is_not_nan x /\ is_not_nan y /\ fmt x = fmt y }3496ensures { fp_le x y <-> zi x <= zi y }3497ensures { fp_lt x y <-> zi x < zi y }3498ensures { fp_eq x y <-> zi x = zi y }3499= {proof…}3500assert { is_zero x <-> (index x = 0 \/ index x = -1) };3501assert { is_zero y <-> (index y = 0 \/ index y = -1) };3502assert { index x = index y -> x = y3503by of_index (fmt x) (index x) = x /\ of_index (fmt y) (index y) = y }3504{qed}3505
x <= y, x < y, y <= x, y < x, x == y
let constant z_le : Zi.t = Zi.mk (Some 0) None3508let constant z_lt : Zi.t = Zi.mk (Some 1) None3509let constant z_ge : Zi.t = Zi.mk None (Some 0)3510let constant z_gt : Zi.t = Zi.mk None (Some (-1))3511let constant z_eq : Zi.t = Zi.mk (Some 0) (Some 0)3512
The relation of x and y when the comparison o of x and y is t
Valid (105ms) (colibri2)let cmp_rel (o: cop) (t: bool) (ghost x y: t) : Zi.t3516ensures { fmt x = fmt y -> (fcmp o x y <-> t) -> relh result x y }3517= {proof…}3518if pure { is_not_nan x /\ is_not_nan y /\ fmt x = fmt y } then zi_facts x y;3519{qed}3520match o, t with3521| CLe, True -> z_le3522| CLe, False -> z_gt3523| CLt, True -> z_lt3524| CLt, False -> z_ge3525| CEq, True -> z_eq3526| CEq, False -> Zi.top3527end3528
The database says a <= b and the domains exclude NaN
Valid (114ms) (colibri2)let rel_le (d: envp 'm) (fm: format) (a b: Atom.t) : bool3531ensures { result -> live d -> fmt (d.mf a) = fmt (d.mf b) -> fp_le (d.mf a) (d.mf b) }3532= let i = getrel d fm a b in3533let res = not_nan_dom d a && not_nan_dom d b && Zi.incl i z_le in3534{proof…}3535Zi.incl_spec i z_le;3536if pure { res /\ live d /\ fmt (d.mf a) = fmt (d.mf b) } then begin3537zi_facts (d.mf a) (d.mf b);3538assert { Zi.mem (zi (d.mf b) - zi (d.mf a)) z_le }3539end;3540{qed}3541res3542
The database says a < b and the domains exclude NaN
Valid (101ms) (colibri2)let rel_lt (d: envp 'm) (fm: format) (a b: Atom.t) : bool3545ensures { result -> live d -> fmt (d.mf a) = fmt (d.mf b) -> fp_lt (d.mf a) (d.mf b) }3546= let i = getrel d fm a b in3547let res = not_nan_dom d a && not_nan_dom d b && Zi.incl i z_lt in3548{proof…}3549Zi.incl_spec i z_lt;3550if pure { res /\ live d /\ fmt (d.mf a) = fmt (d.mf b) } then begin3551zi_facts (d.mf a) (d.mf b);3552assert { Zi.mem (zi (d.mf b) - zi (d.mf a)) z_lt }3553end;3554{qed}3555res3556
The database says that a < b or b < a is known
Valid (33ms) (colibri2)let rel_strict (d: envp 'm) (fm: format) (a b: Atom.t) : bool3559= let i = getrel d fm a b in3560Zi.incl i z_lt || Zi.incl i z_gt3561
The depth of the closure of the relations (colibri: delta_path, 4)
let constant rel_depth : int = 23564
An empty relation between two nodes that are not NaN
Valid (68ms) (colibri2)let rel_conflict (d: env) (x y: Atom.t) (n: Zi.t) : unit3567requires { live d -> relh n (d.mf x) (d.mf y) }3568= if Zi.is_empty n && not_nan_dom d x && not_nan_dom d y then begin3569{proof…} Zi.is_empty_spec n; {qed}3570contradiction d3571end3572
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)let rec write_rel (d: env) (fm: format) (x y: Atom.t) (i: Zi.t) (depth: int) : unit3578requires { live d -> relh i (d.mf x) (d.mf y) }3579variant { depth }3580= match updrel d fm x y i with3581| None -> ()3582| Some n ->3583rel_conflict d x y n;3584if 0 < depth then begin3585(* `x -> y -> z` *)3586let rec via_y (l: list (Atom.t, Zi.t)) : unit3587requires { forall z j. LM.mem (z, j) l -> live d -> relh j (d.mf y) (d.mf z) }3588requires { live d -> relh n (d.mf x) (d.mf y) /\ is_not_nan (d.mf y) }3589variant { l }3590= match l with3591| Nil -> ()3592| Cons (z, j) t ->3593{proof…}3594assert { LM.mem (z, j) l /\ forall w. LM.mem w t -> LM.mem w l };3595if pure { live d /\ is_not_nan (d.mf x) /\ is_not_nan (d.mf z) } then3596Zi.mem_add (zi (d.mf y) - zi (d.mf x)) (zi (d.mf z) - zi (d.mf y)) n j;3597{qed}3598if not (is_equal d z x) then write_rel d fm x z (Zi.add n j) (depth - 1);3599via_y t3600end in3601(* `z -> x -> y` *)3602let rec via_x (l: list (Atom.t, Zi.t)) : unit3603requires { forall z j. LM.mem (z, j) l -> live d -> relh j (d.mf x) (d.mf z) }3604requires { live d -> relh n (d.mf x) (d.mf y) /\ is_not_nan (d.mf x) }3605variant { l }3606= match l with3607| Nil -> ()3608| Cons (z, j) t ->3609{proof…}3610assert { LM.mem (z, j) l /\ forall w. LM.mem w t -> LM.mem w l };3611if pure { live d /\ is_not_nan (d.mf y) /\ is_not_nan (d.mf z) } then begin3612Zi.mem_rev (zi (d.mf z) - zi (d.mf x)) j;3613Zi.mem_add (zi (d.mf x) - zi (d.mf z)) (zi (d.mf y) - zi (d.mf x)) (Zi.rev j) n3614end;3615{qed}3616if not (is_equal d z y) then write_rel d fm z y (Zi.add (Zi.rev j) n) (depth - 1);3617via_x t3618end in3619if not_nan_dom d y then via_y (RD.entries d y);3620if not_nan_dom d x then via_x (RD.entries d x)3621end3622end3623
An empty relation of a and b: one of them is NaN
Valid (100ms) (colibri2)let rel_check (d: env) (fm: format) (a b: Atom.t) : unit3626requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm }3627= let i = getrel d fm a b in3628if Zi.is_empty i then begin3629{proof…}3630Zi.is_empty_spec i;3631assert { live d -> is_nan (d.mf a) \/ is_nan (d.mf b) };3632{qed}3633if not_nan_dom d a then upd_dom d b (nan_dom fm)3634else if not_nan_dom d b then upd_dom d a (nan_dom fm)3635end3636
a <= b in the database
Valid (43ms) (colibri2)let set_le (d: env) (fm: format) (a b: Atom.t) : unit3639requires { fmt_of a = fm /\ fmt_of b = fm }3640requires { live d -> fmt (d.mf a) = fm /\ fp_le (d.mf a) (d.mf b) }3641= {proof…}3642if pure { live d } then begin3643assert { is_not_nan (d.mf a) /\ is_not_nan (d.mf b) /\ fmt (d.mf a) = fmt (d.mf b) };3644zi_facts (d.mf a) (d.mf b)3645end;3646{qed}3647write_rel d fm a b z_le rel_depth;3648rel_check d fm a b3649
a < b in the database
Valid (28ms) (colibri2)let set_lt (d: env) (fm: format) (a b: Atom.t) : unit3652requires { fmt_of a = fm /\ fmt_of b = fm }3653requires { live d -> fmt (d.mf a) = fm /\ fp_lt (d.mf a) (d.mf b) }3654= {proof…}3655if pure { live d } then begin3656assert { is_not_nan (d.mf a) /\ is_not_nan (d.mf b) /\ fmt (d.mf a) = fmt (d.mf b) };3657zi_facts (d.mf a) (d.mf b)3658end;3659{qed}3660write_rel d fm a b z_lt rel_depth;3661rel_check d fm a b3662
a == b in the database
Valid (50ms) (colibri2)let set_eq (d: env) (fm: format) (a b: Atom.t) : unit3665requires { fmt_of a = fm /\ fmt_of b = fm }3666requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\ fp_eq (d.mf a) (d.mf b) }3667= {proof…}3668if pure { live d /\ is_not_nan (d.mf a) /\ is_not_nan (d.mf b) } then zi_facts (d.mf a) (d.mf b);3669{qed}3670write_rel d fm a b z_eq rel_depth;3671rel_check d fm a b3672
The database says a == b and the domains exclude NaN
Valid (489ms) (cvc5)let rel_eq (d: envp 'm) (fm: format) (a b: Atom.t) : bool3675ensures { result -> live d -> fmt (d.mf a) = fmt (d.mf b) -> fp_eq (d.mf a) (d.mf b) }3676= let i = getrel d fm a b in3677let res = not_nan_dom d a && not_nan_dom d b && Zi.incl i z_eq in3678{proof…}3679Zi.incl_spec i z_eq;3680if pure { res /\ live d /\ fmt (d.mf a) = fmt (d.mf b) } then begin3681zi_facts (d.mf a) (d.mf b);3682assert { Zi.mem (zi (d.mf b) - zi (d.mf a)) z_eq }3683end;3684{qed}3685res3686
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)let cmp_of_rel (d: env) (o: cop) (fm: format) (r a b: Atom.t) : unit3691requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\3692(d.mb r <-> fcmp o (d.mf a) (d.mf b)) }3693= let i = getrel d fm a b in3694let nn = not_nan_dom d a && not_nan_dom d b in3695{proof…}3696Zi.incl_spec i z_le; Zi.incl_spec i z_lt; Zi.incl_spec i z_ge;3697Zi.incl_spec i z_gt; Zi.incl_spec i z_eq;3698if pure { live d } then begin3699if pure { is_not_nan (d.mf a) /\ is_not_nan (d.mf b) } then zi_facts (d.mf a) (d.mf b)3700else assert { not fp_le (d.mf a) (d.mf b) /\ not fp_lt (d.mf a) (d.mf b) /\3701not fp_eq (d.mf a) (d.mf b) }3702end;3703{qed}3704match o with3705| CLe ->3706if nn && Zi.incl i z_le then setb d r true3707else if Zi.incl i z_gt then setb d r false3708| CLt ->3709if nn && Zi.incl i z_lt then setb d r true3710else if Zi.incl i z_ge then setb d r false3711| CEq ->3712if nn && Zi.incl i z_eq then setb d r true3713else if Zi.incl i z_lt || Zi.incl i z_gt then setb d r false3714end3715
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)let rel_div (d: env) (fm: format) (r a b: Atom.t) : unit3720requires { fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm }3721requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\3722exists md. d.mf r = fp_div md (d.mf a) (d.mf b) }3723= match get d b with3724| None -> ()3725| Some vb ->3726let (minf, pinf, nz, pz) = consts fm in3727let o = round_a fm RNE (a_of_int 1) in3728{proof…}3729one_exact fm RNE;3730assert { o = round_f fm RNE false (Fin 1.0) };3731{qed}3732let nonzero = match is_distinct_or_included fm vb (zeros fm nz pz) with3733| Disjoint -> true | _ -> false end in3734let posb = nonzero &&3735match is_distinct_or_included fm vb (positives fm pz pinf) with3736| Included -> true | _ -> false end in3737let negb = nonzero &&3738match is_distinct_or_included fm vb (negatives fm minf nz) with3739| Included -> true | _ -> false end in3740if posb || negb then begin3741let le_ab = rel_le d fm a b in3742let le_ba = rel_le d fm b a in3743let below = union fm (interval fm minf o) (nan_dom fm) in3744let above = union fm (interval fm o pinf) (nan_dom fm) in3745{proof…}3746if pure { live d } then begin3747let ghost md = any mode ensures { d.mf r = fp_div result (d.mf a) (d.mf b) } in3748div_one md (d.mf a) (d.mf b) o;3749assert { is_not_nan (d.mf b) /\ not is_zero (d.mf b) };3750assert { posb -> is_positive (d.mf b) };3751assert { negb -> not is_positive (d.mf b) };3752assert { fmt (d.mf r) = fm };3753if pure { is_not_nan (d.mf r) } then begin3754minf_le fm (d.mf r); le_pinf fm (d.mf r)3755end;3756assert { is_not_nan (d.mf r) -> le_dz minf (d.mf r) /\ le_dz (d.mf r) pinf };3757assert { is_not_nan (d.mf r) -> is_not_nan (d.mf a) };3758total_any (d.mf a) (d.mf b);3759total_any (d.mf b) (d.mf a);3760assert { is_not_nan (d.mf r) -> not le_dz (d.mf r) o ->3761(posb -> fp_lt (d.mf b) (d.mf a)) /\ (negb -> fp_lt (d.mf a) (d.mf b)) };3762assert { is_not_nan (d.mf r) -> not le_dz o (d.mf r) ->3763(posb -> fp_lt (d.mf a) (d.mf b)) /\ (negb -> fp_lt (d.mf b) (d.mf a)) }3764end;3765{qed}3766if (posb && le_ab) || (negb && le_ba) then upd_dom d r below;3767if (posb && le_ba) || (negb && le_ab) then upd_dom d r above;3768match get d r with3769| None -> ()3770| Some vr ->3771match is_distinct_or_included fm vr below with3772| Disjoint ->3773{proof…}3774assert { live d -> not mem (d.mf r) below };3775assert { live d -> is_not_nan (d.mf r) /\ not le_dz (d.mf r) o };3776{qed}3777if posb then set_lt d fm b a else set_lt d fm a b3778| _ -> ()3779end;3780match is_distinct_or_included fm vr above with3781| Disjoint ->3782{proof…}3783assert { live d -> not mem (d.mf r) above };3784assert { live d -> is_not_nan (d.mf r) /\ not le_dz o (d.mf r) };3785{qed}3786if posb then set_lt d fm a b else set_lt d fm b a3787| _ -> ()3788end3789end3790end3791end3792
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)let div_useful (d: envp 'm) (fm: format) (r a b: Atom.t) : bool3796requires { fmt_of r = fm /\ fmt_of b = fm }3797= match get d b, get d r with3798| Some vb, Some vr ->3799let (minf, pinf, nz, pz) = consts fm in3800let o = round_a fm RNE (a_of_int 1) in3801{proof…}3802one_exact fm RNE;3803assert { o = round_f fm RNE false (Fin 1.0) };3804{qed}3805let nonzero = match is_distinct_or_included fm vb (zeros fm nz pz) with3806| Disjoint -> true | _ -> false end in3807let posb = nonzero &&3808match is_distinct_or_included fm vb (positives fm pz pinf) with3809| Included -> true | _ -> false end in3810let negb = nonzero &&3811match is_distinct_or_included fm vb (negatives fm minf nz) with3812| Included -> true | _ -> false end in3813if posb || negb then begin3814let le_ab = rel_le d fm a b in3815let le_ba = rel_le d fm b a in3816let below = union fm (interval fm minf o) (nan_dom fm) in3817let above = union fm (interval fm o pinf) (nan_dom fm) in3818let cb = is_distinct_or_included fm vr below in3819let ca = is_distinct_or_included fm vr above in3820let nb = (posb && le_ab) || (negb && le_ba) in3821let na = (posb && le_ba) || (negb && le_ab) in3822(nb && match cb with Included -> false | _ -> true end) ||3823(na && match ca with Included -> false | _ -> true end) ||3824(not le_ab && not le_ba &&3825(match cb, ca with (Disjoint, _) | (_, Disjoint) -> true | _ -> false end) &&3826not (rel_strict d fm a b))3827end else false3828| _ -> false3829end3830
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)let rec avg_useful (d: envp 'm) (fm: format) (a b: Atom.t) (l: list (Atom.t, Atom.t)) : bool3834variant { l }3835= match l with3836| Nil -> false3837| Cons (h, _) t ->3838let ab = rel_le d fm a b in3839let ba = rel_le d fm b a in3840(ab && not (rel_le d fm a h && rel_le d fm h b)) ||3841(ba && not (rel_le d fm b h && rel_le d fm h a)) ||3842avg_useful d fm a b t3843end3844
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)let avg_pair (d: env) (fm: format) (r m x y h c: Atom.t) : unit3850requires { fmt_of x = fm /\ fmt_of y = fm /\ fmt_of r = fm /\ fmt_of h = fm }3851requires { live d -> fmt (d.mf x) = fm /\ fmt (d.mf y) = fm /\ is_two fm (d.mf c) /\3852d.mf r = fp_add (d.mm m) (d.mf x) (d.mf y) /\3853(exists md. d.mf h = fp_div md (d.mf r) (d.mf c)) }3854= if rel_le d fm x y then begin3855let (minf, pinf, _, _) = consts fm in3856let near = match mode d m with Some RNE | Some RNA -> true | _ -> false end in3857let fin = match get d r with3858| Some vr -> match to_real_fwd fm minf pinf vr with Some _ -> true | None -> false end3859| None -> false end in3860if near && fin then begin3861{proof…}3862if pure { live d } then begin3863let ghost m2 = any mode ensures { d.mf h = fp_div result (d.mf r) (d.mf c) } in3864assert { is_not_nan (d.mf r) /\ not is_infinity (d.mf r) };3865avg_near (d.mm m) m2 (d.mf x) (d.mf y) (d.mf c)3866end;3867{qed}3868set_le d fm x h;3869set_le d fm h y3870end else3871match get d x, get d y with3872| Some vx, Some vy ->3873match vx.u, vy.u with3874| Cons _ _, Cons _ _ ->3875let lo = first fm vx in3876let hi = last fm vy in3877let (minf, pinf, _, _) = consts fm in3878let l2 = add rtn lo lo in3879let h2 = add rtp hi hi in3880if not (le_diff_zero l2 minf) && not (le_diff_zero pinf h2) then begin3881{proof…}3882if pure { live d } then begin3883let ghost m1 = any mode ensures { d.mf r = fp_add result (d.mf x) (d.mf y) } in3884let ghost m2 = any mode ensures { d.mf h = fp_div result (d.mf r) (d.mf c) } in3885le_refl_any l2; le_refl_any h2;3886assert { is_not_nan (d.mf x) /\ is_not_nan (d.mf y) };3887assert { mem_u (d.mf x) vx.u /\ mem_u (d.mf y) vy.u };3888avg m1 m2 (d.mf x) (d.mf y) (d.mf c) lo hi3889end;3890{qed}3891set_le d fm x h;3892set_le d fm h y3893end3894| _ -> ()3895end3896| _ -> ()3897end3898end3899
r = a + b: the averages r / 2 of the list l (Env.divs)
Valid (414ms) (colibri2 13) (cvc5 2) (split_vc) (depth 1)let rec rel_avg (d: env) (fm: format) (r m a b: Atom.t) (l: list (Atom.t, Atom.t)) : unit3902requires { fmt_of r = fm /\ fmt_of a = fm /\ fmt_of b = fm }3903requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf b) = fm /\3904d.mf r = fp_add (d.mm m) (d.mf a) (d.mf b) }3905requires { forall h c. LM.mem (h, c) l -> fmt_of c = fmt_of r /\ fmt_of h = fmt_of r /\3906(live d -> exists md. d.mf h = fp_div md (d.mf r) (d.mf c)) }3907variant { l }3908= match l with3909| Nil -> ()3910| Cons (h, c) t ->3911{proof…}3912assert { LM.mem (h, c) l /\ forall x. LM.mem x t -> LM.mem x l };3913if pure { live d } then add_comm (d.mm m) (d.mf a) (d.mf b);3914{qed}3915if is_two_node d fm c then begin3916avg_pair d fm r m a b h c;3917avg_pair d fm r m b a h c3918end;3919rel_avg d fm r m a b t3920end3921
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.
let function bk (o: bop) : int = match o with OAdd -> 0 | OMul -> 1 | ODiv -> 2 end39303931predicate mono_ok (k: int) (a: t) =39320 <= k <= 2 /\ (k = 0 \/ (is_not_nan a /\ (k = 1 \/ not is_zero a)))3933
Increasing in y (else decreasing)
predicate incr (k: int) (a: t) = k = 0 \/ is_positive a3936
Two floats in the order of their values
Valid (30ms) (colibri2)let ghost fp_le_ext (x y: t) : unit3939requires { fmt x = fmt y /\ is_not_nan x /\ is_not_nan y /\ ele (ext x) (ext y) }3940ensures { fp_le x y }3941= {proof…} if pure { is_zero x /\ is_zero y } then () else ele_le x y {qed}3942
The product by c is monotonic, by the sign of c
Valid (629ms) (colibri2)let ghost emul_mono (c u v: ereal) : unit3945requires { ele u v }3946ensures { ele (Fin 0.0) c -> ele (emul c u) (emul c v) /\ ele (emul u c) (emul v c) }3947ensures { ele c (Fin 0.0) -> ele (emul c v) (emul c u) /\ ele (emul v c) (emul u c) }3948= {proof…}3949match c, u, v with3950| Fin z, Fin p, Fin q ->3951assert { z *. q -. z *. p = z *. (q -. p) };3952assert { p *. z = z *. p /\ q *. z = z *. q };3953if pure { z >=. 0.0 } then assert { z *. (q -. p) >=. 0.0 }3954else assert { z *. (q -. p) <=. 0.0 }3955| _ -> ()3956end3957{qed}3958
mop k md a y is not NaN: neither a nor y is NaN
Valid (492ms) (cvc5)let ghost mop_nan (k: int) (md: mode) (a y: t) : unit3961requires { 0 <= k <= 2 }3962ensures { is_not_nan (mop k md a y) -> is_not_nan a /\ is_not_nan y }3963= ()3964
The monotonicity
Valid (665ms) (colibri2 26) (cvc4) (cvc5 4) (split_vc) (depth 1)let ghost mono (k: int) (md: mode) (a x y: t) : unit3967requires { fmt x = fmt a /\ fmt y = fmt a /\ mono_ok k a }3968requires { fp_le x y }3969requires { is_not_nan (mop k md a x) /\ is_not_nan (mop k md a y) }3970ensures { incr k a -> fp_le (mop k md a x) (mop k md a y) }3971ensures { not incr k a -> fp_le (mop k md a y) (mop k md a x) }3972= {proof…}3973let fm = fmt a in3974let r1 = mop k md a x in3975let r2 = mop k md a y in3976mop_nan k md a x; mop_nan k md a y;3977ext_sign x; ext_sign y; ext_sign a;3978assert { ele (ext x) (ext y) };3979if k = 0 then begin3980assert { not opposite (ext a) (ext x) /\ not opposite (ext a) (ext y) };3981eadd_le2 (ext a) (ext a) (ext x) (ext y);3982assert { r1 = round_f fm md (add_zneg md a x) (eadd (ext a) (ext x)) };3983assert { r2 = round_f fm md (add_zneg md a y) (eadd (ext a) (ext y)) };3984round_f_ele fm md (add_zneg md a x) (add_zneg md a y) (eadd (ext a) (ext x)) (eadd (ext a) (ext y));3985fp_le_ext r1 r23986end else if k = 1 then begin3987emul_mono (ext a) (ext x) (ext y);3988assert { r1 = round_f fm md (mul_zneg a x) (emul (ext a) (ext x)) };3989assert { r2 = round_f fm md (mul_zneg a y) (emul (ext a) (ext y)) };3990if is_positive a then begin3991round_f_ele fm md (mul_zneg a x) (mul_zneg a y) (emul (ext a) (ext x)) (emul (ext a) (ext y));3992fp_le_ext r1 r23993end else begin3994round_f_ele fm md (mul_zneg a y) (mul_zneg a x) (emul (ext a) (ext y)) (emul (ext a) (ext x));3995fp_le_ext r2 r13996end3997end else begin3998let c = einv (ext a) in3999assert { is_positive a -> ele (Fin 0.0) c };4000assert { not is_positive a -> ele c (Fin 0.0) };4001emul_mono c (ext x) (ext y);4002assert { r1 = round_f fm md (mul_zneg x a) (emul (ext x) c) };4003assert { r2 = round_f fm md (mul_zneg y a) (emul (ext y) c) };4004if is_positive a then begin4005round_f_ele fm md (mul_zneg x a) (mul_zneg y a) (emul (ext x) c) (emul (ext y) c);4006fp_le_ext r1 r24007end else begin4008round_f_ele fm md (mul_zneg y a) (mul_zneg x a) (emul (ext y) c) (emul (ext x) c);4009fp_le_ext r2 r14010end4011end4012{qed}4013
The contrapositive: the results strictly in order give the arguments strictly in order
Valid (371ms) (colibri2)let ghost mono_back (k: int) (md: mode) (a x y: t) : unit4017requires { fmt x = fmt a /\ fmt y = fmt a /\ mono_ok k a }4018requires { fp_lt (mop k md a x) (mop k md a y) }4019ensures { incr k a -> fp_lt x y }4020ensures { not incr k a -> fp_lt y x }4021= {proof…}4022let r1 = mop k md a x in4023let r2 = mop k md a y in4024mop_nan k md a x; mop_nan k md a y;4025lt_not_le_any r1 r2;4026assert { not fp_le r2 r1 };4027total_any x y;4028index_inj x; index_inj y;4029if pure { incr k a } then begin4030if pure { not fp_lt x y } then begin4031assert { fp_le y x };4032mono k md a y x;4033absurd4034end4035end else begin4036if pure { not fp_lt y x } then begin4037assert { fp_le x y };4038mono k md a x y;4039absurd4040end4041end4042{qed}4043
The direction of the monotonicity of mop k in y, by the domain of a
Valid (1.1s) (colibri2)let mono_dir (d: envp 'm) (k: int) (fm: format) (a: Atom.t) : option bool4047requires { fmt_of a = fm /\ 0 <= k <= 2 }4048ensures { match result with4049| Some i -> live d -> mono_ok k (d.mf a) /\ (i <-> incr k (d.mf a))4050| None -> true end }4051= if k = 0 then Some true4052else match get d a with4053| None -> None4054| Some va ->4055let (minf, pinf, nz, pz) = consts fm in4056let nonzero = k = 1 ||4057match is_distinct_or_included fm va (zeros fm nz pz) with4058| Disjoint -> true | _ -> false end in4059if not nonzero then None4060else match is_distinct_or_included fm va (positives fm pz pinf) with4061| Included -> Some true4062| _ ->4063match is_distinct_or_included fm va (negatives fm minf nz) with4064| Included -> Some false4065| _ -> None4066end4067end4068end4069
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)let le_pair (d: env) (fm: format) (s1 s2: Atom.t) : unit4073requires { fmt_of s1 = fm /\ fmt_of s2 = fm }4074requires { live d -> fmt (d.mf s1) = fm /\ fp_le (d.mf s1) (d.mf s2) }4075= let (minf, pinf, nz, pz) = consts fm in4076{proof…}4077if pure { live d } then begin4078le_not_nan_any (d.mf s1) (d.mf s2);4079le_refl_any (d.mf s1); le_refl_any (d.mf s2);4080assert { is_not_nan (d.mf s1) /\ is_not_nan (d.mf s2) }4081end;4082{qed}4083match get d s1 with4084| Some vu ->4085match vu.u with4086| Cons _ _ ->4087let lo = first fm vu in4088let lo' = if is_zero_f fm nz pz lo then nz else lo in4089{proof…}4090if pure { live d } then begin4091assert { mem_u (d.mf s1) vu.u };4092assert { le_dz lo (d.mf s1) };4093index_range (d.mf s2);4094assert { index lo <= index (d.mf s1) };4095assert { index (d.mf s1) <= index (d.mf s2) \/4096(is_zero (d.mf s1) /\ is_zero (d.mf s2)) };4097assert { index lo' <= index (d.mf s2) };4098assert { le_dz lo' (d.mf s2) };4099assert { le_dz (d.mf s2) pinf }4100end;4101le_pinf fm lo';4102{qed}4103upd_dom d s2 (interval fm lo' pinf)4104| Nil -> ()4105end4106| None -> ()4107end;4108match get d s2 with4109| Some vv ->4110match vv.u with4111| Cons _ _ ->4112let hi = last fm vv in4113let hi' = if is_zero_f fm nz pz hi then pz else hi in4114{proof…}4115if pure { live d } then begin4116assert { mem_u (d.mf s2) vv.u };4117assert { le_dz (d.mf s2) hi };4118index_range (d.mf s1);4119assert { index (d.mf s2) <= index hi };4120assert { index (d.mf s1) <= index (d.mf s2) \/4121(is_zero (d.mf s1) /\ is_zero (d.mf s2)) };4122assert { index (d.mf s1) <= index hi' };4123assert { le_dz (d.mf s1) hi' };4124assert { le_dz minf (d.mf s1) }4125end;4126minf_le fm hi';4127{qed}4128upd_dom d s1 (interval fm minf hi')4129| Nil -> ()4130end4131| None -> ()4132end;4133set_le d fm s1 s24134
u < v
Valid (48ms) (colibri2 6) (split_vc 3) (depth 3)let lt_pair (d: env) (fm: format) (u v: Atom.t) : unit4137requires { fmt_of u = fm /\ fmt_of v = fm }4138requires { live d -> fmt (d.mf u) = fm /\ fp_lt (d.mf u) (d.mf v) }4139= {proof…} if pure { live d } then lt_le_any (d.mf u) (d.mf v); {qed}4140set_lt d fm u v;4141le_pair d fm u v4142
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)let rec mono_pairs (d: env) (k: int) (fm: format) (r m a y: Atom.t) (i: bool)4145(l: list (Atom.t, Atom.t)) : unit4146requires { fmt_of r = fm /\ fmt_of y = fm /\ 0 <= k <= 2 }4147requires { live d -> fmt (d.mf a) = fm /\ fmt (d.mf y) = fm /\4148mono_ok k (d.mf a) /\ (i <-> incr k (d.mf a)) /\4149d.mf r = mop k (d.mm m) (d.mf a) (d.mf y) }4150requires { forall r' x. LM.mem (r', x) l -> fmt_of x = fm /\ fmt_of r' = fm /\4151(live d -> fmt (d.mf x) = fm /\ d.mf r' = mop k (d.mm m) (d.mf a) (d.mf x)) }4152variant { l }4153= match l with4154| Nil -> ()4155| Cons (r', x) t ->4156{proof…}4157assert { LM.mem (r', x) l /\ forall z. LM.mem z t -> LM.mem z l };4158assert { fmt_of x = fm /\ fmt_of r' = fm };4159let ghost md = d.mm m in4160let ghost fa = d.mf a in4161let ghost fx = d.mf x in4162let ghost fy = d.mf y in4163assert { live d -> fmt fa = fm /\ fmt fx = fm /\ fmt fy = fm /\ mono_ok k fa /\4164(i <-> incr k fa) /\ d.mf r = mop k md fa fy /\ d.mf r' = mop k md fa fx };4165{qed}4166if not_nan_dom d r && not_nan_dom d r' then begin4167if rel_le d fm x y then begin4168{proof…} if pure { live d } then mono k md fa fx fy; {qed}4169if i then le_pair d fm r' r else le_pair d fm r r'4170end;4171if rel_le d fm y x then begin4172{proof…} if pure { live d } then mono k md fa fy fx; {qed}4173if i then le_pair d fm r r' else le_pair d fm r' r4174end4175end;4176if rel_lt d fm r' r then begin4177{proof…} if pure { live d } then mono_back k md fa fx fy; {qed}4178if i then lt_pair d fm x y else lt_pair d fm y x4179end;4180if rel_lt d fm r r' then begin4181{proof…} if pure { live d } then mono_back k md fa fy fx; {qed}4182if i then lt_pair d fm y x else lt_pair d fm x y4183end;4184mono_pairs d k fm r m a y i t4185end4186
Whether a pair may give something: a relation known
Valid (44ms) (colibri2)let rec mono_useful (d: envp 'm) (fm: format) (r y: Atom.t) (l: list (Atom.t, Atom.t)) : bool4189variant { l }4190= match l with4191| Nil -> false4192| Cons (r', x) t ->4193rel_le d fm x y || rel_le d fm y x || rel_lt d fm r' r ||4194rel_lt d fm r r' || mono_useful d fm r y t4195end4196
The common argument and the other one of Mono o fm r m p q sw
Valid (17ms) (colibri2)let mono_args (o: bop) (p q: Atom.t) (sw: bool) : (Atom.t, Atom.t)4199ensures { let (a, y) = result in4200match o with4201| ODiv -> a = q /\ y = p4202| _ -> if sw then a = q /\ y = p else a = p /\ y = q4203end }4204= match o with ODiv -> (q, p) | _ -> if sw then (q, p) else (p, q) end4205
dsem dec v n: what the decision dec of fp_interval.Rules says of the result v and the argument n
predicate dsem (dec: IR.decision) (v n: t) =4211match dec with4212| IR.DNone -> true4213| IR.DMerge -> v = n4214| IR.DEq -> fp_eq v n4215| IR.DLeB -> fp_le n v4216| IR.DLeR -> fp_le v n4217end4218
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)let decide (o: bop) (fm: format) (da db: dom) : IR.decision4222ensures { forall md x y. FE.mem_at fm x da -> FE.mem_at fm y db ->4223match o with4224| ODiv -> dsem result (fop o md x y) x4225| _ -> fop o md y x = fop o md x y /\ dsem result (fop o md x y) y4226end }4227= try4228match o with4229| OAdd -> FE.add_rule fm da db4230| OMul ->4231match FE.mul_rule fm da db with IR.DEq -> IR.DNone | dec -> dec end4232| ODiv ->4233match FE.div_rule fm da db with IR.DEq -> IR.DNone | dec -> dec end4234end4235with FE.FormatMismatch -> IR.DNone4236end4237
The fact of the decision dec on the result r and the argument n
Valid (165ms) (colibri2 7) (split_vc) (depth 1)let act (d: env) (fm: format) (dec: IR.decision) (r n: Atom.t) : unit4240requires { fmt_of r = fm /\ fmt_of n = fm }4241requires { live d -> fmt (d.mf r) = fm /\ fmt (d.mf n) = fm /\ dsem dec (d.mf r) (d.mf n) }4242= match dec with4243| IR.DNone -> ()4244| IR.DMerge -> mergef d n r4245| IR.DEq -> set_eq d fm n r4246| IR.DLeB -> set_le d fm n r4247| IR.DLeR -> set_le d fm r n4248end4249
x + x is 2 * x
Valid (411ms) (colibri2)let lemma add_self (md: mode) (x c: t)4252requires { is_two (fmt x) c }4253ensures { fp_add md x x = fp_mul md c x }4254= {proof…}4255ext_sign c;4256assert { is_positive c /\ not is_zero c };4257assert { not is_infinity c };4258if is_nan x then ()4259else begin4260ext_sign x;4261assert { not opposite (ext x) (ext x) };4262assert { add_zneg md x x = mul_zneg c x };4263assert { eadd (ext x) (ext x) = emul (ext c) (ext x) };4264assert { not (is_zero c /\ is_infinity x) /\ not (is_infinity c /\ is_zero x) }4265end4266{qed}4267
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)let may_change (d: envp 'm) (p: prop) : bool4272requires { wf p }4273requires { live d -> holds d p }4274= match p with4275| RBin o r a b -> rbin_check d o r a b4276| Rel ODiv fm r _ a b -> div_useful d fm r a b4277| Rel OAdd fm r _ a b -> avg_useful d fm a b (divs d fm r)4278| Cmp _ _ r _ _ -> match getb d r with None -> true | Some _ -> false end4279| Mono o fm r m p q sw ->4280let (a, y) = mono_args o p q sw in4281let k = bk o in4282match mono_dir d k fm a with4283| Some _ -> mono_useful d fm r y (sibs d k fm m a r)4284| None -> false4285end4286| _ -> true4287end4288
The step of the propagator p; the result true stops it
Valid (2.1s) (colibri2 682) (cvc5 75) (split_vc 33) (depth 5)let run (d: env) (p: prop) : bool4293requires { wf p }4294requires { live d -> holds d p }4295= match p with4296| Bin o fm r m a b ->4297let c = consts fm in4298let (minf, pinf, _, _) = c in4299let om = mode d m in4300(* forward *)4301match get d a, get d b with4302| Some va, Some vb -> upd_dom d r (fwd fm c o om va vb)4303| _ -> ()4304end;4305(* backward, when the domain of [r] is known *)4306match get d r with4307| None -> ()4308| Some vr ->4309let tp = top fm minf pinf in4310let va = match get d a with Some v -> v | None -> tp end in4311let vb = match get d b with Some v -> v | None -> tp end in4312{proof…}4313assert { live d -> (om = None \/ om = Some (d.mm m)) /\4314mem (d.mf r) vr /\ mem (d.mf a) va /\ mem (d.mf b) vb };4315{qed}4316let x = back fm c o om false vr vb va in4317{proof…}4318assert { live d -> back_ok o (d.mm m) false vr vb va x };4319assert { live d -> match x with Some v -> mem (d.mf a) v | None -> false end };4320{qed}4321match x with4322| None -> contradiction d4323| Some x -> upd_dom d a x4324end;4325let va = match get d a with Some v -> v | None -> tp end in4326let vb = match get d b with Some v -> v | None -> tp end in4327{proof…}4328assert { live d -> (om = None \/ om = Some (d.mm m)) /\4329mem (d.mf r) vr /\ mem (d.mf a) va /\ mem (d.mf b) vb };4330{qed}4331let y = back fm c o om true vr va vb in4332{proof…}4333assert { live d -> back_ok o (d.mm m) true vr va vb y };4334assert { live d -> match y with Some v -> mem (d.mf b) v | None -> false end };4335{qed}4336match y with4337| None -> contradiction d4338| Some y -> upd_dom d b y4339end4340end;4341dyadic_bin d o fm r m a b;4342false4343| Un o fm r m a ->4344let c = consts fm in4345let (minf, pinf, _, _) = c in4346let om = mode d m in4347match get d a with4348| Some va -> upd_dom d r (fwd_u fm c o om va)4349| None -> ()4350end;4351match get d r with4352| None -> ()4353| Some vr ->4354let va = match get d a with Some v -> v | None -> top fm minf pinf end in4355{proof…}4356assert { live d -> (om = None \/ om = Some (d.mm m)) /\4357mem (d.mf r) vr /\ mem (d.mf a) va };4358{qed}4359let x = back_u fm c o om vr va in4360{proof…}4361assert { live d -> back_u_ok o (d.mm m) vr va x };4362{qed}4363match x with4364| None -> contradiction d4365| Some x -> upd_dom d a x4366end4367end;4368match o with URti -> dyadic_rti d fm r m a | USqrt -> () end;4369false4370| Cvt fm fm' r m a ->4371let c = consts fm in4372let c' = consts fm' in4373let (minf, pinf, _, _) = c in4374let om = mode d m in4375match get d a with4376| Some va -> upd_dom d r (fwd_c fm fm' om va)4377| None -> ()4378end;4379match get d r with4380| None -> ()4381| Some vr ->4382let va = match get d a with Some v -> v | None -> top fm minf pinf end in4383{proof…}4384assert { live d -> (om = None \/ om = Some (d.mm m)) /\4385mem (d.mf r) vr /\ mem (d.mf a) va };4386{qed}4387let x = back_c fm fm' c c' om vr va in4388{proof…}4389assert { live d -> back_c_ok fm' (d.mm m) vr va x };4390{qed}4391match x with4392| None -> contradiction d4393| Some x -> upd_dom d a x4394end4395end;4396dyadic_cvt d fm fm' r m a;4397false4398| Abs fm r a ->4399let (_, pinf, _, pz) = consts fm in4400match get d a with4401| Some va -> upd_dom d r (abs_dom fm pz va)4402| None -> ()4403end;4404match get d r with4405| Some vr -> upd_dom d a (abs_back fm pz pinf vr)4406| None -> ()4407end;4408(* `abs a = a` for `a` positive, `a = - (abs a)` for `a` negative *)4409match get d a with4410| Some va ->4411if abs_id fm (consts fm) va then mergef d a r4412else if abs_opp fm (consts fm) va then begin4413let c = match negs d r with Some c -> c | None -> mk_neg d fm r end in4414{proof…} if pure { live d } then neg_neg (d.mf a); {qed}4415mergef d a c4416end4417| None -> ()4418end;4419false4420| Choice r a b ->4421match get d a, get d b with4422| Some va, Some vb -> upd_dom d r (union (fmt_of a) va vb)4423| _ -> ()4424end;4425false4426| Cmp o fm r a b ->4427let c = consts fm in4428let (minf, pinf, _, _) = c in4429match getb d r with4430| None -> cmp_of_rel d o fm r a b4431| Some t ->4432let va = match get d a with Some v -> v | None -> top fm minf pinf end in4433{proof…}4434assert { live d -> mem (d.mf a) va /\ fmt (d.mf b) = fm /\4435(t <-> fcmp_r o false (d.mf a) (d.mf b)) };4436{qed}4437match cmp_back fm c o t false va with4438| None -> contradiction d4439| Some x -> upd_dom d b x4440end;4441let vb = match get d b with Some v -> v | None -> top fm minf pinf end in4442match cmp_back fm c o t true vb with4443| None -> contradiction d4444| Some x -> upd_dom d a x4445end;4446(* the relation database *)4447write_rel d fm a b (cmp_rel o t (ghost d.mf a) (ghost d.mf b)) rel_depth;4448rel_check d fm a b;4449(* the database may contradict `t` (a false `fp.eq` writes nothing) *)4450cmp_of_rel d o fm r a b;4451(* `fp.eq a b` is `a = b` when the signs of zero cannot differ *)4452match o, t with4453| CEq, True ->4454match get d a, get d b with4455| Some va, Some vb -> if fp_eq_merge fm c va vb then mergef d a b4456| _ -> ()4457end;4458(* the terms `a - b` and `b - a` are zeros (or NaN) *)4459{proof…}4460assert { live d -> fp_eq (d.mf b) (d.mf a) };4461{qed}4462sub_eq_terms d fm a b (subs d fm a b);4463sub_eq_terms d fm b a (subs d fm b a)4464| _ -> ()4465end4466end;4467false4468| Is o fm r a ->4469let c = consts fm in4470let (minf, pinf, _, _) = c in4471let cd = class_dom fm c (classes fm) o in4472match getb d r with4473| Some True -> upd_dom d a cd4474| Some False ->4475match diff fm (top fm minf pinf) cd with4476| None -> contradiction d4477| Some x -> upd_dom d a x4478end4479| None ->4480match get d a with4481| None -> ()4482| Some va ->4483match is_distinct_or_included fm va cd with4484| Included -> setb d r true4485| Disjoint -> setb d r false4486| Uncomparable -> ()4487end4488end4489end;4490false4491| ToReal fm r a ->4492let (minf, pinf, _, _) = consts fm in4493match get d a with4494| None -> ()4495| Some va ->4496match to_real_fwd fm minf pinf va with4497| None -> ()4498| Some l -> updr_dom d r l4499end4500end;4501match getr d r with4502| None -> ()4503| Some vr ->4504let va = match get d a with Some v -> v | None -> top fm minf pinf end in4505match to_real_back fm minf pinf va vr with4506| None -> contradiction d4507| Some x -> upd_dom d a x4508end4509end;4510dyadic_to_real d fm r a;4511false4512| OfReal fm r m a ->4513let (minf, pinf, _, _) = consts fm in4514let om = mode d m in4515{proof…}4516assert { live d -> om = None \/ om = Some (d.mm m) };4517{qed}4518match getr d a with4519| None -> ()4520| Some l -> upd_dom d r (of_real_fwd fm minf pinf om l)4521end;4522match get d r with4523| None -> ()4524| Some vr ->4525match of_real_back fm om vr with4526| None -> ()4527| Some l -> updr_dom d a l4528end4529end;4530false4531| OfBits fm r a back ->4532match getr d a with4533| None -> ()4534| Some l -> upd_dom d r (of_bits_fwd fm l)4535end;4536if back then begin4537match get d r with4538| None -> ()4539| Some vr -> updr_dom d a (of_bits_back fm vr)4540end4541end;4542false4543| ToRealIn fm r a lo hi ->4544let (minf, pinf, _, _) = consts fm in4545match get d a with4546| None -> ()4547| Some va ->4548match to_real_fwd fm minf pinf va with4549| Some l -> if in_range lo hi l then updr_dom d r l4550| None -> ()4551end4552end;4553match getr d r with4554| None -> ()4555| Some vr ->4556let va = match get d a with Some v -> v | None -> top fm minf pinf end in4557let out = Cons (RInter BInf (BStrict (a_of_int lo)))4558(Cons (RInter (BStrict (a_of_int hi)) BInf) vr) in4559match to_real_back fm minf pinf va out with4560| None -> contradiction d4561| Some x -> upd_dom d a x4562end4563end;4564dyadic_to_real_in d fm r a lo hi;4565false4566| ExactInt fm r a t ->4567let (_, _, _, nl) = classes fm in4568let p = pow2 (fmt_sb fm) in4569let f = a_floor (to_a nl) in4570let b = if p <= f then p else f in4571match getr d a with4572| None -> false4573| Some l ->4574if in_range (- b) b l then begin4575{proof…}4576if pure { live d } then begin4577let ghost n = any int ensures { d.mr a = from_int result } in4578let ghost md = any mode ensures { d.mf r = round_x fm result (d.mr a) } in4579assert { - b <= n <= b };4580assert { nl = of_index fm (nb_sign fm - 2) };4581round_int_exact fm md n4582end;4583{qed}4584merge d t a; true4585end else begin4586(* exact when the integer is a float of `fm` (its dyadic domain) in the range of `fm` *)4588let (umin, _, psb) = fmt_dy fm in4589let da = D.inter (getdr_r d a) (D.mk (Some 0) None None) in4590{proof…}4591if pure { live d } then begin4592let ghost n = any int ensures { d.mr a = from_int result } in4593assert { pow2r 0 = 1.0 };4594dv_intro (d.mr a) (pow2r 0) n4595end;4596{qed}4597if in_range_a (to_a (neg nl)) (to_a nl) l && FD.is_exact umin psb da then begin4598{proof…}4599if pure { live d } then begin4600let ghost md = any mode ensures { d.mf r = round_x fm result (d.mr a) } in4601assert { nl = of_index fm (nb_sign fm - 2) };4602assert { umin = ulp_min fm /\ psb = sb fm };4603assert { D.mem (d.mr a) da };4604assert { D.fix (d.mr a) umin /\ D.flt (d.mr a) psb };4605max_facts fm; neg_fin nl;4606assert { -. to_real nl <=. d.mr a <=. to_real nl };4607FD.round_exact fm md (d.mr a <. 0.0) (d.mr a)4608end;4609{qed}4610merge d t a; true4611end else false4612end4613end4614| ExactCvt fm fm' r a tr ta ->4615if fmt_eb fm <= fmt_eb fm' && fmt_sb fm <= fmt_sb fm' then begin4616let (minf, pinf, _, _) = consts fm in4617match get d a with4618| None -> false4619| Some va ->4620match to_real_fwd fm minf pinf va with4621| None -> false4622| Some _ ->4623{proof…}4624if pure { live d } then begin4625let ghost md = any mode ensures { d.mf r = fp_convert fm' result (d.mf a) } in4626convert_wider fm' md (d.mf a)4627end;4628{qed}4629merge d tr ta; true4630end4631end4632end else begin4633(* narrowing: exact when the float is a float of `fm'` (its dyadic domain) in the range of `fm'` *)4635let (minf, pinf, _, _) = consts fm in4636let (umin, umax, psb) = fmt_dy fm in4637let (umin', _, psb') = fmt_dy fm' in4638let (_, _, _, nl') = classes fm' in4639match get d a with4640| None -> false4641| Some va ->4642match to_real_fwd fm minf pinf va with4643| None -> false4644| Some ra ->4645let m = to_a nl' in4646let ml = to_a (neg nl') in4647let da = getd_f d a umin umax psb minf pinf in4648if in_range_a ml m ra && FD.is_exact umin' psb' da then begin4649{proof…}4650if pure { live d } then begin4651let ghost x = d.mf a in4652let ghost md = any mode ensures { d.mf r = fp_convert fm' result x } in4653assert { nl' = of_index fm' (nb_sign fm' - 2) };4654assert { mem x va };4655assert { is_not_nan x /\ not (is_inf x) /\ rmem (to_real x) ra };4656assert { ext x = Fin (to_real x) };4657assert { FD.finite x };4658assert { D.mem (to_real x) da };4659assert { D.fix (to_real x) (ulp_min fm') /\ D.flt (to_real x) (sb fm') };4660assert { A.real ml <=. to_real x <=. A.real m };4661max_facts fm'; neg_fin nl';4662assert { ext (neg nl') = Fin (-. to_real nl') };4663assert { -. to_real nl' <=. to_real x <=. to_real nl' };4664FD.round_exact fm' md (if is_positive x then false else true) (to_real x);4665assert { d.mf r = round_f fm' md (if is_positive x then false else true) (Fin (to_real x)) }4666end;4667{qed}4668merge d tr ta; true4669end else false4670end4671end4672end4673| RBin o r a b -> dyadic_rbin d o r a b; false4674| RNeg r a -> dyadic_rneg d r a; false4675| AddSelf r a b t ->4676if is_equal d a b then begin register d t; mergef d r t; true end4677else false4678| NegInv r a ->4679(* `a = - b` gives `r = b` *)4680let s1 = match negs d a with4681| Some b -> {proof…} neg_neg (d.mf b); {qed} mergef d r b; true4682| None -> false4683end in4684(* `r = - c` gives `a = c` *)4685let s2 = match negs d r with4686| Some c -> {proof…} neg_neg (d.mf a); neg_neg (d.mf c); {qed} mergef d a c; true4687| None -> false4688end in4689(* the other terms `fp.neg` of the classes have their own propagator *)4690s1 && s24691| AddOpp fm r m a b ->4692(* `a - c` with `fp.eq a c` true *)4693match negs d b with4694| Some c ->4695if rel_eq d fm a c then begin4696{proof…}4697assert { live d -> d.mf b = neg (d.mf c) /\ fp_eq (d.mf a) (d.mf c) };4698assert { live d -> d.mf r = fp_add (d.mm m) (d.mf a) (neg (d.mf c)) };4699{qed}4700let v = sub_eq_dom fm (consts fm) (get d a) in4701upd_dom d r v4702end4703| None -> ()4704end;4705match negs d a with4706| Some c ->4707if rel_eq d fm b c then begin4708{proof…}4709assert { live d -> d.mf a = neg (d.mf c) /\ fp_eq (d.mf b) (d.mf c) };4710if pure { live d } then add_comm (d.mm m) (d.mf a) (d.mf b);4711assert { live d -> d.mf r = fp_add (d.mm m) (d.mf b) (neg (d.mf c)) };4712{qed}4713let v = sub_eq_dom fm (consts fm) (get d b) in4714upd_dom d r v4715end4716| None -> ()4717end;4718let opp =4719match negs d b with4720| Some c -> is_equal d c a4721| None -> false4722end ||4723match negs d a with4724| Some c -> is_equal d c b4725| None -> false4726end in4727if opp then begin4728let (minf, pinf, nz, pz) = consts fm in4729let fin = match get d a with4730| Some va -> is_finite fm minf pinf va4731| None -> false4732end in4733{proof…}4734if pure { live d } then begin4735assert { d.mf b = neg (d.mf a) \/ d.mf a = neg (d.mf b) };4736neg_special (d.mf a); neg_special (d.mf b);4737if pure { is_not_nan (d.mf a) /\ not (is_inf (d.mf a)) } then begin4738add_opp (d.mm m) (d.mf a) nz pz; add_opp (d.mm m) (d.mf b) nz pz4739end else begin4740add_opp_nan (d.mm m) (d.mf a); add_opp_nan (d.mm m) (d.mf b)4741end4742end;4743{qed}4744let (z, stop) = match mode d m with4745| Some RTN -> (singleton fm nz, true)4746| Some _ -> (singleton fm pz, true)4747| None -> (zeros fm nz pz, false)4748end in4749(* the domains of `a` and `b` then remove NaN from `r` *)4750upd_dom d r (if fin then z else union fm z (nan_dom fm));4751stop4752end4753else false4754| Mono o fm r m p q sw ->4755let (a, y) = mono_args o p q sw in4756let k = bk o in4757{proof…}4758if pure { live d } then begin4759match o with4760| OAdd -> add_comm (d.mm m) (d.mf p) (d.mf q)4761| OMul -> mul_comm (d.mm m) (d.mf p) (d.mf q)4762| ODiv -> ()4763end;4764assert { d.mf r = mop k (d.mm m) (d.mf a) (d.mf y) }4765end;4766{qed}4767match mono_dir d k fm a with4768| Some i -> mono_pairs d k fm r m a y i (sibs d k fm m a r)4769| None -> ()4770end;4771false4772| Rel o fm r m a b ->4773match o with4774| ODiv -> rel_div d fm r a b4775| OAdd -> rel_avg d fm r m a b (divs d fm r)4776| OMul -> ()4777end;4778false4779| Rule o fm r _ a b ->4780match get d a, get d b with4781| Some va, Some vb ->4782(* nothing when both are singletons (the domains then decide) *)4783match FE.is_singleton va, FE.is_singleton vb with4784| (No, _) | (_, No) ->4785match o with4786| ODiv -> act d fm (decide o fm va vb) r a4787| _ ->4788act d fm (decide o fm va vb) r b;4789act d fm (decide o fm vb va) r a4790end4791| _ -> ()4792end4793| _ -> ()4794end;4795false4796| Neg r a ->4797{proof…} if pure { live d } then neg_neg (d.mf a); {qed}4798match get d a with4799| Some va -> upd_dom d r (neg_dom (fmt_of a) va)4800| None -> ()4801end;4802match get d r with4803| Some vr -> upd_dom d a (neg_dom (fmt_of a) vr)4804| None -> ()4805end;4806false4807end4808
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)
predicate valid (p: prop) =4827wf p /\ (forall d: env. live d -> holds d p) /\4828(forall d: envp ro. live d -> holds d p)4829
The model of an environment (colibrilib/env.mlw)
function model_of (d: envp 'm) : model = d.model4832
A propagator that holds in the environments of the model m when l (the environment where it is registered is live)
predicate valid_at (m: model) (l: bool) (p: prop) =4836wf p /\ (l -> (forall d: env. model_of d = m -> holds d p) /\4837(forall d: envp ro. model_of d = m -> holds d p))4838Valid (54ms) (colibri2)4839type reg = { rp: prop; ghost rm: model; ghost rl: bool }4840invariant { valid_at rm rl rp }4841by { rp = (let x = any Atom.t in Choice x x x); rm = any model; rl = false }4842
The propagator p, registered in d
Valid (59ms) (colibri2)let mk_reg (d: env) (p: prop) : reg4845requires { valid_at (model_of d) (live d) p }4846ensures { result.rp = p /\ result.rm = model_of d /\ result.rl = live d }4847= { rp = p; rm = pure { model_of d }; rl = pure { live d } }4848Valid (41ms) (colibri2)4849let run_reg (d: env) (r: reg) : bool4850requires { model_of d = r.rm /\ (live d -> r.rl) }4851= run d r.rp4852Valid (53ms) (colibri2)4853let may_change_reg (d: envp ro) (r: reg) : bool4854requires { model_of d = r.rm /\ (live d -> r.rl) }4855= may_change d r.rp4856end4857