library colibrilib.polynome — module AssocSorted association lists: the model of the maps
module Assoc10use int.Int11use mach.int.Int6312use real.RealInfix13use list.List14use list.Length15use option.Option16use colibrilib.ring.Atom17use colibrilib.stda.StdA as A1819type binding = (Atom.t, A.t)2021function assoc (k:Atom.t) (l:list binding) : option A.t =22match l with23| Nil -> None24| Cons (k', v) r -> if k = k' then Some v else assoc k r25end2627predicate has (k:Atom.t) (l:list binding) = assoc k l <> None28
every key of l is above k
predicate above (k:Atom.t) (l:list binding) = forall k'. has k' l -> lt k k'3132predicate sorted (l:list binding) =33match l with34| Nil -> true35| Cons (k, _) r -> above k r /\ sorted r36end37
the sum of the v * env k
function evall (env: Atom.t -> real) (l:list binding) : real =40match l with41| Nil -> 0.042| Cons (k, v) r -> A.real v *. env k +. evall env r43end44
Two sorted lists with the same bindings are equal
Valid (405ms) (colibri2 9) (cvc5 2) (split_vc) (depth 1)let rec ghost ext (l1 l2:list binding) : unit47requires { sorted l1 /\ sorted l2 }48requires { forall k. assoc k l1 = assoc k l2 }49ensures { l1 = l2 }50variant { l1 }51= match l1, l2 with52| Nil, Nil -> ()53| Cons (k1, _) _, Nil -> assert { has k1 l1 }54| Nil, Cons (k2, _) _ -> assert { has k2 l2 }55| Cons (k1, _) r1, Cons (k2, _) r2 ->56assert { has k1 l2 };57assert { has k2 l1 };58if pure { k1 <> k2 } then begin59absurd60end;61let lemma pw (k:Atom.t) : unit62ensures { assoc k r1 = assoc k r2 }63= if pure { k = k1 } then begin64()65end else begin66assert { assoc k l2 = assoc k r2 }67end in68ext r1 r269end70
A non zero value
function nzv (a:A.t) : option A.t = if A.real a = 0.0 then None else Some a73
The bindings of c1 * l1 + c2 * l2
function comb (c1 c2:A.t) (o1 o2:option A.t) : option A.t =76match o1, o2 with77| None, None -> None78| Some a, None -> nzv (A.mul c1 a)79| None, Some b -> nzv (A.mul c2 b)80| Some a, Some b -> nzv (A.add (A.mul c1 a) (A.mul c2 b))81end82Valid (13ms) (cvc5)83let ghost comb_both (c1 c2 a b v x e1 e2:real) : unit84requires { v = c1 *. a +. c2 *. b }85ensures { c1 *. (a *. x +. e1) +. c2 *. (b *. x +. e2)86= v *. x +. (c1 *. e1 +. c2 *. e2) }87= ()88
c1 * l1 + c2 * l2
Valid (657ms) (colibri2 45) (cvc5 2) (split_vc) (depth 1)let rec ghost lcomb (c1 c2:A.t) (l1 l2:list binding) : list binding91requires { sorted l1 /\ sorted l2 }92ensures { sorted result }93ensures { forall k. has k result -> has k l1 \/ has k l2 }94ensures { forall k. assoc k result = comb c1 c2 (assoc k l1) (assoc k l2) }95ensures { forall env. evall env result96= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }97variant { l1, l2 }98= match l1, l2 with99| Nil, Nil -> Nil100| Cons (k, a) r, Nil ->101let t = lcomb c1 c2 r Nil in102let v = A.mul c1 a in103let res = if pure { A.real v = 0.0 } then t else Cons (k, v) t in104let lemma pw (k':Atom.t) : unit105ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }106= if pure { k' = k } then assert { not (has k t) } in107let lemma ev (env: Atom.t -> real) : unit108ensures { evall env res109= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }110= assert { A.real v = A.real c1 *. A.real a };111assert { A.real c1 *. (A.real a *. env k +. evall env r)112= A.real v *. env k +. A.real c1 *. evall env r } in113res114| Nil, Cons (k, b) r ->115let t = lcomb c1 c2 Nil r in116let v = A.mul c2 b in117let res = if pure { A.real v = 0.0 } then t else Cons (k, v) t in118let lemma pw (k':Atom.t) : unit119ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }120= if pure { k' = k } then assert { not (has k t) } in121let lemma ev (env: Atom.t -> real) : unit122ensures { evall env res123= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }124= assert { A.real v = A.real c2 *. A.real b };125assert { A.real c2 *. (A.real b *. env k +. evall env r)126= A.real v *. env k +. A.real c2 *. evall env r } in127res128| Cons (k1, a) r1, Cons (k2, b) r2 ->129let c = Atom.compare k1 k2 in130if c < 0 then begin131let t = lcomb c1 c2 r1 l2 in132let v = A.mul c1 a in133let res = if pure { A.real v = 0.0 } then t else Cons (k1, v) t in134assert { not (has k1 l2) };135let lemma ab (k:Atom.t) : unit136requires { has k t }137ensures { lt k1 k }138= if pure { has k l2 /\ k <> k2 } then Atom.lt_trans k1 k2 k in139let lemma pw (k':Atom.t) : unit140ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }141= if pure { k' = k1 } then assert { not (has k1 t) } in142let lemma ev (env: Atom.t -> real) : unit143ensures { evall env res144= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }145= assert { A.real v = A.real c1 *. A.real a };146assert { A.real c1 *. (A.real a *. env k1 +. evall env r1)147= A.real v *. env k1 +. A.real c1 *. evall env r1 } in148res149end else if c > 0 then begin150let t = lcomb c1 c2 l1 r2 in151let v = A.mul c2 b in152let res = if pure { A.real v = 0.0 } then t else Cons (k2, v) t in153assert { not (has k2 l1) };154let lemma ab (k:Atom.t) : unit155requires { has k t }156ensures { lt k2 k }157= if pure { has k l1 /\ k <> k1 } then Atom.lt_trans k2 k1 k in158let lemma pw (k':Atom.t) : unit159ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }160= if pure { k' = k2 } then assert { not (has k2 t) } in161let lemma ev (env: Atom.t -> real) : unit162ensures { evall env res163= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }164= assert { A.real v = A.real c2 *. A.real b };165assert { A.real c2 *. (A.real b *. env k2 +. evall env r2)166= A.real v *. env k2 +. A.real c2 *. evall env r2 } in167res168end else begin169let t = lcomb c1 c2 r1 r2 in170let v = A.add (A.mul c1 a) (A.mul c2 b) in171let res = if pure { A.real v = 0.0 } then t else Cons (k1, v) t in172let lemma pw (k':Atom.t) : unit173ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }174= if pure { k' = k1 } then assert { not (has k1 t) } in175let lemma ev (env: Atom.t -> real) : unit176ensures { evall env res177= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }178= assert { A.real v = A.real c1 *. A.real a +. A.real c2 *. A.real b };179comb_both (A.real c1) (A.real c2) (A.real a) (A.real b) (A.real v)180(env k1) (evall env r1) (evall env r2) in181res182end183end184
l without the key k
Valid (269ms) (colibri2 5) (cvc5) (split_vc) (depth 1)let rec ghost lremove (k:Atom.t) (l:list binding) : list binding187requires { sorted l }188ensures { sorted result }189ensures { forall k'. assoc k' result = if k' = k then None else assoc k' l }190ensures { forall env. evall env result = match assoc k l with191| None -> evall env l192| Some v -> evall env l -. A.real v *. env k end }193variant { l }194= match l with195| Nil -> Nil196| Cons (k', v) r ->197if Atom.equal k k' then begin198let lemma pw (k'':Atom.t) : unit199ensures { assoc k'' r = if k'' = k then None else assoc k'' l }200= () in201r202end else begin203let t = lremove k r in204Cons (k', v) t205end206end207
The values of l are not zero
predicate nonzero (l:list binding) =210forall k v. assoc k l = Some v -> A.real v <> 0.0211
Two optional coefficients with the same value
predicate oeq (o1 o2:option A.t) =214match o1, o2 with215| None, None -> true216| Some a, Some b -> A.real a = A.real b217| _ -> false218end219
Two sorted lists with bindings of the same values have the same evaluation (the coefficients are compared by their values)
Valid (1.2s) (colibri2 11) (cvc4 2) (split_vc) (depth 1)let rec ghost ext_eval (l1 l2:list binding) : unit223requires { sorted l1 /\ sorted l2 }224requires { forall k. oeq (assoc k l1) (assoc k l2) }225ensures { forall env. evall env l1 = evall env l2 }226ensures { nonzero l1 <-> nonzero l2 }227variant { l1 }228= match l1, l2 with229| Nil, Nil -> ()230| Cons (k1, _) _, Nil -> assert { has k1 l1 }231| Nil, Cons (k2, _) _ -> assert { has k2 l2 }232| Cons (k1, _) r1, Cons (k2, _) r2 ->233assert { has k1 l2 };234assert { has k2 l1 };235if pure { k1 <> k2 } then begin236absurd237end;238let lemma pw (k:Atom.t) : unit239ensures { oeq (assoc k r1) (assoc k r2) }240= if pure { k = k1 } then begin241assert { not (has k r1) /\ not (has k r2) }242end else begin243assert { assoc k l2 = assoc k r2 }244end in245ext_eval r1 r2246end247end248