View mode: basic / threaded / horizontal-split · Log in · Help
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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...
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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...
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
October 29, 2012
Re: "isDroppable" range trait for slicing to end
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
October 30, 2012
Re: "isDroppable" range trait for slicing to end
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.
October 30, 2012
Re: "isDroppable" range trait for slicing to end
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
October 31, 2012
Re: "isDroppable" range trait for slicing to end
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
October 31, 2012
Re: "isDroppable" range trait for slicing to end
----
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
1 2 3
Top | Discussion index | About this forum | D home