View mode: basic / threaded / horizontal-split · Log in · Help
September 18, 2011
Go and generic programming on reddit, also touches on D
Quite interesting.

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

Andrei
September 18, 2011
Re: Go and generic programming on reddit, also touches on D
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.
September 18, 2011
Re: Go and generic programming on reddit, also touches on D
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
September 18, 2011
Re: Go and generic programming on reddit, also touches on D
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
September 18, 2011
Re: Go and generic programming on reddit, also touches on D
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.
September 18, 2011
Re: Go and generic programming on reddit, also touches on D
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.
September 18, 2011
Re: Go and generic programming on reddit, also touches on D
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
September 18, 2011
Re: Go and generic programming on reddit, also touches on D
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.
September 18, 2011
Re: Go and generic programming on reddit, also touches on D
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).
September 18, 2011
Re: Go and generic programming on reddit, also touches on D
"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.
« First   ‹ Prev
1 2 3 4 5
Top | Discussion index | About this forum | D home