library colibrilib.sign_product — module SAssocAssociation lists from atoms to powers, sorted by atom, and their value
module SAssoc9use int.Int10use mach.int.Int6311use real.RealInfix12use list.List13use list.Mem14use option.Option15use colibrilib.ring.Atom16
The power of a sign
type power = Odd | Even | OddNonZero1920type binding = (Atom.t, power)2122function assoc (k:Atom.t) (l:list binding) : option power =23match l with24| Nil -> None25| Cons (k', v) r -> if k = k' then Some v else assoc k r26end2728predicate has (k:Atom.t) (l:list binding) = assoc k l <> None29
every key of l is above k
predicate above (k:Atom.t) (l:list binding) = forall k'. has k' l -> lt k k'3233predicate sorted (l:list binding) =34match l with35| Nil -> true36| Cons (k, _) r -> above k r /\ sorted r37end38
The sign of a real
function sgn (x:real) : real =41if 0.0 <. x then 1.0 else if x <. 0.0 then -. 1.0 else 0.042
0, 1 or –1
predicate unit3 (s:real) = s = 0.0 \/ s = 1.0 \/ s = -. 1.045
The power v of the sign s
function fac (s:real) (v:power) : real =48match v with Even -> s *. s | Odd | OddNonZero -> s end4950function ofac (s:real) (o:option power) : real =51match o with None -> 1.0 | Some v -> fac s v end52
The product of the powers of the signs of l
function evs (env: Atom.t -> real) (l:list binding) : real =55match l with56| Nil -> 1.057| Cons (k, v) r -> fac (sgn (env k)) v *. evs env r58end59
The nodes OddNonZero of l are not zero
predicate lvalid (env: Atom.t -> real) (l:list binding) =62forall k. assoc k l = Some OddNonZero -> env k <> 0.063
The product of two powers of the same sign (None: 1)
let function mulp (o1 o2:option power) : option power =66match o1, o2 with67| None, o -> o68| o, None -> o69| Some Odd, Some Odd -> Some Even70| Some Even, Some v -> Some v71| Some v, Some Even -> Some v72| Some _, Some _ -> None73end74
The closure of SPT.merge
let function mulk (_k:Atom.t) (o1 o2:option power) : option power =77mulp o1 o278Valid (20ms) (colibri2)79let ghost sgn_unit3 (x:real) : unit80ensures { unit3 (sgn x) }81ensures { sgn x = 0.0 <-> x = 0.0 }82= ()83Valid (331ms) (colibri2)84let ghost mulp_fac (s:real) (o1 o2:option power) : unit85requires { unit3 s }86requires { o1 = Some OddNonZero \/ o2 = Some OddNonZero -> s <> 0.0 }87ensures { ofac s (mulp o1 o2) = ofac s o1 *. ofac s o2 }88= ()89Valid (110ms) (colibri2)90let rec ghost evs_unit3 (env: Atom.t -> real) (l:list binding) : unit91ensures { unit3 (evs env l) }92ensures { evs env l = 0.0 <-> exists k. has k l /\ env k = 0.0 }93variant { l }94= match l with95| Nil -> ()96| Cons (k, _) r -> evs_unit3 env r; sgn_unit3 (env k)97end98
Two sorted lists with the same bindings are equal
Valid (403ms) (colibri2)let rec ghost ext (l1 l2:list binding) : unit101requires { sorted l1 /\ sorted l2 }102requires { forall k. assoc k l1 = assoc k l2 }103ensures { l1 = l2 }104variant { l1 }105= match l1, l2 with106| Nil, Nil -> ()107| Cons (k1, _) _, Nil -> assert { has k1 l1 }108| Nil, Cons (k2, _) _ -> assert { has k2 l2 }109| Cons (k1, v1) r1, Cons (k2, v2) r2 ->110assert { has k1 l2 };111assert { has k2 l1 };112if pure { k1 <> k2 } then begin113assert { lt k1 k2 /\ lt k2 k1 };114Atom.lt_trans k1 k2 k1;115absurd116end;117assert { v1 = v2 by assoc k1 l1 = assoc k1 l2 };118let lemma pw (k:Atom.t) : unit119ensures { assoc k r1 = assoc k r2 }120= if pure { k = k1 } then begin121assert { not (has k r1) /\ not (has k r2) }122end else begin123assert { assoc k l2 = assoc k r2 }124end in125ext r1 r2126end127Valid (15ms) (colibri2)128let ghost assoc3 (a b c:real) : unit129ensures { a *. (b *. c) = (a *. b) *. c }130= ()131Valid (14ms) (colibri2)132let ghost comm3 (a b c:real) : unit133ensures { a *. (b *. c) = b *. (a *. c) }134= ()135
The product of two lists
Valid (709ms) (colibri2 34) (split_vc) (depth 1)let rec ghost lmul (l1 l2:list binding) : list binding138requires { sorted l1 /\ sorted l2 }139ensures { sorted result }140ensures { forall k. has k result -> has k l1 \/ has k l2 }141ensures { forall k. assoc k result = mulp (assoc k l1) (assoc k l2) }142ensures { forall env. lvalid env l1 -> lvalid env l2 ->143evs env result = evs env l1 *. evs env l2 /\ lvalid env result }144variant { l1, l2 }145= match l1, l2 with146| Nil, _ -> l2147| _, Nil -> l1148| Cons (k1, a) r1, Cons (k2, b) r2 ->149let c = Atom.compare k1 k2 in150if c < 0 then begin151let t = lmul r1 l2 in152let res = Cons (k1, a) t in153assert { not (has k1 l2) };154let lemma ab (k:Atom.t) : unit155requires { has k t }156ensures { lt k1 k }157= if pure { has k l2 /\ k <> k2 } then Atom.lt_trans k1 k2 k in158let lemma pw (k:Atom.t) : unit159ensures { assoc k res = mulp (assoc k l1) (assoc k l2) }160= if pure { k = k1 } then assert { not (has k1 t) } in161let lemma ev (env: Atom.t -> real) : unit162requires { lvalid env l1 /\ lvalid env l2 }163ensures { evs env res = evs env l1 *. evs env l2 }164= assert { lvalid env r1165by forall k. has k r1 -> assoc k r1 = assoc k l1 };166assoc3 (fac (sgn (env k1)) a) (evs env r1) (evs env l2) in167res168end else if c > 0 then begin169let t = lmul l1 r2 in170let res = Cons (k2, b) t in171assert { not (has k2 l1) };172let lemma ab (k:Atom.t) : unit173requires { has k t }174ensures { lt k2 k }175= if pure { has k l1 /\ k <> k1 } then Atom.lt_trans k2 k1 k in176let lemma pw (k:Atom.t) : unit177ensures { assoc k res = mulp (assoc k l1) (assoc k l2) }178= if pure { k = k2 } then assert { not (has k2 t) } in179let lemma ev (env: Atom.t -> real) : unit180requires { lvalid env l1 /\ lvalid env l2 }181ensures { evs env res = evs env l1 *. evs env l2 }182= assert { lvalid env r2183by forall k. has k r2 -> assoc k r2 = assoc k l2 };184comm3 (fac (sgn (env k2)) b) (evs env l1) (evs env r2) in185res186end else begin187let t = lmul r1 r2 in188let res = match mulp (Some a) (Some b) with189| None -> t190| Some v -> Cons (k1, v) t191end in192let lemma ab (k:Atom.t) : unit193requires { has k t }194ensures { lt k1 k }195= () in196let lemma pw (k:Atom.t) : unit197ensures { assoc k res = mulp (assoc k l1) (assoc k l2) }198= if pure { k = k1 } then assert { not (has k1 t) } in199let lemma ev (env: Atom.t -> real) : unit200requires { lvalid env l1 /\ lvalid env l2 }201ensures { evs env res = evs env l1 *. evs env l2 }202= assert { lvalid env r1203by forall k. has k r1 -> assoc k r1 = assoc k l1 };204assert { lvalid env r2205by forall k. has k r2 -> assoc k r2 = assoc k l2 };206sgn_unit3 (env k1);207mulp_fac (sgn (env k1)) (Some a) (Some b) in208res209end210end211
l without x
Valid (121ms) (colibri2)let rec ghost lrem (x:Atom.t) (l:list binding) : list binding214requires { sorted l }215ensures { sorted result }216ensures { forall k. assoc k result = if k = x then None else assoc k l }217ensures { forall env. evs env l = ofac (sgn (env x)) (assoc x l) *. evs env result }218variant { l }219= match l with220| Nil -> Nil221| Cons (k, v) r ->222if Atom.equal k x then begin223assert { not (has x r) };224r225end else begin226let t = lrem x r in227let res = Cons (k, v) t in228assert { forall k'. has k' t -> has k' r };229res230end231end232
Odd becomes OddNonZero
let function liftp (v:power) : power =235match v with Odd -> OddNonZero | v -> v end236237function omap (o:option power) : option power =238match o with None -> None | Some v -> Some (liftp v) end239
l with its Odd powers made OddNonZero: the same value
Valid (334ms) (colibri2)let rec ghost llift (l:list binding) : list binding242requires { sorted l }243ensures { sorted result }244ensures { forall k. assoc k result = omap (assoc k l) }245ensures { forall env. evs env result = evs env l }246variant { l }247= match l with248| Nil -> Nil249| Cons (k, v) r ->250let t = llift r in251assert { forall k'. has k' t -> has k' r };252Cons (k, liftp v) t253end254
The atoms of l
Valid (32ms) (colibri2)let rec keys (l:list binding) : list Atom.t257ensures { forall k. Mem.mem k result <-> has k l }258variant { l }259= match l with260| Nil -> Nil261| Cons (k, _) r -> Cons k (keys r)262end263end264