module QWithInf
use real.RealInfix
use int.Int
use real.FromInt
use Z as Z
type value =
| MinusInf
| PlusInf
| NaN
| Real
type t = {
num: int;
den: int;
ghost value: value;
}
invariant { value = Real -> 0 < den }
invariant { value = Real -> Z.prime_to_one_another num den }
Valid (17ms) (colibri2)
by { num = 1; den = 1; value = Real }
predicate is_real (q:t) =
q.value = Real
predicate is_minus_inf (q:t) =
q.value = MinusInf
predicate is_plus_inf (q:t) =
q.value = PlusInf
predicate is_nan (q:t) =
q.value = NaN
predicate not_NaN (q:t) = q.value <> NaN
function real (q:t) : real
axiom real_def:
forall q:t. is_real q -> real q = ((from_int q.num) /. (from_int q.den))
type kind =
| ZERO | NZERO | INF | MINF | UNDEF
val classify (v:t) : kind
ensures {
match result with
| ZERO -> is_real v /\ real v = 0.
| NZERO -> is_real v /\ real v <> 0.
| UNDEF -> v.value = NaN
| MINF -> v.value = MinusInf
| INF -> v.value = PlusInf
end
}
predicate equal (a b:t) =
if a.is_real /\ b.is_real then a.real = b.real else a.value = b.value
val (=) (a:t) (b:t) : bool
ensures { equal a b = result }
function (<=) (a:t) (b:t) : bool
function (<) (a:t) (b:t) : bool = a <= b /\ not (equal a b)
axiom le_def: forall a b. a.is_real -> b.is_real -> ((a <= b) <-> (a.real <=. b.real))
axiom le_def_full: forall a b [a <= b].
match a.value, b.value with
| Real, Real -> true
| NaN, NaN -> a <= b
| NaN, _ -> a <= b
| _, NaN -> not (a <= b)
| MinusInf, _ -> a <= b
| _, PlusInf -> a <= b
| _, MinusInf -> not (a <= b)
| PlusInf, _ -> not (a <= b)
end
val (<=) (a:t) (b:t) : bool
requires { not_NaN a /\ not_NaN b }
ensures { result = (a <= b) }
val (<) (a:t) (b:t) : bool
requires { not_NaN a /\ not_NaN b }
ensures { result = (a < b) }
val (+) (a b:t) : t
requires { not_NaN a /\ not_NaN b }
ensures { match a.value, b.value with
| Real, Real -> true
| NaN, _ -> false
| _, NaN -> false
| (MinusInf | Real), (MinusInf | Real) -> result.value = MinusInf
| (PlusInf | Real), (PlusInf | Real) -> result.value = PlusInf
| MinusInf, PlusInf | PlusInf, MinusInf -> result.value = NaN
end
}
ensures { is_real a -> is_real b -> is_real result }
ensures { is_real a -> is_real b -> a.real +. b.real = result.real }
val (-) (a b:t) : t
requires { not_NaN a /\ not_NaN b }
ensures { match a.value, b.value with
| Real, Real -> true
| NaN, _ -> false
| _, NaN -> false
| (MinusInf | Real), (PlusInf | Real) -> result.value = MinusInf
| (PlusInf | Real), (MinusInf | Real) -> result.value = PlusInf
| MinusInf, MinusInf | PlusInf, PlusInf -> result.value = NaN
end
}
ensures { is_real a -> is_real b -> is_real result }
ensures { is_real a -> is_real b -> a.real -. b.real = result.real }
val (*) (a b:t) : t
requires { is_real a /\ is_real b }
ensures { match a.value, b.value with
| Real, Real -> true
| NaN, _ -> false
| _, NaN -> false
| MinusInf, PlusInf | PlusInf, MinusInf -> result.value = MinusInf
| MinusInf, Real -> result.value = (if b.real = 0. then NaN else MinusInf)
| PlusInf, Real -> result.value = (if b.real >=. 0. then PlusInf else MinusInf)
| Real, MinusInf -> result.value = (if a.real = 0. then NaN else MinusInf)
| Real, PlusInf -> result.value = (if a.real >=. 0. then PlusInf else MinusInf)
| MinusInf, MinusInf | PlusInf, PlusInf -> result.value = PlusInf
end
}
ensures { is_real a -> is_real b -> is_real result }
ensures { is_real a -> is_real b -> a.real *. b.real = result.real }
val (/) (a b:t) : t
requires { not_NaN a /\ not_NaN b }
ensures { match a.value, b.value with
| Real, Real -> if b.real = 0. then begin
if a.real = 0. then result.value = NaN
else if a.real <. 0. then result.value = MinusInf else result.value = PlusInf
end
else true
| NaN, _ -> false
| _, NaN -> false
| (MinusInf | PlusInf), (MinusInf | PlusInf) -> result.value = NaN
| MinusInf, Real -> result.value = (if b.real <. 0. then PlusInf else MinusInf)
| PlusInf, Real -> result.value = (if b.real >=. 0. then PlusInf else MinusInf)
| Real, (MinusInf | PlusInf) -> result.value = Real /\ result.real = 0.
end
}
ensures { is_real a -> is_real b -> b.real <> 0. -> is_real result }
ensures { is_real a -> is_real b -> b.real <> 0. -> a.real /. b.real = result.real }
val make (num den: int): t
requires { den <> 0 }
ensures { result.is_real }
ensures { result.real = (from_int num) /. (from_int den) }
val make_exact (num den: int): t
requires { Int.(<) 0 den } requires { Z.prime_to_one_another num den }
ensures { result.is_real }
ensures { result.num = num }
ensures { result.den = den }
use real.Truncate
val to_int (a:t) : int
requires { is_real a }
ensures { result = truncate a.real }
val of_int (a:int) : t
ensures { is_real result }
ensures { result.real = from_int a }
Valid (81ms) (colibri2)
let floor (a:t) : int
requires { is_real a }
ensures { result = floor a.real } =
assert { from_int (floor a.real) <=. a.real <. from_int (floor a.real) +. 1. };
assert { 0. <=. a.real -. from_int (floor a.real) <. 1. };
let r = Z.fdiv a.num a.den in
assert { Int.(0 <= a.num - r*a.den < a.den) };
assert { 0. <=. (from_int a.num) -. (from_int r)*.(from_int a.den) <. (from_int a.den) };
assert { ((from_int a.num) -. (from_int r)*.(from_int a.den))/.(from_int a.den) <. (from_int a.den)/.(from_int a.den) };
assert { 0. <=. a.real -. from_int r <. 1. };
r
Valid (352ms) (colibri2)
let ceil (a:t) : int
requires { is_real a }
ensures { result = ceil a.real } =
assert { from_int (ceil a.real) -. 1. <. a.real <=. from_int (ceil a.real) };
assert { 0. <=. from_int (ceil a.real) -. a.real <. 1. };
let r = Z.cdiv a.num a.den in
assert { Int.(0 <= r*a.den - a.num < a.den) };
assert { 0. <=. (from_int r)*.(from_int a.den) -. (from_int a.num) <. (from_int a.den) };
assert { ((from_int r)*.(from_int a.den) -. (from_int a.num))/.(from_int a.den) <. (from_int a.den)/.(from_int a.den) };
assert { 0. <=. from_int r -. a.real <. 1. };
r
end