www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Inability to dup/~ for const arrays of class objects

reply Peter Williams <pwil3058 bigpond.net.au> writes:
Is the inability to use dup and ~ with const arrays of class objects a 
deliberate design restriction?  I couldn't find mention of it in the 
specification or Andrei's book and only discovered it the hard way.

Thanks
Peter
May 25 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 25 May 2013 23:58:39 -0400, Peter Williams  
<pwil3058 bigpond.net.au> wrote:


 Is the inability to use dup and ~ with const arrays of class objects a  
 deliberate design restriction?  I couldn't find mention of it in the  
 specification or Andrei's book and only discovered it the hard way.


It has to be.  There is no cdup.

For any const(T)[] x, the type of x.dup is T[].  Because this would mean  
that you would remove const, you cannot do that.  Nor can you idup, since  
implicit conversion to immutable is not possible.

As far as I know, ~ works with const arrays of class objects.  Can you  
give a case where it fails?

-Steve
May 28 2013
next sibling parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 28/05/13 23:41, Steven Schveighoffer wrote:

 On Sat, 25 May 2013 23:58:39 -0400, Peter Williams
 <pwil3058 bigpond.net.au> wrote:


 Is the inability to use dup and ~ with const arrays of class objects a
 deliberate design restriction?  I couldn't find mention of it in the
 specification or Andrei's book and only discovered it the hard way.


 It has to be.  There is no cdup.

 For any const(T)[] x, the type of x.dup is T[].


Yes, that's why I was doing the dup.  I wanted a non const copy of the 
array.


  Because this would mean
 that you would remove const, you cannot do that.


I find that dup works for const T[] when T is not a class (although I 
haven't tried it with pointers).  This means I write two versions of my 
code - one for classes (which does (cast(T[])).dup) and one for the rest.


  Nor can you idup,
 since implicit conversion to immutable is not possible.

 As far as I know, ~ works with const arrays of class objects.  Can you
 give a case where it fails?


Looking at my code that caused me to ask this question, I've realised 
that I'm appending a const object onto a no const array.  Once again 
this works for non class objects but not for classes.

I can see why this might be the case as non class objects are probably 
copied by value where the class objects are pointers and the constness 
applies to the items in an array as well the array itself.

If this behaviour is a deliberate design decision I'll accept that and 
(probably) modify my code to use (cast(T[])).dup in all cases.  (At the 
moment, I'm using a single mixin template to handle this issue and the 
inability to use ==, !=, < and friends with constant class objects. 
When that problem goes away I'll do the above modifications.)

This is the type of issue that can come as a surprise when you have a 
working/tested code that suddenly stops compiling when you use it with 
classes.  So a heads up in the documentation would be useful.

Thanks for your response,
Peter
May 28 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 28 May 2013 19:32:30 -0400, Peter Williams  
<pwil3058 bigpond.net.au> wrote:


 On 28/05/13 23:41, Steven Schveighoffer wrote:

 On Sat, 25 May 2013 23:58:39 -0400, Peter Williams
 <pwil3058 bigpond.net.au> wrote:


 Is the inability to use dup and ~ with const arrays of class objects a
 deliberate design restriction?  I couldn't find mention of it in the
 specification or Andrei's book and only discovered it the hard way.


 It has to be.  There is no cdup.

 For any const(T)[] x, the type of x.dup is T[].


 Yes, that's why I was doing the dup.  I wanted a non const copy of the  
 array.


You can't do that for arrays that contain references (which means any  
class type).  A dup is a shallow copy of the array bits.


  Because this would mean
 that you would remove const, you cannot do that.


 I find that dup works for const T[] when T is not a class (although I  
 haven't tried it with pointers).  This means I write two versions of my  
 code - one for classes (which does (cast(T[])).dup) and one for the rest.


It won't work for pointers, or types that contain pointers either.   
Basically, anything that contains a reference cannot be implicitly copied  
 from a const version to a non-const.

It is the same for simple variables too:

const int x = 5;
int y = x; // ok

const int *px = &x;
int *py = &y;
py = px; // error!

but:

*py = *px; // ok!

It makes logical sense that you can't duplicate arrays of these types  
while removing const also.


 As far as I know, ~ works with const arrays of class objects.  Can you
 give a case where it fails?


 Looking at my code that caused me to ask this question, I've realised  
 that I'm appending a const object onto a no const array.  Once again  
 this works for non class objects but not for classes.


Because for value types, like int, const, immutable, and mutable all  
implicitly cast to each other -- you are creating a FULL copy.  When  
copying a pointer or reference type, you have to create a "deep" copy of  
the data, or the const-ness is violated.  in D, const is transitive, which  
means if you apply const to a type, it means anything it points at is also  
const.


 I can see why this might be the case as non class objects are probably  
 copied by value where the class objects are pointers and the constness  
 applies to the items in an array as well the array itself.


In fact, const(T)[] applies ONLY to the data in the array, the array  
itself is not const.  A fully const array is:

const(T[])

Which cannot be appended to or modified.

However, a const(T[]) implicitly casts to a const(T)[].


 If this behaviour is a deliberate design decision


It is


 I'll accept that and (probably) modify my code to use (cast(T[])).dup in  
 all cases.  (At the moment, I'm using a single mixin template to handle  
 this issue and the inability to use ==, !=, < and friends with constant  
 class objects. When that problem goes away I'll do the above  
 modifications.)


This is not a good idea.  You are circumventing const.  What you want is a  
deep copy.

For example:

class Dupable
{
    this(int _x) { x = _x;}
    int x;
    pure Dupable dup() const { return new Dupable(x);}
}

T[] deepDup(T)(const(T)[] n) // should put template constraint here...
{
    T[] result = new T[n.length];
    foreach(i, ref x; n)
       result[i] = x.dup();

    return result;
}

Some people have also written libraries that make deep copies without  
having to have the class support it (e.g. for serialization).  Those may  
be of use to you.

In all likelihood, the problem could be that you are using classes and  
really should be using structs.

-Steve
May 28 2013
parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 29/05/13 09:58, Steven Schveighoffer wrote:

 In fact, const(T)[] applies ONLY to the data in the array, the array
 itself is not const.  A fully const array is:

 const(T[])

 Which cannot be appended to or modified.


Thanks, I'll change my code.


 However, a const(T[]) implicitly casts to a const(T)[].


 If this behaviour is a deliberate design decision


 It is


 I'll accept that and (probably) modify my code to use (cast(T[])).dup
 in all cases.  (At the moment, I'm using a single mixin template to
 handle this issue and the inability to use ==, !=, < and friends with
 constant class objects. When that problem goes away I'll do the above
 modifications.)


 This is not a good idea.  You are circumventing const.


Unfortunately, I have to circumvent const just to use ==, <=, etc in the 
current incarnation of D.  So this won't make things worse.


  What you want is a deep copy.


No, I don't.

I'm implementing sets and the concept is sets of objects not sets of the 
values in the objects.  I want to be able to initialize sets using 
arrays and I'm promising that I won't change the array or its contents. 
  I'm also trying to promise that I won't (inside the set 
implementation) make any changes to individual objects.  But I'm not 
promising that they won't be changed by other code that has access to 
them.  The invariant (I wrote) for the sets implies that any changes 
made by that code can't change the sort order of the objects.


 In all likelihood, the problem could be that you are using classes and
 really should be using structs.


No, I really don't want copies although I can see that might have it's 
uses in another application.  It's the mathematical concept of sets that 
I'm trying for not just containers.  I.e. it's a way of selecting groups 
of objects, combining groups without duplicates, etc.

Peter
May 28 2013
next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/28/2013 06:04 PM, Peter Williams wrote:


 I'm implementing sets and the concept is sets of objects not sets of the
 values in the objects.  I want to be able to initialize sets using
 arrays and I'm promising that I won't change the array or its contents.
   I'm also trying to promise that I won't (inside the set
 implementation) make any changes to individual objects.  But I'm not
 promising that they won't be changed by other code that has access to
 them.


Then I still think that it is related to the fact that a const class 
variable (not object) cannot refer to another object, which I think 
should be possible. Others think so too:

   http://forum.dlang.org/thread/bug-5325-3 http.d.puremagic.com/issues/

I remember the discussions on that topic and various syntax proposals 
but I don't remember why class variable assignment syntax would not work:

     // C is a class
     const(C) c = new const(C);

     // c promises that it won't mutate the object.
     // Why can't it promise to not mutate another object?

     c = new const(C);  // <-- compilation error

I don't see the rationale for disallowing the last line. I think it 
should work without any syntax change. Merely the class handle is being 
changed.

In this case it looks like "turtles all the way *up*" because just 
because the object is const, the handle is treated as const as well.

Ali
My head is thick today. :p
May 28 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 28 May 2013 21:19:49 -0400, Ali =C3=87ehreli <acehreli yahoo.com=

 wrote:



      // C is a class
      const(C) c =3D new const(C);

      // c promises that it won't mutate the object.
      // Why can't it promise to not mutate another object?

      c =3D new const(C);  // <-- compilation error

 I don't see the rationale for disallowing the last line. I think it  =



 should work without any syntax change. Merely the class handle is bein=


g  =


 changed.


The issue is that you cannot separate out the reference from the  =

referred-to data, and apply const only to the tail.

It's a syntax issue, not a semantic issue.  It should be allowed, but we=
  =

lack the syntax to specify it.  You can only apply const to both the  =

reference and the data.

-Steve
May 28 2013
parent "Diggory" <diggsey googlemail.com> writes:
On Wednesday, 29 May 2013 at 01:33:57 UTC, Steven Schveighoffer 
wrote:

 On Tue, 28 May 2013 21:19:49 -0400, Ali Çehreli 
 <acehreli yahoo.com> wrote:


     // C is a class
     const(C) c = new const(C);

     // c promises that it won't mutate the object.
     // Why can't it promise to not mutate another object?

     c = new const(C);  // <-- compilation error

 I don't see the rationale for disallowing the last line. I 
 think it should work without any syntax change. Merely the 
 class handle is being changed.


 The issue is that you cannot separate out the reference from 
 the referred-to data, and apply const only to the tail.

 It's a syntax issue, not a semantic issue.  It should be 
 allowed, but we lack the syntax to specify it.  You can only 
 apply const to both the reference and the data.

 -Steve


At the moment type qualifiers are also implicitly storage 
classes, I wonder if it would cause any problems to separate the 
two uses out...

For a class:
const(C) myvar;   // Normal variable holding a const(C)
const C myvar;    // Const variable holding a const(C) (due to 
transitivity)

For a struct:
const(S) myvar;   // Const-ness of struct leaks out to variable 
because it is a value type
const S myvar;    // Const variable holding a const(S) (due to 
transitivity)
May 28 2013
prev sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, May 28, 2013 18:19:49 Ali Çehreli wrote:

 I remember the discussions on that topic and various syntax proposals
 but I don't remember why class variable assignment syntax would not work:


The problem is that the type system does not differentiate between a class 
object and a reference to a class object. The type refers explicitly to the 
reference, not the object. It doesn't have the concept of a class object 
separate from its reference, so regardless of what syntax could be proposed, 
the compiler needs to be rewired a fair bit with regards to classes in order 
to make it possible to separate the class object and the reference pointing to 
it. Walter tried it but gave up on it after having quite a few problems with 
it. I fully expect that it's feasible, but it's hard enough that it hasn't 
happened. Someone (Michel Fortin IIRC) created one of the first dmd pull 
requests with a possible solution, but Walter didn't get around to reviewing 
it (probably because he was sick of dealing with the issue), and it suffered 
bitrot to the point that it was dropped. I don't know how viable that pull 
request was, but someone else would need to put in similar effort (if not more) 
in order to rewire the compiler enough to understand the difference between a 
class object and its reference.

- Jonathan M Davis
May 28 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/28/2013 07:24 PM, Jonathan M Davis wrote:


 On Tuesday, May 28, 2013 18:19:49 Ali Çehreli wrote:

 I remember the discussions on that topic and various syntax proposals
 but I don't remember why class variable assignment syntax would not 




work:

 The problem is that the type system does not differentiate between a 


class

 object and a reference to a class object. The type refers explicitly 


to the

 reference, not the object. It doesn't have the concept of a class object
 separate from its reference


However, most of the operations on a class reference are relayed to the 
object:

   auto r = new C();
   r.foo();            // relayed to the object
   r.bar = 42;         // relayed to the object
   writeln(r);         // relayed to the object
   // ...              // etc.

With exception of assignment, which stays with the reference:

   r = new C();        // on the reference

How about the following two rules, which do not require any syntax 
change. Let's make it so that there are two kinds of type checks on a 
class reference:

1) For operations that involve the object, perform the type check as it 
is today.

2) The assignment operation is type-checked specially:

   const: Allow the assignment for any type on the right-hand side)

   immutable: Allow the assignment for only immutable on the right-hand side

   mutable: Allow the assignment for only mutable on the right-hand side

Of course this throws out the current behavior of non-mutable references 
being non-rebindable, but I think non-rebindable references are 
overrated. Even in C and C++, most of the time it is the data that is 
const. For example, nobody takes 'const char * const' parameters. Yes, 
it is helpful in theory, but programmers simply define the parameter as 
'const char *'. (Or 'char const *' if they are more purist. :) )

It seems simple enough but perhaps it is too difficult to implement at 
this point. Only Kenji can tell! ;)

Ali
May 28 2013
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, May 28, 2013 22:58:39 Ali =C3=87ehreli wrote:

 On 05/28/2013 07:24 PM, Jonathan M Davis wrote:
  > On Tuesday, May 28, 2013 18:19:49 Ali =C3=87ehreli wrote:
  >> I remember the discussions on that topic and various syntax propo=


sals

  >> but I don't remember why class variable assignment syntax would n=


ot

=20
 work:
  > The problem is that the type system does not differentiate between=


 a

=20
 class
=20
  > object and a reference to a class object. The type refers explicit=


ly

=20
 to the
=20
  > reference, not the object. It doesn't have the concept of a class =


object

  > separate from its reference
=20
 However, most of the operations on a class reference are relayed to t=


he

 object:
=20
    auto r =3D new C();
    r.foo();            // relayed to the object
    r.bar =3D 42;         // relayed to the object
    writeln(r);         // relayed to the object
    // ...              // etc.
=20
 With exception of assignment, which stays with the reference:
=20
    r =3D new C();        // on the reference
=20
 How about the following two rules, which do not require any syntax
 change. Let's make it so that there are two kinds of type checks on a=



 class reference:
=20
 1) For operations that involve the object, perform the type check as =


it

 is today.
=20
 2) The assignment operation is type-checked specially:
=20
    const: Allow the assignment for any type on the right-hand side)
=20
    immutable: Allow the assignment for only immutable on the right-ha=


nd side

=20
    mutable: Allow the assignment for only mutable on the right-hand s=


ide

=20
 Of course this throws out the current behavior of non-mutable referen=


ces

 being non-rebindable, but I think non-rebindable references are
 overrated. Even in C and C++, most of the time it is the data that is=



 const. For example, nobody takes 'const char * const' parameters. Yes=


,

 it is helpful in theory, but programmers simply define the parameter =


as

 'const char *'. (Or 'char const *' if they are more purist. :) )
=20
 It seems simple enough but perhaps it is too difficult to implement a=


t

 this point. Only Kenji can tell! ;)


Having const references or pointers is occasionally useful, but we woul=
dn't=20
lose much IMHO if we lost them. Java got it backwards in that that's th=
e=20
_only_ kind of const that it has (via final). However, I don't know how=
=20
feasible your suggestion is. Remember that there isn't really any diffe=
rence=20
between the reference and the object in the type system. When you mark =
a=20
function as const, it's the this reference which is const. So, when you=
 have a=20
const C that you're operating on, it's the reference itself which is th=
en the=20
this reference and is passed around as const. As far as the type system=
 is=20
concerned, there's nothing else to _be_ const. So, you're asking for it=
 to be=20
treated as const as far as function calls go but treated as mutable oth=
erwise,=20
which goes against how const works. You're asking for a half-constness =
of=20
sorts.

To make matters worse, what happens when you have a const object which =
has a=20
reference as a member variable? e.g.

class C
{
    class D d;
}

const C c;

Because of the transitivity of const, d must be fully const, and yet wi=
th your=20
suggestion, it isn't. Or if it is, we now have a situation where the co=
nstness=20
of a reference depends on its context, and the compiler must keep track=
 of its=20
context in addition to its type in order to determine whether it's full=
y const=20
or just half const.

So, while at first glance, I think that your suggestion makes sense=20
conceptually, I think that it's going to fall apart when we get into th=
e=20
details.

I confess that for the most part, I've just given up and resigned mysel=
f to=20
using Rebindable.

- Jonathan M Davis
May 28 2013
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/28/2013 11:13 PM, Jonathan M Davis wrote:


 On Tuesday, May 28, 2013 22:58:39 Ali Çehreli wrote:



 To make matters worse, what happens when you have a const object 


which has a

 reference as a member variable? e.g.

 class C
 {
      class D d;
 }

 const C c;


Thanks for doing the thinking for me. :) I could not think deeper than 
one level yesterday. :)


 Because of the transitivity of const, d must be fully const, and yet 


with your

 suggestion, it isn't.


We know the phrase "turtles all the way down". It makes sense. The 
interesting thing is, in the case of a class reference, at least due to 
syntax, it feels like it is "turtle one level up":

     const(C) c = new const(C);

The reason is, the syntax const(C) suggests that the object is const. 
(Compared to 'const C c = ...') However, although it looks like const 
qualifiying the object, it comes one step up affects the reference as well.

I wondered whether there were more turtles up: :)

void main()
{
     class A
     {
         int i;
         this(int i) { this.i = i; }
     }

     const(A) a1 = new const(A)(1);
     const(A) a2 = new const(A)(2);

     // The following is a compilation ERROR because it is not
     // possible to refer to another object in a non-mutating way:

     // a1 = a2;  <-- compilation ERROR

     // No problem at all! Define a wrapper for a const(A):
     class B
     {
         const(A) a;
         this(const(A) a) { this.a = a; }
     }

     B b1 = new B(a1);
     B b2 = new B(a2);

     // And use your const(A) through that wrapper:
     assert(b1.a.i == 1);

     // Maybe we should call this wrapper Rebindable ;)
     b1 = b2;

     // Yay! :)
     assert(b1.a.i == 2);
}

I always fail to remember std.typecons.Rebindable. :( It may be the 
solution to OP's issue:



Ali
May 29 2013
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
 I'm implementing sets and the concept is sets of objects not sets of the  
 values in the objects.  I want to be able to initialize sets using  
 arrays and I'm promising that I won't change the array or its contents.  
   I'm also trying to promise that I won't (inside the set  
 implementation) make any changes to individual objects.  But I'm not  
 promising that they won't be changed by other code that has access to  
 them.  The invariant (I wrote) for the sets implies that any changes  
 made by that code can't change the sort order of the objects.


Then you are trying to make a *momentary* guarantee.

In essence, you want to transform the array into a set, but still  
guarantee that the underlying data hasn't changed.

This is very difficult to express with the type system.  The closest you  
can get is inout, which *might* be able to do it.

For example:

inout(T)[] copyIt(T)(inout(T)[] arr)
{
    // this is quirky, but it's the easiest way to do it without an  
equivalent .dup for inout
    inout(T)[] result;
    result ~= arr;
    return result;
}

Now, if you pass in mutable, you get mutable.  If you pass in const, you  
get const.  If you pass in immutable, you get immutable.

I say *might* because I don't know what your code is doing, or how your  
set type actually looks.  It may be logical, but impossible to currently  
express.  inout still has some room for improvement (and so does the whole  
const system in general).


 No, I really don't want copies although I can see that might have it's  
 uses in another application.  It's the mathematical concept of sets that  
 I'm trying for not just containers.  I.e. it's a way of selecting groups  
 of objects, combining groups without duplicates, etc.


Another option is to simply define your types as "immutable" types.  That  
is, specify the data inside is immutable, but the class itself is not.

e.g.:

class C
{
    immutable int c;
    this(int x) { c = x;}
}

You are hitting a very common pain-point for const/immutable, for which  
there is really not a good answer currently.

-Steve
May 28 2013
parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 29/05/13 11:31, Steven Schveighoffer wrote:

 I'm implementing sets and the concept is sets of objects not sets of
 the values in the objects.  I want to be able to initialize sets using
 arrays and I'm promising that I won't change the array or its
 contents.   I'm also trying to promise that I won't (inside the set
 implementation) make any changes to individual objects.  But I'm not
 promising that they won't be changed by other code that has access to
 them.  The invariant (I wrote) for the sets implies that any changes
 made by that code can't change the sort order of the objects.


 Then you are trying to make a *momentary* guarantee.


Almost.  I'm also saying I won't change it any time within the set.


 In essence, you want to transform the array into a set, but still
 guarantee that the underlying data hasn't changed.


More or less. The set code won't change it something else might.


 This is very difficult to express with the type system.


I'm starting to realize this :-)

I've always been frustrated in other languages by const (and friends) 
being inadequate for saying what I want to say.


 The closest you
 can get is inout, which *might* be able to do it.

 For example:

 inout(T)[] copyIt(T)(inout(T)[] arr)
 {
     // this is quirky, but it's the easiest way to do it without an
 equivalent .dup for inout
     inout(T)[] result;
     result ~= arr;
     return result;
 }

 Now, if you pass in mutable, you get mutable.  If you pass in const, you
 get const.  If you pass in immutable, you get immutable.

 I say *might* because I don't know what your code is doing, or how your
 set type actually looks.  It may be logical, but impossible to currently
 express.  inout still has some room for improvement (and so does the
 whole const system in general).


 No, I really don't want copies although I can see that might have it's
 uses in another application.  It's the mathematical concept of sets
 that I'm trying for not just containers.  I.e. it's a way of selecting
 groups of objects, combining groups without duplicates, etc.


 Another option is to simply define your types as "immutable" types.
 That is, specify the data inside is immutable, but the class itself is not.


No.  I need to be able to make changes to the objects (that doesn't 
effect their order).  It's kind of like an associative array (which I 
did consider as a mechanism for doing what I wanted) but without 
splitting the object into a key/value pair.

One place I'm using it is for managing symbols (look ahead sets, etc) in 
a parser generator.  The symbols' permanent home is in an associative 
array indexed by their name (which is also included in the symbol 
object) but they may belong to many look ahead sets.  Usually, 
processing that requires access to attributes of the symbol (other than 
the key) occurs when processing one of the look ahead sets and going 
looking for the symbol table looking for the data is an unnecessary 
complication (not to mention an efficiency hit).  Having exactly one 
object per symbol but still being able to have it multiple sets is a big 
efficiency gain especially when it comes to making changes to the 
ancillary data as you only have to change it in one place.


 e.g.:

 class C
 {
     immutable int c;
     this(int x) { c = x;}
 }

 You are hitting a very common pain-point for const/immutable, for which
 there is really not a good answer currently.


I agree.

This happens every time I try a new language.  I get all excited about 
making my code bulletproof only to be mugged by reality. :-)  In the 
end, it comes down to coding carefully.

Peter
May 28 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 28 May 2013 23:43:49 -0400, Peter Williams  
<pwil3058 bigpond.net.au> wrote:


 No.  I need to be able to make changes to the objects (that doesn't  
 effect their order).  It's kind of like an associative array (which I  
 did consider as a mechanism for doing what I wanted) but without  
 splitting the object into a key/value pair.

 One place I'm using it is for managing symbols (look ahead sets, etc) in  
 a parser generator.  The symbols' permanent home is in an associative  
 array indexed by their name (which is also included in the symbol  
 object) but they may belong to many look ahead sets.  Usually,  
 processing that requires access to attributes of the symbol (other than  
 the key) occurs when processing one of the look ahead sets and going  
 looking for the symbol table looking for the data is an unnecessary  
 complication (not to mention an efficiency hit).  Having exactly one  
 object per symbol but still being able to have it multiple sets is a big  
 efficiency gain especially when it comes to making changes to the  
 ancillary data as you only have to change it in one place.


OK, this gives more info.

You can't use const elements.  And for good reason -- the elements are not  
const, and cannot be considered const by the set.

Use mutable data, and make the *key* part of the data const.  If you wish,  
you can place inout on the indexing function, which should guarantee that  
during that function the data is not molested.  Then you basically have to  
hand-verify the insertion function does not change the data.

That's the best D can do, and it's pretty good considering what other  
alternatives there are.

-Steve
May 28 2013
parent Peter Williams <pwil3058 bigpond.net.au> writes:
On 29/05/13 13:59, Steven Schveighoffer wrote:

 You can't use const elements.  And for good reason -- the elements are
 not const, and cannot be considered const by the set.

 Use mutable data, and make the *key* part of the data const.


My first implementation does that and it's great for that one 
application.  All the complications arose when I went back to try and 
bulletproof it and make a set implementation that is generally useful 
rather than just for the application it was designed for.

I may just have to accept that two separate implementations are needed 
and that I have to give some thought about how to maximise the shared 
code between them.


  If you
 wish, you can place inout on the indexing function, which should
 guarantee that during that function the data is not molested.  Then you
 basically have to hand-verify the insertion function does not change the
 data.


I always (try to) do hand verification :-).  Once I even toyed with code 
proofs (a la Gries, ISBN 0-387-90641-X) but that rapidly becomes boring 
in practice even when you have language constructs (such as Eiffel's 
loop) which are designed with such proofs in mind.


 That's the best D can do, and it's pretty good considering what other
 alternatives there are.


Yes. I agree - a type attribute system that could say everything we want 
to say would be very complex.  Nevertheless, D has room for improvement 
e.g. more expressive contracts are possible.

Peter
PS There seems to be a reluctance to fix problems in D if it will break 
existing code.  I would opine that the code that would be broken is 
already broken.  I would also opine that fixing the problems now will 
break less code than fixing them later.
May 28 2013
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/28/2013 08:43 PM, Peter Williams wrote:


 One place I'm using it is for managing symbols (look ahead sets, etc) in
 a parser generator.  The symbols' permanent home is in an associative
 array indexed by their name (which is also included in the symbol
 object) but they may belong to many look ahead sets.


Have you considered Rebindable?

import std.typecons;

class C
{
     void mutate() {}
     void readOnly() const {}
}

void main()
{
     // Here is the actual data:
     C[string] mutableData;
     mutableData["one"] = new C();
     mutableData["two"] = new C();

     // Mutable; good...
     mutableData["one"].mutate();

     alias ConstRef = Rebindable!(const C);

     // Here is a const view of mutable data
     ConstRef[] set;
     set ~= ConstRef(mutableData["one"]);
     set ~= ConstRef(mutableData["two"]);

     set[0].readOnly();
     // set[0].mutate();  <-- compilation error; good...
}

Ali
May 29 2013
parent Peter Williams <pwil3058 bigpond.net.au> writes:
On 30/05/13 02:17, Ali Çehreli wrote:

 On 05/28/2013 08:43 PM, Peter Williams wrote:

  > One place I'm using it is for managing symbols (look ahead sets, etc) in
  > a parser generator.  The symbols' permanent home is in an associative
  > array indexed by their name (which is also included in the symbol
  > object) but they may belong to many look ahead sets.

 Have you considered Rebindable?


No. Never heard of it before :-)

But, having now read the documentation, I don't think it meets my needs.

We need a book on the standard library.

Thanks
Peter
May 29 2013
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 29 May 2013 at 01:05:14 UTC, Peter Williams wrote:

 I'm implementing sets and the concept is sets of objects not 
 sets of the values in the objects.  I want to be able to 
 initialize sets using arrays and I'm promising that I won't 
 change the array or its contents.
  I'm also trying to promise that I won't (inside the set 
 implementation) make any changes to individual objects.  But 
 I'm not promising that they won't be changed by other code that 
 has access to them.  The invariant (I wrote) for the sets 
 implies that any changes made by that code can't change the 
 sort order of the objects.

 Peter


The problem is that you are missing a FUNDAMENTAL difference 
between C++ and D. C++'s const merely says: "Though shalt not 
modify this value", whereas D's means "This object's value WILL 
remain constant, until the end of time, and under no circumstance 
can it ever be modified. Oh. And so will everything it 
references".

The fact that *you* are promising to not change it is irrelevant 
to the concept of D's const. D only knows 2 states: objects that 
mutate, and objects that don't mutate.

Ditto about invariants. Contrary to C++, there is no concept of 
"observable constness" (eg invariants).

The reasoning behind this is that in D, const is actually the 
"base attribute" between the "muttable" and the "immutable" 
objects. immutable allows sharing things accross threads, and 
allows more aggressive optimizations than is possible with const 
"the compiler *knows* the object will not be changed by an 
outside force". At this point, const exists only to be able to 
operate on objects that may or may not be immutable.

For example, imagine you have a const array of pointers, and you

--------
Of course, this has its limits, and that's where casting comes 
into play. You must keep in mind these two caveats:
*Never ever ever modify something that is const.
*Once you've casted something to const, make sure that NOTHING 
will modify the object via a non-const handle.

But the "const" you are trying to promise is not what D's const 
was designed for.
May 29 2013
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 29 May 2013 at 09:40:08 UTC, monarch_dodra wrote:

 On Wednesday, 29 May 2013 at 01:05:14 UTC, Peter Williams wrote:

 I'm implementing sets and the concept is sets of objects not 
 sets of the values in the objects.  I want to be able to 
 initialize sets using arrays and I'm promising that I won't 
 change the array or its contents.
 I'm also trying to promise that I won't (inside the set 
 implementation) make any changes to individual objects.  But 
 I'm not promising that they won't be changed by other code 
 that has access to them.  The invariant (I wrote) for the sets 
 implies that any changes made by that code can't change the 
 sort order of the objects.

 Peter


 The problem is that you are missing a FUNDAMENTAL difference 
 between ...


Erm, I posted this without seeing there was more to the thread. 
So I could be wrong. But I think the point is still relevant.
May 29 2013
prev sibling next sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Wednesday, 29 May 2013 at 09:40:08 UTC, monarch_dodra wrote:

 whereas D's means "This object's value WILL remain constant, 
 until the end of time, and under no circumstance can it ever be 
 modified. Oh. And so will everything it references".


That's NOT what D's const means! The data may change through 
other, mutable references to it, but not through any const 
references. That's why const data is not implicitly convertible 
to immutable data (unless it has no mutable indirection, in which 
case it would be a deep copy) - there could be mutable references 
out there!

The difference between C++ and D const is that D's const is 
transitive, and mutating it by casting away const can have 
terrible consequences because const is designed to work with 
immutable.


 The fact that *you* are promising to not change it is 
 irrelevant to the concept of D's const. D only knows 2 states: 
 objects that mutate, and objects that don't mutate.


No.


 *Once you've casted something to const, make sure that NOTHING 
 will modify the object via a non-const handle.


This is *perfectly fine* unless the non-const handle was acquired 
by casting away const or immutable.
May 29 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 29 May 2013 at 12:23:04 UTC, Jakob Ovrum wrote:

 On Wednesday, 29 May 2013 at 09:40:08 UTC, monarch_dodra wrote:

 whereas D's means "This object's value WILL remain constant, 
 until the end of time, and under no circumstance can it ever 
 be modified. Oh. And so will everything it references".


 That's NOT what D's const means! The data may change through 
 other, mutable references to it, but not through any const 
 references. That's why const data is not implicitly convertible 
 to immutable data (unless it has no mutable indirection, in 
 which case it would be a deep copy) - there could be mutable 
 references out there!

 The difference between C++ and D const is that D's const is 
 transitive, and mutating it by casting away const can have 
 terrible consequences because const is designed to work with 
 immutable.


 The fact that *you* are promising to not change it is 
 irrelevant to the concept of D's const. D only knows 2 states: 
 objects that mutate, and objects that don't mutate.


 No.


 *Once you've casted something to const, make sure that NOTHING 
 will modify the object via a non-const handle.


 This is *perfectly fine* unless the non-const handle was 
 acquired by casting away const or immutable.


Hum.

...

Sight. I think I let immutable get to my head again :/

You are right. My point was moot.
May 29 2013
prev sibling parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 29/05/13 19:40, monarch_dodra wrote:

 The problem is that you are missing a FUNDAMENTAL difference between C++
 and D. C++'s const merely says: "Though shalt not modify this value",
 whereas D's means "This object's value WILL remain constant, until the
 end of time, and under no circumstance can it ever be modified. Oh. And
 so will everything it references".


More likely C constness but yes I am still learning D.  I suspect that a 
lot of my D code currently looks like C code using D syntax.  As I learn 
more I'll go back and change the code to be more D like than C like 
(especially as this usually leads to major simplifications).

I'm also starting to suspect that my understanding of how C arrays are 
passed as arguments to functions is affecting my desire to use const 
when passing them in and this may be misguided.  I've been trying to 
find out how non ref array arguments are passed to functions in D but 
can't find any documentation on it.  If doing that is not much less 
efficient than passing by ref (and isolates the external representation 
of the array from anything I do) then I can stop using ref and the 
problem goes away.

Peter
May 29 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/29/2013 03:59 PM, Peter Williams wrote:


 I've been trying to find out how non ref array arguments are passed to
 functions in D but can't find any documentation on it.


The following concepts are relevant:

- Dynamic array: Maintained by the D runtime

- Fixed-length array (aka static array): Can be on the stack

- Slice: An efficient tool to access a range of elements (of any type of 
array)

Usually, it is the slice that gets passed:

   void foo(int[] slice);

A slice is made up of the pointer to the first element and the number of 
elements:

struct __SomeImplementationDependentName__
{
     size_t length;
     void * ptr;
}

When you pass a slice by-value, as in the case of foo() above, that 
struct gets copied: a copy of the argument...

So, slice variables have value semantics but they are used as references 
to elements.

Fixed-length arrays are a different story: Unlike C arrays and unlike D 
slices, the elements are always copied.


 If doing that is not much less efficient than passing by ref (and 


isolates

 the external representation of the array from anything I do) then I 


can stop

 using ref and the problem goes away.


Yes, simply pass-by-reference. Not expensive at all. There may be 
surprises though; you may want to read this article:

   http://dlang.org/d-array-article.html

Ali
May 29 2013
next sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/29/2013 04:45 PM, Ali Çehreli wrote:


 Yes, simply pass-by-reference. Not expensive at all.


Arggh! It should say "simply pass-by-value".

Ali
May 29 2013
prev sibling next sibling parent Peter Williams <pwil3058 bigpond.net.au> writes:
On 30/05/13 09:45, Ali Çehreli wrote:

 Yes, simply pass-by-reference. Not expensive at all. There may be
 surprises though; you may want to read this article:

    http://dlang.org/d-array-article.html


Very informative article.

Thanks
Peter
May 29 2013
prev sibling next sibling parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 30/05/13 10:49, Peter Williams wrote:

 On 30/05/13 09:45, Ali Çehreli wrote:

 Yes, simply pass-by-reference. Not expensive at all. There may be
 surprises though; you may want to read this article:

    http://dlang.org/d-array-article.html


 Very informative article.


Thinking about this some more, it seems I still need the const even with 
pass by value to reassure the caller that his array won't be altered. 
So the problem doesn't go away it just changes slightly.

I find the mechanism described in the article a little disconcerting and 
it certainly needs more publicity as it's a bug in waiting for the 
unwary. Wouldn't a better rule for pass by value be that any changes to 
the data part of the array (including assignment to an element) causes 
reallocation of the entire data portion.

Peter
May 29 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/29/2013 06:54 PM, Peter Williams wrote:


 On 30/05/13 10:49, Peter Williams wrote:

 On 30/05/13 09:45, Ali Çehreli wrote:





    http://dlang.org/d-array-article.html







 Thinking about this some more, it seems I still need the const even with
 pass by value to reassure the caller that his array won't be altered. So
 the problem doesn't go away it just changes slightly.


It is sensible that the parameter be const-element, non-const-slice:

     void foo(const(int)[] arr);


 I find the mechanism described in the article a little disconcerting and
 it certainly needs more publicity as it's a bug in waiting for the
 unwary.


It certainly is disconcerting. Performance have played a big role in the 
current semantics of slices.


 Wouldn't a better rule for pass by value be that any changes to
 the data part of the array (including assignment to an element) causes
 reallocation of the entire data portion.


The type of a slice parameter is not different than a local slice 
variable. Since we wouldn't want an entire copy of the elements due to 
an element mutation:

     int[] whole = // ...;
     int[] firstHalf = whole[0 .. $/2];
     firstHalf = 42;    // this should affect whole

Moving the last two lines to a new function should not change meaning:

     int[] whole = // ...;
     setFirstHalf(whole, 42);  // should still affect whole

Ali
May 29 2013
next sibling parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 30/05/13 16:21, Ali Çehreli wrote:

 On 05/29/2013 06:54 PM, Peter Williams wrote:
  > I find the mechanism described in the article a little disconcerting and
  > it certainly needs more publicity as it's a bug in waiting for the
  > unwary.

 It certainly is disconcerting. Performance have played a big role in the
 current semantics of slices.


I should have added that it was the non determinism that disconcerted 
me.  It doesn't really affect me personally as a programmer now that I 
know about it as I can just avoid it.  But it blows out of the water any 
hopes of having "proveably correct"  non trivial code.

Peter
May 30 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 30 May 2013 20:05:59 -0400, Peter Williams  =

<pwil3058 bigpond.net.au> wrote:


 On 30/05/13 16:21, Ali =C3=87ehreli wrote:

 On 05/29/2013 06:54 PM, Peter Williams wrote:
  > I find the mechanism described in the article a little disconcerti=




ng  =


 and
  > it certainly needs more publicity as it's a bug in waiting for the=





  > unwary.

 It certainly is disconcerting. Performance have played a big role in =




the

 current semantics of slices.


 I should have added that it was the non determinism that disconcerted =


 =


 me.  It doesn't really affect me personally as a programmer now that I=


  =


 know about it as I can just avoid it.  But it blows out of the water a=


ny  =


 hopes of having "proveably correct"  non trivial code.


I think this is an overstatement.  It depends heavily on what you are  =

doing, and most usages will be correct.

You can achieve deterministic behavior depending on what you are looking=
  =

for.  For certain, you can tell without any additional tools that an  =

append will not reallocate if the capacity is large enough.

-Steve
May 30 2013
parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 31/05/13 12:07, Steven Schveighoffer wrote:

 On Thu, 30 May 2013 20:05:59 -0400, Peter Williams
 <pwil3058 bigpond.net.au> wrote:


 On 30/05/13 16:21, Ali Çehreli wrote:

 On 05/29/2013 06:54 PM, Peter Williams wrote:
  > I find the mechanism described in the article a little
 disconcerting and
  > it certainly needs more publicity as it's a bug in waiting for the
  > unwary.

 It certainly is disconcerting. Performance have played a big role in the
 current semantics of slices.


 I should have added that it was the non determinism that disconcerted
 me.  It doesn't really affect me personally as a programmer now that I
 know about it as I can just avoid it.  But it blows out of the water
 any hopes of having "proveably correct"  non trivial code.


 I think this is an overstatement.  It depends heavily on what you are
 doing, and most usages will be correct.


All uses have to be correct if you want "provably correct" otherwise you 
just get "mostly correct".


 You can achieve deterministic behavior depending on what you are looking
 for.  For certain, you can tell without any additional tools that an
 append will not reallocate if the capacity is large enough.


That makes programming much easier, doesn't it.  I'll just avoid it by 
using:

a = a ~ b;

instead of:

a ~= b;

where I think it might be an issue or is that broken too?

I toy in my mind with the idea that the difference between dynamic 
arrays and slices should be that slices are read only and if you write 
to them they get reallocated and promoted to dynamic array (kind of like 
copy on write with hard linked files).  But I'm sure that would just 
create another set of problems.  Also I imagine that it's already been 
considered and discarded.  BTW the slice "notation" could still be used 
for assigning to sections of an array.

Peter
May 30 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 31 May 2013 00:48:47 -0400, Peter Williams  =

<pwil3058 bigpond.net.au> wrote:


 On 31/05/13 12:07, Steven Schveighoffer wrote:

 On Thu, 30 May 2013 20:05:59 -0400, Peter Williams
 <pwil3058 bigpond.net.au> wrote:


 On 30/05/13 16:21, Ali =C3=87ehreli wrote:

 On 05/29/2013 06:54 PM, Peter Williams wrote:
  > I find the mechanism described in the article a little
 disconcerting and
  > it certainly needs more publicity as it's a bug in waiting for t=








he

  > unwary.

 It certainly is disconcerting. Performance have played a big role i=








n  =


 the
 current semantics of slices.


 I should have added that it was the non determinism that disconcerte=






d

 me.  It doesn't really affect me personally as a programmer now that=






 I

 know about it as I can just avoid it.  But it blows out of the water=







 any hopes of having "proveably correct"  non trivial code.


 I think this is an overstatement.  It depends heavily on what you are=





 doing, and most usages will be correct.


 All uses have to be correct if you want "provably correct" otherwise y=


ou  =


 just get "mostly correct".


All *your* uses have to be correct.  What I meant was, you have to know =
 =

the pitfalls and avoid them.  Because there are pitfalls, this doesn't  =

mean you can't prove correctness.

And the pitfalls are quite few.


 You can achieve deterministic behavior depending on what you are look=




ing

 for.  For certain, you can tell without any additional tools that an
 append will not reallocate if the capacity is large enough.


 That makes programming much easier, doesn't it.  I'll just avoid it by=


  =


 using:

 a =3D a ~ b;

 instead of:

 a ~=3D b;


If you care nothing for performance, this certainly is a way to go.


 where I think it might be an issue or is that broken too?


This is a conservative "always reallocate" methodology, it should work  =

just like you allocated a new array to hold a and b.

If a is frequently large, and b is frequently small, you will kill your =
 =

performance vs. a ~=3D b.



 I toy in my mind with the idea that the difference between dynamic  =



 arrays and slices should be that slices are read only and if you write=


  =


 to them they get reallocated and promoted to dynamic array (kind of li=


ke  =


 copy on write with hard linked files).  But I'm sure that would just  =



 create another set of problems.  Also I imagine that it's already been=


  =


 considered and discarded.  BTW the slice "notation" could still be use=


d  =


 for assigning to sections of an array.


This was a proposed feature (not the copy on write, but copy on append).=
   =

It was so complex to explain that we simply didn't implement it.  Instea=
d,  =

we improved array appending performance and semantics.

The two largest differences between slices and proper dynamic arrays is =
 =

that a slice does not own it's viewed data (read: is not responsible for=
  =

the lifetime), and it's 'view' is passed by value.

-Steve
May 31 2013
parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 31/05/13 23:58, Steven Schveighoffer wrote:

 On Fri, 31 May 2013 00:48:47 -0400, Peter Williams

 That makes programming much easier, doesn't it.  I'll just avoid it by
 using:

 a = a ~ b;

 instead of:

 a ~= b;


 If you care nothing for performance, this certainly is a way to go.


 where I think it might be an issue or is that broken too?


 This is a conservative "always reallocate" methodology, it should work
 just like you allocated a new array to hold a and b.


That's what I assumed.  I'm still getting used to the idea that "a <op>= 
b" isn't just a shorthand for "a = a <op> b".


 If a is frequently large, and b is frequently small, you will kill your
 performance vs. a ~= b.


I doubt that I'll be doing it often enough (i.e. only when I think that 
it's an issue) for it to matter.  The only time I have two variables for 
the same array is when I pass one to a function as a parameter and if 
I'm intending to modify it in the function I'll pass it by reference so 
that there's no gotchas.

I do like the idea that "~=" is generally cheap as it potentially makes 
building lists easy (is there any need for the singly linked list in D?) 
and I may modify some of my code.  I've been allocating arrays using 
"new array[size]" where I know that "size" will be the max needed but 
that it may be too much (i.e. throwing away duplicates) inserting into 
the array and then adjusting "length" to whatever I used.  In the case, 
where it's highly likely that the whole array will fit in a page I might 
as well allocate an empty array and use "+=".  NB there's only one copy 
of the array.

Peter
May 31 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 31 May 2013 21:04:47 -0400, Peter Williams  
<pwil3058 bigpond.net.au> wrote:


 On 31/05/13 23:58, Steven Schveighoffer wrote:

 On Fri, 31 May 2013 00:48:47 -0400, Peter Williams

 That makes programming much easier, doesn't it.  I'll just avoid it by
 using:

 a = a ~ b;

 instead of:

 a ~= b;


 This is a conservative "always reallocate" methodology, it should work
 just like you allocated a new array to hold a and b.


 That's what I assumed.  I'm still getting used to the idea that "a <op>=  
 b" isn't just a shorthand for "a = a <op> b".


It is if you don't care about where it lands :)  I understand that in some  
cases, it's important or desirable to dictate whether extension-in-place  
is used or not, but in most cases, you don't care, you just want to change  
an array to contain more data.


 If a is frequently large, and b is frequently small, you will kill your
 performance vs. a ~= b.


 I doubt that I'll be doing it often enough (i.e. only when I think that  
 it's an issue) for it to matter.  The only time I have two variables for  
 the same array is when I pass one to a function as a parameter and if  
 I'm intending to modify it in the function I'll pass it by reference so  
 that there's no gotchas.


The only real gotchas come if you append *and then* modify the original  
data.  If you append *after* modifying the original data, or don't modify  
the original data, then there is no issue.  If you only ever have one  
reference to the array data, there is no issue.

There really are very few cases where appending can cause curious  
behavior.  For the most part, it's undetected.


 I do like the idea that "~=" is generally cheap as it potentially makes  
 building lists easy (is there any need for the singly linked list in D?)  
 and I may modify some of my code.  I've been allocating arrays using  
 "new array[size]" where I know that "size" will be the max needed but  
 that it may be too much (i.e. throwing away duplicates) inserting into  
 the array and then adjusting "length" to whatever I used.  In the case,  
 where it's highly likely that the whole array will fit in a page I might  
 as well allocate an empty array and use "+=".  NB there's only one copy  
 of the array.


You can .reserve the space that you need ahead of time.  Then appending  
will always deterministically go into the reserved block, and won't  
reallocate.  This should be relatively quick.  It's not as quick as  
pre-allocating the entire array and then writing the data directly -- you  
still need calls into the runtime for appending.

The appending feature of D arrays/slices is intended to be "good enough"  
for most usages, not horrendously slow, but also not super-optimized for  
specific purposes.

And yes, we still need linked lists, arrays are good for appending, but  
not inserting :)

-Steve
Jun 03 2013
parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 04/06/13 00:57, Steven Schveighoffer wrote:

 On Fri, 31 May 2013 21:04:47 -0400, Peter Williams
 <pwil3058 bigpond.net.au> wrote:

 I do like the idea that "~=" is generally cheap as it potentially
 makes building lists easy (is there any need for the singly linked
 list in D?) and I may modify some of my code.  I've been allocating
 arrays using "new array[size]" where I know that "size" will be the
 max needed but that it may be too much (i.e. throwing away duplicates)
 inserting into the array and then adjusting "length" to whatever I
 used.  In the case, where it's highly likely that the whole array will
 fit in a page I might as well allocate an empty array and use "+=".
 NB there's only one copy of the array.


 You can .reserve the space that you need ahead of time.  Then appending
 will always deterministically go into the reserved block, and won't
 reallocate.  This should be relatively quick.  It's not as quick as
 pre-allocating the entire array and then writing the data directly --
 you still need calls into the runtime for appending.


That's great news.  When I tried to implement what I described above it 
didn't go as well as planned (because I'd misunderstood how much gets 
allocated) and I was thinking that what's needed is a way to tell the 
compiler how much to allocate at the start.  And now you tell me there 
is a way.

This is one of the things I like about learning D.  Almost every time I 
say to myself "I wish there was an easier way to do this" it turns out 
that there is :-).  Some of them are easier to discover than others, though.


 The appending feature of D arrays/slices is intended to be "good enough"
 for most usages, not horrendously slow, but also not super-optimized for
 specific purposes.

 And yes, we still need linked lists, arrays are good for appending, but
 not inserting :)


I use a = a[0..i] ~ v ~ a[i..$] for insertion into a sorted array as I'm 
willing to pay the cost of allocation for the convenience of array 
notation.  One advantage is that finding i is O(log(a.length)) instead 
of O(a.length()).  I also reasoned that the compiler can use memcopy() 
(or whatever its name is) to do the reallocation and therefore it should 
be fairly quick.

I also do a = a[0..i] ~ a[i + 1..$] to remove an item but am starting to 
suspect this isn't as good an idea as for the insert.  Maybe something like:

auto tmp = a[i + 1..$];
a.length = i;
a ~= tmp;

would be more efficient?

Peter
Jun 03 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 03 Jun 2013 20:06:14 -0400, Peter Williams
<pwil3058 bigpond.net.au> wrote:


 On 04/06/13 00:57, Steven Schveighoffer wrote:

 On Fri, 31 May 2013 21:04:47 -0400, Peter Williams
 <pwil3058 bigpond.net.au> wrote:

 I do like the idea that "~=" is generally cheap as it potentially
 makes building lists easy (is there any need for the singly linked
 list in D?) and I may modify some of my code.  I've been allocating
 arrays using "new array[size]" where I know that "size" will be the
 max needed but that it may be too much (i.e. throwing away duplicates)
 inserting into the array and then adjusting "length" to whatever I
 used.  In the case, where it's highly likely that the whole array will
 fit in a page I might as well allocate an empty array and use "+=".
 NB there's only one copy of the array.


 You can .reserve the space that you need ahead of time.  Then appending
 will always deterministically go into the reserved block, and won't
 reallocate.  This should be relatively quick.  It's not as quick as
 pre-allocating the entire array and then writing the data directly --
 you still need calls into the runtime for appending.


 That's great news.  When I tried to implement what I described above it  
 didn't go as well as planned (because I'd misunderstood how much gets  
 allocated) and I was thinking that what's needed is a way to tell the  
 compiler how much to allocate at the start.  And now you tell me there  
 is a way.

 This is one of the things I like about learning D.  Almost every time I  
 say to myself "I wish there was an easier way to do this" it turns out  
 that there is :-).  Some of them are easier to discover than others,  
 though.


I added the capacity, reserve, and assumeSafeAppend array methods when I  
updated the append code, it's been there for a while now, since the  
beginning of 2010.  It was cited in the article mentioned earlier too.   
You might want to re-read that part (it's near the end).


 The appending feature of D arrays/slices is intended to be "good enough"
 for most usages, not horrendously slow, but also not super-optimized for
 specific purposes.

 And yes, we still need linked lists, arrays are good for appending, but
 not inserting :)


 I use a = a[0..i] ~ v ~ a[i..$] for insertion into a sorted array as I'm  
 willing to pay the cost of allocation for the convenience of array  
 notation.  One advantage is that finding i is O(log(a.length)) instead  
 of O(a.length()).  I also reasoned that the compiler can use memcopy()  
 (or whatever its name is) to do the reallocation and therefore it should  
 be fairly quick.


ugh.  Sorry, the performance miser in me must object :)

There are better ways to do this, using range operations.  I'm pretty sure  
you could do it with std.algorithm.copy.


 I also do a = a[0..i] ~ a[i + 1..$] to remove an item but am starting to  
 suspect this isn't as good an idea as for the insert.  Maybe something  
 like:

 auto tmp = a[i + 1..$];
 a.length = i;
 a ~= tmp;

 would be more efficient?


No, because that will also reallocate, just like your original.  This one  
is REALLY easy to get right, because it can be done in place (assuming a  
is not const/immutable).

You can even do:

memmove(&a[i], &a[i + 1], a.length - i - 1);
a.length--;

For some reason, D doesn't support overlapping moves, otherwise, this  
would work:

a[i..$-1] = a[i + 1..$];
a.length--;

I think std.algorithm.remove can do the same thing in one line.

-Steve
Jun 03 2013
next sibling parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 04/06/13 11:56, Steven Schveighoffer wrote:

 On Mon, 03 Jun 2013 20:06:14 -0400, Peter Williams

 That's great news.  When I tried to implement what I described above
 it didn't go as well as planned (because I'd misunderstood how much
 gets allocated) and I was thinking that what's needed is a way to tell
 the compiler how much to allocate at the start.  And now you tell me
 there is a way.

 This is one of the things I like about learning D.  Almost every time
 I say to myself "I wish there was an easier way to do this" it turns
 out that there is :-).  Some of them are easier to discover than
 others, though.


 I added the capacity, reserve, and assumeSafeAppend array methods when I
 updated the append code, it's been there for a while now, since the
 beginning of 2010.  It was cited in the article mentioned earlier too.
 You might want to re-read that part (it's near the end).


I'm finding that the mind tends to skip (even potentially useful) bits 
when reading about computer languages that are similar to ones that I'm 
familiar with.  I've had the same thing happen with Andrei's book i.e. 
when I discover something new I say to myself "Why didn't Andrei mention 
this?" only to discover (on rereading the pertinent section) that he did 
but it didn't register.  I've decided to reread his book cover to cover.


 The appending feature of D arrays/slices is intended to be "good enough"
 for most usages, not horrendously slow, but also not super-optimized for
 specific purposes.

 And yes, we still need linked lists, arrays are good for appending, but
 not inserting :)


 I use a = a[0..i] ~ v ~ a[i..$] for insertion into a sorted array as
 I'm willing to pay the cost of allocation for the convenience of array
 notation.  One advantage is that finding i is O(log(a.length)) instead
 of O(a.length()).  I also reasoned that the compiler can use memcopy()
 (or whatever its name is) to do the reallocation and therefore it
 should be fairly quick.


 ugh.  Sorry, the performance miser in me must object :)

 There are better ways to do this, using range operations.  I'm pretty
 sure you could do it with std.algorithm.copy.


 I also do a = a[0..i] ~ a[i + 1..$] to remove an item but am starting
 to suspect this isn't as good an idea as for the insert.  Maybe
 something like:

 auto tmp = a[i + 1..$];
 a.length = i;
 a ~= tmp;

 would be more efficient?


 No, because that will also reallocate,


Wouldn't the a.length = i prevent that?


 just like your original.  This
 one is REALLY easy to get right, because it can be done in place
 (assuming a is not const/immutable).

 You can even do:

 memmove(&a[i], &a[i + 1], a.length - i - 1);
 a.length--;

 For some reason, D doesn't support overlapping moves,


Probably because there's some instances where it would be a disaster and 
explaining all the cases where you can and can't becomes too difficult 
so it's just easier to say no to all cases.


 otherwise, this
 would work:

 a[i..$-1] = a[i + 1..$];
 a.length--;

 I think std.algorithm.remove can do the same thing in one line.


As I said somewhere else, there's a need for a book on Phobos.

Thanks
Peter
Jun 03 2013
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 03 Jun 2013 23:38:12 -0400, Peter Williams  
<pwil3058 bigpond.net.au> wrote:


 On 04/06/13 11:56, Steven Schveighoffer wrote:

 On Mon, 03 Jun 2013 20:06:14 -0400, Peter Williams





 auto tmp = a[i + 1..$];
 a.length = i;
 a ~= tmp;

 would be more efficient?


 No, because that will also reallocate,


 Wouldn't the a.length = i prevent that?


No.  The runtime specifically will reallocate on this case.

It does not know that tmp is never going to be used again, nor does it  
know that there aren't any other references to the data past i.  It MUST  
reallocate to avoid stomping (in fact, prior to my changes it DID  
overwrite).

Case in point, if it didn't reallocate, the above would be copying tmp  
over itself, offset by one!

The runtime expects that when it is appending data, it is doing so into  
space that is currently unused.  You can use assumeSafeAppend to tell it  
"the data after this is unused", but then it better be unused :)  In your  
case, you are using it (via tmp), so that doesn't work.


 For some reason, D doesn't support overlapping moves,


 Probably because there's some instances where it would be a disaster and  
 explaining all the cases where you can and can't becomes too difficult  
 so it's just easier to say no to all cases.


No, memmove is valid C code and supports overlapping writes.  It's not as  
optimized as memcpy, which does not.

But I don't know exactly what the difference is.  A simple check at the  
beginning can determine which mode to use, memmove should devolve to  
memcpy if there is no overlap.  And in some cases, the compiler  
specifically knows whether there is overlap at compile time.

-Steve
Jun 03 2013
prev sibling next sibling parent Peter Williams <pwil3058 bigpond.net.au> writes:
On 04/06/13 11:56, Steven Schveighoffer wrote:

 On Mon, 03 Jun 2013 20:06:14 -0400, Peter Williams
 <pwil3058 bigpond.net.au> wrote:

 I use a = a[0..i] ~ v ~ a[i..$] for insertion into a sorted array as
 I'm willing to pay the cost of allocation for the convenience of array
 notation.  One advantage is that finding i is O(log(a.length)) instead
 of O(a.length()).  I also reasoned that the compiler can use memcopy()
 (or whatever its name is) to do the reallocation and therefore it
 should be fairly quick.


 ugh.  Sorry, the performance miser in me must object :)


I worry about correct first and then come back and worry about 
efficiency.  That way I have tests in place to make sure I don't break 
things during tweaking.  :-)


 There are better ways to do this, using range operations.  I'm pretty
 sure you could do it with std.algorithm.copy.


To insert "newElement" into array a" at index "i" where "i <= a.length", 
I've come up with:

     a ~= newElement;
     if (a.length > 1 && i < a.length - 1) {
         copy(retro(a[i .. $ - 1]), retro(a[i + 1 .. $]));
         a[i] = newElement;
     }

which works (i.e. it is correct in that it passes my unit tests).  I'm 
assuming allocation will only occur if it's required for the first line?

Peter
PS It's not as pretty as the original.
PPS For remove, "a = a.remove(index);" does the job.
Jun 03 2013
prev sibling parent Peter Williams <pwil3058 bigpond.net.au> writes:
On 04/06/13 15:25, Peter Williams wrote:

 On 04/06/13 11:56, Steven Schveighoffer wrote:

 On Mon, 03 Jun 2013 20:06:14 -0400, Peter Williams
 <pwil3058 bigpond.net.au> wrote:

 I use a = a[0..i] ~ v ~ a[i..$] for insertion into a sorted array as
 I'm willing to pay the cost of allocation for the convenience of array
 notation.  One advantage is that finding i is O(log(a.length)) instead
 of O(a.length()).  I also reasoned that the compiler can use memcopy()
 (or whatever its name is) to do the reallocation and therefore it
 should be fairly quick.


 ugh.  Sorry, the performance miser in me must object :)


 I worry about correct first and then come back and worry about
 efficiency.  That way I have tests in place to make sure I don't break
 things during tweaking.  :-)


 There are better ways to do this, using range operations.  I'm pretty
 sure you could do it with std.algorithm.copy.


 To insert "newElement" into array a" at index "i" where "i <= a.length",
 I've come up with:

      a ~= newElement;
      if (a.length > 1 && i < a.length - 1) {
          copy(retro(a[i .. $ - 1]), retro(a[i + 1 .. $]));
          a[i] = newElement;
      }

 which works (i.e. it is correct in that it passes my unit tests).  I'm
 assuming allocation will only occur if it's required for the first line?

 Peter
 PS It's not as pretty as the original.
 PPS For remove, "a = a.remove(index);" does the job.


I've since discovered std.array.insertInPlace() which does the job in a 
single call statement.

I found it interesting that std.algorithm has a remove but no insert and 
std.array has an insert but no remove.

Peter
Jun 03 2013
prev sibling parent Peter Williams <pwil3058 bigpond.net.au> writes:
On 30/05/13 16:21, Ali Çehreli wrote:

 On 05/29/2013 06:54 PM, Peter Williams wrote:
  > Wouldn't a better rule for pass by value be that any changes to
  > the data part of the array (including assignment to an element) causes
  > reallocation of the entire data portion.

 The type of a slice parameter is not different than a local slice
 variable. Since we wouldn't want an entire copy of the elements due to
 an element mutation:

      int[] whole = // ...;
      int[] firstHalf = whole[0 .. $/2];
      firstHalf = 42;    // this should affect whole

 Moving the last two lines to a new function should not change meaning:

      int[] whole = // ...;
      setFirstHalf(whole, 42);  // should still affect whole


I think that setFirstHalf() should only effect whole if it's passed in 
by reference.  I certainly intend to adopt that practice in my D code.

Peter
May 30 2013
prev sibling parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Wednesday, 29 May 2013 at 23:45:04 UTC, Ali Çehreli wrote:

 On 05/29/2013 03:59 PM, Peter Williams wrote:


 I've been trying to find out how non ref array arguments are


 passed to

 functions in D but can't find any documentation on it.


 The following concepts are relevant:

 - Dynamic array: Maintained by the D runtime


Generally yes, but not always http://dpaste.dzfl.pl/ffbcb449


 - Fixed-length array (aka static array): Can be on the stack

 - Slice: An efficient tool to access a range of elements (of 
 any type of array)

 Usually, it is the slice that gets passed:

   void foo(int[] slice);


Isn't it a dynamic array? I don't understand listing slice as 
separate type of arrays or mixing meaning of slice and dynamic 
array. As far as D spec is concerned, slice is a SliceExpression 
which produces dynamic array for array types.


 A slice is made up of the pointer to the first element and the 
 number of elements:

 struct __SomeImplementationDependentName__
 {
     size_t length;
     void * ptr;
 }

 Ali
May 29 2013
parent reply "Diggory" <diggsey googlemail.com> writes:
On Thursday, 30 May 2013 at 05:41:06 UTC, Maxim Fomin wrote:

 On Wednesday, 29 May 2013 at 23:45:04 UTC, Ali Çehreli wrote:

 On 05/29/2013 03:59 PM, Peter Williams wrote:


 I've been trying to find out how non ref array arguments are


 passed to

 functions in D but can't find any documentation on it.


 The following concepts are relevant:

 - Dynamic array: Maintained by the D runtime


 Generally yes, but not always http://dpaste.dzfl.pl/ffbcb449


That's not a dynamic array, it's a slice of a static array.


 - Fixed-length array (aka static array): Can be on the stack

 - Slice: An efficient tool to access a range of elements (of 
 any type of array)

 Usually, it is the slice that gets passed:

  void foo(int[] slice);


 Isn't it a dynamic array? I don't understand listing slice as 
 separate type of arrays or mixing meaning of slice and dynamic 
 array. As far as D spec is concerned, slice is a 
 SliceExpression which produces dynamic array for array types.


You can't directly access dynamic arrays in D, you can only 
manipulate views of them using slices. "new int[5]" creates a new 
dynamic array internally but only returns a slice of that array.
May 29 2013
parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 05:44:43 UTC, Diggory wrote:

 On Thursday, 30 May 2013 at 05:41:06 UTC, Maxim Fomin wrote:

 On Wednesday, 29 May 2013 at 23:45:04 UTC, Ali Çehreli wrote:

 On 05/29/2013 03:59 PM, Peter Williams wrote:


 I've been trying to find out how non ref array arguments are


 passed to

 functions in D but can't find any documentation on it.


 The following concepts are relevant:

 - Dynamic array: Maintained by the D runtime


 Generally yes, but not always http://dpaste.dzfl.pl/ffbcb449


 That's not a dynamic array, it's a slice of a static array.


And this is a problem, because article about D slices encourages 
to call some raw memory (which almost never is directly 
manipulated and doesn't appear in source code) as a dynamic 
array, and dynamic array as a slice.


 - Fixed-length array (aka static array): Can be on the stack

 - Slice: An efficient tool to access a range of elements (of 
 any type of array)

 Usually, it is the slice that gets passed:

 void foo(int[] slice);


 Isn't it a dynamic array? I don't understand listing slice as 
 separate type of arrays or mixing meaning of slice and dynamic 
 array. As far as D spec is concerned, slice is a 
 SliceExpression which produces dynamic array for array types.


 You can't directly access dynamic arrays in D, you can only 
 manipulate views of them using slices. "new int[5]" creates a 
 new dynamic array internally but only returns a slice of that 
 array.


That's clear, issue here is misleading definitions used by D 
slices article.

typeof(slice) => int[]

 From array page spec: type[] => dynamic array. So, int[] slice is 
a parameter of type 'dynamic array'.

 From expression spec page what slice is:
SliceExpression:
    PostfixExpression [ ]
    PostfixExpression [ AssignExpression .. AssignExpression ]

and clearly 'slice' object is not an expression.
May 29 2013
next sibling parent reply "Diggory" <diggsey googlemail.com> writes:
On Thursday, 30 May 2013 at 05:54:57 UTC, Maxim Fomin wrote:

 On Thursday, 30 May 2013 at 05:44:43 UTC, Diggory wrote:

 On Thursday, 30 May 2013 at 05:41:06 UTC, Maxim Fomin wrote:

 On Wednesday, 29 May 2013 at 23:45:04 UTC, Ali Çehreli wrote:

 On 05/29/2013 03:59 PM, Peter Williams wrote:


 I've been trying to find out how non ref array arguments 
 are


 passed to

 functions in D but can't find any documentation on it.


 The following concepts are relevant:

 - Dynamic array: Maintained by the D runtime


 Generally yes, but not always http://dpaste.dzfl.pl/ffbcb449


 That's not a dynamic array, it's a slice of a static array.


 And this is a problem, because article about D slices 
 encourages to call some raw memory (which almost never is 
 directly manipulated and doesn't appear in source code) as a 
 dynamic array, and dynamic array as a slice.


The article about slices on this site - 
http://dlang.org/d-array-article.html is perfectly correct.


 - Fixed-length array (aka static array): Can be on the stack

 - Slice: An efficient tool to access a range of elements (of 
 any type of array)

 Usually, it is the slice that gets passed:

 void foo(int[] slice);


 Isn't it a dynamic array? I don't understand listing slice as 
 separate type of arrays or mixing meaning of slice and 
 dynamic array. As far as D spec is concerned, slice is a 
 SliceExpression which produces dynamic array for array types.


 You can't directly access dynamic arrays in D, you can only 
 manipulate views of them using slices. "new int[5]" creates a 
 new dynamic array internally but only returns a slice of that 
 array.


 That's clear, issue here is misleading definitions used by D 
 slices article.

 typeof(slice) => int[]

 From array page spec: type[] => dynamic array. So, int[] slice 
 is a parameter of type 'dynamic array'.


Yep, it's misleading but the D documentation is misleading and 
wrong in a lot of places and I'd say here the problems are 
relatively minor. Still they should be fixed.


 From expression spec page what slice is:
 SliceExpression:
    PostfixExpression [ ]
    PostfixExpression [ AssignExpression .. AssignExpression ]

 and clearly 'slice' object is not an expression.


This is talking about the slice operator, not slices. The slice 
operator can be applied to any object which defines it.
May 29 2013
parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 06:08:09 UTC, Diggory wrote:

 On Thursday, 30 May 2013 at 05:54:57 UTC, Maxim Fomin wrote:

 On Thursday, 30 May 2013 at 05:44:43 UTC, Diggory wrote:

 On Thursday, 30 May 2013 at 05:41:06 UTC, Maxim Fomin wrote:

 On Wednesday, 29 May 2013 at 23:45:04 UTC, Ali Çehreli wrote:

 On 05/29/2013 03:59 PM, Peter Williams wrote:


 I've been trying to find out how non ref array arguments 
 are


 passed to

 functions in D but can't find any documentation on it.


 The following concepts are relevant:

 - Dynamic array: Maintained by the D runtime


 Generally yes, but not always http://dpaste.dzfl.pl/ffbcb449


 That's not a dynamic array, it's a slice of a static array.


 And this is a problem, because article about D slices 
 encourages to call some raw memory (which almost never is 
 directly manipulated and doesn't appear in source code) as a 
 dynamic array, and dynamic array as a slice.


 The article about slices on this site - 
 http://dlang.org/d-array-article.html is perfectly correct.


No, the article is incorrect in vocabulary because it contradicts 
to the spec definitions, and spec incompletence is not a reason 
to dilute what is already defined. What actually happens is:
1) T[] is defined as dynamic array,  PostfixExpression [ ] is 
defined as SliceExpression.
2) Array article calls dynamic arrays as slices. Since notion of 
dynamic array is occupied, the article calls GC memory as dynamic 
array. This is a complete contradiction to spec.
3) Folks start using these misleading definitions.

This actually leads to incorrect assumptions, as was pointed out 
previously that dynamic array points only to runtime memory 
(which is not always the case).


 - Fixed-length array (aka static array): Can be on the stack

 - Slice: An efficient tool to access a range of elements 
 (of any type of array)

 Usually, it is the slice that gets passed:

 void foo(int[] slice);


 Isn't it a dynamic array? I don't understand listing slice 
 as separate type of arrays or mixing meaning of slice and 
 dynamic array. As far as D spec is concerned, slice is a 
 SliceExpression which produces dynamic array for array types.


 You can't directly access dynamic arrays in D, you can only 
 manipulate views of them using slices. "new int[5]" creates a 
 new dynamic array internally but only returns a slice of that 
 array.


 That's clear, issue here is misleading definitions used by D 
 slices article.

 typeof(slice) => int[]

 From array page spec: type[] => dynamic array. So, int[] slice 
 is a parameter of type 'dynamic array'.


 Yep, it's misleading but the D documentation is misleading and 
 wrong in a lot of places and I'd say here the problems are 
 relatively minor. Still they should be fixed.


This is not a reason to confuse what exists.


 From expression spec page what slice is:
 SliceExpression:
   PostfixExpression [ ]
   PostfixExpression [ AssignExpression .. AssignExpression ]

 and clearly 'slice' object is not an expression.


 This is talking about the slice operator, not slices. The slice 
 operator can be applied to any object which defines it.


than please point out what else slice according to spec is (spec 
mentions slices in context of SliceExpressions and it is the only 
valid usage).
May 30 2013
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, May 30, 2013 09:01:06 Maxim Fomin wrote:

 The article about slices on this site -
 http://dlang.org/d-array-article.html is perfectly correct.


 
 No, the article is incorrect in vocabulary because it contradicts
 to the spec definitions, and spec incompletence is not a reason
 to dilute what is already defined. What actually happens is:
 1) T[] is defined as dynamic array,  PostfixExpression [ ] is
 defined as SliceExpression.
 2) Array article calls dynamic arrays as slices. Since notion of
 dynamic array is occupied, the article calls GC memory as dynamic
 array. This is a complete contradiction to spec.
 3) Folks start using these misleading definitions.
 
 This actually leads to incorrect assumptions, as was pointed out
 previously that dynamic array points only to runtime memory
 (which is not always the case).


Much as I love that article, I really don't like the fact that it tries to 
claim that dynamic arrays and slices are two different things, since they 
aren't. T[] is a dynamic array _and_ a slice, and for the article to be 
completely correct in its terminology, it would actually be incorrect to refer 
to _anything_ in D as a dynamic array, as it would be something completely 
internal to the runtime. T[] would be only a slice, and the type system 
wouldn't have dynamic arrays in it anywhere.

The runtime holds the memory that dynamic arrays / slices refer to, but I 
really wish that that article had not referred to that underlying memory as 
being the dymanic array as opposed to simply a block of memory that the 
runtime gave slices to, letting the slices be referred to as dynamic arrays 
like they are.

I would argue that all dynamic arrays are array slices and vice versa. And 
that's how std.traits.isDynamicArray treats them as well.

- Jonathan M Davis
May 30 2013
parent reply "Diggory" <diggsey googlemail.com> writes:
On Thursday, 30 May 2013 at 07:15:39 UTC, Jonathan M Davis wrote:

 On Thursday, May 30, 2013 09:01:06 Maxim Fomin wrote:

 The article about slices on this site -
 http://dlang.org/d-array-article.html is perfectly correct.


 
 No, the article is incorrect in vocabulary because it 
 contradicts
 to the spec definitions, and spec incompletence is not a reason
 to dilute what is already defined. What actually happens is:
 1) T[] is defined as dynamic array,  PostfixExpression [ ] is
 defined as SliceExpression.
 2) Array article calls dynamic arrays as slices. Since notion 
 of
 dynamic array is occupied, the article calls GC memory as 
 dynamic
 array. This is a complete contradiction to spec.
 3) Folks start using these misleading definitions.
 
 This actually leads to incorrect assumptions, as was pointed 
 out
 previously that dynamic array points only to runtime memory
 (which is not always the case).


 Much as I love that article, I really don't like the fact that 
 it tries to
 claim that dynamic arrays and slices are two different things, 
 since they
 aren't. T[] is a dynamic array _and_ a slice, and for the 
 article to be
 completely correct in its terminology, it would actually be 
 incorrect to refer
 to _anything_ in D as a dynamic array, as it would be something 
 completely
 internal to the runtime. T[] would be only a slice, and the 
 type system
 wouldn't have dynamic arrays in it anywhere.

 The runtime holds the memory that dynamic arrays / slices refer 
 to, but I
 really wish that that article had not referred to that 
 underlying memory as
 being the dymanic array as opposed to simply a block of memory 
 that the
 runtime gave slices to, letting the slices be referred to as 
 dynamic arrays
 like they are.

 I would argue that all dynamic arrays are array slices and vice 
 versa. And
 that's how std.traits.isDynamicArray treats them as well.

 - Jonathan M Davis


But it's clearly not the case that all slices are dynamic 
arrays... A dynamic array is already a well-established term to 
mean an array allocated on the heap. Slices can point to arrays 
on the stack.
May 30 2013
next sibling parent "Dicebot" <m.strashun gmail.com> writes:
On Thursday, 30 May 2013 at 08:11:08 UTC, Diggory wrote:

 But it's clearly not the case that all slices are dynamic 
 arrays... A dynamic array is already a well-established term to 
 mean an array allocated on the heap. Slices can point to arrays 
 on the stack.


Where did you get that definition? Dynamic arrays can change 
size. Static can't. It does not matter where memory is actually 
allocated. C array allocated on heap is still static array.
May 30 2013
prev sibling parent "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 08:11:08 UTC, Diggory wrote:

 But it's clearly not the case that all slices are dynamic 
 arrays... A dynamic array is already a well-established term to 
 mean an array allocated on the heap. Slices can point to arrays 
 on the stack.


Confusion comes from calling a dynamic array as a slice and 
runtime memory as a dynamic array. Memory kind allocation and 
dynamic/static kind of array are quite ortogonal issues with high 
correlation between dynamic array and heap memory which is not 1.

extern(C) int printf(const char*,...);

struct S
{
	int[3] s;
}

int[] foo()
{
	S* s = new S; //static array in heap
	int[] ret = s.s;
	return ret; //dynamic array in heap
}

void bar(int[] data...)
{
	printf("%p\n", data.ptr); // dynamic array in stack
}

void main()
{
	int[] arr = foo();
	printf("%p\n", arr.ptr);
	bar(0,1,2);
}

http://dpaste.dzfl.pl/4df8108d

Note, that s.s in foo() is clearly a static array, but it is 
still in the heap. By the way, this kills idea that casting from 
static array to dynamic array always leads to stack memory 
pointer leak, as well as idea that 'slice to static array' can 
only point to the stack memory.
May 30 2013
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/29/2013 10:54 PM, Maxim Fomin wrote:


 And this is a problem, because article about D slices encourages to call
 some raw memory (which almost never is directly manipulated and doesn't
 appear in source code) as a dynamic array, and dynamic array as a slice.


An array is simply consecutive elements in memory. There are two types 
of arrays: static (aka fixed-length) and dynamic.

Slice is not an array itself: It is both an accessor to array elements 
(static or dynamic) and a tool that can spawn a new dynamic array when 
another element is appended to its view.

Documentations use "slice" and "dynamic array" synonymously because of 
the latter semantics.

Ali
May 29 2013
parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 06:12:03 UTC, Ali Çehreli wrote:

 On 05/29/2013 10:54 PM, Maxim Fomin wrote:


 And this is a problem, because article about D slices


 encourages to call

 some raw memory (which almost never is directly manipulated


 and doesn't

 appear in source code) as a dynamic array, and dynamic array


 as a slice.

 An array is simply consecutive elements in memory. There are 
 two types of arrays: static (aka fixed-length) and dynamic.


As a general programming notion - yes, in D (array spec page):
"Dynamic arrays consist of a length and a pointer to the array 
data."

This actually kills two misinterpretations encouraged by array 
article that a) dynamic array is some kind of runtime memory b) 
that T[] data is not a dynamic array, it is a slice.


 Slice is not an array itself: It is both an accessor to array 
 elements (static or dynamic) and a tool that can spawn a new 
 dynamic array when another element is appended to its view.

 Documentations use "slice" and "dynamic array" synonymously 
 because of the latter semantics.

 Ali
May 30 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/30/2013 12:11 AM, Maxim Fomin wrote:


 On Thursday, 30 May 2013 at 06:12:03 UTC, Ali Çehreli wrote:

 On 05/29/2013 10:54 PM, Maxim Fomin wrote:


 And this is a problem, because article about D slices


 encourages to call

 some raw memory (which almost never is directly manipulated


 and doesn't

 appear in source code) as a dynamic array, and dynamic array


 as a slice.

 An array is simply consecutive elements in memory. There are two types
 of arrays: static (aka fixed-length) and dynamic.


 As a general programming notion - yes, in D (array spec page):
 "Dynamic arrays consist of a length and a pointer to the array data."


Then the spec is wrong because that is the definition of a slice. The 
reason is, there is no dynamic array is sight below but a static array 
and a slice:

     int[10] arr;
     int[] slice = arr;
     assert(slice.ptr == &arr[0]);  // (yes, same as arr.ptr)

Even though 'slice' above "consists of a length a pointer to the array 
data" despite the language of the spec, that is not a dynamic array:

     slice[0] = 42;

The static array's element is changed, not some dynamic array's.

The correct description is that the 'slice' variable above is a slice, 
having the ability to refer to elements of a dynamic array and a static 
array.

(I know I am repeating the article at this point but it happens to be 
the fact.) If there is no dynamic array to speak of above, what is a 
dynamic array then? The answer is, dynamic array is an entity that is 
owned and managed by the D runtime.

For the above code to finally involve a dynamic array, we can add an 
element to 'slice':

     slice ~= 7;
     assert(slice.ptr != &arr[0]);

Now there is a dynamic array but it is not our 'slice' that is the 
dynamic array. Here is the proof:

     slice = arr[5 .. $];
     assert(slice.ptr == &arr[5]);

Has 'slice' been a dynamic array until that last assignment and suddenly 
become a slice again? No, D does not involve type changes like that. It 
has always been a slice, which is not the same thing as a dynamic array.


 This actually kills two misinterpretations encouraged by array article
 that a) dynamic array is some kind of runtime memory


I still think so.


 b) that T[] data is not a dynamic array, it is a slice.


I still think so.

The spec must be outdated then; the array semantics have been finalized 
relatively recently (in 2009? or 2010?).

Ali
May 30 2013
parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 07:57:41 UTC, Ali Çehreli wrote:

 On 05/30/2013 12:11 AM, Maxim Fomin wrote:

 As a general programming notion - yes, in D (array spec page):
 "Dynamic arrays consist of a length and a pointer to the


 array data."

 Then the spec is wrong because that is the definition of a 
 slice. The reason is, there is no dynamic array is sight below 
 but a static array and a slice:

     int[10] arr;
     int[] slice = arr;
     assert(slice.ptr == &arr[0]);  // (yes, same as arr.ptr)


No, spec is right and article is wrong. It uses incorrect 
definition and calls correct definitions as incorrect. Is exactly 
what is writing an article calling dynamic array to be not a 
dynamic array but a banana and latter calling original definition 
incorrect because according to the article it is a banana.


 Even though 'slice' above "consists of a length a pointer to 
 the array data" despite the language of the spec, that is not a 
 dynamic array:

     slice[0] = 42;

 The static array's element is changed, not some dynamic array's.


This does not mean that the object is not a dynamic array (false 
logic consequence).


 The correct description is that the 'slice' variable above is a 
 slice, having the ability to refer to elements of a dynamic 
 array and a static array.


static assert(typeof(slice) == typeof(int[])); // int[] type is 
dynamic array

this checks that object 'slice' is of type dynamic array. Note, 
that notion of slice is not embebed into compiler at all (you 
cannot test whether some object is of type 'slice' or not).


 (I know I am repeating the article at this point but it happens 
 to be the fact.) If there is no dynamic array to speak of 
 above, what is a dynamic array then? The answer is, dynamic 
 array is an entity that is owned and managed by the D runtime.


This is recalling incorrect definitions from article. You are 
simply assuming that dynamic array is runtime memory and 
everything which does not refer to runtime memory is not a 
dynamic array. This is wrong because dynamic array is not defined 
to be runtime memory and not promised to be in 100% cases. 
Consider example with typesafe variardic functions when dynamic 
array is constructed on caller side from stack memory. It is of 
type dynamic array yet it is not from runtime memory. By the way, 
this is good example of how incorrect definition confuses people 
and make them to write buggy code. I remember at least two bugs 
in bugzilla when people were complaining that 'dynamic array from 
typesafe variardic function seems not to refer to runtime memory'.


 For the above code to finally involve a dynamic array, we can 
 add an element to 'slice':

     slice ~= 7;
     assert(slice.ptr != &arr[0]);

 Now there is a dynamic array but it is not our 'slice' that is 
 the dynamic array. Here is the proof:

     slice = arr[5 .. $];
     assert(slice.ptr == &arr[5]);

 Has 'slice' been a dynamic array until that last assignment and 
 suddenly become a slice again? No, D does not involve type 
 changes like that. It has always been a slice, which is not the 
 same thing as a dynamic array.


One of the funny consequences of using incorrect definition is 
that is forces to call an entity as not a dynamic array and after 
some manipulations the same entity to call a dynamic array. This 
is obviously wrong because it is the same object.


 This actually kills two misinterpretations encouraged by


 array article

 that a) dynamic array is some kind of runtime memory


 I still think so.


 b) that T[] data is not a dynamic array, it is a slice.


 I still think so.

 The spec must be outdated then; the array semantics have been 
 finalized relatively recently (in 2009? or 2010?).

 Ali


Actually the article should be updated in accordance with the 
spec.
May 30 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 30 May 2013 04:58:46 -0400, Maxim Fomin <maxim maxim-fomin.ru>  
wrote:


 No, spec is right and article is wrong. It uses incorrect definition and  
 calls correct definitions as incorrect. Is exactly what is writing an  
 article calling dynamic array to be not a dynamic array but a banana and  
 latter calling original definition incorrect because according to the  
 article it is a banana.


The spec needs to be clarified.  I caution that the spec is misleading in  
the article:

"In fact, most D coders consider the D slice to be the dynamic array type  
-- it's even listed as a dynamic array type in the spec!"

A dynamic array is one that can add length, a slice is NOT a dynamic  
array, it is a view of a chunk of data.  Without the runtime managing  
dynamic arrays using the GC, the slice could not be extended.  When you  
"add length" to a slice, the runtime takes the following steps:

1. Is this slice pointing into a dynamic array?  If not, go to step 3
2. Can the dynamic array expand in place?  If so, do it
3. Create a new dynamic array that can hold the data plus the extra length  
(and perhaps some extra reserved space to amortize appending), copy the  
existing slice data to that new dynamic array, and update the slice to  
point at that array.

It does NOT deallocate the original data, nor does it change any other  
references to the original data, and this aspect is important.  The slice  
has no ownership of the data, it is a view.  We agree as coders not to  
care what happens to the old data or when the slice shifts views to a new  
dynamic array, in trade for the convenience and illusion of slices being  
similar to dynamic arrays.

Note also that when a slice "shrinks", it does nothing to alter the  
dynamic array size or data.

A slice is not a dynamic array, any more than a pair of iterators is a  
dynamic array.  It does behave similarly to a dynamic array through the  
magic of UFCS and the runtime.  But not exactly the same.


 static assert(typeof(slice) == typeof(int[])); // int[] type is dynamic  
 array


Your definition of dynamic array is wrong.  Built-in dynamic arrays in D  
have no formal type, the runtime manages them.

There is no sense in arguing further, if you think int[] is a dynamic  
array, you are simply using the wrong definition, and we must agree on  
these basics in order to have a meaningful discussion.

A good formal definition of a dynamic array can be found here:

http://en.wikipedia.org/wiki/Dynamic_array

It is what I read while writing that article, to make sure I got my  
definitions correct.  D's dynamic array is a "bounded size dynamic array."

-Steve
May 30 2013
next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Thursday, 30 May 2013 at 14:36:23 UTC, Steven Schveighoffer 
wrote:

 The spec needs to be clarified.  I caution that the spec is 
 misleading in the article:

 -snip-


I agree that the slice/dynamic array distinction is important to 
make.

The vague, sometimes contradictory specification has done a lot 
of damage to beginners of D trying to learn about D's slices. In 
the IRC channel, helping beginners understand D's slices is a 
recurring theme. During the last year or so, there's been a trend 
to teach from the POV of making the distinction, and it helps *a 
lot*. The article now on the official website, which embraces the 
non-conflative way of reasoning about it, has been a valuable 
tool along the way.

There's a reason why such a big portion of the community has 
adopted this terminology even after we were all familiar with the 
conflation (it's because it's simply better).

I remember long ago there were even talks of separating slices 
and dynamic arrays in the type system of D2. It was too big a 
change too late, but the fact that this was considered so 
strongly by the community brings some background to the current 
debate.
May 30 2013
prev sibling parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 14:36:23 UTC, Steven Schveighoffer 
wrote:

 On Thu, 30 May 2013 04:58:46 -0400, Maxim Fomin 
 <maxim maxim-fomin.ru> wrote:


 No, spec is right and article is wrong. It uses incorrect 
 definition and calls correct definitions as incorrect. Is 
 exactly what is writing an article calling dynamic array to be 
 not a dynamic array but a banana and latter calling original 
 definition incorrect because according to the article it is a 
 banana.


 The spec needs to be clarified.  I caution that the spec is 
 misleading in the article:

 "In fact, most D coders consider the D slice to be the dynamic 
 array type -- it's even listed as a dynamic array type in the 
 spec!"


No, sorry this cannot be accepted. Formal definitions can be 
changed due to private POV and as far as spec exists, it is 
higher priority on any private POV, especially when it is 
problematic.


 A dynamic array is one that can add length, a slice is NOT a 
 dynamic array, it is a view of a chunk of data.  Without the 
 runtime managing dynamic arrays using the GC, the slice could 
 not be extended.  When you "add length" to a slice, the runtime 
 takes the following steps:

 1. Is this slice pointing into a dynamic array?  If not, go to 
 step 3
 2. Can the dynamic array expand in place?  If so, do it
 3. Create a new dynamic array that can hold the data plus the 
 extra length (and perhaps some extra reserved space to amortize 
 appending), copy the existing slice data to that new dynamic 
 array, and update the slice to point at that array.


This is again dispute about what is slice and what is dynamic 
array. Note, that such definition confuses array kind and memory 
kind which encourage applying wrong assumptions that dynamic 
array means only heap memory. As mentioned previosly, there is no 
100% relation between dynamic array type and runtime memory.


 It does NOT deallocate the original data, nor does it change 
 any other references to the original data, and this aspect is 
 important.  The slice has no ownership of the data, it is a 
 view.  We agree as coders not to care what happens to the old 
 data or when the slice shifts views to a new dynamic array, in 
 trade for the convenience and illusion of slices being similar 
 to dynamic arrays.

 Note also that when a slice "shrinks", it does nothing to alter 
 the dynamic array size or data.

 A slice is not a dynamic array, any more than a pair of 
 iterators is a dynamic array.  It does behave similarly to a 
 dynamic array through the magic of UFCS and the runtime.  But 
 not exactly the same.


 static assert(typeof(slice) == typeof(int[])); // int[] type 
 is dynamic array


 Your definition of dynamic array is wrong.  Built-in dynamic 
 arrays in D have no formal type, the runtime manages them.


Yes, they are, as far as spec exists. There is no thing like 'my' 
definition, I refer to official spec. Note, that it is supported 
also by TDPL and the only objection to it is ungrounded article 
which confuses things.


 There is no sense in arguing further, if you think int[] is a 
 dynamic array, you are simply using the wrong definition, and 
 we must agree on these basics in order to have a meaningful 
 discussion.

 A good formal definition of a dynamic array can be found here:

 http://en.wikipedia.org/wiki/Dynamic_array


That is a general idea like an array which was mentioned by Ali.


 It is what I read while writing that article, to make sure I 
 got my definitions correct.  D's dynamic array is a "bounded 
 size dynamic array."

 -Steve


That' fine that you check things, but this does not mean that 
they are 100% correct. Note, that article definiton comes from 
nowhere (at least I have found no sources why it calls things 
this way and why spec is wrong, and what is more important, my 
guess is that name collision comes from author confusion between 
runtime implementation and formal language description, for ex. 
_d_newitemT returns void* which does not mean that new expression 
return void pointers).
May 30 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 30 May 2013 12:08:45 -0400, Maxim Fomin <maxim maxim-fomin.ru>  
wrote:


 No, sorry this cannot be accepted. Formal definitions can be changed due  
 to private POV and as far as spec exists, it is higher priority on any  
 private POV, especially when it is problematic.


If we don't use the same terms to mean the same things, then there is no  
point in discussing.

The spec's definition is somewhat wrong, and needs to be clarified.  This  
is an important thing when people coming from other languages are trying  
to anchor what they know to what D provides, we need to use correct  
terminology.

Once that is fixed (and you can come to grips with the change), we can  
discuss.

-Steve
May 30 2013
parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 16:25:53 UTC, Steven Schveighoffer 
wrote:

 On Thu, 30 May 2013 12:08:45 -0400, Maxim Fomin 
 <maxim maxim-fomin.ru> wrote:


 No, sorry this cannot be accepted. Formal definitions can be 
 changed due to private POV and as far as spec exists, it is 
 higher priority on any private POV, especially when it is 
 problematic.


 If we don't use the same terms to mean the same things, then 
 there is no point in discussing.

 The spec's definition is somewhat wrong, and needs to be 
 clarified.  This is an important thing when people coming from 
 other languages are trying to anchor what they know to what D 
 provides, we need to use correct terminology.


Please provide reasons why it is wrong (but without explanation 
how druntime allocates memory which is irrelevant).


 Once that is fixed (and you can come to grips with the change), 
 we can discuss.

 -Steve


That's nice to hear, but at that point there would be no point 
for discussions. I see no roots from where contradictory 
definition in article comes from.


By the way, I decided to look into dmd sources to search for 
slice and dynamic by using grep --color=auto -iRnH $1 *.c *.h 
command where $1 stands for 'slice' and 'dynamic'. Slice search 
shows hoards of lines related to slice expression and almost 
nothing to dynamic array, and there are plenty of results which 
shows how dynamic array type (according to spec) are actually 
called dynamic arrays, including class TypeDArray.

http://pastebin.com/S2asda4c
http://pastebin.com/PQWXS7U2

Good luck fixing this.
May 30 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 30 May 2013 12:46:39 -0400, Maxim Fomin <maxim maxim-fomin.ru>  
wrote:


 Please provide reasons why it is wrong (but without explanation how  
 druntime allocates memory which is irrelevant).


It's wrong in that D's spec re-defines dynamic arrays from the traditional  
definition (I think for the sake of simplicity, but I didn't write the  
definition, so I'm not sure).  D's slices aren't dynamic arrays, no matter  
how many specs say so.


 That's nice to hear, but at that point there would be no point for  
 discussions. I see no roots from where contradictory definition in  
 article comes from.


It comes from the experience of observing anyone who knows what a dynamic  
array is, comes to D, sees from the spec that it's T[], and then gets  
confused when T[] does not act like the dynamic array they know from C++,  


In other words, explaining countless times on the newsgroups how slices  
work prompted me to write the article.  It's not an easy concept to grasp.

-Steve
May 30 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 30 May 2013 12:56:46 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 On Thu, 30 May 2013 12:46:39 -0400, Maxim Fomin <maxim maxim-fomin.ru>  
 wrote:


 Please provide reasons why it is wrong (but without explanation how  
 druntime allocates memory which is irrelevant).


 It's wrong in that D's spec re-defines dynamic arrays from the  
 traditional definition (I think for the sake of simplicity, but I didn't  
 write the definition, so I'm not sure).  D's slices aren't dynamic  
 arrays, no matter how many specs say so.


Oh, you were looking for an actual *functional* differences between slices  
and dynamic arrays.

The major concept difference is ownership.  Two references to the same  
array do not mysteriously split when length is extended on one of those  
references.  All references to the same array always refer to the same  
array, even when it has to reallocate to extend length.  Slices differ  
 from this behavior, and I can say with great confidence that this is the  
most confusing aspect of D slices.

In addition, shrinking a dynamic array invalidates any data that has now  
been removed.  D slices do not do this either.  Because slices simply  
point at data, they don't own it.

-Steve
May 30 2013
next sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/30/2013 10:09 AM, Steven Schveighoffer wrote:


 The major concept difference is ownership.  Two references to the same
 array do not mysteriously split when length is extended on one of those
 references.  All references to the same array always refer to the same
 array, even when it has to reallocate to extend length.  Slices differ
 from this behavior, and I can say with great confidence that this is the
 most confusing aspect of D slices.

 In addition, shrinking a dynamic array invalidates any data that has now
 been removed.  D slices do not do this either.  Because slices simply
 point at data, they don't own it.


I tried to name those semantics by "discretionary sharing semantics":

   http://forum.dlang.org/thread/hd2fot$mkc$1 digitalmars.com

I have not read that old post mine again now but I still like the term. :)

Ali
May 30 2013
prev sibling parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 17:09:05 UTC, Steven Schveighoffer 
wrote:

 On Thu, 30 May 2013 12:56:46 -0400, Steven Schveighoffer 
 <schveiguy yahoo.com> wrote:


 On Thu, 30 May 2013 12:46:39 -0400, Maxim Fomin 
 <maxim maxim-fomin.ru> wrote:


 Please provide reasons why it is wrong (but without 
 explanation how druntime allocates memory which is 
 irrelevant).


 It's wrong in that D's spec re-defines dynamic arrays from the 
 traditional definition (I think for the sake of simplicity, 
 but I didn't write the definition, so I'm not sure).  D's 
 slices aren't dynamic arrays, no matter how many specs say so.


 Oh, you were looking for an actual *functional* differences 
 between slices and dynamic arrays.


 -Steve


I was looking for explanation why after years of stable array 
definition one article abolish official spec (without changing 
it) and major implementation without any Walter or Andrei 
approval. I got an answer in previous comment but found it 
unsatisfactory: simply because somebody considers that D 
definitions contradict to some external notions is not a reason 
to change it. There are other places in D which do not correspond 
with names in other languages or with general terms. Also, there 
is as much opinions, as much people, so moving language toward 
some external definition is a problematic task.

It would be good if Walter or Andrei comment on this.
May 30 2013
next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, May 30, 2013 19:44:17 Maxim Fomin wrote:

 I was looking for explanation why after years of stable array
 definition one article abolish official spec (without changing
 it) and major implementation without any Walter or Andrei
 approval. I got an answer in previous comment but found it
 unsatisfactory: simply because somebody considers that D
 definitions contradict to some external notions is not a reason
 to change it. There are other places in D which do not correspond
 with names in other languages or with general terms. Also, there
 is as much opinions, as much people, so moving language toward
 some external definition is a problematic task.
 
 It would be good if Walter or Andrei comment on this.


Then you'll probably need to start a new thread on it. They're unlikely to see 
any of this (let alone comment on it) if they haven't already been involved in 
the thread, and I don't think that either of them have said anything in this 
thread.

- Jonathan M Davis
May 30 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/30/13 1:44 PM, Maxim Fomin wrote:

 On Thursday, 30 May 2013 at 17:09:05 UTC, Steven Schveighoffer wrote:

 On Thu, 30 May 2013 12:56:46 -0400, Steven Schveighoffer
 <schveiguy yahoo.com> wrote:


 On Thu, 30 May 2013 12:46:39 -0400, Maxim Fomin
 <maxim maxim-fomin.ru> wrote:


 Please provide reasons why it is wrong (but without explanation how
 druntime allocates memory which is irrelevant).


 It's wrong in that D's spec re-defines dynamic arrays from the
 traditional definition (I think for the sake of simplicity, but I
 didn't write the definition, so I'm not sure). D's slices aren't
 dynamic arrays, no matter how many specs say so.


 Oh, you were looking for an actual *functional* differences between
 slices and dynamic arrays.


 -Steve


 I was looking for explanation why after years of stable array definition
 one article abolish official spec (without changing it) and major
 implementation without any Walter or Andrei approval. I got an answer in
 previous comment but found it unsatisfactory: simply because somebody
 considers that D definitions contradict to some external notions is not
 a reason to change it. There are other places in D which do not
 correspond with names in other languages or with general terms. Also,
 there is as much opinions, as much people, so moving language toward
 some external definition is a problematic task.

 It would be good if Walter or Andrei comment on this.


Not sure I understand the context.

Andrei
May 30 2013
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, May 30, 2013 16:15:36 Andrei Alexandrescu wrote:

 It would be good if Walter or Andrei comment on this.


 
 Not sure I understand the context.


The D spec uses the terms dynamic array and slice interchangeably. TDPL and 
Phobos do the same. However, Steven has argued that using the term dynamic 
array for a slice is incorrect and goes against how the term is normally 
defined in computer science, because dynamic arrays own their memory, and 
slices don't. So, in his article on arrays which is on dlang.org, he basically 
uses the CS terminology and says that the spec is incorrect in calling T[] a 
dynamic array.

Some people around here (like Steven) are of the opinion that the spec is 
wrong in calling T[] a dynamic array (as it doesn't own its memory like a 
dynamic array would per CS). Others (like Maxim) are arguing in favor of the 
spec or at least that people should be using terms that follow the spec rather 
than trying to claim that T[] is not actually a dynamic array and that the 
dynamic array is the runtime-owned memory and T[] is merely a slice to it (in 
which case, D technically wouldn't even have dynamic arrays except as an 
implementation detail of druntime).

So, Maxim wants clarification from you and/or Walter on what the correct 
meaning for dynamic array is - is T[] both a dynamic array and a slice, or is 
the dynamic array only the chunk of memory owned by druntime, and T[] is only 
a slice? Maxim started the "Dynamic array and slices (need Walter and Andrei 
decision)" thread in order to try and get that clarification.

- Jonathan M Davis
May 30 2013
prev sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, May 30, 2013 12:56:46 Steven Schveighoffer wrote:

 On Thu, 30 May 2013 12:46:39 -0400, Maxim Fomin <maxim maxim-fomin.ru>
 
 wrote:

 Please provide reasons why it is wrong (but without explanation how
 druntime allocates memory which is irrelevant).


 
 It's wrong in that D's spec re-defines dynamic arrays from the traditional
 definition (I think for the sake of simplicity, but I didn't write the
 definition, so I'm not sure). D's slices aren't dynamic arrays, no matter
 how many specs say so.


Well, we've clearly ended up with a few terms that get re-used with different 
meanings and cause confusion. The terms dynamic array and slices are generally 
used interchangeably by the spec and plenty of D users, whereas you're 
basically arguing that D doesn't even have dynamic arrays. Rather, dynamic 
arrays are basically an implementation feature of druntime. However, trying to 
call them all slices instead of dynamic arrays has its own issues, because 
slices are for more than just arrays - they're a core concept of ranges, many 
of which have no relation with arrays. So, I guess that the best term that we 
have would be array slice (not even dynamic array slice, since it could be a 
silce of a static array). But even if we agreed that that was the correct term 
and fixed the spec, it's still ripe for confusion.

It reminds me of the tuple fiasco. Having the bulit-in tuples that TypeTuple 
wraps called tuples causes all kinds of confusion with std.typecons.Tuple (on 
top of the fact that the built-in tuples arguably aren't even tuples).

We seem to have at least a couple of serious terminology/naming problems on 
our hands, and I'm not sure that we have good solutions for any of them. For 
the moment at least, we're stuck trying to give good explanations in order to 
clarify the situation.

And of course, with the spec, TDPL, and the standard library (e.g. 
isDynamicArray) all using the term dynamic array pretty much interchangeably 
with the term slice when discussing arrays, I don't know that there's any 
chance of really clarifying the situation beyond explaining it to people.

- Jonathan M Davis
May 30 2013
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 30 May 2013 13:52:08 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:



 And of course, with the spec, TDPL, and the standard library (e.g.
 isDynamicArray) all using the term dynamic array pretty much  
 interchangeably
 with the term slice when discussing arrays, I don't know that there's any
 chance of really clarifying the situation beyond explaining it to people.


I think clarifying is what we need to do.  We need to inform the user  
reading the spec that although D calls them dynamic arrays, they aren't  
true dynamic arrays in the formal sense.

array slices is a better/more appropriate term IMO.  I agree it would be  
near impossible to change all references to dynamic arrays, especially  
isDynamicArray.

-Steve
May 30 2013
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/30/2013 01:58 AM, Maxim Fomin wrote:


 On Thursday, 30 May 2013 at 07:57:41 UTC, Ali Çehreli wrote:

 On 05/30/2013 12:11 AM, Maxim Fomin wrote:

 As a general programming notion - yes, in D (array spec page):
 "Dynamic arrays consist of a length and a pointer to the


 array data."

 Then the spec is wrong because that is the definition of a slice. The
 reason is, there is no dynamic array is sight below but a static array
 and a slice:

     int[10] arr;
     int[] slice = arr;
     assert(slice.ptr == &arr[0]);  // (yes, same as arr.ptr)


 No, spec is right and article is wrong. It uses incorrect definition and
 calls correct definitions as incorrect.


Your definition of "correct" depends stems from the fact that it is what 
the spec says. If we take the spec as the final word, you are right. 
However, there are historical reasons why terminology sometimes lag 
behind reality and sometimes never change.

Steven's article is trying to correct or avoid misunderstandings of 
novices and experts alike. I have been confused a lot about D's array 
and slice semantics. Only after seeing dynamic arrays separate from 
slices it finally made (more) sense to me.

The code above is a good example of the confusion. If we tell a novice 
that there are two entities in that code, the novice gets confused. The 
reason is, when it comes to actual elements, there is a singe array. 
Calling a single array two is a confusion.

Another example:

void foo(int[] a, int[] b, int[] c)
{
     // ...
}

If we call a novice that the function takes three dynamic arrays, then 
the novice gets confused. (Even the experts get confused because the bug 
that you mention later below about variadic arguments is because the 
spec calls it dynamic array.)

The reality of the code above is that there may be a single array 
depending how the function is called.

The solution for the confusion is to call the entity a "slice" for both 
code fragments above.


 static assert(typeof(slice) == typeof(int[])); // int[] type is dynamic
 array


You call it a "dynamic array" because the spec does so. Staying with 
that definition, you are absolutely correct. As Steven said, we can't 
argue further.

However, 'slice' up there is not an array itself; it is just a view of 
existing elements, wherever they are.


 this checks that object 'slice' is of type dynamic array. Note, that
 notion of slice is not embebed into compiler at all (you cannot test
 whether some object is of type 'slice' or not).


I am happy with the definition that a slice is a length and a pointer to 
the first element that it provides access to. This definition exists in 
the compiler.


 (I know I am repeating the article at this point but it happens to be
 the fact.) If there is no dynamic array to speak of above, what is a
 dynamic array then? The answer is, dynamic array is an entity that is
 owned and managed by the D runtime.


 This is recalling incorrect definitions from article. You are simply
 assuming that dynamic array is runtime memory and everything which does
 not refer to runtime memory is not a dynamic array. This is wrong
 because dynamic array is not defined to be runtime memory and not
 promised to be in 100% cases.


I agree with your quote from another post in the same thread:


 Confusion comes from calling a dynamic array as a slice


Absolutely! :)


 and runtime memory
 as a dynamic array.


(I assume you mean "run-time" there, as in "something happens during the 
execution of the program." Otherwise, "runtime" may also refer to "the D 
runtime", the layer that makes use of the GC to do its magic.)

With that assumption, I never called run-time memory a dynamic array. I 
meant that dynamic arrays are owned and managed by "the D runtime".


 Memory kind allocation and dynamic/static kind of array
 are quite ortogonal issues with high correlation between dynamic 


array and

 heap memory which is not 1.


I agree completely.


 Consider example with typesafe variardic
 functions when dynamic array is constructed on caller side from stack
 memory. It is of type dynamic array yet it is not from runtime memory.


We are using different meanings of "dynamic". Both "static" and 
"dynamic" mean many different things:

dynamic may mean:

* happens at run-time

* sits on the heap

* resizable

* does not have automatic duration

* more?

static may mean:

* initialized at compile time

* sits on the stack

* sits on the code segment

* has automatic duration

* gets destroyed after main exits

* not resizable

* more?

See, that is yet another problem with spec language. The spec must pick 
a word to describe something, which doesn't work in every situation.

That is why I prefer "fixed-length array" over "static array". "static" 
and "dynamic" carry too many meanings.

Getting back to your comment:


 It is of type dynamic array yet it is not from runtime memory.


Agreed that the variadic argument is created at runtime and that it is 
not from "dynamic memory".


 By the way, this is good example of how incorrect definition confuses
 people and make them to write buggy code. I remember at least two bugs
 in bugzilla when people were complaining that 'dynamic array from
 typesafe variardic function seems not to refer to runtime memory'.


Isn't that a good example of my point? Just because the spec calls it a 
"dynamic array" that the programmers make an assumption. If it were 
called a "slice" then it would emphasize the fact that it could be 
referring to elements anywhere.


 For the above code to finally involve a dynamic array, we can add an
 element to 'slice':

     slice ~= 7;
     assert(slice.ptr != &arr[0]);

 Now there is a dynamic array but it is not our 'slice' that is the
 dynamic array. Here is the proof:

     slice = arr[5 .. $];
     assert(slice.ptr == &arr[5]);

 Has 'slice' been a dynamic array until that last assignment and
 suddenly become a slice again? No, D does not involve type changes
 like that. It has always been a slice, which is not the same thing as
 a dynamic array.


 One of the funny consequences of using incorrect definition is that is
 forces to call an entity as not a dynamic array and after some
 manipulations the same entity to call a dynamic array. This is obviously
 wrong because it is the same object.


And that same object is just a view of elements that are not owned by 
themselves. The code above makes sense only by this understanding. For 
only by this definition 'slice' above does *not* change definition. It 
is always a slice and a slice is just a view into some elements.

Ali
May 30 2013
parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 15:50:37 UTC, Ali Çehreli wrote:


 Your definition of "correct" depends stems from the fact that 
 it is what the spec says. If we take the spec as the final 
 word, you are right. However, there are historical reasons why 
 terminology sometimes lag behind reality and sometimes never 
 change.


There is no thing as my definition. It a spec definition. It has 
higher priority over any POV, especially when it comes from 
nowhere, without explaning why it is correct and why it is wrong, 
except long description how D runtime works which is pretty 
irrelevant. I would not comment anything else which is based on 
disagreement between slice and dynamic array. Note, that there is 
no problem with alising of slice and dynamic array, but there is 
problem with denying that dynamic array (according to spec) is a 
slice.


 dynamic may mean:

 * happens at run-time

 * sits on the heap


I provided code when it sits in stack (slice according to the 
article). So, any novice who thinks that dynamic means runtime 
memory can run into bugs (what actually happens). And as was 
mentioned previously, article definition has some kind of 
contribution to dilution between memory types and array types.


 * resizable

 * does not have automatic duration

 * more?

 static may mean:

 * initialized at compile time

 * sits on the stack


I provided code where static array is on the heap. So, making 
definition that static array are stack allocated do not express 
reality of things. However it is unlikely to lead to bugs.
May 30 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/30/2013 09:23 AM, Maxim Fomin wrote:


 Note, that there is no problem with alising of slice and dynamic
 array, but there is problem with denying that dynamic array (according
 to spec) is a slice.


That gets back to your "banana" example. Slice and dynamic array is the 
same thing only because the spec says so. They do not have the same 
semantics of dynamic arrays as I know in programming.

They are not dynamic in the sense that they are on the heap. (Both your 
and my examples have trivially shown that.)

Further, they are not arrays in the sense that they own elements.

Therefore, calling this concept "dynamic array" is a historical 
accident. The spec may call it "dynamic array" but the spec cannot 
change what "dynamic array" means.

Ali
May 30 2013
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 30 May 2013 13:33:31 -0400, Ali =C3=87ehreli <acehreli yahoo.com=

 wrote:



 They are not dynamic in the sense that they are on the heap. (Both you=


r  =


 and my examples have trivially shown that.)


Dynamic arrays themselves do not have to be allocated on the heap.

A C++ std::vector is a valid dynamic array type, yet it's actual contain=
er  =

can exist on the stack.  The data is on the heap, but where the data is =
 =

located is irrelevant.  The important thing here is that any reference t=
o  =

the same instance always affects that instance.  It doesn't mysteriously=
  =

split off into another instance.

-Steve
May 30 2013
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/30/2013 10:38 AM, Steven Schveighoffer wroten

:> On Thu, 30 May 2013 13:33:31 -0400, Ali Çehreli <acehreli yahoo.com> 
wrote:

 They are not dynamic in the sense that they are on the heap. (Both
 your and my examples have trivially shown that.)


 Dynamic arrays themselves do not have to be allocated on the heap.


My wording have been off this morning. I meant what you said.

Ali
May 30 2013
prev sibling parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Thursday, 30 May 2013 at 17:33:32 UTC, Ali Çehreli wrote:

 On 05/30/2013 09:23 AM, Maxim Fomin wrote:


 Note, that there is no problem with alising of slice and


 dynamic

 array, but there is problem with denying that dynamic array


 (according

 to spec) is a slice.


 That gets back to your "banana" example. Slice and dynamic 
 array is the same thing only because the spec says so. They do 
 not have the same semantics of dynamic arrays as I know in 
 programming.
 They are not dynamic in the sense that they are on the heap. 
 (Both your and my examples have trivially shown that.)
 Further, they are not arrays in the sense that they own 
 elements.
 Therefore, calling this concept "dynamic array" is a historical 
 accident. The spec may call it "dynamic array" but the spec 
 cannot change what "dynamic array" means.

 Ali


Really it is repetition of banana example. One article severely 
changes spec because there is opinion that existing spec 
contradicts some ideas. And now it is claimed that some things 
are false just because they are false. It is a hijack of language 
which allows to anyone whose opinion is somewhat different to D 
to claim that his opinion is what D actually is. Without Walter 
or Andrei approval such claims are cheap.
May 30 2013
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/30/2013 10:56 AM, Maxim Fomin wrote:


 Really it is repetition of banana example.


Mmm... Chocolate sauce over a banana slice would be pretty good now. :p

Ali
May 30 2013
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/28/2013 04:32 PM, Peter Williams wrote:


 I find that dup works for const T[] when T is not a class (although I
 haven't tried it with pointers).  This means I write two versions of my
 code - one for classes (which does (cast(T[])).dup) and one for the rest.


There is current and related thread on the D.learn forum:

   http://forum.dlang.org/post/bsbhpdgcpfmkvsclsskq forum.dlang.org

I think it is unnecessarily restrictive that a const class variable 
cannot refer to another class object:

class C
{}

void main()
{
     const(C) c;
     c = new const(C);    // <-- compilation error
}

I think this limitation is at the core of your issue as well: .dup 
creates mutable objects but your array is not able to contain const 
class variables to refer to those mutable objects. I think it should be 
possible.

I have a feeling that this may be related to that surprising issue with 
C and C++:

   http://www.parashift.com/c++-faq-lite/constptrptr-conversion.html

The reason I suspect so is because a class variable is one level of 
indirection and a slice is another level of indirection. Does that make 
this issue the same as the C++ issue? If not, perhaps the implementation 
of such a limitation is the cause of this bug. (?)

Ali
May 28 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 28 May 2013 20:08:44 -0400, Ali =C3=87ehreli <acehreli yahoo.com=

 wrote:



 On 05/28/2013 04:32 PM, Peter Williams wrote:

  > I find that dup works for const T[] when T is not a class (although=


 I

  > haven't tried it with pointers).  This means I write two versions o=


f  =


 my
  > code - one for classes (which does (cast(T[])).dup) and one for the=


  =


 rest.

 There is current and related thread on the D.learn forum:

    http://forum.dlang.org/post/bsbhpdgcpfmkvsclsskq forum.dlang.org

 I think it is unnecessarily restrictive that a const class variable  =



 cannot refer to another class object:

 class C
 {}

 void main()
 {
      const(C) c;
      c =3D new const(C);    // <-- compilation error
 }


This is a separate problem.  What you are looking for could be legal if =
 =

syntax existed for it.

dup-ing just copies the class reference.  It does not copy the bits.

For example:

class C
{
    pure this(int _x) {x =3D _x;}
    int x;
}

immutable(C) c =3D new immutable(C)(5);

const(C)[] arr;
arr ~=3D c;
auto mc =3D (cast(C[])arr).dup; // error without cast!
mc[0].x =3D 6;
assert(c.x =3D=3D 6); // oops!  changed immutable


 I think this limitation is at the core of your issue as well: .dup  =



 creates mutable objects but your array is not able to contain const  =



 class variables to refer to those mutable objects. I think it should b=


e  =


 possible.


This is a different problem.  Your problem is you can't apply const  =

selectively to the tail of the reference.  It's fundamentally sound, but=
 D  =

lacks the syntax to do it.

Peter's problem is that you can't implicitly cast an indirection away fr=
om  =

const, which is a fundamentally unsound operation.


 I have a feeling that this may be related to that surprising issue wit=


h  =


 C and C++:

    http://www.parashift.com/c++-faq-lite/constptrptr-conversion.html

 The reason I suspect so is because a class variable is one level of  =



 indirection and a slice is another level of indirection. Does that mak=


e  =


 this issue the same as the C++ issue? If not, perhaps the implementati=


on  =


 of such a limitation is the cause of this bug. (?)


This is a different problem also, but also is disallowed for good reason=
.

The equivalent in D slices would be this:

int*[] arrofintptrs =3D new int*[1];
const(int)*[] arr2 =3D arrofintptrs; // error....
const int i =3D 5;
arr2[0] =3D &i; // ...because of this
*arrofintptrs[0] =3D 6; // oops, changed i!

-Steve
May 28 2013
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, May 28, 2013 20:37:12 Steven Schveighoffer wrote:

 This is a different problem. Your problem is you can't apply const
 selectively to the tail of the reference. It's fundamentally sound, but D
 lacks the syntax to do it.


The syntax is actually the easy part. The problem is that the type system 
itself doesn't differentiate between a class and a reference to a class, and 
the whole compiler is wired that way. So, while adding a new syntax isn't that 
hard (several have been proposed before), actually implementing it is a royal 
pain (enough so that Walter gave up on it). It would definitely be nice to have 
that fixed though.

- Jonathan M Davis
May 28 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 28 May 2013 22:20:08 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:


 On Tuesday, May 28, 2013 20:37:12 Steven Schveighoffer wrote:

 This is a different problem. Your problem is you can't apply const
 selectively to the tail of the reference. It's fundamentally sound, but  
 D
 lacks the syntax to do it.


 The syntax is actually the easy part. The problem is that the type system
 itself doesn't differentiate between a class and a reference to a class,  
 and
 the whole compiler is wired that way. So, while adding a new syntax  
 isn't that
 hard (several have been proposed before), actually implementing it is a  
 royal
 pain (enough so that Walter gave up on it). It would definitely be nice  
 to have
 that fixed though.


No, this is wrong.  The issue is entirely syntax.  And it is hard, because  
*conceptually*, it's difficult to separate out the reference from the  
data.  It's hard to say "The part of C that isn't the reference" in a  
succinct way.

Michel Fortin has created a pull request to make

const(T)ref

work, and only apply the const to the data.  It's certainly doable.  But  
the syntax, as you can see, is ugly.

As it turns out, we need more than this, and a more critical problem to  
solve is creating tail-const custom ranges (I am working on an article to  
discuss and hopefully address this).

-Steve
May 28 2013
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, May 28, 2013 22:25:01 Steven Schveighoffer wrote:

 On Tue, 28 May 2013 22:20:08 -0400, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:

 On Tuesday, May 28, 2013 20:37:12 Steven Schveighoffer wrote:

 This is a different problem. Your problem is you can't apply const
 selectively to the tail of the reference. It's fundamentally sound, but
 D
 lacks the syntax to do it.


 
 The syntax is actually the easy part. The problem is that the type system
 itself doesn't differentiate between a class and a reference to a class,
 and
 the whole compiler is wired that way. So, while adding a new syntax
 isn't that
 hard (several have been proposed before), actually implementing it is a
 royal
 pain (enough so that Walter gave up on it). It would definitely be nice
 to have
 that fixed though.


 
 No, this is wrong. The issue is entirely syntax. And it is hard, because
 *conceptually*, it's difficult to separate out the reference from the
 data. It's hard to say "The part of C that isn't the reference" in a
 succinct way.


Every time that this comes up and Walter comments on it, he makes a point of 
saying that it's _not_ a syntax issue.

- Jonathan M Davis
May 28 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 28 May 2013 22:57:50 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:


 Every time that this comes up and Walter comments on it, he makes a  
 point of
 saying that it's _not_ a syntax issue.


I remember differently, but maybe you are right.  Haven't the time to look  
back.

But even if he *does* say that, I think it's more that we haven't found  
the *right* syntax.

It's certainly only a syntax issue from a specification perspective, there  
is nothing inherently difficult about the underlying details.

-Steve
May 28 2013
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, May 28, 2013 23:03:10 Steven Schveighoffer wrote:

 On Tue, 28 May 2013 22:57:50 -0400, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:

 Every time that this comes up and Walter comments on it, he makes a
 point of
 saying that it's _not_ a syntax issue.


 
 I remember differently, but maybe you are right. Haven't the time to look
 back.
 
 But even if he *does* say that, I think it's more that we haven't found
 the *right* syntax.

 It's certainly only a syntax issue from a specification perspective, there
 is nothing inherently difficult about the underlying details.


It's primarily an implementation issue. As far as the spec itself goes, it 
shouldn't be a problem. As far as the spec goes, it's pretty much just a 
question of picking a good syntax. But getting that to work with the compiler 
when it doesn't differentiate between the class object and the reference to it 
in the type system isn't necessarily easy. As I recall, that was the core of 
what caused Walter so many problems when he worked on it in the past.

- Jonathan M Davis
May 28 2013
prev sibling parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-05-29 02:25:01 +0000, "Steven Schveighoffer" 
<schveiguy yahoo.com> said:


 On Tue, 28 May 2013 22:20:08 -0400, Jonathan M Davis 
 <jmdavisProg gmx.com>  wrote:
 

 The syntax is actually the easy part. The problem is that the type system
 itself doesn't differentiate between a class and a reference to a class,  and
 the whole compiler is wired that way. So, while adding a new syntax  isn't that
 hard (several have been proposed before), actually implementing it is a  royal
 pain (enough so that Walter gave up on it). It would definitely be nice 
  to have
 that fixed though.


 
 No, this is wrong.  The issue is entirely syntax.  And it is hard, 
 because  *conceptually*, it's difficult to separate out the reference 
 from the  data.  It's hard to say "The part of C that isn't the 
 reference" in a  succinct way.
 
 Michel Fortin has created a pull request to make
 
 const(T)ref
 
 work, and only apply the const to the data.  It's certainly doable.  
 But  the syntax, as you can see, is ugly.


Well, that pull request wasn't trivial to implement correctly and the 
syntax took some time to come with. And also there's no guaranty Walter 
would have accepted the somewhat contorted solution even though it was 
working pretty well (but with no review comment it's hard to say).


 As it turns out, we need more than this, and a more critical problem to 
  solve is creating tail-const custom ranges (I am working on an article 
 to  discuss and hopefully address this).


It's a different problem that'll require a different solution, and if 
it requires special syntax it should be at the struct declaration, not 
at the type declaration. Something like that:

	struct MyRange(inheritedconstness(T)) {
		T[] bla;
		this(const MyRange r) { bla = r.bla; }
	}

	immutable(MyRange!T) t; // real type becomes immutable(MyRange!(immutable(T))
	MyRange!(immutable(T)) u = t; // calls above constructor

Wouldn't this be enough?

-- 
Michel Fortin
michel.fortin michelf.ca
http://michelf.ca/
May 28 2013
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 28 May 2013 23:09:56 -0400, Michel Fortin  
<michel.fortin michelf.ca> wrote:


 On 2013-05-29 02:25:01 +0000, "Steven Schveighoffer"  
 <schveiguy yahoo.com> said:


 On Tue, 28 May 2013 22:20:08 -0400, Jonathan M Davis  
 <jmdavisProg gmx.com>  wrote:


 The syntax is actually the easy part. The problem is that the type  
 system
 itself doesn't differentiate between a class and a reference to a  
 class,  and
 the whole compiler is wired that way. So, while adding a new syntax   
 isn't that
 hard (several have been proposed before), actually implementing it is  
 a  royal
 pain (enough so that Walter gave up on it). It would definitely be  
 nice  to have
 that fixed though.


  No, this is wrong.  The issue is entirely syntax.  And it is hard,  
 because  *conceptually*, it's difficult to separate out the reference  
 from the  data.  It's hard to say "The part of C that isn't the  
 reference" in a  succinct way.
  Michel Fortin has created a pull request to make
  const(T)ref
  work, and only apply the const to the data.  It's certainly doable.   
 But  the syntax, as you can see, is ugly.


 Well, that pull request wasn't trivial to implement correctly and the  
 syntax took some time to come with. And also there's no guaranty Walter  
 would have accepted the somewhat contorted solution even though it was  
 working pretty well (but with no review comment it's hard to say).


I was not trying to say it was trivial, I'm sorry if it came across that  
way.  What I really meant was that if it was difficulty of implementation,  
Walter would have pulled that request seeing as you did all the work!

I don't think it's as much an issue with implementation as it is concept  
and perception.  To say that "C ref" is the same as C is really difficult  
to swallow, then you have ref const(C) ref, which looks horrible IMO.


 As it turns out, we need more than this, and a more critical problem to  
  solve is creating tail-const custom ranges (I am working on an article  
 to  discuss and hopefully address this).


 It's a different problem that'll require a different solution, and if it  
 requires special syntax it should be at the struct declaration, not at  
 the type declaration. Something like that:

 	struct MyRange(inheritedconstness(T)) {
 		T[] bla;
 		this(const MyRange r) { bla = r.bla; }
 	}

 	immutable(MyRange!T) t; // real type becomes  
 immutable(MyRange!(immutable(T))
 	MyRange!(immutable(T)) u = t; // calls above constructor

 Wouldn't this be enough?


I thought some sort of template (or parameterized) solution also.  I'm  
pretty convinced now that this method is unworkable.

I have an article I haven't touched since the plane ride home from dconf  
which discusses these problems, I need to finish it.  I think I have a  
good solution for both this and object references.  I don't want to set  
any expectations, so I'll leave it at that :)

-Steve
May 28 2013
prev sibling next sibling parent Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-05-29 03:09:56 +0000, Michel Fortin <michel.fortin michelf.ca> said:


 It's a different problem that'll require a different solution, and if 
 it requires special syntax it should be at the struct declaration, not 
 at the type declaration. Something like that:
 
 	struct MyRange(inheritedconstness(T)) {
 		T[] bla;
 		this(const MyRange r) { bla = r.bla; }
 	}
 
 	immutable(MyRange!T) t; // real type becomes immutable(MyRange!(immutable(T))
 	MyRange!(immutable(T)) u = t; // calls above constructor
 
 Wouldn't this be enough?


Ah, well no it won't work if you want to copy or reinterpret it as a 
MyRange!(const(T)) or const(MyRange!T).

-- 
Michel Fortin
michel.fortin michelf.ca
http://michelf.ca/
May 28 2013
prev sibling parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Michel Fortin" <michel.fortin michelf.ca> wrote in message 
news:ko3ri4$kkb$1 digitalmars.com...

 Michel Fortin has created a pull request to make

 const(T)ref

 work, and only apply the const to the data.  It's certainly doable.  But 
 the syntax, as you can see, is ugly.


 Well, that pull request wasn't trivial to implement correctly and the 
 syntax took some time to come with. And also there's no guaranty Walter 
 would have accepted the somewhat contorted solution even though it was 
 working pretty well (but with no review comment it's hard to say).


Manu and I had a conversation about this on the last night of dconf, a came 
up with a slight improvement -

Introduce *C (syntax not important) to give you the raw class type, much 
like the raw function type.  You can then apply const directly to this type, 
and an appropriate suffix gets you back to the reference.  (eg 
shared(const(*C) ref) )  No more optional suffix, no more need to collapse 
chains of 'ref' back into a single type.

This should reduce the compiler changes required, as I recall much of the 
complexity was due to changing the meaning of the existing type.

This would also play better with template argument deduction, as there was 
no clear way to define it when ref was optional.  The inconsistent handling 
of arrays and pointers has since been fixed (eg const(T*) matching 
const(U*), U becomes const(T)* and the same for arrays) so there is a clear 
pattern to follow.

In terms of syntax, I'm leaning towards asterix for prefix and postfix, ie
shared(const(*C)*)
May 29 2013
parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-05-29 16:02:58 +0000, "Daniel Murphy" <yebblies nospamgmail.com> said:


 Introduce *C (syntax not important) to give you the raw class type, 
 much like the raw function type.  You can then apply const directly to 
 this type, and an appropriate suffix gets you back to the reference.


Are you sure you're not starting from the wrong assumption? There's no 
such thing as a "raw class type" in the compiler that is separate from 
a "class reference".


 This should reduce the compiler changes required, as I recall much of 
 the complexity was due to changing the meaning of the existing type.


To implement what you want you'd have to separate the current class 
type in two types… which would change pretty much everything related to 
classes in the compiler.

My technique for "const(Object)ref" was to minimize those changes. What 
I ended up adding is a way for a type to have head modifiers different 
from its regular modifiers (but only classes are allowed to have 
different head modifiers). Then I went on a hunt for places checking 
modifiers in the compiler (code such as `c->mod`) and convert them to 
use head modifiers instead (`c->head()->mod`) where it made sense. It 
took some time, but it's not really difficult once you figure it out.


 This would also play better with template argument deduction, as there 
 was no clear way to define it when ref was optional. The inconsistent 
 handling of arrays and pointers has since been fixed (eg const(T*) 
 matching const(U*), U becomes const(T)* and the same for arrays) so 
 there is a clear pattern to follow.


What was problematic for template argument deduction was the lack of a 
coherent example of how it should work -- which as you said has been 
fixed since -- not the optionality of ref.


-- 
Michel Fortin
michel.fortin michelf.ca
http://michelf.ca/
May 29 2013
parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Michel Fortin" <michel.fortin michelf.ca> wrote in message 
news:ko5dl5$b2v$1 digitalmars.com...

 On 2013-05-29 16:02:58 +0000, "Daniel Murphy" <yebblies nospamgmail.com> 
 said:


 Introduce *C (syntax not important) to give you the raw class type, much 
 like the raw function type.  You can then apply const directly to this 
 type, and an appropriate suffix gets you back to the reference.


 Are you sure you're not starting from the wrong assumption? There's no 
 such thing as a "raw class type" in the compiler that is separate from a 
 "class reference".


I know, this would be an addition.


 This should reduce the compiler changes required, as I recall much of the 
 complexity was due to changing the meaning of the existing type.


 To implement what you want you'd have to separate the current class type 
 in two types. which would change pretty much everything related to classes 
 in the compiler.


Yes, my hope is that this is less disruptive than changing 'everything 
related to modifiers' as your patch did.


 My technique for "const(Object)ref" was to minimize those changes. What I 
 ended up adding is a way for a type to have head modifiers different from 
 its regular modifiers (but only classes are allowed to have different head 
 modifiers). Then I went on a hunt for places checking modifiers in the 
 compiler (code such as `c->mod`) and convert them to use head modifiers 
 instead (`c->head()->mod`) where it made sense. It took some time, but 
 it's not really difficult once you figure it out.


I am familiar with your implementation.


 This would also play better with template argument deduction, as there 
 was no clear way to define it when ref was optional. The inconsistent 
 handling of arrays and pointers has since been fixed (eg const(T*) 
 matching const(U*), U becomes const(T)* and the same for arrays) so there 
 is a clear pattern to follow.


 What was problematic for template argument deduction was the lack of a 
 coherent example of how it should work -- which as you said has been fixed 
 since -- not the optionality of ref.


This is not true.

What does const(C) matching (T : const(U), U) give?

If we follow what arrays and pointers do, it removes one level of const, 
giving:
const(C) : const(U)
U == const(C)ref

If you then match with (T : const(U)ref, U)

You get the 'ref' suffix removed, giving const(C), then one level of const 
removed, giving:
const(C)ref

This is the problem I hit with template deduction.  It is possible to define 
the matching differently for classes... but the problem comes from the 'ref' 
suffix being optional.

My observation is that class head types behave similar to function types - 
you can point to them but cannot instantiate them.  My hope is that most of 
the class stuff will stay in TypeClass, with a the new reference type 
leveraging the existing default treatment of TypeNext derived types.

I guess we'll see if I ever get some time to implement this.
Jun 11 2013
parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-06-11 23:24:56 +0000, "Daniel Murphy" <yebblies nospamgmail.com> said:


 What does const(C) matching (T : const(U), U) give?
 
 If we follow what arrays and pointers do, it removes one level of const,
 giving:
 const(C) : const(U)
 U == const(C)ref


Exactly. That works.


 If you then match with (T : const(U)ref, U)
 
 You get the 'ref' suffix removed, giving const(C), then one level of const
 removed, giving:
 const(C)ref
 
 This is the problem I hit with template deduction.  It is possible to define
 the matching differently for classes... but the problem comes from the 'ref'
 suffix being optional.


If you can manage to patch DMD as you suggest, then it'll be 
theoretically more sound and there's chances the resulting code in the 
compiler (at the semantic level at least) will be cleaner than what I 
did, so I'm all for it.

I fail to see how getting a "non-reference" type for the class (through 
U in this template) would be useful though. You can't use that type 
directly, all you can do is add a 'ref' after it.

My fear is that you'll just move some weird behaviour from the semantic 
to the syntactic level. You'll have a true reference type that'll be 
implicitly there but optional at the same time. Well, maybe. That's 
just a feeling I have. By all means, give it a try so we know how it 
fares.

-- 
Michel Fortin
michel.fortin michelf.ca
http://michelf.ca/
Jun 12 2013
parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Michel Fortin" <michel.fortin michelf.ca> wrote in message 
news:kp9s6b$29lq$1 digitalmars.com...

 If you can manage to patch DMD as you suggest, then it'll be theoretically 
 more sound and there's chances the resulting code in the compiler (at the 
 semantic level at least) will be cleaner than what I did, so I'm all for 
 it.

 I fail to see how getting a "non-reference" type for the class (through U 
 in this template) would be useful though. You can't use that type 
 directly, all you can do is add a 'ref' after it.

 My fear is that you'll just move some weird behaviour from the semantic to 
 the syntactic level. You'll have a true reference type that'll be 
 implicitly there but optional at the same time. Well, maybe. That's just a 
 feeling I have. By all means, give it a try so we know how it fares.


Yeah, I can't really say much for sure until I've implemented it.  Let's 
hope it all works as well in practise as it does in theory.
Jun 13 2013
prev sibling parent Kenji Hara <k.hara.pg gmail.com> writes:
Maybe this is too late replying, but I'd like to provide an information.

Current D does not provide generic way for deep copy of class object.
But, you can use std.conv.to with adding a kind of copy constructor.

class C
{
    int x;
    this(int n) { x = n; }

    // Do deep copy, this is used by to!(array-type)(array)
    this(const C c) { this.x = c.x; }
}
void main()
{
    const(C)[] carr = [new C(1), new C(2)];
    // C[] marr = carr.dup;
    // --> Error: cannot implicitly convert element type const(C) to
mutable in carr.dup

    import std.conv;
    C[] marr = carr.to!(C[]);
    // For class arrays which need copy elements,
    // std.conv.to returns [new C(carr[0]), new C(carr[1]), ...]

    // modify element of returned array
    marr[0].x = 5;

    // Right now carr[0] and marr[0] are completely unrelated objects
    assert(carr[0].x == 1);
    assert(marr[0].x == 5);
}

Kenji Hara

2013/5/29 Peter Williams <pwil3058 bigpond.net.au>


 On 28/05/13 23:41, Steven Schveighoffer wrote:


 On Sat, 25 May 2013 23:58:39 -0400, Peter Williams
 <pwil3058 bigpond.net.au> wrote:

  Is the inability to use dup and ~ with const arrays of class objects a

 deliberate design restriction?  I couldn't find mention of it in the
 specification or Andrei's book and only discovered it the hard way.


 It has to be.  There is no cdup.

 For any const(T)[] x, the type of x.dup is T[].


 Yes, that's why I was doing the dup.  I wanted a non const copy of the
 array.


   Because this would mean

 that you would remove const, you cannot do that.


 I find that dup works for const T[] when T is not a class (although I
 haven't tried it with pointers).  This means I write two versions of my
 code - one for classes (which does (cast(T[])).dup) and one for the rest.


   Nor can you idup,

 since implicit conversion to immutable is not possible.

 As far as I know, ~ works with const arrays of class objects.  Can you
 give a case where it fails?


 Looking at my code that caused me to ask this question, I've realised that
 I'm appending a const object onto a no const array.  Once again this works
 for non class objects but not for classes.

 I can see why this might be the case as non class objects are probably
 copied by value where the class objects are pointers and the constness
 applies to the items in an array as well the array itself.

 If this behaviour is a deliberate design decision I'll accept that and
 (probably) modify my code to use (cast(T[])).dup in all cases.  (At the
 moment, I'm using a single mixin template to handle this issue and the
 inability to use ==, !=, < and friends with constant class objects. When
 that problem goes away I'll do the above modifications.)

 This is the type of issue that can come as a surprise when you have a
 working/tested code that suddenly stops compiling when you use it with
 classes.  So a heads up in the documentation would be useful.

 Thanks for your response,
 Peter
May 30 2013