library colibrilib.zinterval — module Zimodule Zi9use int.Int10use option.Option11
lo <= z <= hi, None an infinite bound
type t = { lo: option int; hi: option int }1415predicate mem_lo (z: int) (l: option int) =16match l with None -> true | Some k -> k <= z end17predicate mem_hi (z: int) (h: option int) =18match h with None -> true | Some k -> z <= k end1920predicate mem (z: int) (i: t) = mem_lo z i.lo /\ mem_hi z i.hi2122let function mk (lo hi: option int) : t = { lo = lo; hi = hi }23
All the integers
let constant top : t = { lo = None; hi = None }26Valid (16ms) (colibri2)27let ghost mem_top (z: int) : unit28ensures { mem z top }29= ()30
let function max_lo (a b: option int) : option int =34match a, b with35| None, x | x, None -> x36| Some x, Some y -> Some (if x <= y then y else x)37end3839let function min_hi (a b: option int) : option int =40match a, b with41| None, x | x, None -> x42| Some x, Some y -> Some (if x <= y then x else y)43end4445let function inter (a b: t) : t = { lo = max_lo a.lo b.lo; hi = min_hi a.hi b.hi }46Valid (63ms) (colibri2)47let ghost mem_inter (z: int) (a b: t) : unit48ensures { mem z (inter a b) <-> mem z a /\ mem z b }49= ()50
let function neg_o (o: option int) : option int =54match o with None -> None | Some k -> Some (- k) end5556let function rev (a: t) : t = { lo = neg_o a.hi; hi = neg_o a.lo }57Valid (30ms) (colibri2)58let ghost mem_rev (z: int) (a: t) : unit59ensures { mem (- z) (rev a) <-> mem z a }60= ()61Valid (15ms) (colibri2)62let ghost rev_rev (a: t) : unit63ensures { rev (rev a) = a }64= match a.lo with None -> () | Some _ -> () end;65match a.hi with None -> () | Some _ -> () end66
let function add_o (a b: option int) : option int =70match a, b with71| Some x, Some y -> Some (x + y)72| _ -> None73end7475let function add (a b: t) : t = { lo = add_o a.lo b.lo; hi = add_o a.hi b.hi }76Valid (33ms) (colibri2)77let ghost mem_add (x y: int) (a b: t) : unit78requires { mem x a /\ mem y b }79ensures { mem (x + y) (add a b) }80= ()81
let function is_empty (a: t) : bool =85match a.lo, a.hi with86| Some l, Some h -> h < l87| _ -> false88end89Valid (29ms) (colibri2)90let ghost is_empty_spec (a: t) : unit91ensures { is_empty a <-> forall z. not mem z a }92= match a.lo, a.hi with93| Some l, Some _ -> assert { not is_empty a -> mem l a }94| Some l, None -> assert { mem l a }95| None, Some h -> assert { mem h a }96| None, None -> assert { mem 0 a }97end98
The bound l is implied by l': every integer above l' is above l
let function le_lo (l l': option int) : bool =102match l, l' with103| None, _ -> true104| Some _, None -> false105| Some x, Some y -> x <= y106end107108let function ge_hi (h h': option int) : bool =109match h, h' with110| None, _ -> true111| Some _, None -> false112| Some x, Some y -> y <= x113end114
a is included in b
let function incl (a b: t) : bool =117is_empty a || (le_lo b.lo a.lo && ge_hi b.hi a.hi)118
A member of a non–empty a at most k, when the lower bound of a is at most k
Valid (18ms) (colibri2)let ghost low_wit (a: t) (k: int) : int122requires { not is_empty a /\ mem_lo k a.lo }123ensures { mem result a /\ result <= k }124= match a.hi with125| Some h -> if h < k then (is_empty_spec a; h) else k126| None -> k127end128Valid (13ms) (colibri2)129let ghost high_wit (a: t) (k: int) : int130requires { not is_empty a /\ mem_hi k a.hi }131ensures { mem result a /\ k <= result }132= match a.lo with133| Some l -> if k < l then l else k134| None -> k135end136Valid (30ms) (colibri2 9) (cvc5) (split_vc 4) (depth 3)137let ghost incl_spec (a b: t) : unit138ensures { incl a b <-> forall z. mem z a -> mem z b }139= {proof…}140is_empty_spec a;141if not is_empty a && not (le_lo b.lo a.lo) then begin142match b.lo with143| Some l -> let w = low_wit a (l - 1) in assert { mem w a /\ not mem w b }144| None -> absurd145end146end;147if not is_empty a && not (ge_hi b.hi a.hi) then begin148match b.hi with149| Some h -> let w = high_wit a (h + 1) in assert { mem w a /\ not mem w b }150| None -> absurd151end152end153{qed}154155let function eq_o (a b: option int) : bool =156match a, b with157| None, None -> true158| Some x, Some y -> x = y159| _ -> false160end161162let function equal (a b: t) : bool = eq_o a.lo b.lo && eq_o a.hi b.hi163Valid (16ms) (colibri2)164let ghost equal_spec (a b: t) : unit165ensures { equal a b <-> a = b }166= ()167end168