[Submission] D Slices

[Timon Gehr]

eles wrote:
>> Is Python successful?
>>  >>> a = [0,1,2,3,4,5,6]
>>  >>> a[3:5]
>> [3, 4]
>
> Well, I am not a Python user, I give you credit for that. Actually, I
> don't really appreciate Python for its indentation choice, but that's
> a matter of taste.
>
>> In C++'s iterator concept, x.end() points to one position after the
> last
>> element, so the a "range" (x.begin(), x.end()) is has an open limit
> at
>> the end. Every C++ algorithm that operates on a pair of iterator
> take
>> use [...) range concept.
>
> That's a good point. I work in C, not in C++. I think it comes from:
>
> for(i=0; i<N; i++){}
>
> while other languages use more
>
> for(i=0; i<=N-1; i++){}

Indeed, but you agree that in that special case, the first one is better?

In C++ you cannot have the same for iterators, because iterators are not
necessarily ordered.

Eg:

map m;
/*fill map with values*/

for(map<int>::iterator it=m.begin();it!=m.end();++it){}

But that is not really important for D slices.

>
>> BTW, Ruby has both of them
>>  >> a = [0,1,2,3,4,5,6]
>> => [0, 1, 2, 3, 4, 5, 6]
>>  >> a[3..5]
>> => [3, 4, 5]
>>  >> a[3...5]
>> => [3, 4]
>
> So, they have studied the well established ground of using an open-
> right limit and... chose to implement the other way too. Good for
> them. But, if using right-open limit is the natural and established
> way... why then, the choice they made?

Probably because in different contexts both make sense.

Half-open intervals save you from many +-1 errors.

a very simple and archetypical example: binary search in array a for value v.

Assuming _closed_ slicing intervals:
while(a.length>1){
    a = v<=a[$/2] ? a[0..$/2] : a[$/2+1..$-1];
}

Do you see the bug? People do that all the time when implementing binary search.

Half-open slicing intervals (correct):
while(a.length>1){
    a = v<a[$/2] ? a[0..$/2] : a[$/2..$];
}

Half-open intervals encourage a correct implementation of binary search! They
cannot be that bad, right?

Well, I might have biased this display a little bit. Fact is, that many
programmers fail to implement binary search correctly. It can be assumed that most
of those use closed intervals for their l and h. It gets really simple once the
intervals are half-open. It is easier to reason about half-open intervals than
about closed intervals when indexes are 0-based.

Another valid reason is, that the slicing of half-open intervals can be done in
less machine instructions ;).

slicing with closed intervals:

b=a[i..j];
<=>
b.ptr:=a.ptr+i;
b.length:=j-i+1; // boom

slicing with half-open intervals:
b=a[i..j];
<=>
b.prt:=a.ptr+i;
b.length:=j-i; // nice!

When you want to have closed interval slicing, you do it by making the overhead
visible:

b=a[i..j+1];


Timon