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.

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.

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.

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

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

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.

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).

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.

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

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.