library colibrilib.fp_conv — module Envmodule Env17use int.Int18use int.Power19use option.Option20use colibrilib.ring.Atom21use colibrilib.fp.Ereal22use colibrilib.fbin.Fp23use colibrilib.fp_interval.Intervals24use colibrilib.fp_interval.FpInterval25use real.RealInfix26use list.List27use list.Mem as LM28use real.FromInt29use real.Truncate30use colibrilib.stda.StdA as A31use colibrilib.dyadic.Dyadic as D32use colibrilib.fp_dyadic.Rules as FD33use colibrilib.pow2r.Pow2r34use colibrilib.zinterval.Zi as Zi35use colibrilib.stdq.StdQ as Q36use colibrilib.zarith.Zbit as Zbit37use colibrilib.zbit.ZbitInt38use colibrilib.stdq.QBits as QB39use int.Abs as IA40use colibrilib.fp_interval.Export as IE41
The generic environment of colibrilib/env.mlw: the model is immutable, one model for the run; alive is mutable (the backtracking of colibri2 changes it, no function here does); the writes change only the state of the propagation (writes { d.state }). This module gives the view of the floats of the model and of the state.
use export colibrilib.env.State49use export colibrilib.env.RealValue50
The values of the float nodes, of the rounding mode nodes and of the Boolean nodes in a model
function float_value (md: model) (n: Atom.t) : Fp.t54function mode_value (md: model) (n: Atom.t) : mode55function bool_value (md: model) (n: Atom.t) : bool56
The dyadic domain of each node (Dom_dyadic.dom), and the set of the values that the domain of the reals of each node (Dom_interval.dom: intervals and congruence) allows, in a state
function dyadic_dom (s: state) (n: Atom.t) : option D.t61function real_dom (s: state) (n: Atom.t) (x: real) : bool62
The views of d
function mf (d: envp 'm) : Atom.t -> Fp.t = float_value d.model65function mm (d: envp 'm) : Atom.t -> mode = mode_value d.model66function mb (d: envp 'm) : Atom.t -> bool = bool_value d.model67function mr (d: envp 'm) : Atom.t -> real = real_value d.model68function dy (d: envp 'm) : Atom.t -> option D.t = dyadic_dom d.state69function ri (d: envp 'm) : Atom.t -> real -> bool = real_dom d.state70
The update of a dyadic domain w by v changes nothing: the meet of Dom.Lattice.upd_dom is w, or v is the top, not set (Fp_conv_env.upddr)
predicate dnoop (w: option D.t) (v: D.t) =75match w with None -> v = D.top | Some w -> D.meet w v = w end76
The format of the type of a float node: it does not depend on the model
function fmt_of (n:Atom.t) : format80
Egraph.register
val register (d:env) (n:Atom.t) : unit83writes { d.state }84
Egraph.get_dom of the domain of the floats (Dom_interval.dom)
val get (d: envp 'm) (n:Atom.t) : option dom87ensures { match result with88| Some v -> v.fm = fmt_of n /\ (live d -> mem (d.mf n) v)89| None -> true90end }91
Dom_interval.upd_dom: the intersection with the domain of n; it raises Egraph.Contradiction when it is empty, so only when d is not live (the branches that are not live are not modelled)
val upd (d:env) (n:Atom.t) (v:dom) : unit96requires { live d -> mem (d.mf n) v }97writes { d.state }98
Rounding_mode.get
val mode (d: envp 'm) (n:Atom.t) : option mode101ensures { match result with102| Some md -> live d -> d.mm n = md103| None -> true104end }105
Boolean.is: the value of a Boolean node, when it is known
val getb (d: envp 'm) (n:Atom.t) : option bool108ensures { match result with109| Some b -> live d -> d.mb n = b110| None -> true111end }112
Boolean.set_bool
val setb (d:env) (n:Atom.t) (b:bool) : unit115requires { live d -> d.mb n = b }116writes { d.state }117
A union of intervals with algebraic bounds (Dom_interval.D.t): the empty list is the empty domain.
type bnd = BInf | BLarge A.t | BStrict A.t123type riv = RSing A.t | RInter bnd bnd124type rdom = list riv125126predicate rmem_lo (x: real) (b: bnd) =127match b with BInf -> true | BLarge a -> A.real a <=. x | BStrict a -> A.real a <. x end128predicate rmem_hi (x: real) (b: bnd) =129match b with BInf -> true | BLarge a -> x <=. A.real a | BStrict a -> x <. A.real a end130predicate rmem_iv (x: real) (i: riv) =131match i with132| RSing a -> x = A.real a133| RInter lo hi -> rmem_lo x lo /\ rmem_hi x hi134end135predicate rmem (x: real) (l: rdom) =136match l with Nil -> false | Cons i l' -> rmem_iv x i \/ rmem x l' end137
Egraph.get_dom of the domain of the reals (Dom_interval.dom)
val getr (d: envp 'm) (n:Atom.t) : option rdom140ensures { match result with141| Some v -> (live d -> rmem (d.mr n) v) /\ forall x. d.ri n x -> rmem x v142| None -> true143end }144
The congruence part of Dom_interval.dom (Union.t.c, the class rem + div ℤ of colibrilib/congruence.mlw), as Cls div rem (NoCls: none; not an option of a pair: the provers did not get its components in the proof of RealDom.getc): every node of sort Int has Cls 1 0 (converter.ml, bounds_of_type)
type ocls = NoCls | Cls A.t A.t151152val getc (d: envp 'm) (n:Atom.t) : ocls153ensures { match result with154| Cls dv rm ->155(live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv) /\156forall x. d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv157| NoCls -> true158end }159
The class rem + div ℤ of the domain of n, for RealDom.getc
Valid (47ms) (colibri2)let mk_cls (ghost d: envp 'm) (ghost n: Atom.t) (dv rm: A.t) : ocls162requires { live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv }163requires { forall x. d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv }164ensures { match result with165| Cls dv rm ->166(live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv) /\167forall x. d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv168| NoCls -> true169end }170= Cls dv rm171
The classes rem + div ℤ that updc drops: div not rational, or of more than 256 bits (numerator or denominator in lowest terms): the classes 2^-1074 ℤ of the doubles slow the LRA theory down (colibri/sat/propLnExp3.smt2: 1.2s without them, 7s with them)
predicate dropped (dv: A.t) =177forall q: Q.t. A.real dv = Q.real q ->178power 2 256 <= IA.abs (Q.num q) \/ power 2 256 <= Q.den q179Valid (58ms) (colibri2)180let c_dropped (dv: A.t) : bool181ensures { result <-> dropped dv }182= match A.view dv with183| A.Irr -> true184| A.Rat q ->185{proof…}186let lemma uniq (q': Q.t) : unit187requires { A.real dv = Q.real q' } ensures { q' = q }188= Q.equal_is_eq q' q in189{qed}190QB.big 256 q191end192
Dom_interval.upd_dom of the class rem + div ℤ (Union.of_congruence); nothing when div is not rational
val updc (d:env) (n:Atom.t) (dv rm: A.t) : unit196requires { live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv }197writes { d.state }198ensures { (dropped dv \/199forall x. old d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv) ->200d.ri = old d.ri /\ d.dy = old d.dy }201
Dom_interval.upd_dom: the intersection with the domain of n
val updr (d:env) (n:Atom.t) (v:rdom) : unit204requires { live d -> rmem (d.mr n) v }205writes { d.state }206ensures { (forall x. old d.ri n x -> rmem x v) -> d.ri = old d.ri /\ d.dy = old d.dy }207
Egraph.merge of two real nodes
val merge (d:env) (a b:Atom.t) : unit210requires { live d -> d.mr a = d.mr b }211writes { d.state }212
Egraph.is_equal of two nodes: equal in the model, of one sort
val is_equal (d: envp 'm) (a b: Atom.t) : bool215ensures { result -> fmt_of a = fmt_of b }216ensures { result -> live d -> d.mf a = d.mf b /\ d.mm a = d.mm b }217
The operation of the terms of the kind k: fp.add (0), fp.mul (1), fp.div (2), fp.neg (3, of x alone)
function kop (k: int) (md: mode) (x y: t) : t =221if k = 0 then fp_add md x y else if k = 1 then fp_mul md x y222else if k = 2 then fp_div md x y else neg x223
A term r = kop k m x y of the e–graph (m and y are x for fp.neg), as Conv.view reads it: same format, the value of its interpretation
predicate kterm (d: envp 'm) (k: int) (t: (Atom.t, Atom.t, Atom.t, Atom.t)) =228let (r, m, x, y) = t in229fmt_of r = fmt_of x /\ fmt_of y = fmt_of x /\230(live d -> fmt (d.mf r) = fmt_of r /\ fmt (d.mf x) = fmt_of x /\231fmt (d.mf y) = fmt_of y /\ d.mf r = kop k (d.mm m) (d.mf x) (d.mf y))232
The terms of the kind k among the parents of the class of a (the Info domain of the theory of quantifiers); which ones is only a matter of completeness
val kparents (d: envp 'm) (k: int) (a: Atom.t) : list (Atom.t, Atom.t, Atom.t, Atom.t)237ensures { forall t. LM.mem t result -> kterm d k t }238
The terms of the kind k in the class of a (its applications in the Info domain)
val kapps (d: envp 'm) (k: int) (a: Atom.t) : list (Atom.t, Atom.t, Atom.t, Atom.t)242ensures { forall t. LM.mem t result -> kterm d k t }243
agents/design/ordering-relations.md,step B)
For two float nodes x and y of one format, an interval of zi y - zi x, zi the index with the two zeros merged: the order of the comparisons of IEEE 754 (Rules.zi_facts). It holds when neither is NaN. Implemented, with the same specifications, in RelDb.
function zi (x: t) : int = if index x < 0 then index x + 1 else index x252253predicate relh (i: Zi.t) (x y: t) =254is_not_nan x -> is_not_nan y -> Zi.mem (zi y - zi x) i255
What the database knows of x and y, of format fm (Zi.top if nothing)
val getrel (d: envp 'm) (fm: format) (x y: Atom.t) : Zi.t259ensures { live d -> relh result (d.mf x) (d.mf y) }260
Add i to the relation of x and y, of format fm: when it changes, the propagators registered on the pair (Conv.wait_rel) and the Mono of the terms around x and y (Conv.wait_mono) are scheduled, and the result is the new relation
val updrel (d: env) (fm: format) (x y: Atom.t) (i: Zi.t) : option Zi.t266requires { live d -> relh i (d.mf x) (d.mf y) }267writes { d.state }268ensures { d.ri = old d.ri /\ d.dy = old d.dy }269ensures { match result with Some n -> live d -> relh n (d.mf x) (d.mf y) | None -> true end }270
The operations monotonic in y for a fixed a: a + y (k = 0), a * y (k = 1), y / a (k = 2)
function mop (k: int) (md: mode) (a y: t) : t =274if k = 0 then fp_add md a y else if k = 1 then fp_mul md a y else fp_div md y a275
The node of the term fp.neg a, a of format fm, registered
val mk_neg (d: env) (fm: format) (a: Atom.t) : Atom.t278ensures { live d -> d.mf result = neg (d.mf a) }279ensures { fmt_of result = fmt_of a }280writes { d.state }281
Egraph.merge of two float nodes
val mergef (d:env) (a b:Atom.t) : unit284requires { live d -> d.mf a = d.mf b }285writes { d.state }286
Egraph.get_dom of the dyadic domain (Dom_dyadic.dom): on a float node, the powers of 2 dividing its real when it is finite (colibrilib/fp_dyadic.mlw)
val getd (d: envp 'm) (n:Atom.t) : option D.t291ensures { result = d.dy n }292ensures { match result with293| Some v -> live d -> FD.fmem (d.mf n) v294| None -> true295end }296
Dom_dyadic.upd_dom: the meet with the domain of n
val updd (d:env) (n:Atom.t) (v:D.t) : unit299requires { live d -> FD.fmem (d.mf n) v }300writes { d.state }301
The dyadic domain of a real node (Dom_dyadic.dom too): the powers of 2 dividing its real
val getdr (d: envp 'm) (n:Atom.t) : option D.t305ensures { result = d.dy n }306ensures { match result with307| Some v -> live d -> D.mem (d.mr n) v308| None -> true309end }310311val upddr (d:env) (n:Atom.t) (v:D.t) : unit312requires { live d -> D.mem (d.mr n) v }313writes { d.state }314ensures { dnoop (old d.dy n) v -> d.dy = old d.dy /\ d.ri = old d.ri }315
2^k
Valid (71ms) (colibri2)let a_pow2 (k: int) : A.t318ensures { A.real result = pow2r k }319= if 0 <= k then begin320{proof…} Zbit.lsl_mul 1 k; {qed}321A.of_bigint (lsl_int 1 k)322end else begin323{proof…} Zbit.lsl_mul 1 (-k); assert { 0 < power 2 (-k) }; {qed}324A.div (A.of_bigint 1) (A.of_bigint (lsl_int 1 (-k)))325end326
The rounding of the real a in a mode, a zero being negative when a < 0. A rational is rounded exactly (Intf.of_q). An irrational a is bracketed by [n/2^k, (n+1)/2^k], n = floor (a 2^k) (A.round_down_to, no test of rationality), with k growing by 64 bits until the two ends round to the same float (Intf.round_bracket). The rounding boundaries (the floats, their midpoints, the overflow threshold) are multiples of half the least positive float, 2^-(emax + sb - 2): at that precision, a, being strictly between the two ends, rounds as any real between them (Intf.round_between); the loop is bounded.
Valid (1.8s) (colibri2)let round_a (fm: format) (m: mode) (a: A.t) : t338ensures { result = round_f fm m (A.real a <. 0.0) (Fin (A.real a)) }339= match A.view a with340| A.Rat q ->341let (n, d) = QB.num_den q in342{proof…}343assert { n < 0 <-> A.real a <. 0.0 };344{qed}345Fp.of_q fm m (n < 0) n d346| A.Irr ->347let kmax = lsl_int 1 (eb_v fm - 1) + sb_v fm - 2 in348{proof…} Zbit.lsl_mul 1 (eb fm - 1); {qed}349let rec bracket (k: int) : t350requires { 0 <= k }351variant { kmax - k }352ensures { result = round_f fm m (A.real a <. 0.0) (Fin (A.real a)) }353= let k = if k > kmax then kmax else k in354let p = lsl_int 1 k in355{proof…} Zbit.lsl_mul 1 k; assert { 0 < p }; {qed}356let qp = Q.of_bigint p in357let r = A.round_down_to a (Q.div (Q.of_bigint 1) qp) in358let n = Q.floor_z (Q.mul r qp) in359{proof…}360assert { Q.real r *. from_int p = from_int n };361assert { from_int n /. from_int p <=. A.real a <=.362from_int (n + 1) /. from_int p };363{qed}364if k = kmax then begin365{proof…}366let ghost qn = Q.div (Q.of_bigint n) (Q.of_bigint p) in367assert { A.real a <> Q.real qn };368assert { from_int n /. from_int (power 2 k) <. A.real a };369{qed}370Fp.round_between fm m n k371end else372match Fp.round_bracket fm m n p (n + 1) p with373| Some x -> x374| None -> bracket (k + 64)375end376in377bracket (sb_v fm - 1)378end379
The float of the format fm that is the rounding up (resp. down) of the real a, a zero being negative when a < 0
Valid (58ms) (colibri2)let ceil_f (fm: format) (a: A.t) : t383ensures { result = round_f fm RTP (A.real a <. 0.0) (Fin (A.real a)) }384= round_a fm RTP a Valid (51ms) (colibri2)385let floor_f (fm: format) (a: A.t) : t386ensures { result = round_f fm RTN (A.real a <. 0.0) (Fin (A.real a)) }387= round_a fm RTN a388
The value of a finite float, from its significand and exponent
Valid (59ms) (colibri2)let to_a (x: t) : A.t391requires { is_not_nan x /\ not (is_inf x) }392ensures { A.real result = to_real x }393= let (n, e) = to_dyadic x in394A.mul (A.of_bigint n) (a_pow2 e)395Valid (44ms) (colibri2)396let a_eq (a b: A.t) : bool397ensures { result <-> A.real a = A.real b }398= A.equal a b399
The least (resp. greatest) finite float above (resp. below) a real r, strictly when strict, from the rounding f of r up (resp. down) and exact, whether f is finite of value r (Intf.float_lo, proved in fbin.mlw)
Valid (111ms) (colibri2)let float_lo (f: t) (strict exact: bool) : t405ensures { fmt result = fmt f }406ensures { forall r. f = round_f (fmt f) RTP (r <. 0.0) (Fin r) ->407(exact <-> is_not_nan f /\ not (is_inf f) /\ to_real f = r) ->408forall v. fmt v = fmt f -> is_not_nan v -> not (is_inf v) ->409(if strict then r <. to_real v else r <=. to_real v) -> le_dz result v }410= Fp.float_lo f strict exact Valid (113ms) (colibri2)411let float_hi (f: t) (strict exact: bool) : t412ensures { fmt result = fmt f }413ensures { forall r. f = round_f (fmt f) RTN (r <. 0.0) (Fin r) ->414(exact <-> is_not_nan f /\ not (is_inf f) /\ to_real f = r) ->415forall v. fmt v = fmt f -> is_not_nan v -> not (is_inf v) ->416(if strict then to_real v <. r else to_real v <=. r) -> le_dz v result }417= Fp.float_hi f strict exact418
The integer nodes of the bit–vectors (bv2nat, RealValue.bv_to_int of the LRA theory) are real nodes.
The widths of the format (mw + 1 and ew of F)
Valid (47ms) (colibri2)let fmt_eb (fm: format) : int426ensures { result = eb fm }427= eb_v fm Valid (51ms) (colibri2)428let fmt_sb (fm: format) : int429ensures { result = sb fm }430= sb_v fm431
The index of a float, and the float of an index
Valid (46ms) (colibri2)let index_f (x: t) : int434requires { is_not_nan x }435ensures { result = index x }436= index_v x Valid (46ms) (colibri2)437let of_index_f (fm: format) (i: int) : t438requires { - nb_sign fm <= i < nb_sign fm }439ensures { result = of_index fm i }440= of_index_v fm i441Valid (44ms) (colibri2)442let a_of_int (i: int) : A.t443ensures { A.real result = from_int i }444= A.of_bigint i Valid (43ms) (colibri2)445let a_neg (a: A.t) : A.t446ensures { A.real result = -. A.real a }447= A.neg a448
A rational n / 2^k of A as (n, -k)
Valid (65ms) (colibri2)let a_dyadic (a: A.t) : option (int, int)451ensures { match result with452| Some (n, e) -> A.real a = from_int n *. pow2r e453| None -> true end }454= match A.view a with455| A.Irr -> None456| A.Rat q -> QB.dyadic q457end Valid (41ms) (colibri2)458let a_ceil (a: A.t) : int459ensures { result = ceil (A.real a) }460= A.ceil_z a Valid (38ms) (colibri2)461let a_floor (a: A.t) : int462ensures { result = floor (A.real a) }463= A.floor_z a Valid (42ms) (colibri2)464let a_le (a b: A.t) : bool465ensures { result <-> A.real a <=. A.real b }466= A.le a b467
The special floats of a format: –inf, +inf, –0, +0 (F.get_special_values)
predicate consts_ok (fm: format) (c: (t, t, t, t)) =471let (minf, pinf, nz, pz) = c in472fmt minf = fm /\ fmt pinf = fm /\ fmt nz = fm /\ fmt pz = fm /\473specials4 fm minf pinf nz pz474Valid (370ms) (colibri2)475let consts (fm: format) : (t, t, t, t)476ensures { consts_ok fm result }477= {proof…} FpInterval.format_facts fm (); {qed}478(IE.minf fm, IE.pinf fm, IE.at_i fm (-1), IE.at_i fm 0)479
The bounds of the positive subnormals and normals of a format: the first and the last subnormal, the first and the last normal (F.get_special_values)
predicate classes_ok (fm: format) (c: (t, t, t, t)) =484let (sf, sl, nf, nl) = c in485at_index fm sf 1 /\ at_index fm sl (power 2 (sb fm - 1) - 1) /\486at_index fm nf (power 2 (sb fm - 1)) /\ at_index fm nl (nb_sign fm - 2)487Valid (370ms) (colibri2)488let classes (fm: format) : (t, t, t, t)489ensures { classes_ok fm result }490= {proof…} FpInterval.format_facts fm (); {qed}491let h = binade_v fm in492(IE.at_i fm 1, IE.at_i fm (h - 1), IE.at_i fm h, IE.at_i fm (nb_sign_v fm - 2))493
The bounds of x when x + y rounds into [lo, hi], in any mode (Intf.add_bounds, proved in fbin.mlw, AddBound)
Valid (364ms) (colibri2 2) (split_vc) (depth 1)let add_bounds (lo hi: t) : option (t, t)497ensures { match result with498| Some (a, b) -> fmt a = fmt lo /\ fmt b = fmt lo /\499forall m x y. fmt x = fmt lo -> fmt y = fmt lo ->500le_dz lo (fp_add m x y) -> le_dz (fp_add m x y) hi ->501le_dz a x /\ le_dz x b502| None -> true503end }504= {proof…}505assert { forall m x y [fp_add m x y]. fp_add m x y = fp_add_i m x y };506{qed}507Fp.add_bounds lo hi508end509