Common — library colibrilib.product — module QAssoc

Sorted association lists from the atoms to the exponents: the model of the maps of colibri2 (Node.PT) used by the products, as polynome.Assoc for the linear forms

194
module QAssoc
195
use int.Int
196
use mach.int.Int63
197
use real.RealInfix
198
use list.List
199
use option.Option
200
use colibrilib.ring.Atom
201
use colibrilib.stdq.StdQ as Q
202
use Apow
203
204
type
binding
= (Atom.t, Q.t)
205
206
function
assoc
(k:Atom.t) (l:list binding) : option Q.t =
207
match l with
208
| Nil -> None
209
| Cons (k', v) r -> if k = k' then Some v else assoc k r
210
end
211
212
predicate
has
(k:Atom.t) (l:list binding) = assoc k l <> None

every key of l is above k

215
predicate
above
(k:Atom.t) (l:list binding) = forall k'. has k' l -> lt k k'
216
217
predicate
sorted
(l:list binding) =
218
match l with
219
| Nil -> true
220
| Cons (k, _) r -> above k r /\ sorted r
221
end

The exponents of l are not zero

224
predicate
nonzero
(l:list binding) =
225
forall k v. assoc k l = Some v -> Q.real v <> 0.0

The exponent of k (zero when absent)

228
function
ex
(k:Atom.t) (l:list binding) : real =
229
match assoc k l with None -> 0.0 | Some v -> Q.real v end

The product of the |env k|^v

232
function
evp
(env: Atom.t -> real) (l:list binding) : real =
233
match l with
234
| Nil -> 1.0
235
| Cons (k, v) r -> apow (env k) (Q.real v) *. evp env r
236
end

Two optional exponents with the same value

239
predicate
oeq
(o1 o2:option Q.t) =
240
match o1, o2 with
241
| None, None -> true
242
| Some a, Some b -> Q.real a = Q.real b
243
| _ -> false
244
end
245
Valid (38ms) (colibri2)
246
let rec ghost
evp_nonneg
(env: Atom.t -> real) (l:list binding) : unit
247
ensures { 0.0 <=. evp env l }
248
variant { l }
249
= match l with
250
| Nil -> ()
251
| Cons (k, v) r -> evp_nonneg env r; apow_nonneg (env k) (Q.real v)
252
end

A product is zero exactly when one of its atoms is zero

  Valid (378ms) (colibri2 7) (split_vc 2) (depth 2)
255
let rec ghost
evp_zero
(env: Atom.t -> real) (l:list binding) : unit
256
requires { sorted l /\ nonzero l }
257
ensures { evp env l = 0.0 <-> exists k. has k l /\ env k = 0.0 }
258
variant { l }
259
= match l with
260
| Nil -> ()
261
| Cons (k, v) r ->
262
let lemma nz (k':Atom.t) (v':Q.t) : unit
263
requires { assoc k' r = Some v' }
264
ensures { Q.real v' <> 0.0 }
265
= if pure { k' = k } then begin
266
assert { has k r }; Atom.lt_irrefl k
267
end else assert { assoc k' l = Some v' } in
268
evp_zero env r;
269
apow_nonneg (env k) (Q.real v)
270
end

Two sorted lists with bindings of the same values have the same evaluation

  Valid (2.7s) (colibri2 13) (cvc5 5) (split_vc 3) (depth 2)
274
let rec ghost
ext_evp
(l1 l2:list binding) : unit
275
requires { sorted l1 /\ sorted l2 }
276
requires { forall k. oeq (assoc k l1) (assoc k l2) }
277
ensures { forall env. evp env l1 = evp env l2 }
278
ensures { nonzero l1 <-> nonzero l2 }
279
ensures { forall k. ex k l1 = ex k l2 }
280
ensures { forall k. has k l1 <-> has k l2 }
281
variant { l1 }
282
= match l1, l2 with
283
| Nil, Nil -> ()
284
| Cons (k1, _) _, Nil -> assert { has k1 l1 }
285
| Nil, Cons (k2, _) _ -> assert { has k2 l2 }
286
| Cons (k1, _) r1, Cons (k2, _) r2 ->
287
assert { has k1 l2 };
288
assert { has k2 l1 };
289
if pure { k1 <> k2 } then begin
290
absurd
291
end;
292
let lemma pw (k:Atom.t) : unit
293
ensures { oeq (assoc k r1) (assoc k r2) }
294
= if pure { k = k1 } then begin
295
assert { not (has k r1) /\ not (has k r2) }
296
end else begin
297
assert { assoc k l2 = assoc k r2 }
298
end in
299
ext_evp r1 r2
300
end

A non zero exponent

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

The exponents of l1^c1 * l2^c2

306
function
comb
(c1 c2:Q.t) (o1 o2:option Q.t) : option Q.t =
307
match o1, o2 with
308
| None, None -> None
309
| Some a, None -> nzv (Q.mul c1 a)
310
| None, Some b -> nzv (Q.mul c2 b)
311
| Some a, Some b -> nzv (Q.add (Q.mul c1 a) (Q.mul c2 b))
312
end

The atoms that are zero have exponents of the sign of the power: the condition of apow_add

316
predicate
compat
(env: Atom.t -> real) (c1 c2:real) (l1 l2:list binding) =
317
forall k. env k = 0.0 -> 0.0 <=. c1 *. ex k l1 /\ 0.0 <=. c2 *. ex k l2
318
Valid (32ms) (colibri2)
319
let ghost
step
(x a c e:real) : unit
320
ensures { apow (apow x a *. e) c = apow x (c *. a) *. apow e c }
321
= apow_prod (apow x a) e c; apow_apow x a c;
322
assert { a *. c = c *. a }
323
Valid (32ms) (colibri2)
324
let ghost
step2
(x a b c1 c2 e1 e2:real) : unit
325
requires { x <> 0.0 \/ (0.0 <=. c1 *. a /\ 0.0 <=. c2 *. b) }
326
ensures { apow (apow x a *. e1) c1 *. apow (apow x b *. e2) c2
327
= apow x (c1 *. a +. c2 *. b) *. (apow e1 c1 *. apow e2 c2) }
328
= step x a c1 e1; step x b c2 e2; apow_add x (c1 *. a) (c2 *. b)

l1^c1 * l2^c2

  Valid (972ms) (colibri2 49) (cvc5 3) (split_vc 5) (depth 2)
331
let rec ghost
lcomb
(c1 c2:Q.t) (l1 l2:list binding) : list binding
332
requires { sorted l1 /\ sorted l2 }
333
ensures { sorted result }
334
ensures { forall k. has k result -> has k l1 \/ has k l2 }
335
ensures { forall k. assoc k result = comb c1 c2 (assoc k l1) (assoc k l2) }
336
ensures { forall env. compat env (Q.real c1) (Q.real c2) l1 l2 ->
337
evp env result
338
= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }
339
variant { l1, l2 }
340
= match l1, l2 with
341
| Nil, Nil -> Nil
342
| Cons (k, a) r, Nil ->
343
let t = lcomb c1 c2 r Nil in
344
let v = Q.mul c1 a in
345
let res = if pure { Q.real v = 0.0 } then t else Cons (k, v) t in
346
let lemma pw (k':Atom.t) : unit
347
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
348
= if pure { k' = k } then assert { not (has k t) } in
349
let lemma ev (env: Atom.t -> real) : unit
350
requires { compat env (Q.real c1) (Q.real c2) l1 l2 }
351
ensures { evp env res
352
= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }
353
= assert { not (has k r) by not (lt k k) };
354
assert { compat env (Q.real c1) (Q.real c2) r Nil
355
by forall k'. ex k' r = (if k' = k then 0.0 else ex k' l1) };
356
step (env k) (Q.real a) (Q.real c1) (evp env r);
357
apow_zero (env k) in
358
res
359
| Nil, Cons (k, b) r ->
360
let t = lcomb c1 c2 Nil r in
361
let v = Q.mul c2 b in
362
let res = if pure { Q.real v = 0.0 } then t else Cons (k, v) t in
363
let lemma pw (k':Atom.t) : unit
364
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
365
= if pure { k' = k } then assert { not (has k t) } in
366
let lemma ev (env: Atom.t -> real) : unit
367
requires { compat env (Q.real c1) (Q.real c2) l1 l2 }
368
ensures { evp env res
369
= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }
370
= assert { not (has k r) by not (lt k k) };
371
assert { compat env (Q.real c1) (Q.real c2) Nil r
372
by forall k'. ex k' r = (if k' = k then 0.0 else ex k' l2) };
373
step (env k) (Q.real b) (Q.real c2) (evp env r);
374
apow_zero (env k) in
375
res
376
| Cons (k1, a) r1, Cons (k2, b) r2 ->
377
let c = Atom.compare k1 k2 in
378
if c < 0 then begin
379
let t = lcomb c1 c2 r1 l2 in
380
let v = Q.mul c1 a in
381
let res = if pure { Q.real v = 0.0 } then t else Cons (k1, v) t in
382
assert { not (has k1 l2) };
383
let lemma ab (k:Atom.t) : unit
384
requires { has k t }
385
ensures { lt k1 k }
386
= if pure { has k l2 /\ k <> k2 } then Atom.lt_trans k1 k2 k in
387
let lemma pw (k':Atom.t) : unit
388
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
389
= if pure { k' = k1 } then assert { not (has k1 t) } in
390
let lemma ev (env: Atom.t -> real) : unit
391
requires { compat env (Q.real c1) (Q.real c2) l1 l2 }
392
ensures { evp env res
393
= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }
394
= assert { compat env (Q.real c1) (Q.real c2) r1 l2
395
by forall k'. ex k' r1 = (if k' = k1 then 0.0 else ex k' l1) };
396
step (env k1) (Q.real a) (Q.real c1) (evp env r1);
397
apow_zero (env k1) in
398
res
399
end else if c > 0 then begin
400
let t = lcomb c1 c2 l1 r2 in
401
let v = Q.mul c2 b in
402
let res = if pure { Q.real v = 0.0 } then t else Cons (k2, v) t in
403
assert { not (has k2 l1) };
404
let lemma ab (k:Atom.t) : unit
405
requires { has k t }
406
ensures { lt k2 k }
407
= if pure { has k l1 /\ k <> k1 } then Atom.lt_trans k2 k1 k in
408
let lemma pw (k':Atom.t) : unit
409
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
410
= if pure { k' = k2 } then assert { not (has k2 t) } in
411
let lemma ev (env: Atom.t -> real) : unit
412
requires { compat env (Q.real c1) (Q.real c2) l1 l2 }
413
ensures { evp env res
414
= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }
415
= assert { compat env (Q.real c1) (Q.real c2) l1 r2
416
by forall k'. ex k' r2 = (if k' = k2 then 0.0 else ex k' l2) };
417
step (env k2) (Q.real b) (Q.real c2) (evp env r2);
418
apow_zero (env k2);
419
assert { apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2)
420
= apow (env k2) (Q.real c2 *. Q.real b)
421
*. (apow (evp env l1) (Q.real c1) *. apow (evp env r2) (Q.real c2)) } in
422
res
423
end else begin
424
let t = lcomb c1 c2 r1 r2 in
425
let v = Q.add (Q.mul c1 a) (Q.mul c2 b) in
426
let res = if pure { Q.real v = 0.0 } then t else Cons (k1, v) t in
427
let lemma pw (k':Atom.t) : unit
428
ensures { assoc k' res = comb c1 c2 (assoc k' l1) (assoc k' l2) }
429
= if pure { k' = k1 } then assert { not (has k1 t) } in
430
let lemma ev (env: Atom.t -> real) : unit
431
requires { compat env (Q.real c1) (Q.real c2) l1 l2 }
432
ensures { evp env res
433
= apow (evp env l1) (Q.real c1) *. apow (evp env l2) (Q.real c2) }
434
= assert { compat env (Q.real c1) (Q.real c2) r1 r2
435
by forall k'. ex k' r1 = (if k' = k1 then 0.0 else ex k' l1)
436
/\ ex k' r2 = (if k' = k1 then 0.0 else ex k' l2) };
437
assert { ex k1 l1 = Q.real a /\ ex k1 l2 = Q.real b };
438
step2 (env k1) (Q.real a) (Q.real b) (Q.real c1) (Q.real c2)
439
(evp env r1) (evp env r2);
440
apow_zero (env k1) in
441
res
442
end
443
end
444
Valid (33ms) (colibri2)
445
let ghost
nil_of_none
(l:list binding) : unit
446
requires { forall k. not has k l }
447
ensures { l = Nil }
448
= match l with Nil -> () | Cons (k, _) _ -> assert { has k l } end

l without the key k

  Valid (703ms) (colibri2)
451
let rec ghost
lremove
(k:Atom.t) (l:list binding) : list binding
452
requires { sorted l }
453
ensures { sorted result }
454
ensures { forall k'. assoc k' result = if k' = k then None else assoc k' l }
455
ensures { forall env. evp env l = apow (env k) (ex k l) *. evp env result }
456
variant { l }
457
= match l with
458
| Nil -> Nil
459
| Cons (k', v) r ->
460
if Atom.equal k k' then begin
461
assert { not (has k r) by not (lt k k) };
462
let lemma pw (k'':Atom.t) : unit
463
ensures { assoc k'' r = if k'' = k then None else assoc k'' l }
464
= () in
465
r
466
end else begin
467
let t = lremove k r in
468
assert { ex k l = ex k r };
469
Cons (k', v) t
470
end
471
end
472
end