library colibrilib.polynome — module LinThe linear polynomials
module Lin320use int.Int321use real.RealInfix322use real.Abs323use list.List324use list.Length325use option.Option326use colibrilib.ring.Atom327use colibrilib.stda.StdA as A328use Assoc329use PT330use colibrilib.spec.Sound331use colibrilib.spec.Eval332use colibrilib.spec.Value333use colibrilib.spec.Test334use colibrilib.spec.Opt335
The coefficient a, unless it is zero
Valid (38ms) (colibri2)let function nz (a:A.t) : option A.t338ensures { result = nzv a }339= if A.is_zero a then None else Some a340
No zero coefficient: every value of t is well formed
Valid (126ms) (colibri2)type t = { cst: A.t; poly: PT.t }343invariant { nonzero (bindings poly) }344by { cst = A.of_int 0; poly = PT.empty () }345346function eval (env: Atom.t -> real) (p:t) : real =347A.real p.cst +. evall env (bindings p.poly)348
The evaluation of a map is given by its bindings
Valid (807ms) (colibri2 5) (split_vc) (depth 1)let ghost same_eval (m:PT.t) (l1 l2:list binding) (c1 c2:A.t) : unit351requires { sorted l1 /\ sorted l2 }352requires { forall k. oeq (get k m) (comb c1 c2 (assoc k l1) (assoc k l2)) }353ensures { nonzero (bindings m) }354ensures { forall env. evall env (bindings m)355= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }356= let l = lcomb c1 c2 l1 l2 in357ext_eval (bindings m) l358
eval with the arguments in the order of the shapes of spec.Eval
function value (p:t) (env: Atom.t -> real) : real = eval env p361
p has the value of the atom n
predicate is_node (p:t) (n:Atom.t) = denotes0 value (fun env -> env n) p364
p has the absolute value of the atom y
predicate is_abs_node (p:t) (y:Atom.t) =367forall env. abs (eval env p) = abs (env y)368Valid (29ms) (colibri2)369let zero () : t370ensures { denotes0 value (fun _ -> 0.0) result }371= { cst = A.of_int 0; poly = PT.empty () }372Valid (26ms) (colibri2)373let const (c:A.t) : t374ensures { denotes0 value (fun _ -> A.real c) result }375= { cst = c; poly = PT.empty () }376
c * x
Valid (51ms) (colibri2)let monome (c:A.t) (x:Atom.t) : t379ensures { denotes0 value (fun env -> A.real c *. env x) result }380= if A.equal c (A.of_int 0) then { cst = A.of_int 0; poly = PT.empty () }381else { cst = A.of_int 0; poly = PT.singleton x c }382Valid (28ms) (colibri2)383let is_cst (p:t) : option A.t384ensures { match result with385| Some c -> bindings p.poly = Nil /\ c = p.cst386| None -> bindings p.poly <> Nil387end }388= if PT.is_empty p.poly then Some p.cst else None389Valid (30ms) (colibri2)390let is_zero (p:t) : bool391ensures { decides (bindings p.poly = Nil /\ A.real p.cst = 0.0) result }392= A.equal p.cst (A.of_int 0) && PT.is_empty p.poly393Valid (22ms) (colibri2)394let add_cst (p:t) (c:A.t) : t395ensures { denotes1 value (fun v -> v +. A.real c) p result }396= { p with cst = A.add p.cst c }397Valid (26ms) (colibri2)398let sub_cst (p:t) (c:A.t) : t399ensures { denotes1 value (fun v -> v -. A.real c) p result }400= { p with cst = A.sub p.cst c }401
The closure of add, x_p_cy and cx_p_cy: c1 * o1 + c2 * o2
Valid (20ms) (colibri2)let function combf (c1 c2:A.t) (_k:Atom.t) (o1 o2:option A.t) : option A.t =404match o1, o2 with405| None, None -> None406| Some a, None -> nz (A.mul c1 a)407| None, Some b -> nz (A.mul c2 b)408| Some a, Some b -> nz (A.add (A.mul c1 a) (A.mul c2 b))409end410
c1 * p1 + c2 * p2
Valid (432ms) (colibri2 7) (cvc5) (split_vc) (depth 1)let cx_p_cy (c1:A.t) (p1:t) (c2:A.t) (p2:t) : t413ensures { denotes2 value (fun x y -> A.real c1 *. x +. A.real c2 *. y) p1 p2 result }414= let m = PT.merge (combf c1 c2) p1.poly p2.poly in415same_eval m (bindings p1.poly) (bindings p2.poly) c1 c2;416let res = { cst = A.add (A.mul c1 p1.cst) (A.mul c2 p2.cst); poly = m } in417let lemma ev (env: Atom.t -> real) : unit418ensures { eval env res419= A.real c1 *. eval env p1 +. A.real c2 *. eval env p2 }420= let e1 = evall env (bindings p1.poly) in421let e2 = evall env (bindings p2.poly) in422assert { eval env res = A.real c1 *. A.real p1.cst +. A.real c2 *. A.real p2.cst423+. (A.real c1 *. e1 +. A.real c2 *. e2) };424assert { A.real c1 *. (A.real p1.cst +. e1) +. A.real c2 *. (A.real p2.cst +. e2)425= A.real c1 *. A.real p1.cst +. A.real c2 *. A.real p2.cst426+. (A.real c1 *. e1 +. A.real c2 *. e2) } in427res428
The closure of add: no multiplication
Valid (24ms) (colibri2)let function addf (_k:Atom.t) (o1 o2:option A.t) : option A.t =431match o1, o2 with432| None, o | o, None -> o433| Some a, Some b -> nz (A.add a b)434end435Valid (385ms) (colibri2 11) (cvc4) (split_vc 2) (depth 2)436let add (p1 p2:t) : t437ensures { denotes2 value (+.) p1 p2 result }438= let m = PT.merge addf p1.poly p2.poly in439let ghost one = A.of_int 1 in440let lemma pw (k:Atom.t) : unit441ensures { oeq (get k m) (comb one one (get k p1.poly) (get k p2.poly)) }442= match get k p1.poly, get k p2.poly with443| Some a, None -> assert { A.real (A.mul one a) = A.real a }444| None, Some b -> assert { A.real (A.mul one b) = A.real b }445| Some a, Some b -> assert { A.real (A.add (A.mul one a) (A.mul one b)) = A.real (A.add a b) }446| None, None -> ()447end in448same_eval m (bindings p1.poly) (bindings p2.poly) one one;449{ cst = A.add p1.cst p2.cst; poly = m }450
The closure of sub, m1 is -1
Valid (27ms) (colibri2)let function subf (m1:A.t) (_k:Atom.t) (o1 o2:option A.t) : option A.t =453match o1, o2 with454| o, None -> o455| None, Some b -> nz (A.mul m1 b)456| Some a, Some b -> nz (A.sub a b)457end458Valid (1.4s) (colibri2 9) (cvc5) (split_vc 2) (depth 2)459let sub (p1 p2:t) : t460ensures { denotes2 value (-.) p1 p2 result }461= let ghost one = A.of_int 1 in462let m1 = A.of_int (-1) in463let m = PT.merge (subf m1) p1.poly p2.poly in464let lemma pw (k:Atom.t) : unit465ensures { oeq (get k m) (comb one m1 (get k p1.poly) (get k p2.poly)) }466= match get k p1.poly, get k p2.poly with467| Some a, None -> assert { A.real (A.mul one a) = A.real a }468| Some _, Some _ ->469()470| _ -> ()471end in472same_eval m (bindings p1.poly) (bindings p2.poly) one m1;473{ cst = A.sub p1.cst p2.cst; poly = m }474
The closure of mult_cst
Valid (22ms) (colibri2)let function mulf (c v:A.t) : A.t = A.mul c v477
c * p
Valid (223ms) (colibri2 8) (split_vc) (depth 1)let mult_cst (c:A.t) (p:t) : t480ensures { denotes1 value (fun v -> A.real c *. v) p result }481= if A.equal c (A.of_int 1) then p482else if A.equal c (A.of_int 0) then zero ()483else begin484let m = PT.map (mulf c) p.poly in485let ghost z = A.of_int 0 in486let lemma pw (k:Atom.t) : unit487ensures { oeq (get k m) (comb c z (get k p.poly) None) }488= match get k p.poly with489| Some v -> assert { A.real (A.mul c v) <> 0.0 }490| None -> ()491end in492same_eval m (bindings p.poly) Nil c z;493let res = { cst = A.mul c p.cst; poly = m } in494let lemma ev (env: Atom.t -> real) : unit495ensures { eval env res = A.real c *. eval env p }496= let e = evall env (bindings p.poly) in497assert { A.real c *. (A.real p.cst +. e) = A.real c *. A.real p.cst +. A.real c *. e } in498res499end500Valid (55ms) (colibri2)501let neg (p:t) : t502ensures { denotes1 value (fun v -> -. v) p result }503= mult_cst (A.of_int (-1)) p504
The closure of x_p_cy
Valid (28ms) (colibri2)let function xpcyf (c:A.t) (_k:Atom.t) (o1 o2:option A.t) : option A.t =507match o1, o2 with508| o, None -> o509| None, Some b -> nz (A.mul c b)510| Some a, Some b -> nz (A.add a (A.mul c b))511end512
p1 + c * p2
Valid (1.1s) (colibri2 11) (cvc5) (split_vc 2) (depth 2)let x_p_cy (p1:t) (c:A.t) (p2:t) : t515ensures { denotes2 value (fun x y -> x +. A.real c *. y) p1 p2 result }516= let ghost one = A.of_int 1 in517let m = PT.merge (xpcyf c) p1.poly p2.poly in518let lemma pw (k:Atom.t) : unit519ensures { oeq (get k m) (comb one c (get k p1.poly) (get k p2.poly)) }520= match get k p1.poly, get k p2.poly with521| Some a, None -> assert { A.real (A.mul one a) = A.real a }522| Some _, Some _ ->523()524| _ -> ()525end in526same_eval m (bindings p1.poly) (bindings p2.poly) one c;527let res = { cst = A.add p1.cst (A.mul c p2.cst); poly = m } in528let lemma ev (env: Atom.t -> real) : unit529ensures { eval env res = eval env p1 +. A.real c *. eval env p2 }530= let e2 = evall env (bindings p2.poly) in531assert { A.real c *. (A.real p2.cst +. e2) = A.real c *. A.real p2.cst +. A.real c *. e2 } in532res533
The coefficient of x in p (zero if absent)
function coef (x:Atom.t) (p:t) : real =536match get x p.poly with None -> 0.0 | Some v -> A.real v end537
p without its monomial on x
Valid (242ms) (colibri2 7) (split_vc) (depth 1)let remove (x:Atom.t) (p:t) : t540ensures { result.cst = p.cst }541ensures { not (has x (bindings result.poly)) }542ensures { denotes0 value (fun env -> eval env p -. coef x p *. env x) result }543= let m = PT.remove x p.poly in544let l = lremove x (bindings p.poly) in545ext (bindings m) l;546{ cst = p.cst; poly = m }547
p where x is replaced by s, and the coefficient of x in p
Valid (488ms) (colibri2 6) (split_vc) (depth 1)let subst (p:t) (x:Atom.t) (s:t) : (t, A.t)550returns { (r, q) -> A.real q = coef x p551/\ denotes0 value (fun env -> eval env p +. A.real q *. (eval env s -. env x)) r }552= match PT.find_opt x p.poly with553| None ->554let q = A.of_int 0 in555assert { forall env. eval env p = eval env p +. A.real q *. (eval env s -. env x) };556(p, q)557| Some q ->558let p' = remove x p in559let r = x_p_cy p' q s in560let lemma ev (env: Atom.t -> real) : unit561ensures { eval env r = eval env p +. A.real q *. (eval env s -. env x) }562= assert { eval env p' = eval env p -. A.real q *. env x };563assert { eval env r = eval env p' +. A.real q *. eval env s };564assert { A.real q *. (eval env s -. env x)565= A.real q *. eval env s -. A.real q *. env x } in566(r, q)567end568
The closure of subst_node
Valid (20ms) (colibri2)let function updf (q:A.t) (o:option A.t) : option A.t =571match o with None -> Some q | Some q' -> nz (A.add q q') end572
p where x is replaced by y, and the coefficient of x in p
Valid (1.1s) (colibri2 14) (split_vc) (depth 1)let subst_node (p:t) (x y:Atom.t) : (t, A.t)575returns { (r, q) -> A.real q = coef x p576/\ denotes0 value (fun env -> eval env p +. A.real q *. (env y -. env x)) r }577= match PT.find_opt x p.poly with578| None ->579let q = A.of_int 0 in580assert { forall env. eval env p = eval env p +. A.real q *. (env y -. env x) };581(p, q)582| Some q ->583let p' = remove x p in584let m = PT.update y (updf q) p'.poly in585let ghost one = A.of_int 1 in586let ghost ly = Cons (y, one) Nil in587let lemma pw (k:Atom.t) : unit588ensures { oeq (get k m) (comb one q (get k p'.poly) (assoc k ly)) }589= if pure { k = y } then590match get k p'.poly with591| None -> assert { A.real (A.mul q one) = A.real q }592| Some q' -> assert { A.real (A.add (A.mul one q') (A.mul q one)) = A.real (A.add q q') }593end594else595match get k p'.poly with596| None -> ()597| Some a -> assert { A.real (A.mul one a) = A.real a }598end in599same_eval m (bindings p'.poly) ly one q;600let r = { cst = p.cst; poly = m } in601let lemma ev (env: Atom.t -> real) : unit602ensures { eval env r = eval env p +. A.real q *. (env y -. env x) }603= assert { evall env ly = env y };604assert { evall env (bindings m) = evall env (bindings p'.poly) +. A.real q *. env y };605assert { eval env p' = eval env p -. A.real q *. env x };606assert { A.real q *. (env y -. env x) = A.real q *. env y -. A.real q *. env x } in607(r, q)608end609610type extract =611| Zero612| Cst A.t613| Var A.t Atom.t t614
Var q x p': p = q * x + p'
Valid (325ms) (colibri2)let extract (p:t) : extract617ensures { match result with618| Zero -> bindings p.poly = Nil /\ A.real p.cst = 0.0619| Cst c -> bindings p.poly = Nil /\ c = p.cst /\ A.real c <> 0.0620| Var q x p' -> get x p.poly = Some q /\ not (has x (bindings p'.poly))621/\ denotes0 value (fun env -> A.real q *. env x +. eval env p') p622end }623= if PT.is_empty p.poly then624if A.equal p.cst (A.of_int 0) then Zero else Cst p.cst625else begin626let x, q = PT.pivot_binding p.poly in627Var q x (remove x p)628end629630type kind = ZERO | CST | VAR631Valid (33ms) (colibri2)632let classify (p:t) : kind633ensures { match result with634| ZERO -> bindings p.poly = Nil /\ A.real p.cst = 0.0635| CST -> bindings p.poly = Nil /\ A.real p.cst <> 0.0636| VAR -> bindings p.poly <> Nil637end }638= if PT.is_empty p.poly then639if A.equal p.cst (A.of_int 0) then ZERO else CST640else VAR641
p is the node n
Valid (241ms) (colibri2)let is_one_node (p:t) : option Atom.t644ensures { when_some (is_node p) result }645= if A.equal p.cst (A.of_int 0) && PT.cardinal p.poly = 1 then begin646let n, k = PT.min_binding p.poly in647if A.equal k (A.of_int 1) then begin648assert { match bindings p.poly with649| Cons (n', k') Nil -> n' = n /\ k' = k650| _ -> false end };651Some n652end else None653end else None654
The constant of p
Valid (22ms) (colibri2)let cst_of (p:t) : A.t657ensures { value_is p.cst result }658= p.cst659
The bindings of p
Valid (27ms) (colibri2)let atoms (p:t) : list binding662ensures { value_is (bindings p.poly) result }663= PT.to_list p.poly664
p is y or -y
Valid (1.0s) (cvc5)let is_pm_node (p:t) : option Atom.t667ensures { when_some (is_abs_node p) result }668= if A.equal p.cst (A.of_int 0) && PT.cardinal p.poly = 1 then begin669let y, k = PT.min_binding p.poly in670if A.equal (A.abs k) (A.of_int 1) then begin671assert { match bindings p.poly with672| Cons (y', k') Nil -> y' = y /\ k' = k673| _ -> false end };674Some y675end else None676end else None677
cst + c1 * x1 + ... + cn * xn for the list (x1, c1); ... (the atoms may repeat)
Valid (468ms) (colibri2 11) (split_vc 3) (depth 3)let rec of_list (c:A.t) (l:list binding) : t681ensures { denotes0 value (fun env -> A.real c +. evall env l) result }682variant { l }683= match l with684| Nil -> const c685| Cons (x, q) r ->686let p = of_list c r in687if A.equal q (A.of_int 0) then p688else begin689let m = PT.update x (updf q) p.poly in690let ghost one = A.of_int 1 in691let ghost lx = Cons (x, one) Nil in692let lemma pw (k:Atom.t) : unit693ensures { oeq (get k m) (comb one q (get k p.poly) (assoc k lx)) }694= if pure { k = x } then695match get k p.poly with696| None -> assert { A.real (A.mul q one) = A.real q }697| Some q' -> assert { A.real (A.add (A.mul one q') (A.mul q one)) = A.real (A.add q q') }698end699else700match get k p.poly with701| None -> ()702| Some a -> assert { A.real (A.mul one a) = A.real a }703end in704same_eval m (bindings p.poly) lx one q;705{ cst = p.cst; poly = m }706end707end708end709