Common — library colibrilib.sign_product — module Sign

The products of signs, and the solver of the equations between them

306
module Sign
307
use int.Int
308
use mach.int.Int63
309
use real.RealInfix
310
use list.List
311
use list.Mem
312
use list.Append
313
use option.Option
314
use colibrilib.ring.Atom
315
use SAssoc
316
use SPT
317
318
type
cst
=
Pos
|
Neg

Zero, or P c m: c times the powers of the signs of m

321
type
t
=
Zero
|
P
cst SPT.t
322
323
function
cv
(c:cst) : real = match c with Pos -> 1.0 | Neg -> -. 1.0 end
324
325
function
eval
(env: Atom.t -> real) (p:t) : real =
326
match p with
327
| Zero -> 0.0
328
| P c m -> cv c *. evs env (bindings m)
329
end

The nodes OddNonZero are not zero

332
predicate
valid
(env: Atom.t -> real) (p:t) =
333
match p with
334
| Zero -> true
335
| P _ m -> lvalid env (bindings m)
336
end
337
338
predicate
mem
(k:Atom.t) (p:t) =
339
match p with
340
| Zero -> false
341
| P _ m -> has k (bindings m)
342
end
343
Valid (32ms) (colibri2)
344
let ghost
eval_unit3
(env: Atom.t -> real) (p:t) : unit
345
ensures { unit3 (eval env p) }
346
ensures { eval env p = 0.0 <-> (p = Zero \/ exists k. mem k p /\ env k = 0.0) }
347
= match p with
348
| Zero -> ()
349
| P _ m -> evs_unit3 env (bindings m)
350
end
351
352
let function
mulc
(c1 c2:cst) : cst =
353
match c1, c2 with
354
| Pos, c | c, Pos -> c
355
| Neg, Neg -> Pos
356
end

p1 * p2

  Valid (48ms) (colibri2 10) (split_vc) (depth 1)
359
let
mul
(p1 p2:t) : t
360
ensures { forall env. valid env p1 -> valid env p2 ->
361
eval env result = eval env p1 *. eval env p2 /\ valid env result }
362
ensures { forall k. mem k result -> mem k p1 \/ mem k p2 }
363
= match p1, p2 with
364
| Zero, _ -> Zero
365
| _, Zero -> Zero
366
| P c1 m1, P c2 m2 ->
367
let m = SPT.merge mulk m1 m2 in
368
let ghost l = lmul (bindings m1) (bindings m2) in
369
ext (bindings m) l;
370
let r = P (mulc c1 c2) m in
371
let lemma ev (env: Atom.t -> real) : unit
372
requires { valid env p1 /\ valid env p2 }
373
ensures { eval env r = eval env p1 *. eval env p2 }
374
= let e1 = evs env (bindings m1) in
375
let e2 = evs env (bindings m2) in
376
assert { evs env (bindings m) = e1 *. e2 };
377
assert { cv (mulc c1 c2) = cv c1 *. cv c2 };
378
assert { (cv c1 *. cv c2) *. (e1 *. e2) = (cv c1 *. e1) *. (cv c2 *. e2) } in
379
r
380
end

The solutions: as Solve.solved of product.mlw

383
type
solved
=
384
|
AlreadyEqual
385
|
Contradiction
386
|
Subst
Atom.t t

sgn x = q

387
|
Unsolved

The result of the solving of e: a substitution is equivalent to e

390
predicate
solves
(h: (Atom.t -> real) -> bool) (e: (Atom.t -> real) -> bool)
391
(r:solved) =
392
match r with
393
| AlreadyEqual -> forall env. h env -> e env
394
| Contradiction -> forall env. h env -> not (e env)
395
| Subst x q -> not mem x q /\
396
forall env. h env -> (e env <-> sgn (env x) = eval env q /\ valid env q)
397
| Unsolved -> true
398
end

All the powers of l are OddNonZero

  Valid (19ms) (colibri2)
401
let rec
all_nz_list
(l:list binding) : bool
402
ensures { result -> forall k v. assoc k l = Some v -> v = OddNonZero }
403
variant { l }
404
= match l with
405
| Nil -> true
406
| Cons (_, OddNonZero) r -> all_nz_list r
407
| Cons _ _ -> false
408
end

p is not zero, by valid

  Valid (31ms) (cvc5)
411
let
all_nz
(p:t) : bool
412
ensures { result -> forall env. valid env p -> eval env p <> 0.0 }
413
= match p with
414
| Zero -> false
415
| P _ m ->
416
let r = all_nz_list (SPT.to_list m) in
417
if r then begin
418
let lemma nz (env: Atom.t -> real) : unit
419
requires { valid env p }
420
ensures { eval env p <> 0.0 }
421
= eval_unit3 env p in
422
()
423
end;
424
r
425
end

A node OddNonZero of l

  Valid (35ms) (colibri2 7) (cvc5) (split_vc 2) (depth 2)
428
let rec
find_power
(w:power) (l:list binding) : option Atom.t
429
requires { sorted l }
430
ensures { match result with
431
| Some x -> assoc x l = Some w
432
| None -> forall k. assoc k l <> Some w end }
433
variant { l }
434
= match l with
435
| Nil -> None
436
| Cons (k, v) r ->
437
if match v, w with
438
| Odd, Odd | Even, Even | OddNonZero, OddNonZero -> true
439
| _ -> false end
440
then Some k
441
else match find_power w r with
442
| Some x -> Some x
443
| None -> None
444
end
445
end

The node to substitute: a node OddNonZero, or else a node Odd when there is no Even

  Valid (33ms) (colibri2)
449
let
choose_x
(l:list binding) : option Atom.t
450
requires { sorted l }
451
ensures { match result with
452
| Some x -> assoc x l = Some OddNonZero \/
453
(assoc x l = Some Odd /\ forall k. assoc k l <> Some Even)
454
| None -> true end }
455
= match find_power OddNonZero l with
456
| Some x -> Some x
457
| None ->
458
match find_power Even l with
459
| Some _ -> None
460
| None -> find_power Odd l
461
end
462
end

A solution of an equivalent equation

  Valid (30ms) (colibri2)
465
let ghost
transfer
(h h' e e': (Atom.t -> real) -> bool) (r:solved) : unit
466
requires { solves h' e' r }
467
requires { forall env. h env -> h' env /\ (e env <-> e' env) }
468
ensures { solves h e r }
469
= ()

eval p = 1

  Valid (724ms) (colibri2 19) (cvc5 3) (split_vc 7) (depth 4)
472
let
solve_one
(p:t) : solved
473
ensures { solves (fun env -> valid env p) (fun env -> eval env p = 1.0) result }
474
= match p with
475
| Zero -> Contradiction
476
| P c m ->
477
if SPT.is_empty m then
478
match c with Pos -> AlreadyEqual | Neg -> Contradiction end
479
else begin
480
let l = SPT.to_list m in
481
match choose_x l with
482
| None -> Unsolved
483
| Some x ->
484
let r = SPT.remove x m in
485
let mq = SPT.map liftp r in
486
let q = P c mq in
487
let ghost lr = lrem x l in
488
ext (bindings r) lr;
489
let ghost ll = llift lr in
490
ext (bindings mq) ll;
491
let lemma ev (env: Atom.t -> real) : unit
492
requires { valid env p }
493
ensures { eval env p = 1.0 <-> sgn (env x) = eval env q /\ valid env q }
494
= let s = sgn (env x) in
495
sgn_unit3 (env x);
496
evs_unit3 env lr;
497
evs_unit3 env l;
498
assert { evs env l = s *. evs env lr };
499
assert { evs env (bindings mq) = evs env lr };
500
comm3 s (cv c) (evs env lr);
501
assert { eval env p = s *. eval env q };
502
if pure { eval env p = 1.0 } then begin
503
assert { forall k. has k l -> env k <> 0.0 };
504
assert { valid env q }
505
end else if pure { s = eval env q /\ valid env q } then begin
506
if pure { assoc x l = Some Odd } then begin
507
assert { forall k. assoc k ll = Some OddNonZero \/ assoc k ll = None };
508
assert { forall k. has k ll -> env k <> 0.0 };
509
evs_unit3 env ll
510
end;
511
assert { s <> 0.0 }
512
end in
513
Subst x q
514
end
515
end
516
end

p1 = p2, p1 with a single possibly–zero node n, not in p2: sgn n = p2 * (p1 without n)

  Valid (404ms) (colibri2 8) (cvc5 2) (split_vc) (depth 1)
520
let
one_odd
(p1 p2:t) : solved
521
ensures { solves (fun env -> valid env p1 /\ valid env p2)
522
(fun env -> eval env p1 = eval env p2) result }
523
= match p1 with
524
| Zero -> Unsolved
525
| P c m ->
526
let l = SPT.to_list m in
527
match find_power Odd l with
528
| None -> Unsolved
529
| Some n ->
530
let r = SPT.remove n m in
531
let lr = SPT.to_list r in
532
let in_p2 = match p2 with
533
| Zero -> false
534
| P _ m2 -> match SPT.find_opt n m2 with None -> false | Some _ -> true end
535
end in
536
if not in_p2 && all_nz_list lr then begin
537
let rest = P c r in
538
let q = mul p2 rest in
539
let ghost glr = lrem n l in
540
ext (bindings r) glr;
541
let lemma ev (env: Atom.t -> real) : unit
542
requires { valid env p1 /\ valid env p2 }
543
ensures { eval env p1 = eval env p2 <-> sgn (env n) = eval env q /\ valid env q }
544
= let s = sgn (env n) in
545
sgn_unit3 (env n);
546
assert { valid env rest };
547
eval_unit3 env rest;
548
assert { eval env rest <> 0.0 };
549
eval_unit3 env p2;
550
assert { eval env p1 = s *. eval env rest };
551
assert { eval env q = eval env p2 *. eval env rest } in
552
Subst n q
553
end else Unsolved
554
end
555
end

The atoms of l are not zero when e holds

558
predicate
non_zero
(h: (Atom.t -> real) -> bool) (e: (Atom.t -> real) -> bool)
559
(l:list Atom.t) =
560
forall env. h env -> e env -> forall k. Mem.mem k l -> env k <> 0.0

The atoms of p

  Valid (30ms) (colibri2)
563
let
atoms
(p:t) : list Atom.t
564
ensures { forall k. Mem.mem k result <-> mem k p }
565
= match p with
566
| Zero -> Nil
567
| P _ m -> keys (SPT.to_list m)
568
end

p1 = p2, and the nodes that it makes non zero: when one side is non zero, all the nodes of both sides (Subst cannot say it for the nodes it does not substitute)

  Valid (160ms) (colibri2 9) (split_vc 2) (depth 2)
573
let
solve
(p1 p2:t) : (solved, list Atom.t)
574
returns { (r, l) ->
575
solves (fun env -> valid env p1 /\ valid env p2)
576
(fun env -> eval env p1 = eval env p2) r /\
577
non_zero (fun env -> valid env p1 /\ valid env p2)
578
(fun env -> eval env p1 = eval env p2) l }
579
= if all_nz p1 || all_nz p2 then begin
580
let a1 = atoms p1 in
581
let a2 = atoms p2 in
582
let l = a1 ++ a2 in
583
let lemma nz (env: Atom.t -> real) (k:Atom.t) : unit
584
requires { valid env p1 /\ valid env p2 }
585
requires { eval env p1 = eval env p2 }
586
requires { Mem.mem k l }
587
ensures { env k <> 0.0 }
588
= eval_unit3 env p1; eval_unit3 env p2;
589
mem_append k a1 a2 in
590
let p = mul p2 p1 in
591
let lemma ev (env: Atom.t -> real) : unit
592
requires { valid env p1 /\ valid env p2 }
593
ensures { valid env p }
594
ensures { eval env p1 = eval env p2 <-> eval env p = 1.0 }
595
= eval_unit3 env p1; eval_unit3 env p2 in
596
let r = solve_one p in
597
transfer (pure { fun (env: Atom.t -> real) -> valid env p1 /\ valid env p2 })
598
(pure { fun (env: Atom.t -> real) -> valid env p })
599
(pure { fun (env: Atom.t -> real) -> eval env p1 = eval env p2 })
600
(pure { fun (env: Atom.t -> real) -> eval env p = 1.0 }) r;
601
(r, l)
602
end else
603
match one_odd p1 p2 with
604
| Unsolved ->
605
let r = one_odd p2 p1 in
606
transfer (pure { fun (env: Atom.t -> real) -> valid env p1 /\ valid env p2 })
607
(pure { fun (env: Atom.t -> real) -> valid env p2 /\ valid env p1 })
608
(pure { fun (env: Atom.t -> real) -> eval env p1 = eval env p2 })
609
(pure { fun (env: Atom.t -> real) -> eval env p2 = eval env p1 }) r;
610
(r, Nil)
611
| r -> (r, Nil)
612
end
613
end