On Mon, Dec 23, 2013 at 03:00:25PM +0000, Francesco Cattoglio wrote:
> Sorry for the amount of text, but I tried to explain everything in a
> clear and simple way.
> I'm willing to volunteer for adding support for more types in iota.
> The relevant discussion is:
> https://d.puremagic.com/issues/show_bug.cgi?id=10762
>
> A few preliminary considerations:
> - iota() currently returns a Random Access range, and I'm sure
> nobody would agree to downgrade the result to a ForwardRange or an
> InputRange, because that would break an unknown amount of code.
Certainly, the new iota() implementation should not reduce current
functionality, but only add to it.
> - I think everyone agrees that even after enhancements, iota()
> should always return a RA range, even if we use types that are
> currently not supported. It would make little sense returning
> different kind of ranges for different input types.
This is false. Phobos has a lot of code that returns slightly different
types depending on what the input was. For example, .map returns a
random access range if the input is random access, a bidirectional /
forward / input range if that's that the input is, etc.. This is
perfectly normal.
It makes little sense to require, e.g., .map to always return, say, a
forward range even if you hand it an input range -- it wouldn't be able
to do this without introducing very inefficient code (like caching
entries so that it can implement .save). Phobos range adaptors should
always return the "best of input functionality", i.e., if the incoming
range has .save, then where reasonable the resulting range also should
have .save; ditto for opIndex, .back, .popBack, etc..
> Let's define the types: When calling iota(start,end,inc)
> S=typeof(start),
> E=typeof(end),
> I=typeof(inc),
> C=CommonType!(S,E).
>
> My proposal:
> iota(start, end, inc) accepts any type, as long as
> {C c; c += inc; c < end;} or {C c; c = c + inc; c < end;} is
> valid code;
>
> Since inc type might not be directly comparable to 0, we also check
> if (start + inc < start). If this returns true, this means that "inc
> is negative" in a more general sense.
I'm a bit uneasy about this, but I guess it's the price of completely
generic code, since you're right, there's no guarantee the inc type is
comparable to 0.
> We can use this information to return an empty range when needed,
> respecting the behaviour defined by the library reference. eg: (start
> < end && inc < 0) => return
> empty range.
>
> end is not required to be equal to (start + n*inc) for any given n;
> eg: iota(4, 9, 2) should be valid and return [4, 6, 8]. We can
> discuss if this makes sense or should be changed, but I think it
> would be better this way.
I think this way is better.
> If the code {int n; I n_inc = n * inc;} is valid, this instruction
> is used for providing O(1) access for opIndex and opSlice methods.
Yes.
> If the code {C c; c -= inc;} or {C c; c = c - inc} is valid, this
> instruction is used for providing O(1) access for popBack() method.
Yes.
> If no optimization is available, the code will provide O(n)
> performance for those methods.
No. If (start + n*inc) is not compilable, then iota should not be a
random-access range. I don't like the idea that iota[n] is O(1) for some
types and O(n) for other types.
> The real issue however is that construction of the range might end up
> taking O(n) time, because we have to provide the length and the back
> property. One work around is computing those lazily only if the
> user requests them.
No, if (start + n*inc) is not available, don't provide .length and don't
provide .back. Otherwise you're adding unnecessary baggage in the
returned range type for most code that don't care about .length or
.back.
> By doing this, anyone only using iota() for forward iteration will
> still obtain O(1) performance.
>
> iota(start, end) accepts any type, as long as
> {C c; ++c; c < end;} or {iota(start, end, 1);} is valid code. If
> both forms are valid, the iota(start, end, 1) version is preferred
> (allowing possible optimizations as discussed before).
> Everything else ends up being the same as before: popBack() can be
> optimized if {--c;} is valid code, the opIndex, opSlice, back and
> length methods will take O(n) time, no way around this sadly.
No, we should not implement any O(n) time methods in iota. If only ++ is
available in the base type, then .length, .back, opSlice, will not be
available. Basically, if the user type only supports ++, then in normal
user code they will not expect to compute length easily, or to be able
jump to over several consecutive values. So chances are that they won't
be using them with the range returned by iota either. So this will just
be unneeded added complexity in the iota implementation. I vote against
it.
> hsteoh suggested:
> If start+inc is *not* supported but start-- is, and end < start,
> should we support iota(start,end)?
> I think this idea should be discarded since some code could quickly
> become a minefield:
> type T implements ++t and --t;
> type P only implements ++p;
> t1 < t2 => iota(t2, t1) has a way to compute a non-empty range;
> p1 < p2 => iota(p2, p1) can do nothing but return an empty range;
> And this behaviour really smells bad, IMHO. The only way to solve
> this is requiring opUnary!"--" being implemented for the type to be
> used, and I am not sure about this (most iota uses only really need
> ++).
I think this part is optional, I won't miss it if it won't be not there,
actually. I only suggested it because I thought it would be nice to
support iota(a,b,-1) for types that don't have a way to specify inc. But
like you said, it's probably very rare for people to actually want to do
this.
> Any suggestion/critique? If this looks good to you, I can start
> working on it. If you disagree on something (and I know you have
> something to say!), discussion is more than welcome!
[...]
I think overall it looks good, except for the parts where you try to
implement .back, .length, opSlice, etc., when the underlying type
doesn't support it. I think that's unnecessary work. Just as we don't
expect sqrt() to return a meaningful value for -1 for real numbers, but
we *do* expect a meaningful value for complex numbers, so there's no
reason iota() must always return a RA range. If the user wants RA
access, then he should implement more primitives in his type, it's not
iota's job to do that for him.
Another thing to be mindful of is the current existing overloads of
iota. Your implementation should either be in distinct overloads from
them (so that they continue to work as they do now), or it should
subsume them and provide (at least) equivalent functionality, if not
better. In no case should existing functionality be broken by the new
replacement.
This sounds obvious but may be harder than it appears, because there's
an overload (or multiple overloads?) specifically for floating-point
types, and you'll have to take into account the quirks of floating-point
types to handle all the cases correctly. Keep in mind that if a float is
too large, iota() may not be able to return a meaningful range (e.g.,
x+inc may not have a distinct floating-point representation from x when
abs(x) is too big relative to inc). Also, what should be done if
mathematically x + n*inc == end exactly, but due to roundoff error it
misses by a few ulps. Then iota() may have different lengths depending
on CPU (e.g. 80-bit real vs. 128-bit real), rounding flags, etc., and
things could get hairy. You might want to keep the floating-point
overload(s) of iota as-is to avoid having to deal with this mess. :)
T
--
One disk to rule them all, One disk to find them. One disk to bring them all
and in the darkness grind them. In the Land of Redmond where the shadows lie.
-- The Silicon Valley Tarot
