library colibrilib.ring — module MonoMonomials: sorted lists of atoms, evaluated as their product
module Mono32use int.Int33use mach.int.Int6334use real.RealInfix35use list.List36use list.Mem37use Atom3839type mono = list Atom.t40
a is not above any atom of m
predicate le_all (a:Atom.t) (m:mono) = forall b. mem b m -> not (lt b a)4344predicate sorted (m:mono) =45match m with46| Nil -> true47| Cons a r -> le_all a r /\ sorted r48end4950function evalm (env: Atom.t -> real) (m:mono) : real =51match m with52| Nil -> 1.053| Cons a r -> env a *. evalm env r54end55
The order on the monomials: lexicographic
predicate mlt (m1 m2:mono) =58match m1, m2 with59| Nil, Nil -> false60| Nil, Cons _ _ -> true61| Cons _ _, Nil -> false62| Cons a r, Cons b s -> lt a b \/ (a = b /\ mlt r s)63end64Valid (24ms) (colibri2)65let rec ghost mlt_irrefl (m:mono) : unit66ensures { not (mlt m m) }67variant { m }68= match m with Nil -> () | Cons _ r -> mlt_irrefl r end69Valid (40ms) (colibri2)70let rec ghost mlt_trans (m1 m2 m3:mono) : unit71requires { mlt m1 m2 }72requires { mlt m2 m3 }73ensures { mlt m1 m3 }74variant { m1 }75= match m1, m2, m3 with76| Cons a r, Cons b s, Cons c u ->77if Atom.equal a b && Atom.equal b c then mlt_trans r s u78| _ -> ()79end80Valid (27ms) (colibri2)81let rec ghost mlt_total (m1 m2:mono) : unit82ensures { mlt m1 m2 \/ m1 = m2 \/ mlt m2 m1 }83variant { m1 }84= match m1, m2 with85| Cons _ r, Cons _ s -> mlt_total r s86| _ -> ()87end88Valid (85ms) (colibri2)89let rec compare (m1 m2:mono) : int6390ensures { result < 0 <-> mlt m1 m2 }91ensures { result = 0 <-> m1 = m2 }92ensures { result > 0 <-> mlt m2 m1 }93variant { m1 }94= match m1, m2 with95| Nil, Nil -> 096| Nil, Cons _ _ -> -197| Cons _ _, Nil -> 198| Cons a r, Cons b s ->99let c = Atom.compare a b in100if c <> 0 then c else compare r s101end102
The product of two monomials: the merge of the sorted lists
Valid (155ms) (colibri2 7) (split_vc) (depth 1)let rec mul (m1 m2:mono) : mono105requires { sorted m1 /\ sorted m2 }106ensures { sorted result }107ensures { forall a. mem a result <-> mem a m1 \/ mem a m2 }108ensures { forall env. evalm env result = evalm env m1 *. evalm env m2 }109variant { m1, m2 }110= match m1, m2 with111| Nil, _ -> m2112| _, Nil -> m1113| Cons a r, Cons b s ->114if Atom.compare b a < 0 then Cons b (mul m1 s)115else Cons a (mul r m2)116end117
m without one occurrence of a
Valid (50ms) (colibri2)let rec remove_one (a:Atom.t) (m:mono) : mono119requires { sorted m }120requires { mem a m }121ensures { sorted result }122ensures { forall b. mem b result -> mem b m }123ensures { forall env. evalm env m = env a *. evalm env result }124variant { m }125= match m with126| Nil -> absurd127| Cons b r ->128if Atom.equal a b then r129else begin130let res = remove_one a r in131let lemma ev (env: Atom.t -> real) : unit132ensures { evalm env m = env a *. evalm env (Cons b res) }133= assert { evalm env r = env a *. evalm env res } in134Cons b res135end136end137end138