library colibrilib.q_model — module QModelA model of the interface q.Q_intf: the rationals as normalized fractions of integers. The clone at the end checks that the implemented functions meet their specifications, so the axioms of q.Q_intf (its val functions) are consistent. The fractions in lowest terms are unique (equal_is_eq), which is the axiom of zarith.Q. All the functions of q.Q_intf are implemented, except the divisibility operations (is_zero, divisible, gcd, gcdext, lcm, divexact, to_z), which the former q.Intf did not have, and the conversions with Zarith (to_zarith, of_zarith).
It is a model, not extracted: colibri2 uses Std.Q and Std.A.
module QModel12use int.Int13use int.Abs14use int.EuclideanDivision as E15use number.Divisibility16use number.Gcd17use number.Coprime18use real.RealInfix19use real.FromInt20use real.Abs as RA21use real.Truncate as T22use mach.int.Int6323use colibrilib.q.Ord as Ord24
num / den, in lowest terms
type t = { num: int; den: int } Valid (29ms) (colibri2)27invariant { 0 < den /\ gcd num den = 1 }28by { num = 0; den = 1 }2930function real (q:t) : real = from_int q.num /. from_int q.den31
The (non negative) greatest common divisor, by Euclid
Valid (33ms) (colibri2)let rec euclid (a b:int) : int34requires { 0 <= a /\ 0 <= b }35ensures { result = gcd a b }36variant { b }37= if b = 0 then a38else begin39assert { gcd a b = gcd b (E.mod a b) };40euclid b (E.mod a b)41end42Valid (28ms) (colibri2)43let ghost cross (n1 d1 n2 d2:int) : unit44requires { d1 <> 0 /\ d2 <> 0 }45ensures { from_int n1 /. from_int d1 = from_int n2 /. from_int d246<-> n1 * d2 = n2 * d1 }47= let x1 = from_int n1 in let y1 = from_int d1 in48let x2 = from_int n2 in let y2 = from_int d2 in49assert { y1 <> 0. /\ y2 <> 0. };50assert { x1 /. y1 = x2 /. y2 <-> x1 *. y2 = x2 *. y151by x1 /. y1 *. (y1 *. y2) = x1 *. y252/\ x2 /. y2 *. (y1 *. y2) = x2 *. y1 };53assert { from_int (n1 * d2) = x1 *. y2 };54assert { from_int (n2 * d1) = x2 *. y1 }55Valid (23ms) (cvc5)56let ghost scale (g a b:int) : unit57ensures { (g * a) * b = a * (g * b) }58ensures { (g * a) * (- b) = (- a) * (g * b) }59= ()60
n / d in lowest terms
Valid (155ms) (colibri2 13) (cvc5 2) (split_vc 2) (depth 2)let make (n d:int) : t63requires { d <> 0 }64ensures { real result = from_int n /. from_int d }65= let g = euclid (abs n) (abs d) in66assert { g = gcd n d };67assert { 0 < g };68let a = E.div n g in69let b = E.div d g in70assert { n = g * a /\ d = g * b };71assert { gcd n d = g * gcd a b };72assert { gcd a b = 1 };73if b < 0 then begin74assert { gcd (-a) (-b) = 175by gcd (-a) (-b) = gcd a (-b) /\ gcd (-b) a = gcd b a };76scale g a b;77cross n d (-a) (-b);78{ num = -a; den = -b }79end else begin80scale g a b;81cross n d a b;82{ num = a; den = b }83end8485predicate equal (a b:t) = (real a = real b)86
The fractions in lowest terms are unique
Valid (88ms) (colibri2 13) (split_vc) (depth 1)let lemma equal_is_eq (a b:t) : unit89requires { equal a b }90ensures { a = b }91= cross a.num a.den b.num b.den;92assert { divides a.den (a.num * b.den) };93assert { coprime a.den a.num by gcd a.den a.num = gcd a.num a.den };94assert { divides a.den b.den };95assert { divides b.den (b.num * a.den) };96assert { coprime b.den b.num by gcd b.den b.num = gcd b.num b.den };97assert { divides b.den a.den };98assert { a.den = b.den \/ a.den = - b.den };99assert { a.den = b.den };100assert { (a.num - b.num) * a.den = 0 };101assert { a.num = b.num };102assert { t'eq a b }103Valid (35ms) (colibri2)104let eq (a b:t) : bool105ensures { equal a b = result }106= if a.num = b.num && a.den = b.den then true107else begin108if pure { equal a b } then equal_is_eq a b;109false110end111Valid (47ms) (colibri2)112let ghost le_cross (a b:t) : unit113ensures { real a <=. real b <-> a.num * b.den <= b.num * a.den }114ensures { real a <. real b <-> a.num * b.den < b.num * a.den }115= assert { real a = from_int (a.num * b.den) /. from_int (a.den * b.den) };116assert { real b = from_int (b.num * a.den) /. from_int (a.den * b.den) };117assert { 0. <. from_int (a.den * b.den) }118Valid (27ms) (colibri2)119let le (a b:t) : bool120ensures { result = (real a <=. real b) }121= le_cross a b; a.num * b.den <= b.num * a.den122Valid (31ms) (colibri2)123let lt (a b:t) : bool124ensures { result = (real a <. real b) }125= le_cross a b; a.num * b.den < b.num * a.den126Valid (36ms) (colibri2)127let compare (a b:t) : Ord.t128ensures { match result with129| Ord.Eq -> equal a b130| Ord.Lt -> real a <. real b131| Ord.Gt -> real b <. real a132end }133= if lt a b then Ord.Lt else if lt b a then Ord.Gt else Ord.Eq134Valid (43ms) (colibri2)135let function add (a b:t) : t136ensures { real a +. real b = real result }137= let r = make (a.num * b.den + b.num * a.den) (a.den * b.den) in138assert { from_int (a.num * b.den + b.num * a.den) /. from_int (a.den * b.den)139= real a +. real b };140r141Valid (41ms) (colibri2)142let function sub (a b:t) : t143ensures { real a -. real b = real result }144= let r = make (a.num * b.den - b.num * a.den) (a.den * b.den) in145assert { from_int (a.num * b.den - b.num * a.den) /. from_int (a.den * b.den)146= real a -. real b };147r148Valid (45ms) (colibri2)149let function mul (a b:t) : t150ensures { real a *. real b = real result }151= let r = make (a.num * b.num) (a.den * b.den) in152assert { from_int (a.num * b.num) /. from_int (a.den * b.den)153= real a *. real b };154r155Valid (52ms) (colibri2)156let function div (a b:t) : t157requires { real b <> 0. }158ensures { real a /. real b = real result }159= assert { b.num <> 0 };160let r = make (a.num * b.den) (a.den * b.num) in161assert { from_int (a.num * b.den) /. from_int (a.den * b.num)162= real a /. real b };163r164Valid (52ms) (colibri2)165let qabs (a:t) : t166ensures { real result = RA.abs (real a) }167= if a.num < 0 then begin168assert { gcd (- a.num) a.den = gcd a.num a.den };169assert { from_int (- a.num) /. from_int a.den = -. real a };170assert { real a <. 0. };171{ num = - a.num; den = a.den }172end else a173Valid (61ms) (colibri2 2) (cvc5) (split_vc) (depth 1)174let of_bigint (n:int) : t175ensures { real result = from_int n }176= assert { gcd n 1 = 1 by divides (gcd n 1) 1 /\ 0 <= gcd n 1 /\ gcd n 1 <> 0 };177{ num = n; den = 1 }178Valid (32ms) (colibri2)179let of_int (n:int63) : t180ensures { real result = from_int n }181= of_bigint (to_int n)182183predicate is_integer (a:real) = (exists z. a = from_int z)184Valid (178ms) (colibri2)185let is_integer (a:t) : bool186ensures { result <-> is_integer (real a) }187= if a.den = 1 then true188else begin189if pure { is_integer (real a) } then begin190let ghost z = any int ensures { real a = from_int result } in191cross a.num a.den z 1;192assert { divides a.den a.num };193assert { divides a.den (gcd a.num a.den) }194end;195false196end197
The roundings: an integer k with k <= x < k + 1 is unique
Valid (34ms) (colibri2)let ghost int_unique (k m:int) (x:real) : unit200requires { from_int k <=. x <. from_int k +. 1. }201requires { from_int m <=. x <. from_int m +. 1. }202ensures { k = m }203= assert { k < m + 1 by from_int k <. from_int (m + 1) };204assert { m < k + 1 by from_int m <. from_int (k + 1) }205
E.div n d is the floor of n / d when 0 < d
Valid (1.6s) (cvc4)let ghost frac_bounds (n d:int) : unit208requires { 0 < d }209ensures { from_int (E.div n d) <=. from_int n /. from_int d210<. from_int (E.div n d) +. 1. }211= let k = E.div n d in212let rd = from_int d in213assert { k * d <= n < k * d + d };214assert { from_int (k * d) <=. from_int n <. from_int (k * d + d) };215assert { from_int k *. rd <=. from_int n <. (from_int k +. 1.) *. rd };216assert { from_int n /. rd *. rd = from_int n }217Valid (42ms) (colibri2)218let floor (a:t) : int219ensures { result = T.floor (real a) }220= let k = E.div a.num a.den in221frac_bounds a.num a.den;222int_unique k (T.floor (real a)) (real a);223k224Valid (117ms) (colibri2)225let ceil (a:t) : int226ensures { result = T.ceil (real a) }227= let k = E.div (- a.num) a.den in228frac_bounds (- a.num) a.den;229assert { from_int (- a.num) /. from_int a.den = -. real a };230let ghost c = T.ceil (real a) in231assert { from_int (- c) <=. -. real a <. from_int (- c) +. 1. };232int_unique k (- c) (-. real a);233- k234Valid (34ms) (colibri2)235let ghost sign (a:t) : unit236ensures { a.num < 0 <-> real a <. 0. }237ensures { a.num = 0 <-> real a = 0. }238= let rn = from_int a.num in239let rd = from_int a.den in240assert { 0. <. rd };241assert { real a *. rd = rn }242Valid (41ms) (cvc5)243let truncate (a:t) : int244ensures { result = T.truncate (real a) }245= sign a;246let ghost t = T.truncate (real a) in247if a.num < 0 then begin248let c = ceil a in249assert { from_int (- c) <=. -. real a <. from_int (- c) +. 1. };250assert { from_int (- t) <=. -. real a <. from_int (- t) +. 1. };251int_unique (- c) (- t) (-. real a);252c253end else begin254let f = floor a in255int_unique f t (real a);256f257end258259function div_e_r (a b:real) : int =260let d = a /. b in if b <. 0. then T.ceil d else T.floor d261function div_t_r (a b:real) : int = T.truncate (a /. b)262function div_f_r (a b:real) : int = T.floor (a /. b)263Valid (37ms) (colibri2)264let div_e (a b:t) : t265requires { real b <> 0. }266ensures { real result = from_int (div_e_r (real a) (real b)) }267= sign b;268let d = div a b in269if b.num < 0 then of_bigint (ceil d) else of_bigint (floor d)270Valid (32ms) (colibri2)271let div_t (a b:t) : t272requires { real b <> 0. }273ensures { real result = from_int (div_t_r (real a) (real b)) }274= of_bigint (truncate (div a b))275Valid (30ms) (colibri2)276let div_f (a b:t) : t277requires { real b <> 0. }278ensures { real result = from_int (div_f_r (real a) (real b)) }279= of_bigint (floor (div a b))280Valid (26ms) (colibri2)281let mod_e (a b:t) : t282requires { real b <> 0. }283ensures { real result284= real a -. real b *. from_int (div_e_r (real a) (real b)) }285= sub a (mul b (div_e a b))286Valid (27ms) (colibri2)287let mod_t (a b:t) : t288requires { real b <> 0. }289ensures { real result290= real a -. real b *. from_int (div_t_r (real a) (real b)) }291= sub a (mul b (div_t a b))292Valid (26ms) (colibri2)293let mod_f (a b:t) : t294requires { real b <> 0. }295ensures { real result296= real a -. real b *. from_int (div_f_r (real a) (real b)) }297= sub a (mul b (div_f a b))298299function num_of (q:t) : int = q.num300function den_of (q:t) : int = q.den301Valid (56ms) (colibri2)302let ghost num_den (q:t) : unit303ensures { 0 < den_of q }304ensures { real q = from_int (num_of q) /. from_int (den_of q) }305= ()306307clone colibrilib.q.Q_intf {… begin (* cloned colibrilib.q.Q_intf *) Valid (32ms) (cvc5) lemma Q_intf.equal_is_eq predicate Q_intf.is_rat real function Q_intf.gcd_q t t : real val function Q_intf.is_zero t : bool val Q_intf.divisible t t : bool,int val Q_intf.gcd t t : t val Q_intf.gcdext t t : t,int,int val Q_intf.lcm t t : t val Q_intf.divexact t t : int val Q_intf.to_z t : int val Q_intf.to_zarith t : t val Q_intf.of_zarith t : t end } with308type t = t, function real = real,309function num = num_of, function den = den_of, val num_den = num_den,310val equal = eq, val le = le, val lt = lt, val abs = qabs,311val compare = compare,312val add = add, val sub = sub, val mul = mul, val div = div,313val of_int = of_int, val of_bigint = of_bigint,314val is_integer = is_integer,315val truncate_z = truncate, val floor_z = floor, val ceil_z = ceil,316val div_e = div_e, val mod_e = mod_e,317val div_t = div_t, val mod_t = mod_t,318val div_f = div_f, val mod_f = mod_f,319lemma equal_is_eq320end321