I'm almost at the end of my tether here. There are so many problems with the language/compiler, that I'm wondering seriously whether it's going to be possible to have a decent generic template library.

Before I preface this, I should reiterate the "modes" of DTL, to inform on any thoughts anyone might have on this:

1. foreach - client code uses foreach. This all works well for all containers. The problem with this is only that it's an unsophisticated view of looking at a container: you get everything, and have to do all filtering and transformations yourself in client code. This can result in verbose and tedious coding. Good libraries should provide more power.

2. Transformations/filtering - based on "Ranges" (a concept John Torjo and I concocted for C++, but which is eminently suitable for D.). Basically, each container provides a set of methods (eventually via a mixin) that returns a "range". For example, the "select()" method takes either a function/delegate/functor predicate, and returns a freachable range that "contains" only the elements matching the predicate, e.g.

    List!(int)        list = . . .; // Assume it's filled with numbers 0 - 9
    bool IsOdd(int i)
    {
        return 0 != (i & 0x2);
    }
    foreach(int i; list.select(IsOdd))
    {
        printf("%d ", i);
    }

This will print out "1 3 5 7 9"

The power of this is that the returned "range" itself provides the same transformation methods, which means that the transformations are composable, as in:

    List!(int)        list = . . .; // Assume it's filled with numbers 0 - 9
    bool IsOdd(int i)
    {
        return 0 != (i & 0x2);
    }
    int Times2(int i)
    {
        return 2 * i;
    }
    foreach(int i; list.select(IsOdd).collect(Times2))
    {
        printf("%d ", i);
    }

This will print out "2 6 10 14 18"

I'm sure you can see the power in this approach, as well as the potential efficiency savings, where the transformation "criteria" may be tunnelled into the original container's foreach (I've not done that yet).

3. Interface-based containers

Each container in DTL is declared as follows:

    template Vector(T, B = EmptyBase)
    {
        class Vector
            : public BaseSelector!(B).selected_type


This means that by default the container will be do as the STL does, and will just be all compile-time typing, e.g.

    alias    Vector!(int)     int_vector_t;

    int_vector_t    v = new ...;

    v[10] = 3;
    size_t n = v.length;

    int    r = v[0] + v[1];

Such a type is great, as long as we want to manipulate it in/with code that knows its exact type.

Alternatively, we can also support the old-style Java approach, whereby one can specify a base interface, e.g.

    void dump(IObjectContainer c)
    {
        for(IEnumerator e = c.enumerate(); e.hasMoreElements; )
        {
            printf("%.*s ", e.nextElement().toString());
        }
        printf("\n");
    }

    alias    Vector!(int, IObjectContainer)    int_vector_IObjectContainer_t;
    alias    List!(int, IObjectContainer)        int_list_IObjectContainer_t;

    int_vector_IObjectContainer_t   v = new ...;
    int_list_IObjectContainer_t        l = new ...;

    dump(v);
    dump(l);

Now we can pass instances of any container implementing IObjectContainer this to *any* function that knows how to manipulate that interface.

[btw: both of the above forms work now and, fwiw, I hope to release some of the containers supporting this in the next c/o days.]

The downside to the IObjectContainer type approach is that (i) fundamental types must be "boxed" (I've already worked up
std.box), and (ii) it's not generic, since one must downcast object types to their "real" types from Object. Pretty
pukey stuff, except in the minority of circumstances where the IObject-stuff is what you're after (e.g. a message
board).

Further to these two approaches, which I've been working on today, is inheritance via parameterised-interfaces, e.g.

    template dump(T) { void dump(IContainer!(T) c)
    {
        for(IEnumerator e = c.enumerate(); e.hasMoreElements; )
        {
            T    t    =    e.nextElement();

            // ... write generically, presumably via writef() (which I've not used yet <g>)
        }
        printf("\n");
    }

    alias    IContainer!(int)                         int_IContainer_t;
    alias    Vector!(int, int_IContainer_t)    int_vector_IContainer_int_t;
    alias    List!(int, int_IContainer_t)        int_list_IContainer_int_t;

    int_vector_IContainer_int_t      v = new ...;
    int_list_IContainer_int_t            l = new ...;

    dump(v);
    dump(l);

Note: this approach does _not_ require boxing or downcasting.

Alas, this crashes the compiler. Sigh ...

4. Iterator based approach. There are two reasons why STL-iterators are not possible in D: (i) there is no implicit instantiation, and (ii) there is no operator *(). Neither of these preclude the creation of iterators - and I've done a little of that - including adaptors for arrays/pointers, but it means they're not really very usable. The only way to use them "generically" in algorithms would be polymorphically if the iterator classes derived from interfaces, and that would preclude efficiency mechanisms (such as Random Access iterator advancement in STL), without some nasty hacks.

It's my belief that iterators are not for D, and that we thus have the modes 1-3 described above.

And now on to my litany of woes ...

Some tasters:

1. Beyond a significant, but indefinable level of complexity, the linker/compiler loose the ability to find all required symbols, while chopping out any *unrelated* parts makes them locatable again. Boil it down? I wish!!

Nonetheless, that's a bug in the compiler/linker, and doesn't get my blood up, since one can usually find workarounds, and at this stage a little bugginess is not the crime of the century.

2. Templates in D are instantiated en masse. What "en masse" actually means is beyond me, since I am yet to work out the true rules regarding instantation. But what I can say is that having a template such as the following is totally f**cked:

    template TransformedRange(R, F, T) { class TransformedRange
     : public NotionalRange!(T)
    {
      . . .
        this(R r, F f)
        {
            m_r = r.dup;
            m_f = f;
        }
        this(R r)
        {
            m_r = r.dup;
            m_f = new filter_type();
        }

Without worrying too much about the details of what a TransformedRange does, the problem is pretty obvious. If F does not have a default constructor, one cannot instantiate TransformedRange even in the case where the single parameter ctor *is never called*!

I'm yet to work out a workaround to this one - all I do at the moment is not use certain operations with certain container instantiations in the test programs. Woo hoo!

3. There's no implicit instantiation. This has *massive* consequences, including:

- We can't have iterators (as noted above). This is fine for reading from containers, but consider how we might "generically" insert into container ranges in the same (or any analogous) way as is the case with STL.

- In order to support the parameterisable interface (e.g. IContainer!(int)) described above, there needs to be a common way to manipulate built-in types, objects and structs. For some things, one can use traits, for others, overloaded functions. Alas, there seems to be no way to discriminate structs via overloaded functions. Hence, currently the DTL containers do not support polymorphic interfaces when storing structs. Naturally, this has much wider consequences

4. D's import stuff just blows my mind! As a related issue to the boxing utility class described above, I'm running into conflicts between the toString() functions in std.string and my box and boxutil modules. I've tried all kinds of use of private imports, to no avail. I concede that this might be my fault, and I might have just failed to grok D's import rules, but as it currently looks to me, it looks bad and stupid.


So, what do we do about this? Walter's stock response is to boil it down, but it's either impossible to do so with non-trivial projects such as DTL, or I'm simply not smart enough to do it. Sure, one might argue that this is indicative of a too-complex design, but I think that's crap: the concept is simple, and the code is simple; it just doesn't work. (Very similar techniques that I've experimented on in C++ work fine.)

Rather than having things boiled down, I think the compiler should be amended to provide *copious" debugging information, so we can email a dump of that to Walter, and which will be useful to him. I don't know what that information should be, but I know that it's simply not practical for me, or anyone else, to "boil down" these precipitating bugs when they only manifest in highly complex code. I do know that it's totally bogus for us to be made to feel guilty for not having the time or the talent to do this boiling down. I for one am investing a large amount of time to the D cause, with all the consequences wrt to more materially lucrative activities. Since I find that boiling down the code generally takes me at least as long to write the code in the first place, I just don't see that it's justified that I should do the boiling as well. Give me a -dump switch, and I can send it all off to Walter.

Anyway, that's just the compiler, and my main problem is with the language. I'm coming to the conclusion that D either will never be suitable for generic programming, or such suitability is years away. Given that, my aims for DTL are starting to seem naive at best, unattainable at worst.

What's to be done? Well, one might say let's just have vanilla containers, and skip all the transformation stuff. That's fine, but then where're the generics? We can't have algorithms, remember, because we've not got implicit instantiation! The only remaining way to be generic is to follow the Java-route, and go with polymorphic container interfaces, but (i) they can't contain structures, and (ii) we're in Java-la-la land where everything has to be downcast. Yeuch! Even if we can get the compiler to accept parameterisable container interfaces, it's still a runtme indirection, with the concomitant efficiency costs.

So please, someone enlighten me (since I am quite prepared to believe I've missed something simple and obvious here): how can we do generic programming in D?

Matthew

If all this sounds like I'm down on D, and I've spent several weeks - actually it's several months, but who's counting? - working against all these issues and more, then you'd be about spot on. I can't remember being this technically frustrated in the last 10 years, and I'm generally known as a practical pragmatist! :-(

In article <ceaeid$18ir$1@digitaldaemon.com>, Matthew says...
>
>I'm almost at the end of my tether here. There are so many problems with the language/compiler, that I'm wondering seriously whether it's going to be possible to have a decent generic template library.

This is a real bummer. I was rather hoping that D would end up being /better/ than C++. If that's not to be so, it's a little disheartening.

Arcane Jill

Looks like we wont see D 1.0 anytime soon
*runs away crying*

> Alternatively, we can also support the old-style Java approach, whereby one can specify a base interface, e.g.
> 
>     void dump(IObjectContainer c)
>     {
>         for(IEnumerator e = c.enumerate(); e.hasMoreElements; )
>         {
>             printf("%.*s ", e.nextElement().toString());
>         }
>         printf("\n");
>     }
> 
>     alias    Vector!(int, IObjectContainer)
>     int_vector_IObjectContainer_t;
>     alias    List!(int, IObjectContainer)
>     int_list_IObjectContainer_t;
> 
>     int_vector_IObjectContainer_t   v = new ...;
>     int_list_IObjectContainer_t        l = new ...;
> 
>     dump(v);
>     dump(l);

As you say the Enumeration interface is old-style. It's the equivalent to porting Winows 3.1 to unix or something. Why not support "new-style" Java Iterators? I'm guessing that since the new-style is named Iterator it is too close to STL iterators. If that is the reason I'd look for another name - not that I have any off the top of my head. Or maybe just take the methods of Iterator and call it IList or something. In general, though, I don't think we should be saddled with Java's historical baggage.

"Ben Hinkle" <bhinkle4@juno.com> wrote in message news:ceaqp7$1d2b$1@digitaldaemon.com...
>
> > Alternatively, we can also support the old-style Java approach, whereby one can specify a base interface, e.g.
> >
> >     void dump(IObjectContainer c)
> >     {
> >         for(IEnumerator e = c.enumerate(); e.hasMoreElements; )
> >         {
> >             printf("%.*s ", e.nextElement().toString());
> >         }
> >         printf("\n");
> >     }
> >
> >     alias    Vector!(int, IObjectContainer)
> >     int_vector_IObjectContainer_t;
> >     alias    List!(int, IObjectContainer)
> >     int_list_IObjectContainer_t;
> >
> >     int_vector_IObjectContainer_t   v = new ...;
> >     int_list_IObjectContainer_t        l = new ...;
> >
> >     dump(v);
> >     dump(l);
>
> As you say the Enumeration interface is old-style. It's the equivalent to porting Winows 3.1 to unix or something. Why not support "new-style" Java Iterators? I'm guessing that since the new-style is named Iterator it is too close to STL iterators. If that is the reason I'd look for another name - not that I have any off the top of my head. Or maybe just take the methods of Iterator and call it IList or something. In general, though, I don't think we should be saddled with Java's historical baggage.

First: this stuff was worked out and implemented months ago, and in a single day. It costs nothing when you don't use it, and there are limited circumstances (e.g. Message boards) where such functionality is exactly right, so what's the beef?

Second: you don't seem to have read the full post. The very next thing I discussed was the new Java-style parameterised interfaces, which is also already implemented, and seemingly supported by the language; just not by the compiler. Please have another look, and let me know if that was not clear.

Matthew wrote:

> 
> "Ben Hinkle" <bhinkle4@juno.com> wrote in message news:ceaqp7$1d2b$1@digitaldaemon.com...
>>
>> > Alternatively, we can also support the old-style Java approach, whereby one can specify a base interface, e.g.
>> >
>> >     void dump(IObjectContainer c)
>> >     {
>> >         for(IEnumerator e = c.enumerate(); e.hasMoreElements; )
>> >         {
>> >             printf("%.*s ", e.nextElement().toString());
>> >         }
>> >         printf("\n");
>> >     }
>> >
>> >     alias    Vector!(int, IObjectContainer)
>> >     int_vector_IObjectContainer_t;
>> >     alias    List!(int, IObjectContainer)
>> >     int_list_IObjectContainer_t;
>> >
>> >     int_vector_IObjectContainer_t   v = new ...;
>> >     int_list_IObjectContainer_t        l = new ...;
>> >
>> >     dump(v);
>> >     dump(l);
>>
>> As you say the Enumeration interface is old-style. It's the equivalent to porting Winows 3.1 to unix or something. Why not support "new-style" Java Iterators? I'm guessing that since the new-style is named Iterator it is too close to STL iterators. If that is the reason I'd look for another name - not that I have any off the top of my head. Or maybe just take the methods of Iterator and call it IList or something. In general, though, I don't think we should be saddled with Java's historical baggage.
> 
> First: this stuff was worked out and implemented months ago, and in a single day. It costs nothing when you don't use it, and there are limited circumstances (e.g. Message boards) where such functionality is exactly right, so what's the beef?

My beef is just with the choice of iterface to support. Sun's Javadoc for Enumeration says "NOTE: The functionality of this interface is duplicated by the Iterator interface. In addition, Iterator adds an optional remove operation, and has shorter method names. New implementations should consider using Iterator in preference to Enumeration."

> Second: you don't seem to have read the full post. The very next thing I discussed was the new Java-style parameterised interfaces, which is also already implemented, and seemingly supported by the language; just not by the compiler. Please have another look, and let me know if that was not clear.

umm - ok. I'll read it more carefully. I only saw Enumeration examples and no Iterator examples so I didn't realize you had also gotten Iterator ported. Maybe it's best for me to wait and see what is in there instead of guessing.

In article <ceaeid$18ir$1@digitaldaemon.com>, Matthew says...
>So, what do we do about this? Walter's stock response is to boil it down, but it's either impossible to do so with non-trivial projects such as DTL, or I'm simply not smart enough to do it. Sure, one might argue that this is indicative of a too-complex design, but I think that's crap: the concept is simple, and the code is simple; it just doesn't work. (Very similar techniques that I've experimented on in C++ work fine.)

If you're unable (or unwilling) to boil it down for Walter, maybe someone else is. (I've worked on shortening problem code from Mango a while back.) If you post some code that produces a compiler error, I'll look at making it Walter-sized.

jcc7

I've read over your rant.  I'll not pretend to understand all of it, and I don't have any suggestions for your specific problems, except to that the Java route is not the way to go. I'm a Java guy, and I hate the Java collections API.

Whenever I work on an open-source project, I put my code in a publicly accessable repository (a subversion repository, specifically) and I generally commit my code to it after each new change (even small changes, like a since bug fix) and generally before I stop for the day.  This way, I can get input from others, not that there are many (hell, let's face it: any) followers of my projects.  (Plus, the code gets backed up, but that's OT.) It's kind of a "release early, release often" approach (btw, if you haven't read ESR's "The Cathedral and the Bazaar", it's a good read.) I think your decision to release what you've got in a day or two is a good one. It's always good to have more people reading the code. The more perspectives one can get input from, the more successful a project will be, in my opinion.  I would even encourage you to put the project on dsource, and commit to the repository often.  I know I'd definately be more help giving advice (or even patches) if I could see the entire source.

On a very positive note, from what I understood of your post, it appears to me that should the language/compiler problems get worked out, DTL will be a very powerful, robust tool.  I am most impressed.

As always, I salute you for your effort, and intellect. John

I hope to see Walter reply on this one.  I will be throughly disappointed should he not.

On Thu, 29 Jul 2004 19:04:11 +1000, Matthew wrote:

> I'm almost at the end of my tether here. There are so many problems with the language/compiler, that I'm wondering
> seriously whether it's going to be possible to have a decent generic template library.
> ...
> If all this sounds like I'm down on D, and I've spent several weeks -
> actually it's several months, but who's counting? - working against all
> these issues and more, then you'd be about spot on. I can't remember
> being this technically frustrated in the last 10 years, and I'm
> generally known as a practical pragmatist! :-(

> - In order to support the parameterisable interface (e.g.
IContainer!(int)) described above, there needs to be a common
> way to manipulate built-in types, objects and structs. For some things,
one can use traits, for others, overloaded
> functions. Alas, there seems to be no way to discriminate structs via
overloaded functions. Hence, currently the DTL
> containers do not support polymorphic interfaces when storing structs.
Naturally, this has much wider consequences

Could TypeInfo's help here? Structs don't currently have TypeInfo so it won't solve the struct issue but Walter has said he knows TypeInfos for structs needs improvement so eventually it should get fixed. I've been using TypeInfo for compare, swap, equals and getHash and found them very useful.

In article <ceaeid$18ir$1@digitaldaemon.com>, Matthew says...
>
>4. Iterator based approach. There are two reasons why STL-iterators are not possible in D: (i) there is no implicit
>instantiation, and (ii) there is no operator *().

In my more evil moments I've considered requesting an overloaded dot operator for much the same reason operator-> can be overloaded in C++.  I find it unfortunate that smart pointers can't really be implemented in D either, even though GC makes them far less necessary.

>2. Templates in D are instantiated en masse. What "en masse" actually means is beyond me, since I am yet to work out the true rules regarding instantation. But what I can say is that having a template such as the following is totally f**cked:
>
>    template TransformedRange(R, F, T) { class TransformedRange
>     : public NotionalRange!(T)
>    {
>      . . .
>        this(R r, F f)
>        {
>            m_r = r.dup;
>            m_f = f;
>        }
>        this(R r)
>        {
>            m_r = r.dup;
>            m_f = new filter_type();
>        }
>
>Without worrying too much about the details of what a TransformedRange does, the problem is pretty obvious. If F does not have a default constructor, one cannot instantiate TransformedRange even in the case where the single parameter ctor *is never called*!

Your example is confusing.  I don't see "new F()" anywhere.  Why the need for a
default constructor?

But this raises an interesting point.  One useful but little mentioned feature of C++ is that primitive types support default constructor semantics just like user defined classes do.  For generic programming it might be nice to have the same thing:

MyClass c = new MyClass();
int i = new int(); // equivalent to "int i;"

This makes the difference between pointers and nonpointers a tad confusing but it would make life much easier in some cases.

>3. There's no implicit instantiation. This has *massive* consequences, including:
..
>
>- In order to support the parameterisable interface (e.g. IContainer!(int)) described above, there needs to be a common way to manipulate built-in types, objects and structs. For some things, one can use traits, for others, overloaded functions. Alas, there seems to be no way to discriminate structs via overloaded functions. Hence, currently the DTL containers do not support polymorphic interfaces when storing structs.

See my comment above.  This is pretty important.  We should be able to use the same semantics for all types in D and be able to distinguish between them. TypeInfo is a good start, though someone mentioned that structs and pointers have the same base TypeInfo class?

>4. D's import stuff just blows my mind! As a related issue to the boxing utility class described above, I'm running into conflicts between the toString() functions in std.string and my box and boxutil modules.

I ran into this problem when trying to import std.ctype and std.c.string into the same module.  I ended up just adding extern declarations for the C functions I wanted, but it's an outstanding issue.  IMO an import should import everything it can and leave conflicting symbols out.  Then they could still be referenced via std.string.strcmp or whatever.  Perhaps this is a good instance where a compiler warning would be useful?

I've tried all kinds of use of
>private imports, to no avail. I concede that this might be my fault, and I might have just failed to grok D's import rules, but as it currently looks to me, it looks bad and stupid.

I haven't found any way around this either, but I think this may be more a bug with the import functionality than any language deficiency.  It's something I haven't taken the time to experiment with sufficiently.

>Rather than having things boiled down, I think the compiler should be amended to provide *copious" debugging information, so we can email a dump of that to Walter, and which will be useful to him. I don't know what that information should be, but I know that it's simply not practical for me, or anyone else, to "boil down" these precipitating bugs when they only manifest in highly complex code.

That's a handy idea, provided doing so doesn't take up weeks of Walter's time to add.

>Anyway, that's just the compiler, and my main problem is with the language. I'm coming to the conclusion that D either will never be suitable for generic programming, or such suitability is years away. Given that, my aims for DTL are starting to seem naive at best, unattainable at worst.

I think some language issues may just need to be refined.  Implicit instantiation is a big one for me, though I know that it is not a simple feature to add.  Ideally, I would like to do everything GP-wise in D that I can in C++. Perhaps a set of examples of what works and what doesn't followed by a discussion of language features D may be lacking?  In some respects I've found D more capable (alias template parameters) and in others, less.

> We can't have algorithms, remember, because we've not got implicit instantiation!

Well, we can in some cases because we've got typeof, it just means more typing. But I'm sure there are cases where types are determined in odd ways in C++ that a wrapper template in D couldn't work around.

>So please, someone enlighten me (since I am quite prepared to believe I've missed something simple and obvious here): how can we do generic programming in D?

Let's try and work it out.  I'll admit I've been focusing on other things until now.  Another day and I'll be finished with unFormat and I'll be able to play with a new project.  Perhaps trying to implement <algorithm> and <functional> would be a good place to start.  At the very least it would help to determine just what D can and can't do so far as templates are concerned.

The iterator thing is a tough one though, because so much depends on that.  Is there truly no way to generate them?  I had played with creating a list type and thought I'd got the basics of one working, though I didn't experiment much with primitves vs. structs vs. classes.


Sean