library colibrilib.union — module Unionmodule Union1use int.Int2use bool.Bool3use option.Option4use colibrilib.bound.Bound5use real.RealInfix67scope Make8use colibrilib.stda.StdA as Q9use colibrilib.q.Real as Real10use real.Square111213type t'' =14| Sin Q.t t''15| Chg Q.t Bound.t t''16| Inf1718type t' =19| On t''20| Off t''2122function on (x:t') : bool = match x with On _ -> True | Off _ -> False end23function in_ (x:t') : t'' = match x with On a | Off a -> a end2425function length' (l:t'') : int =26match l with27| Sin _ l ->28length' l + 129| Chg _ _ l ->30length' l + 131| Inf -> 032end33Valid (16ms) (cvc5)34let rec lemma pos_length' (l:t'')35ensures { length' l >= 0 } =36match l with37| Sin _ l -> pos_length' l38| Chg _ _ l ->39pos_length' l40| Inf -> ()41end4243function length (l:t') : int =44match l with45| On l ->46length' l + 147| Off l ->48length' l49end5051type infr =52| R real53| I (* positive or negative infinity depending of the side *)5455predicate lt_sup (r1:infr) (r2:infr) =56match r1,r2 with57| R r1, R r2 -> r1 <. r258| I, _ -> false59| _, I -> true60end6162predicate le_sup (r1:infr) (r2:infr) =63match r1,r2 with64| R r1, R r2 -> r1 <=. r265| I, I -> true66| I, _ -> false67| _, I -> true68end6970use real.MinMax7172function min_sup (r1:infr) (r2:infr) : infr =73match r1,r2 with74| R r1, R r2 -> R (min r1 r2)75| I, I -> I76| I, _ -> r277| _, I -> r178end7980predicate r1_lt_sup (r1:real) (r2:infr) =81match r2 with82| R r2 -> r1 <. r283| I -> true84end8586function bound (l:t'') : infr =87match l with88| Sin q _ -> R q89| Chg q _ _ -> R q90| Inf -> I91end9293predicate lt_bound' (x:real) (l:t'') =94r1_lt_sup x (bound l)9596predicate lt_bound (x:real) (l:t') =97match l with98| On l -> lt_bound' x l99| Off l -> lt_bound' x l100end101102predicate le_bound' (x:real) (l:t'') =103match l with104| Sin q _ ->105x <=. q106| Chg q _ _ ->107x <=. q108| Inf -> true109end110111predicate le_bound (x:real) (l:t') =112match l with113| On l -> le_bound' x l114| Off l -> le_bound' x l115end116117118predicate le_infr (r1:infr) (r2:infr) =119match r1,r2 with120| R r1, R r2 -> r1 <=. r2121| I, _ -> true122| _, I -> true123end124125predicate lt_infr (r1:infr) (r2:infr) =126match r1,r2 with127| R r1, R r2 -> r1 <. r2128| I, _ -> true129| _, I -> true130end131132predicate le_sup_infr (r1:infr) (r2:infr) =133match r1,r2 with134| _, I -> true135| R r1, R r2 -> r1 <=. r2136| I, R _ -> false137end138139140function infr_bound' (r2:t'') : infr =141match r2 with142| Sin r1 _ | Chg r1 _ _ -> R r1143| Inf -> I144end145146function infr_bound (r2:t') : infr =147match r2 with148| On a | Off a -> infr_bound' a149end150151use real.MinMax152153function le_min_sup_infr (r1:infr) (r2:infr) : infr =154match r1,r2 with155| I, I -> I156| R r1, R r2 -> R (min r1 r2)157| R _, I -> r1158| I, R _ -> r2159end160161predicate lt_infr_bound' (r1:infr) (r2:t'') =162lt_infr r1 (infr_bound' r2)163164predicate le_infr_bound' (r1:infr) (r2:t'') =165le_infr r1 (infr_bound' r2)166167predicate le_infr_bound (r1:infr) (r2:t') =168match r2 with169| On _ -> r1 = I170| Off r2 -> le_infr_bound' r1 r2171end172173174predicate in_infr (r1:infr) (r:real) (r2:infr) =175le_infr r1 (R r) /\ le_infr (R r) r2176177178predicate ordered' (l:t'') =179match l with180| Sin q l ->181lt_bound' q l /\182ordered' l183| Chg q _ l ->184lt_bound' q l /\185ordered' l186| Inf -> true187end188189predicate ordered (l:t') =190match l with191| On l -> ordered' l192| Off l -> ordered' l193end194Valid (17ms) (cvc5)195type t = { a: t' }196invariant { ordered a }197invariant {198a <> Off Inf199}200by { a = On Inf }201202predicate cmp (x:real) (b:Bound.t) (y:real) =203match b with204| Bound.Large -> x <=. y205| Bound.Strict -> x <. y206end207208predicate mem_on (x:real) (l:t'') =209match l with210| Sin q l ->211x <. q \/ (q <. x /\ mem_on x l)212| Chg q b l ->213not (cmp q b x) \/ (cmp q b x /\ not (mem_on x l))214| Inf -> true215end216217predicate mem_if (if_:bool) (x:real) (l:t'') =218match l with219| Sin q l ->220if q <. x then mem_if if_ x l else (if if_ then x <. q else x = q)221| Chg q b l ->222if cmp q b x then mem_if (notb if_) x l else if_223| Inf -> if_224end225Valid (25ms) (cvc5)226let rec ghost mem_if_def (if_:bool) (x:real) (l:t'')227ensures { mem_if if_ x l <-> if if_ then mem_on x l else not (mem_on x l) }228variant { l } =229match l with230| Sin _ l -> mem_if_def if_ x l231| Chg _ _ l -> mem_if_def (not if_) x l232| Inf -> ()233end234235predicate mem (x:real) (l:t') =236match l with237| On l ->238mem_if True x l239| Off l ->240mem_if False x l241end242
The membership in an abstract value, for the shapes of spec.Sound
predicate memt (x:real) (u:t) = mem x u.a245246use colibrilib.spec.Sound247use colibrilib.spec.Opt248use colibrilib.spec.Test249Valid (325ms) (cvc5)250let ghost not_bottom' (if_:bool) (l:t'') : real251requires { ordered' l }252requires { l = Inf -> if_ }253ensures { mem_if if_ result l } =254if if_ then255match l with256| (Sin q _) -> (Q.real q-.1.)257| (Chg q _ _) -> (Q.real q-.1.) (* Must be before *)258| Inf -> 0.259end260else261match l with262| (Sin q _) -> Q.real q263| (Chg q _ (Sin q' _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)264| (Chg q _ (Chg q' _ _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)265| (Chg q _ Inf) -> (Q.real q+.1.)266| Inf -> absurd267end268269Valid (25ms) (cvc5)270let ghost lt_bound_exists (if_:bool) (l:t'') : real271requires { ordered' l }272ensures { if_ <-> mem_if if_ result l }273ensures { lt_bound' result l }274=275match l with276| (Sin q _) -> (Q.real q-.1.)277| (Chg q _ _) -> (Q.real q-.1.) (* Must be before *)278| Inf -> 0.279end280281Valid (366ms) (cvc5)282let ghost not_bottom_after' (before:real) (if_:bool) (l:t'') : real283requires { ordered' l }284requires { lt_bound' before l }285requires { l = Inf -> if_ }286ensures { mem_if if_ result l }287ensures { before <. result } =288if if_ then289match l with290| (Sin q _) -> (Q.real q*.0.5+.before*.0.5)291| (Chg q _ _) -> (Q.real q*.0.5+.before*.0.5)292| Inf -> before +. 1.293end294else295match l with296| (Sin q _) -> Q.real q297| (Chg q _ (Sin q' _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)298| (Chg q _ (Chg q' _ _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)299| (Chg q _ Inf) -> (Q.real q+.1.)300| Inf -> absurd301end302Valid (26ms) (cvc5)303let ghost not_bottom_before' (before:real) (if_:bool) (l:t'') : real304requires { lt_bound' before l }305ensures { forall x. before <=. x <=. result -> (if_ <-> mem_if if_ x l) }306ensures { before <. result } =307match l with308| (Sin q _) -> (Q.real q*.0.5+.before*.0.5)309| (Chg q _ _) -> (Q.real q*.0.5+.before*.0.5)310| Inf -> before +. 1.311end312Valid (19ms) (cvc5)313let ghost not_bottom_a (l:t') : real314requires { ordered l }315requires { not (l = Off Inf) }316ensures { mem result l } =317match l with318| Off l -> not_bottom' False l319| On l -> not_bottom' True l320end321Valid (19ms) (cvc5)322let ghost not_bottom (l:t) : real323ensures { mem result l.a } =324not_bottom_a l.a325Valid (27ms) (cvc5)326let ghost lt_bound_is_mem (if_:bool) (q:real) (l:t'')327requires { lt_bound' q l }328ensures { forall r. r <=. q -> (if_ <-> mem_if if_ r l)}329=330match l with331| Sin _ _ -> ()332| Chg _ _ _ -> ()333| Inf -> ()334end335Valid (45ms) (colibri2 2) (cvc5 5) (split_vc 2) (depth 2)336let ghost not_mem_is_le_bound' (if_:bool) (q:real) (l:t'')337requires { ordered' l }338requires { forall x. x <. q -> (if_ <-> mem_if if_ x l) }339ensures { le_bound' q l} =340match l with341| Sin a _ -> assert { not if_ <-> mem_if if_ a l }342| Chg a Strict l' ->343if pure { a <. q } then344let a' = not_bottom_before' (Q.real a) (not if_) l' in345let b = pure { a*.0.5+.(min a' q)*.0.5 } in346assert { (not if_ <-> mem_if if_ b l) };347absurd348| Chg a Large _ -> assert { (not if_) <-> (mem_if if_ a l) }349| Inf -> ()350end351Valid (351ms) (cvc5)352let ghost not_mem_is_le_bound (if_:bool) (q:real) (l:t')353requires { ordered l }354requires { forall x. x <. q -> (if_ <-> mem x l) }355ensures { le_bound q l}356ensures { l.on = if_ } =357let b = (lt_bound_exists l.on l.in_) in358lt_bound_is_mem l.on b l.in_;359let a = min b (q-.1.) in360assert { l.on <-> mem a l };361not_mem_is_le_bound' l.on q l.in_362363Valid (411ms) (cvc5)364let singleton (q:Q.t) : t365ensures { exact memt (fun (x:real) -> x = q) result }366=367{ a = Off (Sin q Inf) }368Valid (190ms) (colibri2 16) (cvc4 10) (split_vc 4) (depth 3)369let is_singleton (u:t) : (option Q.t, ghost real, ghost real)370ensures {371let (o,x1,x2) = result in372match o with373| Some q -> forall x:real. mem x u.a <-> x = q374| None -> x1 <> x2 /\ mem x1 u.a /\ mem x2 u.a375end376} =377match u.a with378| Off (Sin q Inf) -> (Some q,ghost 0.,ghost 1.)379| Off (Sin q (Sin q' _)) -> (None,ghost Q.real q,ghost Q.real q')380| Off (Sin _ (Chg q _ on)) ->381match on with382| Sin q' _ -> (None,ghost (Q.real q*.0.3+.Q.real q'*.0.7),383ghost (Q.real q*.0.7+.Q.real q'*.0.3))384| Chg q' _ _ -> (None,ghost(Q.real q*.0.3+.Q.real q'*.0.7),385ghost(Q.real q*.0.7+.Q.real q'*.0.3))386| Inf -> (None,ghost(Q.real q+.1.),ghost(Q.real q+.2.))387end388| Off (Chg q _ on) ->389match on with390| Sin q' _ -> (None,ghost (Q.real q*.0.3+.Q.real q'*.0.7),391ghost (Q.real q*.0.7+.Q.real q'*.0.3))392| Chg q' _ _ -> (None,ghost(Q.real q*.0.3+.Q.real q'*.0.7),393ghost(Q.real q*.0.7+.Q.real q'*.0.3))394| Inf -> (None,ghost(Q.real q+.1.),ghost(Q.real q+.2.))395end396| On (Sin q _) -> (None, ghost (Q.real q-.1.), ghost (Q.real q-.2.))397| On (Chg q _ _) -> (None, ghost (Q.real q-.1.), ghost (Q.real q-.2.))398| On Inf -> (None, ghost 0., ghost 1.)399| Off Inf -> absurd400end401402use colibrilib.q.Ord as Ord403Valid (24ms) (cvc5)404let min_bound_sup v1 b1 v2 b2: (v3:Q.t,b3:Bound.t)405ensures { forall q. (cmp q b1 v1 /\ cmp q b2 v2) <-> cmp q b3 v3 }406ensures { (v3 <=. v1) } ensures { (v3 <=. v2) }407ensures { v3 = v1 || v3 = v2 }408ensures { b1 = Large -> b2 = Large -> b3 = Large }409=410match Q.compare v1 v2, b1, b2 with411| Ord.Eq, Large, Large -> (v1,Large)412| Ord.Eq, _ ,_ -> (v1,Strict)413| Ord.Lt, _, _ -> (v1,b1)414| Ord.Gt, _ ,_ -> (v2,b2)415end416Valid (28ms) (cvc5)417let min_bound_inf v1 b1 v2 b2: (v3:Q.t,b3:Bound.t)418ensures { forall q. (cmp v1 b1 q \/ cmp v2 b2 q) <-> cmp v3 b3 q }419ensures { (v3 <=. v1) } ensures { (v3 <=. v2) }420ensures { v3 = v1 || v3 = v2 }421ensures { b1 = Large -> b2 = Large -> b3 = Large }422=423match Q.compare v1 v2, b1, b2 with424| Ord.Eq, Strict, Strict -> (v1,Strict)425| Ord.Eq, _, _ -> (v1,Large)426| Ord.Lt, _, _ -> (v1,b1)427| Ord.Gt, _, _ -> (v2,b2)428end429430use real.MinMax431Valid (26ms) (cvc5)432let max_bound_sup v1 b1 v2 b2: (v3:Q.t,b3:Bound.t)433ensures { forall q. (cmp q b1 v1 \/ cmp q b2 v2) <-> cmp q b3 v3 }434ensures { (v1 <=. v3) } ensures { (v2 <=. v3) }435ensures { max v1 v2 = v3 }436ensures { b1 = Large -> b2 = Large -> b3 = Large }437=438match Q.compare v1 v2, b1, b2 with439| Ord.Eq, Strict, Strict -> (v1,Strict)440| Ord.Eq, _, _ -> (v1,Large)441| Ord.Lt, _, _ -> (v2,b2)442| Ord.Gt, _, _ -> (v1,b1)443end444Valid (23ms) (cvc5)445let max_bound_inf v1 b1 v2 b2: (v3:Q.t,b3:Bound.t)446ensures { forall q. (cmp v1 b1 q /\ cmp v2 b2 q) <-> cmp v3 b3 q }447ensures { (v1 <=. v3) } ensures { (v2 <=. v3) }448ensures { v3 = v1 || v3 = v2 }449ensures { b1 = Large -> b2 = Large -> b3 = Large }450=451match Q.compare v1 v2, b1, b2 with452| Ord.Eq, Large, Large -> (v1,Large)453| Ord.Eq, _, _ -> (v1,Strict)454| Ord.Lt, _, _ -> (v2,b2)455| Ord.Gt, _, _ -> (v1,b1)456end457Valid (2.0s) (colibri2 71) (cvc4 9) (cvc5 85) (split_vc 29) (depth 5)458let rec inter' (ifu:bool) (ifv:bool) (u:t'') (v:t'') : t''459requires { ordered' u }460requires { ordered' v }461ensures { ordered' result }462ensures {463forall x:real. (mem_if ifu x u /\ mem_if ifv x v) <-> mem_if (andb ifu ifv) x result464}465ensures { le_sup (min_sup (bound u) (bound v)) (bound result) }466variant { length' u + length' v } =467match u, v with468| u, Inf -> if ifv then u else Inf469| Inf, v -> if ifu then v else Inf470| Sin qu lu, Sin qv lv ->471match Q.compare qu qv with472| Ord.Eq -> let l = inter' ifu ifv lu lv in if xorb ifu ifv then l else Sin qu l473| Ord.Lt ->474let l = inter' ifu ifv lu v in475if ifv then Sin qu l else l476| Ord.Gt ->477let l = inter' ifu ifv u lv in478if ifu then Sin qv l else l479end480| Chg qu bu lu, Chg qv bv lv ->481match Q.compare qu qv with482| Ord.Eq ->483(* lt_bound_is_mem ifv qu lv; lt_bound_is_mem ifu qu lu; *)485let l = inter' (notb ifu) (notb ifv) lu lv in486match bu, bv with487| Large, Large | Strict, Strict -> if xorb ifu ifv then l else Chg qu bu l488| Large, Strict ->489match ifu, ifv with490| True, True -> Chg qu Large l491| False, False -> Chg qu Strict l492| True, False -> l493| False, True -> Sin qu l494end495| Strict, Large ->496match ifv, ifu with497| True, True -> Chg qu Large l498| False, False -> Chg qu Strict l499| True, False -> l500| False, True -> Sin qu l501end502end503| Ord.Lt -> let l = (inter' (notb ifu) ifv lu v) in if ifv then Chg qu bu l else l504| Ord.Gt -> let l = (inter' ifu (notb ifv) u lv) in if ifu then Chg qv bv l else l505end506| Sin qu lu, Chg qv bv lv ->507match Q.compare qu qv with508| Ord.Eq ->509let l = inter' ifu (notb ifv) lu lv in510if ifu then511Chg qu (if ifv then Large else Strict) l512else513match ifv, bv with514| False, Large | True, Strict -> Sin qu l515| _ -> l516end517| Ord.Lt ->518let l = inter' ifu ifv lu v in if ifv then Sin qu l else l519| Ord.Gt ->520let l = inter' ifu (notb ifv) u lv in if ifu then Chg qv bv l else l521end522| Chg qu bu lu, Sin qv lv ->523match Q.compare qu qv with524| Ord.Eq ->525let l = inter' (notb ifu) ifv lu lv in526if ifv then527Chg qv (if ifu then Large else Strict) l528else529match ifu, bu with530| False, Large | True, Strict -> Sin qv l531| _ -> l532end533| Ord.Lt ->534let l = inter' (notb ifu) ifv lu v in if ifv then Chg qu bu l else l535| Ord.Gt ->536let l = inter' ifu ifv u lv in if ifu then Sin qv l else l537end538end539540Valid (701ms) (colibri2 19) (split_vc) (depth 1)541let inter (u:t) (v:t) : option t542ensures { exact_opt memt (fun (x:real) -> memt x u /\ memt x v) result }543ensures {544match result with545| None -> true546| Some w ->547le_sup_infr (le_min_sup_infr (infr_bound u.a) (infr_bound v.a)) (infr_bound w.a)548end549}550=551let mk_off_option (l:t'') : option t552requires { ordered' l }553ensures {554forall x:real. mem_if False x l <->555match result with556| None -> false557| Some w -> mem x w.a558end559}560ensures {561match result with562| None -> true563| Some w -> (infr_bound' l) = (infr_bound w.a)564end565}566=567match l with568| Inf -> None569| l -> Some { a = Off l }570end571in572match u.a,v.a with573| On u, On v -> Some { a = On (inter' True True u v) }574| On u, Off v -> mk_off_option (inter' True False u v)575| Off u, On v -> mk_off_option (inter' False True u v)576| Off u, Off v -> mk_off_option (inter' False False u v)577end578Valid (3.2s) (colibri2 64) (cvc5 71) (split_vc 23) (depth 5)579let rec union' (ifu:bool) (ifv:bool) (u:t'') (v:t'') : t''580requires { ordered' u }581requires { ordered' v }582ensures { ordered' result }583ensures {584forall x:real. (mem_if ifu x u \/ mem_if ifv x v) <-> mem_if (orb ifu ifv) x result585}586ensures { le_sup (min_sup (bound u) (bound v)) (bound result) }587variant { length' u + length' v } =588match u, v with589| u, Inf -> if ifv then Inf else u590| Inf, v -> if ifu then Inf else v591| Sin qu lu, Sin qv lv ->592match Q.compare qu qv with593| Ord.Eq -> let l = union' ifu ifv lu lv in if xorb ifu ifv then l else Sin qu l594| Ord.Lt ->595let l = union' ifu ifv lu v in596if ifv then l else Sin qu l597| Ord.Gt ->598let l = union' ifu ifv u lv in599if ifu then l else Sin qv l600end601| Chg qu bu lu, Chg qv bv lv ->602match Q.compare qu qv with603| Ord.Eq ->604let l = union' (notb ifu) (notb ifv) lu lv in605match bu, bv with606| Large, Large | Strict, Strict -> if xorb ifu ifv then l else Chg qu bu l607| Large, Strict ->608match ifu, ifv with609| True, True -> Chg qu Strict l610| False, False -> Chg qu Large l611| True, False -> Sin qu l612| False, True -> l613end614| Strict, Large ->615match ifv, ifu with616| True, True -> Chg qu Strict l617| False, False -> Chg qu Large l618| True, False -> Sin qu l619| False, True -> l620end621end622| Ord.Lt -> let l = (union' (notb ifu) ifv lu v) in if ifv then l else Chg qu bu l623| Ord.Gt -> let l = (union' ifu (notb ifv) u lv) in if ifu then l else Chg qv bv l624end625| Sin qu lu, Chg qv bv lv ->626match Q.compare qu qv with627| Ord.Eq ->628let l = union' ifu (notb ifv) lu lv in629if ifu then630match ifv, bv with631| False, Large | True, Strict -> l632| _ -> Sin qu l633end634else635Chg qu (if ifv then Strict else Large) l636| Ord.Lt ->637let l = union' ifu ifv lu v in if ifv then l else Sin qu l638| Ord.Gt ->639let l = union' ifu (notb ifv) u lv in if ifu then l else Chg qv bv l640end641| Chg qu bu lu, Sin qv lv ->642match Q.compare qu qv with643| Ord.Eq ->644let l = union' (notb ifu) ifv lu lv in645if ifv then646match ifu, bu with647| False, Large | True, Strict -> l648| False, Strict | True, Large -> Sin qv l649end650else651Chg qv (if ifu then Strict else Large) l652| Ord.Lt ->653let l = union' (notb ifu) ifv lu v in if ifv then l else Chg qu bu l654| Ord.Gt ->655let l = union' ifu ifv u lv in if ifu then l else Sin qv l656end657end658Valid (368ms) (cvc5)659let union_a (u:t') (v:t') : t'660requires { ordered u }661requires { ordered v }662ensures { ordered result }663ensures {664forall x:real. (mem x u \/ mem x v) <-> mem x result665} =666match u,v with667| On u, On v -> On (union' True True u v)668| On u, Off v -> On (union' True False u v)669| Off u, On v -> On (union' False True u v)670| Off u, Off v -> Off (union' False False u v)671end672673Valid (394ms) (cvc5)674let union (u:t) (v:t) : t675ensures { exact memt (fun (x:real) -> memt x u \/ memt x v) result } =676let w = union_a u.a v.a in677let ghost x = not_bottom u in678assert { mem x w };679{ a = w }680681682let cmp (x:Q.t) (b:Bound.t) (y:Q.t) =683match b with684| Bound.Large -> Q.le x y685| Bound.Strict -> Q.lt x y686end687688Valid (335ms) (cvc5)689let mem (x:Q.t) (l:t)690ensures { decides (memt x.Q.real l) result }691=692let rec mem' (if_:bool) (x:Q.t) (l:t'')693requires { ordered' l }694ensures { result = mem_if if_ x.Q.real l }695variant { length' l }696=697match l with698| Sin q l ->699match Q.compare x q with700| Ord.Eq -> notb if_701| Ord.Lt -> if_702| Ord.Gt -> mem' if_ x l703end704| Chg q b l ->705if cmp q b x then mem' (notb if_) x l706else if_707| Inf -> if_708end709in710match l.a with711| On l ->712mem' True x l713| Off l ->714mem' False x l715end716Valid (777ms) (colibri2 5) (cvc5 16) (split_vc 2) (depth 2)717let except l x718ensures {719match result with720| Some res -> forall q. (mem q l.a /\ q <> x.Q.real) <-> mem q res.a721| None -> forall q. mem q l.a <-> q = x.Q.real722end723}724=725let rec except' (if_:bool) (x:Q.t) (l:t'') : t''726requires { ordered' l }727ensures { ordered' result }728ensures { le_sup (min_sup (R x) (bound l)) (bound result) }729ensures { forall q. (mem_if if_ q l /\ q <> x.Q.real) <-> mem_if if_ q result }730variant { length' l }731=732match l with733| Sin q l' ->734lt_bound_is_mem if_ (Q.real q) l';735match Q.compare x q with736| Ord.Eq -> if if_ then l else l'737| Ord.Lt -> if if_ then Sin x l else l738| Ord.Gt -> Sin q (except' if_ x l')739end740| Chg q bv l' ->741match Q.compare x q with742| Ord.Eq -> lt_bound_is_mem if_ (Q.real q) l'; Chg q (if if_ then Large else Strict) l'743| Ord.Lt -> if if_ then Sin x l else l744| Ord.Gt -> Chg q bv (except' (notb if_) x l')745end746| Inf -> if if_ then Sin x Inf else Inf747end748in749match l.a with750| On l ->751Some { a = On (except' True x l) }752| Off l ->753match except' False x l with754| Inf ->755let ghost v = not_bottom' False l in756assert { v = x };757None758| l' -> Some { a = Off l' }759end760end761762Valid (144ms) (colibri2 8) (split_vc) (depth 1)763let complement l764ensures { exact_opt memt (fun (x:real) -> not (memt x l)) result } =765let rec lemma complement' (if_:bool) (l:t'') : unit766ensures { forall q. not (mem_if if_ q l) <-> mem_if (not if_) q l }767variant { l }768=769match l with770| Sin _ l' -> complement' if_ l'771| Chg _ _ l' -> (complement' (notb if_) l')772| Inf -> ()773end774in775match l.a with776| On Inf -> None777| On l ->778Some { a = Off l }779| Off l ->780Some { a = On l }781end782783784let function add_bound b1 b2 =785match b1, b2 with786| Large, Large -> Large787| Large, Strict -> Strict788| Strict, Large -> Strict789| Strict, Strict -> Strict790end791792let function both_strict b1 b2 =793match b1, b2 with794| Strict, Strict -> Strict795| Large, Strict -> Large796| Strict, Large -> Large797| Large, Large -> Large798end799800801use real.MinMax802803let bound_compare test if1 if2 b1 b2 =804match (b1, b2) with805| Large, Large -> test if1 if2806| Strict, Large -> test (notb if1) if2807| Large, Strict -> test if1 (notb if2)808| Strict, Strict -> test (notb if1) (notb if2)809end810Valid (1.6s) (colibri2 10) (cvc5 61) (split_vc 3) (depth 3)811let rec for_all test t1 t2812ensures { result -> (forall q. test (mem q t1.a) (mem q t2.a)) }813=814let rec aux test if1 if2 t1 t2815requires { ordered' t1 }816requires { ordered' t2 }817requires { test if1 if2 }818ensures { result -> (forall q1. test (mem_if if1 q1 t1) (mem_if if2 q1 t2)) }819variant { length' t1 + length' t2 }820=821match (t1, t2) with822| Inf, Inf -> test if1 if2823| _, Inf -> test (notb if1) if2824| Inf, _ -> test if1 (notb if2)825| Sin q1 l1, Sin q2 l2 ->826match Q.compare q1 q2 with827| Ord.Lt -> test (notb if1) if2 && aux test if1 if2 l1 t2828| Ord.Gt -> test if1 (notb if2) && aux test if1 if2 t1 l2829| Ord.Eq -> test (notb if1) (notb if2) && aux test if1 if2 l1 l2830end831| Sin q1 l1, Chg q2 b2 l2 ->832match Q.compare q1 q2 with833| Ord.Lt -> test (notb if1) if2 && aux test if1 if2 l1 t2834| Ord.Gt -> test if1 (notb if2) && test if1 (notb if2) && aux test if1 (notb if2) t1 l2835| Ord.Eq -> bound_compare test (notb if1) (notb if2) Large b2 && test if1 (notb if2) && aux test if1 (notb if2) l1 l2836end837| Chg q1 b1 l1, Sin q2 l2 ->838match Q.compare q1 q2 with839| Ord.Lt -> test (notb if1) if2 && test (notb if1) if2 && aux test (notb if1) if2 l1 t2840| Ord.Gt -> test if1 (notb if2) && test if1 if2 && aux test if1 if2 t1 l2841| Ord.Eq -> bound_compare test (notb if1) (notb if2) b1 Large && test (notb if1) if2 && aux test (notb if1) if2 l1 l2842end843| Chg q1 b1 l1, Chg q2 b2 l2 ->844match Q.compare q1 q2 with845| Ord.Lt -> test (notb if1) if2 && aux test (notb if1) if2 l1 t2846| Ord.Gt -> test if1 (notb if2) && aux test if1 (notb if2) t1 l2847| Ord.Eq -> bound_compare test (notb if1) (notb if2) b1 b2 && test (notb if1) (notb if2) && aux test (notb if1) (notb if2) l1 l2848end849end850in851match (t1.a, t2.a) with852| On on1, On on2 ->853test True True && aux test True True on1 on2854| On on1, Off off2 ->855test True False && aux test True False on1 off2856| Off off1, On on2 ->857test False True && aux test False True off1 on2858| Off off1, Off off2 ->859test False False && aux test False False off1 off2860end861Valid (32ms) (cvc5)862let rec distinct t1 t2863ensures { result -> (forall q. not ((mem q t1.a) /\ (mem q t2.a))) }864=865let nand x y = notb (andb x y) in866for_all nand t1 t2867868let function impb b1 b2 =869match b1, b2 with870| True, False -> False871| _ -> True872end873Valid (32ms) (cvc5)874let rec is_included t1 t2875ensures { result -> (forall q. (mem q t1.a) -> (mem q t2.a)) }876=877for_all impb t1 t2878Valid (37ms) (cvc5)879let gt (q:Q.t)880ensures { exact memt (fun (x:real) -> q <. x) result }881= { a = Off (Chg q Strict Inf) }882Valid (414ms) (cvc5)883let lt (q:Q.t)884ensures { exact memt (fun (x:real) -> x <. q) result }885= { a = On (Chg q Large Inf) }886Valid (40ms) (cvc5)887let ge (q:Q.t)888ensures { exact memt (fun (x:real) -> q <=. x) result }889ensures { R q = infr_bound result.a }890= { a = Off (Chg q Large Inf) }891Valid (33ms) (cvc5)892let le (q:Q.t)893ensures { exact memt (fun (x:real) -> x <=. q) result }894= { a = On (Chg q Strict Inf) }895Valid (146ms) (colibri2 4) (cvc5 21) (split_vc) (depth 1)896let le' (u:t)897ensures { sound_rel memt (<=.) u result }898=899let rec aux if_ u900requires { u <> Inf }901requires { ordered' u }902ensures { ordered' result }903ensures { forall q. mem_if if_ q u -> forall q'. q' <=. q -> mem_if True q' result }904variant { u }905=906match u with907| Sin q Inf -> if if_ then Inf else Chg q Strict Inf908| Chg q b Inf -> if if_ then Chg q b Inf else Inf909| Sin q u -> let _ = not_bottom_after' (Q.real q) if_ u in aux if_ u910| Chg q _ u -> let _ = not_bottom_after' (Q.real q) (notb if_) u in aux (notb if_) u911| Inf -> Inf912end913in914match u.a with915| On Inf -> { a = On Inf }916| On on -> { a = On (aux True on) }917| Off off -> { a = On (aux False off) }918end919Valid (302ms) (colibri2)920let rec mem_max' if_ u: option (Q.t,Bound.t)921requires { u <> Inf }922requires { ordered' u }923ensures { match result with924| None -> true925| Some (r,_) -> forall q. lt_bound' q u -> q <.r926end }927ensures { match result with928| None -> true929| Some (r,b) -> forall q. mem_if if_ q u -> cmp q b r930end }931variant { u }932=933match u with934| Sin q Inf -> if if_ then None else Some (q,Large)935| Chg q b Inf -> if if_ then Some (q,inv_bound b) else None936| Sin _ u -> mem_max' if_ u937| Chg _ _ u -> mem_max' (notb if_) u938| Inf -> None939end940
v is an upper bound of u
predicate is_upper (u:t) (v:(Q.t,Bound.t)) =943let (r,b) = v in forall q. mem q u.a -> cmp q b r944Valid (406ms) (cvc5)945let mem_max u946ensures { when_some (is_upper u) result }947=948match u.a with949| On Inf -> None950| On a -> mem_max' True a951| Off a -> mem_max' False a952end953Valid (38ms) (cvc5)954let mem_min (u:t): option (Q.t,Bound.t)955ensures { forall q. mem q u.a ->956match result with957| None -> true958| Some (r,b) -> cmp r b q959end960}961=962match u.a with963| On _ -> None964| Off (Sin q _) -> Some (q,Large)965| Off (Chg q b _) -> Some (q,b)966| _ -> absurd967end968969970Valid (187ms) (colibri2 4) (cvc5 21) (split_vc) (depth 1)971let lt' (u:t)972ensures { sound_rel memt (<.) u result }973=974let rec aux if_ u975requires { u <> Inf }976requires { ordered' u }977ensures { ordered' result }978ensures { forall q. mem_if if_ q u -> forall q'. q' <. q -> mem_if True q' result }979variant { u }980=981match u with982| Sin q Inf -> if if_ then Inf else Chg q Large Inf983| Chg q _ Inf -> if if_ then Chg q Large Inf else Inf984| Sin q u -> let _ = not_bottom_after' (Q.real q) if_ u in aux if_ u985| Chg q _ u -> let _ = not_bottom_after' (Q.real q) (notb if_) u in aux (notb if_) u986| Inf -> Inf987end988in989match u.a with990| On Inf -> { a = On Inf }991| On on -> { a = On (aux True on) }992| Off off -> { a = On (aux False off) }993end994Valid (405ms) (colibri2)995let gt' (u:t)996ensures { sound_rel memt (>.) u result }997=998match u.a with999| On _ -> { a = On Inf }1000| Off (Sin q _) -> { a = Off (Chg q Strict Inf) }1001| Off (Chg q _ _) -> { a = Off (Chg q Strict Inf) }1002| _ -> absurd1003end1004Valid (399ms) (colibri2)1005let ge' (u:t)1006ensures { sound_rel memt (>=.) u result }1007=1008match u.a with1009| On _ -> { a = On Inf }1010| Off (Sin q _) -> { a = Off (Chg q Large Inf) }1011| Off (Chg q b _) -> { a = Off (Chg q b Inf) }1012| _ -> absurd1013end10141015scope IsComparable1016type is_comparable = Gt | Lt | Ge | Le | Eq | Uncomparable1017Valid (275ms) (colibri2)1018let rec is_lt' (if_:bool) (t1:t'') (q:Q.t)1019ensures { match result with1020| Lt -> forall q1. mem_if if_ q1 t1 -> cmp q1 Strict q1021| Le -> forall q1. mem_if if_ q1 t1 -> cmp q1 Large q1022| Uncomparable -> true1023| Eq | Gt | Ge -> false1024end }1025variant { t1 }1026=1027match t1, if_ with1028| Sin _ Inf, True -> Uncomparable1029| Chg _ _ Inf, False -> Uncomparable1030| Sin q1 l1, _ ->1031match Q.compare q1 q, l1 with1032| Ord.Lt, Inf -> Lt1033| Ord.Eq, Inf -> Le1034| Ord.Eq, _ -> Uncomparable1035| Ord.Lt , _ -> is_lt' if_ l1 q1036| Ord.Gt, _ -> Uncomparable1037end1038| Chg q1 b1 l1, _ ->1039match Q.compare q1 q, b1, l1 with1040| Ord.Lt, _, Inf -> Lt1041| Ord.Eq, Large, Inf -> Lt1042| Ord.Eq, Strict, Inf -> Le1043| Ord.Eq, _, _ -> Uncomparable1044| Ord.Lt , _,_ -> is_lt' (notb if_) l1 q1045| Ord.Gt, _, _ -> Uncomparable1046end1047| Inf, True -> Uncomparable1048| Inf, False -> Lt1049end10501105(* let rec is_comparable_q' (start:bool) (if_:bool) (t1:t'') (q:Q.t) ensures { match result with | Lt -> forall q1. mem_if if_ q1 t1 -> cmp q1 Strict q | Le -> false | Uncomparable -> not start | Eq -> mem_if if_ q t1 | Gt -> start /\ forall q1. mem_if if_ q1 t1 -> cmp q Strict q1 | Ge -> false end } variant { t1 } = match t1, if_ with | Sin q1 Inf, True -> match Q.compare q1 q with | Ord.Eq -> Uncomparable | Ord.Gt | Ord.Lt -> Eq end | Chg _ _ Inf, False -> Uncomparable | Sin q1 l1, _ -> match Q.compare q1 q, l1 with | Ord.Lt, Inf -> Lt | Ord.Eq, Inf -> Le | Ord.Eq, _ -> Uncomparable | Ord.Lt , _ -> is_comparable_q' False if_ l1 q | Ord.Gt, _ -> Uncomparable end | Chg q1 b1 l1, _ -> match Q.compare q1 q, b1, l1 with | Ord.Lt, _, Inf -> Lt | Ord.Eq, Large, Inf -> Lt | Ord.Eq, Strict, Inf -> Le | Ord.Eq, _, _ -> Uncomparable | Ord.Lt , _,_ -> is_comparable_q' False (notb if_) l1 q | Ord.Gt, _, _ -> Uncomparable end | Inf, True -> Uncomparable | Inf, False -> Lt end let rec is_comparable_q (l:t) (q:Q.t) ensures { match result with | Lt -> forall q1. mem q1 l.a -> cmp q1 Strict q | Le -> false | Uncomparable -> true | Eq -> mem q1 l.a | Gt -> forall q1. mem q1 t1.a -> cmp q Strict q1 | Ge -> false end } = in match t1.on with | On l -> is_comparable_q' True True l q | Off l -> is_comparable_q' True False l q end *)1106Valid (1.0s) (colibri2 5) (cvc5 120) (split_vc 2) (depth 2)1107let is_comparable (t1:t) (t2:t)1108ensures { match result with1109| Gt -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 >. q21110| Lt -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 <. q21111| Ge -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 >=. q21112| Le -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 <=. q21113| Eq -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 = q21114| Uncomparable -> true1115end }1116=1117match t1.a, t2.a with1118| On _, On _ -> Uncomparable1119| On l1, Off l2 ->1120let q2,b2 = match l2 with1121| Sin q2 _ -> q2, Large1122| Chg q2 b2 _ -> q2, b21123| _ -> absurd1124end1125in1126match is_lt' True l1 q2, b2 with1127| Lt, _ -> Lt1128| Le, Strict -> Lt1129| Le, Large -> Le1130| Uncomparable, _ -> Uncomparable1131| _ -> absurd1132end1133| Off l1, On l2 ->1134let q1,b1 = match l1 with1135| Sin q1 _ -> q1, Large1136| Chg q1 b1 _ -> q1, b11137| _ -> absurd1138end1139in1140match is_lt' True l2 q1, b1 with1141| Lt, _ -> Gt1142| Le, Strict -> Gt1143| Le, Large -> Ge1144| Uncomparable, _ -> Uncomparable1145| _ -> absurd1146end1147| Off l1, Off l2 ->1148let q1,b1 = match l1 with1149| Sin q1 _ -> q1, Large1150| Chg q1 b1 _ -> q1, b11151| _ -> absurd1152end1153in1154let q2,b2 = match l2 with1155| Sin q2 _ -> q2, Large1156| Chg q2 b2 _ -> q2, b21157| _ -> absurd1158end1159in1160match Q.compare q1 q2 with1161| Ord.Eq -> match is_lt' False l1 q2, b2, is_lt' False l2 q1, b1 with1162| Lt, _, _, _ ->1163let ghost w1 = not_bottom' False l1 in1164assert { cmp w1 Strict q2 };1165absurd1166| _, _, Lt, _ ->1167let ghost w2 = not_bottom' False l2 in1168assert { cmp w2 Strict q1 };1169absurd1170| Le, _, Le, _ -> Eq1171| Le, Strict, _, _ -> Lt1172| Le, Large, _, _ -> Le1173| Uncomparable, _, Le, Large -> Ge1174| Uncomparable, _, Le, Strict -> Gt1175| Uncomparable, _, Uncomparable, _ -> Uncomparable1176| _ -> absurd1177end1178| Ord.Lt ->1179match is_lt' False l1 q2, b2 with1180| Lt, _ -> Lt1181| Le, Strict -> Lt1182| Le, Large -> Le1183| Uncomparable, _ -> Uncomparable1184| _ -> absurd1185end1186| Ord.Gt ->1187match is_lt' False l2 q1, b1 with1188| Lt, _ -> Gt1189| Le, Strict -> Gt1190| Le, Large -> Ge1191| Uncomparable, _ -> Uncomparable1192| _ -> absurd1193end1194end1195end1196end11971198type convex_hull = (option (Q.t,Bound.t),option (Q.t,Bound.t))11991200predicate in_hull_sup (q':real) (b2:(option (Q.t,Bound.t))) =1201match b2 with1202| None -> true1203| Some (q,b) -> cmp q' b q1204end12051206predicate in_hull (q':real) (x:convex_hull) =1207let (b1,b2) = x in1208match b1 with1209| None -> true1210| Some (q,b) -> cmp q b q'1211end /\ in_hull_sup q' b212121213Valid (246ms) (colibri2)1214let from_convex_hull x : option t1215ensures { includes_opt memt (fun (q:real) -> in_hull q x) result }1216=1217match x with1218| None, None -> Some { a = On Inf }1219| None, Some (q,b) -> Some { a = On (Chg q (inv_bound b) Inf) }1220| Some (q,b), None -> Some { a = Off (Chg q b Inf) }1221| Some (q1,b1), Some (q2,b2) ->1222match Q.compare q1 q2, b1, b2 with1223| Ord.Eq, Large, Large -> Some { a = Off (Sin q1 Inf) }1224| Ord.Eq, _, _ -> None1225| Ord.Lt, _, _ -> Some { a = Off (Chg q1 b1 (Chg q2 (inv_bound b2) Inf)) }1226| Ord.Gt, _, _ -> None1227end1228end1229Valid (301ms) (colibri2 3) (cvc5 22) (split_vc) (depth 1)1230let get_convex_hull x : convex_hull1231ensures { includes in_hull (fun (q:real) -> memt q x) result }1232=1233let rec get_last_on x =1234requires { ordered' x }1235ensures { forall q'. mem_if True q' x -> in_hull_sup q' result }1236variant { x }1237match x with1238| Sin _ on -> get_last_on on1239| Chg q b Inf -> Some (q, inv_bound b)1240| Chg _ _ off -> let _w = not_bottom' False off in get_last_off off1241| Inf -> None1242end1243with get_last_off x1244requires { x <> Inf }1245requires { ordered' x }1246ensures { forall q'. mem_if False q' x -> in_hull_sup q' result }1247variant { x }1248=1249match x with1250| Sin q Inf -> Some (q, Large)1251| Sin _ off -> let _w = not_bottom' False off in get_last_off off1252| Chg _ _ on -> get_last_on on1253| Inf -> absurd1254end1255in1256match x.a with1257| On on -> (None, get_last_on on)1258| Off off ->1259match off with1260| Sin q Inf -> (Some (q,Bound.Large), Some (q,Large))1261| Sin q off -> let _w = not_bottom' False off in (Some (q,Large), get_last_off off)1262| Chg q b on -> (Some (q,b), get_last_on on)1263| Inf -> absurd1264end1265end12661267scope Increasing1268
footprint, the bounds are in the definition bounds
predicate foot_if (r1:infr) (r2:infr) (l:t'') =1270match l with1271| Sin q l -> le_infr r1 (R q) /\ le_infr (R q) r2 /\ foot_if r1 r2 l1272| Chg q _ l -> le_infr r1 (R q) /\ le_infr (R q) r2 /\ foot_if r1 r2 l1273| Inf -> r2 = I1274end12751276predicate foot (r1:infr) (r2:infr) (l:t') =1277match l with1278| On l -> r1 = I /\ foot_if r1 r2 l1279| Off l -> foot_if r1 r2 l1280end1281Valid (383ms) (cvc5)1282let rec lemma foot_if_inf (l:t'') : unit1283ensures { foot_if I I l } =1284match l with1285| Sin _ l | Chg _ _ l -> foot_if_inf l1286| Inf -> ()1287end12881296(* predicate foot_if (if_:bool) (x:real) (l:t'') = match l with | Sin q l -> if q <. x then foot_if if_ x l else (if if_ then x <=. q else x = q) | Chg q b l -> if q <. x then foot_if (notb if_) x l else (q = x \/ if_) | Inf -> if_ end *)12971298scope Unary Valid (18ms) (cvc5)1299type siop = {1300ghost minr: infr;1301ghost maxr: infr;1302ghost ur: real -> real;1303uq: Q.t -> Q.t;1304}1305invariant { forall v: Q.t. in_infr minr v maxr -> ur v = uq v }1306by { minr = I; maxr = I; ur = (fun x -> x); uq = (fun q -> q); }13071308predicate in_siop (op:siop) (r:real) =1309in_infr op.minr r op.maxr1310
unary stricly increasing
predicate si1 (op: siop) =1313(forall v v' [op.ur v,op.ur v']. v <. v' -> op.ur v <. op.ur v')1314Valid (323ms) (cvc4)1315let rec op_si1_cst' (op: siop) (ghost if_) (l:t'') : t''1316requires { ordered' l }1317requires { si1 op }1318requires { foot_if op.minr op.maxr l }1319ensures { ordered' result }1320ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur q) result) }1321ensures { forall q. ((mem_if if_ q l) -> mem_if if_ (op.ur q) result) }1322variant { length' l }1323=1324match l with1325| Sin q l' -> Sin (op.uq q) (op_si1_cst' op if_ l')1326| Chg q bv l' ->1327Chg (op.uq q) bv (op_si1_cst' op (notb if_) l')1328| Inf -> Inf1329end1330Valid (290ms) (colibri2 15) (split_vc) (depth 1)1331let lemma mem_is_in_foot l min max q =1332requires { foot min max l }1333requires { mem q l }1334ensures { in_infr min q max }1335let rec ghost aux l if_ (min max:infr) (q:real) =1336requires { foot_if min max l }1337requires { mem_if if_ q l }1338ensures { le_infr (R q) max }1339variant { l }1340match l with1341| Sin _ l -> if pure { mem_if if_ q l } then aux l if_ min max q1342| Chg _ _ l -> if pure { mem_if (notb if_) q l } then aux l (notb if_) min max q1343| Inf -> ()1344end1345in1346match l with1347| On l-> aux l True min max q1348| Off Inf -> absurd1349| Off (Sin _ l) -> if pure { mem_if False q l } then aux l False min max q1350| Off (Chg _ _ l) -> aux l True min max q1351end1352Valid (90ms) (colibri2)1353let op_si1_cst (op: siop) l1354requires { si1 op }1355requires { foot op.minr op.maxr l.a }1356ensures { sound1 memt op.ur l result }1357=1358match l.a with1359| On Inf ->1360{ a = On Inf }1361| On l' ->1362{ a = On (op_si1_cst' op True l') }1363| Off Inf -> absurd1364| Off l' ->1365let _ = not_bottom l in1366{ a = Off (op_si1_cst' op False l') }1367end1368Valid (52ms) (colibri2 6) (cvc4 2) (cvc5) (split_vc) (depth 1)1369let test__inv_sub (min_pos:Q.t) l1370requires { 0. <. min_pos }1371requires { foot (R min_pos) I l.a }1372ensures { forall q. (mem q l.a) -> mem (-. (1. /. q)) result.a }1373=1374let function fur (x:real) = pure { if (Q.real min_pos) <=. x then (-. (1. /. x)) else (-. (1. /. (Q.real min_pos)) +. (x -. (Q.real min_pos))) } in1375let fuq (x:Q.t) ensures { min_pos <=. x -> result = fur x } =1376if Q.le min_pos x then (Q.sub (Q.of_int 0) (Q.div (Q.of_int 1) x)) else Q.of_int 01377in1378let lemma inc (v v':real)1379requires { v <. v' }1380ensures { fur v <. fur v' }1381= if Q.real min_pos <=. v then assert { 1. /. v' <. 1. /. v }1382else if Q.real min_pos <. v' then assert { 1. /. v' <. 1. /. Q.real min_pos }1383in1384let op = { minr = (R (Q.real min_pos)); maxr = I; ur = fur; uq = fuq } in1385op_si1_cst op l1386
unary stricly decreasing
predicate sd1 (op: siop) =1389(forall v v' [op.ur v,op.ur v']. v <. v' -> op.ur v' <. op.ur v)13901391predicate first_bound' (x:real) (l:t'') =1392match l with1393| Sin q _ -> x = q1394| Chg q _ _ -> x = q1395| Inf -> true1396end1397Valid (28ms) (cvc5)1398let ghost smaller_first_bound (x:real) (y:real) (m:t'')1399requires { x <. y }1400requires { first_bound' y m }1401requires { ordered' m }1402ensures { lt_bound' x m }1403= ()14041405predicate mem_if_not_top (if_:bool) (x:real) (l:t'') =1406match l with1407| Sin q l ->1408if q <. x then mem_if if_ x l else (if if_ then false else x = q)1409| Chg q b l ->1410if cmp q b x then mem_if (notb if_) x l else (if if_ then x = q else false)1411| Inf -> false1412end141314141415predicate is_bound' (x:real) (l:t'') =1416match l with1417| Sin q l ->1418x = q \/ is_bound' x l1419| Chg q _ l ->1420x = q \/ is_bound' x l1421| Inf -> False1422end14231424predicate is_bound (x:real) (l:t') =1425match l with1426| On l -> is_bound' x l1427| Off l -> is_bound' x l1428end14291430Valid (3.7s) (colibri2 5) (cvc4 2) (cvc5 32) (split_vc 4) (depth 2)1431let rec op_sd1_cst' (op: siop) (l:t'') (acc:t'') if_ (ghost curr:real) : t1432requires { sd1 op }1433requires { ordered' l }1434requires { ordered' acc }1435requires { foot_if op.minr op.maxr l }1436requires { lt_bound' curr l }1437requires { first_bound' (op.ur curr) acc }1438requires { not if_ -> l = Inf -> acc <> Inf }1439ensures { forall q. curr <. q -> mem_if if_ q l -> mem (op.ur q) result.a }1440ensures { forall q. mem_if_not_top if_ q acc -> mem q result.a }1441ensures { forall q. is_bound q result.a -> (is_bound' q acc \/ (exists q'. (q = op.ur q' /\ is_bound' q' l))) }1442variant { length' l }1443=1444match l with1445| Sin q l' ->1446smaller_first_bound pure {op.ur q} pure {op.ur curr} acc;1447op_sd1_cst' op l' (Sin (op.uq q) acc) if_ (Q.real q)1448| Chg q bv l' ->1449assert { forall p. cmp q bv p = cmp (op.ur p) bv (op.ur q) };1450smaller_first_bound pure {op.ur q} pure {op.ur curr} acc;1451op_sd1_cst' op l' (Chg (op.uq q) (inv_bound bv) acc) (notb if_) (Q.real q)1452| Inf -> if if_ then { a = On acc } else begin1453{ a = Off acc }1454end1455end1456Valid (583ms) (colibri2 2) (cvc5 31) (split_vc 2) (depth 2)1457let op_sd1_cst (op: siop) l1458requires { sd1 op }1459requires { foot op.minr op.maxr l.a }1460ensures { sound1 memt op.ur l result }1461=1462match l.a with1463| On (Sin q l') -> op_sd1_cst' op l' (Sin (op.uq q) Inf) True (Q.real q)1464| On (Chg q bv l') -> op_sd1_cst' op l' (Chg (op.uq q) (inv_bound bv) Inf) False (Q.real q)1465| On Inf -> {a=On Inf}1466| Off l' ->1467let ghost curr = match l' with1468| Sin q _ | Chg q _ _ -> let ghost r = (Q.real q) -. 1. in smaller_first_bound r (Q.real q) l'; r1469| Inf -> 0.1470end1471in1472op_sd1_cst' op l' Inf False curr1473end1474Valid (81ms) (colibri2)1475let neg l1476ensures { sound1 memt (fun (x:real) -> -. x) l result }1477=1478let negq (x:Q.t) ensures { result = -. x } = Q.sub (Q.of_int 0) x in1479let op = { ur = (fun x -> -.x); uq = negq; minr = I; maxr = I } in1480op_sd1_cst op l1481Valid (62ms) (colibri2 2) (cvc5 7) (split_vc) (depth 1)1482let mult_cst c l1483ensures { sound1 memt (fun (x:real) -> c *. x) l result }1484=1485let fq (x:Q.t) ensures { result = c *. x } = Q.mul c x in1486let ghost function fr (x:real) = (Q.real c) *. x in1487let op = { minr = I; maxr = I; ur = fr; uq = fq } in1488match Q.compare (Q.of_int 0) c with1489| Ord.Eq -> singleton (Q.of_int 0)1490| Ord.Lt -> op_si1_cst op l1491| Ord.Gt ->1492let lemma op_sd1_aux (v v' : real) : unit1493requires { v <. v' }1494ensures { op.ur v' <. op.ur v } =1495assert { fr v' <. fr v }1496in1497op_sd1_cst op l1498end14991500end15011502type presence =1503| Near t''1504| Far t''15051506predicate mem_presence (c:real) (q:real) (p:presence) =1507match p with1508| Near l -> cmp c Strict q /\ mem_if True q l1509| Far l -> cmp c Strict q /\ mem_if False q l1510end15111512predicate ordered_presence (c:real) (p:presence) =1513match p with1514| Near l -> lt_bound' c l /\ ordered' l1515| Far l -> lt_bound' c l /\ ordered' l1516end1517Valid (33ms) (cvc5)1518let lemma mem_ordered_presence_is_gt (c:real) (q:real) (p:presence) =1519requires { mem_presence c q p }1520requires { ordered_presence c p }1521ensures { c <. q }1522match p with1523| Near _ -> ()1524| Far l -> lt_bound_is_mem False c l1525end1526Valid (483ms) (colibri2 8) (cvc5) (split_vc 2) (depth 2)1527let pos_union_is_presence (r:Q.t) (l:t'') : presence1528requires { ordered' l}1529requires { forall q. mem_if False q l -> r <. q }1530ensures { ordered_presence r result }1531ensures { forall q. mem_if False q l -> mem_presence r q result } =1532match l with1533| Sin q _ -> assert { mem_if False q l }; Far l1534| Chg q b l' ->1535match Q.compare r q with1536| Ord.Eq ->1537assert { b = Large -> mem_if False r l };1538assert { b = Strict }; Near l'1539| x ->1540let ghost p =1541let v = match l' with1542| Sin q' _ -> pure { Q.real q' }1543| Chg q' _ _ -> pure { Q.real q' }1544| Inf -> pure { q +. 1. }1545end1546in1547pure { 0.5 *. q +. 0.5 *. (min r v) }1548in1549assert { x = Ord.Gt -> (mem_if False p l /\ p <. r)};1550assert { x = Ord.Lt };1551Far l1552end1553| Inf -> Far Inf1554end1555Valid (34ms) (cvc5)1556let ghost not_bottom_presence (c:real) (l:presence) : real1557requires { ordered_presence c l }1558requires { not (l = Far Inf) }1559ensures { mem_presence c result l } =1560match l with1561| Far l -> not_bottom_after' c False l1562| Near l -> not_bottom_after' c True l1563end1564Valid (101ms) (colibri2)1565let presence_to_t (c:Q.t) (t:presence) : option t1566requires { ordered_presence c t }1567ensures { forall x. mem_presence c x t <-> match result with None -> false | Some r -> mem x r.a end } =1568match t with1569| Far Inf -> None1570| Far x -> Some { a = Off x }1571| Near x -> Some { a = Off (Chg c Strict x) }1572end15731574Valid (1.9s) (colibri2 9) (cvc4 5) (cvc5 29) (split_vc 8) (depth 3)1575let rec split_at' if_ l acc (ghost current : real) (ghost orig: t) : (p1:presence,b:bool,p2:presence) =1576requires { ordered' l }1577requires { ordered' acc }1578requires { lt_bound' 0. acc }1579requires { lt_bound' current l }1580requires { current <. 0. }1581requires { Unary.first_bound' (-. current) acc }1582requires { forall q. (mem q orig.a) -> if current <. q then mem_if if_ q l else mem_if if_ (-. q) acc }1583requires { forall q. -. current <=. q -> mem_if if_ q acc -> mem (-. q) orig.a }1584requires { forall q. current <. q -> mem_if if_ q l -> mem q orig.a }1585ensures { ordered_presence 0. p1 }1586ensures { ordered_presence 0. p2 }1587ensures { forall q. (mem q orig.a) -> (if 0. <. q then mem_presence 0. q p2 else if 0. = q then b else mem_presence 0. (-. q) p1) }1588ensures { forall q. mem_presence 0. q p1 -> mem (-. q) orig.a }1589ensures { forall q. mem_presence 0. q p2 -> mem q orig.a }1590ensures { b -> mem 0. orig.a }1591variant { length' l }1592match l with1593| Sin q l' ->1594match Q.compare q (Q.of_int 0) with1595| Ord.Eq ->1596let llt = if if_ then Near acc else Far acc in1597let lgt = if if_ then Near l' else Far l' in1598(llt,notb if_,lgt)1599| Ord.Lt ->1600Unary.smaller_first_bound pure {-. q} pure {-. current} acc;1601split_at' if_ l' (Sin (Q.sub (Q.of_int 0) q) acc) (Q.real q) orig1602| Ord.Gt ->16031604let llt = if if_ then Near acc else Far acc in1605let lgt = if if_ then Near l else Far l in1606(llt,if_,lgt)1607end1608| Chg q bv l' ->1609match Q.compare q (Q.of_int 0) with1610| Ord.Eq ->1611let llt = if if_ then Near acc else Far acc in1612let lgt = if if_ then Far l' else Near l' in1613let b = match bv with1614| Large -> notb if_1615| Strict -> if_1616end in1617(llt,b,lgt)1618| Ord.Lt ->1619Unary.smaller_first_bound pure {-. q} pure {-. current} acc;1620split_at' (notb if_) l' (Chg (Q.sub (Q.of_int 0) q) (inv_bound bv) acc) (Q.real q) orig1621| Ord.Gt ->1622let llt = if if_ then Near acc else Far acc in1623let lgt = if if_ then Near l else Far l in16241625(llt,if_,lgt)1626end1627| Inf ->1628let llt = if if_ then Near acc else Far acc in1629let lgt = if if_ then Near l else Far l in1630(llt,if_,lgt)1631end1632Valid (78ms) (colibri2)1633let rec ghost first_bound_is_foot_if (x:real) (q:real) l =1634requires { x <=. q }1635requires { Unary.first_bound' q l }1636requires { ordered' l }1637ensures { foot_if (R x) I l }1638variant { l }1639match l with1640| Sin _ ((Sin q _ | Chg q _ _) as l) -> first_bound_is_foot_if x (Q.real q) l1641| Chg _ _ ((Sin q _ | Chg q _ _) as l) -> first_bound_is_foot_if x (Q.real q) l1642| Sin _ Inf -> ()1643| Chg _ _ Inf -> ()1644| Inf -> ()1645end16461647Valid (83ms) (colibri2)1648let rec ghost lt_bound_is_foot_if (x:real) (q:real) l =1649requires { x <=. q }1650requires { lt_bound' q l }1651requires { ordered' l }1652ensures { foot_if (R x) I l }1653variant { l }1654match l with1655| Sin _ l -> lt_bound_is_foot_if x q l1656| Chg _ _ l -> lt_bound_is_foot_if x q l1657| Sin _ Inf -> ()1658| Chg _ _ Inf -> ()1659| Inf -> ()1660end16611662Valid (1.4s) (colibri2 58) (cvc4 5) (cvc5) (split_vc) (depth 1)1663let split_at (l:t) : (p1:presence,b:bool,p2:presence) =1664ensures { ordered_presence 0. p1 }1665ensures { ordered_presence 0. p2 }1666ensures { forall q. (mem q l.a) -> (if 0. <. q then mem_presence 0. q p2 else if 0. = q then b else mem_presence 0. (-. q) p1) }1667match l.a with1668| On l' ->1669match l' with1670| Sin q _ | Chg q _ _ ->1671if Q.le q (Q.of_int 0) then1672let ghost r = (Q.real q) -. 1. in Unary.smaller_first_bound r (Q.real q) l';1673split_at' True l' Inf r l1674else (1675Unary.smaller_first_bound 0.0 (Q.real q) l';1676Near Inf, True, Near l'1677)1678| Inf -> Near Inf, True, Near Inf1679end1680| Off l' ->1681match l' with1682| Sin q _ | Chg q _ _ ->1683if Q.le q (Q.of_int 0) then1684let ghost r = (Q.real q) -. 1. in Unary.smaller_first_bound r (Q.real q) l';1685split_at' False l' Inf r l1686else (1687Unary.smaller_first_bound 0.0 (Q.real q) l';1688Far Inf, False, Far l'1689)1690| Inf -> absurd1691end1692end16931694use real.Abs1695Valid (1.1s) (colibri2)1696let union_bzero (bzero:bool) (if_:bool) (l:t'')1697requires { ordered' l }1698requires { lt_bound' 0. l }1699ensures { ordered' result }1700ensures { forall q. 0. <. q -> mem_if if_ q l -> mem_if False q result }1701ensures { bzero <-> mem_if False 0. result }1702=1703let zero = Q.of_int 0 in1704if if_ then1705let b = (if bzero then Large else Strict) in1706Chg zero b l1707else1708if bzero then Sin zero l else l17091710let function open_presence (l:presence) =1711match l with1712| Far l -> False, l1713| Near l -> True, l1714end1715Valid (1.4s) (colibri2 8) (cvc4) (cvc5 3) (split_vc) (depth 1)1716let abs_forward (l:t) : t1717ensures { sound1 memt (fun (x:real) -> abs x) l result }1718=1719let neg,b,pos = split_at l in1720let ghost w = not_bottom l in1721let if_neg, neg = open_presence neg in1722let if_pos, pos = open_presence pos in1723let u = union' if_neg if_pos neg pos in1724assert { forall r. r <. 0. -> mem r l.a -> mem_if (orb if_neg if_pos) (-. r) u };1725assert { 0. <. w -> mem_if (orb if_neg if_pos) w u };1726let u' = union_bzero b (orb if_neg if_pos) u in1727assert { mem_if False (abs w) u' };1728let result = { a = Off u'} in1729assert { forall r. r >. 0. -> mem r l.a -> mem (abs r) result.a };1730assert { forall r. r = 0. -> mem r l.a -> mem (abs r) result.a };1731result1732Valid (33ms) (cvc5)1733let abs_backward (l:t) : t1734ensures { preimage1 memt (fun (x:real) -> abs x) l result }1735=1736union (Unary.neg l) l17371738scope Binary1739Valid (30ms) (cvc5)1740type siop = {1741ghost minr: infr;1742ghost maxr: infr;1743ghost ur: real -> real -> real;1744uq: Q.t -> Q.t -> Q.t;1745}1746invariant { forall u v: Q.t. in_infr minr u maxr -> in_infr minr v maxr -> ur u v = uq u v }1747by { minr = I; maxr = I; ur = (fun x _ -> x); uq = (fun q _ -> q); }17481749predicate in_siop (op:siop) (r:real) =1750in_infr op.minr r op.maxr1751
stricly increasing
predicate si (op:siop) =1754(forall u v v' [op.ur u v, op.ur u v']. v <. v' -> op.ur u v <. op.ur u v') /\1755(forall u u' v [op.ur u v, op.ur u' v]. u <. u' -> op.ur u v <. op.ur u' v)1756Valid (927ms) (cvc4)1757let rec op_si_cst' (op:siop) (x:Q.t) (l:t'') : t''1758requires { ordered' l }1759requires { si op }1760requires { in_siop op x }1761requires { foot_if op.minr op.maxr l }1762ensures { ordered' result }1763ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur x q) result) }1764ensures { forall if_ q. (mem_if if_ q l) <-> mem_if if_ (op.ur x q) result }1765variant { length' l }1766=1767match l with1768| Sin q l' -> Sin (op.uq x q) (op_si_cst' op x l')1769| Chg q bv l' ->1770assert { forall p. cmp q bv p = cmp (op.uq x q) bv (op.ur x p) };1771Chg (op.uq x q) bv (op_si_cst' op x l')1772| Inf -> Inf1773end17741775Valid (74ms) (cvc5)1776let op_si_cst (op: siop) l x1777requires { si op }1778requires { in_siop op x }1779requires { foot op.minr op.maxr l.a }1780ensures {1781forall q. (mem q l.a) <-> mem (op.ur x q) result.a1782}1783=1784match l.a with1785| On l ->1786{ a = On (op_si_cst' op x l) }1787| Off l ->1788let v = not_bottom' False l in1789let l = (op_si_cst' op x l) in1790assert { mem_if False (op.ur x v) l };1791{ a = Off l }1792end1793Valid (143ms) (colibri2)1794let add_cst l x1795ensures {1796forall q. (mem q l.a) <-> mem (x+.q) result.a1797}1798=1799let op = { minr = I; maxr = I; ur = (+.); uq = Q.add } in1800op_si_cst op l x18011802Valid (54ms) (cvc5)1803lemma si_le: forall op [si op]. si op -> (1804(forall u v v' [op.ur u v,op.ur u v']. v <=. v' -> op.ur u v <=. op.ur u v') /\1805(forall u u' v [op.ur u v, op.ur u' v]. u <=. u' -> op.ur u v <=. op.ur u' v)1806)1807Valid (361ms) (cvc5)1808lemma si_cmp1: forall op [si op]. si op -> (1809(forall u v v' b. cmp v b v' -> cmp (op.ur u v) b (op.ur u v')) /\1810(forall u u' v b. cmp u b u' -> cmp (op.ur u v) b (op.ur u' v))1811)1812Valid (391ms) (cvc5 2) (split_vc) (depth 1)1813lemma si_cmp2: forall op[si op]. si op -> (1814(forall u v b u' v' b'. cmp u b v -> cmp u' b' v' -> cmp (op.ur u u') (add_bound b b') (op.ur v v')) /\1815(forall u v b u' v' b'. (not (cmp u b v)) -> (not (cmp u' b' v')) -> (not (cmp (op.ur u u') (both_strict b b') (op.ur v v'))))1816)1817Valid (570ms) (colibri2 4) (cvc4) (cvc5 20) (split_vc 2) (depth 2)1818let rec op_si_interval_on (op: siop) (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t) (l:t'') : (result:t'')1819requires { si op }1820requires { (u <. v) }1821requires { ordered' l }1822requires { in_siop op u }1823requires { in_siop op v }1824requires { foot_if op.minr op.maxr l }1825ensures { ordered' result }1826ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur u q) result) }1827ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur v q) result) }1828ensures { forall q q'. (mem_if True q l /\ cmp u bu q' /\ not (cmp v bv q')) -> mem_if True (op.ur q' q) result }1829variant { length' l }1830=1831match l with1832| Sin _ l' ->1833assert { forall q'. mem_if True q' l -> mem_if True q' l'};1834op_si_interval_on op bu u v bv l'1835| Chg qs bq l' ->1836lt_bound_is_mem True (Q.real qs) l';1837let br = both_strict bq bv in1838let r = op.uq v qs in1839let res = op_si_interval_off_remain op bu u v bv r br (Q.real qs) l' in1840res1841| Inf -> Inf1842end1843Valid (378ms) (colibri2 20) (cvc4) (cvc5 2) (split_vc 2) (depth 2)1844with op_si_interval_off (op: siop) (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t) (l:t'') : (result:t'')1845requires { si op }1846requires { (u <. v) }1847requires { ordered' l }1848requires { in_siop op u }1849requires { in_siop op v }1850requires { foot_if op.minr op.maxr l }1851ensures { ordered' result }1852ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur u q) result) }1853ensures { forall q q'. (mem_if False q l /\ cmp u bu q' /\ (not (cmp v bv q'))) -> mem_if False (op.ur q' q) result }1854variant { length' l }1855=1856match l with1857| Sin qs l' ->1858lt_bound_is_mem False (Q.real qs) l';1859let r = op.uq v qs in1860let res = (op_si_interval_off_remain op bu u v bv r bv (Q.real qs) l') in1861let res = Chg (op.uq u qs) bu res in1862res1863| Chg qs b l' ->1864let bbu = add_bound b bu in1865let res0 = (op_si_interval_on op bu u v bv l') in1866let res = Chg (op.uq u qs) bbu res0 in1867res1868| Inf -> Inf1869end1870Valid (757ms) (colibri2 5) (cvc4 8) (cvc5 23) (split_vc 6) (depth 3)1871with op_si_interval_off_remain (op: siop) (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t) (r:Q.t) (br:Bound.t) (ghost rv:real) (l:t'') : (result:t'')1872requires { si op }1873requires { (u <. v) }1874requires { op.ur v rv = r }1875requires { lt_bound' rv l }1876requires { br = Strict -> bv = Strict }1877requires { in_siop op u }1878requires { in_siop op v }1879requires { foot_if op.minr op.maxr l }1880requires { ordered' l }1881ensures { ordered' result }1882ensures { forall q. (q <. r) -> (lt_bound' q result) }1883ensures { forall q q'. (mem_if False q l /\ cmp u bu q' /\ not (cmp v bv q')) -> mem_if True (op.ur q' q) result }1884ensures { forall q. not (cmp r br q) -> mem_if True q result }1885variant { length' l }1886=1887match l with1888| Sin qs l' ->1889lt_bound_is_mem False (Q.real qs) l';1890let qu = (op.uq u qs) in1891let r' = (op.uq v qs) in1892let res = (op_si_interval_off_remain op bu u v bv r' bv (Q.real qs) l') in1893match Q.compare r qu with1894| Ord.Lt ->18951896let res = Chg r br (Chg qu bu res) in1897res1898| Ord.Gt ->1899res1900| Ord.Eq ->1901match br, bu with1902| Large, Strict ->1903let res = Sin qu res in1904res1905| _ ->1906res1907end1908end1909| Chg qs b l' ->1910let qu = (op.uq u qs) in1911let bbu = add_bound b bu in1912let res = (op_si_interval_on op bu u v bv l') in1913match Q.compare r qu with1914| Ord.Lt ->1915let res2 = Chg r br (Chg qu bbu res) in1916res21917| Ord.Gt ->1918let lemma smaller_true (q:Q.t) =1919requires { not (cmp r br q) }1920ensures { mem_if True q res }1921lt_bound_is_mem True (Q.real q) res1922in1923res1924| Ord.Eq ->1925match br, bbu with1926| Large, Strict ->1927let res = Sin qu res in1928res1929| _ ->1930res1931end1932end1933| Inf ->1934Chg r br Inf1935end1936Valid (33ms) (cvc5)1937let op_si_interval' (op: siop) if_ l (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t): (result:t'')1938requires { si op }1939requires { (u <. v) }1940requires { ordered' l }1941requires { in_siop op u }1942requires { in_siop op v }1943requires { foot_if op.minr op.maxr l }1944ensures { ordered' result }1945ensures {1946forall q q'. (mem_if if_ q l /\ cmp u bu q' /\ (not cmp v bv q')) -> mem_if if_ (op.ur q' q) result1947}1948ensures { forall q. (lt_bound' q l) -> (lt_bound' (op.ur u q) result) }1949=1950if if_ then op_si_interval_on op bu u v bv l else op_si_interval_off op bu u v bv l19511952Valid (157ms) (cvc4)1953let op_si_interval (op: siop) l (bu:Bound.t) (u:Q.t) (v:Q.t) (bv:Bound.t): (result:t)1954requires { si op }1955requires { (u <. v) }1956requires { in_siop op u }1957requires { in_siop op v }1958requires { foot op.minr op.maxr l.a }1959ensures {1960forall q q'. (mem q l.a /\ cmp u bu q' /\ (not cmp v bv q')) -> mem (op.ur q' q) result.a1961}1962=1963match l.a with1964| On l ->1965let res = op_si_interval_on op bu u v bv l in1966{ a = On res }1967| Off l ->1968let w = not_bottom' False l in1969let l = (op_si_interval_off op bu u v bv l) in1970assert { mem_if False (op.ur (u*.0.5+.v*.0.5) w) l };1971{ a = Off l }1972end1973197419751976Valid (385ms) (colibri2 6) (cvc4) (cvc5 18) (split_vc 3) (depth 2)1977let rec op_si_minus_inf (op: siop) (if_:bool) (v: Q.t) (bv:Bound.t) l: (result:t'')1978requires { si op }1979requires { ordered' l }1980requires { in_siop op v }1981requires { foot_if op.minr op.maxr l }1982ensures { ordered' result }1983ensures {1984forall q q'. ((not cmp v bv q) /\ mem_if if_ q' l) -> mem_if True (op.ur q q') result1985}1986ensures { forall q'' q' q. lt_bound' q l -> (not cmp v bv q') -> q'' <=. q -> mem_if True (op.ur q' q'') result }1987variant { length' l } =1988match l with1989| Sin qs Inf -> if if_ then Inf else Chg (op.uq v qs) bv Inf1990| Sin _ l' -> op_si_minus_inf op if_ v bv l'1991| Chg qs bs Inf -> if if_ then Chg (op.uq v qs) (add_bound bv bs) Inf else Inf1992| Chg _ _ l' -> op_si_minus_inf op (notb if_) v bv l'1993| Inf -> Inf1994end1995Valid (767ms) (colibri2 4) (cvc5 51) (split_vc 3) (depth 2)1996let rec op_si_on (op: siop) (if2:bool) (u:Q.t) (bu:Bound.t) (l1:t'') (l2:t'') : (result:t'')1997requires { si op }1998requires { lt_bound' u l1 }1999requires { in_siop op u }2000requires { foot_if op.minr op.maxr l1 }2001requires { foot_if op.minr op.maxr l2 }2002requires { ordered' l1 }2003requires { ordered' l2 }2004ensures { ordered' result }2005ensures { forall q q'. ((cmp u bu q /\ mem_if True q l1) /\ mem_if if2 q' l2) -> mem_if if2 (op.ur q q') result }2006ensures {2007forall q. lt_bound' q l2 -> lt_bound' (op.ur u q) result2008}2009variant { length' l1 }2010=2011match l1 with2012| Sin qs l1' ->2013let res1 = op_si_interval' op if2 l2 bu u qs Large in2014let res2 = op_si_on op if2 qs Strict l1' l2 in2015let res = union' if2 if2 res1 res2 in2016assert { forall q. (mem_if if2 q res1 \/ mem_if if2 q res2) -> mem_if if2 q res };2017res2018| Chg qs bq Inf ->2019op_si_interval' op if2 l2 bu u qs bq2020| Chg qs bq l1' ->2021let res1 = op_si_interval' op if2 l2 bu u qs bq in2022let res2 = op_si_off op if2 l1' l2 in2023let res = union' if2 if2 res1 res2 in2024assert { forall q. (mem_if if2 q res1 \/ mem_if if2 q res2) -> mem_if if2 q res };2025assert { forall q. (cmp q (inv_bound bq) qs \/ mem_if False q l1') -> mem_if True q l1 };2026res2027| Inf -> if if2 then Inf else2028match l2 with2029| Sin q2 _ -> Chg (op.uq u q2) bu Inf2030| Chg q2 b2 _ -> Chg (op.uq u q2) (add_bound bu b2) Inf2031| Inf -> Inf2032end2033end2034Valid (757ms) (colibri2 4) (cvc5 28) (split_vc 2) (depth 2)2035with op_si_off (op : siop) if2 (l1:t'') (l2:t'') : (result:t'')2036requires { si op }2037requires { foot_if op.minr op.maxr l1 }2038requires { foot_if op.minr op.maxr l2 }2039requires { ordered' l1 }2040requires { ordered' l2 }2041requires { l1 <> Inf }2042ensures { ordered' result }2043ensures { forall q q'. (mem_if False q l1 /\ mem_if if2 q' l2) -> mem_if if2 (op.ur q q') result }2044ensures {2045forall q q'.2046(lt_bound' q l1) -> (lt_bound' q' l2) ->2047(lt_bound' (op.ur q q') result )2048}2049variant { length' l1 }2050=2051match l1 with2052| Sin qs Inf -> op_si_cst' op qs l22053| Sin qs l1' ->2054let res1 = op_si_cst' op qs l2 in2055let res2 = op_si_off op if2 l1' l2 in2056let res = union' if2 if2 res1 res2 in2057assert { forall q. (mem_if if2 q res1 \/ mem_if if2 q res2) -> mem_if if2 q res };2058res2059| Chg qs b l1' ->2060op_si_on op if2 qs b l1' l22061| Inf -> absurd2062end20632064Valid (200ms) (colibri2 71) (cvc4 2) (split_vc 2) (depth 2)2065let op_si (op : siop) u v: (result:t)2066requires { si op }2067requires { foot op.minr op.maxr u.a }2068requires { foot op.minr op.maxr v.a }2069ensures { sound2 memt op.ur u v result }2070=2071let op_si_on' (op : siop) (if2:bool) l1 l2: (result:t'')2072requires { si op }2073requires { foot_if op.minr op.maxr l1 }2074requires { foot_if op.minr op.maxr l2 }2075requires { ordered' l1 }2076requires { ordered' l2 }2077ensures { ordered' result }2078ensures {2079forall q q'. (mem_if True q l1 /\ mem_if if2 q' l2) -> mem_if True (op.ur q q') result2080}2081=2082match l1 with2083| Sin qs l1' ->2084let res1 = op_si_minus_inf op if2 qs Large l2 in2085let res2 = op_si_on op if2 qs Strict l1' l2 in2086let res = union' True if2 res1 res2 in2087assert { forall q. (mem_if True q res1 \/ mem_if if2 q res2) -> mem_if True q res };2088assert { forall q. (cmp q Strict qs \/ (cmp qs Strict q /\ mem_if True q l1')) -> mem_if True q l1 };2089res2090| Chg qs bq Inf ->2091op_si_minus_inf op if2 qs bq l22092| Chg qs bq l1' ->2093let res1 = op_si_minus_inf op if2 qs bq l2 in2094let res2 = op_si_off op if2 l1' l2 in2095let res = union' True if2 res1 res2 in2096assert { forall q. (mem_if True q res1 \/ mem_if if2 q res2) -> mem_if True q res };2097res2098| Inf -> Inf2099end2100in2101match u.a,v.a with2102| On u, On v -> { a = On (op_si_on' op True u v) }2103| On u, Off v -> { a = On (op_si_on' op False u v) }2104| Off u, On v -> { a = On (op_si_off op True u v) }2105| Off u, Off v ->2106let w = (op_si_off op False u v) in2107let ghost ux = not_bottom' False u in2108let ghost vx = not_bottom' False v in2109assert { mem_if False (op.ur ux vx) w };2110{ a = Off w }2111end2112Valid (151ms) (colibri2)2113let add u v: (result:t)2114ensures { sound2 memt (fun (x y:real) -> x +. y) u v result } =2115let op = { minr = I; maxr = I; ur = (+.); uq = Q.add } in2116op_si op u v21172118211921202121Valid (315ms) (colibri2)2122let rec find_max if_ l : option (Bound.t,Q.t) =2123requires { ordered' l }2124requires { l = Inf -> if_ }2125ensures { match result with2126| None -> true2127| Some (b,m) -> forall q. mem_if if_ q l -> cmp q b m2128end }2129ensures { match result with2130| None -> true2131| Some (_,m) -> forall q. lt_bound' q l -> q <. m2132end }2133variant { l }2134match l with2135| Sin q Inf -> if if_ then None else Some (Large,q)2136| Sin _ l -> find_max if_ l2137| Chg q bv Inf -> if if_ then Some (inv_bound bv, q) else None2138| Chg _ _ l -> find_max (notb if_) l2139| Inf -> None2140end2141Valid (138ms) (colibri2)2142let ghost compat_mul_lt (x1 x2 y:real) =2143requires { x1 <. x2 }2144requires { 0. <. y }2145ensures { x1 *. y <. x2 *. y } ()2146Valid (190ms) (colibri2)2147let ghost compat_mul_lt2 x1 (b:Bound.t) x2 y1 (c:Bound.t) y2 =2148requires { cmp x1 b x2 }2149requires { cmp y1 c y2 }2150requires { 0. <. x1 }2151requires { 0. <. y1 }2152ensures { cmp (x1 *. y1) (add_bound b c) (x2 *. y2) }2153(if pure { x1 = x2 } then () else2154compat_mul_lt x1 x2 y1);2155(if pure { y1 = y2 } then () else2156compat_mul_lt y1 y2 x2)2157Valid (97ms) (colibri2)2158let hd_on w : (q:Q.t,b:Bound.t,l:t'') =2159requires { w <> Inf }2160requires { ordered' w }2161requires { lt_bound' 0.0 w }2162ensures { ordered' l }2163ensures { lt_bound' (q *. 0.5) l }2164ensures { lt_bound' 0.0 l }2165ensures { 0.0 <. q }2166ensures { forall q'. mem_if True q' w -> (cmp q' b q \/ mem_if False q' l) }2167match w with2168| Inf -> absurd2169| Sin q l -> q, Strict, Chg q Strict l2170| Chg q bv l -> q, (inv_bound bv), l2171end2172Valid (404ms) (colibri2 74) (cvc5 35) (split_vc 2) (depth 2)2173let mul_off w x =2174requires { ordered' w }2175requires { ordered' x }2176requires { lt_bound' 0. w }2177requires { lt_bound' 0. x }2178(* ensures { lt_bound' (-1.) result } *)2179ensures { ordered' result }2180ensures {2181forall q q'. (mem_if False q w /\ mem_if False q' x) -> mem_if False (q*.q') result2182}2183match w, x with2184| Inf, _ | _, Inf -> Inf2185| (Sin q1 _ | Chg q1 _ _), (Sin q2 _ | Chg q2 _ _) ->2186let ghost m = min (Q.real q1) (Q.real q2) in2187let ghost ur' x y = match m <=. x, m <=. y with2188| True, True -> x *. y2189| False, True -> x -. m +. m *. y2190| True, False -> y -. m +. m *. x2191| False, False -> x -. m +. y -. m +. m *. m2192end2193in2194let op = { minr = R m; maxr = I; ur = ur'; uq = Q.mul } in2195assert { 0. <. m };2196let lemma inc2 (u v v':real)2197requires { v <. v' }2198ensures { op.ur u v <. op.ur u v' }2199= if m <=. u then begin2200if m <=. v then assert { u *. v <. u *. v' }2201else if m <=. v' then assert { m *. u <=. u *. v' }2202end else begin2203if m <=. v then assert { m *. v <. m *. v' }2204else if m <=. v' then begin2205assert { m *. v' -. m *. m = m *. (v' -. m) };2206assert { 0. <=. m *. (v' -. m) }2207end2208end2209in2210let lemma inc1 (u u' v:real)2211requires { u <. u' }2212ensures { op.ur u v <. op.ur u' v }2213= if m <=. v then begin2214if m <=. u then assert { u *. v <. u' *. v }2215else if m <=. u' then assert { m *. v <=. u' *. v }2216end else begin2217if m <=. u then assert { m *. u <. m *. u' }2218else if m <=. u' then assert { m *. m <=. m *. u' }2219end2220in2221first_bound_is_foot_if m (Q.real q1) w;2222first_bound_is_foot_if m (Q.real q2) x;2223op_si_off op False w x2224end2225Valid (225ms) (colibri2)2226let mul_near_zero if_w w xq xb =2227requires { ordered' w }2228requires { lt_bound' 0.0 w }2229requires { w <> Inf }2230requires { 0. <. xq }2231ensures { ordered' result }2232ensures { lt_bound' (-1.) result }2233ensures { forall q q'. 0. <. q -> mem_if if_w q w -> 0. <. q' -> cmp q' xb xq -> mem_if False (q *. q') result }2234match find_max if_w w with2235| None -> Chg (Q.of_int 0) Strict Inf2236| Some (wmb,wm) ->2237let lemma cmp_mul q q' =2238requires { 0. <. q }2239requires { cmp q wmb wm }2240requires { 0. <. q' }2241requires { cmp q' xb xq }2242ensures { 0. <. (q *. q') }2243ensures { cmp (q *. q') (add_bound wmb xb) (wm *. xq) }2244compat_mul_lt2 q wmb (Q.real wm) q' xb (Q.real xq)2245in2246Chg (Q.of_int 0) Strict (Chg (Q.mul wm xq) (inv_bound (add_bound wmb xb)) Inf)2247end2248Valid (368ms) (cvc4 3) (cvc5 66) (split_vc 2) (depth 2)2249let mul_aux w x =2250requires { ordered_presence 0. w }2251requires { ordered_presence 0. x }2252ensures { ordered' result }2253ensures { forall q,q'. mem_presence 0. q w -> mem_presence 0. q' x -> mem_if False (q *. q') result }2254match w, x with2255| Far Inf, _ | _, Far Inf -> Inf2256| Near Inf, _ | _, Near Inf -> Chg (Q.of_int 0) Strict Inf2257| Near w, Near x ->2258let (wq,wb,wl) = hd_on w in2259let (xq,xb,xl) = hd_on x in2260let l1 = mul_near_zero True w xq xb in2261let l2 = mul_near_zero True x wq wb in2262let l3 = mul_off wl xl in2263union' False False (union' False False l1 l2) l32264| Far w, Far x -> mul_off w x2265| Near w, Far x | Far x, Near w ->2266let (wq,wb,wl) = hd_on w in2267let l2 = mul_near_zero False x wq wb in2268let l3 = mul_off wl x in2269union' False False l2 l32270end2271Valid (590ms) (cvc4)2272let neg' l : t2273requires { ordered' l }2274requires { l <> Inf }2275ensures { forall q. (mem_if False q l) -> mem (-. q) result.a }2276=2277let negq (x:Q.t) ensures { result = -. x } = Q.sub (Q.of_int 0) x in2278let ghost c = pure { match l with Inf -> 0. | Sin q _ | Chg q _ _ -> q -. 1. end } in2279let op = Unary.{ ur = (fun x -> -.x); uq = negq; minr = I; maxr = I } in2280Unary.op_sd1_cst' op l Inf False c22812282Valid (1.2s) (colibri2 27) (cvc4 4) (cvc5 7) (split_vc 2) (depth 2)2283let mul u v: (result:t)2284ensures { sound2 memt (fun x y -> x *. y) u v result } =2285let uinf, zu, upos = split_at u in2286let vinf, zv, vpos = split_at v in2287let u1 = (union' False False (mul_aux uinf vinf) (mul_aux upos vpos)) in2288let u2 = (union' False False (mul_aux uinf vpos) (mul_aux upos vinf)) in2289let z = { a = Off (Sin (Q.of_int 0) Inf) } in2290let lemma prod_in (x y:real)2291requires { memt x u /\ memt y v }2292ensures { 0. <. x *. y -> mem_if False (x *. y) u1 }2293ensures { x *. y <. 0. -> mem_if False (-. (x *. y)) u2 }2294ensures { x *. y = 0. -> orb zu zv }2295= if 0. <. x then begin2296if 0. <. y then assert { 0. <. x *. y /\ mem_if False (x *. y) u1 }2297else if y <. 0. then begin2298assert { x *. (-. y) = -. (x *. y) /\ x *. y <. 0. };2299assert { mem_if False (x *. (-. y)) u2 }2300end2301end else if x <. 0. then begin2302if 0. <. y then begin2303assert { (-. x) *. y = -. (x *. y) /\ x *. y <. 0. };2304assert { mem_if False ((-. x) *. y) u2 }2305end else if y <. 0. then begin2306assert { (-. x) *. (-. y) = x *. y /\ 0. <. x *. y };2307assert { mem_if False ((-. x) *. (-. y)) u1 }2308end2309end2310in2311match u1, u2 with2312| Inf, Inf ->2313let ghost eu = not_bottom u in2314let ghost ev = not_bottom v in2315(* assert { (uinf = (Far Inf) \/ vinf = (Far Inf)) /\ (upos = (Far Inf) \/ vpos = (Far Inf)) }; assert { (uinf = (Far Inf) \/ vpos = (Far Inf)) /\ (upos = (Far Inf) \/ vinf = (Far Inf)) }; assert { uinf = (Far Inf) -> upos = (Far Inf) -> eu = 0. }; assert { vinf = (Far Inf) -> vpos = (Far Inf) -> ev = 0. }; assert { uinf = (Far Inf) -> upos = (Far Inf) -> zu }; assert { vinf = (Far Inf) -> vpos = (Far Inf) -> zv }; *)2321assert { eu = 0. \/ ev = 0. };2322assert { orb zu zv }; z2323| Inf, u2 -> let u2 = (neg' u2) in if orb zu zv then union u2 z else u22324| u1, Inf -> let u1 = { a = Off u1 } in if orb zu zv then union u1 z else u12325| u1, u2 -> let u1 = {a = Off u1} in let u2 = neg' u2 in let r = union u1 u2 in if orb zu zv then union r z else r2326end2327Valid (161ms) (cvc4)2328lemma inv_anti_monotonic: forall q r. 0. <. q -> q <. r -> (1. /. r) <. (1. /. q)23292330Valid (410ms) (colibri2 14) (cvc5 30) (split_vc) (depth 1)2331let inv_pos_off wl (ghost wq:real) =2332requires { ordered' wl }2333(* requires { ordered' acc } *)2334requires { 0. <. wq }2335requires { lt_bound' wq wl }2336(* requires { Unary.first_bound' (1. /. wq) acc } *)2337ensures { forall q. mem_if False q wl -> mem_if False (1. /. q) result }2338(* ensures { forall q. mem_if False q result -> 0. <. q } *)2339(* ensures { forall q. Unary.mem_if_not_top False q acc -> mem_if False q result } *)2340ensures { ordered' result }2341match wl with2342| Inf -> Inf2343| _ ->2344let function ur' r =2345if r <=. wq then (-. r) +. wq +. (1. /. wq) else 1. /. r2346in2347let uq' (q:Q.t) =2348ensures { wq <=. q -> result = ur' q }2349if Q.equal q (Q.of_int 0) then q else Q.div (Q.of_int 1) q2350in2351lt_bound_is_foot_if wq wq wl;2352let op = Unary.{2353uq = uq';2354ur = ur';2355minr = R wq; maxr = I;2356} in2357let lemma sdop v v' =2358requires { v <. v' }2359ensures { op.Unary.ur v' <. op.Unary.ur v }2360match v <=. wq, v' <=. wq with2361| True, True -> ()2362| True, False -> assert { 1. /. v' <. 1. /. wq }2363| False, True -> absurd2364| False, False -> assert { 1. /. v' <. 1. /. v }2365end2366in2367let v = Unary.op_sd1_cst' op wl Inf False wq in2368match v.a with2369| Off v -> v2370| On v' ->2371let rec ghost pos_bound l =2372requires { ordered' l }2373requires { lt_bound' 0. l }2374ensures { forall q. Unary.is_bound' q l -> 0. <. q }2375variant { l }2376match l with2377| Sin _ l -> pos_bound l2378| Chg _ _ l -> pos_bound l2379| Inf -> ()2380end2381in2382let rec ghost bound_pos l =2383requires { forall q. Unary.is_bound' q l -> 0. <. q }2384ensures { lt_bound' 0. l }2385variant { l }2386match l with2387| Sin q l' -> assert { Unary.is_bound' q l }; assert { forall q'. Unary.is_bound' q' l' -> Unary.is_bound' q' l }; bound_pos l'2388| Chg q _ l' -> assert { Unary.is_bound' q l }; assert { forall q'. Unary.is_bound' q' l' -> Unary.is_bound' q' l }; bound_pos l'2389| Inf -> ()2390end2391in2392pos_bound wl;2393assert { forall q. Unary.is_bound' q v' -> Unary.is_bound q v.a };2394assert { forall q. Unary.is_bound' q v' -> (exists q'. (q = ur' q' /\ Unary.is_bound' q' wl)) };2395assert { forall q. Unary.is_bound' q v' -> (exists q'. (q = ur' q' /\ 0. <. q')) };2396assert { forall q. Unary.is_bound' q v' -> 0. <. q };2397bound_pos v';2398Chg (Q.of_int 0) Strict v'2399end2400end2401Valid (345ms) (colibri2) (cvc4) (cvc5 13) (split_vc) (depth 1)2402let inv_pos u =2403requires { ordered_presence 0. u }2404ensures { forall q. mem_presence 0. q u -> mem_if False (1. /. q) result }2405(* ensures { forall q. mem_if False q result -> 0. <. q } *)2406ensures { ordered' result }2407match u with2408| Near Inf -> Chg (Q.of_int 0) Strict Inf2409| Near w ->2410let (wq,wb,wl) = hd_on w in2411let wq' = Q.div (Q.of_int 1) wq in2412let acc = Chg wq' wb Inf in2413assert { forall q. cmp 0. Strict q -> cmp q wb wq -> mem_if False (1. /. q) acc };2414let acc' = inv_pos_off wl (Q.real wq *. 0.5) in2415union' False False acc acc'2416| Far w ->2417let ghost wq = pure { match w with Inf -> 0.5 | Sin q _ | Chg q _ _ -> q *. 0.5 end } in2418inv_pos_off w wq2419end2420Valid (968ms) (colibri2 16) (cvc4 2) (split_vc 3) (depth 3)2421let inv (u:t): (result:t)2422ensures { sound1 memt (fun (x:real) -> 1. /. x) u result }2423=2424let uinf, zu, upos = split_at u in2425if zu then let x = { a = On Inf } in x2426else2427let uinf = inv_pos uinf in2428let upos = inv_pos upos in2429(* let negq (x:Q.t) ensures { result = -. x } = Q.sub (Q.of_int 0) x in let op = { ur = (fun x -> -.x); uq = negq; minr = I; maxr = I } in *)2431match upos, uinf with2432| Inf, Inf ->2433let ghost eu = not_bottom u in2434assert { eu = eu };2435absurd2436| Inf, u2 -> Unary.neg { a = Off u2 }2437| u1, Inf -> { a = Off u1 }2438| u1, u2 -> union (Unary.neg { a = Off u2 }) { a = Off u1 }2439end2440Valid (401ms) (colibri2 5) (cvc5 2) (split_vc 2) (depth 2)2441let div u v : t =2442ensures { sound2 memt (fun (x y:real) -> x /. y) u v result }2443if mem (Q.of_int 0) v then let x = { a = On Inf } in x2444else begin2445let v' = inv v in2446let r = mul u v' in2447let lemma m (q q':real)2448requires { mem q u.a }2449requires { mem q' v.a }2450ensures { mem (q /. q') r.a }2451= assert { mem (1. /. q') v'.a };2452assert { q /. q' = q *. (1. /. q') } in2453r2454end2455end2456end24572458scope NonIncreasing Valid (34ms) (cvc5)2459type unary = {2460uq: Q.t -> Q.t;2461ghost ur: real -> real;2462(* uq_left: Q.t -> (Bound.t,Q.t); *)2463(* uq_right: Q.t -> (Bound.t,Q.t); *)2464(* ghost ur_left: real -> Bound.t; *)2465(* ghost ur_right: real -> Bound.t; *)2466}2467invariant { forall v:Q.t. (ur v) = (uq v) }2468by {2469ur = (fun r -> r);2470uq = (fun q -> q);2471(* uq = (fun q -> Strict,q,Strict); *)2472(* ur_left = (fun _ -> Strict); *)2473(* ur_right = (fun _ -> Strict); *)2474}2475
unary non–strict increasing
predicate nsi1 (op:unary) =2478(forall v v' [op.ur v,op.ur v']. v <. v' -> (op.ur v) <=. (op.ur v'))2479Valid (307ms) (cvc5)2480lemma nsi1_cmp: forall op[nsi1 op]. nsi1 op ->2481(forall v v' b. cmp v b v' -> cmp (op.ur v) Large (op.ur v'))2482Valid (958ms) (colibri2 5) (cvc4) (cvc5 32) (split_vc 3) (depth 2)2483let rec op_nsi1_sin start (ghost rstart:real) if_ op (l:t'') : t''2484requires { ordered' l }2485requires { nsi1 op }2486requires { lt_bound' rstart l }2487requires { op.ur rstart = start }2488ensures { ordered' result }2489ensures { forall q. q <. start -> (lt_bound' q result) }2490ensures { forall q. (mem_if if_ q l) -> rstart <=. q -> mem_if False (op.ur q) result }2491ensures { mem_if False start result }2492variant { length' l }2493=2494match l with2495| Sin q l' ->2496let qop = (op.uq q) in2497if Q.equal start qop2498then op_nsi1_sin start rstart if_ op l'2499else if if_2500then begin2501Chg start Large (op_nsi1_wait if_ op l')2502end2503else Sin start (op_nsi1_sin qop (Q.real q) if_ op l')2504| Chg q _ l' ->2505(* assert { forall p. cmp q bv p = cmp (op.ur q) Large (op.ur p) };*)2506let qop = (op.uq q) in2507if Q.equal start qop then op_nsi1_sin start rstart (notb if_) op l'2508else if if_ then2509Chg start Large (op_nsi1_inter qop (Q.real q) op l')2510else2511Sin start (op_nsi1_sin qop (Q.real q) (notb if_) op l')2512| Inf -> if if_ then Chg start Large Inf else Sin start Inf2513end Valid (878ms) (colibri2 24) (split_vc) (depth 1)2514with op_nsi1_inter stop (ghost rstop:real) op (l:t'') : t''2515requires { ordered' l }2516requires { nsi1 op }2517requires { lt_bound' rstop l }2518requires { op.ur rstop = stop }2519ensures { ordered' result }2520ensures { forall q. q <. stop -> (lt_bound' q result) }2521ensures { forall q. (mem_if False q l) -> mem_if True (op.ur q) result }2522ensures { forall q. q <=. stop -> mem_if True q result }2523variant { length' l }2524=2525match l with2526| Sin q l' ->2527let qop = (op.uq q) in2528if Q.equal stop qop2529then op_nsi1_inter stop (Q.real q) op l'2530else2531Chg stop Strict (op_nsi1_sin qop (Q.real q) False op l')2532| Chg q _ l' ->2533(* assert { forall p. cmp q bv p = cmp (op.ur q) Large (op.ur p) };*)2534let qop = (op.uq q) in2535if Q.equal stop qop then begin2536let r = op_nsi1_wait True op l' in2537let lemma aux q' =2538requires { q' <. stop }2539ensures { mem_if True q' r }2540lt_bound_is_mem True q' r;2541in2542r2543end2544else2545Chg stop Strict (op_nsi1_sin qop (Q.real q) True op l')2546| Inf -> Chg stop Strict Inf2547end Valid (547ms) (colibri2)2548with op_nsi1_wait if_ op (l:t'') : t''2549requires { ordered' l }2550requires { nsi1 op }2551ensures { ordered' result }2552ensures { forall q q'. (lt_bound' q l) -> q' <. op.ur q -> (lt_bound' q' result) }2553ensures { forall q. (mem_if if_ q l) -> mem_if if_ (op.ur q) result }2554variant { length' l }2555=2556match l with2557| Sin q l' ->2558let qop = (op.uq q) in2559if if_ then op_nsi1_wait if_ op l'2560else op_nsi1_sin qop (Q.real q) False op l'2561| Chg q _ l' ->2562(*assert { forall p. cmp q bv p = cmp (op.ur q) Large (op.ur p) };*)2563let qop = (op.uq q) in2564if if_ then op_nsi1_inter qop (Q.real q) op l'2565else op_nsi1_sin qop (Q.real q) True op l'2566| Inf -> Inf2567end256825692570Valid (56ms) (colibri2)2571let op_nsi1 (op:unary) l2572requires { nsi1 op }2573ensures { sound1 memt op.ur l result }2574=2575match l.a with2576| On l ->2577{ a = On (op_nsi1_wait True op l) }2578| Off l ->2579let v = not_bottom' False l in2580let l = (op_nsi1_wait False op l) in2581assert { mem_if False (op.ur v) l };2582{ a = Off l }2583end25842585use real.Truncate2586use real.FromInt2587Valid (54ms) (colibri2)2588let ceil l =2589ensures { sound1 memt (fun (x:real) -> from_int (ceil x)) l result }2590let qceil x = Q.of_bigint (Q.ceil_z x) in2591let ghost rceil x = from_int (ceil x) in2592let op = { uq = qceil; ur = rceil } in2593op_nsi1 op l2594Valid (49ms) (colibri2)2595let floor l =2596ensures { sound1 memt (fun (x:real) -> from_int (floor x)) l result }2597let qfloor x = Q.of_bigint (Q.floor_z x) in2598let ghost rfloor x = from_int (floor x) in2599let op = { uq = qfloor; ur = rfloor } in2600op_nsi1 op l2601Valid (63ms) (colibri2)2602let truncate l =2603ensures { sound1 memt (fun (x:real) -> from_int (truncate x)) l result }2604let q x = Q.of_bigint (Q.truncate_z x) in2605let ghost r x = from_int (truncate x) in2606let op = { uq = q; ur = r } in2607op_nsi1 op l260826092610use real.MinMax2611Valid (69ms) (cvc5)2612let relu l =2613ensures { sound1 memt (fun (x:real) -> max 0. x) l result }2614let zero = Q.of_int 0 in2615let qrelu x = if Q.le zero x then x else zero in2616let ghost rrelu x = max 0. x in2617let op = { uq = qrelu; ur = rrelu } in2618op_nsi1 op l26192620end262126222623use list.List26242625scope Map2626type qbound =2627| BInf2628| BLarge Q.t2629| BStrict Q.t26302631predicate cmp_inf_qbound (qb:qbound) (r:real) =2632match qb with2633| BInf -> true2634| BLarge q -> Q.real q <=. r2635| BStrict q -> Q.real q <. r2636end26372638predicate cmp_sup_qbound (r:real) (qb:qbound) =2639match qb with2640| BInf -> true2641| BLarge q -> Q.real q >=. r2642| BStrict q -> Q.real q >. r2643end264426452646type interval =2647| Singleton Q.t2648| Inter qbound qbound2649Valid (26ms) (cvc5)2650type input_interval = { i : interval }2651invariant { match i with Inter (BLarge q1|BStrict q1) (BLarge q2|BStrict q2) -> q1 <=. q2 | _ -> true end }2652by { i = Inter BInf BInf }26532654type res_interval = list interval26552656predicate mem_interval (r:real) (i:interval) =2657match i with2658| Singleton q -> Q.real q = r2659| Inter qb1 qb2 ->2660cmp_inf_qbound qb1 r /\ cmp_sup_qbound r qb22661end26622663predicate mem_res_interval (r:real) (i:res_interval) =2664match i with2665| Nil -> false2666| Cons i1 l -> mem_interval r i1 \/ mem_res_interval r l2667end26682669let function qbound_of_bound q b =2670match b with2671| Strict -> BStrict q2672| Large -> BLarge q2673end26742675Valid (31ms) (cvc5)2676let function bound_of_qbound b =2677requires { b <> BInf }2678match b with2679| BStrict q -> (Strict,q)2680| BLarge q -> (Large,q)2681| BInf -> absurd2682end26832684Valid (1.3s) (colibri2)2685let convert_interval (i:interval) : t'2686ensures { forall r. mem_interval r i <-> mem r result }2687ensures { ordered result }2688=2689match i with2690| Singleton q -> Off (Sin q Inf)2691| Inter BInf BInf -> On Inf2692| Inter BInf bq ->2693let (b,q) = bound_of_qbound bq in On (Chg q (inv_bound b) Inf)2694| Inter bq BInf ->2695let (b,q) = bound_of_qbound bq in Off (Chg q b Inf)2696| Inter bq1 bq2 ->2697let (b1,q1) = bound_of_qbound bq1 in2698let (b2,q2) = bound_of_qbound bq2 in2699match Q.compare q1 q2, b1, b2 with2700| Ord.Eq, Large, Large -> Off (Sin q1 Inf)2701| Ord.Lt, _, _ -> Off (Chg q1 b1 (Chg q2 (inv_bound b2) Inf))2702| _ -> Off Inf2703end2704end2705Valid (66ms) (cvc5)2706let rec convert_res_interval (i:res_interval) : t'2707ensures { forall r. mem_res_interval r i <-> mem r result }2708ensures { ordered result }2709variant { i }2710=2711match i with2712| Nil -> Off Inf2713| Cons i1 Nil -> (convert_interval i1)2714| Cons i2 l -> (union_a (convert_interval i2) (convert_res_interval l))2715end2716Valid (67ms) (colibri2)2717type fmap = {2718f: input_interval -> input_interval -> res_interval;2719ghost fr: real -> real-> real;2720}2721invariant { forall i1 i2 r1 r2. mem_interval r1 i1.i -> mem_interval r2 i2.i -> mem_res_interval (fr r1 r2) (f i1 i2) }2722by { f = (fun x _ -> Cons x.i Nil); fr = (fun i _ -> i) }27232724predicate qlt_bound' (q:qbound) (l:t'') =2725match q with2726| BInf -> true2727| BLarge q | BStrict q -> lt_bound' q l2728end2729Valid (363ms) (colibri2 5) (cvc4 5) (cvc5 57) (split_vc 3) (depth 2)2730let map (fm:fmap) (l1:t) (l2:t) : t2731ensures { sound2 memt fm.fr l1 l2 result }2732=2733let rec map_cst_left_on (i1:input_interval) (q2:qbound) (l2:t'') : t'2734requires { ordered' l2 }2735requires { qlt_bound' q2 l2 }2736ensures { forall r1 r2. mem_interval r1 i1.i -> cmp_inf_qbound q2 r2 -> mem_if True r2 l2 -> mem (fm.fr r1 r2) result }2737ensures { ordered result }2738variant { l2 }2739=2740match l2 with2741| Inf ->2742let u = fm.f i1 {i=Inter q2 BInf} in2743(convert_res_interval u)2744| Sin q l2 ->2745let q3 = (BStrict q) in2746let u = fm.f i1 {i=Inter q2 q3} in2747union_a (convert_res_interval u) (map_cst_left_on i1 q3 l2)2748| Chg q b l2 ->2749let u = fm.f i1 {i=Inter q2 (qbound_of_bound q (inv_bound b))} in2750union_a (convert_res_interval u) (map_cst_left_off i1 l2)2751end2752with map_cst_left_off (i1:input_interval) (l2:t'') : t'2753requires { ordered' l2 }2754ensures { forall r1 r2. mem_interval r1 i1.i -> mem_if False r2 l2 -> mem (fm.fr r1 r2) result }2755ensures { ordered result }2756variant { l2 }2757=2758match l2 with2759| Inf -> Off Inf2760| Sin q l2 ->2761let u = fm.f i1 {i=Singleton q} in2762union_a (convert_res_interval u) (map_cst_left_off i1 l2)2763| Chg q b l2 ->2764map_cst_left_on i1 (qbound_of_bound q b) l22765end2766in2767let map_cst_left (i1:input_interval) (l2:t) : t'2768ensures { forall r1 r2. mem_interval r1 i1.i -> mem r2 l2.a -> mem (fm.fr r1 r2) result }2769ensures { ordered result }2770=2771match l2.a with2772| On l2 -> map_cst_left_on i1 BInf l22773| Off l2 -> map_cst_left_off i1 l22774end2775in2776let rec map_cst_on (q1:qbound) (l1:t'') (l2:t) : t'2777requires { ordered' l1 }2778requires { qlt_bound' q1 l1 }2779ensures { forall r1 r2. cmp_inf_qbound q1 r1 -> mem_if True r1 l1 -> mem r2 l2.a -> mem (fm.fr r1 r2) result }2780ensures { ordered result }2781variant { l1 }2782=2783match l1 with2784| Inf -> map_cst_left {i=Inter q1 BInf} l22785| Sin q l1' ->2786let q2 = (BStrict q) in2787let u1 = map_cst_left {i=Inter q1 q2} l2 in2788let u2 = map_cst_on q2 l1' l2 in2789union_a u1 u22790| Chg q b l1' ->2791let u1 = map_cst_left {i=Inter q1 (qbound_of_bound q (inv_bound b))} l2 in2792let u2 = map_cst_off l1' l2 in2793union_a u1 u22794end2795with map_cst_off (l1:t'') (l2:t) : t'2796requires { ordered' l1 }2797ensures { forall r1 r2. mem_if False r1 l1 -> mem r2 l2.a -> mem (fm.fr r1 r2) result }2798ensures { ordered result }2799variant { l1 }2800=2801match l1 with2802| Inf -> Off Inf2803| Sin q l1' ->2804let u1 = map_cst_left {i=Singleton q} l2 in2805let u2 = map_cst_off l1' l2 in2806union_a u1 u22807| Chg q b l1' -> map_cst_on (qbound_of_bound q b) l1' l22808end2809in2810let ghost r1 = not_bottom l1 in2811let ghost r2 = not_bottom l2 in2812match l1.a with2813| On l1 ->2814let m = map_cst_on BInf l1 l2 in2815assert { mem (fm.fr r1 r2) m };2816{ a = m }2817| Off l1 ->2818let m = map_cst_off l1 l2 in2819assert { mem (fm.fr r1 r2) m };2820{ a = m }2821end28222823scope UnaryFold Valid (40ms) (cvc5)2824type fmap 'a = {2825f: interval -> 'a;2826union: 'a -> 'a -> 'a;2827ghost inv: real -> 'a -> bool;2828}2829invariant { forall i1 r1. mem_interval r1 i1 -> inv r1 (f i1) }2830invariant { forall a1 a2. forall r. (inv r a1 \/ inv r a2) -> inv r (union a1 a2) }2831by (2832let v = any 'a ensures { result = result } in2833{ f = (fun _ -> v); inv = (fun _ _ -> true); union = (fun x _ -> x) })2834Valid (1.4s) (colibri2 2) (cvc5 15) (split_vc) (depth 1)2835let map (fm:fmap 'a) (l1:t) : 'a2836ensures { forall r1. mem r1 l1.a -> fm.inv r1 result }2837=2838let rec map_cst_left_on (q2:qbound) (l2:t'') : 'a2839requires { ordered' l2 }2840ensures { forall r2. cmp_inf_qbound q2 r2 -> mem_if True r2 l2 -> fm.inv r2 result }2841variant { l2 }2842=2843match l2 with2844| Inf ->2845fm.f (Inter q2 BInf)2846| Sin q l2 ->2847let q3 = (BStrict q) in2848let u = fm.f (Inter q2 q3) in2849fm.union u (map_cst_left_on q3 l2)2850| Chg q b l2 ->2851let u = fm.f (Inter q2 (qbound_of_bound q (inv_bound b))) in2852match l2 with2853| Inf -> u2854| _ -> fm.union u (map_cst_left_off l2)2855end2856end2857with map_cst_left_off (l2:t'') : 'a2858requires { ordered' l2 }2859requires { l2 <> Inf }2860ensures { forall r2. mem_if False r2 l2 -> fm.inv r2 result }2861variant { l2 }2862=2863match l2 with2864| Inf -> absurd2865| Sin q Inf -> fm.f (Singleton q)2866| Sin q l2 ->2867let u = fm.f (Singleton q) in2868fm.union u (map_cst_left_off l2)2869| Chg q b l2 ->2870map_cst_left_on (qbound_of_bound q b) l22871end2872in2873match l1.a with2874| On l1 ->2875map_cst_left_on BInf l12876| Off l1 ->2877map_cst_left_off l12878end28792880end28812882scope Unary Valid (379ms) (cvc5)2883type fmap = {2884f: interval -> res_interval;2885ghost fr: real -> real;2886}2887invariant { forall i1 r1. mem_interval r1 i1 -> mem_res_interval (fr r1) (f i1) }2888invariant { forall i1. f i1 <> Nil }2889by { f = (fun i -> Cons i Nil); fr = (fun i -> i) }2890Valid (25ms) (colibri2)2891type t'_ordered = { u : t' }2892invariant { ordered u }2893by { u = On Inf }2894Valid (155ms) (cvc4)2895let map (fm:fmap) (l1:t) : t2896ensures { sound1 memt fm.fr l1 result }2897=2898let predicate inv (r:real) (u':t'_ordered) = pure { mem (fm.fr r) u'.u } in2899let f i =2900ensures { forall r1. mem_interval r1 i -> inv r1 result }2901{u=convert_res_interval (fm.f i)}2902in2903let union x y =2904ensures { forall r1. (inv r1 x \/ inv r1 y) -> inv r1 result }2905{u=union_a x.u y.u}2906in2907let fmap' = { UnaryFold.f = f;2908UnaryFold.union = union;2909UnaryFold.inv = inv;2910}2911in2912let ghost r1 = not_bottom l1 in2913let m = UnaryFold.map fmap' l1 in2914assert { mem (fm.fr r1) m.u };2915{ a = m.u }2916end291729182919end2920Valid (408ms) (colibri2)2921let ghost not_bottom_lt_bound (q':real) (if_:bool) (l:t'') : real2922requires { ordered' l }2923requires { lt_bound' q' l }2924requires { l = Inf -> if_ }2925ensures { mem_if if_ result l }2926ensures { q' <. result }2927=2928if if_ then2929match l with2930| (Sin q _) -> (Q.real q*.0.5+.q'*.0.5)2931| (Chg q _ _) -> (Q.real q*.0.5+.q'*.0.5)2932| Inf -> q' +. 1.2933end2934else2935match l with2936| (Sin q _) -> Q.real q2937| (Chg q _ (Sin q' _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)2938| (Chg q _ (Chg q' _ _)) -> (Q.real q*.0.5+.Q.real q'*.0.5)2939| (Chg q _ Inf) -> (Q.real q+.1.)2940| Inf -> absurd2941end2942
Square
use real.Square2946Valid (1.2s) (colibri2 22) (cvc4 4) (cvc5 21) (split_vc) (depth 1)2947let square_backward l2948ensures { preimage1_opt memt (fun (x:real) -> sqr x) l result }2949=2950let _,zb,pos = Increasing.split_at l in2951match zb, pos with2952| False, Increasing.Far Inf -> None2953| True, Increasing.Far Inf -> Some (singleton (Q.of_int 0))2954| _ ->2955let ghost function sqrt' (x:real) = if x <. 0. then x else sqrt x in2956let function sqrtq (v:Q.t) : Q.t ensures { result = sqrt' v } =2957if Q.lt v (Q.of_int 0) then v else Q.sqrt v in2958let lemma sqrt_op (v: Q.t)2959requires { in_infr (R 0.) v I }2960ensures { sqrt' v = sqrtq v } =2961()2962in2963let if_pos,pos = Increasing.open_presence pos in2964let _ = not_bottom_lt_bound 0. if_pos pos in2965let op = Increasing.{ Unary.minr = R 0.;2966Unary.maxr = I;2967Unary.ur = sqrt';2968Unary.uq = sqrtq } in2969Increasing.lt_bound_is_foot_if 0. 0. pos;2970let r = Increasing.Unary.op_si1_cst' op if_pos pos in2971assert { forall q. 0. <. q -> (mem (sqr q) l.a) -> mem_if if_pos q r };2972let r = { a = Off (Increasing.union_bzero zb if_pos r) } in2973assert { forall q. 0. <=. q -> (mem (sqr q) l.a) -> mem q r.a };2974let rn = Increasing.Unary.neg r in2975assert { forall q. mem q r.a -> mem (-. q) rn.a };2976assert { forall q. q <. 0. -> (mem (sqr q) l.a) -> mem (-. q) r.a2977by sqr (-. q) = sqr q };2978let res = union rn r in2979assert { forall q. mem q res.a <-> (mem q rn.a \/ mem q r.a) };2980assert { forall q. (mem (sqr q) l.a) -> mem q res.a2981by q <. 0. -> mem q rn.a by -. (-. q) = q };2982Some res2983end29842985use real.FromInt2986Valid (4.5s) (colibri2 5) (split_vc 3) (depth 3)2987let ceilb q b : Q.t2988ensures { Real.is_integer (Q.real result) }2989ensures { cmp q b result }2990ensures { forall r. cmp q b r -> r <. result -> not (Real.is_integer r) }2991=2992match b with2993| Large -> Q.of_bigint (Q.ceil_z q)2994| Strict -> if Q.is_integer q then (Q.add q (Q.of_int 1)) else Q.of_bigint (Q.ceil_z q)2995end2996Valid (123ms) (colibri2)2997let floorb q b : Q.t2998ensures { Real.is_integer (Q.real result) }2999ensures { cmp result b q }3000ensures { forall r. cmp r b q -> result <. r -> not (Real.is_integer r) }3001=3002match b with3003| Large -> Q.of_bigint (Q.floor_z q)3004| Strict -> if Q.is_integer q then (Q.sub q (Q.of_int 1)) else Q.of_bigint (Q.floor_z q)3005end3006Valid (161ms) (cvc4)3007type reducer = {3008ghost red_min: infr;3009ghost red_is_in: real -> bool;3010red_is_integer: Q.t -> bool;3011red_floorb: Q.t -> Bound.t -> Q.t;3012red_ceilb: Q.t -> Bound.t -> Q.t;3013}3014invariant { forall q. red_is_integer q <-> red_is_in q }3015invariant { forall q b. (lt_infr red_min (R (Q.real q))) -> red_is_in (red_floorb q b) }3016invariant { forall q b. (le_infr red_min (R (Q.real q))) -> red_is_in (red_ceilb q b) }3017invariant { forall q b. (lt_infr red_min (R (Q.real q))) -> cmp (red_floorb q b) b q }3018invariant { forall q b. (le_infr red_min (R (Q.real q))) -> cmp q b (red_ceilb q b) }3019invariant { forall q:Q.t.forall b r. (lt_infr red_min (R (Q.real q))) -> cmp r b q -> (red_floorb q b) <. r -> not (red_is_in r) }3020invariant { forall q:Q.t.forall b r. (le_infr red_min (R (Q.real q))) -> cmp q b r -> r <. (red_ceilb q b) -> not (red_is_in r) }3021by { red_is_in = pure { Real.is_integer }; red_is_integer = Q.is_integer; red_floorb = floorb; red_ceilb = ceilb; red_min = I }3022Valid (7.8s) (colibri2 63) (cvc4 2) (cvc5 13) (split_vc 5) (depth 2)3023let reduce_generic (op:reducer) (num:t) : option t3024requires { le_infr_bound op.red_min num.a }3025ensures { restrict memt op.red_is_in num result } =3026let add_on start q l3027requires { ordered' l }3028requires { lt_bound' q l }3029requires { le_bound' start l }3030ensures { ordered' result }3031ensures { forall r. start <=. r <=. q -> mem_if False r result }3032ensures { forall r. mem_if False r l -> mem_if False r result }3033ensures { le_bound' start result }3034=3035match Q.compare q start with3036| Ord.Lt -> l3037| Ord.Eq -> Sin start l3038| Ord.Gt -> Chg start Large (Chg q Strict l)3039end3040in3041let rec aux_on (op:reducer) (ghost b:Bound.t) (ghost before: real) (start:Q.t) (num:t''): t''3042requires { lt_infr_bound' op.red_min num }3043requires { ordered' num }3044requires { lt_bound' before num }3045requires { cmp before b start }3046requires { forall r. cmp before b r -> r <. start -> not (op.red_is_in r) }3047requires { op.red_is_in start }3048ensures { forall n. start <=. n -> mem_if True n num -> op.red_is_in n3049-> mem_if False n result }3050ensures { le_bound' start result }3051ensures { ordered' result }3052variant {num}3053= match num with3054| Sin q l ->3055let qf = op.red_floorb q Strict in3056let qc = op.red_ceilb q Strict in3057assert { start <=. qc };3058assert { forall x. qf <. x -> x <. q -> not (op.red_is_in x) };3059assert { forall x. q <. x -> x <. qc -> not (op.red_is_in x) };3060assert { forall x. qf <. x <=. qc -> op.red_is_in x -> (x = q \/ x = qc)};3061if pure { qf <. start } then begin3062assert { op.red_is_in start };3063assert { qf <. start <=. qc };3064assert { Q.real start = Q.real q \/ Q.real start = Q.real qc }3065end;3066let l' = aux_on op Strict (Q.real q) qc l in3067assert { forall n. start <=. n -> mem_if True n num -> op.red_is_in n -> (mem_if True n l \/ start <=. n <=. qf) };3068add_on start qf l'3069| Chg q b l ->3070let qf = op.red_floorb q (Bound.inv_bound b) in3071assert { forall x. qf <. x -> x <. q -> not (op.red_is_in x) };3072let l' = aux_off op l in3073add_on start qf l'3074| Inf -> Chg start Large Inf3075end3076with aux_off (op:reducer) (num:t'') : t''3077requires { le_infr_bound' op.red_min num }3078requires { ordered' num }3079ensures { forall n. mem_if False n num -> op.red_is_in n -> mem_if False n result }3080ensures { ordered' result }3081ensures { forall q. lt_bound' q num -> lt_bound' q result }3082ensures { forall before q. lt_bound' before num -> (forall r. before <. r <. q -> not (op.red_is_in r))3083-> le_bound' q result }3084variant {num}3085=3086match num with3087| Sin q l -> if op.red_is_integer q then Sin q (aux_off op l) else aux_off op l3088| Chg q b l ->3089let q' = op.red_ceilb q b in3090aux_on op b (Q.real q) q' l3091| Inf -> Inf3092end3093in3094let rec aux_on_inf (op:reducer) (num:t'') : t''3095requires { lt_infr_bound' op.red_min num }3096requires { ordered' num }3097ensures { forall n. mem_if True n num -> op.red_is_in n -> mem_if True n result }3098ensures { ordered' result }3099= match num with3100| Sin q num' ->3101let qf = op.red_floorb q Strict in3102let qc = op.red_ceilb q Strict in3103assert { forall x. qf <. x -> x <. q -> not (op.red_is_in x) };3104assert { forall x. q <. x -> x <. qc -> not (op.red_is_in x) };3105Chg qf Strict (aux_on op Strict (Q.real q) qc num')3106| Chg q b l ->3107let qf = op.red_floorb q (Bound.inv_bound b) in3108Chg qf Strict (aux_off op l)3109| Inf -> Inf3110end3111in3112match num.a with3113| On u -> Some { a = On (aux_on_inf op u) }3114| Off u -> (match aux_off op u with Inf -> None | u -> Some {a=Off u} end)3115end3116Valid (1.6s) (colibri2)3117let reduce_integers (l:t) : option t3118ensures { restrict memt (fun (x:real) -> Real.is_integer x) l result } =3119reduce_generic3120{ red_is_in = pure { Real.is_integer }; red_is_integer = Q.is_integer; red_floorb = floorb; red_ceilb = ceilb; red_min = I; }3121l312231233124scope ED3125use real.Abs3126Valid (342ms) (cvc5)3127lemma div_mod_e: forall a b. b <> 0. -> a = b *. (from_int (Real.div_e a b)) +. (Real.mod_e a b) Valid (355ms) (colibri2 4) (cvc5) (split_vc) (depth 1)3128let lemma mod_e (a b:real)3129requires { b <> 0. }3130ensures { 0. <=. (Real.mod_e a b) <. abs b }3131= if b >. 0. then begin3132assert { let d = from_int (Real.div_e a b) in d <=. a /. b <. d +. 1. };3133assert { let d = from_int (Real.div_e a b) in b *. d <=. a <. b *. d +. b }3134end else begin3135assert { let d = from_int (Real.div_e a b) in d -. 1. <. a /. b <=. d };3136assert { let d = from_int (Real.div_e a b) in b *. d <=. a <. b *. d -. b }3137end31383139function div_e_real(x :real) (y:real) : real = from_int (Real.div_e x y)3140Valid (1.0s) (colibri2) (cvc4 2) (cvc5 10) (split_vc) (depth 1)3141let ghost div_real_monotonies () : unit3142ensures { forall xm xM ym yM. 0. <. xm <=. xM -> 0. <. ym <=. yM ->31430. <=. div_e_real xm yM <=. div_e_real xM ym }3144ensures { forall xm xM ym yM. xm <=. 0. <=. xM -> 0. <. ym <=. yM ->3145div_e_real xm ym <=. 0. <=. div_e_real xM ym }3146ensures { forall xm xM ym yM. xm <=. xM <. 0. -> 0. <. ym <=. yM ->3147div_e_real xm ym <=. div_e_real xM yM <. 0. }3148ensures { forall xm xM ym yM. 0. <. xm <=. xM -> ym <=. yM <. 0. ->3149div_e_real xM yM <=. div_e_real xm ym <=. 0. }3150ensures { forall xm xM ym yM. xm <=. 0. <=. xM -> ym <=. yM <. 0. ->3151div_e_real xM yM <=. 0. <=. div_e_real xm yM }3152ensures { forall xm xM ym yM. xm <=. xM <. 0. -> ym <=. yM <. 0. ->31530. <. div_e_real xM ym <=. div_e_real xm yM } =3154
Proof
assert { forall xm xM ym yM. 0. <. xm <=. xM -> 0. <. ym <=. yM -> 0 <= Real.div_e xm yM <= Real.div_e xM ym };3156assert { forall xm xM ym yM. xm <=. 0. <=. xM -> 0. <. ym <=. yM -> Real.div_e xm ym <= 0 <= Real.div_e xM ym };3157assert { forall xm xM ym yM. xm <=. xM <. 0. -> 0. <. ym <=. yM -> Real.div_e xm ym <= Real.div_e xM yM < 0 };3158assert { forall x x' y. y <. 0. -> x <=. x' -> Real.div_e x y >= Real.div_e x' y };3159assert { forall xm xM ym yM. 0. <. xm <=. xM -> ym <=. yM <. 0. -> Real.div_e xM yM <= Real.div_e xm ym <= 0 };3160assert { forall xm xM ym yM. xm <=. 0. <=. xM -> ym <=. yM <. 0. -> Real.div_e xM yM <= 0 <= Real.div_e xm yM };3161assert { forall xm xM ym yM. xm <=. xM <. 0. -> ym <=. yM <. 0. -> 0 < Real.div_e xM ym <= Real.div_e xm yM }3162
QED
use real.Truncate3165use real.FromInt3166Valid (107ms) (cvc5)3167let ghost div_e_real_is_ceil_floor (): unit3168ensures { forall n d. d <> 0. ->3169let r = n /. d in3170let r = if d <. 0. then from_int (ceil r) else from_int (floor r) in3171div_e_real n d = r } =3172assert {3173forall n d. d <> 0. ->3174let r = n /. d in3175let r = if d <. 0. then (ceil r) else (floor r) in3176Real.div_e n d = r }31773178use real.Abs3179Valid (295ms) (cvc4)3180let ghost uniq_div_e_real (num:real) (den:real) (div:int) (mod:real) : unit3181requires { num = (from_int div)*.den +. mod }3182requires { 0. <=. mod <. abs den }3183ensures { Real.div_e num den = div }3184ensures { Real.mod_e num den = mod }3185= ()31863187Valid (160ms) (cvc5)3188let compare_interval (r:Q.t) (x:Map.input_interval) : Ord.t3189ensures { match result with3190| Ord.Eq -> Map.mem_interval r x.Map.i3191| Ord.Lt -> forall s. Map.mem_interval s x.Map.i -> r <. s3192| Ord.Gt -> forall s. Map.mem_interval s x.Map.i -> s <. r3193end }3194=3195Map.(match x.i with3196| Singleton q -> Q.compare r q3197| Inter qb1 qb2 ->3198if (match qb1 with BInf -> True | BLarge q -> Q.le q r3199| BStrict q -> (Q.lt q r) end) then3200if (match qb2 with BInf -> True | BLarge q -> Q.le r q3201| BStrict q -> (Q.lt r q) end) then Ord.Eq else Ord.Gt3202else Ord.Lt3203end)32043205(* Same as compare_interval but BStrict is considered as BLarge *)3206let function near_r (r:Q.t) (x:Map.input_interval) : Ord.t3207=3208Map.(match x.i with3209| Singleton q -> Q.compare r q3210| Inter qb1 qb2 ->3211if (match qb1 with BInf -> True | (BLarge q|BStrict q) -> (Q.le q r) end) then3212if (match qb2 with BInf -> True | (BLarge q | BStrict q) -> Q.le r q3213end) then Ord.Eq else Ord.Gt3214else Ord.Lt3215end)32163217let function get_min (x:Map.input_interval) : Map.qbound =3218match x.Map.i with3219| Map.Singleton q -> Map.BLarge q3220| Map.Inter q _ -> q3221end32223223let function get_max (x:Map.input_interval) : Map.qbound =3224match x.Map.i with3225| Map.Singleton q -> Map.BLarge q3226| Map.Inter _ q -> q3227end32283229Valid (2.2s) (colibri2 5) (cvc5 20) (split_vc 3) (depth 3)3230let fmap_div () : Map.fmap3231ensures { result.Map.fr = div_e_real }3232=3233Map.(3234let zero = (Q.of_int 0) in3235let fi (x:input_interval) (y:input_interval) : res_interval3236ensures { forall r1 r2. mem_interval r1 x.i -> mem_interval r2 y.i -> mem_res_interval (div_e_real r1 r2) result}3237=3238Map.(3239div_real_monotonies ();3240let x_for_rmin,y_for_rmin,x_for_rmax,y_for_rmax =3241match near_r zero y with3242| Ord.Eq -> BInf,BInf,BInf,BInf3243| Ord.Lt -> (* y positive *)3244let ymin = get_min y in3245let ymax = get_max y in3246let y_for_rmin, y_for_rmax =3247match near_r zero x with3248| Ord.Lt -> ymax,ymin3249| Ord.Eq -> ymin,ymin3250| Ord.Gt -> ymin,ymax3251end3252in3253get_min x,y_for_rmin,get_max x,y_for_rmax3254| Ord.Gt -> (* y negative *)3255let ymin = get_min y in3256let ymax = get_max y in3257let y_for_rmin, y_for_rmax =3258match near_r zero x with3259| Ord.Lt -> ymax,ymin3260| Ord.Eq -> ymax,ymax3261| Ord.Gt -> ymin,ymax3262end3263in3264get_max x,y_for_rmin,get_min x,y_for_rmax3265end in3266let rmin = match x_for_rmin, y_for_rmin with3267| BInf, _ -> BInf3268| _, BInf -> BLarge zero3269| (BLarge x|BStrict x),(BLarge y|BStrict y) ->3270BLarge (Q.div_e x y)3271end3272in3273let rmax = match x_for_rmax, y_for_rmax with3274| BInf, _ -> BInf3275| _, BInf -> BLarge zero3276| (BLarge x|BStrict x),(BLarge y|BStrict y) ->3277BLarge (Q.div_e x y)3278end3279in3280Cons (Inter rmin rmax) Nil3281)3282in3283{ fr = div_e_real; f = fi })3284Valid (68ms) (cvc5)3285let div_e_forward_bak (l1 l2:t) : t3286ensures { forall r1 r2. mem r1 l1.a -> mem r2 l2.a -> mem (div_e_real r1 r2) result.a } =3287Map.map (fmap_div ()) l1 l232883289Valid (1.7s) (colibri2 75) (cvc4 9) (cvc5 23) (split_vc 10) (depth 3)3290let div_e_forward (l1 l2:t) : t3291ensures { sound2 memt div_e_real l1 l2 result } =3292div_e_real_is_ceil_floor ();3293let neg2,b2,pos2 = Increasing.split_at l2 in3294if b2 then { a = On Inf }3295else3296let _ = not_bottom l2 in3297match neg2,pos2 with3298| Increasing.Far Inf, Increasing.Far Inf -> absurd3299| Increasing.Far Inf, _ ->3300let pos2 = { a = Off (Increasing.Binary.inv_pos pos2) } in3301assert { forall x. mem x l2.a -> mem (1. /. x) pos2.a };3302let p = Increasing.Binary.mul l1 pos2 in3303let r = NonIncreasing.floor p in3304let lemma m (r1 r2:real)3305requires { mem r1 l1.a }3306requires { mem r2 l2.a }3307ensures { mem (div_e_real r1 r2) r.a }3308= assert { 0. <. r2 };3309assert { mem (r1 *. (1. /. r2)) p.a };3310assert { r1 /. r2 = r1 *. (1. /. r2) } in3311r3312| _, Increasing.Far Inf ->3313let neg2 = Increasing.Binary.neg' (Increasing.Binary.inv_pos neg2) in3314assert { forall x. mem x l2.a -> x <. 0. };3315assert { forall x. x <. 0. -> -. (1. /. (-. x)) = 1. /. x };3316assert { forall x. mem x l2.a -> mem (1. /. x) neg2.a };3317let p = Increasing.Binary.mul l1 neg2 in3318let r = NonIncreasing.ceil p in3319let lemma m (r1 r2:real)3320requires { mem r1 l1.a }3321requires { mem r2 l2.a }3322ensures { mem (div_e_real r1 r2) r.a }3323= assert { r2 <. 0. };3324assert { mem (r1 *. (1. /. r2)) p.a };3325assert { r1 /. r2 = r1 *. (1. /. r2) } in3326r3327| _ ->3328let _ = Increasing.not_bottom_presence 0. pos2 in3329let _ = Increasing.not_bottom_presence 0. neg2 in3330let pos2 = { a = Off (Increasing.Binary.inv_pos pos2) } in3331let neg2 = Increasing.Binary.neg' (Increasing.Binary.inv_pos neg2) in3332assert { forall q q'. q' <> 0. -> q /. q' = q *. (1./.q') };3333assert { forall x. mem x l2.a -> (if x <. 0. then mem (1. /. x) neg2.a else mem (1. /. x) pos2.a) };3334let neg2 = (Increasing.Binary.mul l1 neg2) in3335let neg2 = (NonIncreasing.ceil neg2) in3336let pos2 = (NonIncreasing.floor (Increasing.Binary.mul l1 pos2)) in3337assert { forall y x. mem y l1.a -> mem x l2.a -> (if x <. 0. then mem (from_int (ceil (y /. x))) neg2.a else mem (from_int (floor (y /. x))) pos2.a) };3338union neg2 pos23339end3340334133423343Valid (1.9s) (colibri2 16) (cvc4 6) (cvc5 48) (split_vc 7) (depth 4)3344let mod_e_forward (l1 l2:t) : t3345ensures { sound2 memt (fun (x y:real) -> Real.mod_e x y) l1 l2 result } =3346let zero = (Q.of_int 0) in3347if mem zero l2 then { a = On Inf }3348else3349let _ = not_bottom l2 in3350match l2.a with3351| Off (Sin m Inf) ->3352let m = Q.abs m in3353let function fr (x:real) = pure { Real.mod_e x m } in3354let f (i:Map.interval) : list Map.interval3355ensures { forall r. Map.mem_interval r i -> Map.mem_res_interval (fr r) result }3356ensures { result <> Nil }3357=3358match i with3359| Map.Singleton r -> Cons (Map.Singleton (Q.mod_e r m)) Nil3360| Map.Inter Map.BInf _ | Map.Inter _ Map.BInf ->3361Cons (Map.Inter (Map.BLarge (Q.of_int 0)) (Map.BStrict m)) Nil3362| Map.Inter ((Map.BLarge rmin | Map.BStrict rmin) as bmin)3363((Map.BLarge rmax | Map.BStrict rmax) as bmax) ->3364let rmin_mod = match bmin with3365| Map.BInf -> absurd3366| Map.BLarge b -> Map.BLarge (Q.mod_e b m)3367| Map.BStrict b -> Map.BStrict (Q.mod_e b m)3368end3369in3370let rmax_mod = match bmax with3371| Map.BInf -> absurd3372| Map.BLarge b -> Map.BLarge (Q.mod_e b m)3373| Map.BStrict b -> Map.BStrict (Q.mod_e b m)3374end3375in3376let rmin_div = Q.div_e rmin m in3377let rmax_div = Q.div_e rmax m in3378div_real_monotonies ();3379if Q.equal rmin_div rmax_div then3380Cons (Map.Inter rmin_mod rmax_mod) Nil3381else if Q.equal (Q.add rmin_div (Q.of_int 1)) rmax_div3382then3383Cons (Map.Inter rmin_mod (Map.BStrict m))3384(Cons (Map.Inter (Map.BLarge (Q.of_int 0)) rmax_mod) Nil)3385else3386Cons (Map.Inter (Map.BLarge (Q.of_int 0)) (Map.BStrict m)) Nil3387end3388in3389let f = { Map.Unary.f = f; Map.Unary.fr = fr } in3390Map.Unary.map f l13391| _ ->3392match mem_min l2,mem_max l2 with3393| None, _ | _, None -> (ge zero)3394| Some (m,b), Some (m',b') ->3395let m = Q.abs m in3396let m' = Q.abs m' in3397let (m,b) = max_bound_sup m b m' b' in3398assert { forall r2. mem r2 l2.a -> cmp (abs r2) b m };3399{ a = Off (Chg (Q.of_int 0) Large (Chg m Large Inf))}3400end3401end3402Valid (1.5s) (colibri2 4) (cvc4 4) (cvc5 25) (split_vc 2) (depth 2)3403let mod_e_backward_num (num:t) (denl:t) (modl:t) : option t3404ensures { back2 memt (fun (x y:real) -> Real.mod_e x y) num denl modl result } =3405match denl.a, modl.a with3406| Off (Sin den Inf), Off (Sin mod Inf) ->3407
Only singleton in den and mod for now
if Q.equal den (Q.of_int 0) then Some num3408else if notb (andb ((Q.le (Q.of_int 0) mod)) ((Q.lt mod (Q.abs den)))) then None3409else3410let ghost den_sign = pure { if den <. 0. then -1 else 1 } in3411let predicate mod_is_in (num:real) =3412pure { mod = Real.mod_e num den }3413in3414let mod_is_integer (num:Q.t)3415ensures { mod_is_in num <-> result }3416=3417(Q.equal (Q.mod_e num den) mod)3418in3419let mod_floorb (num:Q.t) (b:Bound.t) : Q.t3420ensures { mod_is_in result }3421ensures { cmp result b num }3422ensures { forall r. cmp r b num -> result <. r -> not (mod_is_in r) }3423=3424let mod_e = Q.mod_e num den in3425(* num = (div_e num den)*den + (mod_e num den) *)3426(* num - mod_e num den + mod = (div_e num den)*den + mod *)3427let (r,div) = match Q.compare mod mod_e with3428| Ord.Eq -> match b with3429| Large -> num, pure {Real.div_e (Q.real num) (Q.real den)}3430| Strict -> (Q.sub num (Q.abs den)), pure {Real.div_e (Q.real num) (Q.real den) - den_sign }3431end3432| Ord.Lt -> (Q.add (Q.sub num mod_e) mod),pure {Real.div_e (Q.real num) (Q.real den) }3433| Ord.Gt -> (Q.sub (Q.add (Q.sub num mod_e) mod) (Q.abs den)),3434pure {Real.div_e (Q.real num) (Q.real den) - den_sign}3435end in3436uniq_div_e_real (Q.real r) (Q.real den) div (Q.real mod);3437r3438in3439let mod_ceilb (num:Q.t) (b:Bound.t) : Q.t3440ensures { mod_is_in result }3441ensures { cmp num b result }3442ensures { forall r. cmp num b r -> r <. result -> not (mod_is_in r) }3443=3444let mod_e = Q.mod_e num den in3445let (r,div) = match Q.compare mod mod_e with3446| Ord.Eq -> match b with3447| Large -> num, pure {Real.div_e (Q.real num) (Q.real den)}3448| Strict -> (Q.add num (Q.abs den)), pure {Real.div_e (Q.real num) (Q.real den) + den_sign}3449end3450| Ord.Lt -> (Q.add (Q.add (Q.sub num mod_e) mod) (Q.abs den)),3451pure {Real.div_e (Q.real num) (Q.real den) + den_sign}3452| Ord.Gt -> (Q.add (Q.sub num mod_e) mod),pure {Real.div_e (Q.real num) (Q.real den) }3453end in3454uniq_div_e_real (Q.real r) (Q.real den) div (Q.real mod);3455let lemma no_other (q:real)3456requires { cmp num b q } requires { q <. r }3457ensures { Real.mod_e q den <> mod } =3458let mod_q_aux = pure { q-.num+.mod_e } in3459let div_q = pure { if mod_q_aux <. abs (Q.real den) then Real.div_e (Q.real num) (Q.real den) else div } in3460let mod_q = pure { if mod_q_aux <. abs den then mod_q_aux else mod_q_aux -. abs den } in3461assert { if mod_q_aux <. abs den then mod_q <> mod3462else mod_q <. mod };3463uniq_div_e_real q (Q.real den) div_q mod_q;3464in3465r3466in3467let op =3468{ red_is_in = mod_is_in; red_is_integer = mod_is_integer;3469red_floorb = mod_floorb; red_ceilb = mod_ceilb; red_min = I;}3470in3471assert { forall d n. mem (Real.mod_e n d) modl.a -> (Real.mod_e n d) = mod };3472assert { forall d n. mem d denl.a -> mem (Real.mod_e n d) modl.a -> Real.mod_e n den = mod };3473assert { forall d n. mem d denl.a -> mem (Real.mod_e n d) modl.a -> op.red_is_in n };3474reduce_generic op num3475| _ -> Some num3476end34773478function div_t_real (a b:real) : real = from_int (Real.div_t a b)3479Valid (1.7s) (colibri2)3480let div_t_forward (l1 l2:t) : t3481ensures { sound2 memt div_t_real l1 l2 result } =3482NonIncreasing.truncate (Increasing.Binary.div l1 l2)3483Valid (955ms) (cvc4)3484lemma mod_t: forall a b. b <> 0. -> (-. abs b) <. (Real.mod_t a b) <. abs b3485Valid (487ms) (cvc4)3486let ghost uniq_div_t_real (num:real) (den:real) (div:int) (mod:real) : unit3487requires { num = (from_int div)*.den +. mod }3488requires { if num <. 0. then -. (abs den) <. mod <=. 0. else 0. <=. mod <. abs den }3489ensures { Real.mod_t num den = mod } = ()3490Valid (267ms) (cvc4)3491let ghost mod_t_nonneg (x den:real) : unit3492requires { den <> 0. }3493requires { 0. <=. x }3494ensures { 0. <=. Real.mod_t x den <. abs den }3495= ()3496Valid (1.2s) (colibri2) (cvc4) (cvc5) (split_vc) (depth 1)3497let ghost mod_t_neg (n d:real) : unit3498requires { d <> 0. }3499ensures { Real.mod_t (-. n) d = -. Real.mod_t n d }3500= assert { (-. n) /. d = -. (n /. d) };3501assert { Truncate.truncate (-. (n /. d)) = - Truncate.truncate (n /. d) }3502Valid (32ms) (colibri2)3503let ghost mod_t_nonpos (x den:real) : unit3504requires { den <> 0. }3505requires { x <=. 0. }3506ensures { -. abs den <. Real.mod_t x den <=. 0. }3507= mod_t_neg (-. x) den; mod_t_nonneg (-. x) den3508Valid (33ms) (colibri2)3509let ghost mod_t_le (x den:real) : unit3510requires { 0. <=. x }3511ensures { Real.mod_t x den <=. x }3512= if pure { den <> 0. } then mod_t_nonneg x den3513Valid (1.1s) (cvc4)3514let ghost mod_t_period (x y den:real) : unit3515requires { den <> 0. }3516requires { x <. y <. x +. abs den }3517ensures { Real.mod_t x den <> Real.mod_t y den }3518= let ghost k = pure { Real.div_t y den - Real.div_t x den } in3519assert { Real.mod_t x den = Real.mod_t y den -> y -. x = from_int k *. den };3520assert { k = 0 \/ k >= 1 \/ k <= -1 };3521assert { k >= 1 -> abs (from_int k *. den) >=. abs den };3522assert { k <= -1 -> abs (from_int k *. den) >=. abs den }35233524(* The Euclidean Definition of the Functions div and mod RAYMOND T. BOUTE *) Valid (1.1s) (colibri2) (cvc4 3) (cvc5 9) (split_vc) (depth 1)3525let ghost div_t_real_monotonies () : unit3526ensures { forall xm xM ym yM. 0. <. xm <=. xM -> 0. <. ym <=. yM ->35270. <=. div_t_real xm yM <=. div_t_real xM ym }3528ensures { forall xm xM ym yM. xm <=. 0. <=. xM -> 0. <. ym <=. yM ->3529div_t_real xm ym <=. 0. <=. div_t_real xM ym }3530ensures { forall xm xM ym yM. xm <=. xM <. 0. -> 0. <. ym <=. yM ->3531div_t_real xm ym <=. div_t_real xM yM <=. 0. }3532ensures { forall xm xM ym yM. 0. <. xm <=. xM -> ym <=. yM <. 0. ->3533div_t_real xM yM <=. div_t_real xm ym <=. 0. }3534ensures { forall xm xM ym yM. xm <=. 0. <=. xM -> ym <=. yM <. 0. ->3535div_t_real xM yM <=. 0. <=. div_t_real xm yM }3536ensures { forall xm xM ym yM. xm <=. xM <. 0. -> ym <=. yM <. 0. ->35370. <=. div_t_real xM ym <=. div_t_real xm yM } =3538
Proof
assert { forall xm xM ym yM. 0. <. xm <=. xM -> 0. <. ym <=. yM -> 0 <= Real.div_t xm yM <= Real.div_t xM ym };3540assert { forall xm xM ym yM. xm <=. 0. <=. xM -> 0. <. ym <=. yM -> Real.div_t xm ym <= 0 <= Real.div_t xM ym };3541assert { forall xm xM ym yM. xm <=. xM <. 0. -> 0. <. ym <=. yM -> Real.div_t xm ym <= Real.div_t xM yM <= 0 };3542assert { forall x x' y. y <. 0. -> x <=. x' -> Real.div_t x y >= Real.div_t x' y };3543assert { forall xm xM ym yM. 0. <. xm <=. xM -> ym <=. yM <. 0. -> Real.div_t xM yM <= Real.div_t xm ym <= 0 };3544assert { forall xm xM ym yM. xm <=. 0. <=. xM -> ym <=. yM <. 0. -> Real.div_t xM yM <= 0 <= Real.div_t xm yM };3545assert { forall xm xM ym yM. xm <=. xM <. 0. -> ym <=. yM <. 0. -> 0 <= Real.div_t xM ym <= Real.div_t xm yM }3546
QED
The cases of mod_t_forward where the interval spans two periods, apart so that the or–patterns of the bounds do not duplicate them
Valid (853ms) (colibri2 11) (cvc5) (split_vc) (depth 1)
3552 let ghost mod_t_two_neg (rmin rmax m mid:real) : unit
3553 requires { 0. <. m }
3554 requires { rmin <. 0. }
3555 requires { rmax <. 0. }
3556 requires { from_int (Real.div_t rmax m) = from_int (Real.div_t rmin m) +. 1. }
3557 requires { mid = from_int (Real.div_t rmin m) *. m }
3558 ensures { Real.mod_t rmax m <=. 0. }
3559 ensures { Real.mod_t rmin m <=. 0. }
3560 ensures { rmin <=. mid <. rmax }
3561 ensures { Real.mod_t mid m = 0. }
3562 ensures { forall q. mid <. q <. rmax -> -. m <. Real.mod_t q m <. Real.mod_t rmax m }
3563 ensures { forall q. rmin <. q <=. mid -> Real.mod_t rmin m <. Real.mod_t q m <=. 0. }
3564 = div_t_real_monotonies ();
3565 assert { Real.mod_t rmax m <=. 0. };
3566 assert { Real.mod_t rmin m <=. 0. };
3567 assert { rmin <=. mid <. rmax };
3568 assert { Real.mod_t mid m = 0. };
3569 assert { forall q. mid <. q <. rmax -> -. m <. Real.mod_t q m <. Real.mod_t rmax m };
3570 assert { forall q. rmin <. q <=. mid -> Real.mod_t rmin m <. Real.mod_t q m <=. 0. };
3571 ()
3572
Valid (1.2s) (colibri2 13) (cvc4 2) (cvc5) (split_vc) (depth 1)
3573 let ghost mod_t_two_pos (rmin rmax m mid:real) : unit
3574 requires { 0. <. m }
3575 requires { 0. <=. rmin }
3576 requires { 0. <=. rmax }
3577 requires { from_int (Real.div_t rmax m) = from_int (Real.div_t rmin m) +. 1. }
3578 requires { mid = from_int (Real.div_t rmax m) *. m }
3579 ensures { 0. <=. Real.mod_t rmax m }
3580 ensures { 0. <=. Real.mod_t rmin m }
3581 ensures { rmin <. mid <=. rmax }
3582 ensures { Real.mod_t mid m = 0. }
3583 ensures { forall q. mid <=. q <. rmax -> 0. <=. Real.mod_t q m <. Real.mod_t rmax m }
3584 ensures { forall q. rmin <. q <. mid ->
3585 from_int (Real.div_t rmin m) <=. q /. m <. from_int (Real.div_t rmin m) +. 1. }
3586 ensures { forall q. rmin <. q <. mid -> Real.div_t q m = Real.div_t rmin m }
3587 ensures { forall q. rmin <. q <. mid -> Real.mod_t rmin m <. Real.mod_t q m <. m }
3588 = div_t_real_monotonies ();
3589 assert { 0. <=. Real.mod_t rmax m };
3590 assert { 0. <=. Real.mod_t rmin m };
3591 assert { rmin <. mid <=. rmax };
3592 assert { Real.mod_t mid m = 0. };
3593 assert { forall q. mid <=. q <. rmax -> 0. <=. Real.mod_t q m <. Real.mod_t rmax m };
3594 assert { forall q. rmin <. q <. mid ->
3595 from_int (Real.div_t rmin m) <=. q /. m <. from_int (Real.div_t rmin m) +. 1. };
3596 assert { forall q. rmin <. q <. mid -> Real.div_t q m = Real.div_t rmin m };
3597 assert { forall q. rmin <. q <. mid -> Real.mod_t rmin m <. Real.mod_t q m <. m };
3598 ()
3599
Valid (550ms) (colibri2 12) (cvc4 2) (split_vc) (depth 1)
3600 let ghost mod_t_two_zero (rmin rmax m mid:real) : unit
3601 requires { 0. <. m }
3602 requires { rmin <. 0. }
3603 requires { 0. <=. rmax }
3604 requires { from_int (Real.div_t rmin m) = 0. }
3605 requires { from_int (Real.div_t rmax m) = from_int (Real.div_t rmin m) +. 1. }
3606 requires { mid = from_int (Real.div_t rmax m) *. m }
3607 ensures { 0. <=. Real.mod_t rmax m }
3608 ensures { Real.mod_t rmin m <=. 0. }
3609 ensures { rmin <. mid <=. rmax }
3610 ensures { Real.mod_t mid m = 0. }
3611 ensures { forall q. mid <=. q <. rmax -> Real.mod_t rmin m <. 0. <=. Real.mod_t q m <. Real.mod_t rmax m <. m }
3612 ensures { forall q. rmin <. q <. mid -> Real.mod_t rmin m <. Real.mod_t q m <. m }
3613 ensures { forall q. rmin <. q <. rmax -> Real.mod_t rmin m <. Real.mod_t q m <. m }
3614 = div_t_real_monotonies ();
3615 assert { 0. <=. Real.mod_t rmax m };
3616 assert { Real.mod_t rmin m <=. 0. };
3617 assert { rmin <. mid <=. rmax };
3618 assert { Real.mod_t mid m = 0. };
3619 assert { forall q. mid <=. q <. rmax -> Real.mod_t rmin m <. 0. <=. Real.mod_t q m <. Real.mod_t rmax m <. m };
3620 assert { forall q. rmin <. q <. mid -> Real.mod_t rmin m <. Real.mod_t q m <. m };
3621 assert { forall q. rmin <. q <. rmax -> Real.mod_t rmin m <. Real.mod_t q m <. m };
3622 ()
3623
Valid (588ms) (colibri2 12) (cvc4 2) (split_vc) (depth 1)
3624 let ghost mod_t_two_cross (rmin rmax m mid:real) : unit
3625 requires { 0. <. m }
3626 requires { rmin <. 0. }
3627 requires { 0. <=. rmax }
3628 requires { from_int (Real.div_t rmin m) <> 0. }
3629 requires { from_int (Real.div_t rmax m) = from_int (Real.div_t rmin m) +. 1. }
3630 requires { mid = from_int (Real.div_t rmin m) *. m }
3631 ensures { 0. <=. Real.mod_t rmax m }
3632 ensures { Real.mod_t rmin m <=. 0. }
3633 ensures { rmin <=. mid <. rmax }
3634 ensures { Real.mod_t mid m = 0. }
3635 ensures { forall q. mid <. q <. rmax -> -. m <. Real.mod_t q m <. Real.mod_t rmax m }
3636 ensures { forall q. rmin <. q <=. mid -> -. m <. Real.mod_t rmin m <. Real.mod_t q m <=. 0. <=. Real.mod_t rmax m }
3637 ensures { forall q. rmin <. q <. rmax -> -. m <. Real.mod_t q m <=. Real.mod_t rmax m }
3638 = div_t_real_monotonies ();
3639 assert { 0. <=. Real.mod_t rmax m };
3640 assert { Real.mod_t rmin m <=. 0. };
3641 assert { rmin <=. mid <. rmax };
3642 assert { Real.mod_t mid m = 0. };
3643 assert { forall q. mid <. q <. rmax -> -. m <. Real.mod_t q m <. Real.mod_t rmax m };
3644 assert { forall q. rmin <. q <=. mid -> -. m <. Real.mod_t rmin m <. Real.mod_t q m <=. 0. <=. Real.mod_t rmax m };
3645 assert { forall q. rmin <. q <. rmax -> -. m <. Real.mod_t q m <=. Real.mod_t rmax m };
3646 ()
3647
Valid (1.9s) (colibri2 166) (cvc4 60) (cvc5 13) (split_vc 19) (depth 5)
3648 let mod_t_forward (l1 l2:t) : t
3649 ensures { sound2 memt (fun (x y:real) -> Real.mod_t x y) l1 l2 result } =
3650 let zero = (Q.of_int 0) in
3651 if mem zero l2 then { a = On Inf }
3652 else
3653 let _ = not_bottom l2 in
3654 match l2.a with
3655 | Off (Sin m Inf) ->
3656 let function fr (x:real) = pure { Real.mod_t x m } in
3657 let m0 = m in
3658 let m = Q.abs m in
3659 let all = Cons (Map.Inter (Map.BStrict ((Q.sub zero m))) (Map.BStrict m)) Nil in
3660 let all_pos = Cons (Map.Inter (Map.BLarge zero) (Map.BStrict m)) Nil in
3661 let all_neg = Cons (Map.Inter (Map.BStrict ((Q.sub zero m))) (Map.BLarge zero)) Nil in
3662 let f (i:Map.interval) : list Map.interval
3663 ensures { forall r. Map.mem_interval r i -> Map.mem_res_interval (fr r) result }
3664 ensures { result <> Nil }
3665 =
3666 match i with
3667 | Map.Singleton r -> Cons (Map.Singleton (Q.mod_t r m)) Nil
3668 | Map.Inter Map.BInf Map.BInf -> all
3669 | Map.Inter Map.BInf (Map.BLarge r | Map.BStrict r) ->
3670 if Q.lt zero r then all else all_neg
3671 | Map.Inter (Map.BLarge r | Map.BStrict r) Map.BInf ->
3672 if Q.lt r zero then all else all_pos
3673 | Map.Inter ((Map.BLarge rmin | Map.BStrict rmin) as bmin)
3674 ((Map.BLarge rmax | Map.BStrict rmax) as bmax) ->
3675 let rmin_mod = match bmin with
3676 | Map.BInf -> absurd
3677 | Map.BLarge b -> Map.BLarge (Q.mod_t b m)
3678 | Map.BStrict b -> Map.BStrict (Q.mod_t b m)
3679 end
3680 in
3681 let rmax_mod = match bmax with
3682 | Map.BInf -> absurd
3683 | Map.BLarge b -> Map.BLarge (Q.mod_t b m)
3684 | Map.BStrict b -> Map.BStrict (Q.mod_t b m)
3685 end
3686 in
3687 let rmin_div = Q.div_t rmin m in
3688 let rmax_div = Q.div_t rmax m in
3689 div_t_real_monotonies ();
3690 assert { forall x. Real.mod_t x m = Real.mod_t x m0 };
3691 if Q.equal rmin_div rmax_div then
3692 Cons (Map.Inter rmin_mod rmax_mod) Nil
3693 else if Q.equal (Q.add rmin_div (Q.of_int 1)) rmax_div
3694 then
3695 match (Q.lt rmin zero), (Q.lt rmax zero) with
3696 | True, True ->
3697 let mid = pure { rmin_div *. m } in
3698 mod_t_two_neg (pure { Q.real rmin }) (pure { Q.real rmax }) (pure { Q.real m }) mid;
3699 Cons (Map.Inter rmin_mod (Map.BLarge zero))
3700 (Cons (Map.Inter (Map.BStrict (Q.sub zero m)) rmax_mod) Nil)
3701 | False, False ->
3702 let mid = pure { rmax_div *. m } in
3703 mod_t_two_pos (pure { Q.real rmin }) (pure { Q.real rmax }) (pure { Q.real m }) mid;
3704 Cons (Map.Inter rmin_mod (Map.BStrict m))
3705 (Cons (Map.Inter (Map.BLarge (Q.of_int 0)) rmax_mod) Nil)
3706 | False, True -> absurd
3707 | True, False ->
3708 assert { rmin <=. 0. <=. rmax };
3709 if Q.equal rmin_div zero then (
3710 let mid = pure { rmax_div *. m } in
3711 mod_t_two_zero (pure { Q.real rmin }) (pure { Q.real rmax }) (pure { Q.real m }) mid;
3712 Cons (Map.Inter (Map.BLarge (Q.mod_t rmin m)) (Map.BStrict m)) Nil
3713 )
3714 else (
3715 let mid = pure { rmin_div *. m } in
3716 mod_t_two_cross (pure { Q.real rmin }) (pure { Q.real rmax }) (pure { Q.real m }) mid;
3717 Cons (Map.Inter (Map.BStrict ((Q.sub zero m))) (Map.BLarge (Q.mod_t rmax m))) Nil
3718 )
3719 end
3720 else if Q.le zero rmin then begin
3721 let lemma lem (x:real) requires { rmin <=. x } ensures { 0. <=. fr x <. m } = mod_t_nonneg x (Q.real m0) in
3722 all_pos end
3723 else if Q.le rmax zero then begin
3724 let lemma lem (x:real) requires { x <=. rmax } ensures { -. m <. fr x <=. 0. } = mod_t_nonpos x (Q.real m0) in
3725 all_neg end
3726 else begin
3727 assert { forall x. -. m <. fr x <. m };
3728 all end
3729 end
3730 in
3731 let f = { Map.Unary.f = f; Map.Unary.fr = fr } in
3732 Map.Unary.map f l1
3733 | _ ->
3734 match mem_min l2,mem_max l2 with
3735 | None, _ | _, None -> { a = On Inf }
3736 | Some (m,b), Some (m',b') ->
3737 let m = Q.abs m in
3738 let m' = Q.abs m' in
3739 let (m,b) = max_bound_sup m b m' b' in
3740 assert { forall r2. mem r2 l2.a -> cmp (abs r2) b m };
3741 { a = Off (Chg (Q.sub zero m) Strict (Chg m Large Inf))}
3742 end
3743 end
3760
3761 (* let mod_t_forward (l1 l2:t) : t
ensures { forall r1 r2. mem r1 l1.a -> mem r2 l2.a -> mem (Real.mod_t r1 r2) result.a } =
let zero = (Q.of_int 0) in
if mem zero l2 then { a = On Inf }
else
let _ = not_bottom l2 in
match mem_min l2,mem_max l2 with
| None, _ | _, None -> { a = On Inf }
| Some (m0,b0), Some (m1,b1) ->
let m0' = Q.abs m0 in
let m1' = Q.abs m1 in
let (m,b) = max_bound_sup m0' b0 m1' b1 in
assert { forall r2. mem r2 l2.a -> cmp r2 b m };
assert { forall r2. cmp (-. m0') b0 r2 -> cmp (-. m1') b1 r2 -> cmp (-. m) b r2 };
assert { forall r2. mem r2 l2.a -> cmp (-. m) b r2 };
{ a = Off (Chg (Q.sub zero m) b (Chg m (inv_bound b) Inf)) }
end *)
3762
Valid (1.8s) (colibri2 66) (cvc4 9) (cvc5 38) (split_vc 28) (depth 4)
3763 let mod_t_backward_num (num:t) (denl:t) (modl:t) : option t
3764 ensures { back2 memt (fun (x y:real) -> Real.mod_t x y) num denl modl result } =
3765 match denl.a, modl.a with
3766 | Off (Sin den Inf), Off (Sin mod Inf) ->
3767 let zero = Q.of_int 0 in
3768 let f_pos mod (num:t) =
3769 requires { 0. <=. mod }
3770 requires { (le_infr_bound (R mod) num.a) }
3771 ensures { forall n d. mem n num.a -> mem d denl.a -> (Real.mod_t n d) = mod -> match result with None -> false | Some r -> mem n r.a end }
3772 (* Only singleton in den and mod for now *)
3773 if Q.equal den zero then Some num
3774 else if notb (andb ((Q.le (Q.sub zero (Q.abs den)) mod)) ((Q.lt mod (Q.abs den)))) then None
3775 else
3776 let ghost den_sign = if (Q.real den <. 0.) then (-1:int) else (1:int) in
3777 assert { from_int den_sign = abs den /. den };
3778 let ghost mod_min = R (Q.real mod) in
3779 let predicate mod_is_in (num:real) =
3780 pure { mod = Real.mod_t num den }
3781 in
3782 let mod_is_integer (num:Q.t)
3783 ensures { mod_is_in num <-> result }
3784 =
3785 (Q.equal (Q.mod_t num den) mod)
3786 in
3787 let mod_floorb (num:Q.t) (b:Bound.t) : Q.t
3788 ensures { (lt_infr mod_min (R num)) -> mod_is_in result }
3789 ensures { (lt_infr mod_min (R num)) -> cmp result b num }
3790 ensures { forall r. (lt_infr mod_min (R num)) -> cmp r b num -> result <. r -> not (mod_is_in r) }
3791 =
3792 let mod_t = Q.mod_t num den in
3793 if pure { 0. <=. num } then mod_t_nonneg (Q.real num) (Q.real den);
3794 (* num = (div_t num den)*den + (mod_t num den) *)
3795 let r,div =(
3796 (* num = (div_e num den)*den + (mod_e num den) *)
3797 (* num - mod_e num den + mod = (div_e num den)*den + mod *)
3798 match Q.compare mod mod_t with
3799 | Ord.Eq -> match b with
3800 | Large -> num, pure {Real.div_t (Q.real num) (Q.real den)}
3801 | Strict -> (Q.sub num (Q.abs den)), pure {Real.div_t (Q.real num) (Q.real den) - den_sign }
3802 end
3803 | Ord.Lt -> (Q.add (Q.sub num mod_t) mod),pure {Real.div_t (Q.real num) (Q.real den) }
3804 | Ord.Gt -> (Q.sub (Q.add (Q.sub num mod_t) mod) (Q.abs den)),
3805 pure {Real.div_t (Q.real num) (Q.real den) - den_sign}
3806 end) in
3807 if pure {mod <. num} then begin
3808 uniq_div_t_real (Q.real r) (Q.real den) div (Q.real mod)
3809 end;
3810 let lemma no_other (r':real)
3811 requires { mod <. num /\ r <. r' /\ cmp r' b num }
3812 ensures { not (mod_is_in r') } = mod_t_period (Q.real r) r' (Q.real den) in
3813 r
3814 in
3815 let mod_ceilb (num:Q.t) (b:Bound.t) : Q.t
3816 ensures { (le_infr mod_min (R num)) -> mod_is_in result }
3817 ensures { (le_infr mod_min (R num)) -> cmp num b result }
3818 ensures { forall r. (le_infr mod_min (R num)) -> cmp num b r -> r <. result -> not (mod_is_in r) }
3819 =
3820 let mod_t = Q.mod_t num den in
3821 if pure { 0. <=. num } then mod_t_nonneg (Q.real num) (Q.real den);
3822 let (r,div) = match Q.compare mod mod_t with
3823 | Ord.Eq -> match b with
3824 | Large -> num, pure {Real.div_t (Q.real num) (Q.real den)}
3825 | Strict -> (Q.add num (Q.abs den)), pure {Real.div_t (Q.real num) (Q.real den) + den_sign}
3826 end
3827 | Ord.Lt -> (Q.add (Q.add (Q.sub num mod_t) mod) (Q.abs den)),
3828 pure {Real.div_t (Q.real num) (Q.real den) + den_sign}
3829 | Ord.Gt ->
3830 let lemma no_other (r:real)
3831 requires { mod <=. num }
3832 requires { num <=. r <. num -. mod_t +. mod }
3833 ensures { mod_t <=. Real.mod_t r den <. mod } =
3834 let mod_r = pure { r-.num+.mod_t } in
3835 uniq_div_t_real r (Q.real den) pure {Real.div_t (Q.real num) (Q.real den)} mod_r;
3836 in
3837 (Q.add (Q.sub num mod_t) mod),pure {Real.div_t (Q.real num) (Q.real den) }
3838 end in
3839 if pure {mod <=. num} then begin
3840 uniq_div_t_real (Q.real r) (Q.real den) div (Q.real mod);
3841 end;
3842 let lemma no_other (r':real)
3843 requires { mod <=. num /\ r' <. r /\ cmp num b r' }
3844 ensures { not (mod_is_in r') } = mod_t_period r' (Q.real r) (Q.real den) in
3845 r
3846 in
3847 let op =
3848 { red_is_in = mod_is_in; red_is_integer = mod_is_integer;
3849 red_floorb = mod_floorb; red_ceilb = mod_ceilb; red_min = mod_min }
3850 in
3853 (* assert { forall d n. mem (Real.mod_t n d) modl.a -> (Real.mod_t n d) = mod };
assert { forall d n. mem d denl.a -> mem (Real.mod_t n d) modl.a -> Real.mod_t n den = mod };
assert { forall d n. mem d denl.a -> mem (Real.mod_t n d) modl.a -> op.red_is_in n }; *)
3854 reduce_generic op num
3855 in
3856 let neg,b,pos = Increasing.split_at num in
3857 let aux_neg () : option t
3858 requires { mod <=. 0. }
3859 ensures { forall n d. Increasing.mem_presence 0. (-. n) neg -> mem d denl.a -> (Real.mod_t n d) = mod -> match result with None -> false | Some r -> mem n r.a end }
3860 =
3861 match Increasing.presence_to_t zero neg with
3862 | None -> None
3863 | Some neg2 ->
3864 let mod' = (Q.abs mod) in
3865 let lemma ge_n (n d:real) requires { n <=. 0. }
3866 ensures { n <=. Real.mod_t n d } =
3867 if pure { d <> 0. } then begin mod_t_neg n d; mod_t_le (-. n) d end in
3868 match inter (ge mod') neg2 with
3869 | None -> None
3870 | Some neg3 ->
3871 assert { forall x:real. mem x neg3.a <-> (Q.real mod' <=. x /\ mem x neg2.a) };
3872 not_mem_is_le_bound False (Q.real mod') neg3.a;
3873 assert { forall n d. Increasing.mem_presence 0. (-. n) neg -> mem d denl.a -> (Real.mod_t n d) = mod -> mem (-. n) neg3.a };
3874 let lemma mn (n d:real) requires { d <> 0. }
3875 ensures { Real.mod_t (-.n) d = -. Real.mod_t n d } = mod_t_neg n d in
3876 match f_pos mod' neg3 with
3877 | None -> None
3878 | Some neg4 ->
3879 Some (Increasing.Unary.neg neg4)
3880 end
3881 end
3882 end
3883 in
3884 let aux_pos () : option t
3885 requires { 0. <=. mod }
3886 ensures { forall n d. Increasing.mem_presence 0. n pos -> mem d denl.a -> (Real.mod_t n d) = mod -> match result with None -> false | Some r -> mem n r.a end }
3887 =
3888 match Increasing.presence_to_t zero pos with
3889 | None -> None
3890 | Some neg2 ->
3891 let mod' = mod in
3892 let lemma le_n (n d:real) requires { 0. <=. n }
3893 ensures { Real.mod_t n d <=. n } = mod_t_le n d in
3894 match inter (ge mod') neg2 with
3895 | None -> None
3896 | Some neg3 ->
3897 assert { forall x:real. mem x neg3.a <-> (Q.real mod' <=. x /\ mem x neg2.a) };
3898 not_mem_is_le_bound False (Q.real mod') neg3.a;
3899 assert { forall n d. Increasing.mem_presence 0. n pos -> mem d denl.a -> (Real.mod_t n d) = mod -> mem n neg3.a };
3900 f_pos mod' neg3
3901 end
3902 end
3903 in
3904 match Q.compare zero mod with
3905 | Ord.Eq -> match aux_neg (), aux_pos () with
3906 | Some neg, Some pos -> Some (let u = union neg pos in if b then union (singleton zero) u else u)
3907 | Some neg, None -> Some (let u = neg in if b then union (singleton zero) u else u)
3908 | None, Some pos -> Some (let u = pos in if b then union (singleton zero) u else u)
3909 | None, None -> if b then Some (singleton zero) else None
3910 end
3911 | Ord.Lt ->
3912 assert { forall n d. mem n num.a -> mem d denl.a -> mem (Real.mod_t n d) modl.a -> (Real.mod_t n d) = mod };
3913 assert { forall n d. d <> 0. -> (Real.mod_t n d) >. 0. -> n >. 0. };
3914 assert { forall n. mem n num.a -> (Real.mod_t n den) = mod -> n >. 0. };
3915 assert { forall n d. mem n num.a -> mem d denl.a -> mem (Real.mod_t n d) modl.a -> Increasing.mem_presence 0. n pos };
3916 aux_pos ()
3917 | Ord.Gt ->
3918 assert { forall n d. mem n num.a -> mem d denl.a -> mem (Real.mod_t n d) modl.a -> (Real.mod_t n d) = mod };
3919 assert { forall n d. d <> 0. -> (Real.mod_t n d) <. 0. -> n <. 0. };
3920 assert { forall n. mem n num.a -> (Real.mod_t n den) = mod -> n <. 0. };
3921 assert { forall n d. mem n num.a -> mem d denl.a -> mem (Real.mod_t n d) modl.a -> Increasing.mem_presence 0. (-. n) neg };
3922 aux_neg ()
3923 end
3924 | _ -> Some num
3925 end
3926
3927
3928 function div_f_real (a b:real) : real = from_int (Real.div_f a b)
3929
Valid (169ms) (colibri2)
3930 let div_f_forward (l1 l2:t) : t
3931 ensures { sound2 memt div_f_real l1 l2 result } =
3932 NonIncreasing.floor (Increasing.Binary.div l1 l2)
3933
Valid (503ms) (cvc4)
3934 lemma mod_f: forall a b. b <> 0. -> (-. abs b) <. (Real.mod_f a b) <. abs b
3935
Valid (861ms) (cvc4)
3936 let ghost uniq_div_f_real (num:real) (den:real) (div:int) (mod:real) : unit
3937 requires { num = (from_int div)*.den +. mod }
3938 requires { if den <. 0. then den <. mod <=. 0. else 0. <=. mod <. den }
3939 ensures { Real.mod_f num den = mod } = ()
3940
Valid (384ms) (colibri2 9) (cvc4 2) (cvc5 8) (split_vc 3) (depth 3)
3941 let mod_f_forward (l1 l2:t) : t
3942 ensures { sound2 memt (fun (x y:real) -> Real.mod_f x y) l1 l2 result } =
3943 let zero = (Q.of_int 0) in
3944 if mem zero l2 then { a = On Inf }
3945 else
3946 let _ = not_bottom l2 in
3947 match mem_min l2,mem_max l2 with
3948 | None, _ | _, None -> { a = On Inf }
3949 | Some (m0,b0), Some (m1,b1) ->
3950 let m0' = Q.abs m0 in
3951 let m1' = Q.abs m1 in
3952 let (m,b) = max_bound_sup m0' b0 m1' b1 in
3953 assert { forall r2. mem r2 l2.a -> cmp r2 b m };
3954 assert { forall r2. mem r2 l2.a -> cmp (-. r2) b0 m0' };
3955 assert { forall r2. mem r2 l2.a -> cmp (-. r2) b m };
3956 assert { forall r2. mem r2 l2.a -> cmp (-. m) b r2 };
3957 { a = Off (Chg (Q.sub zero m) b (Chg m (inv_bound b) Inf)) }
3958 end
3959
Valid (3.5s) (colibri2 8) (cvc4 11) (cvc5 20) (split_vc 9) (depth 4)
3960 let mod_f_backward_num (num:t) (denl:t) (modl:t) : option t
3961 ensures { back2 memt (fun (x y:real) -> Real.mod_f x y) num denl modl result } =
3962 match denl.a, modl.a with
3963 | Off (Sin den Inf), Off (Sin mod Inf) ->
3964 let zero = Q.of_int 0 in
3965 (* Only singleton in den and mod for now *)
3966 if Q.equal den zero then Some num
3967 else
3968 let inside = if Q.lt den zero then (andb ((Q.lt den mod)) ((Q.le mod zero))) else (andb ((Q.le zero mod)) ((Q.lt mod den))) in
3969 if not inside then None
3970 else
3971 let ghost den_sign = if (Q.real den <. 0.) then (-1:int) else (1:int) in
3972 assert { from_int den_sign = abs den /. den };
3973 let ghost mod_min = I in
3974 let predicate mod_is_in (num:real) =
3975 pure { mod = Real.mod_f num den }
3976 in
3977 let mod_is_integer (num:Q.t)
3978 ensures { mod_is_in num <-> result }
3979 =
3980 (Q.equal (Q.mod_f num den) mod)
3981 in
3982 let mod_floorb (num:Q.t) (b:Bound.t) : Q.t
3983 ensures { (lt_infr mod_min (R num)) -> mod_is_in result }
3984 ensures { (lt_infr mod_min (R num)) -> cmp result b num }
3985 ensures { forall r. (lt_infr mod_min (R num)) -> cmp r b num -> result <. r -> not (mod_is_in r) }
3986 =
3987 let mod_f = Q.mod_f num den in
3988 (* num = (div_f num den)*den + (mod_f num den) *)
3989 let r,div =(
3990 (* num = (div_e num den)*den + (mod_e num den) *)
3991 (* num - mod_e num den + mod = (div_e num den)*den + mod *)
3992 match Q.compare mod mod_f with
3993 | Ord.Eq -> match b with
3994 | Large -> num, pure {Real.div_f (Q.real num) (Q.real den)}
3995 | Strict -> (Q.sub num (Q.abs den)), pure {Real.div_f num den - den_sign }
3996 end
3997 | Ord.Lt -> (Q.add (Q.sub num mod_f) mod),pure {Real.div_f num den }
3998 | Ord.Gt -> (Q.sub (Q.add (Q.sub num mod_f) mod) (Q.abs den)),
3999 pure {Real.div_f num den - den_sign}
4000 end) in
4001 uniq_div_f_real (Q.real r) (Q.real den) div (Q.real mod);
4002 r
4003 in
4004 let mod_ceilb (num:Q.t) (b:Bound.t) : Q.t
4005 ensures { (le_infr mod_min (R num)) -> mod_is_in result }
4006 ensures { (le_infr mod_min (R num)) -> cmp num b result }
4007 ensures { forall r. (le_infr mod_min (R num)) -> cmp num b r -> r <. result -> not (mod_is_in r) }
4008 =
4009 let mod_f = Q.mod_f num den in
4010 let (r,div) = match Q.compare mod mod_f with
4011 | Ord.Eq -> match b with
4012 | Large -> num, pure {Real.div_f num den}
4013 | Strict -> (Q.add num (Q.abs den)), pure {Real.div_f num den + den_sign}
4014 end
4015 | Ord.Lt -> (Q.add (Q.add (Q.sub num mod_f) mod) (Q.abs den)),
4016 pure {Real.div_f num den + den_sign}
4017 | Ord.Gt ->
4018 let lemma no_other (r:real)
4019 requires { mod <=. num }
4020 requires { num <=. r <. num -. mod_f +. mod }
4021 ensures { mod_f <=. Real.mod_f r den <. mod } =
4022 let mod_r = pure { r-.num+.mod_f } in
4023 uniq_div_f_real r (Q.real den) pure {Real.div_f num den} mod_r;
4024 in
4025 (Q.add (Q.sub num mod_f) mod),pure {Real.div_f num den }
4026 end in
4027 uniq_div_f_real (Q.real r) (Q.real den) div (Q.real mod);
4028 r
4029 in
4030 let op =
4031 { red_is_in = mod_is_in; red_is_integer = mod_is_integer;
4032 red_floorb = mod_floorb; red_ceilb = mod_ceilb; red_min = mod_min }
4033 in
4034 reduce_generic op num
4035 | _ -> Some num
4036 end
4037
4038
4039 end
4040
4041 end
4042end