Extend the theory of positive rationals `Qp`
This MR extends the theory of positive rationals Qp
. The most important change is that it fixes the leaky abstraction, adds tons of lemmas, and no longer relies on the coercions to the non-negative rationals Qc
to obtain notions like orders.
New features
- Add the orders
Qc_le
andQp_lt
. - Add a function
Qc_inv
for the multiplicative inverse. - Define the division function
Qp_div
in terms ofQp_inv
, and generalize the second argument frompositive
toQp
. - Define a function
pos_to_Qp
that converts apositive
into a positive rationalQp
. - Add many lemmas and missing type class instances, especially for orders, multiplication, multiplicative inverse, division, and the conversion.
Technical changes:
- Remove the coercion from
Qp
toQc
. This follows our recent tradition of getting rid of coercions since they are more often confusing than useful. - Rename the conversion from
Qp
toQc
fromQp_car
intoQp_to_Qc
to be consistent with other conversion functions in std++. Also rename the lemmaQp_eq
intoQp_to_Qc_inj_iff
. - Use
let '(..) = ...
in the definitions ofQp_plus
/Qp_mult
/Qp_inv
/Qp_le
/Qp_lt
to avoid Coq tactics (likeinjection
) to unfold these definitions eagerly. We already used this trick in e.g.,gmap
for the same reason. This works around the Coq issue that @simonfv ran into here. - Define the literals 1, 2, 3, 4 in terms of
pos_to_Qp
instead of iterated addition. This avoids weird rewrites. For example, before2
was defined as1 + 1
, so rewriting with1 = stuff
in a goal containing2
turned it intostuff + stuff
, which was extremely confusing.
Things to discuss
- We could use Coq's extensible notation machinery to get proper notations for the literals. AFAIK this is only possible in Coq 8.9+, so that requires us to drop support for Coq 8.8. Do ▷
-
While we are changing the API anyway, use add
/mul
instead ofplus
/mult
, to be consistent with the lemmas fornat
andZ
. - Also improve the
Qc
library in the same way. Do ▷
Impact on reverse dependencies
This MR will cause some breakage for libraries that rely on the order on fractions, but in my opinion, this is for the better. I have ported some of the developments that use fractions in interesting ways, namely Iris, Iron, and LambdaRust. While stuff broke, I managed to shorten proofs significantly by making use of the new lemmas introduced in this MR. Also, after this MR, none of these developments rely on the conversion to Qc
anymore, showing that we indeed provide a reasonable API now.
Some stats:
- Iris: 66 insertions, 78 deletions
- LambdaRust: 32 insertions, 63 deletions
- Iron: no changes needed
- Examples: no changed needed, after removing an unused lemma
- gpfls: 8 insertions, 8 deletions
To land this MR, we should first merge iris!497 (merged).