std.rational -- update and progress towards review

[H. S. Teoh]

On Wed, Oct 02, 2013 at 04:25:53PM +0200, Joseph Rushton Wakeling wrote:
> Hello all,
> 
> I thought I'd ask for some guidance here, since this is the first
> time I'm involved in bringing a new Phobos module to review.
> 
> If I understand right, "review" means that I present a pull request
> to Phobos, rather than just a standalone piece of code as currently
> available.  The question is how to handle various bits of
> std.rational that arguably could or maybe should be implemented
> elsewhere in Phobos.  Is there a preference to present the module
> as-is, and have the review process decide what goes where, or is it
> better to present the pull request including patches against other
> modules?

I'll let others give the "official" answer, but IIRC the best way to
start a review is to have the corresponding pull request ready to merge
(or in a state readily made mergeable).


> To help with answers to the above, I'll summarize the state of
> std.rational and what I've done so far.
> 
>    * std.rational is designed to allow the construction of rational
>      numbers based on any of the built-in integer types (it also works
>      with char:-), std.bigint.BigInt, or arbitrary user-defined
>      "integer-like" types.
> 
>    * Because it doesn't just want to work with built-in integer types,
>      David Simcha was forced to define custom versions of various
>      functionality found elsewhere in Phobos (or in some cases,
>      perhaps at the time the functionality simply was not there).
>      Some of these have been deleted in my recent updates as they are
>      no longer necessary: e.g. today it is fine to use std.math.abs,
>      std.traits.isAssignable.  Others remain, and the question is how
>      to handle these cases.
> 
>    * David defines an isRational template, which is currently very
>      simple (it just checks that the type has numerator and
>      denominator properties).  This presumably is fine to keep in
>      std.rational and should not be moved elsewhere.

Sounds reasonable to me. Also keeps well with Phobos generic philosophy:
if you don't need an explicit concrete type, don't depend on it, but use
signature constraints to select all types you know how to work with.


>    * Because std.rational doesn't just want to work with built-in
>      integer types it can't rely on the existing isIntegral.

TBH, I found isIntegral rather counterintuitive. I thought it would
evaluate to true with BigInt, but it doesn't. If I had my way, I'd
propose renaming isIntegral to isBuiltInIntegral, and David's
isIntegerLike to isIntegral.


>      Instead, David defined a new template, "isIntegerLike", which
>      checks the operations supported by the type and whether they work
>      in an integer-like way.  Could/should this be placed in
>      std.traits?

I support putting it in std.traits. It's useful not just to the proposed
std.rational, but also other generic numerics-related code. E.g.,
iota(), which in theory should accept any integer-like types, not just a
fixed set of built-in types (it doesn't even accept BigInt, which is
currently filed as a bug).


>      Better to do this in the initial pull or let the decision be part
>      of the review process?

This seems a rather significant change outside of std.rational itself,
so my feeling is, probably better to let others review it first.


>    * For similar reasons, CommonType is insufficient and David defined
>      two new templates, CommonInteger (which works out an appropriate
>      common type for two "integer-like" types) and CommonRational.
>      The former at least looks to me like it should be in std.traits.

Agreed.


>      Again, better to do this in the initial pull request, or make it
>      a decision to take at review time?

Maybe we could have a bit of discussion here in the forum on all of the
proposed additions to std.traits, then once that decision is made, put
up std.rational for the actual "official" review?


>    * Several Rational-based overrides for std.math functions are
>      defined: floor, ceil and round.  I believe it's normal for such
>      type-specific overrides to be in the same module as their type?

I would think so.


>    * Finally, there are two mathematical functions, gcf (greatest
>      common factor) and lcm (least common multiple) which again are
>      locally defined because Phobos' existing std.math.gcd cannot
>      handle BigInts (let alone any other user-defined integer type).
>      These should presumably be sent over to std.math but that relies
>      on isIntegerLike being accepted for std.traits, or else some
>      alternative type check being in place.

I agree gcd/lcm should be put into std.math. Also, gcf should be renamed
gcd, I think that's more well-known.


>    * (... actually, there is no lcm in std.math in any case.  An
>      oversight:-)

I vote for gcd & lcm to be added to std.math.


> I need to do a careful review of the function attributes (there's a
> complete lack of @safe, pure, nothrow, const, ... in the module, only
> @property is used), but apart from that I think that the code is now
> working within the confines of its design parameters, and in that
> sense is ready for review.

Since Rational is a templated type, no function attributes are needed.
The compiler should be able to infer the appropriate attributes.

Unless, of course, you find a case where it makes sense to constrict any
future changes in implementation (e.g., guarantee that gcd is always
pure -- but even that is questionable since gcd's purity would depend on
the purity of operations on the type it is being instantiated for, so
even in this case I'd say keep it unmarked and let attribute inference
do its job).


> I've squashed the only overt bug found, added unittests to confirm
> this and to check other cases (David's were already very extensive so
> I haven't needed to do much), updated and corrected the docs and
> removed all unnecessary code duplication, and of course also brought
> the code style in line with current Phobos standards.

Good!


> The remaining open issues
> <https://github.com/WebDrake/Rational/issues?state=open> are all
> design-related.  Apart from those raised by my above queries, the
> major one is how rationals should relate to floating-point numbers --
> e.g. there is currently no opCmp for floating-point, meaning this:

> 
>     assert(rational(10, 1) == 10);
> 
> ... will work, but this:
> 
>     assert(rational(10, 1) == 10.0);
> 
> ... will fail to compile.  It's not entirely obvious how to resolve
> this as floating-point vs. rational comparisons risk accidentally
> creating huge temporary BigInt-based rationals ... :-(

Does addition/subtraction with floating point work correctly? If so, the
user should simply write:

	assert(abs(rational(10,1) - 10.0) < EPSILON);

We should definitely not convert floats to Rational just so they can be
compared, because floats are inexact by definition, whereas Rationals
are always exact. For example, rational(2,10) != 0.2f, because 0.2f has
no exact representation in any binary floating-point format. But if you
support rational(10,1) == 10.0, then people will expect that
rational(2,10) == 0.2 should also work, but it *can't* work.  We should
not sweep these issues under the rug, but force the user to come to
terms with the nature of floating-point numbers.

OTOH, one compromise might be to allow implicit conversion of Rationals
to floating-point via alias this:

	struct Rational(T) {
		...
		@property real toReal() { return this.convertToReal(); }
		alias toReal this;
	}

	void main() {
		float x = 1.0;
		assert(rational(1,1) == x);
	}

This works because Rational implicitly converts to real, and x also
implicitly converts to real, and both are then comparable.


T

-- 
Give a man a fish, and he eats once. Teach a man to fish, and he will sit forever.