library colibrilib.fp_conv — module TermsThe lookups of the rules: proved filters of Env.kparents and Env.kapps
module Terms761use int.Int762use list.List763use list.Mem as LM764use option.Option765use colibrilib.ring.Atom766use colibrilib.fbin.Fp767use colibrilib.fp_facts.Facts768use Env769
A node b of a term fp.neg b in the class of a, if any
Valid (579ms) (cvc5)let rec negs_l (d: envp 'm) (a: Atom.t) (l: list (Atom.t, Atom.t, Atom.t, Atom.t)) : option Atom.t772requires { forall t. LM.mem t l -> kterm d 3 t }773ensures { match result with774| Some b -> fmt_of b = fmt_of a /\ (live d -> d.mf a = neg (d.mf b))775| None -> true776end }777variant { l }778= match l with779| Nil -> None780| Cons (r, m, x, y) t ->781{proof…} assert { LM.mem (r, m, x, y) l }; {qed}782if is_equal d r a then Some x else negs_l d a t783end784Valid (184ms) (colibri2)785let negs (d: envp 'm) (a: Atom.t) : option Atom.t786ensures { match result with787| Some b -> fmt_of b = fmt_of a /\ (live d -> d.mf a = neg (d.mf b))788| None -> true789end }790= negs_l d a (kapps d 3 a)791
The nodes r of the terms fp.add m a (fp.neg b) of the e–graph
Valid (847ms) (cvc5)let rec subs_l (d: envp 'm) (a b: Atom.t) (l: list (Atom.t, Atom.t, Atom.t, Atom.t)) : list Atom.t794requires { forall t. LM.mem t l -> kterm d 0 t }795ensures { forall r. LM.mem r result -> live d ->796exists md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) }797variant { l }798= match l with799| Nil -> Nil800| Cons (r, m, x, y) t ->801{proof…} assert { LM.mem (r, m, x, y) l }; {qed}802let rest = subs_l d a b t in803if is_equal d x a then804match negs d y with805| Some c -> if is_equal d c b then Cons r rest else rest806| None -> rest807end808else rest809end810Valid (158ms) (colibri2)811let subs (d: envp 'm) (fm: format) (a b: Atom.t) : list Atom.t812ensures { forall r. LM.mem r result -> live d ->813exists md. d.mf r = fp_add md (d.mf a) (neg (d.mf b)) }814= subs_l d a b (kparents d 0 a)815
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)let rec sibs_l (d: envp 'm) (k: int) (fm: format) (m a r: Atom.t)821(l: list (Atom.t, Atom.t, Atom.t, Atom.t)) : list (Atom.t, Atom.t)822requires { 0 <= k <= 2 /\ fmt_of a = fm }823requires { forall t. LM.mem t l -> kterm d k t }824ensures { forall r' x. LM.mem (r', x) result -> fmt_of x = fm /\ fmt_of r' = fm /\825(live d -> fmt (d.mf x) = fm /\ d.mf r' = mop k (d.mm m) (d.mf a) (d.mf x)) }826variant { l }827= match l with828| Nil -> Nil829| Cons (n, m', x1, x2) t ->830{proof…} assert { LM.mem (n, m', x1, x2) l }; {qed}831let rest = sibs_l d k fm m a r t in832if is_equal d n r || not (is_equal d m' m) then rest833else begin834let first = k <> 2 && is_equal d x1 a in835let acc = if first then Cons (n, x2) rest else rest in836if not first && is_equal d x2 a then begin837{proof…}838if pure { live d } then begin839if pure { k = 0 } then add_comm (d.mm m) (d.mf x1) (d.mf x2);840if pure { k = 1 } then mul_comm (d.mm m) (d.mf x1) (d.mf x2)841end;842{qed}843Cons (n, x1) acc844end else acc845end846end847Valid (194ms) (colibri2)848let sibs (d: envp 'm) (k: int) (fm: format) (m a r: Atom.t) : list (Atom.t, Atom.t)849requires { 0 <= k <= 2 /\ fmt_of a = fm }850ensures { forall r' x. LM.mem (r', x) result -> fmt_of x = fm /\ fmt_of r' = fm /\851(live d -> fmt (d.mf x) = fm /\ d.mf r' = mop k (d.mm m) (d.mf a) (d.mf x)) }852= sibs_l d k fm m a r (kparents d k a)853
The pairs (h, c) of the terms h = fp.div m r c of the e–graph
Valid (601ms) (cvc5)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)856requires { forall t. LM.mem t l -> kterm d 2 t }857ensures { forall h c. LM.mem (h, c) result -> fmt_of c = fmt_of r /\ fmt_of h = fmt_of r /\858(live d -> exists md. d.mf h = fp_div md (d.mf r) (d.mf c)) }859variant { l }860= match l with861| Nil -> Nil862| Cons (h, m, x, c) t ->863{proof…} assert { LM.mem (h, m, x, c) l }; {qed}864let rest = divs_l d r t in865if is_equal d x r then Cons (h, c) rest else rest866end867Valid (149ms) (colibri2)868let divs (d: envp 'm) (fm: format) (r: Atom.t) : list (Atom.t, Atom.t)869ensures { forall h c. LM.mem (h, c) result -> fmt_of c = fmt_of r /\ fmt_of h = fmt_of r /\870(live d -> exists md. d.mf h = fp_div md (d.mf r) (d.mf c)) }871= divs_l d r (kparents d 2 r)872873end874