Quite interesting.

http://www.reddit.com/r/programming/comments/kikut/think_in_go_gos_alternative_to_the/

Andrei

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.

Andrei Alexandrescu:

In that thread you have said: http://www.reddit.com/r/programming/comments/kikut/think_in_go_gos_alternative_to_the/c2krft0

> I'm interested in furthering D's grok of dependent types.

This blog post shows some basic nice examples of dependent types in ATS language: http://www.bluishcoder.co.nz/2010/09/01/dependent-types-in-ats.html

Some other notes: http://leonardo-m.livejournal.com/98077.html

But those are toys. For practical programming this alternative version is close to what you can do in D, and keep both efficiency and sanity:
http://rosettacode.org/wiki/Matrix_multiplication#Alternative_version

Bye,
bearophile

On 18/09/11 5:08 PM, 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.

Yes. As I understand, Andrei prefers things in libraries and Walter prefers things built in to the compiler (obviously an oversimplification, but I believe that's the general way they 'lean').

There's advantages to both. Being implementable in a library means that they can easily be swapped out or modified to work with other code, but being built-in ("magic", as Andrei puts it) means that the compiler has greater awareness of them and can do better optimizations, give better errors etc.

Of course, there are ways of extending the language to provide better errors and allow better optimizations (e.g. 'pure' in D), but as a purely practical matter, it's easier if they are just built-in.


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

I don't think you'd get much bloat in D by implementing dynamic arrays with templates. Remember, the built-in arrays *are* mostly implemented in D: https://github.com/D-Programming-Language/druntime/tree/master/src/rt

On 09/18/2011 07:16 PM, Peter Alexander wrote:
> On 18/09/11 5:08 PM, 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.
>
> Yes. As I understand, Andrei prefers things in libraries and Walter
> prefers things built in to the compiler (obviously an
> oversimplification, but I believe that's the general way they 'lean').
>
> There's advantages to both. Being implementable in a library means that
> they can easily be swapped out or modified to work with other code, but
> being built-in ("magic", as Andrei puts it) means that the compiler has
> greater awareness of them and can do better optimizations, give better
> errors etc.
>
> Of course, there are ways of extending the language to provide better
> errors and allow better optimizations (e.g. 'pure' in D), but as a
> purely practical matter, it's easier if they are just built-in.
>

Well, I think arrays should be built-in. What I was implying was that D, not entirely unlike Go, also has some magic. You can get almost the same with templates, so it is way better in that aspect than Go, but it is still there.

>
>> 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.
>
> I don't think you'd get much bloat in D by implementing dynamic arrays
> with templates.  Remember, the built-in arrays *are* mostly implemented
> in D: https://github.com/D-Programming-Language/druntime/tree/master/src/rt

Those work like generics, not like templates. Making them templates would duplicate all the runtime functions that process arrays for every element type it is instantiated with. And I am sure that would add some bloat. D has no generics, just templates. But built-in arrays work like generics.

On 18/09/11 6:55 PM, Timon Gehr wrote:
> On 09/18/2011 07:16 PM, Peter Alexander wrote:
>> On 18/09/11 5:08 PM, 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.
>>
>> Yes. As I understand, Andrei prefers things in libraries and Walter
>> prefers things built in to the compiler (obviously an
>> oversimplification, but I believe that's the general way they 'lean').
>>
>> There's advantages to both. Being implementable in a library means that
>> they can easily be swapped out or modified to work with other code, but
>> being built-in ("magic", as Andrei puts it) means that the compiler has
>> greater awareness of them and can do better optimizations, give better
>> errors etc.
>>
>> Of course, there are ways of extending the language to provide better
>> errors and allow better optimizations (e.g. 'pure' in D), but as a
>> purely practical matter, it's easier if they are just built-in.
>>
>
> Well, I think arrays should be built-in. What I was implying was that D,
> not entirely unlike Go, also has some magic. You can get almost the same
> with templates, so it is way better in that aspect than Go, but it is
> still there.

Yes, you are right. D does have some "magic". Every language has to draw a line between library code and built-in code. The only way a language can be purely library is if the "language" is just the source code for the compiler :-)


>>> 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.
>>
>> I don't think you'd get much bloat in D by implementing dynamic arrays
>> with templates. Remember, the built-in arrays *are* mostly implemented
>> in D:
>> https://github.com/D-Programming-Language/druntime/tree/master/src/rt
>
> Those work like generics, not like templates. Making them templates
> would duplicate all the runtime functions that process arrays for every
> element type it is instantiated with. And I am sure that would add some
> bloat. D has no generics, just templates. But built-in arrays work like
> generics.

Yeah, they use runtime polymorphism like generics instead of compile time polymorphism.

I don't believe there's any way round this -- you can't solve it with a better language design. If you want to handle different types with a single interface then either you need to generate code for each type (templates) or use runtime polymorphism (generics). Of course, you can improve both to minimize the overhead, but there's a fundamental memory v.s. performance compromise.

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. Yes, D's slices are built-in but the language offers facilities for defining any other parameterized types that are just as powerful. 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 '$'.

Walter and I have long discussed that T[] should use an actual type object.Slice!T as back-end. That would allow us to e.g. switch from the pointer+length representation to the arguably better pointer+pointer representation with ease. 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.


Andrei

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.

On 09/18/2011 08:17 PM, Peter Alexander wrote:
> On 18/09/11 6:55 PM, Timon Gehr wrote:
>> On 09/18/2011 07:16 PM, Peter Alexander wrote:
>>> On 18/09/11 5:08 PM, 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.
>>>
>>> Yes. As I understand, Andrei prefers things in libraries and Walter
>>> prefers things built in to the compiler (obviously an
>>> oversimplification, but I believe that's the general way they 'lean').
>>>
>>> There's advantages to both. Being implementable in a library means that
>>> they can easily be swapped out or modified to work with other code, but
>>> being built-in ("magic", as Andrei puts it) means that the compiler has
>>> greater awareness of them and can do better optimizations, give better
>>> errors etc.
>>>
>>> Of course, there are ways of extending the language to provide better
>>> errors and allow better optimizations (e.g. 'pure' in D), but as a
>>> purely practical matter, it's easier if they are just built-in.
>>>
>>
>> Well, I think arrays should be built-in. What I was implying was that D,
>> not entirely unlike Go, also has some magic. You can get almost the same
>> with templates, so it is way better in that aspect than Go, but it is
>> still there.
>
> Yes, you are right. D does have some "magic". Every language has to draw
> a line between library code and built-in code. The only way a language
> can be purely library is if the "language" is just the source code for
> the compiler :-)
>

It is not at all about syntax sugar, or whether or not the functionality comes in a library or as a built-in. I am merely feature-oriented here, and D does not have generics, but arrays work like generics. I am not even saying that is a bad thing. :)

>
>>>> 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.
>>>
>>> I don't think you'd get much bloat in D by implementing dynamic arrays
>>> with templates. Remember, the built-in arrays *are* mostly implemented
>>> in D:
>>> https://github.com/D-Programming-Language/druntime/tree/master/src/rt
>>
>> Those work like generics, not like templates. Making them templates
>> would duplicate all the runtime functions that process arrays for every
>> element type it is instantiated with. And I am sure that would add some
>> bloat. D has no generics, just templates. But built-in arrays work like
>> generics.
>
> Yeah, they use runtime polymorphism like generics instead of compile
> time polymorphism.
>
> I don't believe there's any way round this -- you can't solve it with a
> better language design. If you want to handle different types with a
> single interface then either you need to generate code for each type
> (templates) or use runtime polymorphism (generics). Of course, you can
> improve both to minimize the overhead, but there's a fundamental memory
> v.s. performance compromise.

Consider eg this:

T foo(T: Object)(T x){
    return x;
}

Generics clearly win on that one, because it does not require code duplication or runtime polymorphism (as often is true in pure OO design programs for instance!). The same is the case for arrays. They don't need runtime polymorphism (except for stray language bugs such as array.sort).

"Timon Gehr" <timon.gehr@gmx.ch> wrote in message news:j55h4f$1ia5$1@digitalmars.com...
>
>> The only advantages slices have left
>> are (a) type syntax, i.e. T[] instead of Slice!T, (b) literal syntax,
>> i.e. [ 1, 2, 3 ] instead of slice(1, 2, 3), and (c) a couple of stray
>> language bugs such as '$'.
>
> I am thankful for $, as it is a great feature, and it really should be made accessible to user defined types. Either through opDollar or the rewrite a[foo($)] => a[foo(a.length)]. What makes it qualify as a stray language bug to you?
>

He's saying that one of the few advantages slices have left over user-defined types is that, for slices, $ actually works. The bug is that it doesn't work for user-defined types.

FWIW, I like the rewrite idea far better than opDollar.