library colibrilib.product — module ProdThe products c * |x1|^q1 * ... * |xn|^qn of colibri2 (colibri2/theories/LRA/product.ml): the value of the absolute value of a node. c is non negative, the exponents are rationals. A negative exponent means that its node is not zero: the specifications assume it (valid).
module Prod566use int.Int567use mach.int.Int63568use real.RealInfix569use real.Abs570use list.List571use list.Length572use option.Option573use colibrilib.ring.Atom574use colibrilib.stdq.StdQ as Q575use colibrilib.stda.StdA as A576use Apow577use QAssoc578use PT579use APow580use colibrilib.spec.Sound581use colibrilib.spec.Eval582use colibrilib.spec.EvalOn583use colibrilib.spec.Test584use colibrilib.spec.Opt585
The coefficient a, unless it is zero
Valid (39ms) (colibri2)let function nz (a:Q.t) : option Q.t588ensures { result = nzv a }589= if Q.is_zero a then None else Some a590591exception DivZero592
A non negative constant, zero only without nodes; no zero exponent
Valid (139ms) (colibri2)type t = { cst: A.t; poly: PT.t }595invariant { 0.0 <=. A.real cst /\ (A.real cst = 0.0 -> bindings poly = Nil)596/\ nonzero (bindings poly) }597by { cst = A.of_int 0; poly = PT.empty () }598599function eval (env: Atom.t -> real) (p:t) : real =600A.real p.cst *. evp env (bindings p.poly)601602function exp (k:Atom.t) (p:t) : real = ex k (bindings p.poly)603604predicate mem (k:Atom.t) (p:t) = has k (bindings p.poly)605
The nodes with a negative exponent are not zero
predicate valid (env: Atom.t -> real) (p:t) =608forall k. exp k p <. 0.0 -> env k <> 0.0609
eval with the arguments in the order of the shapes of spec.Eval
function value (p:t) (env: Atom.t -> real) : real = eval env p612
The environments where p is defined
predicate ok1 (p:t) (env: Atom.t -> real) = valid env p615
The environments where p1 and p2 are defined
predicate ok2 (p1 p2:t) (env: Atom.t -> real) = valid env p1 /\ valid env p2618
The environments where p1 / p2 is defined
predicate ok_div (p1 p2:t) (env: Atom.t -> real) =621valid env p1 /\ eval env p2 <> 0.0622
The environments where p^c is defined
predicate ok_pow (c:Q.t) (p:t) (env: Atom.t -> real) =625valid env p /\ (Q.real c <. 0.0 -> eval env p <> 0.0)626
The environments where p1 * p2^c is defined
predicate ok_mul_pow (p1 p2:t) (c:Q.t) (env: Atom.t -> real) =629valid env p1 /\ valid env p2 /\ (Q.real c <. 0.0 -> eval env p2 <> 0.0)630
The environments where |x| = s, and p and s are defined
predicate ok_subst (p:t) (x:Atom.t) (s:t) (env: Atom.t -> real) =633valid env p /\ valid env s /\ abs (env x) = eval env s634
p is defined in every environment
predicate total (p:t) = includes valid (fun _ -> true) p637
p is |x|, and defined in every environment
predicate is_abs_node (p:t) (x:Atom.t) =640denotes0 value (fun env -> abs (env x)) p /\ total p641Valid (26ms) (colibri2)642let ghost eval_nonneg (env: Atom.t -> real) (p:t) : unit643ensures { 0.0 <=. eval env p }644= evp_nonneg env (bindings p.poly)645
A product is zero exactly when its constant or one of its nodes is
Valid (47ms) (colibri2)let ghost eval_zero (env: Atom.t -> real) (p:t) : unit648ensures { eval env p = 0.0 <->649(A.real p.cst = 0.0 \/ exists k. mem k p /\ env k = 0.0) }650= evp_zero env (bindings p.poly)651
The bindings of a map built by PT.merge
Valid (2.9s) (colibri2 12) (split_vc 2) (depth 2)let ghost merged (m:PT.t) (l1 l2:list binding) (c1 c2:Q.t) : unit654requires { sorted l1 /\ sorted l2 }655requires { forall k. oeq (get k m) (comb c1 c2 (assoc k l1) (assoc k l2)) }656ensures { nonzero (bindings m) }657ensures { forall k. has k (bindings m) -> has k l1 \/ has k l2 }658ensures { forall k. ex k (bindings m)659= Q.real c1 *. ex k l1 +. Q.real c2 *. ex k l2 }660ensures { forall env. compat env (Q.real c1) (Q.real c2) l1 l2 ->661evp env (bindings m)662= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }663= let l = lcomb c1 c2 l1 l2 in664ext_evp (bindings m) l;665let lemma pw (k:Atom.t) : unit666ensures { ex k l = Q.real c1 *. ex k l1 +. Q.real c2 *. ex k l2 }667= assert { assoc k l = comb c1 c2 (assoc k l1) (assoc k l2) };668match assoc k l1, assoc k l2 with669| None, None -> ()670| Some _, None -> ()671| None, Some _ -> ()672| Some _, Some _ -> ()673end in674()675Valid (36ms) (colibri2)676let ghost apow_inv (x:real) : unit677requires { 0.0 <. x }678ensures { apow x (-. 1.0) = 1.0 /. x }679= apow_neg x 1.0; apow_one x680Valid (60ms) (colibri2)681let zero () : t682ensures { denotes0 value (fun _ -> 0.0) result /\ total result }683ensures { forall k. not mem k result }684= { cst = A.of_int 0; poly = PT.empty () }685Valid (306ms) (colibri2)686let one () : t687ensures { denotes0 value (fun _ -> 1.0) result /\ total result }688ensures { forall k. not mem k result }689ensures { A.real result.cst = 1.0 }690= { cst = A.of_int 1; poly = PT.empty () }691
|c|
Valid (379ms) (colibri2)let const (c:A.t) : t694ensures { denotes0 value (fun _ -> abs (A.real c)) result /\ total result }695ensures { forall k. not mem k result }696= if A.equal c (A.of_int 0) then zero () else { cst = A.abs c; poly = PT.empty () }697
|x|^c
Valid (329ms) (colibri2 5) (split_vc) (depth 1)let monome (x:Atom.t) (c:Q.t) : t700ensures { denotes0 value (fun env -> apow (env x) (Q.real c)) result }701ensures { exact valid (fun env -> Q.real c <. 0.0 -> env x <> 0.0) result }702ensures { forall k. mem k result -> k = x }703= if Q.equal c (Q.of_int 0) then begin704let r = one () in705let lemma ev (env: Atom.t -> real) : unit706ensures { eval env r = apow (env x) (Q.real c) }707= apow_zero (env x) in708r709end else { cst = A.of_int 1; poly = PT.singleton x c }710Valid (33ms) (colibri2)711let is_zero (p:t) : bool712ensures { decides (A.real p.cst = 0.0) result }713ensures { result -> forall env. eval env p = 0.0 }714= A.equal p.cst (A.of_int 0)715
The closures of PT.merge
Valid (34ms) (colibri2)let function addf (_k:Atom.t) (o1 o2:option Q.t) : option Q.t =718match o1, o2 with719| None, o | o, None -> o720| Some a, Some b -> nz (Q.add a b)721end722
m1 is -1
Valid (45ms) (colibri2)let function subf (m1:Q.t) (_k:Atom.t) (o1 o2:option Q.t) : option Q.t =725match o1, o2 with726| o, None -> o727| None, Some b -> nz (Q.mul m1 b)728| Some a, Some b -> nz (Q.sub a b)729end730
The exponent nonzero, if any
predicate onz (o:option Q.t) =733match o with Some a -> Q.real a <> 0.0 | None -> true end734
addf is comb 1 1
Valid (867ms) (colibri2)let ghost addf_comb (c1 c2:Q.t) (k:Atom.t) (o1 o2:option Q.t) : unit737requires { Q.real c1 = 1.0 /\ Q.real c2 = 1.0 /\ onz o1 /\ onz o2 }738ensures { oeq (addf k o1 o2) (comb c1 c2 o1 o2) }739= match o1, o2 with740| Some a, None -> assert { Q.real (Q.mul c1 a) = Q.real a }741| None, Some b -> assert { Q.real (Q.mul c2 b) = Q.real b }742| Some a, Some b -> assert { Q.real (Q.add (Q.mul c1 a) (Q.mul c2 b)) = Q.real (Q.add a b) }743| None, None -> ()744end745
subf (-1) is comb 1 (-1)
Valid (741ms) (colibri2)let ghost subf_comb (m1 c1 c2:Q.t) (k:Atom.t) (o1 o2:option Q.t) : unit748requires { Q.real m1 = -1.0 /\ Q.real c1 = 1.0 /\ Q.real c2 = -1.0 }749requires { onz o1 /\ onz o2 }750ensures { oeq (subf m1 k o1 o2) (comb c1 c2 o1 o2) }751= match o1, o2 with752| Some a, None -> assert { Q.real (Q.mul c1 a) = Q.real a }753| None, Some b -> assert { Q.real (Q.mul c2 b) = Q.real (Q.mul m1 b) }754| Some a, Some b -> assert { Q.real (Q.add (Q.mul c1 a) (Q.mul c2 b)) = Q.real (Q.sub a b) }755| None, None -> ()756end757Valid (37ms) (colibri2)758let function combf (c1 c2:Q.t) (_k:Atom.t) (o1 o2:option Q.t) : option Q.t =759match o1, o2 with760| None, None -> None761| Some a, None -> nz (Q.mul c1 a)762| None, Some b -> nz (Q.mul c2 b)763| Some a, Some b -> nz (Q.add (Q.mul c1 a) (Q.mul c2 b))764end765Valid (600ms) (colibri2 13) (split_vc 2) (depth 2)766let mul (p1 p2:t) : t767ensures { denotes2_on (ok2 p1 p2) value (*.) p1 p2 result }768ensures { includes valid (ok2 p1 p2) result }769ensures { forall k. mem k result -> mem k p1 \/ mem k p2 }770= if is_zero p1 || is_zero p2 then zero ()771else begin772let m = PT.merge addf p1.poly p2.poly in773let one = Q.of_int 1 in774let lemma pt (k:Atom.t) : unit775ensures { oeq (get k m) (comb one one (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly))) }776= addf_comb one one k (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly)) in777merged m (bindings p1.poly) (bindings p2.poly) one one;778let r = { cst = A.mul p1.cst p2.cst; poly = m } in779let lemma ev (env: Atom.t -> real) : unit780requires { valid env p1 /\ valid env p2 }781ensures { eval env r = eval env p1 *. eval env p2 /\ valid env r }782= let e1 = evp env (bindings p1.poly) in783let e2 = evp env (bindings p2.poly) in784evp_nonneg env (bindings p1.poly); evp_nonneg env (bindings p2.poly);785apow_one e1; apow_one e2;786assert { compat env 1.0 1.0 (bindings p1.poly) (bindings p2.poly) };787assert { eval env r = A.real p1.cst *. A.real p2.cst *. (e1 *. e2) } in788r789end790
p1 / p2; p2 is not zero
Valid (485ms) (colibri2 18) (split_vc) (depth 1)let div (p1 p2:t) : t793ensures { denotes2_on (ok_div p1 p2) value (/.) p1 p2 result }794ensures { includes valid (ok_div p1 p2) result }795ensures { forall k. mem k result -> mem k p1 \/ mem k p2 }796ensures { A.real p1.cst <> 0.0 -> forall k. exp k result = exp k p1 -. exp k p2 }797ensures { A.real p1.cst <> 0.0 -> A.real result.cst <> 0.0 }798raises { DivZero -> A.real p2.cst = 0.0 }799= if is_zero p2 then raise DivZero;800if is_zero p1 then zero ()801else begin802let m1 = Q.of_int (-1) in803let m = PT.merge (subf m1) p1.poly p2.poly in804let one = Q.of_int 1 in805let lemma pt (k:Atom.t) : unit806ensures { oeq (get k m) (comb one m1 (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly))) }807= subf_comb m1 one m1 k (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly)) in808merged m (bindings p1.poly) (bindings p2.poly) one m1;809let r = { cst = A.div p1.cst p2.cst; poly = m } in810let lemma ev (env: Atom.t -> real) : unit811requires { valid env p1 /\ eval env p2 <> 0.0 }812ensures { eval env r = eval env p1 /. eval env p2 /\ valid env r }813= let e1 = evp env (bindings p1.poly) in814let e2 = evp env (bindings p2.poly) in815eval_zero env p2;816evp_nonneg env (bindings p1.poly); evp_nonneg env (bindings p2.poly);817apow_one e1; apow_inv e2;818assert { compat env 1.0 (-1.0) (bindings p1.poly) (bindings p2.poly) };819assert { eval env r = (A.real p1.cst /. A.real p2.cst) *. (e1 *. (1.0 /. e2)) } in820r821end822
The closure of power_cst
Valid (33ms) (colibri2)let function mulf (c e:Q.t) : Q.t = Q.mul e c825
p^c
Valid (895ms) (colibri2 25) (cvc4) (split_vc) (depth 1)let power_cst (c:Q.t) (p:t) : t828ensures { denotes1_on (ok_pow c p) value (fun v -> apow v (Q.real c)) p result }829ensures { includes valid (ok_pow c p) result }830ensures { forall k. mem k result -> mem k p }831ensures { A.real p.cst <> 0.0 -> forall k. exp k result = Q.real c *. exp k p }832ensures { A.real p.cst <> 0.0 -> A.real result.cst <> 0.0 }833raises { DivZero -> Q.real c <. 0.0 /\ A.real p.cst = 0.0 }834= if Q.equal c (Q.of_int 0) then begin835let r = one () in836let lemma ev (env: Atom.t -> real) : unit837ensures { eval env r = apow (eval env p) (Q.real c) }838= apow_zero (eval env p) in839assert { forall k. exp k r = 0.0 };840r841end else if is_zero p then begin842if Q.lt c (Q.of_int 0) then raise DivZero;843zero ()844end else begin845let ghost z = Q.of_int 0 in846let m = PT.map (mulf c) p.poly in847merged m (bindings p.poly) Nil c z;848assert { forall k. ex k Nil = 0.0 };849let r = { cst = positive_pow p.cst c; poly = m } in850apow_nonneg (A.real p.cst) (Q.real c);851let lemma ev (env: Atom.t -> real) : unit852requires { valid env p /\ (Q.real c <. 0.0 -> eval env p <> 0.0) }853ensures { eval env r = apow (eval env p) (Q.real c) /\ valid env r }854= let e = evp env (bindings p.poly) in855eval_zero env p;856apow_zero 1.0;857assert { compat env (Q.real c) 0.0 (bindings p.poly) Nil };858apow_prod (A.real p.cst) e (Q.real c);859assert { evp env (bindings m) = apow e (Q.real c) } in860r861end862
p1 * p2^c
Valid (1.4s) (colibri2 22) (split_vc) (depth 1)let x_m_yc (p1 p2:t) (c:Q.t) : t865ensures { denotes2_on (ok_mul_pow p1 p2 c) value (fun x y -> x *. apow y (Q.real c)) p1 p2 result }866ensures { includes valid (ok_mul_pow p1 p2 c) result }867ensures { forall k. mem k result -> mem k p1 \/ mem k p2 }868raises { DivZero -> Q.real c <. 0.0 /\ A.real p2.cst = 0.0 }869= if Q.equal c (Q.of_int 0) then begin870let lemma ev (env: Atom.t -> real) : unit871ensures { eval env p1 = eval env p1 *. apow (eval env p2) (Q.real c) }872= apow_zero (eval env p2) in873p1874end else if is_zero p2 then begin875if Q.lt c (Q.of_int 0) then raise DivZero;876zero ()877end else if is_zero p1 then zero ()878else if Q.equal c (Q.of_int 1) then begin879let lemma ev (env: Atom.t -> real) : unit880ensures { apow (eval env p2) (Q.real c) = eval env p2 }881= eval_nonneg env p2; apow_one (eval env p2) in882mul p1 p2883end else begin884let o = Q.of_int 1 in885let m = PT.merge (combf o c) p1.poly p2.poly in886let lemma pt (k:Atom.t) : unit887ensures { oeq (get k m) (comb o c (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly))) }888= assert { get k m = combf o c k (get k p1.poly) (get k p2.poly) } in889merged m (bindings p1.poly) (bindings p2.poly) o c;890let r = { cst = A.mul p1.cst (positive_pow p2.cst c); poly = m } in891let lemma ev (env: Atom.t -> real) : unit892requires { valid env p1 /\ valid env p2 }893requires { Q.real c <. 0.0 -> eval env p2 <> 0.0 }894ensures { eval env r = eval env p1 *. apow (eval env p2) (Q.real c)895/\ valid env r }896= let e1 = evp env (bindings p1.poly) in897let e2 = evp env (bindings p2.poly) in898eval_zero env p2;899evp_nonneg env (bindings p1.poly);900apow_one e1;901assert { compat env 1.0 (Q.real c) (bindings p1.poly) (bindings p2.poly) };902apow_prod (A.real p2.cst) e2 (Q.real c);903assert { eval env r = A.real p1.cst *. apow (A.real p2.cst) (Q.real c)904*. (e1 *. apow e2 (Q.real c)) } in905r906end907
p without the node n: p = |n|^(exp n p) * remove n p
Valid (392ms) (colibri2 10) (split_vc) (depth 1)let remove (n:Atom.t) (p:t) : t910ensures { denotes0 value (fun env -> apow (env n) (exp n p) *. eval env result) p }911ensures { includes valid (ok1 p) result }912ensures { exact mem (fun k -> mem k p /\ k <> n) result }913ensures { forall k. k <> n -> exp k result = exp k p }914ensures { result.cst = p.cst }915= let m = PT.remove n p.poly in916let l = lremove n (bindings p.poly) in917ext_evp (bindings m) l;918if pure { bindings p.poly = Nil } then nil_of_none (bindings m);919{ cst = p.cst; poly = m }920
The substitution of |x| by s; None when x is not in p
Valid (1.8s) (colibri2 4) (cvc4) (split_vc) (depth 1)let subst (p:t) (x:Atom.t) (s:t) : option t923ensures { match result with924| None -> not mem x p925| Some r -> mem x p926/\ (forall k. mem k r -> (mem k p /\ k <> x) \/ mem k s)927/\ denotes1_on (ok_subst p x s) value (fun v -> v) p r928/\ includes valid (ok_subst p x s) r929end }930raises { DivZero -> exp x p <. 0.0 /\ A.real s.cst = 0.0 }931= match PT.find_opt x p.poly with932| None -> None933| Some q ->934let p' = remove x p in935let r = x_m_yc p' s q in936let lemma ev (env: Atom.t -> real) : unit937requires { valid env p /\ valid env s /\ abs (env x) = eval env s }938ensures { eval env r = eval env p /\ valid env r }939= apow_abs (env x) (Q.real q);940assert { Q.real q <. 0.0 -> env x <> 0.0 } in941Some r942end943944type extracted =945| One946| Cst A.t947| Var Q.t Atom.t t948
A node of p and the rest
Valid (71ms) (colibri2)let extract (p:t) : extracted951ensures { match result with952| One -> bindings p.poly = Nil /\ A.real p.cst = 1.0953| Cst c -> bindings p.poly = Nil /\ c = p.cst /\ A.real c <> 1.0954| Var q x r -> exp x p = Q.real q /\ Q.real q <> 0.0 /\ r.cst = p.cst955/\ exact mem (fun k -> mem k p /\ k <> x) r956/\ denotes0 value (fun env -> apow (env x) (Q.real q) *. eval env r) p957/\ includes valid (ok1 p) r958end }959= if PT.is_empty p.poly then960if A.equal p.cst (A.of_int 1) then One else Cst p.cst961else begin962let x, q = PT.choose p.poly in963Var q x (remove x p)964end965
|x|
Valid (349ms) (colibri2 8) (split_vc) (depth 1)let partial is_one_node (p:t) : option Atom.t968ensures { when_some (is_abs_node p) result }969= if A.equal p.cst (A.of_int 1) && PT.cardinal p.poly = 1 then begin970let x, q = PT.choose p.poly in971if Q.equal q (Q.of_int 1) then begin972assert { match bindings p.poly with973| Cons (y, v) Nil -> y = x /\ v = q | _ -> false end };974let lemma ev (env: Atom.t -> real) : unit975ensures { eval env p = abs (env x) }976= apow_one (env x) in977Some x978end else None979end else None980981type kind =982| CST A.t983| NODE A.t Atom.t984| PRODUCT985Valid (406ms) (colibri2)986let partial classify (p:t) : kind987ensures { match result with988| CST c -> bindings p.poly = Nil /\ c = p.cst989| NODE c x -> c = p.cst /\ denotes0 value (fun env -> A.real c *. abs (env x)) p990/\ total p991| PRODUCT -> true992end }993= if PT.is_empty p.poly then CST p.cst994else if PT.cardinal p.poly = 1 then begin995let x, q = PT.choose p.poly in996if Q.equal q (Q.of_int 1) then begin997assert { match bindings p.poly with998| Cons (y, v) Nil -> y = x /\ v = q | _ -> false end };999let lemma ev (env: Atom.t -> real) : unit1000ensures { eval env p = A.real p.cst *. abs (env x) }1001= apow_one (env x) in1002NODE p.cst x1003end else PRODUCT1004end else PRODUCT1005
The closure of common
Valid (34ms) (colibri2)let function commonf (_k:Atom.t) (o1 o2:option Q.t) : option Q.t =1008match o1, o2 with1009| Some a, Some b -> (match nz (Q.sub a b) with None -> Some a | Some _ -> None end)1010| _ -> None1011end1012
The nodes with the same exponent in p1 and p2, with this exponent
Valid (375ms) (colibri2 8) (cvc5) (split_vc) (depth 1)let common (p1 p2:t) : t1015ensures { A.real result.cst = 1.0 }1016ensures { forall k. mem k result -> mem k p1 /\ mem k p21017/\ exp k result = exp k p1 /\ exp k result = exp k p2 }1018= let m = PT.merge commonf p1.poly p2.poly in1019let lemma nz (k:Atom.t) (v:Q.t) : unit1020requires { get k m = Some v }1021ensures { Q.real v <> 0.0 }1022= assert { get k p1.poly = Some v } in1023let lemma memk (k:Atom.t) : unit1024requires { has k (bindings m) }1025ensures { has k (bindings p1.poly) /\ has k (bindings p2.poly) }1026ensures { ex k (bindings m) = ex k (bindings p1.poly) = ex k (bindings p2.poly) }1027= assert { get k m = commonf k (get k p1.poly) (get k p2.poly) } in1028{ cst = A.of_int 1; poly = m }1029
The nodes of p that satisfy f
Valid (42ms) (colibri2 6) (split_vc) (depth 1)let filter (f: Atom.t -> bool) (p:t) : t1032ensures { result.cst = p.cst }1033ensures { forall k. get k result.poly = if f k then get k p.poly else None }1034= let m = PT.filter f p.poly in1035let lemma nz (k:Atom.t) (v:Q.t) : unit1036requires { get k m = Some v }1037ensures { Q.real v <> 0.0 }1038= assert { get k p.poly = Some v } in1039if pure { bindings p.poly = Nil } then nil_of_none (bindings m);1040{ cst = p.cst; poly = m }1041
The nodes with a negative exponent in l are not zero
predicate lvalid (env: Atom.t -> real) (l:list binding) =1044match l with1045| Nil -> true1046| Cons (k, q) r -> (Q.real q <. 0.0 -> env k <> 0.0) /\ lvalid env r1047end1048
lvalid as a set of environments
predicate lvalid_at (l:list binding) (env: Atom.t -> real) = lvalid env l1051
The environments where |k| = f k for the atoms of p, all defined
predicate ok_normalize (p:t) (f: Atom.t -> t) (env: Atom.t -> real) =1054valid env p /\1055forall k. mem k p -> abs (env k) = eval env (f k) /\ valid env (f k)1056
|c| * |x1|^q1 * ... * |xn|^qn, the xi are not necessarily distinct
Valid (743ms) (colibri2 10) (split_vc 2) (depth 2)let rec of_list (c:A.t) (l:list binding) : t1060ensures { denotes0_on (lvalid_at l) value (fun env -> abs (A.real c) *. evp env l) result }1061ensures { includes valid (lvalid_at l) result }1062variant { l }1063= match l with1064| Nil -> const c1065| Cons (k, q) r ->1066let p = of_list c r in1067let mk = monome k q in1068let res = mul mk p in1069let lemma ev (env: Atom.t -> real) : unit1070requires { lvalid env l }1071ensures { eval env res = abs (A.real c) *. evp env l /\ valid env res }1072= assert { valid env mk };1073assert { lvalid env r };1074assert { eval env p = abs (A.real c) *. evp env r /\ valid env p };1075assert { eval env res = apow (env k) (Q.real q) *. eval env p };1076assert { evp env l = apow (env k) (Q.real q) *. evp env r };1077assert { apow (env k) (Q.real q) *. (abs (A.real c) *. evp env r)1078= abs (A.real c) *. (apow (env k) (Q.real q) *. evp env r) } in1079res1080end1081
Every node k of p replaced by f k, its value: the nodes k with a negative exponent are not zero
Valid (3.0s) (colibri2 30) (cvc4) (split_vc 5) (depth 2)let normalize (p:t) (f: Atom.t -> t) : t1085ensures { denotes1_on (ok_normalize p f) value (fun v -> v) p result }1086ensures { includes valid (ok_normalize p f) result }1087raises { DivZero -> exists k. exp k p <. 0.0 /\ A.real (f k).cst = 0.0 }1088= let rec aux (acc:t) (l:list binding) : t1089requires { sorted l /\ nonzero l }1090requires { forall k. has k l -> ex k l = exp k p }1091ensures { forall env. valid env acc -> valid env p ->1092(forall k. has k l -> abs (env k) = eval env (f k) /\ valid env (f k)) ->1093eval env result = eval env acc *. evp env l /\ valid env result }1094raises { DivZero -> exists k. exp k p <. 0.0 /\ A.real (f k).cst = 0.0 }1095variant { l }1096= match l with1097| Nil -> acc1098| Cons (k, q) r ->1099assert { has k l };1100assert { forall k'. has k' r -> ex k' r = ex k' l1101by k' <> k by lt k k' };1102assert { nonzero r by forall k' v. assoc k' r = Some v ->1103assoc k' l = Some v by k' <> k by has k' r };1104let acc' = x_m_yc acc (f k) q in1105let res = aux acc' r in1106let lemma ev (env: Atom.t -> real) : unit1107requires { valid env acc /\ valid env p }1108requires { forall k. has k l -> abs (env k) = eval env (f k) /\ valid env (f k) }1109ensures { eval env res = eval env acc *. evp env l /\ valid env res }1110= apow_abs (env k) (Q.real q);1111assert { Q.real q <. 0.0 -> env k <> 0.0 };1112assert { eval env acc' = eval env acc *. apow (env k) (Q.real q) };1113assert { evp env l = apow (env k) (Q.real q) *. evp env r };1114assert { valid env acc' };1115assert { forall k'. has k' r -> has k' l };1116assert { forall k'. has k' r -> abs (env k') = eval env (f k') /\ valid env (f k') };1117assert { eval env res = eval env acc' *. evp env r /\ valid env res } in1118res1119end1120in1121let res = aux (const p.cst) (PT.to_list p.poly) in1122let lemma ev (env: Atom.t -> real) : unit1123requires { valid env p }1124requires { forall k. mem k p -> abs (env k) = eval env (f k) /\ valid env (f k) }1125ensures { eval env res = eval env p /\ valid env res }1126= assert { abs (A.real p.cst) = A.real p.cst } in1127res1128end1129