library colibrilib.models — module SortedMapThe maps of polynome.PT and product.PT: the sorted lists of bindings, for any value type, with their length as a Peano number (mach.peano): the length of a map is bounded by the number of steps of the program that built it, so cardinal can return an int63 (Peano.to_int63 is partial).
module SortedMap35use int.Int36use mach.int.Int6337use mach.peano.Peano as P38use mach.peano.Int63 as PI39use list.List40use list.Length41use option.Option42use colibrilib.ring.Atom4344type value4546type binding = (Atom.t, value)4748function assoc (k:Atom.t) (l:list binding) : option value =49match l with50| Nil -> None51| Cons (k', v) r -> if k = k' then Some v else assoc k r52end5354predicate has (k:Atom.t) (l:list binding) = assoc k l <> None5556predicate above (k:Atom.t) (l:list binding) = forall k'. has k' l -> lt k k'5758predicate sorted (l:list binding) =59match l with60| Nil -> true61| Cons (k, _) r -> above k r /\ sorted r62end6364type t = { l: list binding; n: P.t }65invariant { sorted l /\ n.P.v = length l } Valid (17ms) (colibri2)66by { l = Nil; n = P.zero }6768function bindings (m:t) : list binding = m.l69Valid (17ms) (colibri2)70let ghost above_trans (k1 k2:Atom.t) (l:list binding) : unit71requires { lt k1 k2 }72requires { above k2 l }73ensures { above k1 l }74= assert { forall k. has k l -> lt k1 k by lt k2 k }75Valid (18ms) (colibri2)76let ghost above_not_has (k:Atom.t) (l:list binding) : unit77requires { above k l }78ensures { assoc k l = None }79= assert { not (lt k k) }80
Cons (k, v) t if o = Some v, else t, and its length
Valid (25ms) (colibri2)let cons_opt (k:Atom.t) (o:option value) (t:list binding) (n:P.t)83: (list binding, P.t)84requires { sorted t /\ above k t }85requires { n.P.v = length t }86returns { (r, rn) ->87sorted r /\ rn.P.v = length r /\88assoc k r = o /\89(forall k'. k' <> k -> assoc k' r = assoc k' t) /\90(forall k'. has k' r -> k' = k \/ has k' t) }91= above_not_has k t;92match o with93| None -> t, n94| Some v -> Cons (k, v) t, P.succ n95end96Valid (13ms) (colibri2)97let empty () : t98ensures { bindings result = Nil }99= { l = Nil; n = P.zero }100Valid (13ms) (colibri2)101let is_empty (m:t) : bool102ensures { result <-> bindings m = Nil }103= match m.l with Nil -> true | _ -> false end104Valid (13ms) (colibri2)105let singleton (k:Atom.t) (v:value) : t106ensures { bindings result = Cons (k, v) Nil }107= { l = Cons (k, v) Nil; n = P.one }108Valid (15ms) (colibri2)109let rec find (k:Atom.t) (l:list binding) : option value110ensures { result = assoc k l }111variant { l }112= match l with113| Nil -> None114| Cons (k', v) r -> if Atom.equal k k' then Some v else find k r115end116Valid (13ms) (colibri2)117let find_opt (k:Atom.t) (m:t) : option value118ensures { result = assoc k (bindings m) }119= find k m.l120Valid (58ms) (colibri2)121let rec rem (k:Atom.t) (l:list binding) : list binding122requires { sorted l }123ensures { sorted result }124ensures { forall k'. assoc k' result = if k' = k then None else assoc k' l }125ensures { forall k'. has k' result -> has k' l }126ensures { length result = if has k l then length l - 1 else length l }127variant { l }128= match l with129| Nil -> Nil130| Cons (k', v) r ->131if Atom.equal k k' then begin above_not_has k r; r end132else Cons (k', v) (rem k r)133end134Valid (20ms) (colibri2)135let remove (k:Atom.t) (m:t) : t136ensures { forall k'. assoc k' (bindings result)137= if k' = k then None else assoc k' (bindings m) }138= match find k m.l with139| None -> { l = rem k m.l; n = m.n }140| Some _ -> { l = rem k m.l; n = P.pred m.n }141end142Valid (12ms) (colibri2)143let cardinal (m:t) : int144ensures { result = length (bindings m) }145= P.to_int m.n146Valid (22ms) (colibri2)147let partial cardinal63 (m:t) : int63148ensures { to_int result = length (bindings m) }149= PI.to_int63 m.n150Valid (11ms) (colibri2)151let to_list (m:t) : list binding152ensures { result = bindings m }153= m.l154Valid (13ms) (colibri2)155let some_binding (m:t) : (Atom.t, value)156requires { bindings m <> Nil }157returns { (k, v) -> assoc k (bindings m) = Some v }158= match m.l with159| Nil -> absurd160| Cons (k, v) _ -> (k, v)161end162Valid (1.3s) (colibri2 31) (cvc5) (split_vc) (depth 1)163let rec mrg (f: Atom.t -> option value -> option value -> option value)164(l1 l2:list binding) : (list binding, P.t)165requires { sorted l1 /\ sorted l2 }166requires { forall k. f k None None = None }167returns { (r, rn) ->168sorted r /\ rn.P.v = length r /\169(forall k. has k r -> has k l1 \/ has k l2) /\170(forall k. assoc k r = f k (assoc k l1) (assoc k l2)) }171variant { l1, l2 }172= match l1, l2 with173| Nil, Nil -> Nil, P.zero174| Cons (k, a) r, Nil ->175let t, n = mrg f r Nil in cons_opt k (f k (Some a) None) t n176| Nil, Cons (k, b) r ->177let t, n = mrg f Nil r in cons_opt k (f k None (Some b)) t n178| Cons (k1, a) r1, Cons (k2, b) r2 ->179let c = Atom.compare k1 k2 in180if c < 0 then begin181above_trans k1 k2 r2;182above_not_has k1 l2;183let t, n = mrg f r1 l2 in cons_opt k1 (f k1 (Some a) None) t n184end else if c > 0 then begin185above_trans k2 k1 r1;186above_not_has k2 l1;187let t, n = mrg f l1 r2 in cons_opt k2 (f k2 None (Some b)) t n188end else begin189let t, n = mrg f r1 r2 in cons_opt k1 (f k1 (Some a) (Some b)) t n190end191end192Valid (15ms) (colibri2)193let merge (f: Atom.t -> option value -> option value -> option value) (m1 m2:t) : t194requires { forall k. f k None None = None }195ensures { forall k. assoc k (bindings result)196= f k (assoc k (bindings m1)) (assoc k (bindings m2)) }197= let r, n = mrg f m1.l m2.l in { l = r; n = n }198Valid (144ms) (cvc5)199let rec ins (k:Atom.t) (v:value) (l:list binding) : list binding200requires { sorted l }201ensures { sorted result }202ensures { forall k'. assoc k' result = if k' = k then Some v else assoc k' l }203ensures { forall k'. has k' result -> k' = k \/ has k' l }204ensures { length result = if has k l then length l else length l + 1 }205variant { l }206= match l with207| Nil -> Cons (k, v) Nil208| Cons (k', w) r ->209let c = Atom.compare k k' in210if c < 0 then begin above_trans k k' r; above_not_has k l; Cons (k, v) l end211else if c = 0 then begin above_not_has k r; Cons (k, v) r end212else Cons (k', w) (ins k v r)213end214Valid (21ms) (colibri2)215let update (k:Atom.t) (f: option value -> option value) (m:t) : t216ensures { forall k'. assoc k' (bindings result)217= if k' = k then f (assoc k (bindings m)) else assoc k' (bindings m) }218= let o = find k m.l in219match f o, o with220| None, None -> m221| None, Some _ -> { l = rem k m.l; n = P.pred m.n }222| Some v, None -> { l = ins k v m.l; n = P.succ m.n }223| Some v, Some _ -> { l = ins k v m.l; n = m.n }224end225Valid (325ms) (colibri2)226let rec mp (f: value -> value) (l:list binding) : list binding227requires { sorted l }228ensures { sorted result }229ensures { length result = length l }230ensures { forall k. has k result <-> has k l }231ensures { forall k. assoc k result = match assoc k l with232| None -> None | Some v -> Some (f v) end }233variant { l }234= match l with235| Nil -> Nil236| Cons (k, v) r -> Cons (k, f v) (mp f r)237end238Valid (18ms) (colibri2)239let map (f: value -> value) (m:t) : t240ensures { forall k. assoc k (bindings result) = match assoc k (bindings m) with241| None -> None | Some v -> Some (f v) end }242= { l = mp f m.l; n = m.n }243Valid (72ms) (colibri2)244let rec flt (f: Atom.t -> bool) (l:list binding) : (list binding, P.t)245requires { sorted l }246returns { (r, rn) ->247sorted r /\ rn.P.v = length r /\248(forall k. has k r -> has k l) /\249(forall k. assoc k r = if f k then assoc k l else None) }250variant { l }251= match l with252| Nil -> Nil, P.zero253| Cons (k, v) r ->254above_not_has k r;255let t, n = flt f r in256if f k then Cons (k, v) t, P.succ n else t, n257end258Valid (17ms) (colibri2)259let filter (f: Atom.t -> bool) (m:t) : t260ensures { forall k. assoc k (bindings result)261= if f k then assoc k (bindings m) else None }262= let r, n = flt f m.l in { l = r; n = n }263end264