Common — library colibrilib.fp_conv — module Terms

The terms of the e–graph

The lookups of the rules: proved filters of Env.kparents and Env.kapps

761
module Terms
762
use int.Int
763
use list.List
764
use list.Mem as LM
765
use option.Option
766
use colibrilib.ring.Atom
767
use colibrilib.fbin.Fp
768
use colibrilib.fp_facts.Facts
769
use Env

A node b of a term fp.neg b in the class of a, if any

  Valid (579ms) (cvc5)
772
let rec
negs_l
(d: envp 'm) (a: Atom.t) (l: list (Atom.t, Atom.t, Atom.t, Atom.t)) : option Atom.t
773
requires { forall t. LM.mem t l -> kterm d 3 t }
774
ensures { match result with
775
| Some b -> fmt_of b = fmt_of a /\ (live d -> d.mf a = neg (d.mf b))
776
| None -> true
777
end }
778
variant { l }
779
= match l with
780
| Nil -> None
781
| Cons (r, m, x, y) t ->
782
{proof…} assert { LM.mem (r, m, x, y) l }; {qed}
783
if is_equal d r a then Some x else negs_l d a t
784
end
785
Valid (184ms) (colibri2)
786
let
negs
(d: envp 'm) (a: Atom.t) : option Atom.t
787
ensures { match result with
788
| Some b -> fmt_of b = fmt_of a /\ (live d -> d.mf a = neg (d.mf b))
789
| None -> true
790
end }
791
= negs_l d a (kapps d 3 a)

The nodes r of the terms fp.add m a (fp.neg b) of the e–graph

  Valid (847ms) (cvc5)
794
let rec
subs_l
(d: envp 'm) (a b: Atom.t) (l: list (Atom.t, Atom.t, Atom.t, Atom.t)) : list Atom.t
795
requires { forall t. LM.mem t l -> kterm d 0 t }
796
ensures { forall r. LM.mem r result -> live d ->
797
exists md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) }
798
variant { l }
799
= match l with
800
| Nil -> Nil
801
| Cons (r, m, x, y) t ->
802
{proof…} assert { LM.mem (r, m, x, y) l }; {qed}
803
let rest = subs_l d a b t in
804
if is_equal d x a then
805
match negs d y with
806
| Some c -> if is_equal d c b then Cons r rest else rest
807
| None -> rest
808
end
809
else rest
810
end
811
Valid (158ms) (colibri2)
812
let
subs
(d: envp 'm) (fm: format) (a b: Atom.t) : list Atom.t
813
ensures { forall r. LM.mem r result -> live d ->
814
exists md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) }
815
= subs_l d a b (kparents d 0 a)

The siblings (r', x) of the term r of the operation k, r = mop k m a y: the terms r' = mop k m a x of the e–graph with the same mode and the argument a (for + and * at either position, by commutativity), among the parents of a

  Valid (991ms) (cvc5)
821
let rec
sibs_l
(d: envp 'm) (k: int) (fm: format) (m a r: Atom.t)
822
(l: list (Atom.t, Atom.t, Atom.t, Atom.t)) : list (Atom.t, Atom.t)
823
requires { 0 <= k <= 2 /\ fmt_of a = fm }
824
requires { forall t. LM.mem t l -> kterm d k t }
825
ensures { forall r' x. LM.mem (r', x) result -> fmt_of x = fm /\ fmt_of r' = fm /\
826
(live d -> fmt (d.mf x) = fm /\ d.mf r' = mop k (d.mm m) (d.mf a) (d.mf x)) }
827
variant { l }
828
= match l with
829
| Nil -> Nil
830
| Cons (n, m', x1, x2) t ->
831
{proof…} assert { LM.mem (n, m', x1, x2) l }; {qed}
832
let rest = sibs_l d k fm m a r t in
833
if is_equal d n r || not (is_equal d m' m) then rest
834
else begin
835
let first = k <> 2 && is_equal d x1 a in
836
let acc = if first then Cons (n, x2) rest else rest in
837
if not first && is_equal d x2 a then begin
838
{proof…}
839
if pure { live d } then begin
840
if pure { k = 0 } then add_comm (d.mm m) (d.mf x1) (d.mf x2);
841
if pure { k = 1 } then mul_comm (d.mm m) (d.mf x1) (d.mf x2)
842
end;
843
{qed}
844
Cons (n, x1) acc
845
end else acc
846
end
847
end
848
Valid (194ms) (colibri2)
849
let
sibs
(d: envp 'm) (k: int) (fm: format) (m a r: Atom.t) : list (Atom.t, Atom.t)
850
requires { 0 <= k <= 2 /\ fmt_of a = fm }
851
ensures { forall r' x. LM.mem (r', x) result -> fmt_of x = fm /\ fmt_of r' = fm /\
852
(live d -> fmt (d.mf x) = fm /\ d.mf r' = mop k (d.mm m) (d.mf a) (d.mf x)) }
853
= sibs_l d k fm m a r (kparents d k a)

The pairs (h, c) of the terms h = fp.div m r c of the e–graph

  Valid (601ms) (cvc5)
856
let rec
divs_l
(d: envp 'm) (r: Atom.t) (l: list (Atom.t, Atom.t, Atom.t, Atom.t)) : list (Atom.t, Atom.t)
857
requires { forall t. LM.mem t l -> kterm d 2 t }
858
ensures { forall h c. LM.mem (h, c) result -> fmt_of c = fmt_of r /\ fmt_of h = fmt_of r /\
859
(live d -> exists md. d.mf h = fp_div md (d.mf r) (d.mf c)) }
860
variant { l }
861
= match l with
862
| Nil -> Nil
863
| Cons (h, m, x, c) t ->
864
{proof…} assert { LM.mem (h, m, x, c) l }; {qed}
865
let rest = divs_l d r t in
866
if is_equal d x r then Cons (h, c) rest else rest
867
end
868
Valid (149ms) (colibri2)
869
let
divs
(d: envp 'm) (fm: format) (r: Atom.t) : list (Atom.t, Atom.t)
870
ensures { forall h c. LM.mem (h, c) result -> fmt_of c = fmt_of r /\ fmt_of h = fmt_of r /\
871
(live d -> exists md. d.mf h = fp_div md (d.mf r) (d.mf c)) }
872
= divs_l d r (kparents d 2 r)
873
874
end