library colibrilib.product — module QAssocSorted association lists from the atoms to the exponents: the model of the maps of colibri2 (Node.PT) used by the products, as polynome.Assoc for the linear forms
module QAssoc194use int.Int195use mach.int.Int63196use real.RealInfix197use list.List198use option.Option199use colibrilib.ring.Atom200use colibrilib.stdq.StdQ as Q201use Apow202203type binding = (Atom.t, Q.t)204205function assoc (k:Atom.t) (l:list binding) : option Q.t =206match l with207| Nil -> None208| Cons (k', v) r -> if k = k' then Some v else assoc k r209end210211predicate has (k:Atom.t) (l:list binding) = assoc k l <> None212
every key of l is above k
predicate above (k:Atom.t) (l:list binding) = forall k'. has k' l -> lt k k'215216predicate sorted (l:list binding) =217match l with218| Nil -> true219| Cons (k, _) r -> above k r /\ sorted r220end221
The exponents of l are not zero
predicate nonzero (l:list binding) =224forall k v. assoc k l = Some v -> Q.real v <> 0.0225
The exponent of k (zero when absent)
function ex (k:Atom.t) (l:list binding) : real =228match assoc k l with None -> 0.0 | Some v -> Q.real v end229
The product of the |env k|^v
function evp (env: Atom.t -> real) (l:list binding) : real =232match l with233| Nil -> 1.0234| Cons (k, v) r -> apow (env k) (Q.real v) *. evp env r235end236
Two optional exponents with the same value
predicate oeq (o1 o2:option Q.t) =239match o1, o2 with240| None, None -> true241| Some a, Some b -> Q.real a = Q.real b242| _ -> false243end244Valid (38ms) (colibri2)245let rec ghost evp_nonneg (env: Atom.t -> real) (l:list binding) : unit246ensures { 0.0 <=. evp env l }247variant { l }248= match l with249| Nil -> ()250| Cons (k, v) r -> evp_nonneg env r; apow_nonneg (env k) (Q.real v)251end252
A product is zero exactly when one of its atoms is zero
Valid (378ms) (colibri2 7) (split_vc 2) (depth 2)let rec ghost evp_zero (env: Atom.t -> real) (l:list binding) : unit255requires { sorted l /\ nonzero l }256ensures { evp env l = 0.0 <-> exists k. has k l /\ env k = 0.0 }257variant { l }258= match l with259| Nil -> ()260| Cons (k, v) r ->261let lemma nz (k':Atom.t) (v':Q.t) : unit262requires { assoc k' r = Some v' }263ensures { Q.real v' <> 0.0 }264= if pure { k' = k } then begin265assert { has k r }; Atom.lt_irrefl k266end else assert { assoc k' l = Some v' } in267evp_zero env r;268apow_nonneg (env k) (Q.real v)269end270
Two sorted lists with bindings of the same values have the same evaluation
Valid (2.7s) (colibri2 13) (cvc5 5) (split_vc 3) (depth 2)let rec ghost ext_evp (l1 l2:list binding) : unit274requires { sorted l1 /\ sorted l2 }275requires { forall k. oeq (assoc k l1) (assoc k l2) }276ensures { forall env. evp env l1 = evp env l2 }277ensures { nonzero l1 <-> nonzero l2 }278ensures { forall k. ex k l1 = ex k l2 }279ensures { forall k. has k l1 <-> has k l2 }280variant { l1 }281= match l1, l2 with282| Nil, Nil -> ()283| Cons (k1, _) _, Nil -> assert { has k1 l1 }284| Nil, Cons (k2, _) _ -> assert { has k2 l2 }285| Cons (k1, _) r1, Cons (k2, _) r2 ->286assert { has k1 l2 };287assert { has k2 l1 };288if pure { k1 <> k2 } then begin289absurd290end;291let lemma pw (k:Atom.t) : unit292ensures { oeq (assoc k r1) (assoc k r2) }293= if pure { k = k1 } then begin294assert { not (has k r1) /\ not (has k r2) }295end else begin296assert { assoc k l2 = assoc k r2 }297end in298ext_evp r1 r2299end300
A non zero exponent
function nzv (a:Q.t) : option Q.t = if Q.real a = 0.0 then None else Some a303
The exponents of l1^c1 * l2^c2
function comb (c1 c2:Q.t) (o1 o2:option Q.t) : option Q.t =306match o1, o2 with307| None, None -> None308| Some a, None -> nzv (Q.mul c1 a)309| None, Some b -> nzv (Q.mul c2 b)310| Some a, Some b -> nzv (Q.add (Q.mul c1 a) (Q.mul c2 b))311end312
The atoms that are zero have exponents of the sign of the power: the condition of apow_add
predicate compat (env: Atom.t -> real) (c1 c2:real) (l1 l2:list binding) =316forall k. env k = 0.0 -> 0.0 <=. c1 *. ex k l1 /\ 0.0 <=. c2 *. ex k l2317Valid (32ms) (colibri2)318let ghost step (x a c e:real) : unit319ensures { apow (apow x a *. e) c = apow x (c *. a) *. apow e c }320= apow_prod (apow x a) e c; apow_apow x a c;321assert { a *. c = c *. a }322Valid (32ms) (colibri2)323let ghost step2 (x a b c1 c2 e1 e2:real) : unit324requires { x <> 0.0 \/ (0.0 <=. c1 *. a /\ 0.0 <=. c2 *. b) }325ensures { apow (apow x a *. e1) c1 *. apow (apow x b *. e2) c2326= apow x (c1 *. a +. c2 *. b) *. (apow e1 c1 *. apow e2 c2) }327= step x a c1 e1; step x b c2 e2; apow_add x (c1 *. a) (c2 *. b)328
l1^c1 * l2^c2
Valid (972ms) (colibri2 49) (cvc5 3) (split_vc 5) (depth 2)let rec ghost lcomb (c1 c2:Q.t) (l1 l2:list binding) : list binding331requires { sorted l1 /\ sorted l2 }332ensures { sorted result }333ensures { forall k. has k result -> has k l1 \/ has k l2 }334ensures { forall k. assoc k result = comb c1 c2 (assoc k l1) (assoc k l2) }335ensures { forall env. compat env (Q.real c1) (Q.real c2) l1 l2 ->336evp env result337= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }338variant { l1, l2 }339= match l1, l2 with340| Nil, Nil -> Nil341| Cons (k, a) r, Nil ->342let t = lcomb c1 c2 r Nil in343let v = Q.mul c1 a in344let res = if pure { Q.real v = 0.0 } then t else Cons (k, v) t in345let lemma pw (k':Atom.t) : unit346ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }347= if pure { k' = k } then assert { not (has k t) } in348let lemma ev (env: Atom.t -> real) : unit349requires { compat env (Q.real c1) (Q.real c2) l1 l2 }350ensures { evp env res351= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }352= assert { not (has k r) by not (lt k k) };353assert { compat env (Q.real c1) (Q.real c2) r Nil354by forall k'. ex k' r = (if k' = k then 0.0 else ex k' l1) };355step (env k) (Q.real a) (Q.real c1) (evp env r);356apow_zero (env k) in357res358| Nil, Cons (k, b) r ->359let t = lcomb c1 c2 Nil r in360let v = Q.mul c2 b in361let res = if pure { Q.real v = 0.0 } then t else Cons (k, v) t in362let lemma pw (k':Atom.t) : unit363ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }364= if pure { k' = k } then assert { not (has k t) } in365let lemma ev (env: Atom.t -> real) : unit366requires { compat env (Q.real c1) (Q.real c2) l1 l2 }367ensures { evp env res368= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }369= assert { not (has k r) by not (lt k k) };370assert { compat env (Q.real c1) (Q.real c2) Nil r371by forall k'. ex k' r = (if k' = k then 0.0 else ex k' l2) };372step (env k) (Q.real b) (Q.real c2) (evp env r);373apow_zero (env k) in374res375| Cons (k1, a) r1, Cons (k2, b) r2 ->376let c = Atom.compare k1 k2 in377if c < 0 then begin378let t = lcomb c1 c2 r1 l2 in379let v = Q.mul c1 a in380let res = if pure { Q.real v = 0.0 } then t else Cons (k1, v) t in381assert { not (has k1 l2) };382let lemma ab (k:Atom.t) : unit383requires { has k t }384ensures { lt k1 k }385= if pure { has k l2 /\ k <> k2 } then Atom.lt_trans k1 k2 k in386let lemma pw (k':Atom.t) : unit387ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }388= if pure { k' = k1 } then assert { not (has k1 t) } in389let lemma ev (env: Atom.t -> real) : unit390requires { compat env (Q.real c1) (Q.real c2) l1 l2 }391ensures { evp env res392= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }393= assert { compat env (Q.real c1) (Q.real c2) r1 l2394by forall k'. ex k' r1 = (if k' = k1 then 0.0 else ex k' l1) };395step (env k1) (Q.real a) (Q.real c1) (evp env r1);396apow_zero (env k1) in397res398end else if c > 0 then begin399let t = lcomb c1 c2 l1 r2 in400let v = Q.mul c2 b in401let res = if pure { Q.real v = 0.0 } then t else Cons (k2, v) t in402assert { not (has k2 l1) };403let lemma ab (k:Atom.t) : unit404requires { has k t }405ensures { lt k2 k }406= if pure { has k l1 /\ k <> k1 } then Atom.lt_trans k2 k1 k in407let lemma pw (k':Atom.t) : unit408ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }409= if pure { k' = k2 } then assert { not (has k2 t) } in410let lemma ev (env: Atom.t -> real) : unit411requires { compat env (Q.real c1) (Q.real c2) l1 l2 }412ensures { evp env res413= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }414= assert { compat env (Q.real c1) (Q.real c2) l1 r2415by forall k'. ex k' r2 = (if k' = k2 then 0.0 else ex k' l2) };416step (env k2) (Q.real b) (Q.real c2) (evp env r2);417apow_zero (env k2);418assert { apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2)419= apow (env k2) (Q.real c2 *. Q.real b)420*. (apow (evp env l1) (Q.real c1) *. apow (evp env r2) (Q.real c2)) } in421res422end else begin423let t = lcomb c1 c2 r1 r2 in424let v = Q.add (Q.mul c1 a) (Q.mul c2 b) in425let res = if pure { Q.real v = 0.0 } then t else Cons (k1, v) t in426let lemma pw (k':Atom.t) : unit427ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }428= if pure { k' = k1 } then assert { not (has k1 t) } in429let lemma ev (env: Atom.t -> real) : unit430requires { compat env (Q.real c1) (Q.real c2) l1 l2 }431ensures { evp env res432= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }433= assert { compat env (Q.real c1) (Q.real c2) r1 r2434by forall k'. ex k' r1 = (if k' = k1 then 0.0 else ex k' l1)435/\ ex k' r2 = (if k' = k1 then 0.0 else ex k' l2) };436assert { ex k1 l1 = Q.real a /\ ex k1 l2 = Q.real b };437step2 (env k1) (Q.real a) (Q.real b) (Q.real c1) (Q.real c2)438(evp env r1) (evp env r2);439apow_zero (env k1) in440res441end442end443Valid (33ms) (colibri2)444let ghost nil_of_none (l:list binding) : unit445requires { forall k. not has k l }446ensures { l = Nil }447= match l with Nil -> () | Cons (k, _) _ -> assert { has k l } end448
l without the key k
Valid (703ms) (colibri2)let rec ghost lremove (k:Atom.t) (l:list binding) : list binding451requires { sorted l }452ensures { sorted result }453ensures { forall k'. assoc k' result = if k' = k then None else assoc k' l }454ensures { forall env. evp env l = apow (env k) (ex k l) *. evp env result }455variant { l }456= match l with457| Nil -> Nil458| Cons (k', v) r ->459if Atom.equal k k' then begin460assert { not (has k r) by not (lt k k) };461let lemma pw (k'':Atom.t) : unit462ensures { assoc k'' r = if k'' = k then None else assoc k'' l }463= () in464r465end else begin466let t = lremove k r in467assert { ex k l = ex k r };468Cons (k', v) t469end470end471end472