library colibrilib.fp_conv — module DolmenA copy of the constructors of Dolmen_std.Builtin.t (and of the builtins of colibri2 RealValue.Builtin and Fp_value.Builtin) of the terms that Conv.view reads, and their meaning in the model, as in SMT–LIB. The extraction maps each constructor to the Dolmen one (colibri2/theories/FP/fp_conv.drv), in patterns too: the trusted part is this list of names and the meanings (sem_in), not a translation in OCaml. The constructor Other stands for all the other builtins (the Dolmen type is extensible): it is never built, so a match always keeps a wildcard. The integers are the ones of Dolmen: Fp_add (e, p) is the format of e bits of exponent and p of significand (the hidden bit included); Sbv_to_fp (n, e, p) converts a bit–vector of n bits, To_sbv (e, p, n) converts to one.
module Dolmen4882use int.Int4883use int.Power4884use real.RealInfix4885use real.FromInt4886use list.List4887use option.Option4888use mach.int.Int634889use colibrilib.ring.Atom4890use colibrilib.fbin.Fp4891use colibrilib.stda.StdA as A4892use Env4893use RealConv4894use BvConv4895use colibrilib.fp_interval.Intervals4896use colibrilib.fp_interval.FpInterval4897use Rules4898use GTerm4899
The arithmetic of +, -, *, - (unary): Int , Rat , Real `
type arith = AInt | ARat | AReal4903
The sorts of the division of Dolmen
type darith = DRat | DReal49064907type builtin =4908| Fp_add int63 int634909| Fp_sub int63 int634910| Fp_mul int63 int634911| Fp_div int63 int634912| Fp_sqrt int63 int634913| Fp_roundToIntegral int63 int634914| Fp_to_fp int63 int63 int63 int634915| Ieee_format_to_fp int63 int634916| Fp int63 int634917| Sbv_to_fp int63 int63 int634918| Ubv_to_fp int63 int63 int634919| To_sbv int63 int63 int634920| To_ubv int63 int63 int634921| Fp_abs int63 int634922| Fp_neg int63 int634923| Fp_min int63 int634924| Fp_max int63 int634925| Fp_leq int63 int634926| Fp_lt int63 int634927| Fp_eq int63 int634928| Fp_geq int63 int634929| Fp_gt int63 int634930| Fp_isNaN int63 int634931| Fp_isNormal int63 int634932| Fp_isSubnormal int63 int634933| Fp_isZero int63 int634934| Fp_isInfinite int63 int634935| Fp_isNegative int63 int634936| Fp_isPositive int63 int634937| Fp_isFinite int63 int634938| To_real int63 int634939| Real_to_fp int63 int634940| Add arith4941| Sub arith4942| Mul arith4943| Minus arith4944| Div darith4945| Bitv_to_int int63 bool4946| Other4947
The format of e bits of exponent and p of significand
predicate isfmt (fm: format) (e p: int63) = eb fm = to_int e /\ sb fm = to_int p4950
The number of bits of a bit–vector node, from its type: it does not depend on the model
function bvsize (n: Atom.t) : int4954
The integer of the bits b of a bit–vector of n bits, in two's complement
function sbv (n b: int) : int =4958if power 2 (n - 1) <= b then b - power 2 n else b4959
The bit–vector node x of n bits: its real is its unsigned integer b (as RealValue checks it in the model)
predicate bv_val (d: envp 'm) (x: Atom.t) (n b: int) =4963bvsize x = n /\ d.mr x = from_int b /\ 0 <= b < power 2 n4964
A propagator that holds when the environment is live
predicate sp (d: envp 'm) (p: prop) = wf p /\ (live d -> holds d p)4967
The meaning of the term b l of node r in the model of d, as in SMT–LIB. fp.sub is fp.add of the opposite (IEEE 754 §6.3). The conversion fp.to_sbv (resp. fp.to_ubv) is the integral rounding when it is finite and fits in the bit–vectors, unspecified otherwise. fp is the float of the concatenation of its three bit–vectors (sign, exponent, significand). A meaning on other arguments is true
predicate sem_in (d: envp 'm) (b: builtin) (r: Atom.t) (l: list Atom.t) =4975match b with4976| Fp_add e p ->4977match l with4978| Cons m (Cons x (Cons y Nil)) ->4979forall fm. isfmt fm e p -> sp d (Bin OAdd fm r m x y)4980| _ -> true4981end4982| Fp_mul e p ->4983match l with4984| Cons m (Cons x (Cons y Nil)) ->4985forall fm. isfmt fm e p -> sp d (Bin OMul fm r m x y)4986| _ -> true4987end4988| Fp_div e p ->4989match l with4990| Cons m (Cons x (Cons y Nil)) ->4991forall fm. isfmt fm e p -> sp d (Bin ODiv fm r m x y)4992| _ -> true4993end4994| Fp_sub e p ->4995match l with4996| Cons m (Cons x (Cons y Nil)) ->4997forall fm. isfmt fm e p ->4998fmt_of r = fm /\ fmt_of x = fm /\ fmt_of y = fm /\4999(live d -> fmt (d.mf r) = fm /\ fmt (d.mf x) = fm /\ fmt (d.mf y) = fm /\5000d.mf r = fp_add (d.mm m) (d.mf x) (neg (d.mf y)))5001| _ -> true5002end5003| Fp_sqrt e p ->5004match l with5005| Cons m (Cons x Nil) ->5006forall fm. isfmt fm e p -> sp d (Un USqrt fm r m x)5007| _ -> true5008end5009| Fp_roundToIntegral e p ->5010match l with5011| Cons m (Cons x Nil) ->5012forall fm. isfmt fm e p -> sp d (Un URti fm r m x)5013| _ -> true5014end5015| Fp_to_fp e p e' p' ->5016match l with5017| Cons m (Cons x Nil) ->5018forall fm fm'. isfmt fm e p -> isfmt fm' e' p' -> sp d (Cvt fm fm' r m x)5019| _ -> true5020end5021| Fp_abs e p ->5022match l with5023| Cons x Nil ->5024forall fm. isfmt fm e p -> sp d (Abs fm r x)5025| _ -> true5026end5027| Fp_neg _ _ ->5028match l with5029| Cons x Nil ->5030sp d (Neg r x)5031| _ -> true5032end5033| Fp_min _ _ ->5034match l with5035| Cons x (Cons y Nil) ->5036fmt_of r = fmt_of x /\ fmt_of y = fmt_of x /\5037(live d -> d.mf r = min (d.mf x) (d.mf y))5038| _ -> true5039end5040| Fp_max _ _ ->5041match l with5042| Cons x (Cons y Nil) ->5043fmt_of r = fmt_of x /\ fmt_of y = fmt_of x /\5044(live d -> d.mf r = max (d.mf x) (d.mf y))5045| _ -> true5046end5047| Fp_leq e p ->5048match l with5049| Cons x (Cons y Nil) ->5050forall fm. isfmt fm e p -> sp d (Cmp CLe fm r x y)5051| _ -> true5052end5053| Fp_lt e p ->5054match l with5055| Cons x (Cons y Nil) ->5056forall fm. isfmt fm e p -> sp d (Cmp CLt fm r x y)5057| _ -> true5058end5059| Fp_eq e p ->5060match l with5061| Cons x (Cons y Nil) ->5062forall fm. isfmt fm e p -> sp d (Cmp CEq fm r x y)5063| _ -> true5064end5065| Fp_geq e p ->5066match l with5067| Cons x (Cons y Nil) ->5068forall fm. isfmt fm e p -> sp d (Cmp CLe fm r y x)5069| _ -> true5070end5071| Fp_gt e p ->5072match l with5073| Cons x (Cons y Nil) ->5074forall fm. isfmt fm e p -> sp d (Cmp CLt fm r y x)5075| _ -> true5076end5077| Fp_isNaN e p ->5078match l with5079| Cons x Nil ->5080forall fm. isfmt fm e p -> sp d (Is INaN fm r x)5081| _ -> true5082end5083| Fp_isNormal e p ->5084match l with5085| Cons x Nil ->5086forall fm. isfmt fm e p -> sp d (Is INormal fm r x)5087| _ -> true5088end5089| Fp_isSubnormal e p ->5090match l with5091| Cons x Nil ->5092forall fm. isfmt fm e p -> sp d (Is ISubnormal fm r x)5093| _ -> true5094end5095| Fp_isZero e p ->5096match l with5097| Cons x Nil ->5098forall fm. isfmt fm e p -> sp d (Is IZero fm r x)5099| _ -> true5100end5101| Fp_isInfinite e p ->5102match l with5103| Cons x Nil ->5104forall fm. isfmt fm e p -> sp d (Is IInf fm r x)5105| _ -> true5106end5107| Fp_isNegative e p ->5108match l with5109| Cons x Nil ->5110forall fm. isfmt fm e p -> sp d (Is INeg fm r x)5111| _ -> true5112end5113| Fp_isPositive e p ->5114match l with5115| Cons x Nil ->5116forall fm. isfmt fm e p -> sp d (Is IPos fm r x)5117| _ -> true5118end5119| Fp_isFinite e p ->5120match l with5121| Cons x Nil ->5122forall fm. isfmt fm e p -> sp d (Is IFinite fm r x)5123| _ -> true5124end5125| To_real e p ->5126match l with5127| Cons x Nil ->5128forall fm. isfmt fm e p -> sp d (ToReal fm r x)5129| _ -> true5130end5131| Real_to_fp e p ->5132match l with5133| Cons m (Cons x Nil) ->5134forall fm. isfmt fm e p -> sp d (OfReal fm r m x)5135| _ -> true5136end5137| Ieee_format_to_fp e p ->5138match l with5139| Cons x Nil ->5140forall fm. isfmt fm e p -> fmt_of r = fm /\ bvsize x = to_int e + to_int p /\5141(live d -> exists b. bv_val d x (to_int e + to_int p) b /\ of_bits fm b (d.mf r))5142| _ -> true5143end5144| Fp e p ->5145match l with5146| Cons s (Cons x (Cons y Nil)) ->5147forall fm. isfmt fm e p -> fmt_of r = fm /\5148(live d -> exists bs bx bm.5149bv_val d s 1 bs /\ bv_val d x (to_int e) bx /\ bv_val d y (to_int p - 1) bm /\5150of_bits fm (bs * power 2 (to_int e + to_int p - 1) +5151bx * power 2 (to_int p - 1) + bm) (d.mf r))5152| _ -> true5153end5154| Sbv_to_fp n e p ->5155match l with5156| Cons m (Cons x Nil) ->5157forall fm. isfmt fm e p -> fmt_of r = fm /\ bvsize x = to_int n /\5158(live d -> exists b. bv_val d x (to_int n) b /\5159d.mf r = round_x fm (d.mm m) (from_int (sbv (to_int n) b)))5160| _ -> true5161end5162| Ubv_to_fp n e p ->5163match l with5164| Cons m (Cons x Nil) ->5165forall fm. isfmt fm e p -> fmt_of r = fm /\ bvsize x = to_int n /\5166(live d -> exists b. bv_val d x (to_int n) b /\5167d.mf r = round_x fm (d.mm m) (from_int b))5168| _ -> true5169end5170| To_sbv e p n ->5171match l with5172| Cons m (Cons x Nil) ->5173forall fm. isfmt fm e p -> fmt_of x = fm /\ bvsize r = to_int n /\5174(live d -> fmt (d.mf x) = fm /\ exists b. bv_val d r (to_int n) b /\5175let y = fp_rti (d.mm m) (d.mf x) in5176is_not_nan y /\ not (is_inf y) /\5177from_int (- power 2 (to_int n - 1)) <=. to_real y <=.5178from_int (power 2 (to_int n - 1) - 1) ->5179from_int (sbv (to_int n) b) = to_real y)5180| _ -> true5181end5182| To_ubv e p n ->5183match l with5184| Cons m (Cons x Nil) ->5185forall fm. isfmt fm e p -> fmt_of x = fm /\ bvsize r = to_int n /\5186(live d -> fmt (d.mf x) = fm /\ exists b. bv_val d r (to_int n) b /\5187let y = fp_rti (d.mm m) (d.mf x) in5188is_not_nan y /\ not (is_inf y) /\51890.0 <=. to_real y <=. from_int (power 2 (to_int n) - 1) ->5190from_int b = to_real y)5191| _ -> true5192end5193| Bitv_to_int n s ->5194match l with5195| Cons x Nil ->5196bvsize x = to_int n ->5197(live d -> exists b. bv_val d x (to_int n) b /\5198d.mr r = from_int (if s then sbv (to_int n) b else b))5199| _ -> true5200end5201| Add _ ->5202match l with5203| Cons x (Cons y Nil) ->5204sp d (RBin RAdd r x y)5205| _ -> true5206end5207| Sub _ ->5208match l with5209| Cons x (Cons y Nil) ->5210sp d (RBin RSub r x y)5211| _ -> true5212end5213| Mul _ ->5214match l with5215| Cons x (Cons y Nil) ->5216sp d (RBin RMul r x y)5217| _ -> true5218end5219| Minus _ ->5220match l with5221| Cons x Nil ->5222sp d (RNeg r x)5223| _ -> true5224end5225| Div _ ->5226(* the division by zero is unspecified *)5227match l with5228| Cons x (Cons y Nil) ->5229live d -> d.mr y <> 0.0 -> d.mr r = d.mr x /. d.mr y5230| _ -> true5231end5232| _ -> true5233end5234
The meaning in every model
predicate means (b: builtin) (r: Atom.t) (l: list Atom.t) =5237(forall d: env. sem_in d b r l) /\ (forall d: envp ro. sem_in d b r l)5238
The meaning in d (its formats and sizes do not depend on d)
Valid (66ms) (colibri2)let ghost means_at (d: env) (b: builtin) (r: Atom.t) (l: list Atom.t) : unit5241requires { means b r l }5242ensures { sem_in d b r l }5243= ()5244
A propagator that follows from the meaning of three terms is valid
Valid (327ms) (colibri2 10) (split_vc 3) (depth 2)let ghost valid_of (d0: env) (b1: builtin) (r1: Atom.t) (l1: list Atom.t)5247(b2: builtin) (r2: Atom.t) (l2: list Atom.t)5248(b3: builtin) (r3: Atom.t) (l3: list Atom.t) (p: prop) : unit5249requires { means b1 r1 l1 /\ means b2 r2 l2 /\ means b3 r3 l3 }5250requires { forall d: env.5251sem_in d b1 r1 l1 -> sem_in d b2 r2 l2 -> sem_in d b3 r3 l3 -> sp d p }5252requires { forall d: envp ro.5253sem_in d b1 r1 l1 -> sem_in d b2 r2 l2 -> sem_in d b3 r3 l3 -> sp d p }5254ensures { valid p }5255= {proof…}5256assert { sp d0 p by sem_in d0 b1 r1 l1 /\ sem_in d0 b2 r2 l2 /\ sem_in d0 b3 r3 l3 };5257assert { forall d: env. live d -> holds d p5258by sem_in d b1 r1 l1 /\ sem_in d b2 r2 l2 /\ sem_in d b3 r3 l3 };5259assert { forall d: envp ro. live d -> holds d p5260by sem_in d b1 r1 l1 /\ sem_in d b2 r2 l2 /\ sem_in d b3 r3 l3 }5261{qed}5262
The integer of the concatenation of the bit–vectors of the sign, the exponent and the significand is an encoding
Valid (389ms) (colibri2 5) (split_vc) (depth 1)let ghost concat_range (e p bs bx bm: int) : unit5266requires { 0 <= e /\ 1 <= p }5267requires { 0 <= bs < 2 /\ 0 <= bx < power 2 e /\ 0 <= bm < power 2 (p - 1) }5268ensures { 0 <= bs * power 2 (e + p - 1) + bx * power 2 (p - 1) + bm < power 2 (e + p) }5269= {proof…}5270assert { power 2 (e + p - 1) = power 2 e * power 2 (p - 1) };5271assert { power 2 (e + p) = 2 * power 2 (e + p - 1) };5272assert { bx * power 2 (p - 1) <= (power 2 e - 1) * power 2 (p - 1) };5273assert { bs * power 2 (e + p - 1) <= power 2 (e + p - 1) }5274{qed}5275
The propagator of fp s x y, on the node n of the integer of the concatenation
Valid (1.3s) (colibri2 23) (split_vc 5) (depth 2)let ghost concat_valid (d0: env) (fm: format) (e p: int) (bi: builtin)5279(r s x y n: Atom.t) : unit5280requires { means bi r (Cons s (Cons x (Cons y Nil))) }5281requires { match bi with5282| Fp e' p' -> to_int e' = e /\ to_int p' = p /\ isfmt fm e' p'5283| _ -> false end }5284requires { live d0 -> forall d: env. model_of d = model_of d0 ->5285d.mr n = d.mr s *. from_int (power 2 (e + p - 1)) +.5286d.mr x *. from_int (power 2 (p - 1)) +. d.mr y }5287requires { live d0 -> forall d: envp ro. model_of d = model_of d0 ->5288d.mr n = d.mr s *. from_int (power 2 (e + p - 1)) +.5289d.mr x *. from_int (power 2 (p - 1)) +. d.mr y }5290ensures { valid_at (model_of d0) (live d0) (OfBits fm r n false) }5291= {proof…}5292let l = Cons s (Cons x (Cons y Nil)) in5293assert { 2 * half_bits fm = power 2 (e + p) };5294let lemma enc_rw (d: env)5295requires { live d0 /\ model_of d = model_of d0 }5296requires { d.mr n = d.mr s *. from_int (power 2 (e + p - 1)) +.5297d.mr x *. from_int (power 2 (p - 1)) +. d.mr y }5298ensures { holds d (OfBits fm r n false) }5299= assert { d.mf = d0.mf /\ d.mr = d0.mr /\ sem_in d0 bi r l };5300let (bs, bx, bm) = any (int, int, int) ensures { let (bs, bx, bm) = result in5301bv_val d0 s 1 bs /\ bv_val d0 x e bx /\ bv_val d0 y (p - 1) bm /\5302of_bits fm (bs * power 2 (e + p - 1) + bx * power 2 (p - 1) + bm) (d.mf r) } in5303concat_range e p bs bx bm;5304let v = bs * power 2 (e + p - 1) + bx * power 2 (p - 1) + bm in5305assert { from_int v = from_int bs *. from_int (power 2 (e + p - 1)) +.5306from_int bx *. from_int (power 2 (p - 1)) +. from_int bm };5307assert { d.mr n = from_int v };5308assert { 0 <= v < 2 * half_bits fm }5309in5310let lemma enc_ro (d: envp ro)5311requires { live d0 /\ model_of d = model_of d0 }5312requires { d.mr n = d.mr s *. from_int (power 2 (e + p - 1)) +.5313d.mr x *. from_int (power 2 (p - 1)) +. d.mr y }5314ensures { holds d (OfBits fm r n false) }5315= assert { d.mf = d0.mf /\ d.mr = d0.mr /\ sem_in d0 bi r l };5316let (bs, bx, bm) = any (int, int, int) ensures { let (bs, bx, bm) = result in5317bv_val d0 s 1 bs /\ bv_val d0 x e bx /\ bv_val d0 y (p - 1) bm /\5318of_bits fm (bs * power 2 (e + p - 1) + bx * power 2 (p - 1) + bm) (d.mf r) } in5319concat_range e p bs bx bm;5320let v = bs * power 2 (e + p - 1) + bx * power 2 (p - 1) + bm in5321assert { from_int v = from_int bs *. from_int (power 2 (e + p - 1)) +.5322from_int bx *. from_int (power 2 (p - 1)) +. from_int bm };5323assert { d.mr n = from_int v };5324assert { 0 <= v < 2 * half_bits fm }5325in5326assert { sem_in d0 bi r l };5327assert { live d0 -> forall d: env. model_of d = model_of d0 ->5328holds d (OfBits fm r n false) };5329assert { live d0 -> forall d: envp ro. model_of d = model_of d0 ->5330holds d (OfBits fm r n false) }5331{qed}5332
The Dolmen builtin and the arguments of a ground term without type arguments (Ground.sem): its node has the meaning of the term in every model
val sem (g: ground) : option (builtin, list Atom.t)5337ensures { match result with5338| Some (b, l) -> means b (gnode g) l5339| None -> true end }5340
A term constant of colibri2 (Expr.Term.Const.t, a record of Dolmen) and its Dolmen builtin (its field builtin)
type cst = private { builtin: builtin }5344
Expr.Term.Const.Float.neg, add, mul, roundToIntegral, real_to_fp, to_real of a format, RealValue.Builtin.bv_to_int
val cst_neg (e p: int63) : cst ensures { result.builtin = Fp_neg e p }5348val cst_add (e p: int63) : cst ensures { result.builtin = Fp_add e p }5349val cst_mul (e p: int63) : cst ensures { result.builtin = Fp_mul e p }5350val cst_rti (e p: int63) : cst ensures { result.builtin = Fp_roundToIntegral e p }5351val cst_real_to_fp (e p: int63) : cst ensures { result.builtin = Real_to_fp e p }5352val cst_to_real (e p: int63) : cst ensures { result.builtin = To_real e p }5353val cst_radd () : cst ensures { result.builtin = Add AReal }5354val cst_rmul () : cst ensures { result.builtin = Mul AReal }5355val cst_rdiv () : cst ensures { result.builtin = Div DReal }5356val cst_bv_to_int (n: int63) (s: bool) : cst5357ensures { result.builtin = Bitv_to_int n s }5358
The arguments of the floats and of the bit–vectors of apply have the types of the builtin
predicate well_typed (b: builtin) (l: list Atom.t) =5362match b with5363| Fp_neg e p | To_real e p ->5364match l with5365| Cons x Nil -> eb (fmt_of x) = to_int e /\ sb (fmt_of x) = to_int p5366| _ -> false5367end5368| Fp_roundToIntegral e p ->5369match l with5370| Cons _ (Cons x Nil) -> eb (fmt_of x) = to_int e /\ sb (fmt_of x) = to_int p5371| _ -> false5372end5373| Fp_add e p | Fp_mul e p ->5374match l with5375| Cons _ (Cons x (Cons y Nil)) ->5376eb (fmt_of x) = to_int e /\ sb (fmt_of x) = to_int p /\ fmt_of y = fmt_of x5377| _ -> false5378end5379| Real_to_fp _ _ ->5380match l with Cons _ (Cons _ Nil) -> true | _ -> false end5381| Add _ | Mul _ | Div _ ->5382match l with Cons _ (Cons _ Nil) -> true | _ -> false end5383| Bitv_to_int n _ ->5384match l with Cons x Nil -> bvsize x = to_int n | _ -> false end5385| _ -> false5386end5387
Ground.apply' (no type arguments, not registered): the node of the term c l
val apply (d: env) (c: cst) (l: list Atom.t) : Atom.t5391requires { well_typed c.builtin l }5392ensures { means c.builtin result l }5393
The node of the float x (Fp_value)
val float_node (fm: format) (x: t) : Atom.t5396requires { fmt x = fm }5397ensures { fmt_of result = fm }5398ensures { forall d: env. live d -> d.mf result = x }5399ensures { forall d: envp ro. live d -> d.mf result = x }5400
RealValue.get: the value of a real node in the e–graph, if it is known
val real_value (d: envp 'm) (n: Atom.t) : option A.t5404ensures { match result with5405| Some v -> live d -> d.mr n = A.real v5406| None -> true end }5407
The node of the real constant v (RealValue.cst)
val real_cst (v: A.t) : Atom.t5410ensures { forall d: env. d.mr result = A.real v }5411ensures { forall d: envp ro. d.mr result = A.real v }5412
sum k_i x_i
function lsum (d: envp 'm) (l: list (Atom.t, A.t)) : real =5415match l with5416| Nil -> 0.05417| Cons (x, k) l -> A.real k *. d.mr x +. lsum d l5418end5419
The node of the linear term sum k_i x_i (Dom_polynome), not registered
val real_lin (d: env) (l: list (Atom.t, A.t)) : Atom.t5423writes { d.state }5424ensures { forall d: env. live d -> d.mr result = lsum d l }5425ensures { forall d: envp ro. live d -> d.mr result = lsum d l }5426end5427