September 18, 2011
On Sun, 18 Sep 2011 22:32:44 +0200, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 9/18/11 3:19 PM, dsimcha wrote:
>> On 9/18/2011 4:09 PM, Andrei Alexandrescu wrote:
>>> opDollar is more powerful because it can be made to work with infinite
>>> ranges.
>>>
>>> Andrei
>>
>> Yes, this is important. IMHO, though, the default behavior of the $
>> operator should be to call range.length if it exists and opDollar isn't
>> explicitly overloaded. This would save a lot of boilerplate.
>
> struct MyRange
> {
>    ...
>    alias length opDollar;
> }
>
> I do agree that most of the time this is what you want anyway, so that line would occur a lot of times...

This works if opDollar is expected to be a niladic function. For multi-
dimensional structures, it would have to be monadic.

-- 
  Simen
September 18, 2011
On Sun, 18 Sep 2011 22:37:03 +0200, Timon Gehr <timon.gehr@gmx.ch> wrote:

> On 09/18/2011 10:21 PM, dsimcha wrote:
>> On 9/18/2011 4:16 PM, Timon Gehr wrote:
>>> What would it return?
>>
>> A dummy type, e.g.:
>>
>> struct Repeat(T) {
>> T val;
>> T front() @property { return val; }
>> void popFront() {}
>> enum empty = false;
>>
>> static struct Dollar {}
>> Dollar opDollar() {
>> return Dollar.init;
>> }
>>
>>
>> auto opSlice(size_t lower, Dollar dollar) { return this; }
>> }
>>
>> void main() {
>> auto r = Repeat!int(1);
>> auto r2 = r[666..$];
>> }
>
> Ok, but what about
>
> void main(){
>      auto r = Repeat!int(1);
>      auto r2 = r[666..$-1]; // ok, return entire range
>      auto r3 = r[666..$/2]; // ditto
>      auto r4 = r[666..$<100?$:100]; // ???

Compile-time error. struct Dollar does not have an overloaded <
operator. Or you make one that always returns false, in which case
things are a bit more complex (Dollar and 100 do not have a common
type).


>      // those could be made illegal:
>      auto r5 = r[666..$*0]; // ???
>      auto r6 = r[666..$-$]; // ???
>      auto r7 = r[666..2*$-$]; // ???
>      auto r8 = r[666..($*$)%4==3?667:668]; // ???
> }

They already are. The supplied Dollar struct does not have overloaded
operators for any of those operations. If you implement them, you can
have them do whatever you feel is right.

-- 
  Simen
September 18, 2011
On 9/18/2011 4:32 PM, Andrei Alexandrescu wrote:
> struct MyRange
> {
> ...
> alias length opDollar;
> }
>
> I do agree that most of the time this is what you want anyway, so that
> line would occur a lot of times...
>
>
> Andrei

The problem with this is that everything in std.algorithm and std.range would have to be manually changed.  I don't feel like doing this myself or waiting for someone else to get around to it.  It just makes a heck of a lot more sense to specify it in one place, in the compiler.
September 19, 2011
On Sun, 18 Sep 2011 16:16:23 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:

> On 09/18/2011 10:09 PM, Andrei Alexandrescu wrote:
>> On 9/18/11 2:46 PM, Nick Sabalausky wrote:
>>> "Timon Gehr"<timon.gehr@gmx.ch> wrote in message
>>> news:j55h4f$1ia5$1@digitalmars.com...
>>>>
>>>>> The only advantages slices have left
>>>>> are (a) type syntax, i.e. T[] instead of Slice!T, (b) literal syntax,
>>>>> i.e. [ 1, 2, 3 ] instead of slice(1, 2, 3), and (c) a couple of stray
>>>>> language bugs such as '$'.
>>>>
>>>> I am thankful for $, as it is a great feature, and it really should be
>>>> made accessible to user defined types. Either through opDollar or the
>>>> rewrite a[foo($)] => a[foo(a.length)]. What makes it qualify as a stray
>>>> language bug to you?
>>>>
>>>
>>> He's saying that one of the few advantages slices have left over
>>> user-defined types is that, for slices, $ actually works. The bug is
>>> that it
>>> doesn't work for user-defined types.
>>>
>>> FWIW, I like the rewrite idea far better than opDollar.
>>
>> opDollar is more powerful because it can be made to work with infinite
>> ranges.
>>
>> Andrei
>
> What would it return?

Not all types that have an end also support .length, or use sequential integers for indexes.

-Steve
September 19, 2011
On Sun, 18 Sep 2011 15:34:16 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:

> On 09/18/2011 08:28 PM, Andrei Alexandrescu wrote:
>> That would allow us to e.g. switch from the
>> pointer+length representation to the arguably better pointer+pointer
>> representation with ease.
>
> In what way is that representation better?

I agree, I don't see why the representation is inherently better.  Some operations become higher performance (i.e. popFront), and some become worse (i.e. length).  Most of the others are a wash.

FWIW, you can avoid bloat by converting to runtime calls when templating is not necessary.  For example, append could just be a template shell:

opBinary(string op : "~=")(T other)
{
   return _d_appendTi(...) // don't remember the parameter types/order
}

In any case, before this could happen, we'd need to implement UFCS for custom types, and we'd need a solution on how to specify const(T)[] using a template (that implicitly casts from T[]).

-Steve
September 19, 2011
On 09/19/2011 01:25 PM, Steven Schveighoffer wrote:
> On Sun, 18 Sep 2011 15:34:16 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:
>
>> On 09/18/2011 08:28 PM, Andrei Alexandrescu wrote:
>>> That would allow us to e.g. switch from the
>>> pointer+length representation to the arguably better pointer+pointer
>>> representation with ease.
>>
>> In what way is that representation better?
>
> I agree, I don't see why the representation is inherently better. Some
> operations become higher performance (i.e. popFront), and some become
> worse (i.e. length). Most of the others are a wash.
>
> FWIW, you can avoid bloat by converting to runtime calls when templating
> is not necessary. For example, append could just be a template shell:
>
> opBinary(string op : "~=")(T other)
> {
> return _d_appendTi(...) // don't remember the parameter types/order
> }
>

Ok, but I'd like the opBinary to not even be put into the object file. I believe an @inline annotation that guarantees inlining or compilation failure if it is impossible would be of great use for this and other applications.

> In any case, before this could happen, we'd need to implement UFCS for
> custom types,

First of all, the design of UFCS for custom types has to be settled on. Should it be implicit like the current ad-hoc way for arrays or explicit (eg per a 'this' storage class) ? I would be in favor of an explicit solution.

> and we'd need a solution on how to specify const(T)[]
> using a template (that implicitly casts from T[]).
>

Even more than that, templates would need to be able to specify stuff like

// the fact that this currently compiles is a quite severe bug that compromises type/memory safety, it would have to be disallowed without an explicit cast:

class C{}
class D: C{}
class E: C{}

void main(){
    D[] d = [new D];
    C[] c = d;
    c[0] = new E;
    assert(typeid(d[0]) == typeid(E)); // a stray E in a D[]!
}

// this on the other hand is perfectly fine:
void main(){
    D[] d = [new D];
    const(C)[] c = d;
    // no possibility to screw up d. (no possibility to change the individual elements per method calls either)
}

As I pointed out in my initial post, I think the language changes to make something that works like a dynamic array implementable in a library would be quite involved, because there _is_ some nontrivial magic going on for them. Similar claims hold for pointers.

Probably having something ad-hoc, like an opImplicitCast, would work out, but it would share some functionality with alias this...

Still, imho the best solution is to keep dynamic arrays built in, whether or not their special features are made available to the programmer.


September 19, 2011
On 09/19/2011 01:15 PM, Steven Schveighoffer wrote:
> On Sun, 18 Sep 2011 16:16:23 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:
>
>> On 09/18/2011 10:09 PM, Andrei Alexandrescu wrote:
>>> On 9/18/11 2:46 PM, Nick Sabalausky wrote:
>>>> "Timon Gehr"<timon.gehr@gmx.ch> wrote in message
>>>> news:j55h4f$1ia5$1@digitalmars.com...
>>>>>
>>>>>> The only advantages slices have left
>>>>>> are (a) type syntax, i.e. T[] instead of Slice!T, (b) literal syntax,
>>>>>> i.e. [ 1, 2, 3 ] instead of slice(1, 2, 3), and (c) a couple of stray
>>>>>> language bugs such as '$'.
>>>>>
>>>>> I am thankful for $, as it is a great feature, and it really should be
>>>>> made accessible to user defined types. Either through opDollar or the
>>>>> rewrite a[foo($)] => a[foo(a.length)]. What makes it qualify as a
>>>>> stray
>>>>> language bug to you?
>>>>>
>>>>
>>>> He's saying that one of the few advantages slices have left over
>>>> user-defined types is that, for slices, $ actually works. The bug is
>>>> that it
>>>> doesn't work for user-defined types.
>>>>
>>>> FWIW, I like the rewrite idea far better than opDollar.
>>>
>>> opDollar is more powerful because it can be made to work with infinite
>>> ranges.
>>>
>>> Andrei
>>
>> What would it return?
>
> Not all types that have an end also support .length, or use sequential
> integers for indexes.
>
> -Steve

Yes, but D has already gone the 'being inflexible' path for the comparison/negation/logical/ternary operators. Isn't this a similar thing? I don't think infinite ranges work well with restrictive operator overloading. eg a[0..100<$?100:$]. They'd need some additional language support or they'll possibly blow up randomly on generic code.

Btw, do you know of an example of a data structure that can be indexed continuously and has the notion of an end, but no length?



September 19, 2011
On Mon, 19 Sep 2011 09:49:14 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:

> On 09/19/2011 01:15 PM, Steven Schveighoffer wrote:
>> On Sun, 18 Sep 2011 16:16:23 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:
>>
>>> On 09/18/2011 10:09 PM, Andrei Alexandrescu wrote:
>>>> On 9/18/11 2:46 PM, Nick Sabalausky wrote:
>>>>> "Timon Gehr"<timon.gehr@gmx.ch> wrote in message
>>>>> news:j55h4f$1ia5$1@digitalmars.com...
>>>>>>
>>>>>>> The only advantages slices have left
>>>>>>> are (a) type syntax, i.e. T[] instead of Slice!T, (b) literal syntax,
>>>>>>> i.e. [ 1, 2, 3 ] instead of slice(1, 2, 3), and (c) a couple of stray
>>>>>>> language bugs such as '$'.
>>>>>>
>>>>>> I am thankful for $, as it is a great feature, and it really should be
>>>>>> made accessible to user defined types. Either through opDollar or the
>>>>>> rewrite a[foo($)] => a[foo(a.length)]. What makes it qualify as a
>>>>>> stray
>>>>>> language bug to you?
>>>>>>
>>>>>
>>>>> He's saying that one of the few advantages slices have left over
>>>>> user-defined types is that, for slices, $ actually works. The bug is
>>>>> that it
>>>>> doesn't work for user-defined types.
>>>>>
>>>>> FWIW, I like the rewrite idea far better than opDollar.
>>>>
>>>> opDollar is more powerful because it can be made to work with infinite
>>>> ranges.
>>>>
>>>> Andrei
>>>
>>> What would it return?
>>
>> Not all types that have an end also support .length, or use sequential
>> integers for indexes.
>>
>> -Steve
>
> Yes, but D has already gone the 'being inflexible' path for the comparison/negation/logical/ternary operators. Isn't this a similar thing? I don't think infinite ranges work well with restrictive operator overloading. eg a[0..100<$?100:$]. They'd need some additional language support or they'll possibly blow up randomly on generic code.
>
> Btw, do you know of an example of a data structure that can be indexed continuously and has the notion of an end, but no length?

I was specifically thinking of red-black tree, which has a distinct end, but it's index is not necessarily length (or any value for that matter).

If you look at dcollections, you can slice a TreeMap using indexes or cursors.  However, to index through the last element in the tree, you use the special cursor .end:

auto range = mytree["hello" .. mytree.end]; // get all the elements in the tree which are >= "hello"

Here, mytree["hello" .. mytree.length] would simply not compile.

In addition, a tree with a uint index would silently do the *wrong* thing:

auto set = new TreeSet!uint(1, 3, 5, 7, 9);
assert(set.length == 5);
auto range = set[1..set.length];

assert(walkLength(range) == 2); // probably not what you expected

So I think it's not only limiting to require x.length to be $, it's very wrong in some cases.

Also, think of a string.  It has no length (well technically, it does, but it's not the number of elements), but it has a distinct end point.  A properly written string type would fail to compile if $ was s.length.

-Steve
September 19, 2011
On 9/19/11 6:25 AM, Steven Schveighoffer wrote:
> On Sun, 18 Sep 2011 15:34:16 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:
>
>> On 09/18/2011 08:28 PM, Andrei Alexandrescu wrote:
>>> That would allow us to e.g. switch from the
>>> pointer+length representation to the arguably better pointer+pointer
>>> representation with ease.
>>
>> In what way is that representation better?
>
> I agree, I don't see why the representation is inherently better. Some
> operations become higher performance (i.e. popFront), and some become
> worse (i.e. length). Most of the others are a wash.

That's where frequency of use comes into play. I'm thinking popFront would be used most often, and it touches two words.

Andrei
September 19, 2011
On 09/19/2011 04:02 PM, Steven Schveighoffer wrote:
> On Mon, 19 Sep 2011 09:49:14 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:
>
>> On 09/19/2011 01:15 PM, Steven Schveighoffer wrote:
>>> On Sun, 18 Sep 2011 16:16:23 -0400, Timon Gehr <timon.gehr@gmx.ch>
>>> wrote:
>>>
>>>> On 09/18/2011 10:09 PM, Andrei Alexandrescu wrote:
>>>>> On 9/18/11 2:46 PM, Nick Sabalausky wrote:
>>>>>> "Timon Gehr"<timon.gehr@gmx.ch> wrote in message
>>>>>> news:j55h4f$1ia5$1@digitalmars.com...
>>>>>>>
>>>>>>>> The only advantages slices have left
>>>>>>>> are (a) type syntax, i.e. T[] instead of Slice!T, (b) literal
>>>>>>>> syntax,
>>>>>>>> i.e. [ 1, 2, 3 ] instead of slice(1, 2, 3), and (c) a couple of
>>>>>>>> stray
>>>>>>>> language bugs such as '$'.
>>>>>>>
>>>>>>> I am thankful for $, as it is a great feature, and it really
>>>>>>> should be
>>>>>>> made accessible to user defined types. Either through opDollar or
>>>>>>> the
>>>>>>> rewrite a[foo($)] => a[foo(a.length)]. What makes it qualify as a
>>>>>>> stray
>>>>>>> language bug to you?
>>>>>>>
>>>>>>
>>>>>> He's saying that one of the few advantages slices have left over
>>>>>> user-defined types is that, for slices, $ actually works. The bug is
>>>>>> that it
>>>>>> doesn't work for user-defined types.
>>>>>>
>>>>>> FWIW, I like the rewrite idea far better than opDollar.
>>>>>
>>>>> opDollar is more powerful because it can be made to work with infinite
>>>>> ranges.
>>>>>
>>>>> Andrei
>>>>
>>>> What would it return?
>>>
>>> Not all types that have an end also support .length, or use sequential
>>> integers for indexes.
>>>
>>> -Steve
>>
>> Yes, but D has already gone the 'being inflexible' path for the
>> comparison/negation/logical/ternary operators. Isn't this a similar
>> thing? I don't think infinite ranges work well with restrictive
>> operator overloading. eg a[0..100<$?100:$]. They'd need some
>> additional language support or they'll possibly blow up randomly on
>> generic code.
>>
>> Btw, do you know of an example of a data structure that can be indexed
>> continuously and has the notion of an end, but no length?
>
> I was specifically thinking of red-black tree, which has a distinct end,
> but it's index is not necessarily length (or any value for that matter).
>
> If you look at dcollections, you can slice a TreeMap using indexes or
> cursors. However, to index through the last element in the tree, you use
> the special cursor .end:
>
> auto range = mytree["hello" .. mytree.end]; // get all the elements in
> the tree which are >= "hello"
>
> Here, mytree["hello" .. mytree.length] would simply not compile.
>
> In addition, a tree with a uint index would silently do the *wrong* thing:
>
> auto set = new TreeSet!uint(1, 3, 5, 7, 9);
> assert(set.length == 5);
> auto range = set[1..set.length];
>
> assert(walkLength(range) == 2); // probably not what you expected

Ok, makes sense. Thanks.

>
> So I think it's not only limiting to require x.length to be $, it's very
> wrong in some cases.
>
> Also, think of a string. It has no length (well technically, it does,
> but it's not the number of elements), but it has a distinct end point. A
> properly written string type would fail to compile if $ was s.length.
>

But you'd have to compute the length anyways in the general case:

str[0..$/2];

Or am I misunderstanding something?