library colibrilib.ring — module PolyPolynomials: strictly sorted lists of (monomial, non zero coefficient)
module Poly141use int.Int142use mach.int.Int63143use real.RealInfix144use list.List145use list.Mem146use Atom147use Mono148use option.Option149use colibrilib.stda.StdA as A150151type term = (mono, A.t)152type poly = list term153
m is the monomial of a term of p
predicate has (m:mono) (p:poly) =156match p with157| Nil -> false158| Cons (m', _) r -> m = m' \/ has m r159end160
every monomial of p is above m
predicate above (m:mono) (p:poly) = forall m'. has m' p -> mlt m m'163164predicate wf (p:poly) =165match p with166| Nil -> true167| Cons (m, c) r -> A.real c <> 0.0 /\ sorted m /\ above m r /\ wf r168end169170function eval (env: Atom.t -> real) (p:poly) : real =171match p with172| Nil -> 0.0173| Cons (m, c) r -> A.real c *. evalm env m +. eval env r174end175Valid (21ms) (colibri2)176let ghost above_trans (m1 m2:mono) (p:poly) : unit177requires { mlt m1 m2 }178requires { above m2 p }179ensures { above m1 p }180= let lemma pw (m:mono) : unit181requires { has m p }182ensures { mlt m1 m }183= mlt_trans m1 m2 m in184()185Valid (21ms) (colibri2)186let zero () : poly187ensures { wf result }188ensures { forall env. eval env result = 0.0 }189= Nil190
The constant c
Valid (36ms) (colibri2)let cst (c:A.t) : poly193ensures { wf result }194ensures { forall env. eval env result = A.real c }195= if A.equal c (A.of_int 0) then Nil else Cons (Nil, c) Nil196
The atom a
Valid (36ms) (colibri2)let var (a:Atom.t) : poly199ensures { wf result }200ensures { forall env. eval env result = env a }201= Cons (Cons a Nil, A.of_int 1) Nil202
The sum. The monomials of the result are those of p or q
Valid (1.4s) (colibri2 18) (cvc4) (cvc5) (split_vc 4) (depth 4)let rec add (p q:poly) : poly205requires { wf p /\ wf q }206ensures { wf result }207ensures { forall m. has m result -> has m p \/ has m q }208ensures { forall env. eval env result = eval env p +. eval env q }209variant { p, q }210= match p, q with211| Nil, _ -> q212| _, Nil -> p213| Cons (m1, c1) r1, Cons (m2, c2) r2 ->214let c = Mono.compare m1 m2 in215if c < 0 then begin216let r = add r1 q in217mlt_irrefl m1;218let lemma ab (m:mono) : unit219requires { has m r }220ensures { mlt m1 m }221= if pure { has m q } then begin222if pure { m <> m2 } then mlt_trans m1 m2 m223end in224Cons (m1, c1) r225end else if c > 0 then begin226let r = add p r2 in227let lemma ab (m:mono) : unit228requires { has m r }229ensures { mlt m2 m }230= if pure { has m p } then begin231if pure { m <> m1 } then mlt_trans m2 m1 m232end in233Cons (m2, c2) r234end else begin235let r = add r1 r2 in236let s = A.add c1 c2 in237if A.equal s (A.of_int 0) then r else Cons (m1, s) r238end239end240
The product by the non zero constant k
Valid (341ms) (colibri2)let rec scale (k:A.t) (p:poly) : poly243requires { A.real k <> 0.0 }244requires { wf p }245ensures { wf result }246ensures { forall m. has m result <-> has m p }247ensures { forall env. eval env result = A.real k *. eval env p }248variant { p }249= match p with250| Nil -> Nil251| Cons (m, c) r ->252let c' = A.mul k c in253assert { A.real c' <> 0.0 };254Cons (m, c') (scale k r)255end256Valid (43ms) (colibri2)257let neg (p:poly) : poly258requires { wf p }259ensures { wf result }260ensures { forall m. has m result <-> has m p }261ensures { forall env. eval env result = -. eval env p }262= scale (A.of_int (-1)) p263Valid (51ms) (colibri2)264let sub (p q:poly) : poly265requires { wf p /\ wf q }266ensures { wf result }267ensures { forall env. eval env result = eval env p -. eval env q }268= add p (neg q)269
The product of the term c * m and p
Valid (40ms) (colibri2 12) (split_vc) (depth 1)let rec mul_term (m:mono) (c:A.t) (p:poly) : poly272requires { sorted m /\ A.real c <> 0.0 /\ wf p }273ensures { wf result }274ensures { forall env. eval env result = A.real c *. evalm env m *. eval env p }275variant { p }276= match p with277| Nil -> Nil278| Cons (m', c') r ->279let c'' = A.mul c c' in280assert { A.real c'' <> 0.0 };281let m'' = Mono.mul m m' in282let t = Cons (m'', c'') Nil in283let rest = mul_term m c r in284let res = add t rest in285let lemma ev (env: Atom.t -> real) : unit286ensures { eval env res = A.real c *. evalm env m *. eval env p }287= let x = A.real c in288let y = A.real c' in289let em = evalm env m in290let em' = evalm env m' in291let er = eval env r in292assert { eval env t = (x *. y) *. (em *. em') };293assert { eval env rest = x *. em *. er };294assert { eval env p = y *. em' +. er };295assert { x *. em *. (y *. em' +. er) = (x *. y) *. (em *. em') +. x *. em *. er } in296res297end298Valid (107ms) (colibri2)299let rec mul (p q:poly) : poly300requires { wf p /\ wf q }301ensures { wf result }302ensures { forall env. eval env result = eval env p *. eval env q }303variant { p }304= match p with305| Nil -> Nil306| Cons (m, c) r -> add (mul_term m c q) (mul r q)307end308
The product of the polynomials f a for the atoms a of m
Valid (58ms) (colibri2)let rec compose_mono (f: Atom.t -> poly) (m:mono) : poly311requires { forall a. wf (f a) }312ensures { wf result }313ensures { forall env env'. (forall a. env' a = eval env (f a)) ->314eval env result = evalm env' m }315variant { m }316= match m with317| Nil -> cst (A.of_int 1)318| Cons a r -> mul (f a) (compose_mono f r)319end320
Every atom a of p replaced by f a
Valid (759ms) (colibri2)let rec compose (f: Atom.t -> poly) (p:poly) : poly323requires { forall a. wf (f a) }324requires { wf p }325ensures { wf result }326ensures { forall env env'. (forall a. env' a = eval env (f a)) ->327eval env result = eval env' p }328variant { p }329= match p with330| Nil -> Nil331| Cons (m, c) r -> add (scale c (compose_mono f m)) (compose f r)332end333
The number of monomials of p that contain a
function occ (a:Atom.t) (p:poly) : int =335match p with336| Nil -> 0337| Cons (m, _) r -> (if mem a m then 1 else 0) + occ a r338end339
a is in a monomial of p
predicate occurs (a:Atom.t) (p:poly) =342match p with343| Nil -> false344| Cons (m, _) r -> mem a m \/ occurs a r345end346Valid (32ms) (colibri2)347let rec ghost occ_nonneg (a:Atom.t) (p:poly) : unit348ensures { 0 <= occ a p }349ensures { occurs a p <-> occ a p > 0 }350variant { p }351= match p with Nil -> () | Cons _ r -> occ_nonneg a r end352Valid (35ms) (colibri2)353let rec ghost occurs_has (a:Atom.t) (p:poly) : mono354requires { occurs a p }355ensures { has result p /\ mem a result }356variant { p }357= match p with358| Nil -> absurd359| Cons (m, _) r -> if pure { mem a m } then m else occurs_has a r360end361Valid (38ms) (colibri2)362let rec ghost has_occurs (a:Atom.t) (p:poly) (m:mono) : unit363requires { has m p /\ mem a m }364ensures { occurs a p }365variant { p }366= match p with367| Nil -> absurd368| Cons (m', _) r -> if pure { m <> m' } then has_occurs a r m369end370
Where a occurs once, two monomials that contain a are the same
Valid (38ms) (colibri2 11) (split_vc 3) (depth 3)let rec ghost occ_one (a:Atom.t) (p:poly) (m1 m2:mono) : unit373requires { occ a p = 1 }374requires { has m1 p /\ mem a m1 }375requires { has m2 p /\ mem a m2 }376ensures { m1 = m2 }377variant { p }378= match p with379| Nil -> absurd380| Cons (m, _) r ->381occ_nonneg a r;382if pure { m1 <> m } then has_occurs a r m1;383if pure { m2 <> m } then has_occurs a r m2;384if pure { m1 <> m /\ m2 <> m } then begin385if pure { mem a m } then absurd else occ_one a r m1 m2386end387end388Valid (32ms) (colibri2)389let rec mem_atom (a:Atom.t) (m:mono) : bool390ensures { result <-> mem a m }391variant { m }392= match m with393| Nil -> false394| Cons b r -> Atom.equal a b || mem_atom a r395end396Valid (33ms) (colibri2)397let rec occ_p (a:Atom.t) (p:poly) : int398ensures { result = occ a p }399variant { p }400= match p with401| Nil -> 0402| Cons (m, _) r -> (if mem_atom a m then 1 else 0) + occ_p a r403end404
The coefficient of m in p (zero if absent)
function coef (m:mono) (p:poly) : real =407match p with408| Nil -> 0.0409| Cons (m', c) r -> if m = m' then A.real c else coef m r410end411
p without its term on m, and the coefficient of that term
Valid (769ms) (colibri2)let rec remove (m:mono) (p:poly) : (poly, A.t)414requires { wf p }415returns { (q, c) -> wf q416/\ (forall m'. has m' q <-> has m' p /\ m' <> m)417/\ (has m p -> A.real c <> 0.0)418/\ (forall env. eval env q = eval env p -. A.real c *. evalm env m) }419variant { p }420= match p with421| Nil -> Nil, A.of_int 0422| Cons (m', c') r ->423if Mono.compare m m' = 0 then begin424mlt_irrefl m;425r, c'426end else begin427let q, c = remove m r in428if pure { has m p } then assert { has m r };429Cons (m', c') q, c430end431end432
Search in l an atom x that is a monomial and occurs once in p
Valid (67ms) (colibri2)let rec find (p l:poly) : option Atom.t435requires { wf p }436ensures { match result with437| Some x -> has (Cons x Nil) l /\ occ x p = 1438| None -> forall x. has (Cons x Nil) l -> occ x p <> 1439end }440variant { l }441= match l with442| Nil -> None443| Cons (Cons x Nil, _) r -> if occ_p x p = 1 then Some x else find p r444| Cons _ r -> find p r445end446447type solved =448| Zero449| Contra450| Solved Atom.t poly451| NotSolved452
The non zero constants
predicate is_cst (p:poly) =455match p with456| Cons (Nil, _) Nil -> true457| _ -> false458end459
Solve the equation p = 0. Solved x q: the equation is x = q, and x is not in q. NotSolved exactly when no atom x is a monomial of p and occurs once in p (and p is not a constant).
Valid (1.1s) (colibri2 40) (cvc4 2) (cvc5) (split_vc 3) (depth 2)let solve (p:poly) : solved464requires { wf p }465ensures { match result with466| Zero -> p = Nil467| Contra -> is_cst p /\ (forall env. eval env p <> 0.0)468| Solved x q ->469has (Cons x Nil) p /\ occ x p = 1 /\ wf q /\ not (occurs x q)470/\ (forall env. eval env p = 0.0 <-> env x = eval env q)471| NotSolved ->472p <> Nil /\ not (is_cst p) /\ (forall x. has (Cons x Nil) p -> occ x p <> 1)473end }474= match p with475| Nil -> Zero476| Cons (Nil, _) Nil -> Contra477| _ ->478match find p p with479| None -> NotSolved480| Some x ->481let mx = Cons x Nil in482let rest, c = remove mx p in483let k = A.div (A.of_int (-1)) c in484assert { A.real k *. A.real c = -1.0 };485let q = scale k rest in486let lemma no (m:mono) : unit487requires { has m q }488ensures { not (mem x m) }489= if pure { mem x m } then occ_one x p m mx in490if pure { occurs x q } then begin491let m = occurs_has x q in no m492end;493let lemma ev (env: Atom.t -> real) : unit494ensures { eval env p = 0.0 <-> env x = eval env q }495= let e = eval env p in496let r = eval env rest in497let vk = A.real k in498let vc = A.real c in499assert { evalm env mx = env x };500assert { r = e -. vc *. env x };501assert { eval env q = vk *. r };502assert { vk *. vc = -1.0 };503assert { vk *. (e -. vc *. env x) = vk *. e +. env x };504assert { vc <> 0.0 };505assert { e = 0.0 <-> vk *. e = 0.0 } in506Solved x q507end508end509
p divided by the atom a, when a divides all the monomials
Valid (63ms) (colibri2 11) (split_vc) (depth 1)let rec div_atom (a:Atom.t) (p:poly) : option poly511requires { wf p }512ensures { match result with513| Some q -> wf q /\ (forall env. eval env p = env a *. eval env q)514| None -> exists m. has m p /\ not (mem a m)515end }516variant { p }517= match p with518| Nil -> Some Nil519| Cons (m, c) r ->520if mem_atom a m then521match div_atom a r with522| None -> None523| Some q ->524let m' = Mono.remove_one a m in525let t = Cons (m', c) Nil in526let res = add t q in527let lemma ev (env: Atom.t -> real) : unit528ensures { eval env p = env a *. eval env res }529= let x = A.real c in530assert { evalm env m = env a *. evalm env m' };531assert { eval env t = x *. evalm env m' };532assert { eval env r = env a *. eval env q };533assert { x *. (env a *. evalm env m') +. env a *. eval env q534= env a *. (x *. evalm env m' +. eval env q) } in535Some res536end537else None538end539
Factor out of p the atoms of l that divide all its monomials: g * p = g' * q
Valid (117ms) (colibri2 10) (split_vc) (depth 1)let rec factor_atoms (l: list Atom.t) (g:mono) (p:poly) : (mono, poly)543requires { wf p /\ sorted g }544returns { (g', q) -> sorted g' /\ wf q545/\ (forall env. evalm env g *. eval env p = evalm env g' *. eval env q) }546variant { l }547= match l with548| Nil -> (g, p)549| Cons a l ->550match div_atom a p with551| None -> factor_atoms l g p552| Some q ->553let g1 = Mono.mul (Cons a Nil) g in554let lemma ev (env: Atom.t -> real) : unit555ensures { evalm env g *. eval env p = evalm env g1 *. eval env q }556= assert { evalm env g1 = env a *. evalm env g };557assert { eval env p = env a *. eval env q } in558factor_atoms l g1 q559end560end561
The factorization p = k * g * q: g is the product of the common atoms of the monomials of p (with multiplicity), and q is divided by its first coefficient
Valid (50ms) (colibri2 17) (split_vc 4) (depth 4)let factor (p:poly) : (A.t, mono, poly)566requires { wf p }567returns { (k, g, q) -> A.real k <> 0.0 /\ sorted g /\ wf q568/\ (forall env. eval env p = A.real k *. evalm env g *. eval env q) }569= match p with570| Nil -> (A.of_int 1, Nil, Nil)571| Cons (m, _) _ ->572let g, q = factor_atoms m Nil p in573match q with574| Nil -> (A.of_int 1, g, Nil)575| Cons (_, c) _ ->576let k1 = A.div (A.of_int 1) c in577assert { A.real k1 *. A.real c = 1.0 };578let q1 = scale k1 q in579let lemma ev (env: Atom.t -> real) : unit580ensures { eval env p = A.real c *. evalm env g *. eval env q1 }581= let vk = A.real k1 in582let vc = A.real c in583assert { evalm env Nil = 1.0 };584assert { eval env p = evalm env g *. eval env q };585assert { eval env q1 = vk *. eval env q };586assert { vc *. vk = 1.0 };587assert { vc *. evalm env g *. (vk *. eval env q)588= (vc *. vk) *. (evalm env g *. eval env q) } in589(c, g, q1)590end591end592end593