March 12, 2013
On Tue, 12 Mar 2013 06:49:56 -0400, monarch_dodra <monarchdodra@gmail.com> wrote:

> On Tuesday, 12 March 2013 at 10:01:38 UTC, deadalnix wrote:
>> I want to resurrect that thread. Can someone explains the benefices of isInfinite ? I fail to see how it really benefit the code.
>
> The advantage of "enum empty = false" is that algorithms gain a great performance boost by optimizing out any "if (r.empty)". This can be exploited for things like take, or anything that iterates as a matter of fact. I don't think anybody will argue that this is a bad approach.

Wouldn't it automatically be optimized out?  I mean if r.empty is an enum, it's like saying if(false)  I would think even with optimizations off, this might be done.

Not that I'm questioning the value of isInfinite (I'm neutral on it), but this is not a benefit.

-Steve
March 12, 2013
On Tuesday, 12 March 2013 at 14:30:00 UTC, Steven Schveighoffer wrote:
> On Tue, 12 Mar 2013 06:49:56 -0400, monarch_dodra <monarchdodra@gmail.com> wrote:
>
>> On Tuesday, 12 March 2013 at 10:01:38 UTC, deadalnix wrote:
>>> I want to resurrect that thread. Can someone explains the benefices of isInfinite ? I fail to see how it really benefit the code.
>>
>> The advantage of "enum empty = false" is that algorithms gain a great performance boost by optimizing out any "if (r.empty)". This can be exploited for things like take, or anything that iterates as a matter of fact. I don't think anybody will argue that this is a bad approach.
>
> Wouldn't it automatically be optimized out?  I mean if r.empty is an enum, it's like saying if(false)  I would think even with optimizations off, this might be done.
>
> Not that I'm questioning the value of isInfinite (I'm neutral on it), but this is not a benefit.
>
> -Steve

Right, that's what I said. This first paragraph was just about enum empty = false.

The actual "isInfinite" discussion comes later.

Another point: isInfinite is useful, if only to propagate infiniteness. For example: "1.repeat().map"a * 2"()". If "map" didn't know that repeat is infinite, it would simply provide the "dumb" empty implementation, and the final range will have lost it's infinite trait.
March 12, 2013
On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:
> On Tuesday, 12 March 2013 at 10:01:38 UTC, deadalnix wrote:
>> I want to resurrect that thread. Can someone explains the benefices of isInfinite ? I fail to see how it really benefit the code.
>
> The advantage of "enum empty = false" is that algorithms gain a great performance boost by optimizing out any "if (r.empty)". This can be exploited for things like take, or anything that iterates as a matter of fact. I don't think anybody will argue that this is a bad approach.
>

I think the point is moot for the same reason it is for SentinelRange. A function that return false will be inlined and the whole if optimized away anyway. Same goes for a constant.

I'm not talking about a supposed sufficiently smart compiler, but actual compiler that exist right now.

> The trait itself checks if empty can be evaluated at compile time (to false). The advantage for the *coder* to know if the range is infinite is less obvious.
>
> One of the advantages is that an infinite range can have random access (meets RA requirements), even though it has no length member (normally, any RA range must have length).
>
> Having "isInfinite" can also have the advantage of protecting users from stupid calls. For example, calling "count" on an infinite range is forbidden => shifting problems from runtime to compile time is a HUGE gain.
>

Clearly this is a good point. I however think that a static assert within count is much better because it allow to give nicer feedback. The problem with InfiniteRange is that it does gives you cryptic error message like the count function do not exists.

> One of downsides to having infinite ranges is that their existence tends to make dealing with generic RA ranges a bit more difficult. A lot of our algorithms have changed requirements conditions from:
> "if (isRandomAccessRange!R)"
> to
> "if (isRandomAccessRange!R && hasLength!R)"
> or
> "if (isRandomAccessRange!R && !isInfinite!R)"
> //NOTE: Both are strictly equivalent: An RA range is either infinite, or has length, but not neither nor both.
>
> Up until not so long ago, it was not possible to slice infinite ranges. It is now possible. Unfortunatly, because RA ranges with slicing don't guarantee that r[0 .. $] is legal, things are still complicated in template code.
>

I conclude that the fix introduced complexity without solving the problem, just pushing the limit. I think we should avoid this kind of stuff.

> The last point (IMO minor) that is raised in the thread is "runtime" infiniteness. EG: a range that may or may not be infinite at compile time, but which will be known at runtime. IMO, these a rare enough (arguably, inexistent) to not really matter. The workarounds are easy:
> 1) Make the range always infinite, but with a requirement that user must intialize it or whatnot.
> 2) Make a runtime fork that will call code that operates on a compile-time known infinite adaptor/subtype.

A common case is unknown "infinitivenes".
March 12, 2013
On Tue, 12 Mar 2013 11:02:43 -0400, monarch_dodra <monarchdodra@gmail.com> wrote:

> On Tuesday, 12 March 2013 at 14:30:00 UTC, Steven Schveighoffer wrote:
>> On Tue, 12 Mar 2013 06:49:56 -0400, monarch_dodra <monarchdodra@gmail.com> wrote:
>>
>>> On Tuesday, 12 March 2013 at 10:01:38 UTC, deadalnix wrote:
>>>> I want to resurrect that thread. Can someone explains the benefices of isInfinite ? I fail to see how it really benefit the code.
>>>
>>> The advantage of "enum empty = false" is that algorithms gain a great performance boost by optimizing out any "if (r.empty)". This can be exploited for things like take, or anything that iterates as a matter of fact. I don't think anybody will argue that this is a bad approach.
>>
>> Wouldn't it automatically be optimized out?  I mean if r.empty is an enum, it's like saying if(false)  I would think even with optimizations off, this might be done.
>>
>> Not that I'm questioning the value of isInfinite (I'm neutral on it), but this is not a benefit.
>>
>> -Steve
>
> Right, that's what I said. This first paragraph was just about enum empty = false.

Oh, ok.  When you said "optmizing out" I thought you meant using isInfinite to optionally remove calls to empty by hand.

> Another point: isInfinite is useful, if only to propagate infiniteness. For example: "1.repeat().map"a * 2"()". If "map" didn't know that repeat is infinite, it would simply provide the "dumb" empty implementation, and the final range will have lost it's infinite trait.

With inlining, this should propagate properly:

struct WrapperRange(R)
{
   R src;
   @property auto front() { return src.front;}
   @property bool empty() { return src.empty;} // should be optimized to 'false' with inlining
   void popFront() { src.popFront();}
}

If R's empty is an enum, then WrapperRange's empty should inline to the enum also.

-Steve
March 12, 2013
On Tuesday, 12 March 2013 at 15:02:44 UTC, monarch_dodra wrote:
> Right, that's what I said. This first paragraph was just about enum empty = false.
>
> The actual "isInfinite" discussion comes later.
>
> Another point: isInfinite is useful, if only to propagate infiniteness. For example: "1.repeat().map"a * 2"()". If "map" didn't know that repeat is infinite, it would simply provide the "dumb" empty implementation, and the final range will have lost it's infinite trait.

That will always be optimized away without trouble by existing compilers. You'd loose the character of infinitness, but it seems to me like a lot of trouble as it add a whole class of things to consider when implementing wrapper ranges, for benefice that you can already get most of the time.

Note that something like computeIfCTFEable!(r.empty, true) would be much more beneficial than the actual implementation.
March 12, 2013
On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix <deadalnix@gmail.com> wrote:

> On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:

>> Having "isInfinite" can also have the advantage of protecting users from stupid calls. For example, calling "count" on an infinite range is forbidden => shifting problems from runtime to compile time is a HUGE gain.
>>
>
> Clearly this is a good point. I however think that a static assert within count is much better because it allow to give nicer feedback. The problem with InfiniteRange is that it does gives you cryptic error message like the count function do not exists.
>

Hm... is there a way to test for inifinitness without requiring to be an enum?

Wouldn't this also be valid?

if(!R.init.empty)

Essentially, you can evaluate R.init.empty at compile time AND it's false on an uninitialized range.  How can a correctly written non-infinite range pass that?

That would make forwarding much easier, as the 'dumb' implementation still would result in an infinite range.

-Steve
March 12, 2013
On 3/12/13 11:47 AM, Steven Schveighoffer wrote:
> On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix <deadalnix@gmail.com> wrote:
>
>> On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:
>
>>> Having "isInfinite" can also have the advantage of protecting users
>>> from stupid calls. For example, calling "count" on an infinite range
>>> is forbidden => shifting problems from runtime to compile time is a
>>> HUGE gain.
>>>
>>
>> Clearly this is a good point. I however think that a static assert
>> within count is much better because it allow to give nicer feedback.
>> The problem with InfiniteRange is that it does gives you cryptic error
>> message like the count function do not exists.
>>
>
> Hm... is there a way to test for inifinitness without requiring to be an
> enum?
>
> Wouldn't this also be valid?
>
> if(!R.init.empty)
>
> Essentially, you can evaluate R.init.empty at compile time AND it's
> false on an uninitialized range. How can a correctly written
> non-infinite range pass that?
>
> That would make forwarding much easier, as the 'dumb' implementation
> still would result in an infinite range.

Crossed my mind a few times that fresh non-infinite ranges should be empty. But there's no explicit requirement stating that, and I think e.g. one may define a k-elements buffer backed by in-situ storage.

Andrei
March 12, 2013
On Tue, 12 Mar 2013 12:16:10 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 3/12/13 11:47 AM, Steven Schveighoffer wrote:
>> On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix <deadalnix@gmail.com> wrote:
>>
>>> On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:
>>
>>>> Having "isInfinite" can also have the advantage of protecting users
>>>> from stupid calls. For example, calling "count" on an infinite range
>>>> is forbidden => shifting problems from runtime to compile time is a
>>>> HUGE gain.
>>>>
>>>
>>> Clearly this is a good point. I however think that a static assert
>>> within count is much better because it allow to give nicer feedback.
>>> The problem with InfiniteRange is that it does gives you cryptic error
>>> message like the count function do not exists.
>>>
>>
>> Hm... is there a way to test for inifinitness without requiring to be an
>> enum?
>>
>> Wouldn't this also be valid?
>>
>> if(!R.init.empty)
>>
>> Essentially, you can evaluate R.init.empty at compile time AND it's
>> false on an uninitialized range. How can a correctly written
>> non-infinite range pass that?
>>
>> That would make forwarding much easier, as the 'dumb' implementation
>> still would result in an infinite range.
>
> Crossed my mind a few times that fresh non-infinite ranges should be empty. But there's no explicit requirement stating that, and I think e.g. one may define a k-elements buffer backed by in-situ storage.

So something like this:

struct R
{
  int[4] elems;
  int idx;
  int front() { return elems[idx];}
  void popFront() {++idx;}
  bool empty() {idx < elems.length;}
}

which would make this an infinite range by my measurement.  Crap.

How can we make wrapping ranges easier?  I get the point that it's a pain in the ass in order to implement a wrapper for another range for things like isInfinite, and save.  We need something in std.range that allows you to wrap such functions, like a nice mixin.

-Steve
March 12, 2013
On Tuesday, 12 March 2013 at 16:16:07 UTC, Andrei Alexandrescu wrote:
> On 3/12/13 11:47 AM, Steven Schveighoffer wrote:
>> On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix <deadalnix@gmail.com> wrote:
>>
>>> On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:
>>
>>>> Having "isInfinite" can also have the advantage of protecting users
>>>> from stupid calls. For example, calling "count" on an infinite range
>>>> is forbidden => shifting problems from runtime to compile time is a
>>>> HUGE gain.
>>>>
>>>
>>> Clearly this is a good point. I however think that a static assert
>>> within count is much better because it allow to give nicer feedback.
>>> The problem with InfiniteRange is that it does gives you cryptic error
>>> message like the count function do not exists.
>>>
>>
>> Hm... is there a way to test for inifinitness without requiring to be an
>> enum?
>>
>> Wouldn't this also be valid?
>>
>> if(!R.init.empty)
>>
>> Essentially, you can evaluate R.init.empty at compile time AND it's
>> false on an uninitialized range. How can a correctly written
>> non-infinite range pass that?
>>
>> That would make forwarding much easier, as the 'dumb' implementation
>> still would result in an infinite range.
>
> Crossed my mind a few times that fresh non-infinite ranges should be empty.

s/should/could/

In any case, that's a very dangerous logic to follow. Not-initialized means not initialized. At that point, the concept of empty or not empty is irrelevant, it's a wrong call.

By the same token, I don't think anybody would expect a call to empty on a null class reference to actually succeed.

> But there's no explicit requirement stating that, and I think e.g. one may define a k-elements buffer backed by in-situ storage.
>
> Andrei

Not sure what you mean?
March 12, 2013
On Tue, 12 Mar 2013 12:32:22 -0400, monarch_dodra <monarchdodra@gmail.com> wrote:

> On Tuesday, 12 March 2013 at 16:16:07 UTC, Andrei Alexandrescu wrote:
>> On 3/12/13 11:47 AM, Steven Schveighoffer wrote:
>>> On Tue, 12 Mar 2013 11:25:54 -0400, deadalnix <deadalnix@gmail.com> wrote:
>>>
>>>> On Tuesday, 12 March 2013 at 10:49:57 UTC, monarch_dodra wrote:
>>>
>>>>> Having "isInfinite" can also have the advantage of protecting users
>>>>> from stupid calls. For example, calling "count" on an infinite range
>>>>> is forbidden => shifting problems from runtime to compile time is a
>>>>> HUGE gain.
>>>>>
>>>>
>>>> Clearly this is a good point. I however think that a static assert
>>>> within count is much better because it allow to give nicer feedback.
>>>> The problem with InfiniteRange is that it does gives you cryptic error
>>>> message like the count function do not exists.
>>>>
>>>
>>> Hm... is there a way to test for inifinitness without requiring to be an
>>> enum?
>>>
>>> Wouldn't this also be valid?
>>>
>>> if(!R.init.empty)
>>>
>>> Essentially, you can evaluate R.init.empty at compile time AND it's
>>> false on an uninitialized range. How can a correctly written
>>> non-infinite range pass that?
>>>
>>> That would make forwarding much easier, as the 'dumb' implementation
>>> still would result in an infinite range.
>>
>> Crossed my mind a few times that fresh non-infinite ranges should be empty.
>
> s/should/could/
>
> In any case, that's a very dangerous logic to follow. Not-initialized means not initialized. At that point, the concept of empty or not empty is irrelevant, it's a wrong call.

No, ranges can be initialized without a constructor.  Structs are.  Classes aren't.  But a class with empty as an enum would work.

The idea is that the ultimate underlying source of empty is an enum.  Since it's an enum, it should be calculable at compile-time, and it should always be false, regardless of the state of the range (invalid or valid).

The problem is whether NON-infinite ranges are empty or not.  Looks like there are cases where they could be non-empty.

> By the same token, I don't think anybody would expect a call to empty on a null class reference to actually succeed.

If it's an enum, I would.  If it doesn't work, the constraint is false, which is what we want.

-Steve