library colibrilib.dom_ring — module RingThe normal forms, proved
module Ring183use int.Int184use real.RealInfix185use list.List186use list.Mem187use list.Length188use option.Option189use colibrilib.ring.Atom190use colibrilib.ring.Mono191use colibrilib.ring.Poly as P192use colibrilib.stda.StdA as A193use colibrilib.ring.Export as R194use colibrilib.polynome.Assoc195use colibrilib.polynome.PT196use colibrilib.polynome.Lin as L197use colibrilib.env.Env198use colibrilib.env.Interval199use colibrilib.env.Linear200use colibrilib.spec.Opt201use Env202
The linear form of the terms l of a normal form, with product nodes
Valid (602ms) (colibri2 5) (split_vc) (depth 1)let rec linear_terms (d:env) (l:P.poly) : L.t205variant { l }206ensures { live d -> L.eval d.m result = P.eval d.m l }207= match l with208| Nil -> L.zero ()209| Cons (m, c) r ->210let rest = linear_terms d r in211match m with212| Nil -> L.add_cst rest c213| Cons x Nil -> L.add (L.monome c x) rest214| _ ->215let pn = product_node m in216watch_product d pn;217L.add (L.monome c pn) rest218end219end220
The linear form of a normal form
Valid (16ms) (colibri2)let linear (d:env) (p:R.t) : L.t223ensures { live d -> L.eval d.m result = R.eval d.m p }224= linear_terms d (R.get p)225
The normal form of a free node y in the linear form of x: not used when it contains x (a cycle)
Valid (28ms) (colibri2)let free (d:env) (x y:Atom.t) : R.t229ensures { is_nf d y result }230= match find_nf d y with231| Some p -> if P.occ_p x (R.get p) = 0 then p else R.var y232| None -> R.var y233end234
The product of the normal forms of the atoms of m
Valid (307ms) (colibri2)let rec free_mono (d:env) (x:Atom.t) (m:mono) : R.t237variant { m }238ensures { live d -> R.eval d.m result = evalm d.m m }239= match m with240| Nil -> R.cst (A.of_int 1)241| Cons a r -> R.mul (free d x a) (free_mono d x r)242end243
The normal form of the bindings of a linear form
Valid (597ms) (colibri2)let rec free_bindings (d:env) (x:Atom.t) (l:list binding) : R.t246variant { l }247ensures { live d -> R.eval d.m result = evall d.m l }248= match l with249| Nil -> R.zero ()250| Cons (y, k) r ->251let my = match monomial y with252| None -> free d x y253| Some m -> free_mono d x m254end in255R.add (R.scale k my) (free_bindings d x r)256end257
The normal form of the linear form of x (a node or a product node), if x is eliminated by Dom_polynome
Valid (169ms) (cvc4)let eliminated (d:env) (x:Atom.t) : option R.t261ensures { when_some (is_nf d x) result }262= match Linear.get_repr d x with263| Some l ->264if is_self l x then None265else Some (R.add (R.cst (L.cst_of l)) (free_bindings d x (L.atoms l)))266| None -> None267end268
The normal form of the atom x
Valid (22ms) (colibri2)let atom (d:env) (x:Atom.t) : R.t271ensures { is_nf d x result }272= match find_nf d x with273| Some p -> p274| None ->275match eliminated d x with276| Some p -> p277| None -> R.var x278end279end280
The atoms of a normal form replaced by their normal forms
Valid (316ms) (colibri2)let rec subst_mono (d:env) (m:mono) : R.t283variant { m }284ensures { live d -> R.eval d.m result = evalm d.m m }285= match m with286| Nil -> R.cst (A.of_int 1)287| Cons a r -> R.mul (atom d a) (subst_mono d r)288end289Valid (111ms) (colibri2)290let rec subst_terms (d:env) (l:P.poly) : R.t291variant { l }292ensures { live d -> R.eval d.m result = P.eval d.m l }293= match l with294| Nil -> R.zero ()295| Cons (m, c) r -> R.add (R.scale c (subst_mono d m)) (subst_terms d r)296end297
x is used by n for each atom x of the terms l
Valid (23ms) (colibri2)let rec add_used_terms (d:env) (n:Atom.t) (l:P.poly) : unit300variant { l }301= match l with302| Nil -> ()303| Cons (m, _) r ->304let rec add_mono (m:mono) : unit variant { m } =305match m with Nil -> () | Cons x r -> add_used d x n; add_mono r end in306add_mono m;307add_used_terms d n r308end309
p = c * q, with the first coefficient of q equal to one
Valid (406ms) (colibri2 5) (split_vc 4) (depth 4)let to_monic (p:R.t) : (A.t, R.t)314returns { (c, q) -> A.real c <> 0.0 /\315forall env. R.eval env p = A.real c *. R.eval env q }316= match R.get p with317| Cons (_, c) _ ->318if A.equal c (A.of_int 1) then (A.of_int 1, p)319else (c, R.scale (A.div (A.of_int 1) c) p)320| Nil -> (A.of_int 1, p)321end322
The pending factorizations of n = c * q
Valid (385ms) (colibri2 7) (cvc5 2) (split_vc 2) (depth 2)let rec products_pending (d:env) (n:Atom.t) (c:A.t) (q:R.t)325(l:list (Atom.t, A.t, mono)) : unit326requires { A.real c <> 0.0 }327requires { live d -> d.m n = A.real c *. R.eval d.m q }328requires { live d -> pending_ok d.m q l }329variant { l }330= match l with331| Nil -> ()332| Cons (n', k, g) r ->333let k' = A.div k c in334{proof…}335assert { live d -> d.m n' = A.real k' *. evalm d.m (Cons n g)336by d.m n' = A.real k *. evalm d.m g *. R.eval d.m q337so evalm d.m (Cons n g) = d.m n *. evalm d.m g };338{qed}339product d n' k' (Cons n g);340products_pending d n c q r341end342
n = k * g * q: given to Dom_product when q is a constant or the normal form of a node, else waits for this node
Valid (570ms) (colibri2 10) (split_vc) (depth 1)let factorize (d:env) (n:Atom.t) (p:R.t) : unit346requires { is_nf d n p }347= let k, g, q = R.factor p in348match g, R.get q with349| Nil, _ -> ()350| Cons _ Nil, Cons (Nil, _) Nil -> (* linear *) ()351| _, Cons (Nil, c) Nil -> (* a monomial *) product d n (A.mul k c) g352| _ ->353match find_monic d q with354| Some (m, c) -> product d n (A.div k c) (Cons m g)355| None -> set_pending d q (Cons (n, k, g) (find_pending d q))356end357end358
p is the normal form of n: the factorization of the first node of normal form p (the others are merged with it by Dom_polynome)
Valid (30ms) (colibri2 14) (split_vc) (depth 1)let table_set (d:env) (n:Atom.t) (p:R.t) : unit362requires { is_nf d n p }363= match R.get p with364| Nil | Cons (Nil, _) Nil -> ()365| _ ->366if not (table_mem d p) then begin367table_add d p n;368let c, q = to_monic p in369(match find_monic d q with370| None ->371set_monic d q n c;372let l = find_pending d q in373remove_pending d q;374products_pending d n c q l375| Some _ -> ()376end);377factorize d n p378end379end380
p is the normal form of n
Valid (29ms) (colibri2 7) (split_vc 4) (depth 2)let rec set (d:env) (n:Atom.t) (p:R.t) : unit385requires { is_nf d n p }386diverges387= let same_nf = match find_nf d n with388| Some p' -> same p p'389| None -> false390end in391if length (R.get p) <= max_terms d && not same_nf then begin392if P.occ_p n (R.get p) > 0 then begin393(* [n = p(n)] is an equation, not a definition *)394remove_nf d n;395assume_linear d n (linear d p)396end else begin397set_nf d n p;398add_used_terms d n (R.get p);399table_set d n p;400assume_linear d n (linear d p)401end;402changed d n403end404
The normal form of x changed: the normal forms that use it are updated
with changed (d:env) (x:Atom.t) : unit408diverges409= changed_list d x (used d x)410Valid (27ms) (colibri2)411with changed_list (d:env) (x:Atom.t) (l:list Atom.t) : unit412diverges413= match l with414| Nil -> ()415| Cons n r ->416(match find_nf d n with417| Some p -> if P.occ_p x (R.get p) > 0 then set d n (subst_terms d (R.get p))418| None -> ()419end);420changed_list d x r421end422
Dom_polynome eliminates the product node pm of the monomial m with the linear form l: the equation m = l is solved in the ring, for an atom alone in its monomial.
Valid (485ms) (cvc4)let solve_product (d:env) (pm:Atom.t) : unit427diverges428= match monomial pm with429| Some m ->430match eliminated d pm with431| Some l ->432let pm' = subst_mono d m in433match R.solve (R.sub pm' l) with434| R.Zero | R.NotSolved -> ()435| R.Contra -> contradiction d436| R.Solved x q -> set d x q437end438| None -> ()439end440| None -> ()441end442end443