Common — library colibrilib.q_model — module QModel

A 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.

12
module QModel
13
use int.Int
14
use int.Abs
15
use int.EuclideanDivision as E
16
use number.Divisibility
17
use number.Gcd
18
use number.Coprime
19
use real.RealInfix
20
use real.FromInt
21
use real.Abs as RA
22
use real.Truncate as T
23
use mach.int.Int63
24
use colibrilib.q.Ord as Ord

num / den, in lowest terms

27
type
t
= {
num
: int;
den
: int } Valid (29ms) (colibri2)
28
invariant { 0 < den /\ gcd num den = 1 }
29
by { num = 0; den = 1 }
30
31
function
real
(q:t) : real = from_int q.num /. from_int q.den

The (non negative) greatest common divisor, by Euclid

  Valid (33ms) (colibri2)
34
let rec
euclid
(a b:int) : int
35
requires { 0 <= a /\ 0 <= b }
36
ensures { result = gcd a b }
37
variant { b }
38
= if b = 0 then a
39
else begin
40
assert { gcd a b = gcd b (E.mod a b) };
41
euclid b (E.mod a b)
42
end
43
Valid (28ms) (colibri2)
44
let ghost
cross
(n1 d1 n2 d2:int) : unit
45
requires { d1 <> 0 /\ d2 <> 0 }
46
ensures { from_int n1 /. from_int d1 = from_int n2 /. from_int d2
47
<-> n1 * d2 = n2 * d1 }
48
= let x1 = from_int n1 in let y1 = from_int d1 in
49
let x2 = from_int n2 in let y2 = from_int d2 in
50
assert { y1 <> 0. /\ y2 <> 0. };
51
assert { x1 /. y1 = x2 /. y2 <-> x1 *. y2 = x2 *. y1
52
by x1 /. y1 *. (y1 *. y2) = x1 *. y2
53
/\ x2 /. y2 *. (y1 *. y2) = x2 *. y1 };
54
assert { from_int (n1 * d2) = x1 *. y2 };
55
assert { from_int (n2 * d1) = x2 *. y1 }
56
Valid (23ms) (cvc5)
57
let ghost
scale
(g a b:int) : unit
58
ensures { (g * a) * b = a * (g * b) }
59
ensures { (g * a) * (- b) = (- a) * (g * b) }
60
= ()

n / d in lowest terms

  Valid (155ms) (colibri2 13) (cvc5 2) (split_vc 2) (depth 2)
63
let
make
(n d:int) : t
64
requires { d <> 0 }
65
ensures { real result = from_int n /. from_int d }
66
= let g = euclid (abs n) (abs d) in
67
assert { g = gcd n d };
68
assert { 0 < g };
69
let a = E.div n g in
70
let b = E.div d g in
71
assert { n = g * a /\ d = g * b };
72
assert { gcd n d = g * gcd a b };
73
assert { gcd a b = 1 };
74
if b < 0 then begin
75
assert { gcd (-a) (-b) = 1
76
by gcd (-a) (-b) = gcd a (-b) /\ gcd (-b) a = gcd b a };
77
scale g a b;
78
cross n d (-a) (-b);
79
{ num = -a; den = -b }
80
end else begin
81
scale g a b;
82
cross n d a b;
83
{ num = a; den = b }
84
end
85
86
predicate
equal
(a b:t) = (real a = real b)

The fractions in lowest terms are unique

  Valid (88ms) (colibri2 13) (split_vc) (depth 1)
89
let lemma
equal_is_eq
(a b:t) : unit
90
requires { equal a b }
91
ensures { a = b }
92
= cross a.num a.den b.num b.den;
93
assert { divides a.den (a.num * b.den) };
94
assert { coprime a.den a.num by gcd a.den a.num = gcd a.num a.den };
95
assert { divides a.den b.den };
96
assert { divides b.den (b.num * a.den) };
97
assert { coprime b.den b.num by gcd b.den b.num = gcd b.num b.den };
98
assert { divides b.den a.den };
99
assert { a.den = b.den \/ a.den = - b.den };
100
assert { a.den = b.den };
101
assert { (a.num - b.num) * a.den = 0 };
102
assert { a.num = b.num };
103
assert { t'eq a b }
104
Valid (35ms) (colibri2)
105
let
eq
(a b:t) : bool
106
ensures { equal a b = result }
107
= if a.num = b.num && a.den = b.den then true
108
else begin
109
if pure { equal a b } then equal_is_eq a b;
110
false
111
end
112
Valid (47ms) (colibri2)
113
let ghost
le_cross
(a b:t) : unit
114
ensures { real a <=. real b <-> a.num * b.den <= b.num * a.den }
115
ensures { real a <. real b <-> a.num * b.den < b.num * a.den }
116
= assert { real a = from_int (a.num * b.den) /. from_int (a.den * b.den) };
117
assert { real b = from_int (b.num * a.den) /. from_int (a.den * b.den) };
118
assert { 0. <. from_int (a.den * b.den) }
119
Valid (27ms) (colibri2)
120
let
le
(a b:t) : bool
121
ensures { result = (real a <=. real b) }
122
= le_cross a b; a.num * b.den <= b.num * a.den
123
Valid (31ms) (colibri2)
124
let
lt
(a b:t) : bool
125
ensures { result = (real a <. real b) }
126
= le_cross a b; a.num * b.den < b.num * a.den
127
Valid (36ms) (colibri2)
128
let
compare
(a b:t) : Ord.t
129
ensures { match result with
130
| Ord.Eq -> equal a b
131
| Ord.Lt -> real a <. real b
132
| Ord.Gt -> real b <. real a
133
end }
134
= if lt a b then Ord.Lt else if lt b a then Ord.Gt else Ord.Eq
135
Valid (43ms) (colibri2)
136
let function
add
(a b:t) : t
137
ensures { real a +. real b = real result }
138
= let r = make (a.num * b.den + b.num * a.den) (a.den * b.den) in
139
assert { from_int (a.num * b.den + b.num * a.den) /. from_int (a.den * b.den)
140
= real a +. real b };
141
r
142
Valid (41ms) (colibri2)
143
let function
sub
(a b:t) : t
144
ensures { real a -. real b = real result }
145
= let r = make (a.num * b.den - b.num * a.den) (a.den * b.den) in
146
assert { from_int (a.num * b.den - b.num * a.den) /. from_int (a.den * b.den)
147
= real a -. real b };
148
r
149
Valid (45ms) (colibri2)
150
let function
mul
(a b:t) : t
151
ensures { real a *. real b = real result }
152
= let r = make (a.num * b.num) (a.den * b.den) in
153
assert { from_int (a.num * b.num) /. from_int (a.den * b.den)
154
= real a *. real b };
155
r
156
Valid (52ms) (colibri2)
157
let function
div
(a b:t) : t
158
requires { real b <> 0. }
159
ensures { real a /. real b = real result }
160
= assert { b.num <> 0 };
161
let r = make (a.num * b.den) (a.den * b.num) in
162
assert { from_int (a.num * b.den) /. from_int (a.den * b.num)
163
= real a /. real b };
164
r
165
Valid (52ms) (colibri2)
166
let
qabs
(a:t) : t
167
ensures { real result = RA.abs (real a) }
168
= if a.num < 0 then begin
169
assert { gcd (- a.num) a.den = gcd a.num a.den };
170
assert { from_int (- a.num) /. from_int a.den = -. real a };
171
assert { real a <. 0. };
172
{ num = - a.num; den = a.den }
173
end else a
174
Valid (61ms) (colibri2 2) (cvc5) (split_vc) (depth 1)
175
let
of_bigint
(n:int) : t
176
ensures { real result = from_int n }
177
= assert { gcd n 1 = 1 by divides (gcd n 1) 1 /\ 0 <= gcd n 1 /\ gcd n 1 <> 0 };
178
{ num = n; den = 1 }
179
Valid (32ms) (colibri2)
180
let
of_int
(n:int63) : t
181
ensures { real result = from_int n }
182
= of_bigint (to_int n)
183
184
predicate
is_integer
(a:real) = (exists z. a = from_int z)
185
Valid (178ms) (colibri2)
186
let
is_integer
(a:t) : bool
187
ensures { result <-> is_integer (real a) }
188
= if a.den = 1 then true
189
else begin
190
if pure { is_integer (real a) } then begin
191
let ghost z = any int ensures { real a = from_int result } in
192
cross a.num a.den z 1;
193
assert { divides a.den a.num };
194
assert { divides a.den (gcd a.num a.den) }
195
end;
196
false
197
end

The roundings: an integer k with k <= x < k + 1 is unique

  Valid (34ms) (colibri2)
200
let ghost
int_unique
(k m:int) (x:real) : unit
201
requires { from_int k <=. x <. from_int k +. 1. }
202
requires { from_int m <=. x <. from_int m +. 1. }
203
ensures { k = m }
204
= assert { k < m + 1 by from_int k <. from_int (m + 1) };
205
assert { m < k + 1 by from_int m <. from_int (k + 1) }

E.div n d is the floor of n / d when 0 < d

  Valid (1.6s) (cvc4)
208
let ghost
frac_bounds
(n d:int) : unit
209
requires { 0 < d }
210
ensures { from_int (E.div n d) <=. from_int n /. from_int d
211
<. from_int (E.div n d) +. 1. }
212
= let k = E.div n d in
213
let rd = from_int d in
214
assert { k * d <= n < k * d + d };
215
assert { from_int (k * d) <=. from_int n <. from_int (k * d + d) };
216
assert { from_int k *. rd <=. from_int n <. (from_int k +. 1.) *. rd };
217
assert { from_int n /. rd *. rd = from_int n }
218
Valid (42ms) (colibri2)
219
let
floor
(a:t) : int
220
ensures { result = T.floor (real a) }
221
= let k = E.div a.num a.den in
222
frac_bounds a.num a.den;
223
int_unique k (T.floor (real a)) (real a);
224
k
225
Valid (117ms) (colibri2)
226
let
ceil
(a:t) : int
227
ensures { result = T.ceil (real a) }
228
= let k = E.div (- a.num) a.den in
229
frac_bounds (- a.num) a.den;
230
assert { from_int (- a.num) /. from_int a.den = -. real a };
231
let ghost c = T.ceil (real a) in
232
assert { from_int (- c) <=. -. real a <. from_int (- c) +. 1. };
233
int_unique k (- c) (-. real a);
234
- k
235
Valid (34ms) (colibri2)
236
let ghost
sign
(a:t) : unit
237
ensures { a.num < 0 <-> real a <. 0. }
238
ensures { a.num = 0 <-> real a = 0. }
239
= let rn = from_int a.num in
240
let rd = from_int a.den in
241
assert { 0. <. rd };
242
assert { real a *. rd = rn }
243
Valid (41ms) (cvc5)
244
let
truncate
(a:t) : int
245
ensures { result = T.truncate (real a) }
246
= sign a;
247
let ghost t = T.truncate (real a) in
248
if a.num < 0 then begin
249
let c = ceil a in
250
assert { from_int (- c) <=. -. real a <. from_int (- c) +. 1. };
251
assert { from_int (- t) <=. -. real a <. from_int (- t) +. 1. };
252
int_unique (- c) (- t) (-. real a);
253
c
254
end else begin
255
let f = floor a in
256
int_unique f t (real a);
257
f
258
end
259
260
function
div_e_r
(a b:real) : int =
261
let d = a /. b in if b <. 0. then T.ceil d else T.floor d
262
function
div_t_r
(a b:real) : int = T.truncate (a /. b)
263
function
div_f_r
(a b:real) : int = T.floor (a /. b)
264
Valid (37ms) (colibri2)
265
let
div_e
(a b:t) : t
266
requires { real b <> 0. }
267
ensures { real result = from_int (div_e_r (real a) (real b)) }
268
= sign b;
269
let d = div a b in
270
if b.num < 0 then of_bigint (ceil d) else of_bigint (floor d)
271
Valid (32ms) (colibri2)
272
let
div_t
(a b:t) : t
273
requires { real b <> 0. }
274
ensures { real result = from_int (div_t_r (real a) (real b)) }
275
= of_bigint (truncate (div a b))
276
Valid (30ms) (colibri2)
277
let
div_f
(a b:t) : t
278
requires { real b <> 0. }
279
ensures { real result = from_int (div_f_r (real a) (real b)) }
280
= of_bigint (floor (div a b))
281
Valid (26ms) (colibri2)
282
let
mod_e
(a b:t) : t
283
requires { real b <> 0. }
284
ensures { real result
285
= real a -. real b *. from_int (div_e_r (real a) (real b)) }
286
= sub a (mul b (div_e a b))
287
Valid (27ms) (colibri2)
288
let
mod_t
(a b:t) : t
289
requires { real b <> 0. }
290
ensures { real result
291
= real a -. real b *. from_int (div_t_r (real a) (real b)) }
292
= sub a (mul b (div_t a b))
293
Valid (26ms) (colibri2)
294
let
mod_f
(a b:t) : t
295
requires { real b <> 0. }
296
ensures { real result
297
= real a -. real b *. from_int (div_f_r (real a) (real b)) }
298
= sub a (mul b (div_f a b))
299
300
function
num_of
(q:t) : int = q.num
301
function
den_of
(q:t) : int = q.den
302
Valid (56ms) (colibri2)
303
let ghost
num_den
(q:t) : unit
304
ensures { 0 < den_of q }
305
ensures { real q = from_int (num_of q) /. from_int (den_of q) }
306
= ()
307
308
clone 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
}
with
309
type t = t, function real = real,
310
function num = num_of, function den = den_of, val num_den = num_den,
311
val equal = eq, val le = le, val lt = lt, val abs = qabs,
312
val compare = compare,
313
val add = add, val sub = sub, val mul = mul, val div = div,
314
val of_int = of_int, val of_bigint = of_bigint,
315
val is_integer = is_integer,
316
val truncate_z = truncate, val floor_z = floor, val ceil_z = ceil,
317
val div_e = div_e, val mod_e = mod_e,
318
val div_t = div_t, val mod_t = mod_t,
319
val div_f = div_f, val mod_f = mod_f,
320
lemma equal_is_eq
321
end