Common — library colibrilib.q — module QWithInf
74
module QWithInf
75
76
use real.RealInfix
77
use int.Int
78
use real.FromInt
79
use Z as Z
80
81
type
value
=
82
|
MinusInf
83
|
PlusInf
84
|
NaN
85
|
Real
86
87
type
t
= {
88
num
: int;
89
den
: int;
90
ghost
value
: value;
91
}
92
invariant { value = Real -> 0 < den }
93
invariant { value = Real -> Z.prime_to_one_another num den } Valid (17ms) (colibri2)
94
by { num = 1; den = 1; value = Real }
95
96
predicate
is_real
(q:t) =
97
q.value = Real
98
99
predicate
is_minus_inf
(q:t) =
100
q.value = MinusInf
101
102
predicate
is_plus_inf
(q:t) =
103
q.value = PlusInf
104
105
predicate
is_nan
(q:t) =
106
q.value = NaN
107
108
predicate
not_NaN
(q:t) = q.value <> NaN
109
110
function
real
(q:t) : real
111
112
axiom
real_def
:
113
forall q:t. is_real q -> real q = ((from_int q.num) /. (from_int q.den))
114
115
type
kind
=
116
|
ZERO
|
NZERO
|
INF
|
MINF
|
UNDEF
117
118
val
classify
(v:t) : kind
119
ensures {
120
match result with
121
| ZERO -> is_real v /\ real v = 0.
122
| NZERO -> is_real v /\ real v <> 0.
123
| UNDEF -> v.value = NaN
124
| MINF -> v.value = MinusInf
125
| INF -> v.value = PlusInf
126
end
127
}
128
129
predicate
equal
(a b:t) =
130
if a.is_real /\ b.is_real then a.real = b.real else a.value = b.value
131
132
val (
=
) (a:t) (b:t) : bool
133
ensures { equal a b = result }
134
135
function (
<=
) (a:t) (b:t) : bool
136
function (
<
) (a:t) (b:t) : bool = a <= b /\ not (equal a b)
137
138
axiom
le_def
: forall a b. a.is_real -> b.is_real -> ((a <= b) <-> (a.real <=. b.real))
139
axiom
le_def_full
: forall a b [a <= b].
140
match a.value, b.value with
141
| Real, Real -> true
142
| NaN, NaN -> a <= b
143
| NaN, _ -> a <= b
144
| _, NaN -> not (a <= b)
145
| MinusInf, _ -> a <= b
146
| _, PlusInf -> a <= b
147
| _, MinusInf -> not (a <= b)
148
| PlusInf, _ -> not (a <= b)
149
end
150
151
(* lemma le_anti_refl: forall a b. a <= b -> b <= a -> equal a b *)
152
(* lemma le_trans: forall a b c. a <= b -> b <= c -> a <= c *)
153
(* lemma le_lt_trans: forall a b c. a <= b -> b < c -> a < c *)
154
(* lemma lt_le_trans: forall a b c. a < b -> b <= c -> a < c *)
155
156
val (
<=
) (a:t) (b:t) : bool
157
requires { not_NaN a /\ not_NaN b }
158
ensures { result = (a <= b) }
159
160
val (
<
) (a:t) (b:t) : bool
161
requires { not_NaN a /\ not_NaN b }
162
ensures { result = (a < b) }
163
164
val (
+
) (a b:t) : t
165
requires { not_NaN a /\ not_NaN b }
166
ensures { match a.value, b.value with
167
| Real, Real -> true
168
| NaN, _ -> false (* absurd *)
169
| _, NaN -> false (* absurd *)
170
| (MinusInf | Real), (MinusInf | Real) -> result.value = MinusInf
171
| (PlusInf | Real), (PlusInf | Real) -> result.value = PlusInf
172
| MinusInf, PlusInf | PlusInf, MinusInf -> result.value = NaN
173
end
174
}
175
ensures { is_real a -> is_real b -> is_real result }
176
ensures { is_real a -> is_real b -> a.real +. b.real = result.real }
177
178
val (
-
) (a b:t) : t
179
requires { not_NaN a /\ not_NaN b }
180
ensures { match a.value, b.value with
181
| Real, Real -> true
182
| NaN, _ -> false (* absurd *)
183
| _, NaN -> false (* absurd *)
184
| (MinusInf | Real), (PlusInf | Real) -> result.value = MinusInf
185
| (PlusInf | Real), (MinusInf | Real) -> result.value = PlusInf
186
| MinusInf, MinusInf | PlusInf, PlusInf -> result.value = NaN
187
end
188
}
189
ensures { is_real a -> is_real b -> is_real result }
190
ensures { is_real a -> is_real b -> a.real -. b.real = result.real }
191
192
val (
*
) (a b:t) : t
193
requires { is_real a /\ is_real b }
194
ensures { match a.value, b.value with
195
| Real, Real -> true
196
| NaN, _ -> false (* absurd *)
197
| _, NaN -> false (* absurd *)
198
| MinusInf, PlusInf | PlusInf, MinusInf -> result.value = MinusInf (* todo *)
199
| MinusInf, Real -> result.value = (if b.real = 0. then NaN else MinusInf) (* todo *)
200
| PlusInf, Real -> result.value = (if b.real >=. 0. then PlusInf else MinusInf) (* todo *)
201
| Real, MinusInf -> result.value = (if a.real = 0. then NaN else MinusInf) (* todo *)
202
| Real, PlusInf -> result.value = (if a.real >=. 0. then PlusInf else MinusInf) (* todo *)
203
| MinusInf, MinusInf | PlusInf, PlusInf -> result.value = PlusInf
204
end
205
}
206
ensures { is_real a -> is_real b -> is_real result }
207
ensures { is_real a -> is_real b -> a.real *. b.real = result.real }
208
209
val (
/
) (a b:t) : t
210
requires { not_NaN a /\ not_NaN b }
211
ensures { match a.value, b.value with
212
| Real, Real -> if b.real = 0. then begin
213
if a.real = 0. then result.value = NaN
214
else if a.real <. 0. then result.value = MinusInf else result.value = PlusInf
215
end
216
else true
217
| NaN, _ -> false (* absurd *)
218
| _, NaN -> false (* absurd *)
219
| (MinusInf | PlusInf), (MinusInf | PlusInf) -> result.value = NaN
220
| MinusInf, Real -> result.value = (if b.real <. 0. then PlusInf else MinusInf)
221
| PlusInf, Real -> result.value = (if b.real >=. 0. then PlusInf else MinusInf)
222
| Real, (MinusInf | PlusInf) -> result.value = Real /\ result.real = 0.
223
end
224
}
225
ensures { is_real a -> is_real b -> b.real <> 0. -> is_real result }
226
ensures { is_real a -> is_real b -> b.real <> 0. -> a.real /. b.real = result.real }
227
228
val
make
(num den: int): t
229
requires { den <> 0 }
230
ensures { result.is_real }
231
ensures { result.real = (from_int num) /. (from_int den) }
232
233
val
make_exact
(num den: int): t
234
requires { Int.(<) 0 den } requires { Z.prime_to_one_another num den }
235
ensures { result.is_real }
236
ensures { result.num = num }
237
ensures { result.den = den }
238
239
use real.Truncate
240
241
val
to_int
(a:t) : int
242
requires { is_real a }
243
ensures { result = truncate a.real }
244
245
val
of_int
(a:int) : t
246
ensures { is_real result }
247
ensures { result.real = from_int a }
248
Valid (81ms) (colibri2)
249
let
floor
(a:t) : int
250
requires { is_real a }
251
ensures { result = floor a.real } =
252
assert { from_int (floor a.real) <=. a.real <. from_int (floor a.real) +. 1. };
253
assert { 0. <=. a.real -. from_int (floor a.real) <. 1. };
254
let r = Z.fdiv a.num a.den in
255
assert { Int.(0 <= a.num - r*a.den < a.den) };
256
assert { 0. <=. (from_int a.num) -. (from_int r)*.(from_int a.den) <. (from_int a.den) };
257
assert { ((from_int a.num) -. (from_int r)*.(from_int a.den))/.(from_int a.den) <. (from_int a.den)/.(from_int a.den) };
258
assert { 0. <=. a.real -. from_int r <. 1. };
259
r
260
261
Valid (352ms) (colibri2)
262
let
ceil
(a:t) : int
263
requires { is_real a }
264
ensures { result = ceil a.real } =
265
assert { from_int (ceil a.real) -. 1. <. a.real <=. from_int (ceil a.real) };
266
assert { 0. <=. from_int (ceil a.real) -. a.real <. 1. };
267
let r = Z.cdiv a.num a.den in
268
assert { Int.(0 <= r*a.den - a.num < a.den) };
269
assert { 0. <=. (from_int r)*.(from_int a.den) -. (from_int a.num) <. (from_int a.den) };
270
assert { ((from_int r)*.(from_int a.den) -. (from_int a.num))/.(from_int a.den) <. (from_int a.den)/.(from_int a.den) };
271
assert { 0. <=. from_int r -. a.real <. 1. };
272
r
273
274
275
end