Common — library colibrilib.polynome — module Assoc

Sorted association lists: the model of the maps

10
module Assoc
11
use int.Int
12
use mach.int.Int63
13
use real.RealInfix
14
use list.List
15
use list.Length
16
use option.Option
17
use colibrilib.ring.Atom
18
use colibrilib.stda.StdA as A
19
20
type
binding
= (Atom.t, A.t)
21
22
function
assoc
(k:Atom.t) (l:list binding) : option A.t =
23
match l with
24
| Nil -> None
25
| Cons (k', v) r -> if k = k' then Some v else assoc k r
26
end
27
28
predicate
has
(k:Atom.t) (l:list binding) = assoc k l <> None

every key of l is above k

31
predicate
above
(k:Atom.t) (l:list binding) = forall k'. has k' l -> lt k k'
32
33
predicate
sorted
(l:list binding) =
34
match l with
35
| Nil -> true
36
| Cons (k, _) r -> above k r /\ sorted r
37
end

the sum of the v * env k

40
function
evall
(env: Atom.t -> real) (l:list binding) : real =
41
match l with
42
| Nil -> 0.0
43
| Cons (k, v) r -> A.real v *. env k +. evall env r
44
end

Two sorted lists with the same bindings are equal

  Valid (405ms) (colibri2 9) (cvc5 2) (split_vc) (depth 1)
47
let rec ghost
ext
(l1 l2:list binding) : unit
48
requires { sorted l1 /\ sorted l2 }
49
requires { forall k. assoc k l1 = assoc k l2 }
50
ensures { l1 = l2 }
51
variant { l1 }
52
= match l1, l2 with
53
| Nil, Nil -> ()
54
| Cons (k1, _) _, Nil -> assert { has k1 l1 }
55
| Nil, Cons (k2, _) _ -> assert { has k2 l2 }
56
| Cons (k1, _) r1, Cons (k2, _) r2 ->
57
assert { has k1 l2 };
58
assert { has k2 l1 };
59
if pure { k1 <> k2 } then begin
60
absurd
61
end;
62
let lemma pw (k:Atom.t) : unit
63
ensures { assoc k r1 = assoc k r2 }
64
= if pure { k = k1 } then begin
65
()
66
end else begin
67
assert { assoc k l2 = assoc k r2 }
68
end in
69
ext r1 r2
70
end

A non zero value

73
function
nzv
(a:A.t) : option A.t = if A.real a = 0.0 then None else Some a

The bindings of c1 * l1 + c2 * l2

76
function
comb
(c1 c2:A.t) (o1 o2:option A.t) : option A.t =
77
match o1, o2 with
78
| None, None -> None
79
| Some a, None -> nzv (A.mul c1 a)
80
| None, Some b -> nzv (A.mul c2 b)
81
| Some a, Some b -> nzv (A.add (A.mul c1 a) (A.mul c2 b))
82
end
83
Valid (13ms) (cvc5)
84
let ghost
comb_both
(c1 c2 a b v x e1 e2:real) : unit
85
requires { v = c1 *. a +. c2 *. b }
86
ensures { c1 *. (a *. x +. e1) +. c2 *. (b *. x +. e2)
87
= v *. x +. (c1 *. e1 +. c2 *. e2) }
88
= ()

c1 * l1 + c2 * l2

  Valid (657ms) (colibri2 45) (cvc5 2) (split_vc) (depth 1)
91
let rec ghost
lcomb
(c1 c2:A.t) (l1 l2:list binding) : list binding
92
requires { sorted l1 /\ sorted l2 }
93
ensures { sorted result }
94
ensures { forall k. has k result -> has k l1 \/ has k l2 }
95
ensures { forall k. assoc k result = comb c1 c2 (assoc k l1) (assoc k l2) }
96
ensures { forall env. evall env result
97
= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }
98
variant { l1, l2 }
99
= match l1, l2 with
100
| Nil, Nil -> Nil
101
| Cons (k, a) r, Nil ->
102
let t = lcomb c1 c2 r Nil in
103
let v = A.mul c1 a in
104
let res = if pure { A.real v = 0.0 } then t else Cons (k, v) t in
105
let lemma pw (k':Atom.t) : unit
106
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
107
= if pure { k' = k } then assert { not (has k t) } in
108
let lemma ev (env: Atom.t -> real) : unit
109
ensures { evall env res
110
= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }
111
= assert { A.real v = A.real c1 *. A.real a };
112
assert { A.real c1 *. (A.real a *. env k +. evall env r)
113
= A.real v *. env k +. A.real c1 *. evall env r } in
114
res
115
| Nil, Cons (k, b) r ->
116
let t = lcomb c1 c2 Nil r in
117
let v = A.mul c2 b in
118
let res = if pure { A.real v = 0.0 } then t else Cons (k, v) t in
119
let lemma pw (k':Atom.t) : unit
120
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
121
= if pure { k' = k } then assert { not (has k t) } in
122
let lemma ev (env: Atom.t -> real) : unit
123
ensures { evall env res
124
= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }
125
= assert { A.real v = A.real c2 *. A.real b };
126
assert { A.real c2 *. (A.real b *. env k +. evall env r)
127
= A.real v *. env k +. A.real c2 *. evall env r } in
128
res
129
| Cons (k1, a) r1, Cons (k2, b) r2 ->
130
let c = Atom.compare k1 k2 in
131
if c < 0 then begin
132
let t = lcomb c1 c2 r1 l2 in
133
let v = A.mul c1 a in
134
let res = if pure { A.real v = 0.0 } then t else Cons (k1, v) t in
135
assert { not (has k1 l2) };
136
let lemma ab (k:Atom.t) : unit
137
requires { has k t }
138
ensures { lt k1 k }
139
= if pure { has k l2 /\ k <> k2 } then Atom.lt_trans k1 k2 k in
140
let lemma pw (k':Atom.t) : unit
141
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
142
= if pure { k' = k1 } then assert { not (has k1 t) } in
143
let lemma ev (env: Atom.t -> real) : unit
144
ensures { evall env res
145
= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }
146
= assert { A.real v = A.real c1 *. A.real a };
147
assert { A.real c1 *. (A.real a *. env k1 +. evall env r1)
148
= A.real v *. env k1 +. A.real c1 *. evall env r1 } in
149
res
150
end else if c > 0 then begin
151
let t = lcomb c1 c2 l1 r2 in
152
let v = A.mul c2 b in
153
let res = if pure { A.real v = 0.0 } then t else Cons (k2, v) t in
154
assert { not (has k2 l1) };
155
let lemma ab (k:Atom.t) : unit
156
requires { has k t }
157
ensures { lt k2 k }
158
= if pure { has k l1 /\ k <> k1 } then Atom.lt_trans k2 k1 k in
159
let lemma pw (k':Atom.t) : unit
160
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
161
= if pure { k' = k2 } then assert { not (has k2 t) } in
162
let lemma ev (env: Atom.t -> real) : unit
163
ensures { evall env res
164
= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }
165
= assert { A.real v = A.real c2 *. A.real b };
166
assert { A.real c2 *. (A.real b *. env k2 +. evall env r2)
167
= A.real v *. env k2 +. A.real c2 *. evall env r2 } in
168
res
169
end else begin
170
let t = lcomb c1 c2 r1 r2 in
171
let v = A.add (A.mul c1 a) (A.mul c2 b) in
172
let res = if pure { A.real v = 0.0 } then t else Cons (k1, v) t in
173
let lemma pw (k':Atom.t) : unit
174
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
175
= if pure { k' = k1 } then assert { not (has k1 t) } in
176
let lemma ev (env: Atom.t -> real) : unit
177
ensures { evall env res
178
= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }
179
= assert { A.real v = A.real c1 *. A.real a +. A.real c2 *. A.real b };
180
comb_both (A.real c1) (A.real c2) (A.real a) (A.real b) (A.real v)
181
(env k1) (evall env r1) (evall env r2) in
182
res
183
end
184
end

l without the key k

  Valid (269ms) (colibri2 5) (cvc5) (split_vc) (depth 1)
187
let rec ghost
lremove
(k:Atom.t) (l:list binding) : list binding
188
requires { sorted l }
189
ensures { sorted result }
190
ensures { forall k'. assoc k' result = if k' = k then None else assoc k' l }
191
ensures { forall env. evall env result = match assoc k l with
192
| None -> evall env l
193
| Some v -> evall env l -. A.real v *. env k end }
194
variant { l }
195
= match l with
196
| Nil -> Nil
197
| Cons (k', v) r ->
198
if Atom.equal k k' then begin
199
let lemma pw (k'':Atom.t) : unit
200
ensures { assoc k'' r = if k'' = k then None else assoc k'' l }
201
= () in
202
r
203
end else begin
204
let t = lremove k r in
205
Cons (k', v) t
206
end
207
end

The values of l are not zero

210
predicate
nonzero
(l:list binding) =
211
forall k v. assoc k l = Some v -> A.real v <> 0.0

Two optional coefficients with the same value

214
predicate
oeq
(o1 o2:option A.t) =
215
match o1, o2 with
216
| None, None -> true
217
| Some a, Some b -> A.real a = A.real b
218
| _ -> false
219
end

Two sorted lists with bindings of the same values have the same evaluation (the coefficients are compared by their values)

  Valid (1.2s) (colibri2 11) (cvc4 2) (split_vc) (depth 1)
223
let rec ghost
ext_eval
(l1 l2:list binding) : unit
224
requires { sorted l1 /\ sorted l2 }
225
requires { forall k. oeq (assoc k l1) (assoc k l2) }
226
ensures { forall env. evall env l1 = evall env l2 }
227
ensures { nonzero l1 <-> nonzero l2 }
228
variant { l1 }
229
= match l1, l2 with
230
| Nil, Nil -> ()
231
| Cons (k1, _) _, Nil -> assert { has k1 l1 }
232
| Nil, Cons (k2, _) _ -> assert { has k2 l2 }
233
| Cons (k1, _) r1, Cons (k2, _) r2 ->
234
assert { has k1 l2 };
235
assert { has k2 l1 };
236
if pure { k1 <> k2 } then begin
237
absurd
238
end;
239
let lemma pw (k:Atom.t) : unit
240
ensures { oeq (assoc k r1) (assoc k r2) }
241
= if pure { k = k1 } then begin
242
assert { not (has k r1) /\ not (has k r2) }
243
end else begin
244
assert { assoc k l2 = assoc k r2 }
245
end in
246
ext_eval r1 r2
247
end
248
end