On Monday, 29 October 2012 at 15:48:47 UTC, Andrei Alexandrescu wrote:
> On 10/29/12 11:43 AM, monarch_dodra wrote:
>>
>> I think you missed the point
>
> ... which I think Dmitry destroyed.
>
> Andrei

The only point he contested was the optimization opportunities in std.algorithm.

I agree that optimization opportunities are not enough to warrant new concepts, but that wasn't my main point. But they are there is what I was saying.

(PS: There is currently a pull request for making copy exploit doubly RA ranges)

--------
My main point is that slicing a range to its end *is* something important, and we currently have nothing to provide this functionality, when we could (easily).

The argument: "I'm thinking that simply defining an opDollar to return
special marker type and overloading opSlice should work", works, but brings its own issues to the table.

Inside template code, it would render hasSlicing *even more* complex: If an infinite range indeed has slicing, then what exactly does it mean?
- Does it mean you can slice between two indexes?
- Does it guarantee you can slice to the end with opDollar?
- Does it mean you can do both?
- Would it imply that "r[0 .. 1]" would have a different type from "r[0 .. $]" ?;
- Would it imply that "r = r[0 .. $]" is legal?
- What about that "r = r[0 .. 10]"?

And still, that'd be if anybody actually used opDollar... *cough*

--------
The solution I'm proposing barely requires anything new we don't already have (popFrontN).

I'm saying we can exploit the existence of this method to clearly separate the two (currently conflicting) notions of slicing we currently have:

*On one hand, we can have the "hasSlicing" ranges, where can clearly write "r = r[0 .. 10];" any day of the week, no matter the range.

*On the other end, we'd have "isDroppable", which would give you two limited features for those ranges that don't satisfy hasSlicing:
**Slice to end with guaranteed assignability to original "r = r.drop(10);"
**Extract a slice, but with the explicit notion you *won't* get back-assignability "auto myNewSlice = r.extractSlice(0, 10);"

Note that this "extractSlice" notion would save a bit of functionality for immutable ranges which *would* have slicing, but since they don't support assign, don't actually verify hasSlicing...

10/29/2012 5:40 PM, monarch_dodra пишет:
> On Monday, 29 October 2012 at 15:48:47 UTC, Andrei Alexandrescu wrote:
>> On 10/29/12 11:43 AM, monarch_dodra wrote:
>>>
>>> I think you missed the point
>>
>> ... which I think Dmitry destroyed.
>>
>> Andrei
>
I'd clarify that I'm not against the _trait_ itself. isDroppable.
The name doesn't sit well with me but the idea to test if range supports limited form of slicing i.e. a[x..$]  is a good idea.
I'd call it limited slicing or one-side slicing.

Everything else in the post - a distinctive no.

> The only point he contested was the optimization opportunities in
> std.algorithm.
>

That was an observation. I'm curious how many things you can sensibly do with infinite range directly (no take, takeExactly) that would benefit from being able to iterate them by common index. I have reasons to believe the set is small at best.

> I agree that optimization opportunities are not enough to warrant new
> concepts, but that wasn't my main point. But they are there is what I
> was saying.
>
> (PS: There is currently a pull request for making copy exploit doubly RA
> ranges)
Yeah, that's mine...

Now the challenge.
Quick! How many infinite RA ranges with assignable elements we have in Phobos presently?

> --------
> My main point is that slicing a range to its end *is* something
> important, and we currently have nothing to provide this functionality,
> when we could (easily).
>
> The argument: "I'm thinking that simply defining an opDollar to return
> special marker type and overloading opSlice should work", works, but
> brings its own issues to the table.
>
> Inside template code, it would render hasSlicing *even more* complex: If
> an infinite range indeed has slicing, then what exactly does it mean?

Basically it wasn't defined precisely. And I don't see how problematic it is to refine the definition.

> - Does it mean you can slice between two indexes?
> - Does it guarantee you can slice to the end with opDollar?
> - Does it mean you can do both?
> - Would it imply that "r[0 .. 1]" would have a different type from "r[0
> .. $]" ?;
> - Would it imply that "r = r[0 .. $]" is legal?
> - What about that "r = r[0 .. 10]"?
>
I'll comment more on these at the bottom. The gist is:

All of this boils down to one question adding a popFrontN can't solve: semantics of slicing an Infinite range on 2 indexes. Everything else is trivial to nail down.

> And still, that'd be if anybody actually used opDollar... *cough*

Introducing a new hook for programmers to implement because currently opDollar isn't used (and I told you why) is a bad idea. It is making a new *convention* that is bypassing an existing one built-in into the language.

> --------
> The solution I'm proposing barely requires anything new we don't already
> have (popFrontN).

It requires something new from users. Implement another way to slice a range. While presently popFrontN already works in O(1) for stuff that has [x..$] slicing.
Put it another way: library solutions arenice and usable as long as it blends with the core language. Let's not repeat the (few) mistakes of STL.

>
> I'm saying we can exploit the existence of this method to clearly
> separate the two (currently conflicting) notions of slicing we currently
> have:
>
> *On one hand, we can have the "hasSlicing" ranges, where can clearly
> write "r = r[0 .. 10];" any day of the week, no matter the range.
>
> *On the other end, we'd have "isDroppable", which would give you two
> limited features for those ranges that don't satisfy hasSlicing:
> **Slice to end with guaranteed assignability to original "r = r.drop(10);"

So all of the above can be put into the following 2 statements:
- all RA ranges have $ that is the end of range
- a slice is self-assignable in any case
- Infinite range just plain can't support slicing on 2 indexes (they have limited slicing, or one side slicing not full slicing)

I'd argue that any RA range can support slicing simply because supporting popFront/popBack is required. I believe there are no precedents where implementing these won't avail to:
a) adding a start, end indexes on top of the underlying RA payload
b) using some kind of random access pointer(s) provided natively

For Infinite ranges hasSlicing is false, limitedSlicing (isDropable) is true.

So I suggest we make the function popFrontN more clever w.r.t infinite ranges with limited form of slicing. That's all. And you are correct to notice it's misses an optimization in this case. And the constraint should be fixed to isDroppable/limitedSlicing.

It's a losing battle to add fixed range slicing to InfiniteRange.
Arguably for infinite ranges the way to slice is:
a[x..y] ---> a.drop(x).takeExactly(y-x)

Because it doesn't have full slicing that is hasSlicing. Clear as a day.
Note that drop(x) will get the speed up.

> **Extract a slice, but with the explicit notion you *won't* get
> back-assignability "auto myNewSlice = r.extractSlice(0, 10);"
>
Another primitive or is that UFCS in the work? Now when to use it? I'd hate to see everything turning from
a[x..y]
to
a.extractSlice(x, y)
in generic code. Just because a lot of code doesn't need a slice to have the exact same type.
(I'm just following the simple rule of generic programming: if you don't require something - avoid using it)

> Note that this "extractSlice" notion would save a bit of functionality
> for immutable ranges which *would* have slicing, but since they don't
> support assign, don't actually verify hasSlicing...

immutable ranges is purely a theoretical notion. (immutable elements are on the contrary are ubiquitous)

-- 
Dmitry Olshansky

On Monday, 29 October 2012 at 19:20:34 UTC, Dmitry Olshansky wrote:
> [SNIP]

I'll need some time to fully digest your points. Thank you for the full reply.

I'd like Jonathan's opinions on this too, he is knee deep in hasSlicing right now...

On Monday, October 29, 2012 20:26:38 Dmitry Olshansky wrote:
> Need to ping Jonathon about it and work out something.

I believe that Microsoft did something stupid with one of their functions which makes it function slightly differently around a DST switch on Windows 8 than it used to, so the unit tests fail when verifying that the times come out correctly around a DST switch (since they don't anymore on Windows 8). But I haven't had time yet to thoroughly investigate what exactly is causing it. Microsoft definitely sucks when it comes to time-handling stuff, but they're usually better about backwards compatibility than they appear to have been here.

- Jonathan M Davis

Jonathan M Davis wrote:
> On Monday, October 29, 2012 20:26:38 Dmitry Olshansky wrote:
> > Need to ping Jonathon about it and work out something.
> 
> I believe that Microsoft did something stupid with one of their functions which makes it function slightly differently around a DST switch on Windows 8 than it used to, so the unit tests fail when verifying that the times come out correctly around a DST switch (since they don't anymore on Windows 8). But I haven't had time yet to thoroughly investigate what exactly is causing it. Microsoft definitely sucks when it comes to time-handling stuff, but they're usually better about backwards compatibility than they appear to have been here.

I find it amazing how many bugs your unittests catch.

Jens

On Monday, October 29, 2012 21:56:36 Jens Mueller wrote:
> I find it amazing how many bugs your unittests catch.

That's why they're there. It's far too easy to miss a corner case and end up with mostly working but still buggy code (especially with date/time stuff). At one point, I had a bug with B.C. years that ended in 99 that I only caught when I made some of the tests more thorough. Being thorough seems to be the only way to catch all those sorts of problems. And in spite of all of that, I've still had a bug or two in the calculations when it was merged into Phobos (long since fixed).

DST switches are particularly nasty though, particularly since Microsoft absolutely sucks at time stuff, including the fact that it has a pitifully small number of time zones, and most of them are wrong. Testing that stuff across platforms is a major PITA, but I've tried very hard to guarantee that the behavior is the same across systems. Unfortunately, it looks like I'm going to have to spend some time figuring out how to hack around Windows 8's stupidity though.

- Jonathan M Davis

On Monday, 29 October 2012 at 19:20:34 UTC, Dmitry Olshansky wrote:
>> **Extract a slice, but with the explicit notion you *won't* get
>> back-assignability "auto myNewSlice = r.extractSlice(0, 10);"
>>
> Another primitive or is that UFCS in the work?

That's just UFCS, not another primitive.

> Now when to use it? I'd hate to see everything turning from
> a[x..y]
> to
> a.extractSlice(x, y)
> in generic code. Just because a lot of code doesn't need a slice to have the exact same type.
> (I'm just following the simple rule of generic programming: if you don't require something - avoid using it)

Yes, that's a good point.

>> Note that this "extractSlice" notion would save a bit of functionality
>> for immutable ranges which *would* have slicing, but since they don't
>> support assign, don't actually verify hasSlicing...
>
> immutable ranges is purely a theoretical notion. (immutable elements are on the contrary are ubiquitous)

Not *that* theoretical when you think about it. ascii's "digits" etc are all immutable ranges. They are a bad example, because they are strings (ergo un-sliceable), but as a rule of thumb, any global container can be saved as an immutable range. For example, I could define "first 10 integers" as an immutable range. That range would be slice-able, but would not verify "hasSlicing".

--------
The way I see it, maybe a beter solution would be a refinement of:

*hasSlicing:
**r = r[0 .. 1]; MUST work (so infinite is out)
*hasEndSlicing
**r = r[1 .. $]; Must work (intended for infinite, or to verify opDollor)

To which we could add "limited" variants: "hasLimitedSlicing" and "hasLimitedEndSlicing", which would *just* mean we can extract a slice, but not necessarily re-assign it.

This seems like a simple but efficient solution. Thoughts?

--------
The issue that I still have with slicing (between to indexes) infinite ranges is that even on an implementation stand point, it makes little sense. There is little other way to implement it other than "return this[i .. $].takeExactly(j - i);" In which case, it would make little sense to require it as a primitive.

I'd rather have a global function in range.d, that would provide the implementation for any infinite range that provides has[Limited]EndSlicing.

10/30/2012 6:53 AM, monarch_dodra пишет:
> On Monday, 29 October 2012 at 19:20:34 UTC, Dmitry Olshansky wrote:
>>> Note that this "extractSlice" notion would save a bit of functionality
>>> for immutable ranges which *would* have slicing, but since they don't
>>> support assign, don't actually verify hasSlicing...
>>
>> immutable ranges is purely a theoretical notion. (immutable elements
>> are on the contrary are ubiquitous)
>
> Not *that* theoretical when you think about it. ascii's "digits" etc are
> all immutable ranges. They are a bad example, because they are strings
> (ergo un-sliceable), but as a rule of thumb, any global container can be
> saved as an immutable range.
> For example, I could define "first 10
> integers" as an immutable range. That range would be slice-able, but
> would not verify "hasSlicing".
>
You do make a common mistake of confusing a container and a range over it. Ranges are means of iteration, they are mutable by the very definition - every time you call popFront/popBack iteration state *changes*.

So you can't pop first item of "first 10 integers". It's an immutable entity that you can't manipulate.

In that sense slicing such an entity (container) is the way of extracting a _mutable_ range from it. Yet numbers it cycles through are immutable.

> --------
> The way I see it, maybe a beter solution would be a refinement of:
>
> *hasSlicing:
> **r = r[0 .. 1]; MUST work (so infinite is out)
> *hasEndSlicing
> **r = r[1 .. $]; Must work (intended for infinite, or to verify opDollor)
>

I suggest to stop there. In other words introduce hasEndSlicing (awful name) and check self-assignabliity of both.

> To which we could add "limited" variants: "hasLimitedSlicing" and
> "hasLimitedEndSlicing", which would *just* mean we can extract a slice,
> but not necessarily re-assign it.

This repeats the same argument of extractSlice albeit differently.

> This seems like a simple but efficient solution. Thoughts?

It's not simple. I suggest we drop the no self-assignable slicing altogether.

I claim that *if* you can't self assign a slice of a range it basically means that you are slicing something that is not meant to be a range but rather a container (adapter etc.).

> --------
> The issue that I still have with slicing (between to indexes) infinite
> ranges is that even on an implementation stand point, it makes little
> sense. There is little other way to implement it other than "return
> this[i .. $].takeExactly(j - i);" In which case, it would make little
> sense to require it as a primitive.
>
Yup like I told:
- Infinite range just plain can't support slicing on 2 indexes (they have limited slicing, or one side slicing not full slicing)

It's just I suggested to exclude opSlice(x,y) from primitives unlike in my first post where I didn't think of solving self-assigning problem.

> I'd rather have a global function in range.d, that would provide the
> implementation for any infinite range that provides has[Limited]EndSlicing.
>
Maybe though the utility of such a helper is limited (pun intended).


-- 
Dmitry Olshansky

On Monday, October 29, 2012 15:33:00 monarch_dodra wrote:
> More often than not, we want to slice a range all the way to the end, and we have to use the clumsy "r[0 .. r.length]" syntax.
>
> What's worst is that when a range is infinite, there is no real way to "slice to the end", unless you just repeatedly popFront.

As already pointed out, this is solved by opDollar. We don't have a trait for
it, but it can be tested for easily enough by doing something like
typeof(is(r[0 .. $])) or __traits(compiles, r[0 .. $]). We may still want to
create a trait for it though (e.g. hasOpDollar).

> I'd like to introduce a new primitive: "popFrontN". You may recognize this as a standalone function if range.d: It is. I propose we improve this semantic by allowing ranges to directly implement this function themselves.

They can do so already, and if UFCS is used, then their version will be used. We _could_ go a step further and make it so that popFrontN calls a range's popFrontN if it has one to make it so that it's always used if it exists. The main problem is that you can't rely on the complexity of popFrontN being better than O(n), because that's what it's going to be with non-sliceable ranges. A trait such as isDroppable would fix that, but it's really only an issue with infinite ranges.

Finite ranges which could have n elements popped in O(1) would be sliceable anyway, meaning that popFrontN would be O(1) for them already and that if a function requires popping n elements in O(1), it can just slice the range. So, isDroppable buys us nothing for finite ranges. The only gain that I really see here is that it would provide a way for infinite ranges to pop off their first n elements and still be infinite. As it stands, the best that you can do is slice them, but that has to result in another range type, because a finite slice can't be infinite.

However, if we take advantage of opDollar, then I think we can solve the problem that way. By using opDollar when slicing an infinite range, you should be able to keep the original range type. That being the case, I don't think that isDroppable is really necessary. Howevere, it _does_ mean that I should probably adjust my pull for hasSlicing so that it tests that slicing an infinite range with opDollar returns the original type (assuming that opDollar compiles for it). Of course, once opDollar works (I don't know what it's current state is), it would be desirable to require it to work with slicing anyway, so maybe hasSlicing should have that requirement added at a later date.

- Jonathan M Davis

----
On Tuesday, 30 October 2012 at 17:49:20 UTC, Dmitry Olshansky
wrote:
> 10/30/2012 6:53 AM, monarch_dodra пишет:
>> Not *that* theoretical when you think about it. ascii's "digits" etc are
>> all immutable ranges. They are a bad example, because they are strings
>> (ergo un-sliceable), but as a rule of thumb, any global container can be
>> saved as an immutable range.
>> For example, I could define "first 10
>> integers" as an immutable range. That range would be slice-able, but
>> would not verify "hasSlicing".
>>
> You do make a common mistake of confusing a container and a range over it. Ranges are means of iteration, they are mutable by the very definition - every time you call popFront/popBack iteration state *changes*.
>
> So you can't pop first item of "first 10 integers". It's an immutable entity that you can't manipulate.
>
> In that sense slicing such an entity (container) is the way of extracting a _mutable_ range from it. Yet numbers it cycles through are immutable.

Yes, that is quite true. Although in this case, the slice is both
container and range.

>> --------
>> The way I see it, maybe a beter solution would be a refinement of:
>>
>> *hasSlicing:
>> **r = r[0 .. 1]; MUST work (so infinite is out)
>> *hasEndSlicing
>> **r = r[1 .. $]; Must work (intended for infinite, or to verify opDollor)
>>
>
> I suggest to stop there. In other words introduce hasEndSlicing (awful name) and check self-assignabliity of both.
>
>> To which we could add "limited" variants: "hasLimitedSlicing" and
>> "hasLimitedEndSlicing", which would *just* mean we can extract a slice,
>> but not necessarily re-assign it.
>
> This repeats the same argument of extractSlice albeit differently.

Well, in my mind, the argument was the opposite, it would mean
you'd be able to write r[i..j] simply (as opposed to
r.extractSlice(i, j)).

>> This seems like a simple but efficient solution. Thoughts?
>
> It's not simple. I suggest we drop the no self-assignable slicing altogether.
>
> I claim that *if* you can't self assign a slice of a range it basically means that you are slicing something that is not meant to be a range but rather a container (adapter etc.).

That *would* make things simpler. I guess that's a good way of
seeing it.

----
On Wednesday, 31 October 2012 at 04:53:00 UTC, Jonathan M Davis
wrote:
>
> As already pointed out, this is solved by opDollar. We don't have a trait for
> it, but it can be tested for easily enough by doing something like
> typeof(is(r[0 .. $])) or __traits(compiles, r[0 .. $]). We may still want to
> create a trait for it though (e.g. hasOpDollar).

In my defense, I started thinking about this back when opDollar
didn't work at all.

> However, if we take advantage of opDollar, then I think we can solve the
> problem that way. By using opDollar when slicing an infinite range, you should
> be able to keep the original range type. That being the case, I don't think
> that isDroppable is really necessary.

Yes, in that context, that would also work (but had not thought
of this).

BTW: Once you are done, maybe you could present here what it
means exactly to be slice-able? AFAIK, your current proposal
allows for infinite ranges to verify "hasSlicing", if they can be
sliced between [a ... b], whereas Dmitry seems to think that
should not be so. At all.

----
Well in conclusion, sorry to have brought a crappy solution :/ I
guess we had something simple all along...

----
Whilst were on the subject of opDollar, and how it can solve all
of our problems, could one of you two maybe answer the questions
in this thread?
http://forum.dlang.org/thread/ehywdvmcmgyawgzfpytn@forum.dlang.org