Go and generic programming on reddit, also touches on D

[Timon Gehr]

On 09/18/2011 08:28 PM, Andrei Alexandrescu wrote:
> On 9/18/11 11:08 AM, Timon Gehr wrote:
>> On 09/18/2011 03:48 AM, Andrei Alexandrescu wrote:
>>> Quite interesting.
>>>
>>> http://www.reddit.com/r/programming/comments/kikut/think_in_go_gos_alternative_to_the/
>>>
>>>
>>>
>>>
>>
>> 2 hours ago, Andrei Alexandrescu wrote:
>> > The problem is, Vector was just an example of a multitude of
>> containers. The huge problem with slices is dogfood-related - they are >
>> "magic" because the language features proposed to programmers were not
>> enough for expressing a simple abstraction. Reserving "special" features
>> for the language is a terrible way to go about programming language
>> design.
>>
>> Don't D arrays do a similar thing? They are not templates, yet work with
>> generic element types.
>>
>> Afaics, improving the language to the point were dynamic array-like
>> structures could be implemented in the library without resulting in a
>> bloated executable would be quite involved.
>
> That's an incorrect view of my statement.

I don't think so. The "special" feature we are talking about are 
generics. I am certainly not saying that your statement implies in any 
way that arrays should be a library feature.

> Yes, D's slices are built-in
> but the language offers facilities for defining any other parameterized
> types that are just as powerful.

Even way more powerful. But with great power comes great responsibility, 
eg some binary file bloat, along with the undecidability of the 
well-formedness of a particular template.

I am perfectly fine with arrays being built in. I am also fine with some 
"magic", because, as you say templates are good enough to replace the 
magic. But still I _do_ think that there is a tiny bit of magic.

> The only advantages slices have left
> are (a) type syntax, i.e. T[] instead of Slice!T, (b) literal syntax,
> i.e. [ 1, 2, 3 ] instead of slice(1, 2, 3), and (c) a couple of stray
> language bugs such as '$'.

I am thankful for $, as it is a great feature, and it really should be 
made accessible to user defined types. Either through opDollar or the 
rewrite a[foo($)] => a[foo(a.length)]. What makes it qualify as a stray 
language bug to you?

>
> Walter and I have long discussed that T[] should use an actual type
> object.Slice!T as back-end.

That would make the magic go away indeed, but then you'll get the bloat.

> That would allow us to e.g. switch from the
> pointer+length representation to the arguably better pointer+pointer
> representation with ease.

In what way is that representation better?

Pointer+Length:
b=a[i] <=> b:=*(a.ptr+i); (if lhs typechecks)
b=a[i..j] <=> b.ptr:=a.ptr+i, b.length=j-i;
b=a.length <=> b:=a.length
bounds check a[i]: cmp i,$; jae label;


Pointer+Pointer
b=a[i] <=> b:=*(a.begin+i) (if lhs typechecks)
b=a[i..j] <=> b.begin:=a.begin+i; b.end=a.begin+j
b=a.length <=> b:=a.end-a.begin
bounds check a[i]: cmp i,begin; jb label; cmp i,end; jae label;
(not the only way to do it, you could also increase register pressure by 
first computing the length and then doing the other thing, but if the 
array ptr and length is in fact in registers, that loses)


Therefore, in my eyes Pointer+Pointer loses badly, because getting the 
length/bounds checking requires additional machine instructions.

> The main difficulty with object.Slice is CTFE
> - the compiler can manipulate a T[] during compilation because it
> understands its invariant.  The same invariant would be difficult to
> infer from a user defined type.
>

Basically, all that would have to be done would be to make (at least 
parts) of core.memory.GC CTFE-able. Or to treat the template as special 
all along, because basic efficiency concerns dictate that some amount of 
built-in-ness is great for such a basic data structure. Imho they are 
not built in enough into DMD right now.


As a side note, as soon as you use std.array.appender, the CTFE-ability 
goes away anyways. And most of the array-manipulating code in Phobos 
does just that. Are there any plans to make std.array.appender 
CTFE-able? I guess now that we have if(__ctfe){} that would be trivial, 
and the benefit would be extremely large, because many Phobos functions 
would become CTFE-able at once.