dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

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