library colibrilib.summarize — module ExportThe functor seen by OCaml. Extraction makes a functor of a scope that begins with its parameters (F, FI), and such a scope cannot be used from another module, so this Export is also the core: it holds only fold and mk_partly_defensive.
module Export35use bool.Bool36use int.Int37use array.Array38scope List39use export list.List40use export list.Length41use export list.NthNoOpt42type t 'a = list 'a43end4445scope Make4647clone F {… begin (* cloned colibrilib.summarize.F *) type Make.F.t predicate Make.F.(<) t t predicate Make.F.(<=) t t axiom Make.F.total axiom Make.F.transitive val Make.F.lt t t : bool end } with axiom total, axiom transitive4849scope FI50type intervals = List.t ( t, t)5152predicate ordered1 (ord:intervals) =53(forall i, j. Int.(0 <= i < j < List.length ord) ->54let (_,b) = List.nth i ord in55let (a,_) = List.nth j ord in56b < a)5758predicate ordered2 (ord:intervals) =59(forall i. Int.(0 <= i < List.length ord) ->60let (a,b) = List.nth i ord in61a <= b)626364predicate ordered (ord:intervals) =65ordered1 ord /\ ordered2 ord66Valid (27ms) (colibri2)67lemma G1: forall i:int. forall x:'a. forall l:List.t 'a.68Int.(0 <= i < List.length l) ->69List.nth (i+1) (List.Cons x l) = List.nth i l70Valid (46ms) (cvc5)71let lemma gg1 (x:(t,t)) (ord:intervals)72requires { ordered2 (List.Cons x ord) }73ensures { ordered2 ord } =74let lemma f (i:int)75requires { Int.(0 <= i < List.length ord) }76ensures { let (a,b) = List.nth i ord in77a <= b }78= ()79in80()8182Valid (64ms) (cvc5)83let lemma gg2 (x:(t,t)) (ord:intervals)84requires { ordered1 (List.Cons x ord) }85ensures { ordered1 ord } =86let lemma f (i j:int)87requires { Int.(0 <= i < j < List.length ord) }88ensures { let (_,b) = List.nth i ord in89let (a,_) = List.nth j ord in90b < a }91= ()92in93()9495type u = {96u : intervals ;97nan : bool;98}99invariant { nan = true \/ u <> List.Nil }100invariant { ordered u } Valid (24ms) (colibri2)101by { nan = true; u = List.Nil }102103predicate mem (x:t) (l:List.t ( t, t)) = exists i.104Int.(0 <= i < List.length l) /\105let (a,b) = List.nth i l in106a <= x <= b107Valid (28ms) (colibri2)108let ghost function index (x:t) (l:List.t ( t, t)) : int109requires { mem x l }110ensures { Int.(0 <= result < List.length l) }111ensures { let (a,b) = List.nth result l in112a <= x <= b } =113any int ensures {114Int.(0 <= result < List.length l) /\115let (a,b) = List.nth result l in116a <= x <= b }117118end119Valid (35ms) (colibri2)120type t 'a = {121is_top : 'a -> bool;122nan : 'a;123steps : array F.t;124values : array 'a;125join : 'a -> 'a -> 'a;126ghost inc : 'a -> 'a -> bool;127} invariant { steps.length + 1 = values.length }128invariant { forall i j. Int.(0 <= i < j < steps.length) ->129F.(steps[i] < steps[j]) }130invariant { forall x y:'a. inc x (join x y) }131invariant { forall x y:'a. inc y (join x y) }132invariant { forall x:'a. inc x x }133invariant { forall x y z:'a. inc x y -> inc y z -> inc x z }134invariant { forall x y:'a. is_top y -> inc x y }135by (let x = any 'a ensures { result = result } in136let f = any F.t ensures { result = result } in137{ is_top = (fun _ -> true); nan = x; steps = Array.make 0 f;138values = Array.make 1 x; join = (fun x _ -> x); inc = (fun _ _ -> true) })139Valid (44ms) (colibri2)140let ghost function find (x: t 'a) (f:F.t) : int =141ensures { Int.(0 <= result-1 < Array.length x.steps) -> F.(x.steps[result-1] < f )}142ensures { Int.(0 <= result < Array.length x.steps) -> F.(f <= x.steps[result] )}143ensures { Int.(0 <= result < Array.length x.steps + 1) }144let rec aux i : int145variant { Array.length x.steps - i }146requires { Int.(0 <= i <= Array.length x.steps) }147requires { Int.(1 <= i -> F.(x.steps[i-1] < f)) }148ensures { Int.(0 <= result-1 < Array.length x.steps) -> F.(x.steps[result-1] < f )}149ensures { Int.(0 <= result < Array.length x.steps) -> F.(f <= x.steps[result] )}150ensures { Int.(0 <= result < Array.length x.steps + 1) }151=152if Int.(Array.length x.steps <= i) then i153else if F.(<=) f x.steps[i] then i154else aux (i+1)155in156aux 0157158function get_value (x: t 'a) (f:F.t) : 'a = x.values[find x f]159Valid (169ms) (colibri2 57) (cvc5 3) (split_vc) (depth 1)160let fold (t:t 'a) (l:FI.u) : 'a161ensures { l.FI.nan -> t.inc t.nan result }162ensures { forall x. FI.mem x l.FI.u -> t.inc (get_value t x) result }163=164
r is steps.(i–1) and s is steps.(i)
let rec r_lt_a (t:t 'a) (i:int) (v:'a) (l:FI.intervals) (ghost j:int)166requires { Int.(0 <= i - 1 < Array.length t.steps) -> match l with167| List.Nil -> true168| List.Cons (a,_) _ -> F.(t.steps[i-1] < a) end }169requires { Int.(0 <= i < Array.length t.values) }170requires { FI.ordered l }171ensures { t.inc v result }172ensures { forall x. FI.mem x l -> Int.(i <= find t x) -> t.inc (get_value t x) result }173variant { Array.length t.steps - i,l,j }174=175let _ = j in176match l with177| List.Nil -> v178| List.Cons (a,_) _ ->179if Array.length t.steps <= i then180t.join v t.values[i]181else182if F.lt t.steps[i] a then begin183assert { forall x. F.(a <= x) -> Int.(i+1 <= find t x) };184r_lt_a t (i+1) v l 1185end else186let v = t.join v t.values[i] in187if t.is_top v then v else r_ge_a t (i + 1) v l 1188end189with r_ge_a (t:t 'a) (i:int) (v:'a) (l:FI.intervals) (ghost j:int)190requires { Int.(0 <= i - 1 < Array.length t.steps) -> match l with191| List.Nil -> true192| List.Cons (a,_) _ -> F.(a <= t.steps[i-1]) end }193requires { Int.(1 <= i < Array.length t.values) }194requires { FI.ordered l }195ensures { t.inc v result }196ensures { forall x. FI.mem x l -> Int.(i <= find t x) -> t.inc (get_value t x) result }197variant { Array.length t.steps - i,l,j }198=199let _ = j in200match l with201| List.Nil -> v202| List.Cons (_,b) l' ->203if not (F.lt t.steps[i-1] b) then begin204assert { forall x. F.(x <= b) -> Int.(find t x < i) };205r_unk t i v l' 1206end else207let v = t.join v t.values[i] in208if t.is_top v then v else209if Array.length t.steps <= i then210v211else212r_ge_a t (i + 1) v l 1213end214with r_unk (t:t 'a) (i:int) (v:'a) (l:FI.intervals) (ghost j:int)215requires { Int.(1 <= i < Array.length t.values) }216requires { FI.ordered l }217requires { j = 1 }218ensures { t.inc v result }219ensures { forall x. FI.mem x l -> Int.(i <= find t x) -> t.inc (get_value t x) result }220variant { Array.length t.steps - i,l,j }221=222match l with223| List.Nil -> v224| List.Cons (a,_) _ ->225if F.lt t.steps[i-1] a then begin226r_lt_a t i v l 0227end else228r_ge_a t i v l 0229end230in231let rec find_first (t:t 'a) (i:int) (l:FI.intervals)232requires { Int.(0 <= i - 1 < Array.length t.steps) -> match l with233| List.Nil -> true234| List.Cons (a,_) _ -> F.(t.steps[i-1] < a) end }235requires { Int.(0 <= i < Array.length t.values) }236requires { FI.ordered l }237requires { l <> List.Nil }238ensures { forall x. FI.mem x l -> Int.(i <= find t x) -> t.inc (get_value t x) result }239variant { Array.length t.steps - i }240=241match l with242| List.Nil -> absurd243| List.Cons (a,_) _ ->244if Array.length t.steps <= i then245t.values[i]246else247if F.lt t.steps[i] a then begin248find_first t (i+1) l249end else250let v = t.values[i] in251if t.is_top v then v else r_ge_a t (i + 1) v l 1252end253in254if l.FI.nan then255r_lt_a t 0 t.nan l.FI.u 1256else257find_first t 0 l.FI.u258259exception Defensive_assert260Valid (151ms) (cvc5)261let mk_partly_defensive [@requires:trusted "the caller in fp_interval.ml gives a join and is_top that fit an order inc; inc is ghost, so it cannot be tested"] vis_top (vnan:'a) vsteps vvalues vjoin (ghost vinc)262requires { forall x y:'a. vinc x (vjoin x y) }263requires { forall x y:'a. vinc y (vjoin x y) }264requires { forall x:'a. vinc x x }265requires { forall x y z:'a. vinc x y -> vinc y z -> vinc x z }266requires { forall x y:'a. vis_top y -> vinc x y }267raises { Defensive_assert ->268not (vsteps.length + 1 = vvalues.length) \/269(exists i. Int.(0 <= i < vsteps.length) /\270not F.(vsteps[i] < vsteps[i+1])) }271=272if vsteps.length + 1 <> vvalues.length then raise Defensive_assert;273for k=0 to vsteps.length-2 do274invariant { forall i j. Int.(0 <= i < j <= k) ->275F.(vsteps[i] < vsteps[j]) }276if not (F.lt vsteps[k] vsteps[k+1]) then raise Defensive_assert;277done;278{ is_top = vis_top; nan = vnan; steps = vsteps; values = vvalues; join = vjoin;279inc = vinc }280281end282283end284