library colibrilib.union — module ExportWhat OCaml calls: the contracts of Union.Make. Records built in OCaml (reducer, fmap) have their invariants trusted: only the fields that are not ghost exist there.
module Export4047use int.Int4048use bool.Bool4049use option.Option4050use colibrilib.bound.Bound4051use real.RealInfix4052use colibrilib.stda.StdA as Q4053use colibrilib.q.Real as Real4054use real.Square4055use real.MinMax4056use colibrilib.spec.Sound4057use colibrilib.spec.Opt4058use colibrilib.spec.Test4059use colibrilib.q.Ord as Ord4060use real.Abs4061use real.Truncate4062use real.FromInt4063use list.List4064use Union4065import Make4066import Make.Increasing4067import Make.Increasing.Unary4068import Make.Increasing.Binary4069import Make.NonIncreasing4070import Make.IsComparable4071import Make.Map4072import Make.ED4073Valid (32ms) (colibri2)4074let singleton (q:Q.t) : t4075ensures { exact memt (fun (x:real) -> x = q) result }4076= Make.singleton q4077Valid (40ms) (colibri2)4078let is_singleton (u:t) : (option Q.t, ghost real, ghost real)4079ensures {4080let (o,x1,x2) = result in4081match o with4082| Some q -> forall x:real. mem x u.a <-> x = q4083| None -> x1 <> x2 /\ mem x1 u.a /\ mem x2 u.a4084end4085}4086= Make.is_singleton u4087Valid (28ms) (colibri2)4088let inter (u:t) (v:t) : option t4089ensures { exact_opt memt (fun (x:real) -> memt x u /\ memt x v) result }4090ensures {4091match result with4092| None -> true4093| Some w ->4094le_sup_infr (le_min_sup_infr (infr_bound u.a) (infr_bound v.a)) (infr_bound w.a)4095end4096}4097= Make.inter u v4098Valid (33ms) (colibri2)4099let union (u:t) (v:t) : t4100ensures { exact memt (fun (x:real) -> memt x u \/ memt x v) result }4101= Make.union u v4102Valid (29ms) (colibri2)4103let mem (x:Q.t) (l:t)4104ensures { decides (memt x.Q.real l) result }4105= Make.mem x l4106Valid (32ms) (colibri2)4107let except l x4108ensures {4109match result with4110| Some res -> forall q. (mem q l.a /\ q <> x.Q.real) <-> mem q res.a4111| None -> forall q. mem q l.a <-> q = x.Q.real4112end4113}4114= Make.except l x4115Valid (30ms) (colibri2)4116let complement l4117ensures { exact_opt memt (fun (x:real) -> not (memt x l)) result }4118= Make.complement l4119Valid (24ms) (colibri2)4120let for_all test t1 t24121ensures { result -> (forall q. test (mem q t1.a) (mem q t2.a)) }4122= Make.for_all test t1 t24123Valid (39ms) (colibri2)4124let is_included t1 t24125ensures { result -> (forall q. (mem q t1.a) -> (mem q t2.a)) }4126= Make.is_included t1 t24127Valid (40ms) (colibri2)4128let gt (q:Q.t)4129ensures { exact memt (fun (x:real) -> q <. x) result }4130= Make.gt q4131Valid (30ms) (colibri2)4132let lt (q:Q.t)4133ensures { exact memt (fun (x:real) -> x <. q) result }4134= Make.lt q4135Valid (31ms) (colibri2)4136let ge (q:Q.t)4137ensures { exact memt (fun (x:real) -> q <=. x) result }4138ensures { R q = infr_bound result.a }4139= Make.ge q4140Valid (22ms) (colibri2)4141let le (q:Q.t)4142ensures { exact memt (fun (x:real) -> x <=. q) result }4143= Make.le q4144Valid (22ms) (colibri2)4145let le' (u:t)4146ensures { sound_rel memt (<=.) u result }4147= Make.le' u4148Valid (32ms) (colibri2)4149let lt' (u:t)4150ensures { sound_rel memt (<.) u result }4151= Make.lt' u4152Valid (28ms) (colibri2)4153let gt' (u:t)4154ensures { sound_rel memt (>.) u result }4155= Make.gt' u4156Valid (32ms) (colibri2)4157let ge' (u:t)4158ensures { sound_rel memt (>=.) u result }4159= Make.ge' u4160Valid (30ms) (colibri2)4161let is_comparable (t1:t) (t2:t)4162ensures { match result with4163| Gt -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 >. q24164| Lt -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 <. q24165| Ge -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 >=. q24166| Le -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 <=. q24167| Eq -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 = q24168| Uncomparable -> true4169end }4170= Make.IsComparable.is_comparable t1 t24171Valid (19ms) (colibri2)4172let from_convex_hull x : option t4173ensures { includes_opt memt (fun (q:real) -> in_hull q x) result }4174= Make.from_convex_hull x4175Valid (22ms) (colibri2)4176let get_convex_hull x : convex_hull4177ensures { includes in_hull (fun (q:real) -> memt q x) result }4178= Make.get_convex_hull x4179Valid (33ms) (colibri2)4180let neg l4181ensures { sound1 memt (fun (x:real) -> -. x) l result }4182= Make.Increasing.Unary.neg l4183Valid (24ms) (colibri2)4184let mult_cst c l4185ensures { sound1 memt (fun (x:real) -> c *. x) l result }4186= Make.Increasing.Unary.mult_cst c l4187Valid (24ms) (colibri2)4188let abs_forward (l:t) : t4189ensures { sound1 memt (fun (x:real) -> abs x) l result }4190= Make.Increasing.abs_forward l4191Valid (40ms) (colibri2)4192let abs_backward (l:t) : t4193ensures { preimage1 memt (fun (x:real) -> abs x) l result }4194= Make.Increasing.abs_backward l4195Valid (30ms) (colibri2)4196let add_cst l x4197ensures {4198forall q. (mem q l.a) <-> mem (x+.q) result.a4199}4200= Make.Increasing.Binary.add_cst l x4201Valid (36ms) (colibri2)4202let add u v: (result:t)4203ensures { sound2 memt (fun (x y:real) -> x +. y) u v result }4204= Make.Increasing.Binary.add u v4205Valid (32ms) (colibri2)4206let mul u v: (result:t)4207ensures { sound2 memt (fun x y -> x *. y) u v result }4208= Make.Increasing.Binary.mul u v4209Valid (32ms) (colibri2)4210let inv (u:t): (result:t)4211ensures { sound1 memt (fun (x:real) -> 1. /. x) u result }4212= Make.Increasing.Binary.inv u4213Valid (36ms) (colibri2)4214let div u v : t4215ensures { sound2 memt (fun (x y:real) -> x /. y) u v result }4216= Make.Increasing.Binary.div u v4217Valid (27ms) (colibri2)4218let ceil l4219ensures { sound1 memt (fun (x:real) -> from_int (ceil x)) l result }4220= Make.NonIncreasing.ceil l4221Valid (28ms) (colibri2)4222let floor l4223ensures { sound1 memt (fun (x:real) -> from_int (floor x)) l result }4224= Make.NonIncreasing.floor l4225Valid (29ms) (colibri2)4226let truncate l4227ensures { sound1 memt (fun (x:real) -> from_int (truncate x)) l result }4228= Make.NonIncreasing.truncate l4229Valid (30ms) (colibri2)4230let relu l4231ensures { sound1 memt (fun (x:real) -> max 0. x) l result }4232= Make.NonIncreasing.relu l4233Valid (39ms) (colibri2)4234let square_backward l4235ensures { preimage1_opt memt (fun (x:real) -> sqr x) l result }4236= Make.square_backward l4237Valid (35ms) (colibri2)4238let reduce_integers (l:t) : option t4239ensures { restrict memt (fun (x:real) -> Real.is_integer x) l result }4240= Make.reduce_integers l4241Valid (30ms) (colibri2)4242let div_e_forward (l1 l2:t) : t4243ensures { sound2 memt div_e_real l1 l2 result }4244= Make.ED.div_e_forward l1 l24245Valid (28ms) (colibri2)4246let mod_e_forward (l1 l2:t) : t4247ensures { sound2 memt (fun (x y:real) -> Real.mod_e x y) l1 l2 result }4248= Make.ED.mod_e_forward l1 l24249Valid (37ms) (colibri2)4250let mod_e_backward_num (num:t) (denl:t) (modl:t) : option t4251ensures { back2 memt (fun (x y:real) -> Real.mod_e x y) num denl modl result }4252= Make.ED.mod_e_backward_num num denl modl4253Valid (29ms) (colibri2)4254let div_t_forward (l1 l2:t) : t4255ensures { sound2 memt div_t_real l1 l2 result }4256= Make.ED.div_t_forward l1 l24257Valid (26ms) (colibri2)4258let mod_t_forward (l1 l2:t) : t4259ensures { sound2 memt (fun (x y:real) -> Real.mod_t x y) l1 l2 result }4260= Make.ED.mod_t_forward l1 l24261Valid (29ms) (colibri2)4262let mod_t_backward_num (num:t) (denl:t) (modl:t) : option t4263ensures { back2 memt (fun (x y:real) -> Real.mod_t x y) num denl modl result }4264= Make.ED.mod_t_backward_num num denl modl4265Valid (35ms) (colibri2)4266let div_f_forward (l1 l2:t) : t4267ensures { sound2 memt div_f_real l1 l2 result }4268= Make.ED.div_f_forward l1 l24269Valid (28ms) (colibri2)4270let mod_f_forward (l1 l2:t) : t4271ensures { sound2 memt (fun (x y:real) -> Real.mod_f x y) l1 l2 result }4272= Make.ED.mod_f_forward l1 l24273Valid (25ms) (colibri2)4274let mod_f_backward_num (num:t) (denl:t) (modl:t) : option t4275ensures { back2 memt (fun (x y:real) -> Real.mod_f x y) num denl modl result }4276= Make.ED.mod_f_backward_num num denl modl4277Valid (26ms) (colibri2)4278let reduce_generic [@requires:trusted "the caller in union.ml builds the reducer: red_min is ghost, it cannot be tested"] (op:reducer) (num:t) : option t4279requires { le_infr_bound op.red_min num.a }4280ensures { restrict memt op.red_is_in num result }4281= Make.reduce_generic op num4282Valid (31ms) (colibri2)4283let map_fold (fm:Make.Map.UnaryFold.fmap 'a) (l1:t) : 'a4284ensures { forall r1. mem r1 l1.a -> fm.Make.Map.UnaryFold.inv r1 result }4285= Make.Map.UnaryFold.map fm l14286Valid (29ms) (colibri2)4287let map_unary (fm:Make.Map.Unary.fmap) (l1:t) : t4288ensures { sound1 memt fm.Make.Map.Unary.fr l1 result }4289= Make.Map.Unary.map fm l14290end4291