library colibrilib.sign_product — module SignThe products of signs, and the solver of the equations between them
module Sign306use int.Int307use mach.int.Int63308use real.RealInfix309use list.List310use list.Mem311use list.Append312use option.Option313use colibrilib.ring.Atom314use SAssoc315use SPT316317type cst = Pos | Neg318
Zero, or P c m: c times the powers of the signs of m
type t = Zero | P cst SPT.t321322function cv (c:cst) : real = match c with Pos -> 1.0 | Neg -> -. 1.0 end323324function eval (env: Atom.t -> real) (p:t) : real =325match p with326| Zero -> 0.0327| P c m -> cv c *. evs env (bindings m)328end329
The nodes OddNonZero are not zero
predicate valid (env: Atom.t -> real) (p:t) =332match p with333| Zero -> true334| P _ m -> lvalid env (bindings m)335end336337predicate mem (k:Atom.t) (p:t) =338match p with339| Zero -> false340| P _ m -> has k (bindings m)341end342Valid (32ms) (colibri2)343let ghost eval_unit3 (env: Atom.t -> real) (p:t) : unit344ensures { unit3 (eval env p) }345ensures { eval env p = 0.0 <-> (p = Zero \/ exists k. mem k p /\ env k = 0.0) }346= match p with347| Zero -> ()348| P _ m -> evs_unit3 env (bindings m)349end350351let function mulc (c1 c2:cst) : cst =352match c1, c2 with353| Pos, c | c, Pos -> c354| Neg, Neg -> Pos355end356
p1 * p2
Valid (48ms) (colibri2 10) (split_vc) (depth 1)let mul (p1 p2:t) : t359ensures { forall env. valid env p1 -> valid env p2 ->360eval env result = eval env p1 *. eval env p2 /\ valid env result }361ensures { forall k. mem k result -> mem k p1 \/ mem k p2 }362= match p1, p2 with363| Zero, _ -> Zero364| _, Zero -> Zero365| P c1 m1, P c2 m2 ->366let m = SPT.merge mulk m1 m2 in367let ghost l = lmul (bindings m1) (bindings m2) in368ext (bindings m) l;369let r = P (mulc c1 c2) m in370let lemma ev (env: Atom.t -> real) : unit371requires { valid env p1 /\ valid env p2 }372ensures { eval env r = eval env p1 *. eval env p2 }373= let e1 = evs env (bindings m1) in374let e2 = evs env (bindings m2) in375assert { evs env (bindings m) = e1 *. e2 };376assert { cv (mulc c1 c2) = cv c1 *. cv c2 };377assert { (cv c1 *. cv c2) *. (e1 *. e2) = (cv c1 *. e1) *. (cv c2 *. e2) } in378r379end380
The solutions: as Solve.solved of product.mlw
type solved =383| AlreadyEqual384| Contradiction385| Subst Atom.t t386
sgn x = q
| Unsolved387
The result of the solving of e: a substitution is equivalent to e
predicate solves (h: (Atom.t -> real) -> bool) (e: (Atom.t -> real) -> bool)390(r:solved) =391match r with392| AlreadyEqual -> forall env. h env -> e env393| Contradiction -> forall env. h env -> not (e env)394| Subst x q -> not mem x q /\395forall env. h env -> (e env <-> sgn (env x) = eval env q /\ valid env q)396| Unsolved -> true397end398
All the powers of l are OddNonZero
Valid (19ms) (colibri2)let rec all_nz_list (l:list binding) : bool401ensures { result -> forall k v. assoc k l = Some v -> v = OddNonZero }402variant { l }403= match l with404| Nil -> true405| Cons (_, OddNonZero) r -> all_nz_list r406| Cons _ _ -> false407end408
p is not zero, by valid
Valid (31ms) (cvc5)let all_nz (p:t) : bool411ensures { result -> forall env. valid env p -> eval env p <> 0.0 }412= match p with413| Zero -> false414| P _ m ->415let r = all_nz_list (SPT.to_list m) in416if r then begin417let lemma nz (env: Atom.t -> real) : unit418requires { valid env p }419ensures { eval env p <> 0.0 }420= eval_unit3 env p in421()422end;423r424end425
A node OddNonZero of l
Valid (35ms) (colibri2 7) (cvc5) (split_vc 2) (depth 2)let rec find_power (w:power) (l:list binding) : option Atom.t428requires { sorted l }429ensures { match result with430| Some x -> assoc x l = Some w431| None -> forall k. assoc k l <> Some w end }432variant { l }433= match l with434| Nil -> None435| Cons (k, v) r ->436if match v, w with437| Odd, Odd | Even, Even | OddNonZero, OddNonZero -> true438| _ -> false end439then Some k440else match find_power w r with441| Some x -> Some x442| None -> None443end444end445
The node to substitute: a node OddNonZero, or else a node Odd when there is no Even
Valid (33ms) (colibri2)let choose_x (l:list binding) : option Atom.t449requires { sorted l }450ensures { match result with451| Some x -> assoc x l = Some OddNonZero \/452(assoc x l = Some Odd /\ forall k. assoc k l <> Some Even)453| None -> true end }454= match find_power OddNonZero l with455| Some x -> Some x456| None ->457match find_power Even l with458| Some _ -> None459| None -> find_power Odd l460end461end462
A solution of an equivalent equation
Valid (30ms) (colibri2)let ghost transfer (h h' e e': (Atom.t -> real) -> bool) (r:solved) : unit465requires { solves h' e' r }466requires { forall env. h env -> h' env /\ (e env <-> e' env) }467ensures { solves h e r }468= ()469
eval p = 1
Valid (724ms) (colibri2 19) (cvc5 3) (split_vc 7) (depth 4)let solve_one (p:t) : solved472ensures { solves (fun env -> valid env p) (fun env -> eval env p = 1.0) result }473= match p with474| Zero -> Contradiction475| P c m ->476if SPT.is_empty m then477match c with Pos -> AlreadyEqual | Neg -> Contradiction end478else begin479let l = SPT.to_list m in480match choose_x l with481| None -> Unsolved482| Some x ->483let r = SPT.remove x m in484let mq = SPT.map liftp r in485let q = P c mq in486let ghost lr = lrem x l in487ext (bindings r) lr;488let ghost ll = llift lr in489ext (bindings mq) ll;490let lemma ev (env: Atom.t -> real) : unit491requires { valid env p }492ensures { eval env p = 1.0 <-> sgn (env x) = eval env q /\ valid env q }493= let s = sgn (env x) in494sgn_unit3 (env x);495evs_unit3 env lr;496evs_unit3 env l;497assert { evs env l = s *. evs env lr };498assert { evs env (bindings mq) = evs env lr };499comm3 s (cv c) (evs env lr);500assert { eval env p = s *. eval env q };501if pure { eval env p = 1.0 } then begin502assert { forall k. has k l -> env k <> 0.0 };503assert { valid env q }504end else if pure { s = eval env q /\ valid env q } then begin505if pure { assoc x l = Some Odd } then begin506assert { forall k. assoc k ll = Some OddNonZero \/ assoc k ll = None };507assert { forall k. has k ll -> env k <> 0.0 };508evs_unit3 env ll509end;510assert { s <> 0.0 }511end in512Subst x q513end514end515end516
p1 = p2, p1 with a single possibly–zero node n, not in p2: sgn n = p2 * (p1 without n)
Valid (404ms) (colibri2 8) (cvc5 2) (split_vc) (depth 1)let one_odd (p1 p2:t) : solved520ensures { solves (fun env -> valid env p1 /\ valid env p2)521(fun env -> eval env p1 = eval env p2) result }522= match p1 with523| Zero -> Unsolved524| P c m ->525let l = SPT.to_list m in526match find_power Odd l with527| None -> Unsolved528| Some n ->529let r = SPT.remove n m in530let lr = SPT.to_list r in531let in_p2 = match p2 with532| Zero -> false533| P _ m2 -> match SPT.find_opt n m2 with None -> false | Some _ -> true end534end in535if not in_p2 && all_nz_list lr then begin536let rest = P c r in537let q = mul p2 rest in538let ghost glr = lrem n l in539ext (bindings r) glr;540let lemma ev (env: Atom.t -> real) : unit541requires { valid env p1 /\ valid env p2 }542ensures { eval env p1 = eval env p2 <-> sgn (env n) = eval env q /\ valid env q }543= let s = sgn (env n) in544sgn_unit3 (env n);545assert { valid env rest };546eval_unit3 env rest;547assert { eval env rest <> 0.0 };548eval_unit3 env p2;549assert { eval env p1 = s *. eval env rest };550assert { eval env q = eval env p2 *. eval env rest } in551Subst n q552end else Unsolved553end554end555
The atoms of l are not zero when e holds
predicate non_zero (h: (Atom.t -> real) -> bool) (e: (Atom.t -> real) -> bool)558(l:list Atom.t) =559forall env. h env -> e env -> forall k. Mem.mem k l -> env k <> 0.0560
The atoms of p
Valid (30ms) (colibri2)let atoms (p:t) : list Atom.t563ensures { forall k. Mem.mem k result <-> mem k p }564= match p with565| Zero -> Nil566| P _ m -> keys (SPT.to_list m)567end568
p1 = p2, and the nodes that it makes non zero: when one side is non zero, all the nodes of both sides (Subst cannot say it for the nodes it does not substitute)
Valid (160ms) (colibri2 9) (split_vc 2) (depth 2)let solve (p1 p2:t) : (solved, list Atom.t)573returns { (r, l) ->574solves (fun env -> valid env p1 /\ valid env p2)575(fun env -> eval env p1 = eval env p2) r /\576non_zero (fun env -> valid env p1 /\ valid env p2)577(fun env -> eval env p1 = eval env p2) l }578= if all_nz p1 || all_nz p2 then begin579let a1 = atoms p1 in580let a2 = atoms p2 in581let l = a1 ++ a2 in582let lemma nz (env: Atom.t -> real) (k:Atom.t) : unit583requires { valid env p1 /\ valid env p2 }584requires { eval env p1 = eval env p2 }585requires { Mem.mem k l }586ensures { env k <> 0.0 }587= eval_unit3 env p1; eval_unit3 env p2;588mem_append k a1 a2 in589let p = mul p2 p1 in590let lemma ev (env: Atom.t -> real) : unit591requires { valid env p1 /\ valid env p2 }592ensures { valid env p }593ensures { eval env p1 = eval env p2 <-> eval env p = 1.0 }594= eval_unit3 env p1; eval_unit3 env p2 in595let r = solve_one p in596transfer (pure { fun (env: Atom.t -> real) -> valid env p1 /\ valid env p2 })597(pure { fun (env: Atom.t -> real) -> valid env p })598(pure { fun (env: Atom.t -> real) -> eval env p1 = eval env p2 })599(pure { fun (env: Atom.t -> real) -> eval env p = 1.0 }) r;600(r, l)601end else602match one_odd p1 p2 with603| Unsolved ->604let r = one_odd p2 p1 in605transfer (pure { fun (env: Atom.t -> real) -> valid env p1 /\ valid env p2 })606(pure { fun (env: Atom.t -> real) -> valid env p2 /\ valid env p1 })607(pure { fun (env: Atom.t -> real) -> eval env p1 = eval env p2 })608(pure { fun (env: Atom.t -> real) -> eval env p2 = eval env p1 }) r;609(r, Nil)610| r -> (r, Nil)611end612end613