library colibrilib.fp_conv — module RealDomThe implementations of Env.getr, Env.getc, Env.updr and Env.updc, with the same specifications, on the trusted getu and updu that read and write the domain with its proved type (UnionCongr.t of colibrilib/union_congr.mlw): the extraction (fp_conv.drv) maps the four val of Env to them. A separate module, so that the proofs that use Env do not have union.mlw in their context.
module RealDom520use int.Int521use option.Option522use list.List523use real.RealInfix524use real.FromInt525use colibrilib.ring.Atom526use colibrilib.stda.StdA as A527use colibrilib.stdq.StdQ as Q528use colibrilib.bound.Bound as B529use colibrilib.union.Union as U530use colibrilib.congruence.Congruence as C531use colibrilib.union_congr.UnionCongr as UC532use colibrilib.dv.Dv as Dv533use Env534
Egraph.get_dom of the domain of the reals (Dom_interval.dom)
val getu (d: envp 'm) (n:Atom.t) : option UC.t537ensures { match result with538| Some v -> (live d -> UC.mem (d.mr n) v) /\ forall x. d.ri n x -> UC.mem x v539| None -> true540end }541
Dom_interval.upd_dom: the intersection with the domain of n
val updu (d:env) (n:Atom.t) (v:UC.t) : unit544requires { live d -> UC.mem (d.mr n) v }545writes { d.state }546ensures { (forall x. old d.ri n x -> UC.mem x v) -> d.ri = old d.ri /\ d.dy = old d.dy }547Valid (114ms) (colibri2)548let bnd_of (b: U.Make.Map.qbound) : bnd549ensures { forall x. U.Make.Map.cmp_inf_qbound b x <-> rmem_lo x result }550ensures { forall x. U.Make.Map.cmp_sup_qbound x b <-> rmem_hi x result }551= match b with552| U.Make.Map.BInf -> BInf553| U.Make.Map.BLarge q -> BLarge q554| U.Make.Map.BStrict q -> BStrict q555end556Valid (86ms) (colibri2)557let rec rapp (l1 l2: rdom) : rdom558variant { l1 }559ensures { forall x. rmem x result <-> rmem x l1 \/ rmem x l2 }560= match l1 with Nil -> l2 | Cons i l -> Cons i (rapp l l2) end561
The intervals of u
Valid (783ms) (colibri2)let to_rdom (u: U.Make.t) : rdom564ensures { forall x. U.Make.memt x u -> rmem x result }565= let predicate inv (x: real) (l: rdom) = pure { rmem x l } in566let f (i: U.Make.Map.interval) : rdom567ensures { forall x. U.Make.Map.mem_interval x i -> inv x result }568= match i with569| U.Make.Map.Singleton q -> Cons (RSing q) Nil570| U.Make.Map.Inter lo hi -> Cons (RInter (bnd_of lo) (bnd_of hi)) Nil571end in572let union (a b: rdom) : rdom573ensures { forall x. inv x a \/ inv x b -> inv x result }574= rapp a b in575U.Make.Map.UnaryFold.map { U.Make.Map.UnaryFold.f = f; U.Make.Map.UnaryFold.union = union;576U.Make.Map.UnaryFold.inv = inv } u577Valid (159ms) (colibri2)578let hull (lo hi: bnd) : U.Make.convex_hull579ensures { forall x. rmem_lo x lo /\ rmem_hi x hi <-> U.Make.in_hull x result }580= let l = match lo with581| BInf -> None | BLarge q -> Some (q, B.Large) | BStrict q -> Some (q, B.Strict) end in582let h = match hi with583| BInf -> None | BLarge q -> Some (q, B.Large) | BStrict q -> Some (q, B.Strict) end in584(l, h)585Valid (362ms) (colibri2)586let of_riv (i: riv) : option UC.t587ensures { match result with588| Some v -> forall x. rmem_iv x i -> UC.mem x v589| None -> forall x. not rmem_iv x i590end }591= match i with592| RSing q -> Some (UC.singleton q)593| RInter lo hi -> UC.from_convex_hull (hull lo hi)594end595
The domain of the reals of a list of intervals (None: empty)
Valid (129ms) (colibri2)let rec of_rdom (l: rdom) : option UC.t598variant { l }599ensures { match result with600| Some v -> forall x. rmem x l -> UC.mem x v601| None -> forall x. not rmem x l602end }603= match l with604| Nil -> None605| Cons i l' ->606match of_riv i, of_rdom l' with607| None, o -> o608| o, None -> o609| Some a, Some b -> Some (UC.union a b)610end611end612Valid (76ms) (colibri2)613let getr (d: envp 'm) (n:Atom.t) : option rdom614ensures { match result with615| Some v -> (live d -> rmem (d.mr n) v) /\ forall x. d.ri n x -> rmem x v616| None -> true617end }618= match getu d n with None -> None | Some v -> Some (to_rdom v.UC.u) end619Valid (352ms) (colibri2 6) (split_vc 3) (depth 2)620let getc (d: envp 'm) (n:Atom.t) : ocls621ensures { match result with622| Cls dv rm ->623(live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv) /\624forall x. d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv625| NoCls -> true626end }627= match getu d n with628| Some v -> match v.UC.c with629| Some cc ->630let dv = A.of_q cc.C.div in631let rm = cc.C.rem in632{proof…}633let lemma pt (x: real) : unit634requires { C.member x cc }635ensures { exists k: int. x = A.real rm +. from_int k *. A.real dv }636= let k = Dv.quot (x -. A.real rm) (Q.real cc.C.div) in637assert { x = A.real rm +. from_int k *. A.real dv } in638{qed}639mk_cls d n dv rm640| None -> NoCls641end642| None -> NoCls643end644Valid (1.2s) (colibri2 7) (split_vc) (depth 1)645let updc (d:env) (n:Atom.t) (dv rm: A.t) : unit646requires { live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv }647writes { d.state }648ensures { (dropped dv \/649forall x. old d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv) ->650d.ri = old d.ri /\ d.dy = old d.dy }651= if not (c_dropped dv) then652match A.view dv with653| A.Rat q ->654let c = UC.of_congruence { C.div = q; C.rem = rm } in655match getu d n with656| Some i -> if not (UC.is_included i c) then updu d n c657| None -> updu d n c658end659| A.Irr -> ()660end661Valid (699ms) (colibri2)662let updr (d:env) (n:Atom.t) (v:rdom) : unit663requires { live d -> rmem (d.mr n) v }664writes { d.state }665ensures { (forall x. old d.ri n x -> rmem x v) -> d.ri = old d.ri /\ d.dy = old d.dy }666= match of_rdom v with667| None -> contradiction d668| Some u -> updu d n u669end670end671