Common — library colibrilib.ring — module Mono

Monomials: sorted lists of atoms, evaluated as their product

32
module Mono
33
use int.Int
34
use mach.int.Int63
35
use real.RealInfix
36
use list.List
37
use list.Mem
38
use Atom
39
40
type
mono
= list Atom.t

a is not above any atom of m

43
predicate
le_all
(a:Atom.t) (m:mono) = forall b. mem b m -> not (lt b a)
44
45
predicate
sorted
(m:mono) =
46
match m with
47
| Nil -> true
48
| Cons a r -> le_all a r /\ sorted r
49
end
50
51
function
evalm
(env: Atom.t -> real) (m:mono) : real =
52
match m with
53
| Nil -> 1.0
54
| Cons a r -> env a *. evalm env r
55
end

The order on the monomials: lexicographic

58
predicate
mlt
(m1 m2:mono) =
59
match m1, m2 with
60
| Nil, Nil -> false
61
| Nil, Cons _ _ -> true
62
| Cons _ _, Nil -> false
63
| Cons a r, Cons b s -> lt a b \/ (a = b /\ mlt r s)
64
end
65
Valid (24ms) (colibri2)
66
let rec ghost
mlt_irrefl
(m:mono) : unit
67
ensures { not (mlt m m) }
68
variant { m }
69
= match m with Nil -> () | Cons _ r -> mlt_irrefl r end
70
Valid (40ms) (colibri2)
71
let rec ghost
mlt_trans
(m1 m2 m3:mono) : unit
72
requires { mlt m1 m2 }
73
requires { mlt m2 m3 }
74
ensures { mlt m1 m3 }
75
variant { m1 }
76
= match m1, m2, m3 with
77
| Cons a r, Cons b s, Cons c u ->
78
if Atom.equal a b && Atom.equal b c then mlt_trans r s u
79
| _ -> ()
80
end
81
Valid (27ms) (colibri2)
82
let rec ghost
mlt_total
(m1 m2:mono) : unit
83
ensures { mlt m1 m2 \/ m1 = m2 \/ mlt m2 m1 }
84
variant { m1 }
85
= match m1, m2 with
86
| Cons _ r, Cons _ s -> mlt_total r s
87
| _ -> ()
88
end
89
Valid (85ms) (colibri2)
90
let rec
compare
(m1 m2:mono) : int63
91
ensures { result < 0 <-> mlt m1 m2 }
92
ensures { result = 0 <-> m1 = m2 }
93
ensures { result > 0 <-> mlt m2 m1 }
94
variant { m1 }
95
= match m1, m2 with
96
| Nil, Nil -> 0
97
| Nil, Cons _ _ -> -1
98
| Cons _ _, Nil -> 1
99
| Cons a r, Cons b s ->
100
let c = Atom.compare a b in
101
if c <> 0 then c else compare r s
102
end

The product of two monomials: the merge of the sorted lists

  Valid (155ms) (colibri2 7) (split_vc) (depth 1)
105
let rec
mul
(m1 m2:mono) : mono
106
requires { sorted m1 /\ sorted m2 }
107
ensures { sorted result }
108
ensures { forall a. mem a result <-> mem a m1 \/ mem a m2 }
109
ensures { forall env. evalm env result = evalm env m1 *. evalm env m2 }
110
variant { m1, m2 }
111
= match m1, m2 with
112
| Nil, _ -> m2
113
| _, Nil -> m1
114
| Cons a r, Cons b s ->
115
if Atom.compare b a < 0 then Cons b (mul m1 s)
116
else Cons a (mul r m2)
117
end

m without one occurrence of a

  Valid (50ms) (colibri2)
119
let rec
remove_one
(a:Atom.t) (m:mono) : mono
120
requires { sorted m }
121
requires { mem a m }
122
ensures { sorted result }
123
ensures { forall b. mem b result -> mem b m }
124
ensures { forall env. evalm env m = env a *. evalm env result }
125
variant { m }
126
= match m with
127
| Nil -> absurd
128
| Cons b r ->
129
if Atom.equal a b then r
130
else begin
131
let res = remove_one a r in
132
let lemma ev (env: Atom.t -> real) : unit
133
ensures { evalm env m = env a *. evalm env (Cons b res) }
134
= assert { evalm env r = env a *. evalm env res } in
135
Cons b res
136
end
137
end
138
end