library colibrilib.dom_modrw — module Keymodule Key9use int.Int10use real.RealInfix11use real.Abs12use list.List13use option.Option14use colibrilib.ring.Atom15use colibrilib.stda.StdA as A16use colibrilib.q.Real as Real17use colibrilib.polynome.Assoc18use colibrilib.polynome.PT19use colibrilib.polynome.Lin20use colibrilib.polynome.ModRw21use colibrilib.product.Prod as P22use colibrilib.env.Env23use colibrilib.env.Interval24use colibrilib.env.Linear as L25use colibrilib.env.AbsProduct as AP26use colibrilib.spec.Opt27use colibrilib.spec.Test28
The divisor: a constant |m|, or a node y with |den| = |y|
type div = Cst A.t | Abs Atom.t3132function dv (m:Atom.t -> real) (v:div) : real =33match v with Cst c -> A.real c | Abs y -> m y end34
(p, v) is a key of mod_e x den in the model m
predicate is_key (m:Atom.t -> real) (x den:Atom.t) (p:Lin.t) (v:div) =37m den <> 0.0 /\ abs (dv m v) = abs (m den) /\38Real.mod_e (m x) (m den) = Real.mod_e (eval m p) (dv m v)39
The values of the atoms of l are integers
predicate integers (m:Atom.t -> real) (l:list binding) =42forall k. has k l -> Real.is_integer (m k)43
The nodes a and b have the same absolute value
predicate same_abs (m:Atom.t -> real) (a b:Atom.t) = abs (m a) = abs (m b)46
k is a key of mod_e x den in the model of d, reduced: a linear form in normal form, and for a constant divisor a constant of the polynomial in [0, |c|)
predicate reduced_key (d:env) (x den:Atom.t) (k:(Lin.t, div)) =51let p, v = k in52(live d -> is_key d.m x den p v) /\53match v with54| Cst c -> 0.0 <=. A.real p.cst <. A.real c55| Abs _ -> true56end57
The atoms of l are integers
Valid (31ms) (colibri2)let rec all_integer (d:env) (l:list binding) : bool60variant { l }61ensures { decides_sound (live d -> integers d.m l) result }62= match l with63| Nil -> true64| Cons (k, _) r -> is_integer d k && all_integer d r65end66
A node y with |den| = |y|: den = ±y, or the product |y|
Valid (634ms) (colibri2)let partial abs_node (d:env) (den:Atom.t) : Atom.t69ensures { live d -> same_abs d.m result den }70= let partial from_product () : Atom.t71ensures { live d -> same_abs d.m result den }72= match AP.get_repr d den with73| Some a -> (match P.is_one_node a with Some y -> y | None -> den end)74| None -> den75end76in77let y = match L.get_repr d den with78| Some q ->79match is_pm_node q with80| Some y -> if is_equal d y den then from_product () else y81| None -> from_product ()82end83| None -> from_product ()84end85in86find_def d y87
The key of mod_e x den
Valid (1.1s) (colibri2 18) (cvc4 7) (split_vc 12) (depth 3)let partial key (d:env) (x den:Atom.t) : option (Lin.t, div)90ensures { when_some (reduced_key d x den) result }91= let p = match L.get_repr d x with92| Some p -> p93| None -> monome (A.of_int 1) (find_def d x)94end95in96match value d den with97| Some c ->98if not (A.equal c (A.of_int 0)) && all_integer d (atoms p) then begin99let p' = reduce_cst p c in100assert { live d -> integer_atoms p d.m };101let ac = A.abs c in102let lemma l () : unit103ensures { Real.mod_e (eval d.m p') (A.real c) = Real.mod_e (eval d.m p') (A.real ac) }104= mod_abs (eval d.m p') (A.real c) (A.real ac) in105assert { 0.0 <=. A.real p'.cst <. A.real ac };106assert { live d -> is_key d.m x den p' (Cst ac) };107assert { reduced_key d x den (p', Cst ac) };108Some (p', Cst ac)109end else None110| None ->111if is_not_zero d den then begin112let y = abs_node d den in113let p' = reduce_node p y in114let lemma l () : unit115requires { live d }116ensures { Real.mod_e (eval d.m p') (d.m den) = Real.mod_e (eval d.m p') (d.m y) }117= mod_abs (eval d.m p') (d.m den) (d.m y) in118let lemma k () : unit119requires { live d }120ensures { is_key d.m x den p' (Abs y) }121= assert { Real.mod_e (eval d.m p) (d.m den) = Real.mod_e (eval d.m p') (d.m den) } in122Some (p', Abs y)123end else None124end125126end127