Common — library colibrilib.fp_conv — module RealDom

The domain of the reals, on its proved type

The implementations of Env.getr, Env.getc, Env.updr and Env.updc, with the same specifications, on the trusted getu and updu that read and write the domain with its proved type (UnionCongr.t of colibrilib/union_congr.mlw): the extraction (fp_conv.drv) maps the four val of Env to them. A separate module, so that the proofs that use Env do not have union.mlw in their context.

520
module RealDom
521
use int.Int
522
use option.Option
523
use list.List
524
use real.RealInfix
525
use real.FromInt
526
use colibrilib.ring.Atom
527
use colibrilib.stda.StdA as A
528
use colibrilib.stdq.StdQ as Q
529
use colibrilib.bound.Bound as B
530
use colibrilib.union.Union as U
531
use colibrilib.congruence.Congruence as C
532
use colibrilib.union_congr.UnionCongr as UC
533
use colibrilib.dv.Dv as Dv
534
use Env

Egraph.get_dom of the domain of the reals (Dom_interval.dom)

537
val
getu
(d: envp 'm) (n:Atom.t) : option UC.t
538
ensures { match result with
539
| Some v -> (live d -> UC.mem (d.mr n) v) /\ forall x. d.ri n x -> UC.mem x v
540
| None -> true
541
end }

Dom_interval.upd_dom: the intersection with the domain of n

544
val
updu
(d:env) (n:Atom.t) (v:UC.t) : unit
545
requires { live d -> UC.mem (d.mr n) v }
546
writes { d.state }
547
ensures { (forall x. old d.ri n x -> UC.mem x v) -> d.ri = old d.ri /\ d.dy = old d.dy }
548
Valid (114ms) (colibri2)
549
let
bnd_of
(b: U.Make.Map.qbound) : bnd
550
ensures { forall x. U.Make.Map.cmp_inf_qbound b x <-> rmem_lo x result }
551
ensures { forall x. U.Make.Map.cmp_sup_qbound x b <-> rmem_hi x result }
552
= match b with
553
| U.Make.Map.BInf -> BInf
554
| U.Make.Map.BLarge q -> BLarge q
555
| U.Make.Map.BStrict q -> BStrict q
556
end
557
Valid (86ms) (colibri2)
558
let rec
rapp
(l1 l2: rdom) : rdom
559
variant { l1 }
560
ensures { forall x. rmem x result <-> rmem x l1 \/ rmem x l2 }
561
= match l1 with Nil -> l2 | Cons i l -> Cons i (rapp l l2) end

The intervals of u

  Valid (783ms) (colibri2)
564
let
to_rdom
(u: U.Make.t) : rdom
565
ensures { forall x. U.Make.memt x u -> rmem x result }
566
= let predicate inv (x: real) (l: rdom) = pure { rmem x l } in
567
let f (i: U.Make.Map.interval) : rdom
568
ensures { forall x. U.Make.Map.mem_interval x i -> inv x result }
569
= match i with
570
| U.Make.Map.Singleton q -> Cons (RSing q) Nil
571
| U.Make.Map.Inter lo hi -> Cons (RInter (bnd_of lo) (bnd_of hi)) Nil
572
end in
573
let union (a b: rdom) : rdom
574
ensures { forall x. inv x a \/ inv x b -> inv x result }
575
= rapp a b in
576
U.Make.Map.UnaryFold.map { U.Make.Map.UnaryFold.f = f; U.Make.Map.UnaryFold.union = union;
577
U.Make.Map.UnaryFold.inv = inv } u
578
Valid (159ms) (colibri2)
579
let
hull
(lo hi: bnd) : U.Make.convex_hull
580
ensures { forall x. rmem_lo x lo /\ rmem_hi x hi <-> U.Make.in_hull x result }
581
= let l = match lo with
582
| BInf -> None | BLarge q -> Some (q, B.Large) | BStrict q -> Some (q, B.Strict) end in
583
let h = match hi with
584
| BInf -> None | BLarge q -> Some (q, B.Large) | BStrict q -> Some (q, B.Strict) end in
585
(l, h)
586
Valid (362ms) (colibri2)
587
let
of_riv
(i: riv) : option UC.t
588
ensures { match result with
589
| Some v -> forall x. rmem_iv x i -> UC.mem x v
590
| None -> forall x. not rmem_iv x i
591
end }
592
= match i with
593
| RSing q -> Some (UC.singleton q)
594
| RInter lo hi -> UC.from_convex_hull (hull lo hi)
595
end

The domain of the reals of a list of intervals (None: empty)

  Valid (129ms) (colibri2)
598
let rec
of_rdom
(l: rdom) : option UC.t
599
variant { l }
600
ensures { match result with
601
| Some v -> forall x. rmem x l -> UC.mem x v
602
| None -> forall x. not rmem x l
603
end }
604
= match l with
605
| Nil -> None
606
| Cons i l' ->
607
match of_riv i, of_rdom l' with
608
| None, o -> o
609
| o, None -> o
610
| Some a, Some b -> Some (UC.union a b)
611
end
612
end
613
Valid (76ms) (colibri2)
614
let
getr
(d: envp 'm) (n:Atom.t) : option rdom
615
ensures { match result with
616
| Some v -> (live d -> rmem (d.mr n) v) /\ forall x. d.ri n x -> rmem x v
617
| None -> true
618
end }
619
= match getu d n with None -> None | Some v -> Some (to_rdom v.UC.u) end
620
Valid (352ms) (colibri2 6) (split_vc 3) (depth 2)
621
let
getc
(d: envp 'm) (n:Atom.t) : ocls
622
ensures { match result with
623
| Cls dv rm ->
624
(live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv) /\
625
forall x. d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv
626
| NoCls -> true
627
end }
628
= match getu d n with
629
| Some v -> match v.UC.c with
630
| Some cc ->
631
let dv = A.of_q cc.C.div in
632
let rm = cc.C.rem in
633
{proof…}
634
let lemma pt (x: real) : unit
635
requires { C.member x cc }
636
ensures { exists k: int. x = A.real rm +. from_int k *. A.real dv }
637
= let k = Dv.quot (x -. A.real rm) (Q.real cc.C.div) in
638
assert { x = A.real rm +. from_int k *. A.real dv } in
639
{qed}
640
mk_cls d n dv rm
641
| None -> NoCls
642
end
643
| None -> NoCls
644
end
645
Valid (1.2s) (colibri2 7) (split_vc) (depth 1)
646
let
updc
(d:env) (n:Atom.t) (dv rm: A.t) : unit
647
requires { live d -> exists k: int. d.mr n = A.real rm +. from_int k *. A.real dv }
648
writes { d.state }
649
ensures { (dropped dv \/
650
forall x. old d.ri n x -> exists k: int. x = A.real rm +. from_int k *. A.real dv) ->
651
d.ri = old d.ri /\ d.dy = old d.dy }
652
= if not (c_dropped dv) then
653
match A.view dv with
654
| A.Rat q ->
655
let c = UC.of_congruence { C.div = q; C.rem = rm } in
656
match getu d n with
657
| Some i -> if not (UC.is_included i c) then updu d n c
658
| None -> updu d n c
659
end
660
| A.Irr -> ()
661
end
662
Valid (699ms) (colibri2)
663
let
updr
(d:env) (n:Atom.t) (v:rdom) : unit
664
requires { live d -> rmem (d.mr n) v }
665
writes { d.state }
666
ensures { (forall x. old d.ri n x -> rmem x v) -> d.ri = old d.ri /\ d.dy = old d.dy }
667
= match of_rdom v with
668
| None -> contradiction d
669
| Some u -> updu d n u
670
end
671
end