Common — library colibrilib.sign_product — module SAssoc

Association lists from atoms to powers, sorted by atom, and their value

9
module SAssoc
10
use int.Int
11
use mach.int.Int63
12
use real.RealInfix
13
use list.List
14
use list.Mem
15
use option.Option
16
use colibrilib.ring.Atom

The power of a sign

19
type
power
=
Odd
|
Even
|
OddNonZero
20
21
type
binding
= (Atom.t, power)
22
23
function
assoc
(k:Atom.t) (l:list binding) : option power =
24
match l with
25
| Nil -> None
26
| Cons (k', v) r -> if k = k' then Some v else assoc k r
27
end
28
29
predicate
has
(k:Atom.t) (l:list binding) = assoc k l <> None

every key of l is above k

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

The sign of a real

41
function
sgn
(x:real) : real =
42
if 0.0 <. x then 1.0 else if x <. 0.0 then -. 1.0 else 0.0

0, 1 or –1

45
predicate
unit3
(s:real) = s = 0.0 \/ s = 1.0 \/ s = -. 1.0

The power v of the sign s

48
function
fac
(s:real) (v:power) : real =
49
match v with Even -> s *. s | Odd | OddNonZero -> s end
50
51
function
ofac
(s:real) (o:option power) : real =
52
match o with None -> 1.0 | Some v -> fac s v end

The product of the powers of the signs of l

55
function
evs
(env: Atom.t -> real) (l:list binding) : real =
56
match l with
57
| Nil -> 1.0
58
| Cons (k, v) r -> fac (sgn (env k)) v *. evs env r
59
end

The nodes OddNonZero of l are not zero

62
predicate
lvalid
(env: Atom.t -> real) (l:list binding) =
63
forall k. assoc k l = Some OddNonZero -> env k <> 0.0

The product of two powers of the same sign (None: 1)

66
let function
mulp
(o1 o2:option power) : option power =
67
match o1, o2 with
68
| None, o -> o
69
| o, None -> o
70
| Some Odd, Some Odd -> Some Even
71
| Some Even, Some v -> Some v
72
| Some v, Some Even -> Some v
73
| Some _, Some _ -> None
74
end

The closure of SPT.merge

77
let function
mulk
(_k:Atom.t) (o1 o2:option power) : option power =
78
mulp o1 o2
79
Valid (20ms) (colibri2)
80
let ghost
sgn_unit3
(x:real) : unit
81
ensures { unit3 (sgn x) }
82
ensures { sgn x = 0.0 <-> x = 0.0 }
83
= ()
84
Valid (331ms) (colibri2)
85
let ghost
mulp_fac
(s:real) (o1 o2:option power) : unit
86
requires { unit3 s }
87
requires { o1 = Some OddNonZero \/ o2 = Some OddNonZero -> s <> 0.0 }
88
ensures { ofac s (mulp o1 o2) = ofac s o1 *. ofac s o2 }
89
= ()
90
Valid (110ms) (colibri2)
91
let rec ghost
evs_unit3
(env: Atom.t -> real) (l:list binding) : unit
92
ensures { unit3 (evs env l) }
93
ensures { evs env l = 0.0 <-> exists k. has k l /\ env k = 0.0 }
94
variant { l }
95
= match l with
96
| Nil -> ()
97
| Cons (k, _) r -> evs_unit3 env r; sgn_unit3 (env k)
98
end

Two sorted lists with the same bindings are equal

  Valid (403ms) (colibri2)
101
let rec ghost
ext
(l1 l2:list binding) : unit
102
requires { sorted l1 /\ sorted l2 }
103
requires { forall k. assoc k l1 = assoc k l2 }
104
ensures { l1 = l2 }
105
variant { l1 }
106
= match l1, l2 with
107
| Nil, Nil -> ()
108
| Cons (k1, _) _, Nil -> assert { has k1 l1 }
109
| Nil, Cons (k2, _) _ -> assert { has k2 l2 }
110
| Cons (k1, v1) r1, Cons (k2, v2) r2 ->
111
assert { has k1 l2 };
112
assert { has k2 l1 };
113
if pure { k1 <> k2 } then begin
114
assert { lt k1 k2 /\ lt k2 k1 };
115
Atom.lt_trans k1 k2 k1;
116
absurd
117
end;
118
assert { v1 = v2 by assoc k1 l1 = assoc k1 l2 };
119
let lemma pw (k:Atom.t) : unit
120
ensures { assoc k r1 = assoc k r2 }
121
= if pure { k = k1 } then begin
122
assert { not (has k r1) /\ not (has k r2) }
123
end else begin
124
assert { assoc k l2 = assoc k r2 }
125
end in
126
ext r1 r2
127
end
128
Valid (15ms) (colibri2)
129
let ghost
assoc3
(a b c:real) : unit
130
ensures { a *. (b *. c) = (a *. b) *. c }
131
= ()
132
Valid (14ms) (colibri2)
133
let ghost
comm3
(a b c:real) : unit
134
ensures { a *. (b *. c) = b *. (a *. c) }
135
= ()

The product of two lists

  Valid (709ms) (colibri2 34) (split_vc) (depth 1)
138
let rec ghost
lmul
(l1 l2:list binding) : list binding
139
requires { sorted l1 /\ sorted l2 }
140
ensures { sorted result }
141
ensures { forall k. has k result -> has k l1 \/ has k l2 }
142
ensures { forall k. assoc k result = mulp (assoc k l1) (assoc k l2) }
143
ensures { forall env. lvalid env l1 -> lvalid env l2 ->
144
evs env result = evs env l1 *. evs env l2 /\ lvalid env result }
145
variant { l1, l2 }
146
= match l1, l2 with
147
| Nil, _ -> l2
148
| _, Nil -> l1
149
| Cons (k1, a) r1, Cons (k2, b) r2 ->
150
let c = Atom.compare k1 k2 in
151
if c < 0 then begin
152
let t = lmul r1 l2 in
153
let res = Cons (k1, a) t in
154
assert { not (has k1 l2) };
155
let lemma ab (k:Atom.t) : unit
156
requires { has k t }
157
ensures { lt k1 k }
158
= if pure { has k l2 /\ k <> k2 } then Atom.lt_trans k1 k2 k in
159
let lemma pw (k:Atom.t) : unit
160
ensures { assoc k res = mulp (assoc k l1) (assoc k l2) }
161
= if pure { k = k1 } then assert { not (has k1 t) } in
162
let lemma ev (env: Atom.t -> real) : unit
163
requires { lvalid env l1 /\ lvalid env l2 }
164
ensures { evs env res = evs env l1 *. evs env l2 }
165
= assert { lvalid env r1
166
by forall k. has k r1 -> assoc k r1 = assoc k l1 };
167
assoc3 (fac (sgn (env k1)) a) (evs env r1) (evs env l2) in
168
res
169
end else if c > 0 then begin
170
let t = lmul l1 r2 in
171
let res = Cons (k2, b) t in
172
assert { not (has k2 l1) };
173
let lemma ab (k:Atom.t) : unit
174
requires { has k t }
175
ensures { lt k2 k }
176
= if pure { has k l1 /\ k <> k1 } then Atom.lt_trans k2 k1 k in
177
let lemma pw (k:Atom.t) : unit
178
ensures { assoc k res = mulp (assoc k l1) (assoc k l2) }
179
= if pure { k = k2 } then assert { not (has k2 t) } in
180
let lemma ev (env: Atom.t -> real) : unit
181
requires { lvalid env l1 /\ lvalid env l2 }
182
ensures { evs env res = evs env l1 *. evs env l2 }
183
= assert { lvalid env r2
184
by forall k. has k r2 -> assoc k r2 = assoc k l2 };
185
comm3 (fac (sgn (env k2)) b) (evs env l1) (evs env r2) in
186
res
187
end else begin
188
let t = lmul r1 r2 in
189
let res = match mulp (Some a) (Some b) with
190
| None -> t
191
| Some v -> Cons (k1, v) t
192
end in
193
let lemma ab (k:Atom.t) : unit
194
requires { has k t }
195
ensures { lt k1 k }
196
= () in
197
let lemma pw (k:Atom.t) : unit
198
ensures { assoc k res = mulp (assoc k l1) (assoc k l2) }
199
= if pure { k = k1 } then assert { not (has k1 t) } in
200
let lemma ev (env: Atom.t -> real) : unit
201
requires { lvalid env l1 /\ lvalid env l2 }
202
ensures { evs env res = evs env l1 *. evs env l2 }
203
= assert { lvalid env r1
204
by forall k. has k r1 -> assoc k r1 = assoc k l1 };
205
assert { lvalid env r2
206
by forall k. has k r2 -> assoc k r2 = assoc k l2 };
207
sgn_unit3 (env k1);
208
mulp_fac (sgn (env k1)) (Some a) (Some b) in
209
res
210
end
211
end

l without x

  Valid (121ms) (colibri2)
214
let rec ghost
lrem
(x:Atom.t) (l:list binding) : list binding
215
requires { sorted l }
216
ensures { sorted result }
217
ensures { forall k. assoc k result = if k = x then None else assoc k l }
218
ensures { forall env. evs env l = ofac (sgn (env x)) (assoc x l) *. evs env result }
219
variant { l }
220
= match l with
221
| Nil -> Nil
222
| Cons (k, v) r ->
223
if Atom.equal k x then begin
224
assert { not (has x r) };
225
r
226
end else begin
227
let t = lrem x r in
228
let res = Cons (k, v) t in
229
assert { forall k'. has k' t -> has k' r };
230
res
231
end
232
end

Odd becomes OddNonZero

235
let function
liftp
(v:power) : power =
236
match v with Odd -> OddNonZero | v -> v end
237
238
function
omap
(o:option power) : option power =
239
match o with None -> None | Some v -> Some (liftp v) end

l with its Odd powers made OddNonZero: the same value

  Valid (334ms) (colibri2)
242
let rec ghost
llift
(l:list binding) : list binding
243
requires { sorted l }
244
ensures { sorted result }
245
ensures { forall k. assoc k result = omap (assoc k l) }
246
ensures { forall env. evs env result = evs env l }
247
variant { l }
248
= match l with
249
| Nil -> Nil
250
| Cons (k, v) r ->
251
let t = llift r in
252
assert { forall k'. has k' t -> has k' r };
253
Cons (k, liftp v) t
254
end

The atoms of l

  Valid (32ms) (colibri2)
257
let rec
keys
(l:list binding) : list Atom.t
258
ensures { forall k. Mem.mem k result <-> has k l }
259
variant { l }
260
= match l with
261
| Nil -> Nil
262
| Cons (k, _) r -> Cons k (keys r)
263
end
264
end