On 05/21/2010 11:55 AM, Ellery Newcomer wrote:
> On 05/21/2010 09:14 AM, Steven Schveighoffer wrote:
>> Second, since reference types are the right thing to do, classes are
>> much easier to deal with. I know AA's are reference types that are
>> structs, but the code needed to perform this feat is not trivial. The
>> AA has only one member, a reference to the data struct, which is
>> allocated on the heap. Any member function/property that is used on
>> the AA must first check whether the implementation is allocated yet.
>> The only benefit this gives you IMO is not having to use 'new' on it.
>> And even that has some drawbacks. For example, pass an empty AA by
>> value to a function, and if that function adds any data to it, it is
>> lost. But pass an AA by value with one element in it, and the new data
>> sticks. A class gives you much more in terms of options -- interfaces,
>> builtin synchronization, runtime comparison, etc. And it forces full
>> reference semantics by default. I think regardless of whether
>> interfaces are defined for dcollections, classes give a better set of
>> options than structs.
>
>
> Wow. A partially-nullable type.
>
> Great. Now I have to review everywhere I ever used an AA. Thanks, D.
>
> is there any serious drawback to something like
>
> (int[int]).init = InitializedAA!(int,int)
>
> ?

Or should one just always give an AA param either a const or ref modifier?

On 05/19/2010 07:57 PM, Bill Baxter wrote:
> On Wed, May 19, 2010 at 4:01 PM, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org>  wrote:
>
>> My vision, in very brief, is to foster a federation of independent
>> containers abiding to identical names for similar functionality. Then a few
>> concept checks (a la std.range checks) can easily express what capabilities
>> a given client function needs from a container.
>>
>> Destroy me :o).
>
> So instead of STL's concept hierarchy, you have essentially concept
> tags.  Very Web 2.0. :-)
>
> I agree that there doesn't seem to be any coding benefit to STL's
> concepts being hierarchical.  If you need a push_back(), you've got to
> check for push_back(). The main benefit seems to be for  documentation
> purposes, allowing you to say things like "bidirectional_iterator has
> this and that, plus everything in forward_iterator".  But that could
> easily be rephrased as "it has backward_iteration plus
> forward_iteration" with two pages describing those two tags.
>
> So I like the sound of it.  But it seems actually a pretty small
> departure from the STL approach, in practice.

Well in fact STL has a concept hierarchy for iterators (which D also has for ranges), and a flat, unstructured approach to container.

I don't mind keeping what STL does if there's no good reason. One change I do think is beneficial is making containers reference types by default.


Andrei

On 05/19/2010 08:42 PM, Steven Schveighoffer wrote:
> Andrei Alexandrescu Wrote:
>
>
>> To get back to one of my earlier points, the fact that the
>> container interfaces are unable to express iteration is a corollary
>> of the design's problem and an climactic disharmony.
>>
>> My vision, in very brief, is to foster a federation of independent
>> containers abiding to identical names for similar functionality.
>> Then a few concept checks (a la std.range checks) can easily
>> express what capabilities a given client function needs from a
>> container.
>
> This might have a simple answer.  Dcollections implementations are
> not a hierarchy, just the interfaces are.

Without final, they are the roots of a hierarchy. But I understand you are making containers final, which is great.

> I.e. there aren't many
> kinds of HashMaps that derive from each other.  But the interfaces
> are not detrimental to your ideas.  The only thing interfaces require
> is that the entities implementing them are classes and not structs.
> As long as you agree that classes are the right call, then interfaces
> can co-exist with your other suggestions without interference.

This brings back a discussion I had with Walter a while ago, with echoes in the newsgroup. Basically the conclusion was as follows: if a container never escapes the addresses of its elements, it can manage its own storage. That forces, however, the container to be a struct because copying references to a class container would break that encapsulation. I called those "perfectly encapsulated containers" and I think they are good candidates for manual memory management because they tend to deal in relatively large chunks.

I noticed that your collections return things by value, so they are good candidates for perfect encapsulation.

> Yes, if you want to define "this function needs something that is
> both addable and purgeable, I don't have an interface for that.  But
> a concept can certainly define that generically (which is what you
> want anyways), or you could just say "I need a List" and get those
> functions also.  It also does not force entities other than
> dcollections objects to be classes, they could be structs and
> implement the correct concepts.
>
> I myself don't really use the interface aspect of the classes, it is
> mostly a carryover from the Java/Tango inspirations.

I don't know Tango, but Java's containers are a terrible example to follow. Java's container library is a ill-advised design on top of an underpowered language, patched later with some half-understood seeming of genericity. I think Java containers are a huge disservice to the programming community because they foster bad design.

> But I can see
> one good reason to keep them -- binary interoperability.  For
> example, it might be the case some day when D has good support with
> dynamic libraries that a library exposes some piece of itself as a
> Map or List interface.

I need to disagree with that. I've done and I do a ton of binary interoperability stuff. You never expose a generic container interface! Interoperable objects always embody high-level logic that is specific to the application. They might use containers inside, but they invariably expose high-level, application-specific functionality.

> So my answer is -- go ahead and define these concepts and required
> names, and you can ignore the interfaces if they don't interest you.
> They do not subtract from the possibilities, and others may find good
> use for them.
>
> Does that make sense?

I understand I could ignore the interfaces and call it a day, but it seems that at this point we are both convinced they are not quite good at anything: you only put them in because you suffered the Stockholm syndrome with Java, and I hate them with a passion.

Why would we keep in the standard library bad design with the advice that "if you don't like it ignore it"?


Andrei

On 05/19/2010 08:53 PM, Steven Schveighoffer wrote:
> bearophile Wrote:
>
>> Andrei Alexandrescu:
>>> Destroy me :o).
>>
>> You ideas are surely interesting, but I don't think there's a
>> simple way to change his code according to your ideas.
>
> I don't think the ideas are mutually exclusive.  I don't see why
> having an interface prevents someone from using a concept on the
> concrete class.
>
>> People can use the dcollections in the following weeks and months,
>> and when you have implemented your ideas the people that like them
>> can switch to using your collections.
>
> If it's at all possible, I'd like to cooperate on making dcollections
> phobos-qualified.  So I'm glad to try and find a way to satisfy
> Andrei's concerns.

I'm very grateful to hear that; as I said, dcollections embody a great deal of solid work for which I have all admiration. If we disagree, I hope we won't make this a willpower struggle :o). Let the best ideas win. That being said, how something is said matters even if the said is true; I'll be extra careful with that.

Andrei

On 05/19/2010 09:48 PM, Michel Fortin wrote:
> On 2010-05-19 19:01:51 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> said:
>
>> I wrote a solution to the problem in native D. It goes like this:
>>
>> alias Container!(int, addable | purgeable) Messerschmidt;
>>
>> void messWith(Messerschmidt i) {
>> ... use i's capabilities to add and purge ...
>> }
>
> Are you sure this is necessary? I'm wondering how the above is different
> from:
>
> void messWith(C)(C i) if (IsAddable!C && IsPurgeable!C) {
> ... use i's capabilities to add and purge
> }

It's different in that messWith is a type-parameterized function (aka a template in C++) with the known tradeoffs: multiple instantiations, risk of code bloating, but good speed most of the time. Add to that that some people aren't comfortable with those.

> where IsAddable just checks for an 'add' function and IsPurgeable checks
> for a 'purge' function. Obviously, one is a template and the other
> isn't. I'd expect the template function to be more performant since it
> doesn't require an indirection to call into the container. Is the need
> for runtime-swappable containers really common enough to justify adding
> it to the standard library? Won't adding this encourage people to use it
> without realizing the downside in performance and failed optimization
> opportunities because of the hidden dynamic dispatch? It's a quite nice
> idea, but I don't like the tradeoff.

These arguments are in line with mine. I tried above to convey that the situation is not all-win.

> This criticism is valid for containers implementing interfaces too. In
> my first Java programs, I was always declaring variables as the List
> interface, then instantiating an ArrayList for them, thinking it'd make
> things more generic and easier to change later. Generic sometime is
> good, but if you do that with containers in D you're in for an important
> performance drop. Personally, I'd scrap anything that's not made of
> static calls (final functions in a class are fine) so people can't
> easily make these kind of mistakes (and then believe D is slow).

By the way, I dislike the name ArrayList. Is it just me, or "list" is most often associated with "linked list" in computer lingo? So when I see "ArrayList" it looks like an oxymoron. Steve, could I impose on you to rename ArrayList simply Array?

> Also, addable and purgeable above being or'ed constants makes the system
> difficult to scale to new concepts. The template predicates on the other
> hand are infinitely extendable: if my containers have 'commit' and
> 'rollback' functions, I can define IsTransactional to check for the
> presence of the functions and make some algorithms that benefits from
> this. In fact, this can apply to anything, not just containers. Range
> are already using this pattern. Wouldn't it make things easier to learn
> if we could just reuse the same principle with containers?

Nice arguments!


Andrei

On 05/19/2010 09:59 PM, Robert Jacques wrote:
> On Wed, 19 May 2010 21:42:35 -0400, Steven Schveighoffer
> <schveiguy@yahoo.com> wrote:
>> Andrei Alexandrescu Wrote:
>>
>>
>>> To get back to one of my earlier points, the fact that the container
>>> interfaces are unable to express iteration is a corollary of the
>>> design's problem and an climactic disharmony.
>>>
>>> My vision, in very brief, is to foster a federation of independent
>>> containers abiding to identical names for similar functionality. Then a
>>> few concept checks (a la std.range checks) can easily express what
>>> capabilities a given client function needs from a container.
>>
>> This might have a simple answer. Dcollections implementations are not
>> a hierarchy, just the interfaces are. I.e. there aren't many kinds of
>> HashMaps that derive from each other. But the interfaces are not
>> detrimental to your ideas. The only thing interfaces require is that
>> the entities implementing them are classes and not structs. As long as
>> you agree that classes are the right call, then interfaces can
>> co-exist with your other suggestions without interference.
>>
>> Yes, if you want to define "this function needs something that is both
>> addable and purgeable, I don't have an interface for that. But a
>> concept can certainly define that generically (which is what you want
>> anyways), or you could just say "I need a List" and get those
>> functions also. It also does not force entities other than
>> dcollections objects to be classes, they could be structs and
>> implement the correct concepts.
>>
>> I myself don't really use the interface aspect of the classes, it is
>> mostly a carryover from the Java/Tango inspirations. But I can see one
>> good reason to keep them -- binary interoperability. For example, it
>> might be the case some day when D has good support with dynamic
>> libraries that a library exposes some piece of itself as a Map or List
>> interface.
>>
>> So my answer is -- go ahead and define these concepts and required
>> names, and you can ignore the interfaces if they don't interest you.
>> They do not subtract from the possibilities, and others may find good
>> use for them.
>>
>> Does that make sense?
>>
>> -Steve
>
> Yes and No. I understand where your coming from, but I think it's a bad
> idea. First, I think it needlessly expands the radius of comprehension
> needed to understand and use the library. (See Tangled up in tools
> http://www.pragprog.com/magazines/2010-04/tangled-up-in-tools)

For the record, I strongly agree with this.

> Second, I
> think designing a library to be flexible enough to meet some future,
> anticipated need (e.g. dlls) is a good idea, but actually implementing
> vaporous future needs is fraught with peril; it's too easy to guess
> wrong. Third, interface base design is viral; If library X uses
> interfaces then I have to use interfaces to interface with it. And if
> another library Y uses classes, then I'm going have to write a
> (needless) wrapper around one of them.

That's a good argument as well. I like to put it a different way: you can get the advantages of an interface by wrapping a struct, but you can't get the advantages of a struct by wrapping an interface.


Andrei

On 05/20/2010 05:34 AM, Steven Schveighoffer wrote:
> Robert Jacques Wrote:
>
>> On Wed, 19 May 2010 21:42:35 -0400, Steven Schveighoffer
>>>
>>> Does that make sense?
>>>
>>> -Steve
>>
>> Yes and No. I understand where your coming from, but I think it's a
>> bad idea. First, I think it needlessly expands the radius of
>> comprehension needed to understand and use the library. (See
>> Tangled up in tools
>> http://www.pragprog.com/magazines/2010-04/tangled-up-in-tools)
>> Second, I think designing a library to be flexible enough to meet
>> some future, anticipated need (e.g. dlls) is a good idea, but
>> actually implementing vaporous future needs is fraught with peril;
>> it's too easy to guess wrong. Third, interface base design is
>> viral; If library X uses interfaces then I have to use interfaces
>> to interface with it. And if another library Y uses classes, then
>> I'm going have to write a (needless) wrapper around one of them.
>
> I understand these points, but I'm already using interfaces to copy
> data between containers.  I don't have to, I could have used generic
> code, but this way, only one function is instantiated to copy data
> from all the other containers.  The problem with using generic code
> is that the compiler will needlessly duplicate functions that are
> identical.

There is a copy() function that copies any range to any other range. It
might need a revisit, but I think the way to go about copying is generic.

Let's not forget that the code for copying itself is rather short and
that applications don't tend to use a large number of container types.

> Using interfaces is not as viral as you think.  My interfaces can be
> used in generic code, as long as the generic code uses functions in
> the interfaces.  If a library returns an interface, the author is
> saying "I don't want you using any functions outside this interface,"
> so why is that a bad thing?
>
> Forcing people to *not* use interfaces has its drawbacks too.
> Dcollections gives the most flexible design I could muster, while
> still being useful.
>
> I'm not saying I'm against removing the interfaces until some later
> date, but I don't see any convincing arguments yet, especially since
> I've already seen benefits from having them.

What are the benefits that you have noticed? I think you'd need to back up the copying argument with some data if you want to frame it as a benefit.


Andrei

On 05/20/2010 06:17 AM, Michel Fortin wrote:
> On 2010-05-20 06:34:42 -0400, Steven Schveighoffer <schveiguy@yahoo.com>
> said:
>
>> I understand these points, but I'm already using interfaces to copy
>> data between containers. I don't have to, I could have used generic
>> code, but this way, only one function is instantiated to copy data
>> from all the other containers. The problem with using generic code is
>> that the compiler will needlessly duplicate functions that are identical.
>
> One question. Have you calculated the speed difference between using an
> interface and using generic code? Surely going through all those virtual
> calls slows things down a lot.
>
> I do like interfaces in principle, but I fear it'll make things much
> slower when people implement things in term of interfaces. That's why
> I'm not sure it's a good idea to offer container interfaces in the
> standard library.

There will be differences, but let's keep in mind that that's one of several arguments against container interfaces.

Andrei

On 05/20/2010 08:22 AM, Steven Schveighoffer wrote:
> Michel Fortin Wrote:
>
>> On 2010-05-20 06:34:42 -0400, Steven
>> Schveighoffer<schveiguy@yahoo.com>  said:
>>
>>> I understand these points, but I'm already using interfaces to
>>> copy data between containers.  I don't have to, I could have used
>>> generic code, but this way, only one function is instantiated to
>>> copy data from all the other containers.  The problem with using
>>> generic code is that the compiler will needlessly duplicate
>>> functions that are identical.
>>
>> One question. Have you calculated the speed difference between
>> using an interface and using generic code? Surely going through all
>> those virtual calls slows things down a lot.
>>
>> I do like interfaces in principle, but I fear it'll make things
>> much slower when people implement things in term of interfaces.
>> That's why I'm not sure it's a good idea to offer container
>> interfaces in the standard library.
>
> It's not that much slower.  You get a much higher speedup when things
> can be inlined than virtual vs. non-virtual.
>
> However, I should probably make all the functions in the concrete
> implementations final.  I made several of them final, but I should do
> it across the board.

Yup. Even Java does that. I forgot whether it was a recanting of a former stance (as was the case with synchronized) or things were like that from the get-go.

> One thing I just thought of -- in dcollections, similar types can be
> compared to one another.  For example, you can check to see if a
> HashSet is equal to a TreeSet.  But that would not be possible
> without interfaces.

Of course it would be possible. You write a generic function that takes two generic container and constrain the inputs such that at least one has element lookup capability. (Complexity-oriented design for the win!)


Andrei

On 05/20/2010 09:14 AM, Pelle wrote:
> On 05/20/2010 03:22 PM, Steven Schveighoffer wrote:
>> One thing I just thought of -- in dcollections, similar types can be
>> compared to one another. For example, you can check to see if a
>> HashSet is equal to a TreeSet. But that would not be possible without
>> interfaces.
>>
>> -Steve
>
> I'm sorry, but I think that's a misfeature. In my opinion, a tree is not
> equal to a hash table, ever.

Yes. By the way, TDPL's dogma imposes that a == b for classes means they have the same dynamic type.


Andrei