May 11, 2008
On 11/05/2008, Yigal Chripun <yigal100@gmail.com> wrote:
> I want to be able to do this:
>  List!(T) col = new LinkedList!(T);
>
>  and be able to change the linked list to a vector in the future (or any
>  other suitable collection) with the changes limited to this line alone.
>  is it possible with templates?

Umm. Yes.

    auto col = new LinkedList!(T);
    sort(col);

becomes

    auto col = new Vector!(T);
    sort(col);


> huh?
> the point of interfaces is to define relations so that I can be sure
> that I can sort all sortable collections for instance. the fact that
> it's in the interface dictates that all derived classes have to provide
> some way to do that. I don't care as a user how that is implemented, I
> just know I can sort my sortable collection since it's in the interface.

But ... what if it isn't? What if I import some.other.Collection which doesn't support your interface? All of a sudden, my ability to sort vanishes.

You can argue that that is entirely the fault of some.other.Collection, for not implementing the interface, but come on! If I want to create a collection, frankly, I just want to implement the ability to put things in and get things out and store things efficiently. I don't want to have to muck about re-inventing the wheel by implementing stable sort, over and and over again for each new collection.



>  another benefit is that each derived class can provide a specialized and
>  optimized version for its own internal structure. Iterators add overhead
>  here

No they don't. All they do is expose the ability to access the collection, which you need to have anyway.


> for no reason. oh there is one reason, generality... right?

There are several reasons. Buglessness would be a good one, in my eyes. I know that if I do

    sort(whatever)

using std.algorithm, then there will be no bugs, even if "whatever" is a third-party collection. (That's assuming of course that std.algorithm.sort has been thoroughly debugged, but with a standard library one would certainly expect that). Whereas, if some third-party-collection has reinvented the wheel and implemented their own sort ... again ... well, that's just one more place for bugs to creep in.

And of course, it's not just sort(). std.algorithm also provides
functions like reduce(), filter(), find(), count(), and a gazillion
more, all highly customizable. You want all of those in your container
interface, so that container implementors have to implement all of
them every time?

Frankly, it would be irresponsibility of a standard library /not/ to provide reusable implementations.



>  fortunately, D does provide all the necessary language
>  support, so we are not limited by iterators any more.

Your use of language is prejudicial here. Note that I can substitute anything I don't like into that sentence. For example: "Fortunately, D does provide all the necessary language support, so we are not limited by foreach any more", or "Fortunately, D does provide all the necessary language support, so we are not limited by polymorphism any more", or...

We are not limited, period. We have choices. Why not just say that?
May 11, 2008
On 11/05/2008, Yigal Chripun <yigal100@gmail.com> wrote:
> Actually, we got it slightly wrong:
>  since D defines removal of invariance as undefined behavior and since casting with constancy does not convert the value but rather changes the type tag of the value, it would be more appropriate to use the "cast!" form, IMO.

Hmmm. Perhaps. But then you lose the distinction between const_cast and reinterpret_cast. With cast!() acting as reinterpret_cast, I can do:

    void foo(Something x)
    {
        auto y = cast!(Anything)x;
        ...
    }

and it would always succeed, and you can't say "unless there's a change of constancy" in this case, because the before and after might have completely different memory layouts, so there'd be no way even to tell whether or not that had happened.

I can see that const_cast and dynamic_cast could share the same syntax, but I really don't see how reinterpret_cast could double up with /anything/ else.

So maybe that brings us to this:

    cast(T)x // dynamic_cast
    cast!(T)x // reinterpret_cast
    static cast(T)x // static_cast
    const cast(T)x // const_cast

That does have a certain appeal to it.
May 11, 2008
Janice Caron wrote:
> On 11/05/2008, Yigal Chripun <yigal100@gmail.com> wrote:
>> I want to be able to do this:
>>  List!(T) col = new LinkedList!(T);
>>
>>  and be able to change the linked list to a vector in the future (or any
>>  other suitable collection) with the changes limited to this line alone.
>>  is it possible with templates?
> 
> Umm. Yes.
> 
>     auto col = new LinkedList!(T);
>     sort(col);
> 
> becomes
> 
>     auto col = new Vector!(T);
>     sort(col);
> 
right...
and what about my function?
void WalkListAndDoSomething(List!(T) list);
 would become what?
void WalkListAndDoSomething(auto list);
I wonder if the compiler will accept that..
There is no such thing as List!(T) in the STL design. either you use a
vector or you use a linked list. there's nothing in between.

>> huh?
>> the point of interfaces is to define relations so that I can be sure
>> that I can sort all sortable collections for instance. the fact that
>> it's in the interface dictates that all derived classes have to provide
>> some way to do that. I don't care as a user how that is implemented, I
>> just know I can sort my sortable collection since it's in the interface.
> 
> But ... what if it isn't? What if I import some.other.Collection which doesn't support your interface? All of a sudden, my ability to sort vanishes.
> 
> You can argue that that is entirely the fault of some.other.Collection, for not implementing the interface, but come on! If I want to create a collection, frankly, I just want to implement the ability to put things in and get things out and store things efficiently. I don't want to have to muck about re-inventing the wheel by implementing stable sort, over and and over again for each new collection.

But you are re-inventing the wheel! the entire point is to have a collection framework in the standard library. No one needs to write a list in Java or C#. Those frameworks are built to be extend-able if you in that much of a need of a different specialized collection. but than again, if you are writing a new specialized version instead of using the standard version that comes with the standard library than you would want to implement your highly optimized sort function as well.
> 
> 
> 
>>  another benefit is that each derived class can provide a specialized and
>>  optimized version for its own internal structure. Iterators add overhead
>>  here
> 
> No they don't. All they do is expose the ability to access the collection, which you need to have anyway.
the overhead here is a separate object, and function calls for the iterator object. for most simple traversals, that's an unnecessary overhead when I could just use the collection.each method with a delegate like I can do in Ruby/Smalltalk/other high level languages than don't force me to manually advance an iterator to the next object in the collection. (yes, D does that for me with foreach, yet it is another level of indirectness) Iterators are useful when I really want to control myself the order of traversal or stuff like that. if I just want to sum the values of all the objects in the collection, than an iterator is an overhead. guess what kind of action is more common.
> 
> 
>> for no reason. oh there is one reason, generality... right?
> 
> There are several reasons. Buglessness would be a good one, in my eyes. I know that if I do
> 
>     sort(whatever)
> 
> using std.algorithm, then there will be no bugs, even if "whatever" is a third-party collection. (That's assuming of course that std.algorithm.sort has been thoroughly debugged, but with a standard library one would certainly expect that). Whereas, if some third-party-collection has reinvented the wheel and implemented their own sort ... again ... well, that's just one more place for bugs to creep in.
> 
> And of course, it's not just sort(). std.algorithm also provides
> functions like reduce(), filter(), find(), count(), and a gazillion
> more, all highly customizable. You want all of those in your container
> interface, so that container implementors have to implement all of
> them every time?
> 
> Frankly, it would be irresponsibility of a standard library /not/ to provide reusable implementations.

nothing has to be either/or. D provides many mechanisms such as mixins
for example that could be used. and the standard library can provide
general functions too. if I use the container in the standard library, I
can use the built-in collection.sort(); and if i use a third-party
collection, i could also use thirdPartyCollection.sort(); [that will use
the template solution and the proposed D2 extension for open classes,
I've mentioned a few times]
or if you prefer, sort(thirdPartyCollection);
besides, all those templates could double-up as code the collection
writers can mix-in into their collection classes to implement the
interfaces. this way, a third party vendor can decide to be compatible
to the D standard library and implement all those interfaces with the
provided mixins, and in case his collection isn't compatible the user
could use the same templates himself.
that's a win-win situation.


> 
> 
> 
>>  fortunately, D does provide all the necessary language
>>  support, so we are not limited by iterators any more.
> 
> Your use of language is prejudicial here. Note that I can substitute anything I don't like into that sentence. For example: "Fortunately, D does provide all the necessary language support, so we are not limited by foreach any more", or "Fortunately, D does provide all the necessary language support, so we are not limited by polymorphism any more", or...
> 
> We are not limited, period. We have choices. Why not just say that?
I just did, didn't I? the point was comaring to C++ where those choices aren't available or if they are they are much harder to accomplish.
May 11, 2008
Janice Caron wrote:
> On 11/05/2008, Yigal Chripun <yigal100@gmail.com> wrote:
>> Actually, we got it slightly wrong:
>>  since D defines removal of invariance as undefined behavior and since casting with constancy does not convert the value but rather changes the type tag of the value, it would be more appropriate to use the "cast!" form, IMO.
> 
> Hmmm. Perhaps. But then you lose the distinction between const_cast and reinterpret_cast. With cast!() acting as reinterpret_cast, I can do:
> 
>     void foo(Something x)
>     {
>         auto y = cast!(Anything)x;
>         ...
>     }
> 
> and it would always succeed, and you can't say "unless there's a change of constancy" in this case, because the before and after might have completely different memory layouts, so there'd be no way even to tell whether or not that had happened.
> 
> I can see that const_cast and dynamic_cast could share the same syntax, but I really don't see how reinterpret_cast could double up with /anything/ else.
> 
> So maybe that brings us to this:
> 
>     cast(T)x // dynamic_cast
>     cast!(T)x // reinterpret_cast
>     static cast(T)x // static_cast
>     const cast(T)x // const_cast
> 
> That does have a certain appeal to it.
I'm not sure your syntax can be used since those two words already have
a different meaning, wouldn't it create ambiguity in the language?
--Yigal
since i don't classify the casts as you do, I'm not sure I agree with
the above. didn't you yourself complain that cast(T) can remove
constancy by mistake and create bugs?
why would you allow cast!(T) to do just that?
anyway, I need to think more about that. I haven't arrived at a
conclusion yet, so I'd appreciate more examples/explanations.

Also, My definition was that cast() can change the memory while cast!()
doesn't. it seems you define them in reverse of that.


--Yigal
May 11, 2008
On 11/05/2008, Yigal Chripun <yigal100@gmail.com> wrote:
> > Umm. Yes.
>  >
>  >     auto col = new LinkedList!(T);
>  >     sort(col);
>  >
>  > becomes
>  >
>  >     auto col = new Vector!(T);
>  >     sort(col);
>  >
>
> right...
>  and what about my function?
>  void WalkListAndDoSomething(List!(T) list);
>   would become what?

    List!(T) list;
    map!(doSomething)(list);

or

    List!(T) list;
    reduce!(doSomething)(x,list);

or

    List!(T) list;
    inPlace!(doSomething)(list);

depending on which was more appropriate for doSomething.



>  void WalkListAndDoSomething(auto list);
>  I wonder if the compiler will accept that..

I'm baffled as to why you even said that. You know it won't. It's silly.


>  There is no such thing as List!(T) in the STL design. either you use a
>  vector or you use a linked list. there's nothing in between.

I thought we were talking D here? I took your use of "List!(T)" there to mean any arbitrary collection.


> But you are re-inventing the wheel!

No I'm not.


> the entire point is

Again, you're telling me there's this "the" point, which is different from "a" point, and somehow more important than any point I might make.


> to have a
> collection framework in the standard library.

Again, you're criticising today's D, and failing to acknowledge that tomorrow's D may (and almost certainly will) have a collection framework in the standard library.



> the overhead [of iterators] is a separate object, and function calls for the iterator object.

By "object" you presumably mean struct - often times small enough to pass around in a register. There is essentially no difference between a struct containing a pointer, and a pointer.

By "function" you presumably mean static function, which takes zero space in the struct, and will almost certainly be inlined when compiled.

Overhead gone.



> for most simple traversals, that's an unnecessary
> overhead when I could just use the collection.each method with a
> delegate

Now that /does/ have a function call overhead.


>  if I just want
>  to sum the values of all the objects in the collection, than an iterator
>  is an overhead.

Or you could just do

    int sum = reduce!("a+b")(0,collection);

:-)


>  besides, all those templates could double-up as code the collection
>  writers can mix-in into their collection classes to implement the
>  interfaces.

Then aren't we lucky they exist! :-)


>  that's a win-win situation.

Yes.
May 11, 2008
On Sun, 11 May 2008 19:47:14 +0400, Yigal Chripun <yigal100@gmail.com> wrote:

> Janice Caron wrote:
>> On 11/05/2008, Yigal Chripun <yigal100@gmail.com> wrote:
>>> I want to be able to do this:
>>>  List!(T) col = new LinkedList!(T);
>>>
>>>  and be able to change the linked list to a vector in the future (or any
>>>  other suitable collection) with the changes limited to this line alone.
>>>  is it possible with templates?
>>

Well, yes, is possible. Even with STL.

A typical trick I often do is this:

typedef std::vector<Item*> Items;
Items items;

items.pushBack(new Item());
Item* item = items.front();
Items::iterator it = std::find(items.begin(), items.end(), someItem);
if (it != items.end()) {
	items.erase(it);
}
std::sort(items.begin(), items.end());
// etc

And now if I decide to exchange vector with list or deque or anything else,
all I need to do is to change a single line:

typedef std::list<Item*> Items;

I don't say that it is the best way to stick with, but it usually works.

> ight...
> and what about my function?
> void WalkListAndDoSomething(List!(T) list);

Use templates. Or use polymorhism, if you expect containers to implement some generic interface.
May 11, 2008
On 11/05/2008, Yigal Chripun <yigal100@gmail.com> wrote:
>  > So maybe that brings us to this:
>  >
>  >     cast(T)x // dynamic_cast
>  >     cast!(T)x // reinterpret_cast
>  >     static cast(T)x // static_cast
>  >     const cast(T)x // const_cast
>  >
>  > That does have a certain appeal to it.
>
>  didn't you yourself complain that cast(T) can remove
>  constancy by mistake and create bugs?

Yes, which is why I now suggest

    void foo(in C c)
    {
        C c = cast(C)c; /* ERROR - cast cannot remove constancy */
        C d = const cast(C)c /* OK */
    }


>  why would you allow cast!(T) to do just that?

As in...

    void foo(in C c)
    {
        C c = cast!(C)c; /* OK */
    }

Because the exclamation mark means "allow anything" (but you're only ever reinterpreting bits, not assigning new ones).

Reinterpret cast would most often be used for casting void* to T*, for some T, but it could just as easily be used to interpret T* as U*, or (for classes) C as D. Since the source type may have a completely different memory layout from the destination type, there is, in general, no way for the compiler to determine whether or not constancy has changed. (e.g. you could be casting from a pointer to an intptr_t, or vice versa). In short, this is the most dangerous form of cast of all, and should only ever be used when nothing else will work, and even then only if you're damn sure you need to circumvent the normal rules.

(But since D is a systems programming language, this kind of super-dangerous casting must be allowed. It just shouldn't be the default. To my mind, the exclamation mark says that).

Bear in mind that even without reinterpret cast, you will always be able to achieve the same thing with unions. Watch:

    DstType reinterpret_cast(DstType, SrcType)(SrcType x)
    {
        union U
        {
            SrcType src;
            DstType dst;
        }

        U u;
        u.src = x;
        return u.dst;
    }

In other words, if you ban reinterpret cast, someone's only going to do it anyway.

Ummm ... wait a minute ... !

I think I just found a reason /not/ to have a reinterpret cast in the language - the reason being, it can be done in a library function, as I just showed. Hey, I think that means we don't need that one at all. Hmm...



>  Also, My definition was that cast() can change the memory while cast!()
>  doesn't. it seems you define them in reverse of that.

Well, not quite. In C++, only static_cast<T>(x) can change the memory
(but it might not), wheras I suggest that in D, cast(T)x (i.e. the
default cast) should just "do the sensible thing" - sort of like it
does now, except with the dangerous cases removed - so it would act
like dynamic_cast<T>(x) where appropriate, and static_cast<T>(x) where
dynamic_cast<T> would be inappropriate. So, sometimes it will change
memory, sometimes not. But const cast and cast! would never change
memory.

Examples:

    double d;
    int x = cast(int)d; // creates new int

    class A {}
    class B : A {}
    A a = new B;

    B b = cast(B)a;
        // dynamic cast. a and b point to same object

    C b = static cast(B)a;
        // as above, but without the runtime check that a is really a B

    class D {}
    const d = new D;

    D d2 = cast(D)d; // ERROR - cannot remove constancy
    D d2 = const cast(D)d; // OK

    D d3 = cast(D)a; // ERROR - can't convert A to D
    D d3 = static cast(D)a; // ERROR - can't convert A to D
    D d3 = const cast(D)a; // ERROR - can't convert A to D
    D d3 = cast!(D)a; // OK - but you'd better know what you're doing!
May 11, 2008
Yigal Chripun Wrote:

> Your example does use delegates.
> the difference is this:
> say you have two delegates you pass to sort, for example you sort one
> array in ascending order, and another in descending order. the template
> solution will generate two almost identical sort functions with the only
> difference that one sort instance calls internally the first delegate,
> and the second instance calls the second. you get 4 functions. without
> the template, you get one sort function and two delegates, so only 3
> functions.

This should be good for the standard library. It is the most flexible approach. You can always do what you want in one line:

void mysort(int array[], bool delegate comp(int, int))
{
    sort!(comp)(array);
}

Now you can call mysort many times and there is only one version of std.sort (if I understand it correctly).

But think what if your mysort is the only implementation given in the standard library. Maybe sometimes it is too slow for your program. What do you do?

void fastsort!(alias comp)(int[] array)
{
    bool dg(int a, int b) { return comp(a, b); }
    mysort(array, dg);
}

This will not be faster at all ^_^. As a friend said: You can build a dynamic library from a static one but not inverse. Things only stack one direction. I think it is good the way sort is now in the standard library, it offers the maximum possible and opens all options. It is very impressive for someone coming from many other language.

> Now, when you use a string with the template, the sort will contain the code itself inline to the sort instance so it "saves" you a function call. IMO, the string solution is not clean ( C MACROs? )and while for simple cases it could save you a function call it's premature optimization IMO.

To me it looks very convinent!

> Also, if I use delegates, I can't see how a template
> can save that function call. so it just bloats my executable with
> unneeded copies of sort.

You can use mysort above. It is my first contribution to D. ^_^

> I hate when library code forces me to this. I think the programmer knows his code better than the library writer and should be able to choose himself whether he needs to use a compile time solution to save function calls or a run-time solution to prevent unnecessary executable bloat. this optimization should be made by the programmer and _not_ the library writer. This solution does not give me that freedom.

It looks like you understand the exact oposite. std.sort gives you all freedom, anything else would give less. I have studied many languages but none offers the same flexibility. Functional languages force you to copy. Java, Smalltalk and C# force virtual calls on comparisons. C++ force you to go outside your function and write the comparison even simple as a.member < b.member! D is the best and std.algorithm very elegant.

> this solution is a classic STL piece of code, BUT, the main difference is that for C++ this is probably the only reasonable solution as C++ doesn't have delegates. this is why when coding for D I urge people to rethink their solution instead of just doing what is best in C++ (or any other preferred language of the library writer). This is a prime example why the C++ solution is wrong for D.

The other rant you wrote and the interesting discussion with Janice are good to read. But there is little objective points you bring. I see you do not like anything like C++ and then you go back and try to make arguments.

One objective point is you like a container hierarchy. I have worked with them and they can be useful. But like with mysort the same argument works. You can build a hierarchy of containers on top of fast containers. But not the inverse. Dee Girl
May 11, 2008
Dee Girl wrote:
> Yigal Chripun Wrote:
> 
> 
> This should be good for the standard library. It is the most flexible approach. You can always do what you want in one line:
> 
> void mysort(int array[], bool delegate comp(int, int)) { sort!(comp)(array); }
> 
> Now you can call mysort many times and there is only one version of std.sort (if I understand it correctly).

not exactly. there's always a balance between memory and time, if you
improve the first second worsens.
for each different comp function there will be a different sort instance
created by the compiler.
a simple example:
struct num(N) { int number = N; }
num!(1) is different from num!(2);
so with this method you'll get a bigger executable that contains the
sort code twice.
with my way on the other hand you'll always have only one sort function.
the cost in my case is that sort will always call the comp function to
compare while the template can avoid that function call. simply time vs.
memory. memory is cheap nowadays and the linker could be made better to
try to minimize the memory footprint. on the other hand cpu chips today
come with multi-cores and the compiler could optimize many calls to
small functions. so in the obj file, the compiler can inline the
function body instead of calling it.
the main question would be: what are you optimizing for?
if you develop on a cellphone memory could be more important then time,
but on a missile a nano second could mean the missile missed its target.
so it all depends on what you want to achieve.

> 
> But think what if your mysort is the only implementation given in the standard library. Maybe sometimes it is too slow for your program. What do you do?
> 
> void fastsort!(alias comp)(int[] array) { bool dg(int a, int b) {
> return comp(a, b); } mysort(array, dg); }
> 
> This will not be faster at all ^_^. As a friend said: You can build a dynamic library from a static one but not inverse. Things only stack one direction. I think it is good the way sort is now in the standard library, it offers the maximum possible and opens all options. It is very impressive for someone coming from many other language.
> 
>> Now, when you use a string with the template, the sort will contain the code itself inline to the sort instance so it "saves" you a function call. IMO, the string solution is not clean ( C MACROs? )and while for simple cases it could save you a function call it's premature optimization IMO.
> 
> To me it looks very convinent!
> 
>> Also, if I use delegates, I can't see how a template can save that function call. so it just bloats my executable with unneeded copies of sort.
> 
> You can use mysort above. It is my first contribution to D. ^_^
> 
>> I hate when library code forces me to this. I think the programmer knows his code better than the library writer and should be able to choose himself whether he needs to use a compile time solution to save function calls or a run-time solution to prevent unnecessary executable bloat. this optimization should be made by the programmer and _not_ the library writer. This solution does not give me that freedom.
> 
> It looks like you understand the exact oposite. std.sort gives you all freedom, anything else would give less. I have studied many languages but none offers the same flexibility. Functional languages force you to copy. Java, Smalltalk and C# force virtual calls on comparisons. C++ force you to go outside your function and write the comparison even simple as a.member < b.member! D is the best and std.algorithm very elegant.
> 
>> this solution is a classic STL piece of code, BUT, the main difference is that for C++ this is probably the only reasonable solution as C++ doesn't have delegates. this is why when coding for D I urge people to rethink their solution instead of just doing what is best in C++ (or any other preferred language of the library writer). This is a prime example why the C++ solution is wrong for D.
> 
> The other rant you wrote and the interesting discussion with Janice are good to read. But there is little objective points you bring. I see you do not like anything like C++ and then you go back and try to make arguments.
> 
> One objective point is you like a container hierarchy. I have worked with them and they can be useful. But like with mysort the same argument works. You can build a hierarchy of containers on top of fast containers. But not the inverse. Dee Girl

My rant emphasizes specific things, since that's the point of a rant. I could talk about all the things I like in C++ and Janice would agree and we won't have anything interesting to talk about. I do use c++ and it is a powerful language. My point is not that I'm against templates, or that I hate C++. What i'm trying to say is that using any one tool for everything is wrong. I'm not arguing that delegates should replace all template code in D! I'm arguing that both solutions need to be evaluated and the better one chosen, also note that these two options overlap sometimes and (when it's suitable) both solutions should be provided so the user could choose his preferred trade-off (time vs. memory).

--Yigal
May 11, 2008
On 11/05/2008, Yigal Chripun <yigal100@gmail.com> wrote:
>  for each different comp function there will be a different sort instance
>  created by the compiler.

But surely, every container must itself be templatised on the element? I mean, unless you go the Java way and /only/ have a container for Objects. So your plan would instantiate at least one sort function for every element type.

Moreover, since your OrderedCollection interface would demand that every container must implement sort, then every different kind of collection would have it's own sort function.

So under your scheme, the total number of sort functions would equal the total number of container types. In other word, if your program used

    List!(char) list1, list2;
    List!(int) list3;
    List!(C) list4, list5;
    Array!(double) array1;

then there would be four sort functions. In what way is that fewer than would be produced by

    sort(list1);
    sort(list2);
    sort(list3);
    sort(list4);
    sort(list5);
    sort(array1);

? The way I see it, we both get four. However, if choose /not/ to sort list3, then I only get three instantiations, but you still get four.




>  What i'm trying to say is that using any one tool for
>  everything is wrong.

You should have just said that to start with, because it's a statement of the obvious and no one will disagree with you. :-)


>  I'm not arguing that delegates should replace all
>  template code in D! I'm arguing that both solutions need to be evaluated
>  and the better one chosen

Why are you assuming that that didn't happen?


>  also note that these two options overlap
>  sometimes and (when it's suitable) both solutions should be provided so
>  the user could choose his preferred trade-off (time vs. memory).

Except that, if you can trivially create one from the other, then providing one is effectively providing both anyway.