On 05/19/2010 11:09 AM, Steven Schveighoffer wrote:
> After much work and toil, I have created dcollections for D2.

Awesome! I'm looking through it, unfortunately after wandering in the trunk for a while (I was like, wait, what?). But that was after all good because I saw a lot of awesome improvements in the new library. This is solid work.

I salute your decision to frame complexity as a feature and remove functions with "undecided complexity". This is huge.

That being said, I think dcollections2 has not yet solved a number of problems, some minor, some annoying, and some fundamental. This makes things quite unpleasant because, willingly or not, I'm in a three-way conflict of interest: (1) I can influence to some extent the decision of adopting dcollections2 for phobos; (2) I have my own design in mind which is competing with dcollections2; (3) my time is scarce so I'm having difficulty executing on that design, whereas dcollections2 is already usable.

I'm not sure where this leaves us. I'm tempted to post a list of "grievances" with the current design, but it's difficult to make that sound sincere due to the conflict of interest. Let me start by asking this: on a scale of 0 ("no change") to 10 ("redesign the whole thing"), where do you stand regarding the perspective of operating changes to dcollections2?


Andrei

Andrej Mitrovic Wrote:


> Well as long as you're here can I submit an error here? :)
> 
> I get an error while building the D2 branch:
> 
> Error: ArrayMultiset.obj : No such file or directory

Crud, I admit that I assumed anything that built on Linux would build on Windows.  I still believe it will, but of course, I need to change the batch file :)

> 
> It seems the ArrayMultiset.d is not in the dcollections folder for the D2.x  branch, although it is in trunk (I guess the trunk is the D1.x one?).

Yes, D1 is trunk, D2 is going to eventually be trunk

> 
> Is that module deprecated for d2.x? (although it's listed in the win32 batch file)

Yes, just remove it.  I'll fix it when I get a chance.

-Steve

Andrei Alexandrescu Wrote:

> On 05/19/2010 11:09 AM, Steven Schveighoffer wrote:
> > After much work and toil, I have created dcollections for D2.
> 
> Awesome! I'm looking through it, unfortunately after wandering in the trunk for a while (I was like, wait, what?). But that was after all good because I saw a lot of awesome improvements in the new library. This is solid work.

Yeah, I will move the D1 version to a branch and copy the D2 to trunk when I get a chance, Part of the reason is the automatic doc generator will puke if the trunk is D2.

> That being said, I think dcollections2 has not yet solved a number of problems, some minor, some annoying, and some fundamental. This makes things quite unpleasant because, willingly or not, I'm in a three-way conflict of interest: (1) I can influence to some extent the decision of adopting dcollections2 for phobos; (2) I have my own design in mind which is competing with dcollections2; (3) my time is scarce so I'm having difficulty executing on that design, whereas dcollections2 is already usable.
> 
> I'm not sure where this leaves us. I'm tempted to post a list of "grievances" with the current design, but it's difficult to make that sound sincere due to the conflict of interest. Let me start by asking this: on a scale of 0 ("no change") to 10 ("redesign the whole thing"), where do you stand regarding the perspective of operating changes to dcollections2?

It depends on what you want to change.  If you say cursors have to go, then I would say no.  If you think some functions/classes need to be renamed, or the module structure needs to be changed, I'd say fine.

There are other design decisions that can be changed, but I look at it from the perspective of usefulness to me :)  If it stops being useful to me, or does not provide a feature I want, then I'll not use it, and then I won't want to maintain it.

I guess start with the big ones, 'cause minor ones aren't likely to be a problem.

-Steve

On 05/19/2010 04:37 PM, Steven Schveighoffer wrote:
> Andrei Alexandrescu Wrote:
>> I'm not sure where this leaves us. I'm tempted to post a list of
>> "grievances" with the current design, but it's difficult to make
>> Let me start by
>> asking this: on a scale of 0 ("no change") to 10 ("redesign the
>> whole thing"), where do you stand regarding the perspective of
>> operating changes to dcollections2?
>
> It depends on what you want to change.  If you say cursors have to
> go, then I would say no.  If you think some functions/classes need to
> be renamed, or the module structure needs to be changed, I'd say
> fine.
>
> There are other design decisions that can be changed, but I look at
> it from the perspective of usefulness to me :)  If it stops being
> useful to me, or does not provide a feature I want, then I'll not use
> it, and then I won't want to maintain it.
>
> I guess start with the big ones, 'cause minor ones aren't likely to
> be a problem.

Well the thing is I'm strongly questioning the whole point of defining a hierarchy for containers, in particular when the interfaces are numerous. I'd go as heretical as saying "Container hierarchy are for languages that suck." Also, the fact that (for efficiency reasons) ranges are concrete and inaccessible from the abstract interfaces aggravates the matter even more, to the point where containers are neither horses nor mules: if you use the interfaces you have only severely emasculated access to the container's elements, and if you use the concrete classes why the heck bother with hierarchies in the first place.

Whew. Let me explain; there's a lot to explain.

Right now there are 10 interfaces in 7 files in the /model/ subdir. It happens quite often that a given class inherits more than one interface, for example ArrayList inherits two, and many set types inherit Set which in turn inherits Addable!V, Iterator!V, Purgeable!V.

The problem with this setup that encodes capabilities in interfaces is that many sensible combinations of capabilities are impossible to obtain. Say you want to define a function messWith(C) where C is Purgeable and Addable. There's no type for that! Set has too many capabilities (which not all containers might support), so you'll need to do a runtime check:

void messWith(Addable!int ia) {
    auto ip = cast(Purgeable!int) ia;
    enforce(ip, "Wrong type etc.");
    ...
}

It would be more expressive if such capability constraints could be expressed during compilation.

To see more about this problem, you may want to check "Compound types for Java" by Buechi and Wech (just google it). The paper explains the problem in detail and proposes a Java language change to fix it. Java didn't change and was not able to devise a library solution.

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

The inspiration for this approach was given by Scott Meyers' article "Red code, green code". The approach does work and rather beautifully, but it's impractical: the class hierarchy forms a dense DAG and if you add 4-5 capabilities an empty object already has size 8KB consisting only of routing vtables.

Escalating this discussion one step further (and probably a bit outside the area of commonly-accepted lore), let me hypothesize that maybe the entire idea of container hierarchies is a red herring, the hoax of the 1990s. Hierarchies are for types that have a lot of commonality and a little variability. Containers are not that. They have personality, refuse to accept straitjacket interfaces, and each has unique capabilities - as your capability-based design witnesses.

I agree that reuse via binary interfaces is good when you write functions that exploit them, but in D it's simple and cheap enough to write a concept-checked generic function to get around that. In my designs I either know what container I'm dealing with, or I am in generic-land. I never was like, "mmm, great, I can change this container type at runtime".

But wait, there's less. Furthermore, container hierarchies encourage design by inheritance, which is more often than not poor. If you want to define a container that notifies an observer whenever you add stuff to it, composition is the best to follow. You don't want a horse with a violing grafted on its back; keep the horse a horse and play the violin and it'll dance.

I've never, ever been in a place in life when I thought, "I should derive from this container class and hook a method of it." Composition always wins.

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.

Destroy me :o).


Andrei

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

Bye,
bearophile

While I haven't read dcollections yet, I definitely agree with you about not liking container hierarchies, and about the importance of support for ranges.

I hope Steven can be convinced that this is a good way to go :-).

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.

--bb

Oooohhh goody goody goody!   n_n


I'm in the process of making a little toy project ATM. I'll shall integrate dcollections 2.0a into ASAP.

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

Graham St Jack Wrote:

> While I haven't read dcollections yet, I definitely agree with you about not liking container hierarchies, and about the importance of support for ranges.
> 
> I hope Steven can be convinced that this is a good way to go :-).

All dcollections classes support ranges.  I am already convinced of that :)

-Steve