Common — library colibrilib.product — module Prod

The products c * |x1|^q1 * ... * |xn|^qn of colibri2 (colibri2/theories/LRA/product.ml): the value of the absolute value of a node. c is non negative, the exponents are rationals. A negative exponent means that its node is not zero: the specifications assume it (valid).

566
module Prod
567
use int.Int
568
use mach.int.Int63
569
use real.RealInfix
570
use real.Abs
571
use list.List
572
use list.Length
573
use option.Option
574
use colibrilib.ring.Atom
575
use colibrilib.stdq.StdQ as Q
576
use colibrilib.stda.StdA as A
577
use Apow
578
use QAssoc
579
use PT
580
use APow
581
use colibrilib.spec.Sound
582
use colibrilib.spec.Eval
583
use colibrilib.spec.EvalOn
584
use colibrilib.spec.Test
585
use colibrilib.spec.Opt

The coefficient a, unless it is zero

  Valid (39ms) (colibri2)
588
let function
nz
(a:Q.t) : option Q.t
589
ensures { result = nzv a }
590
= if Q.is_zero a then None else Some a
591
592
exception
DivZero

A non negative constant, zero only without nodes; no zero exponent

  Valid (139ms) (colibri2)
595
type
t
= {
cst
: A.t;
poly
: PT.t }
596
invariant { 0.0 <=. A.real cst /\ (A.real cst = 0.0 -> bindings poly = Nil)
597
/\ nonzero (bindings poly) }
598
by { cst = A.of_int 0; poly = PT.empty () }
599
600
function
eval
(env: Atom.t -> real) (p:t) : real =
601
A.real p.cst *. evp env (bindings p.poly)
602
603
function
exp
(k:Atom.t) (p:t) : real = ex k (bindings p.poly)
604
605
predicate
mem
(k:Atom.t) (p:t) = has k (bindings p.poly)

The nodes with a negative exponent are not zero

608
predicate
valid
(env: Atom.t -> real) (p:t) =
609
forall k. exp k p <. 0.0 -> env k <> 0.0

eval with the arguments in the order of the shapes of spec.Eval

612
function
value
(p:t) (env: Atom.t -> real) : real = eval env p

The environments where p is defined

615
predicate
ok1
(p:t) (env: Atom.t -> real) = valid env p

The environments where p1 and p2 are defined

618
predicate
ok2
(p1 p2:t) (env: Atom.t -> real) = valid env p1 /\ valid env p2

The environments where p1 / p2 is defined

621
predicate
ok_div
(p1 p2:t) (env: Atom.t -> real) =
622
valid env p1 /\ eval env p2 <> 0.0

The environments where p^c is defined

625
predicate
ok_pow
(c:Q.t) (p:t) (env: Atom.t -> real) =
626
valid env p /\ (Q.real c <. 0.0 -> eval env p <> 0.0)

The environments where p1 * p2^c is defined

629
predicate
ok_mul_pow
(p1 p2:t) (c:Q.t) (env: Atom.t -> real) =
630
valid env p1 /\ valid env p2 /\ (Q.real c <. 0.0 -> eval env p2 <> 0.0)

The environments where |x| = s, and p and s are defined

633
predicate
ok_subst
(p:t) (x:Atom.t) (s:t) (env: Atom.t -> real) =
634
valid env p /\ valid env s /\ abs (env x) = eval env s

p is defined in every environment

637
predicate
total
(p:t) = includes valid (fun _ -> true) p

p is |x|, and defined in every environment

640
predicate
is_abs_node
(p:t) (x:Atom.t) =
641
denotes0 value (fun env -> abs (env x)) p /\ total p
642
Valid (26ms) (colibri2)
643
let ghost
eval_nonneg
(env: Atom.t -> real) (p:t) : unit
644
ensures { 0.0 <=. eval env p }
645
= evp_nonneg env (bindings p.poly)

A product is zero exactly when its constant or one of its nodes is

  Valid (47ms) (colibri2)
648
let ghost
eval_zero
(env: Atom.t -> real) (p:t) : unit
649
ensures { eval env p = 0.0 <->
650
(A.real p.cst = 0.0 \/ exists k. mem k p /\ env k = 0.0) }
651
= evp_zero env (bindings p.poly)

The bindings of a map built by PT.merge

  Valid (2.9s) (colibri2 12) (split_vc 2) (depth 2)
654
let ghost
merged
(m:PT.t) (l1 l2:list binding) (c1 c2:Q.t) : unit
655
requires { sorted l1 /\ sorted l2 }
656
requires { forall k. oeq (get k m) (comb c1 c2 (assoc k l1) (assoc k l2)) }
657
ensures { nonzero (bindings m) }
658
ensures { forall k. has k (bindings m) -> has k l1 \/ has k l2 }
659
ensures { forall k. ex k (bindings m)
660
= Q.real c1 *. ex k l1 +. Q.real c2 *. ex k l2 }
661
ensures { forall env. compat env (Q.real c1) (Q.real c2) l1 l2 ->
662
evp env (bindings m)
663
= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }
664
= let l = lcomb c1 c2 l1 l2 in
665
ext_evp (bindings m) l;
666
let lemma pw (k:Atom.t) : unit
667
ensures { ex k l = Q.real c1 *. ex k l1 +. Q.real c2 *. ex k l2 }
668
= assert { assoc k l = comb c1 c2 (assoc k l1) (assoc k l2) };
669
match assoc k l1, assoc k l2 with
670
| None, None -> ()
671
| Some _, None -> ()
672
| None, Some _ -> ()
673
| Some _, Some _ -> ()
674
end in
675
()
676
Valid (36ms) (colibri2)
677
let ghost
apow_inv
(x:real) : unit
678
requires { 0.0 <. x }
679
ensures { apow x (-. 1.0) = 1.0 /. x }
680
= apow_neg x 1.0; apow_one x
681
Valid (60ms) (colibri2)
682
let
zero
() : t
683
ensures { denotes0 value (fun _ -> 0.0) result /\ total result }
684
ensures { forall k. not mem k result }
685
= { cst = A.of_int 0; poly = PT.empty () }
686
Valid (306ms) (colibri2)
687
let
one
() : t
688
ensures { denotes0 value (fun _ -> 1.0) result /\ total result }
689
ensures { forall k. not mem k result }
690
ensures { A.real result.cst = 1.0 }
691
= { cst = A.of_int 1; poly = PT.empty () }

|c|

  Valid (379ms) (colibri2)
694
let
const
(c:A.t) : t
695
ensures { denotes0 value (fun _ -> abs (A.real c)) result /\ total result }
696
ensures { forall k. not mem k result }
697
= if A.equal c (A.of_int 0) then zero () else { cst = A.abs c; poly = PT.empty () }

|x|^c

  Valid (329ms) (colibri2 5) (split_vc) (depth 1)
700
let
monome
(x:Atom.t) (c:Q.t) : t
701
ensures { denotes0 value (fun env -> apow (env x) (Q.real c)) result }
702
ensures { exact valid (fun env -> Q.real c <. 0.0 -> env x <> 0.0) result }
703
ensures { forall k. mem k result -> k = x }
704
= if Q.equal c (Q.of_int 0) then begin
705
let r = one () in
706
let lemma ev (env: Atom.t -> real) : unit
707
ensures { eval env r = apow (env x) (Q.real c) }
708
= apow_zero (env x) in
709
r
710
end else { cst = A.of_int 1; poly = PT.singleton x c }
711
Valid (33ms) (colibri2)
712
let
is_zero
(p:t) : bool
713
ensures { decides (A.real p.cst = 0.0) result }
714
ensures { result -> forall env. eval env p = 0.0 }
715
= A.equal p.cst (A.of_int 0)

The closures of PT.merge

  Valid (34ms) (colibri2)
718
let function
addf
(_k:Atom.t) (o1 o2:option Q.t) : option Q.t =
719
match o1, o2 with
720
| None, o | o, None -> o
721
| Some a, Some b -> nz (Q.add a b)
722
end

m1 is -1

  Valid (45ms) (colibri2)
725
let function
subf
(m1:Q.t) (_k:Atom.t) (o1 o2:option Q.t) : option Q.t =
726
match o1, o2 with
727
| o, None -> o
728
| None, Some b -> nz (Q.mul m1 b)
729
| Some a, Some b -> nz (Q.sub a b)
730
end

The exponent nonzero, if any

733
predicate
onz
(o:option Q.t) =
734
match o with Some a -> Q.real a <> 0.0 | None -> true end

addf is comb 1 1

  Valid (867ms) (colibri2)
737
let ghost
addf_comb
(c1 c2:Q.t) (k:Atom.t) (o1 o2:option Q.t) : unit
738
requires { Q.real c1 = 1.0 /\ Q.real c2 = 1.0 /\ onz o1 /\ onz o2 }
739
ensures { oeq (addf k o1 o2) (comb c1 c2 o1 o2) }
740
= match o1, o2 with
741
| Some a, None -> assert { Q.real (Q.mul c1 a) = Q.real a }
742
| None, Some b -> assert { Q.real (Q.mul c2 b) = Q.real b }
743
| Some a, Some b -> assert { Q.real (Q.add (Q.mul c1 a) (Q.mul c2 b)) = Q.real (Q.add a b) }
744
| None, None -> ()
745
end

subf (-1) is comb 1 (-1)

  Valid (741ms) (colibri2)
748
let ghost
subf_comb
(m1 c1 c2:Q.t) (k:Atom.t) (o1 o2:option Q.t) : unit
749
requires { Q.real m1 = -1.0 /\ Q.real c1 = 1.0 /\ Q.real c2 = -1.0 }
750
requires { onz o1 /\ onz o2 }
751
ensures { oeq (subf m1 k o1 o2) (comb c1 c2 o1 o2) }
752
= match o1, o2 with
753
| Some a, None -> assert { Q.real (Q.mul c1 a) = Q.real a }
754
| None, Some b -> assert { Q.real (Q.mul c2 b) = Q.real (Q.mul m1 b) }
755
| Some a, Some b -> assert { Q.real (Q.add (Q.mul c1 a) (Q.mul c2 b)) = Q.real (Q.sub a b) }
756
| None, None -> ()
757
end
758
Valid (37ms) (colibri2)
759
let function
combf
(c1 c2:Q.t) (_k:Atom.t) (o1 o2:option Q.t) : option Q.t =
760
match o1, o2 with
761
| None, None -> None
762
| Some a, None -> nz (Q.mul c1 a)
763
| None, Some b -> nz (Q.mul c2 b)
764
| Some a, Some b -> nz (Q.add (Q.mul c1 a) (Q.mul c2 b))
765
end
766
Valid (600ms) (colibri2 13) (split_vc 2) (depth 2)
767
let
mul
(p1 p2:t) : t
768
ensures { denotes2_on (ok2 p1 p2) value (*.) p1 p2 result }
769
ensures { includes valid (ok2 p1 p2) result }
770
ensures { forall k. mem k result -> mem k p1 \/ mem k p2 }
771
= if is_zero p1 || is_zero p2 then zero ()
772
else begin
773
let m = PT.merge addf p1.poly p2.poly in
774
let one = Q.of_int 1 in
775
let lemma pt (k:Atom.t) : unit
776
ensures { oeq (get k m) (comb one one (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly))) }
777
= addf_comb one one k (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly)) in
778
merged m (bindings p1.poly) (bindings p2.poly) one one;
779
let r = { cst = A.mul p1.cst p2.cst; poly = m } in
780
let lemma ev (env: Atom.t -> real) : unit
781
requires { valid env p1 /\ valid env p2 }
782
ensures { eval env r = eval env p1 *. eval env p2 /\ valid env r }
783
= let e1 = evp env (bindings p1.poly) in
784
let e2 = evp env (bindings p2.poly) in
785
evp_nonneg env (bindings p1.poly); evp_nonneg env (bindings p2.poly);
786
apow_one e1; apow_one e2;
787
assert { compat env 1.0 1.0 (bindings p1.poly) (bindings p2.poly) };
788
assert { eval env r = A.real p1.cst *. A.real p2.cst *. (e1 *. e2) } in
789
r
790
end

p1 / p2; p2 is not zero

  Valid (485ms) (colibri2 18) (split_vc) (depth 1)
793
let
div
(p1 p2:t) : t
794
ensures { denotes2_on (ok_div p1 p2) value (/.) p1 p2 result }
795
ensures { includes valid (ok_div p1 p2) result }
796
ensures { forall k. mem k result -> mem k p1 \/ mem k p2 }
797
ensures { A.real p1.cst <> 0.0 -> forall k. exp k result = exp k p1 -. exp k p2 }
798
ensures { A.real p1.cst <> 0.0 -> A.real result.cst <> 0.0 }
799
raises { DivZero -> A.real p2.cst = 0.0 }
800
= if is_zero p2 then raise DivZero;
801
if is_zero p1 then zero ()
802
else begin
803
let m1 = Q.of_int (-1) in
804
let m = PT.merge (subf m1) p1.poly p2.poly in
805
let one = Q.of_int 1 in
806
let lemma pt (k:Atom.t) : unit
807
ensures { oeq (get k m) (comb one m1 (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly))) }
808
= subf_comb m1 one m1 k (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly)) in
809
merged m (bindings p1.poly) (bindings p2.poly) one m1;
810
let r = { cst = A.div p1.cst p2.cst; poly = m } in
811
let lemma ev (env: Atom.t -> real) : unit
812
requires { valid env p1 /\ eval env p2 <> 0.0 }
813
ensures { eval env r = eval env p1 /. eval env p2 /\ valid env r }
814
= let e1 = evp env (bindings p1.poly) in
815
let e2 = evp env (bindings p2.poly) in
816
eval_zero env p2;
817
evp_nonneg env (bindings p1.poly); evp_nonneg env (bindings p2.poly);
818
apow_one e1; apow_inv e2;
819
assert { compat env 1.0 (-1.0) (bindings p1.poly) (bindings p2.poly) };
820
assert { eval env r = (A.real p1.cst /. A.real p2.cst) *. (e1 *. (1.0 /. e2)) } in
821
r
822
end

The closure of power_cst

  Valid (33ms) (colibri2)
825
let function
mulf
(c e:Q.t) : Q.t = Q.mul e c

p^c

  Valid (895ms) (colibri2 25) (cvc4) (split_vc) (depth 1)
828
let
power_cst
(c:Q.t) (p:t) : t
829
ensures { denotes1_on (ok_pow c p) value (fun v -> apow v (Q.real c)) p result }
830
ensures { includes valid (ok_pow c p) result }
831
ensures { forall k. mem k result -> mem k p }
832
ensures { A.real p.cst <> 0.0 -> forall k. exp k result = Q.real c *. exp k p }
833
ensures { A.real p.cst <> 0.0 -> A.real result.cst <> 0.0 }
834
raises { DivZero -> Q.real c <. 0.0 /\ A.real p.cst = 0.0 }
835
= if Q.equal c (Q.of_int 0) then begin
836
let r = one () in
837
let lemma ev (env: Atom.t -> real) : unit
838
ensures { eval env r = apow (eval env p) (Q.real c) }
839
= apow_zero (eval env p) in
840
assert { forall k. exp k r = 0.0 };
841
r
842
end else if is_zero p then begin
843
if Q.lt c (Q.of_int 0) then raise DivZero;
844
zero ()
845
end else begin
846
let ghost z = Q.of_int 0 in
847
let m = PT.map (mulf c) p.poly in
848
merged m (bindings p.poly) Nil c z;
849
assert { forall k. ex k Nil = 0.0 };
850
let r = { cst = positive_pow p.cst c; poly = m } in
851
apow_nonneg (A.real p.cst) (Q.real c);
852
let lemma ev (env: Atom.t -> real) : unit
853
requires { valid env p /\ (Q.real c <. 0.0 -> eval env p <> 0.0) }
854
ensures { eval env r = apow (eval env p) (Q.real c) /\ valid env r }
855
= let e = evp env (bindings p.poly) in
856
eval_zero env p;
857
apow_zero 1.0;
858
assert { compat env (Q.real c) 0.0 (bindings p.poly) Nil };
859
apow_prod (A.real p.cst) e (Q.real c);
860
assert { evp env (bindings m) = apow e (Q.real c) } in
861
r
862
end

p1 * p2^c

  Valid (1.4s) (colibri2 22) (split_vc) (depth 1)
865
let
x_m_yc
(p1 p2:t) (c:Q.t) : t
866
ensures { denotes2_on (ok_mul_pow p1 p2 c) value (fun x y -> x *. apow y (Q.real c)) p1 p2 result }
867
ensures { includes valid (ok_mul_pow p1 p2 c) result }
868
ensures { forall k. mem k result -> mem k p1 \/ mem k p2 }
869
raises { DivZero -> Q.real c <. 0.0 /\ A.real p2.cst = 0.0 }
870
= if Q.equal c (Q.of_int 0) then begin
871
let lemma ev (env: Atom.t -> real) : unit
872
ensures { eval env p1 = eval env p1 *. apow (eval env p2) (Q.real c) }
873
= apow_zero (eval env p2) in
874
p1
875
end else if is_zero p2 then begin
876
if Q.lt c (Q.of_int 0) then raise DivZero;
877
zero ()
878
end else if is_zero p1 then zero ()
879
else if Q.equal c (Q.of_int 1) then begin
880
let lemma ev (env: Atom.t -> real) : unit
881
ensures { apow (eval env p2) (Q.real c) = eval env p2 }
882
= eval_nonneg env p2; apow_one (eval env p2) in
883
mul p1 p2
884
end else begin
885
let o = Q.of_int 1 in
886
let m = PT.merge (combf o c) p1.poly p2.poly in
887
let lemma pt (k:Atom.t) : unit
888
ensures { oeq (get k m) (comb o c (assoc k (bindings p1.poly)) (assoc k (bindings p2.poly))) }
889
= assert { get k m = combf o c k (get k p1.poly) (get k p2.poly) } in
890
merged m (bindings p1.poly) (bindings p2.poly) o c;
891
let r = { cst = A.mul p1.cst (positive_pow p2.cst c); poly = m } in
892
let lemma ev (env: Atom.t -> real) : unit
893
requires { valid env p1 /\ valid env p2 }
894
requires { Q.real c <. 0.0 -> eval env p2 <> 0.0 }
895
ensures { eval env r = eval env p1 *. apow (eval env p2) (Q.real c)
896
/\ valid env r }
897
= let e1 = evp env (bindings p1.poly) in
898
let e2 = evp env (bindings p2.poly) in
899
eval_zero env p2;
900
evp_nonneg env (bindings p1.poly);
901
apow_one e1;
902
assert { compat env 1.0 (Q.real c) (bindings p1.poly) (bindings p2.poly) };
903
apow_prod (A.real p2.cst) e2 (Q.real c);
904
assert { eval env r = A.real p1.cst *. apow (A.real p2.cst) (Q.real c)
905
*. (e1 *. apow e2 (Q.real c)) } in
906
r
907
end

p without the node n: p = |n|^(exp n p) * remove n p

  Valid (392ms) (colibri2 10) (split_vc) (depth 1)
910
let
remove
(n:Atom.t) (p:t) : t
911
ensures { denotes0 value (fun env -> apow (env n) (exp n p) *. eval env result) p }
912
ensures { includes valid (ok1 p) result }
913
ensures { exact mem (fun k -> mem k p /\ k <> n) result }
914
ensures { forall k. k <> n -> exp k result = exp k p }
915
ensures { result.cst = p.cst }
916
= let m = PT.remove n p.poly in
917
let l = lremove n (bindings p.poly) in
918
ext_evp (bindings m) l;
919
if pure { bindings p.poly = Nil } then nil_of_none (bindings m);
920
{ cst = p.cst; poly = m }

The substitution of |x| by s; None when x is not in p

  Valid (1.8s) (colibri2 4) (cvc4) (split_vc) (depth 1)
923
let
subst
(p:t) (x:Atom.t) (s:t) : option t
924
ensures { match result with
925
| None -> not mem x p
926
| Some r -> mem x p
927
/\ (forall k. mem k r -> (mem k p /\ k <> x) \/ mem k s)
928
/\ denotes1_on (ok_subst p x s) value (fun v -> v) p r
929
/\ includes valid (ok_subst p x s) r
930
end }
931
raises { DivZero -> exp x p <. 0.0 /\ A.real s.cst = 0.0 }
932
= match PT.find_opt x p.poly with
933
| None -> None
934
| Some q ->
935
let p' = remove x p in
936
let r = x_m_yc p' s q in
937
let lemma ev (env: Atom.t -> real) : unit
938
requires { valid env p /\ valid env s /\ abs (env x) = eval env s }
939
ensures { eval env r = eval env p /\ valid env r }
940
= apow_abs (env x) (Q.real q);
941
assert { Q.real q <. 0.0 -> env x <> 0.0 } in
942
Some r
943
end
944
945
type
extracted
=
946
|
One
947
|
Cst
A.t
948
|
Var
Q.t Atom.t t

A node of p and the rest

  Valid (71ms) (colibri2)
951
let
extract
(p:t) : extracted
952
ensures { match result with
953
| One -> bindings p.poly = Nil /\ A.real p.cst = 1.0
954
| Cst c -> bindings p.poly = Nil /\ c = p.cst /\ A.real c <> 1.0
955
| Var q x r -> exp x p = Q.real q /\ Q.real q <> 0.0 /\ r.cst = p.cst
956
/\ exact mem (fun k -> mem k p /\ k <> x) r
957
/\ denotes0 value (fun env -> apow (env x) (Q.real q) *. eval env r) p
958
/\ includes valid (ok1 p) r
959
end }
960
= if PT.is_empty p.poly then
961
if A.equal p.cst (A.of_int 1) then One else Cst p.cst
962
else begin
963
let x, q = PT.choose p.poly in
964
Var q x (remove x p)
965
end

|x|

  Valid (349ms) (colibri2 8) (split_vc) (depth 1)
968
let partial
is_one_node
(p:t) : option Atom.t
969
ensures { when_some (is_abs_node p) result }
970
= if A.equal p.cst (A.of_int 1) && PT.cardinal p.poly = 1 then begin
971
let x, q = PT.choose p.poly in
972
if Q.equal q (Q.of_int 1) then begin
973
assert { match bindings p.poly with
974
| Cons (y, v) Nil -> y = x /\ v = q | _ -> false end };
975
let lemma ev (env: Atom.t -> real) : unit
976
ensures { eval env p = abs (env x) }
977
= apow_one (env x) in
978
Some x
979
end else None
980
end else None
981
982
type
kind
=
983
|
CST
A.t
984
|
NODE
A.t Atom.t
985
|
PRODUCT
986
Valid (406ms) (colibri2)
987
let partial
classify
(p:t) : kind
988
ensures { match result with
989
| CST c -> bindings p.poly = Nil /\ c = p.cst
990
| NODE c x -> c = p.cst /\ denotes0 value (fun env -> A.real c *. abs (env x)) p
991
/\ total p
992
| PRODUCT -> true
993
end }
994
= if PT.is_empty p.poly then CST p.cst
995
else if PT.cardinal p.poly = 1 then begin
996
let x, q = PT.choose p.poly in
997
if Q.equal q (Q.of_int 1) then begin
998
assert { match bindings p.poly with
999
| Cons (y, v) Nil -> y = x /\ v = q | _ -> false end };
1000
let lemma ev (env: Atom.t -> real) : unit
1001
ensures { eval env p = A.real p.cst *. abs (env x) }
1002
= apow_one (env x) in
1003
NODE p.cst x
1004
end else PRODUCT
1005
end else PRODUCT

The closure of common

  Valid (34ms) (colibri2)
1008
let function
commonf
(_k:Atom.t) (o1 o2:option Q.t) : option Q.t =
1009
match o1, o2 with
1010
| Some a, Some b -> (match nz (Q.sub a b) with None -> Some a | Some _ -> None end)
1011
| _ -> None
1012
end

The nodes with the same exponent in p1 and p2, with this exponent

  Valid (375ms) (colibri2 8) (cvc5) (split_vc) (depth 1)
1015
let
common
(p1 p2:t) : t
1016
ensures { A.real result.cst = 1.0 }
1017
ensures { forall k. mem k result -> mem k p1 /\ mem k p2
1018
/\ exp k result = exp k p1 /\ exp k result = exp k p2 }
1019
= let m = PT.merge commonf p1.poly p2.poly in
1020
let lemma nz (k:Atom.t) (v:Q.t) : unit
1021
requires { get k m = Some v }
1022
ensures { Q.real v <> 0.0 }
1023
= assert { get k p1.poly = Some v } in
1024
let lemma memk (k:Atom.t) : unit
1025
requires { has k (bindings m) }
1026
ensures { has k (bindings p1.poly) /\ has k (bindings p2.poly) }
1027
ensures { ex k (bindings m) = ex k (bindings p1.poly) = ex k (bindings p2.poly) }
1028
= assert { get k m = commonf k (get k p1.poly) (get k p2.poly) } in
1029
{ cst = A.of_int 1; poly = m }

The nodes of p that satisfy f

  Valid (42ms) (colibri2 6) (split_vc) (depth 1)
1032
let
filter
(f: Atom.t -> bool) (p:t) : t
1033
ensures { result.cst = p.cst }
1034
ensures { forall k. get k result.poly = if f k then get k p.poly else None }
1035
= let m = PT.filter f p.poly in
1036
let lemma nz (k:Atom.t) (v:Q.t) : unit
1037
requires { get k m = Some v }
1038
ensures { Q.real v <> 0.0 }
1039
= assert { get k p.poly = Some v } in
1040
if pure { bindings p.poly = Nil } then nil_of_none (bindings m);
1041
{ cst = p.cst; poly = m }

The nodes with a negative exponent in l are not zero

1044
predicate
lvalid
(env: Atom.t -> real) (l:list binding) =
1045
match l with
1046
| Nil -> true
1047
| Cons (k, q) r -> (Q.real q <. 0.0 -> env k <> 0.0) /\ lvalid env r
1048
end

lvalid as a set of environments

1051
predicate
lvalid_at
(l:list binding) (env: Atom.t -> real) = lvalid env l

The environments where |k| = f k for the atoms of p, all defined

1054
predicate
ok_normalize
(p:t) (f: Atom.t -> t) (env: Atom.t -> real) =
1055
valid env p /\
1056
forall k. mem k p -> abs (env k) = eval env (f k) /\ valid env (f k)

|c| * |x1|^q1 * ... * |xn|^qn, the xi are not necessarily distinct

  Valid (743ms) (colibri2 10) (split_vc 2) (depth 2)
1060
let rec
of_list
(c:A.t) (l:list binding) : t
1061
ensures { denotes0_on (lvalid_at l) value (fun env -> abs (A.real c) *. evp env l) result }
1062
ensures { includes valid (lvalid_at l) result }
1063
variant { l }
1064
= match l with
1065
| Nil -> const c
1066
| Cons (k, q) r ->
1067
let p = of_list c r in
1068
let mk = monome k q in
1069
let res = mul mk p in
1070
let lemma ev (env: Atom.t -> real) : unit
1071
requires { lvalid env l }
1072
ensures { eval env res = abs (A.real c) *. evp env l /\ valid env res }
1073
= assert { valid env mk };
1074
assert { lvalid env r };
1075
assert { eval env p = abs (A.real c) *. evp env r /\ valid env p };
1076
assert { eval env res = apow (env k) (Q.real q) *. eval env p };
1077
assert { evp env l = apow (env k) (Q.real q) *. evp env r };
1078
assert { apow (env k) (Q.real q) *. (abs (A.real c) *. evp env r)
1079
= abs (A.real c) *. (apow (env k) (Q.real q) *. evp env r) } in
1080
res
1081
end

Every node k of p replaced by f k, its value: the nodes k with a negative exponent are not zero

  Valid (3.0s) (colibri2 30) (cvc4) (split_vc 5) (depth 2)
1085
let
normalize
(p:t) (f: Atom.t -> t) : t
1086
ensures { denotes1_on (ok_normalize p f) value (fun v -> v) p result }
1087
ensures { includes valid (ok_normalize p f) result }
1088
raises { DivZero -> exists k. exp k p <. 0.0 /\ A.real (f k).cst = 0.0 }
1089
= let rec aux (acc:t) (l:list binding) : t
1090
requires { sorted l /\ nonzero l }
1091
requires { forall k. has k l -> ex k l = exp k p }
1092
ensures { forall env. valid env acc -> valid env p ->
1093
(forall k. has k l -> abs (env k) = eval env (f k) /\ valid env (f k)) ->
1094
eval env result = eval env acc *. evp env l /\ valid env result }
1095
raises { DivZero -> exists k. exp k p <. 0.0 /\ A.real (f k).cst = 0.0 }
1096
variant { l }
1097
= match l with
1098
| Nil -> acc
1099
| Cons (k, q) r ->
1100
assert { has k l };
1101
assert { forall k'. has k' r -> ex k' r = ex k' l
1102
by k' <> k by lt k k' };
1103
assert { nonzero r by forall k' v. assoc k' r = Some v ->
1104
assoc k' l = Some v by k' <> k by has k' r };
1105
let acc' = x_m_yc acc (f k) q in
1106
let res = aux acc' r in
1107
let lemma ev (env: Atom.t -> real) : unit
1108
requires { valid env acc /\ valid env p }
1109
requires { forall k. has k l -> abs (env k) = eval env (f k) /\ valid env (f k) }
1110
ensures { eval env res = eval env acc *. evp env l /\ valid env res }
1111
= apow_abs (env k) (Q.real q);
1112
assert { Q.real q <. 0.0 -> env k <> 0.0 };
1113
assert { eval env acc' = eval env acc *. apow (env k) (Q.real q) };
1114
assert { evp env l = apow (env k) (Q.real q) *. evp env r };
1115
assert { valid env acc' };
1116
assert { forall k'. has k' r -> has k' l };
1117
assert { forall k'. has k' r -> abs (env k') = eval env (f k') /\ valid env (f k') };
1118
assert { eval env res = eval env acc' *. evp env r /\ valid env res } in
1119
res
1120
end
1121
in
1122
let res = aux (const p.cst) (PT.to_list p.poly) in
1123
let lemma ev (env: Atom.t -> real) : unit
1124
requires { valid env p }
1125
requires { forall k. mem k p -> abs (env k) = eval env (f k) /\ valid env (f k) }
1126
ensures { eval env res = eval env p /\ valid env res }
1127
= assert { abs (A.real p.cst) = A.real p.cst } in
1128
res
1129
end