Common — library colibrilib.polynome — module Lin

The linear polynomials

320
module Lin
321
use int.Int
322
use real.RealInfix
323
use real.Abs
324
use list.List
325
use list.Length
326
use option.Option
327
use colibrilib.ring.Atom
328
use colibrilib.stda.StdA as A
329
use Assoc
330
use PT
331
use colibrilib.spec.Sound
332
use colibrilib.spec.Eval
333
use colibrilib.spec.Value
334
use colibrilib.spec.Test
335
use colibrilib.spec.Opt

The coefficient a, unless it is zero

  Valid (38ms) (colibri2)
338
let function
nz
(a:A.t) : option A.t
339
ensures { result = nzv a }
340
= if A.is_zero a then None else Some a

No zero coefficient: every value of t is well formed

  Valid (126ms) (colibri2)
343
type
t
= {
cst
: A.t;
poly
: PT.t }
344
invariant { nonzero (bindings poly) }
345
by { cst = A.of_int 0; poly = PT.empty () }
346
347
function
eval
(env: Atom.t -> real) (p:t) : real =
348
A.real p.cst +. evall env (bindings p.poly)

The evaluation of a map is given by its bindings

  Valid (807ms) (colibri2 5) (split_vc) (depth 1)
351
let ghost
same_eval
(m:PT.t) (l1 l2:list binding) (c1 c2:A.t) : unit
352
requires { sorted l1 /\ sorted l2 }
353
requires { forall k. oeq (get k m) (comb c1 c2 (assoc k l1) (assoc k l2)) }
354
ensures { nonzero (bindings m) }
355
ensures { forall env. evall env (bindings m)
356
= A.real c1 *. evall env l1 +. A.real c2 *. evall env l2 }
357
= let l = lcomb c1 c2 l1 l2 in
358
ext_eval (bindings m) l

eval with the arguments in the order of the shapes of spec.Eval

361
function
value
(p:t) (env: Atom.t -> real) : real = eval env p

p has the value of the atom n

364
predicate
is_node
(p:t) (n:Atom.t) = denotes0 value (fun env -> env n) p

p has the absolute value of the atom y

367
predicate
is_abs_node
(p:t) (y:Atom.t) =
368
forall env. abs (eval env p) = abs (env y)
369
Valid (29ms) (colibri2)
370
let
zero
() : t
371
ensures { denotes0 value (fun _ -> 0.0) result }
372
= { cst = A.of_int 0; poly = PT.empty () }
373
Valid (26ms) (colibri2)
374
let
const
(c:A.t) : t
375
ensures { denotes0 value (fun _ -> A.real c) result }
376
= { cst = c; poly = PT.empty () }

c * x

  Valid (51ms) (colibri2)
379
let
monome
(c:A.t) (x:Atom.t) : t
380
ensures { denotes0 value (fun env -> A.real c *. env x) result }
381
= if A.equal c (A.of_int 0) then { cst = A.of_int 0; poly = PT.empty () }
382
else { cst = A.of_int 0; poly = PT.singleton x c }
383
Valid (28ms) (colibri2)
384
let
is_cst
(p:t) : option A.t
385
ensures { match result with
386
| Some c -> bindings p.poly = Nil /\ c = p.cst
387
| None -> bindings p.poly <> Nil
388
end }
389
= if PT.is_empty p.poly then Some p.cst else None
390
Valid (30ms) (colibri2)
391
let
is_zero
(p:t) : bool
392
ensures { decides (bindings p.poly = Nil /\ A.real p.cst = 0.0) result }
393
= A.equal p.cst (A.of_int 0) && PT.is_empty p.poly
394
Valid (22ms) (colibri2)
395
let
add_cst
(p:t) (c:A.t) : t
396
ensures { denotes1 value (fun v -> v +. A.real c) p result }
397
= { p with cst = A.add p.cst c }
398
Valid (26ms) (colibri2)
399
let
sub_cst
(p:t) (c:A.t) : t
400
ensures { denotes1 value (fun v -> v -. A.real c) p result }
401
= { p with cst = A.sub p.cst c }

The closure of add, x_p_cy and cx_p_cy: c1 * o1 + c2 * o2

  Valid (20ms) (colibri2)
404
let function
combf
(c1 c2:A.t) (_k:Atom.t) (o1 o2:option A.t) : option A.t =
405
match o1, o2 with
406
| None, None -> None
407
| Some a, None -> nz (A.mul c1 a)
408
| None, Some b -> nz (A.mul c2 b)
409
| Some a, Some b -> nz (A.add (A.mul c1 a) (A.mul c2 b))
410
end

c1 * p1 + c2 * p2

  Valid (432ms) (colibri2 7) (cvc5) (split_vc) (depth 1)
413
let
cx_p_cy
(c1:A.t) (p1:t) (c2:A.t) (p2:t) : t
414
ensures { denotes2 value (fun x y -> A.real c1 *. x +. A.real c2 *. y) p1 p2 result }
415
= let m = PT.merge (combf c1 c2) p1.poly p2.poly in
416
same_eval m (bindings p1.poly) (bindings p2.poly) c1 c2;
417
let res = { cst = A.add (A.mul c1 p1.cst) (A.mul c2 p2.cst); poly = m } in
418
let lemma ev (env: Atom.t -> real) : unit
419
ensures { eval env res
420
= A.real c1 *. eval env p1 +. A.real c2 *. eval env p2 }
421
= let e1 = evall env (bindings p1.poly) in
422
let e2 = evall env (bindings p2.poly) in
423
assert { eval env res = A.real c1 *. A.real p1.cst +. A.real c2 *. A.real p2.cst
424
+. (A.real c1 *. e1 +. A.real c2 *. e2) };
425
assert { A.real c1 *. (A.real p1.cst +. e1) +. A.real c2 *. (A.real p2.cst +. e2)
426
= A.real c1 *. A.real p1.cst +. A.real c2 *. A.real p2.cst
427
+. (A.real c1 *. e1 +. A.real c2 *. e2) } in
428
res

The closure of add: no multiplication

  Valid (24ms) (colibri2)
431
let function
addf
(_k:Atom.t) (o1 o2:option A.t) : option A.t =
432
match o1, o2 with
433
| None, o | o, None -> o
434
| Some a, Some b -> nz (A.add a b)
435
end
436
Valid (385ms) (colibri2 11) (cvc4) (split_vc 2) (depth 2)
437
let
add
(p1 p2:t) : t
438
ensures { denotes2 value (+.) p1 p2 result }
439
= let m = PT.merge addf p1.poly p2.poly in
440
let ghost one = A.of_int 1 in
441
let lemma pw (k:Atom.t) : unit
442
ensures { oeq (get k m) (comb one one (get k p1.poly) (get k p2.poly)) }
443
= match get k p1.poly, get k p2.poly with
444
| Some a, None -> assert { A.real (A.mul one a) = A.real a }
445
| None, Some b -> assert { A.real (A.mul one b) = A.real b }
446
| Some a, Some b -> assert { A.real (A.add (A.mul one a) (A.mul one b)) = A.real (A.add a b) }
447
| None, None -> ()
448
end in
449
same_eval m (bindings p1.poly) (bindings p2.poly) one one;
450
{ cst = A.add p1.cst p2.cst; poly = m }

The closure of sub, m1 is -1

  Valid (27ms) (colibri2)
453
let function
subf
(m1:A.t) (_k:Atom.t) (o1 o2:option A.t) : option A.t =
454
match o1, o2 with
455
| o, None -> o
456
| None, Some b -> nz (A.mul m1 b)
457
| Some a, Some b -> nz (A.sub a b)
458
end
459
Valid (1.4s) (colibri2 9) (cvc5) (split_vc 2) (depth 2)
460
let
sub
(p1 p2:t) : t
461
ensures { denotes2 value (-.) p1 p2 result }
462
= let ghost one = A.of_int 1 in
463
let m1 = A.of_int (-1) in
464
let m = PT.merge (subf m1) p1.poly p2.poly in
465
let lemma pw (k:Atom.t) : unit
466
ensures { oeq (get k m) (comb one m1 (get k p1.poly) (get k p2.poly)) }
467
= match get k p1.poly, get k p2.poly with
468
| Some a, None -> assert { A.real (A.mul one a) = A.real a }
469
| Some _, Some _ ->
470
()
471
| _ -> ()
472
end in
473
same_eval m (bindings p1.poly) (bindings p2.poly) one m1;
474
{ cst = A.sub p1.cst p2.cst; poly = m }

The closure of mult_cst

  Valid (22ms) (colibri2)
477
let function
mulf
(c v:A.t) : A.t = A.mul c v

c * p

  Valid (223ms) (colibri2 8) (split_vc) (depth 1)
480
let
mult_cst
(c:A.t) (p:t) : t
481
ensures { denotes1 value (fun v -> A.real c *. v) p result }
482
= if A.equal c (A.of_int 1) then p
483
else if A.equal c (A.of_int 0) then zero ()
484
else begin
485
let m = PT.map (mulf c) p.poly in
486
let ghost z = A.of_int 0 in
487
let lemma pw (k:Atom.t) : unit
488
ensures { oeq (get k m) (comb c z (get k p.poly) None) }
489
= match get k p.poly with
490
| Some v -> assert { A.real (A.mul c v) <> 0.0 }
491
| None -> ()
492
end in
493
same_eval m (bindings p.poly) Nil c z;
494
let res = { cst = A.mul c p.cst; poly = m } in
495
let lemma ev (env: Atom.t -> real) : unit
496
ensures { eval env res = A.real c *. eval env p }
497
= let e = evall env (bindings p.poly) in
498
assert { A.real c *. (A.real p.cst +. e) = A.real c *. A.real p.cst +. A.real c *. e } in
499
res
500
end
501
Valid (55ms) (colibri2)
502
let
neg
(p:t) : t
503
ensures { denotes1 value (fun v -> -. v) p result }
504
= mult_cst (A.of_int (-1)) p

The closure of x_p_cy

  Valid (28ms) (colibri2)
507
let function
xpcyf
(c:A.t) (_k:Atom.t) (o1 o2:option A.t) : option A.t =
508
match o1, o2 with
509
| o, None -> o
510
| None, Some b -> nz (A.mul c b)
511
| Some a, Some b -> nz (A.add a (A.mul c b))
512
end

p1 + c * p2

  Valid (1.1s) (colibri2 11) (cvc5) (split_vc 2) (depth 2)
515
let
x_p_cy
(p1:t) (c:A.t) (p2:t) : t
516
ensures { denotes2 value (fun x y -> x +. A.real c *. y) p1 p2 result }
517
= let ghost one = A.of_int 1 in
518
let m = PT.merge (xpcyf c) p1.poly p2.poly in
519
let lemma pw (k:Atom.t) : unit
520
ensures { oeq (get k m) (comb one c (get k p1.poly) (get k p2.poly)) }
521
= match get k p1.poly, get k p2.poly with
522
| Some a, None -> assert { A.real (A.mul one a) = A.real a }
523
| Some _, Some _ ->
524
()
525
| _ -> ()
526
end in
527
same_eval m (bindings p1.poly) (bindings p2.poly) one c;
528
let res = { cst = A.add p1.cst (A.mul c p2.cst); poly = m } in
529
let lemma ev (env: Atom.t -> real) : unit
530
ensures { eval env res = eval env p1 +. A.real c *. eval env p2 }
531
= let e2 = evall env (bindings p2.poly) in
532
assert { A.real c *. (A.real p2.cst +. e2) = A.real c *. A.real p2.cst +. A.real c *. e2 } in
533
res

The coefficient of x in p (zero if absent)

536
function
coef
(x:Atom.t) (p:t) : real =
537
match get x p.poly with None -> 0.0 | Some v -> A.real v end

p without its monomial on x

  Valid (242ms) (colibri2 7) (split_vc) (depth 1)
540
let
remove
(x:Atom.t) (p:t) : t
541
ensures { result.cst = p.cst }
542
ensures { not (has x (bindings result.poly)) }
543
ensures { denotes0 value (fun env -> eval env p -. coef x p *. env x) result }
544
= let m = PT.remove x p.poly in
545
let l = lremove x (bindings p.poly) in
546
ext (bindings m) l;
547
{ cst = p.cst; poly = m }

p where x is replaced by s, and the coefficient of x in p

  Valid (488ms) (colibri2 6) (split_vc) (depth 1)
550
let
subst
(p:t) (x:Atom.t) (s:t) : (t, A.t)
551
returns { (r, q) -> A.real q = coef x p
552
/\ denotes0 value (fun env -> eval env p +. A.real q *. (eval env s -. env x)) r }
553
= match PT.find_opt x p.poly with
554
| None ->
555
let q = A.of_int 0 in
556
assert { forall env. eval env p = eval env p +. A.real q *. (eval env s -. env x) };
557
(p, q)
558
| Some q ->
559
let p' = remove x p in
560
let r = x_p_cy p' q s in
561
let lemma ev (env: Atom.t -> real) : unit
562
ensures { eval env r = eval env p +. A.real q *. (eval env s -. env x) }
563
= assert { eval env p' = eval env p -. A.real q *. env x };
564
assert { eval env r = eval env p' +. A.real q *. eval env s };
565
assert { A.real q *. (eval env s -. env x)
566
= A.real q *. eval env s -. A.real q *. env x } in
567
(r, q)
568
end

The closure of subst_node

  Valid (20ms) (colibri2)
571
let function
updf
(q:A.t) (o:option A.t) : option A.t =
572
match o with None -> Some q | Some q' -> nz (A.add q q') end

p where x is replaced by y, and the coefficient of x in p

  Valid (1.1s) (colibri2 14) (split_vc) (depth 1)
575
let
subst_node
(p:t) (x y:Atom.t) : (t, A.t)
576
returns { (r, q) -> A.real q = coef x p
577
/\ denotes0 value (fun env -> eval env p +. A.real q *. (env y -. env x)) r }
578
= match PT.find_opt x p.poly with
579
| None ->
580
let q = A.of_int 0 in
581
assert { forall env. eval env p = eval env p +. A.real q *. (env y -. env x) };
582
(p, q)
583
| Some q ->
584
let p' = remove x p in
585
let m = PT.update y (updf q) p'.poly in
586
let ghost one = A.of_int 1 in
587
let ghost ly = Cons (y, one) Nil in
588
let lemma pw (k:Atom.t) : unit
589
ensures { oeq (get k m) (comb one q (get k p'.poly) (assoc k ly)) }
590
= if pure { k = y } then
591
match get k p'.poly with
592
| None -> assert { A.real (A.mul q one) = A.real q }
593
| Some q' -> assert { A.real (A.add (A.mul one q') (A.mul q one)) = A.real (A.add q q') }
594
end
595
else
596
match get k p'.poly with
597
| None -> ()
598
| Some a -> assert { A.real (A.mul one a) = A.real a }
599
end in
600
same_eval m (bindings p'.poly) ly one q;
601
let r = { cst = p.cst; poly = m } in
602
let lemma ev (env: Atom.t -> real) : unit
603
ensures { eval env r = eval env p +. A.real q *. (env y -. env x) }
604
= assert { evall env ly = env y };
605
assert { evall env (bindings m) = evall env (bindings p'.poly) +. A.real q *. env y };
606
assert { eval env p' = eval env p -. A.real q *. env x };
607
assert { A.real q *. (env y -. env x) = A.real q *. env y -. A.real q *. env x } in
608
(r, q)
609
end
610
611
type
extract
=
612
|
Zero
613
|
Cst
A.t
614
|
Var
A.t Atom.t t

Var q x p': p = q * x + p'

  Valid (325ms) (colibri2)
617
let
extract
(p:t) : extract
618
ensures { match result with
619
| Zero -> bindings p.poly = Nil /\ A.real p.cst = 0.0
620
| Cst c -> bindings p.poly = Nil /\ c = p.cst /\ A.real c <> 0.0
621
| Var q x p' -> get x p.poly = Some q /\ not (has x (bindings p'.poly))
622
/\ denotes0 value (fun env -> A.real q *. env x +. eval env p') p
623
end }
624
= if PT.is_empty p.poly then
625
if A.equal p.cst (A.of_int 0) then Zero else Cst p.cst
626
else begin
627
let x, q = PT.pivot_binding p.poly in
628
Var q x (remove x p)
629
end
630
631
type
kind
=
ZERO
|
CST
|
VAR
632
Valid (33ms) (colibri2)
633
let
classify
(p:t) : kind
634
ensures { match result with
635
| ZERO -> bindings p.poly = Nil /\ A.real p.cst = 0.0
636
| CST -> bindings p.poly = Nil /\ A.real p.cst <> 0.0
637
| VAR -> bindings p.poly <> Nil
638
end }
639
= if PT.is_empty p.poly then
640
if A.equal p.cst (A.of_int 0) then ZERO else CST
641
else VAR

p is the node n

  Valid (241ms) (colibri2)
644
let
is_one_node
(p:t) : option Atom.t
645
ensures { when_some (is_node p) result }
646
= if A.equal p.cst (A.of_int 0) && PT.cardinal p.poly = 1 then begin
647
let n, k = PT.min_binding p.poly in
648
if A.equal k (A.of_int 1) then begin
649
assert { match bindings p.poly with
650
| Cons (n', k') Nil -> n' = n /\ k' = k
651
| _ -> false end };
652
Some n
653
end else None
654
end else None

The constant of p

  Valid (22ms) (colibri2)
657
let
cst_of
(p:t) : A.t
658
ensures { value_is p.cst result }
659
= p.cst

The bindings of p

  Valid (27ms) (colibri2)
662
let
atoms
(p:t) : list binding
663
ensures { value_is (bindings p.poly) result }
664
= PT.to_list p.poly

p is y or -y

  Valid (1.0s) (cvc5)
667
let
is_pm_node
(p:t) : option Atom.t
668
ensures { when_some (is_abs_node p) result }
669
= if A.equal p.cst (A.of_int 0) && PT.cardinal p.poly = 1 then begin
670
let y, k = PT.min_binding p.poly in
671
if A.equal (A.abs k) (A.of_int 1) then begin
672
assert { match bindings p.poly with
673
| Cons (y', k') Nil -> y' = y /\ k' = k
674
| _ -> false end };
675
Some y
676
end else None
677
end else None

cst + c1 * x1 + ... + cn * xn for the list (x1, c1); ... (the atoms may repeat)

  Valid (468ms) (colibri2 11) (split_vc 3) (depth 3)
681
let rec
of_list
(c:A.t) (l:list binding) : t
682
ensures { denotes0 value (fun env -> A.real c +. evall env l) result }
683
variant { l }
684
= match l with
685
| Nil -> const c
686
| Cons (x, q) r ->
687
let p = of_list c r in
688
if A.equal q (A.of_int 0) then p
689
else begin
690
let m = PT.update x (updf q) p.poly in
691
let ghost one = A.of_int 1 in
692
let ghost lx = Cons (x, one) Nil in
693
let lemma pw (k:Atom.t) : unit
694
ensures { oeq (get k m) (comb one q (get k p.poly) (assoc k lx)) }
695
= if pure { k = x } then
696
match get k p.poly with
697
| None -> assert { A.real (A.mul q one) = A.real q }
698
| Some q' -> assert { A.real (A.add (A.mul one q') (A.mul q one)) = A.real (A.add q q') }
699
end
700
else
701
match get k p.poly with
702
| None -> ()
703
| Some a -> assert { A.real (A.mul one a) = A.real a }
704
end in
705
same_eval m (bindings p.poly) lx one q;
706
{ cst = p.cst; poly = m }
707
end
708
end
709
end