www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Round-up of the excuses for keeping Object.opCmp, and rebuttals to

reply Stewart Gordon <smjg_1998 yahoo.com> writes:
1. "It's needed for associative arrays to work."

Firstly, this is implementation-specific.  There's no need for AAs to be 
implemented in terms of Object.opCmp, or to rely on an ordering 
comparator at all.  True, an ordering can make AAs more efficient, but 
only where one exists.  If anything, then in the current state 
Object.opCmp is _preventing_ AAs from working on classes that have no 
ordering.

2. "How else can an array of objects be sorted?"

Objects of diverse classes aren't going to be mutually comparable.  Of 
course, one might want to design two or more classes with comparability 
between them.  But if that's the case, then they would derive from some 
common base class or interface that defines the scope of mutual 
comparability.  Then sorting an Object[] doesn't make sense, but sorting 
an array of the common base class does.

3. "Putting it in Object reserves a predictable vtbl[] slot for it."

If everything (e.g. array aggregate properties when/if we get them) 
followed the implementation pattern of AAs and sort, then we would end 
up with a lot of vtbl slots reserved for operators that tend to do 
nothing, and even more coding errors to slip through the compiler to the 
runtime.

Even if there's some reason to keep AAs and sort to use this mechanism, 
rather than reimplementing them by templates, then reserving a 
predictable vtbl slot doesn't need to be done by actually filling it. 
It could be done simply by specifying a slot to be reserved in the ABI. 
  In Object, this slot would be set to null, and the compiler would fill 
it only when a class Qwert defines an opCmp(Qwert).

Of course, if you then have something like

     class Yuiop : Qwert {
         int opCmp(Qwert q) { ... }

         int opCmp(Yuiop y) { ... }
     }

then the first form would override.  This makes sense, as it only makes 
sense for Yuiop.opCmp(Qwert) to call Yuiop.opCmp(Yuiop) if the argument 
is a Yuiop.  Then we have a principle: the reserved slot would carry the 
form of opCmp that reflects the scope of mutual comparability.  Hence 
Yuiop[].sort and Qwert[].sort would behave identically, and consistently 
with uses of the comparison operators directly (under current rules) 
regardless of which types are declared.

Then, when an AA is declared of a certain class as keytype, the compiler 
would look in that class's vtbl to see if the opCmp slot is set to null; 
in which case, it would hook up an AA implementation that doesn't rely 
on opCmp.  Similarly, when sort is called on an array, the compiler 
would report an error if opCmp is null.


Maybe some other excuses have been brought up before, but I can't think 
of them.  Is there anything to add to this list?

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
Sep 13 2004
next sibling parent "Ivan Senji" <ivan.senji public.srce.hr> writes:
"Stewart Gordon" <smjg_1998 yahoo.com> wrote in message
news:ci46lq$19k0$1 digitaldaemon.com...

 1. "It's needed for associative arrays to work."

 Firstly, this is implementation-specific.  There's no need for AAs to be
 implemented in terms of Object.opCmp, or to rely on an ordering
 comparator at all.  True, an ordering can make AAs more efficient, but
 only where one exists.  If anything, then in the current state
 Object.opCmp is _preventing_ AAs from working on classes that have no
 ordering.

 2. "How else can an array of objects be sorted?"

 Objects of diverse classes aren't going to be mutually comparable.  Of
 course, one might want to design two or more classes with comparability
 between them.  But if that's the case, then they would derive from some
 common base class or interface that defines the scope of mutual
 comparability.  Then sorting an Object[] doesn't make sense, but sorting
 an array of the common base class does.

 3. "Putting it in Object reserves a predictable vtbl[] slot for it."

 If everything (e.g. array aggregate properties when/if we get them)
 followed the implementation pattern of AAs and sort, then we would end
 up with a lot of vtbl slots reserved for operators that tend to do
 nothing, and even more coding errors to slip through the compiler to the
 runtime.

 Even if there's some reason to keep AAs and sort to use this mechanism,
 rather than reimplementing them by templates, then reserving a
 predictable vtbl slot doesn't need to be done by actually filling it.
 It could be done simply by specifying a slot to be reserved in the ABI.
   In Object, this slot would be set to null, and the compiler would fill
 it only when a class Qwert defines an opCmp(Qwert).

 Of course, if you then have something like

      class Yuiop : Qwert {
          int opCmp(Qwert q) { ... }

          int opCmp(Yuiop y) { ... }
      }

 then the first form would override.  This makes sense, as it only makes
 sense for Yuiop.opCmp(Qwert) to call Yuiop.opCmp(Yuiop) if the argument
 is a Yuiop.  Then we have a principle: the reserved slot would carry the
 form of opCmp that reflects the scope of mutual comparability.  Hence
 Yuiop[].sort and Qwert[].sort would behave identically, and consistently
 with uses of the comparison operators directly (under current rules)
 regardless of which types are declared.

 Then, when an AA is declared of a certain class as keytype, the compiler
 would look in that class's vtbl to see if the opCmp slot is set to null;
 in which case, it would hook up an AA implementation that doesn't rely
 on opCmp.  Similarly, when sort is called on an array, the compiler
 would report an error if opCmp is null.


 Maybe some other excuses have been brought up before, but I can't think
 of them.  Is there anything to add to this list?


A very nice post! And a great illustration of problems that opCmp causes
:)


 Stewart.

 --
 My e-mail is valid but not my primary mailbox.  Please keep replies on
 the 'group where everyone may benefit.
Sep 13 2004
prev sibling next sibling parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"excuses"? that's a pretty heavy word to use.

More to the point, Walter knows the TypeInfo system needs more bake-time.
opCmp is crucial to Object's TypeInfo. So any proposal to remove opCmp needs
to include a proposal to modify the TypeInfo for Object or to modify the
TypeInfo system generally. I don't know the details about how the compiler
manages TypeInfos (I know there are a bunch in std/typeinfo but I don't know
if the compiler looks at that code during compiling or only at link time).
Since the TypeInfo existed before templates I wouldn't be surprised if some
parts of TypeInfo can be removed - but it would probably take non-trivial
compiler changes. I don't know if Walter is going to take the time to step
back and look at TypeInfos before 1.0.

"Stewart Gordon" <smjg_1998 yahoo.com> wrote in message
news:ci46lq$19k0$1 digitaldaemon.com...

 1. "It's needed for associative arrays to work."

 Firstly, this is implementation-specific.  There's no need for AAs to be
 implemented in terms of Object.opCmp, or to rely on an ordering
 comparator at all.  True, an ordering can make AAs more efficient, but
 only where one exists.  If anything, then in the current state
 Object.opCmp is _preventing_ AAs from working on classes that have no
 ordering.

 2. "How else can an array of objects be sorted?"

 Objects of diverse classes aren't going to be mutually comparable.  Of
 course, one might want to design two or more classes with comparability
 between them.  But if that's the case, then they would derive from some
 common base class or interface that defines the scope of mutual
 comparability.  Then sorting an Object[] doesn't make sense, but sorting
 an array of the common base class does.

 3. "Putting it in Object reserves a predictable vtbl[] slot for it."

 If everything (e.g. array aggregate properties when/if we get them)
 followed the implementation pattern of AAs and sort, then we would end
 up with a lot of vtbl slots reserved for operators that tend to do
 nothing, and even more coding errors to slip through the compiler to the
 runtime.

 Even if there's some reason to keep AAs and sort to use this mechanism,
 rather than reimplementing them by templates, then reserving a
 predictable vtbl slot doesn't need to be done by actually filling it.
 It could be done simply by specifying a slot to be reserved in the ABI.
   In Object, this slot would be set to null, and the compiler would fill
 it only when a class Qwert defines an opCmp(Qwert).

 Of course, if you then have something like

      class Yuiop : Qwert {
          int opCmp(Qwert q) { ... }

          int opCmp(Yuiop y) { ... }
      }

 then the first form would override.  This makes sense, as it only makes
 sense for Yuiop.opCmp(Qwert) to call Yuiop.opCmp(Yuiop) if the argument
 is a Yuiop.  Then we have a principle: the reserved slot would carry the
 form of opCmp that reflects the scope of mutual comparability.  Hence
 Yuiop[].sort and Qwert[].sort would behave identically, and consistently
 with uses of the comparison operators directly (under current rules)
 regardless of which types are declared.

 Then, when an AA is declared of a certain class as keytype, the compiler
 would look in that class's vtbl to see if the opCmp slot is set to null;
 in which case, it would hook up an AA implementation that doesn't rely
 on opCmp.  Similarly, when sort is called on an array, the compiler
 would report an error if opCmp is null.


 Maybe some other excuses have been brought up before, but I can't think
 of them.  Is there anything to add to this list?

 Stewart.

 -- 
 My e-mail is valid but not my primary mailbox.  Please keep replies on
 the 'group where everyone may benefit.
Sep 13 2004
parent Stewart Gordon <smjg_1998 yahoo.com> writes:
Ben Hinkle wrote:


 "excuses"? that's a pretty heavy word to use.
 
 More to the point, Walter knows the TypeInfo system needs more bake-time.
 opCmp is crucial to Object's TypeInfo. So any proposal to remove opCmp needs
 to include a proposal to modify the TypeInfo for Object or to modify the
 TypeInfo system generally.


<snip top of upside-down reply>

LTIK, the plan was to have class-specific TypeInfos - this is already a 
shortcoming in a handful of respects.  But yes, you have a point.

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
Sep 14 2004
prev sibling parent reply "Matthew" <admin stlsoft.dot.dot.dot.dot.org> writes:
First of all, I have to say that I think the whole idea of opCmp, and 
any similar things involving/requiring Object references and casts, 
stinks. I don't have to do any of this kind of crap in C++ to achieve 
all manner of efficient and generic manipulation. One has to to it in 
Java/.NET, but then .... <editor: censored for being rude and 
repetitive> ... which D claims to be an evolution from.

Specific responses (and the occasional gripe) within.

"Stewart Gordon" <smjg_1998 yahoo.com> wrote in message 
news:ci46lq$19k0$1 digitaldaemon.com...

 1. "It's needed for associative arrays to work."

 Firstly, this is implementation-specific.  There's no need for AAs to 
 be implemented in terms of Object.opCmp, or to rely on an ordering 
 comparator at all.  True, an ordering can make AAs more efficient, but 
 only where one exists.  If anything, then in the current state 
 Object.opCmp is _preventing_ AAs from working on classes that have no 
 ordering.


Since AAs are built-in, why on earth do they need to rely on runtime 
polymorphism. Given the classes X and Y

class X
{
}

class Y
{
    int opCmp(Y rhs);
}

What prevents the compiler from generating sorting based on arbitrary 
difference (e.g. address of instance) for X, and using the 
*non-polymorphic* Y::opCmp(Y) ?? (I know all methods are polymorphic in 
D, but


 2. "How else can an array of objects be sorted?"


Why should an array of arbitrary types be sortable??

For example, suppose I have an array of PGP keys, or MD5 hashes. In what 
way could one define a meaningful ordering relation? (Naturally one can 
go lexicographical, but that's an arbitrary choice. Might as well order 
on which one contains the longest character sub-sequence of the word 
"Churlish" within them.)

If anyone truly wants to be able to meaningfully sort a Chair, a 
Weather, an Md5Sum, and a Vector object held in an array, then they need 
to strap on the latex and go wibble!

Sorting of Object is utterly bogus, and should be immediately dispensed 
with. (However, polymorphic sorting is not necessarily wrong .... )


 Objects of diverse classes aren't going to be mutually comparable.


Abso-stinkingly-lutely not!!

It's really easy. For polymorphic classes, such as the following, one 
can easily support comparison:


class Base
{
    int opCmp(Base);    // NOTE: param is Base
}

class Derived
    : public Base
{
}

class MoreDerived
    : public Derived
{
}

As it stands above, a heterogeneous array of instances of these types, 
say [b1, b2, d1, md1, b3, md2, b4] would be sortable because Base 
derives opCmp(). Moreover, it would be sorted solely by the 
implementation of Base.opCmp() for all instances irrespective of their 
actual type.

    Base[]    ba =    [b1, b2, d1, md1, b3, md2, b4];

    ba.sort; // Calls Base.opCmp(Base)

Similarly, an array of Derived (and MoreDerived) would also sort using 
Base.opCmp().

    Derived[]  da = [d1, md1, md2]

    da.sort; // Calls Base.opCmp(Base)

Now consider that the author of MoreDerived knows - and being the author 
of the class, he/she's the one that will know - that they need to 
override the sorting logic for sorting of non-heterogeneous arrays of 
MoreDerived instances. (Actually, it's not "non-heterogeneous arrays of 
MoreDerived instances." In fact, it's "Arrays of MoreDerived (and any 
class derived from MoreDerived).") All he/she does is define an 
_overload_, opCmp(MoreDerived)

class MoreDerived
    : public Derived
{
    int opCmp(MoreDerived); // Note: param is MoreDerived
}

MoreDerived mda = [md1, md2]

mda.sort; // Calls MoreDerived.opCmp(MoreDerived)


Now, when the compiler is generating the code to sort an array on 
MoreDerived, it will implement it in terms of 
MoreDerived.opCmp(MoreDerived). It will do _nothing_ with Base.opCmp(). 
Indeed, if the author of Base was to remove Base.opCmp(Base), rendering 
the lines "ba.sort;" and "da.sort;" as compile errors, the line 
"mda.sort;" would be entirely unaffected and would remain legal.

Now consider that the author of Derived wants to override opCmp(Base), 
in order to something a little smarter when involved in Base sorting. 
Now "ba.sort;" will use both Base.opCmp(Base) and Derived.opCmp(Base). 
That's perfectly right, because MoreDerived, as a child of Derived that 
has _not_ overrident opCmp(Base), is implicitly defined to be happy with 
what Derived does when Base sorting. (Child-Base coupling fragility 
necessarily applies here, of course, but that's an artefact of OO, and 
nothing to do with the ramifications of this proposal.) The important 
thing is that this amendment to the hierarchy does not affect 
"mda.sort;" one whit. It still uses MoreDerived.sort(MoreDerived).

In practical terms, the issues of what-actually-happens-in-the-sort and 
comparing-with-same-type-or-base-type will remain as they do in current 
OO hierarchies. The important distinction between this and the current 
situation is that the compiler sorts using the deepest opCmp() available 
for all types in the array. (I've not considered what other sorting 
arrangements we might consider, but I suspect that polymorphism will 
resolve to the deepest one in sorting template containers, doing what I 
propose for the compiler do as a natural part of runtime polymorphism. 
Which is nice. <g>)

Since a corollary stipulation is that comparison will only be allowed 
(_at_compile_time_ !! Hurrah!!!) for types for which it is sensible to 
do so - i.e. those that are polymorphically related from a common 
non-root subtree of the class hierarchy and have, in a common ancestor, 
an opCmp defined - we'd totally avoid all that evil 
is-rhs-same-type-if-not-throw guff.

In a sense, this would be like the IComparable stuff, but for the fact 
that any shared parent that sports an opCmp can act as such an 
'interface', without the attendant hassles of a prescribed interface.

I respectfully submit that this proposal completely obviates the need 
for opCmp as far as arrays are concerned and, in addition, affords us 
the opportunity to tighted up type resolution at compile time. All 
without costing us any flexibility. (There may, of course, be unforeseen 
drawbacks, as I'm less omniscient than I was ...)


 3. "Putting it in Object reserves a predictable vtbl[] slot for it."

 If everything (e.g. array aggregate properties when/if we get them) 
 followed the implementation pattern of AAs and sort, then we would end 
 up with a lot of vtbl slots reserved for operators that tend to do 
 nothing, and even more coding errors to slip through the compiler to 
 the runtime.


Agreed. Why not have a vtbl[] slot for everthing: serialisation, 
sorting, stringising, etc. etc. etc.

In a modern language with powerful generic facilities - templates, shims 
(if we ever devise the way to do these in D), interfaces, mixins, etc. - 
why do we need to put on such straight jackets?

(That question's not entirely rhetorical. If there is a genuine reason 
that benefits the user, and not just the implementor, then I'm very 
interested to hear it.)


 Even if there's some reason to keep AAs and sort to use this 
 mechanism, rather than reimplementing them by templates, then 
 reserving a predictable vtbl slot doesn't need to be done by actually 
 filling it. It could be done simply by specifying a slot to be 
 reserved in the ABI. In Object, this slot would be set to null, and 
 the compiler would fill it only when a class Qwert defines an 
 opCmp(Qwert).


True, but that's now something that sucks 50% rather than 100%. Let's 
get 0.


 Of course, if you then have something like

     class Yuiop : Qwert {
         int opCmp(Qwert q) { ... }

         int opCmp(Yuiop y) { ... }
     }

 then the first form would override.  This makes sense, as it only 
 makes sense for Yuiop.opCmp(Qwert) to call Yuiop.opCmp(Yuiop) if the 
 argument is a Yuiop.  Then we have a principle: the reserved slot 
 would carry the form of opCmp that reflects the scope of mutual 
 comparability.  Hence Yuiop[].sort and Qwert[].sort would behave 
 identically, and consistently with uses of the comparison operators 
 directly (under current rules) regardless of which types are declared.

 Then, when an AA is declared of a certain class as keytype, the 
 compiler would look in that class's vtbl to see if the opCmp slot is 
 set to null; in which case, it would hook up an AA implementation that 
 doesn't rely on opCmp.  Similarly, when sort is called on an array, 
 the compiler would report an error if opCmp is null.


Hmmm. This seems somewhat similar to my proposal above, apart from the 
slot business (which I say has no business being a concern) - maybe I 
should have read all your post before starting my reply. <CG>

Seriously, though, the fact that two people have come up with a similar 
idea for kicking opCmp() out of where it has no business being gives 
some encouragement, methinks.


 Maybe some other excuses have been brought up before, but I can't 
 think of them.  Is there anything to add to this list?


Since your post elicited little response in September, we must surmise 
that there are none.

Walter, I commend this idea for your sincerest consideration.

:-)

Matthew
Mar 08 2005
next sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
Matthew, may I translate your proposal(?)(below) into this:

"opCmp based array sort is bad.
 It does not support runtime polymorphism. We need to change this"
Am I right?

I've attached simple template (with example)

template sort(T)
{
  void sort(T[] arr, int function(in T l, in T r) cmp) {...}
}

used as:

int arr[] = new int[10000];
sort!(int) ( arr,   function int(int i1,int i2) { return i1 - i2; }    );

It is simple and works *30% faster* than D builtin sort. Walter, please, pay 
attention - C standard qsort is a piece of...

Andrew Fedoniouk.
http://terrainformatica.com

"Matthew" <admin stlsoft.dot.dot.dot.dot.org> wrote in message 
news:d0lsv5$1496$1 digitaldaemon.com...

 First of all, I have to say that I think the whole idea of opCmp, and
 any similar things involving/requiring Object references and casts,
 stinks. I don't have to do any of this kind of crap in C++ to achieve
 all manner of efficient and generic manipulation. One has to to it in
 Java/.NET, but then .... <editor: censored for being rude and
 repetitive> ... which D claims to be an evolution from.

 Specific responses (and the occasional gripe) within.

 "Stewart Gordon" <smjg_1998 yahoo.com> wrote in message
 news:ci46lq$19k0$1 digitaldaemon.com...

 1. "It's needed for associative arrays to work."

 Firstly, this is implementation-specific.  There's no need for AAs to
 be implemented in terms of Object.opCmp, or to rely on an ordering
 comparator at all.  True, an ordering can make AAs more efficient, but
 only where one exists.  If anything, then in the current state
 Object.opCmp is _preventing_ AAs from working on classes that have no
 ordering.


 Since AAs are built-in, why on earth do they need to rely on runtime
 polymorphism. Given the classes X and Y

 class X
 {
 }

 class Y
 {
    int opCmp(Y rhs);
 }

 What prevents the compiler from generating sorting based on arbitrary
 difference (e.g. address of instance) for X, and using the
 *non-polymorphic* Y::opCmp(Y) ?? (I know all methods are polymorphic in
 D, but


 2. "How else can an array of objects be sorted?"


 Why should an array of arbitrary types be sortable??

 For example, suppose I have an array of PGP keys, or MD5 hashes. In what
 way could one define a meaningful ordering relation? (Naturally one can
 go lexicographical, but that's an arbitrary choice. Might as well order
 on which one contains the longest character sub-sequence of the word
 "Churlish" within them.)

 If anyone truly wants to be able to meaningfully sort a Chair, a
 Weather, an Md5Sum, and a Vector object held in an array, then they need
 to strap on the latex and go wibble!

 Sorting of Object is utterly bogus, and should be immediately dispensed
 with. (However, polymorphic sorting is not necessarily wrong .... )


 Objects of diverse classes aren't going to be mutually comparable.


 Abso-stinkingly-lutely not!!

 It's really easy. For polymorphic classes, such as the following, one
 can easily support comparison:


 class Base
 {
    int opCmp(Base);    // NOTE: param is Base
 }

 class Derived
    : public Base
 {
 }

 class MoreDerived
    : public Derived
 {
 }

 As it stands above, a heterogeneous array of instances of these types,
 say [b1, b2, d1, md1, b3, md2, b4] would be sortable because Base
 derives opCmp(). Moreover, it would be sorted solely by the
 implementation of Base.opCmp() for all instances irrespective of their
 actual type.

    Base[]    ba =    [b1, b2, d1, md1, b3, md2, b4];

    ba.sort; // Calls Base.opCmp(Base)

 Similarly, an array of Derived (and MoreDerived) would also sort using
 Base.opCmp().

    Derived[]  da = [d1, md1, md2]

    da.sort; // Calls Base.opCmp(Base)

 Now consider that the author of MoreDerived knows - and being the author
 of the class, he/she's the one that will know - that they need to
 override the sorting logic for sorting of non-heterogeneous arrays of
 MoreDerived instances. (Actually, it's not "non-heterogeneous arrays of
 MoreDerived instances." In fact, it's "Arrays of MoreDerived (and any
 class derived from MoreDerived).") All he/she does is define an
 _overload_, opCmp(MoreDerived)

 class MoreDerived
    : public Derived
 {
    int opCmp(MoreDerived); // Note: param is MoreDerived
 }

 MoreDerived mda = [md1, md2]

 mda.sort; // Calls MoreDerived.opCmp(MoreDerived)


 Now, when the compiler is generating the code to sort an array on
 MoreDerived, it will implement it in terms of
 MoreDerived.opCmp(MoreDerived). It will do _nothing_ with Base.opCmp().
 Indeed, if the author of Base was to remove Base.opCmp(Base), rendering
 the lines "ba.sort;" and "da.sort;" as compile errors, the line
 "mda.sort;" would be entirely unaffected and would remain legal.

 Now consider that the author of Derived wants to override opCmp(Base),
 in order to something a little smarter when involved in Base sorting.
 Now "ba.sort;" will use both Base.opCmp(Base) and Derived.opCmp(Base).
 That's perfectly right, because MoreDerived, as a child of Derived that
 has _not_ overrident opCmp(Base), is implicitly defined to be happy with
 what Derived does when Base sorting. (Child-Base coupling fragility
 necessarily applies here, of course, but that's an artefact of OO, and
 nothing to do with the ramifications of this proposal.) The important
 thing is that this amendment to the hierarchy does not affect
 "mda.sort;" one whit. It still uses MoreDerived.sort(MoreDerived).

 In practical terms, the issues of what-actually-happens-in-the-sort and
 comparing-with-same-type-or-base-type will remain as they do in current
 OO hierarchies. The important distinction between this and the current
 situation is that the compiler sorts using the deepest opCmp() available
 for all types in the array. (I've not considered what other sorting
 arrangements we might consider, but I suspect that polymorphism will
 resolve to the deepest one in sorting template containers, doing what I
 propose for the compiler do as a natural part of runtime polymorphism.
 Which is nice. <g>)

 Since a corollary stipulation is that comparison will only be allowed
 (_at_compile_time_ !! Hurrah!!!) for types for which it is sensible to
 do so - i.e. those that are polymorphically related from a common
 non-root subtree of the class hierarchy and have, in a common ancestor,
 an opCmp defined - we'd totally avoid all that evil
 is-rhs-same-type-if-not-throw guff.

 In a sense, this would be like the IComparable stuff, but for the fact
 that any shared parent that sports an opCmp can act as such an
 'interface', without the attendant hassles of a prescribed interface.

 I respectfully submit that this proposal completely obviates the need
 for opCmp as far as arrays are concerned and, in addition, affords us
 the opportunity to tighted up type resolution at compile time. All
 without costing us any flexibility. (There may, of course, be unforeseen
 drawbacks, as I'm less omniscient than I was ...)


 3. "Putting it in Object reserves a predictable vtbl[] slot for it."

 If everything (e.g. array aggregate properties when/if we get them)
 followed the implementation pattern of AAs and sort, then we would end
 up with a lot of vtbl slots reserved for operators that tend to do
 nothing, and even more coding errors to slip through the compiler to
 the runtime.


 Agreed. Why not have a vtbl[] slot for everthing: serialisation,
 sorting, stringising, etc. etc. etc.

 In a modern language with powerful generic facilities - templates, shims
 (if we ever devise the way to do these in D), interfaces, mixins, etc. -
 why do we need to put on such straight jackets?

 (That question's not entirely rhetorical. If there is a genuine reason
 that benefits the user, and not just the implementor, then I'm very
 interested to hear it.)


 Even if there's some reason to keep AAs and sort to use this
 mechanism, rather than reimplementing them by templates, then
 reserving a predictable vtbl slot doesn't need to be done by actually
 filling it. It could be done simply by specifying a slot to be
 reserved in the ABI. In Object, this slot would be set to null, and
 the compiler would fill it only when a class Qwert defines an
 opCmp(Qwert).


 True, but that's now something that sucks 50% rather than 100%. Let's
 get 0.


 Of course, if you then have something like

     class Yuiop : Qwert {
         int opCmp(Qwert q) { ... }

         int opCmp(Yuiop y) { ... }
     }

 then the first form would override.  This makes sense, as it only
 makes sense for Yuiop.opCmp(Qwert) to call Yuiop.opCmp(Yuiop) if the
 argument is a Yuiop.  Then we have a principle: the reserved slot
 would carry the form of opCmp that reflects the scope of mutual
 comparability.  Hence Yuiop[].sort and Qwert[].sort would behave
 identically, and consistently with uses of the comparison operators
 directly (under current rules) regardless of which types are declared.

 Then, when an AA is declared of a certain class as keytype, the
 compiler would look in that class's vtbl to see if the opCmp slot is
 set to null; in which case, it would hook up an AA implementation that
 doesn't rely on opCmp.  Similarly, when sort is called on an array,
 the compiler would report an error if opCmp is null.


 Hmmm. This seems somewhat similar to my proposal above, apart from the
 slot business (which I say has no business being a concern) - maybe I
 should have read all your post before starting my reply. <CG>

 Seriously, though, the fact that two people have come up with a similar
 idea for kicking opCmp() out of where it has no business being gives
 some encouragement, methinks.


 Maybe some other excuses have been brought up before, but I can't
 think of them.  Is there anything to add to this list?


 Since your post elicited little response in September, we must surmise
 that there are none.

 Walter, I commend this idea for your sincerest consideration.

 :-)

 Matthew

 



begin 666 sorter.d


M;G0 <F%N9&]M*"D-"GL-"B  <F5T=7)N(" H<F%N9&]M4V5E9" ](')A;F1O


M871E('-O<G0H5"D-"GL-"B  =F]I9"!S;W)T*%1;72!A<G(L(&EN="!F=6YC


M;&5N9W1H(#P
M<R  :6YO=70 5"!T,2P :6YO=70 5"!T,B I( T*("  ("  >R -"B  ("  

M('0R(#T =#L ?0T*("  ("  ?0T*("  ("  =F]I9"!S=V%P*"!I;F]U="!4


M86-K6S P73L-"B  ("  (&EN="H =&]P(#T <W1A8VL[( T*("  ("  :6YT


M(&QI;6ET("T 8F%S93L-" T*("  ("  ("  (&EN="!I.PT*("  ("  ("  
M(&EN="!J.PT*("  ("  ("  (&EN="!P:79O=#L-" T*("  ("  ("  (&EF
M*&QE;B ^('%U:6-K7W-O<G1?=&AR97-H;VQD*0T*("  ("  ("  ('L-"B  
M("  ("  ("  ("  +R\ =V4 =7-E(&)A<V4 *R!L96XO,B!A<R!T:&4 <&EV
M;W0-"B  ("  ("  ("  ("  <&EV;W0 /2!B87-E("L ;&5N("\ ,CL-"B  

M("  ("  ("  ("  (&D /2!B87-E("L ,3L-"B  ("  ("  ("  ("  :B ]
M(&QI;6ET("T ,3L-" T*("  ("  ("  ("  (" O+R!N;W< 96YS=7)E('1H
M870 *FD /#T *F)A<V4 /#T

M;&5S<RAA<G);8F%S95TL87)R6VE=*3L-"B  ("  ("  ("  ("  <W=A<%]I

M<B [.RD-"B  ("  ("  ("  ("  >PT*("  ("  ("  ("  ("  ("  9&\ 
M:2LK.R!W:&EL92  87)R6VE=(#P (&%R<EMB87-E72 I.PT*("  ("  ("  
M("  ("  ("  9&\ :BTM.R!W:&EL92  87)R6V)A<V5=(#P (&%R<EMJ72 I
M.PT*("  ("  ("  ("  ("  ("  :68H(&D /B!J("D-"B  ("  ("  ("  
M("  ("  ('L-"B  ("  ("  ("  ("  ("  ("  ("!B<F5A:SL-"B  ("  
M("  ("  ("  ("  ('T-"B  ("  ("  ("  ("  ("  ('-W87 H87)R6VE=


M;F]W+"!P=7-H('1H92!L87)G97-T('-U8BUA<G)A>0T*("  ("  ("  ("  
M("!I9BAJ("T 8F%S92 ^(&QI;6ET("T :2D-"B  ("  ("  ("  ("  >PT*
M("  ("  ("  ("  ("  ("  =&]P6S!=(#T 8F%S93L-"B  ("  ("  ("  


M("  ("  ("  ("  >PT*("  ("  ("  ("  ("  ("  =&]P6S!=(#T :3L-
M"B  ("  ("  ("  ("  ("  ('1O<%LQ72 ](&QI;6ET.PT*("  ("  ("  
M("  ("  ("  ;&EM:70 (#T :CL-"B  ("  ("  ("  ("  ?0T*("  ("  

M90T*("  ("  ("  ('L-"B  ("  ("  ("  ("  +R\ =&AE('-U8BUA<G)A
M>2!I<R!S;6%L;"P <&5R9F]R;2!I;G-E<G1I;VX <V]R= T*("  ("  ("  
M("  ("!J(#T
M("  ("  ("  ("  (&9O<B [(&D /"!L:6UI=#L :B ](&DL(&DK*RD-"B  
M("  ("  ("  ("  >PT*("  ("  ("  ("  ("  ("  9F]R*#L 8VUP*&%R

M('L-"B  ("  ("  ("  ("  ("  ("  ("!S=V%P*&%R<EMJ("L ,5TL87)R
M6VI=*3L-"B  ("  ("  ("  ("  ("  ("  ("!I9BAJ(#T
M("  ("  ("  ("  ("  ("  ("  ("  (&)R96%K.PT*("  ("  ("  ("  



M73L-"B  ("  ("  ("  ("  ("  (&QI;6ET(#T =&]P6S%=.PT*("  ("  


M;G0 8VUP:2AI;B!I;G0 :3$L:6X :6YT(&DR*2![(')E='5R;B!I,2 M(&DR



M:"AI;F]U="!I;G0 93L 87)R*0T*"0EE(#T


M(&DQ+&EN="!I,BD >R!R971U<FX :3$ +2!I,CL ?2 I.PT*"0DO+V%R<BYS


M<T-O=6YT97(N:6YT97)V86Q?='EP92  ;7,Q(#T 8V]U;G1E<BYM:6QL:7-E
M8V]N9',H*3L-" T*"7=R:71E9B B=&EM92 ]("5D;7-<;B(L(&US,2 I.PT*
M"0T*"7=R:71E9B B=" ]("5D7&XB+"!A<G);,%T *3L-" EW<FET968H(G0 

`
end
Mar 08 2005
parent reply Ben Hinkle <Ben_member pathlink.com> writes:
I've attached simple template (with example)

template sort(T)
{
  void sort(T[] arr, int function(in T l, in T r) cmp) {...}
}

used as:

int arr[] = new int[10000];
sort!(int) ( arr,   function int(int i1,int i2) { return i1 - i2; }    );

It is simple and works *30% faster* than D builtin sort. Walter, please, pay 
attention - C standard qsort is a piece of...


I could see having the generic array.sort use TypeInfo and its opCmp and have a
templated sort in Phobos for those cases when people want a sort that can be
optimized for their type (where the comparison function is specified some other
way than through the TypeInfo - either explicitly at the call site as you do
here or through opCmp operator lookup).

Keeping an API where users don't have to know about templates would be nice
since templates are an advanced maneuver.
Mar 09 2005
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
Ben Hinkle wrote:
<snip>

 int arr[] = new int[10000];
 sort!(int) ( arr,   function int(int i1,int i2) { return i1 - i2; }    );

 It is simple and works *30% faster* than D builtin sort.




By a direct translation of the DMD algorithm, or by coding up a better 
sorting algorithm altogether?


 Walter, please, pay attention - C standard qsort is a piece of...




That won't work if two elements of the array can differ by more than 
2147483647.  This used to be a bug with the TypeInfo for int and uint.

But your idea is like one I've had for ages.  Isn't it silly if a given 
D compiler has a state-of-the-art sort implementation but you can't use 
it, because you want to sort by something other than the type's natural 
ordering?

We could have, on every T[], a built-in method .sort(int function(T, T)) 
which would sort using the given function as a comparator.  And it could 
be overloaded so it can take either a function or a delegate - this 
would enable the comparator to be parameterised, and might be useful for 
database apps.

Your code would become

     arr.sort(function int(int i1, int i2) { return i1 - i2; });

Of course,

     arr.sort;

by itself would remain to denote sorting by the natural ordering.


 I could see having the generic array.sort use TypeInfo and its opCmp and have a
 templated sort in Phobos for those cases when people want a sort that can be
 optimized for their type (where the comparison function is specified some other
 way than through the TypeInfo - either explicitly at the call site as you do
 here or through opCmp operator lookup).


<snip>

Why not have opCmp operator lookup as the behaviour of the built-in one?

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
Mar 09 2005
next sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
 But your idea is like one I've had for ages.  Isn't it silly if a given D 
 compiler has a state-of-the-art sort implementation but you can't use it, 
 because you want to sort by something other than the type's natural 
 ordering?


My point is simple.
Existing arr.sort works now (could work better in terms of speed though)
and for simple cases, small arrays and atomic types it is pretty handy.

For other cases anyone can use given template or the like.
I just don't understand the problem.

Andrew.
Mar 09 2005
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Andrew Fedoniouk" <news terrainformatica.com> wrote in message 
news:d0n64j$2i1u$1 digitaldaemon.com...

 But your idea is like one I've had for ages.  Isn't it silly if a given D 
 compiler has a state-of-the-art sort implementation but you can't use it, 
 because you want to sort by something other than the type's natural 
 ordering?


 My point is simple.
 Existing arr.sort works now (could work better in terms of speed though)
 and for simple cases, small arrays and atomic types it is pretty handy.

 For other cases anyone can use given template or the like.
 I just don't understand the problem.

 Andrew.


I just pasted your template into std.array and recompiled phobos. I took 
your main() example and stuck in
  import std.array;
and compiled (with -O -inline -release) and viola everything works great. 
The only downside is that phobos isn't build with debug information so when 
I try to compile my example with debug info I get the following link error:
 Error 42: Symbol Undefined _array_3std5array
So if Walter were really going to put a template into phobos he would either 
have to have debug and non-debug builds of phobos or he'd have to figure out 
a way around that link error.
For those who haven't poked around with Andrew's attached code the actual 
sort call looks like
  int[] arr;
  ...
  sort!(int)(arr, function int(int i1,int i2) { return i1 - i2; } );

nice!

-Ben
Mar 09 2005
parent "Andrew Fedoniouk" <news terrainformatica.com> writes:
  int[] arr;
  ...
  sort!(int)(arr, function int(int i1,int i2) { return i1 - i2; } );

 nice!


Yep, exactly. This is the case when templates work.

Out of scope, IMO: boost (and STL at some extent) are too generic to be 
practicaly
useful. Even basic stuff - I did by myself full implementation of custom
iterator, to use it once or twice - titanic job with zero result 
practically.
onApply way better. One simple function. Little bit "enigmatic" but works.
Mar 09 2005
prev sibling parent "Ben Hinkle" <bhinkle mathworks.com> writes:
 We could have, on every T[], a built-in method .sort(int function(T, T)) 
 which would sort using the given function as a comparator.  And it could 
 be overloaded so it can take either a function or a delegate - this would 
 enable the comparator to be parameterised, and might be useful for 
 database apps.

 Your code would become
     arr.sort(function int(int i1, int i2) { return i1 - i2; });
 Of course,
     arr.sort;
 by itself would remain to denote sorting by the natural ordering.


That would be fine, too. I have no problems with that - though I haven't any 
idea how easy it would be for Walter to do.


 I could see having the generic array.sort use TypeInfo and its opCmp and 
 have a
 templated sort in Phobos for those cases when people want a sort that can 
 be
 optimized for their type (where the comparison function is specified some 
 other
 way than through the TypeInfo - either explicitly at the call site as you 
 do
 here or through opCmp operator lookup).


 <snip>

 Why not have opCmp operator lookup as the behaviour of the built-in one?


I don't have any problem with that, either. One advantage I see of the 
current impl is that the sorting routine is a single routine which cuts down 
on code duplication. The TypeInfo factors out the type-specific pieces of 
the sorting algorithm. Having the compiler make custom sorting routines per 
invocation using either template expansion or something would be fine but 
it's a trade-off decision Walter has to make. Until Walter decides on a 
standard way of supplying a comparison fcn, though, Andrew's template will 
do nicely. I'm sure other people have posted similar things. Maybe Walter 
will end up extending the sort property on arrays, maybe he'll toss 
TypeInfos entirely and go with templates, maybe he'll keep TypeInfos and use 
templates for custom sorting. Who knows :-)
Mar 09 2005
prev sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
Matthew wrote:
<snip>

 Since AAs are built-in, why on earth do they need to rely on runtime 
 polymorphism. Given the classes X and Y
 
 class X
 {
 }
 
 class Y
 {
     int opCmp(Y rhs);
 }
 
 What prevents the compiler from generating sorting based on arbitrary 
 difference (e.g. address of instance) for X, and using the 
 *non-polymorphic* Y::opCmp(Y) ?? (I know all methods are polymorphic in 
 D, but


What would be the purpose of making address of instance the default 
sorting key?  Surely sorting an array of X would be a compiler error.


2. "How else can an array of objects be sorted?"


 
 Why should an array of arbitrary types be sortable??


<snip>

That's exactly my point.  It makes no sense.

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
Mar 09 2005
parent reply "Matthew" <admin stlsoft.dot.dot.dot.dot.org> writes:
"Stewart Gordon" <smjg_1998 yahoo.com> wrote in message 
news:d0mhe2$1rsr$1 digitaldaemon.com...

 Matthew wrote:
 <snip>

 Since AAs are built-in, why on earth do they need to rely on runtime 
 polymorphism. Given the classes X and Y

 class X
 {
 }

 class Y
 {
     int opCmp(Y rhs);
 }

 What prevents the compiler from generating sorting based on arbitrary 
 difference (e.g. address of instance) for X, and using the 
 *non-polymorphic* Y::opCmp(Y) ?? (I know all methods are polymorphic 
 in D, but


 What would be the purpose of making address of instance the default 
 sorting key?  Surely sorting an array of X would be a compiler error.


For AAs, not for arrays. Sorting an array of X would be a compiler 
error.


2. "How else can an array of objects be sorted?"


 Why should an array of arbitrary types be sortable??


 <snip>

 That's exactly my point.  It makes no sense.


Mine too. :-)
Mar 09 2005
parent Stewart Gordon <smjg_1998 yahoo.com> writes:
Matthew wrote:
<snip>

What prevents the compiler from generating sorting based on arbitrary 
difference (e.g. address of instance) for X, and using the 
*non-polymorphic* Y::opCmp(Y) ?? (I know all methods are polymorphic 
in D, but


 What would be the purpose of making address of instance the default 
 sorting key?  Surely sorting an array of X would be a compiler error.


 
 For AAs, not for arrays.


<snip>

This applies here as well:

http://www.digitalmars.com/d/garbage.html

"Depending on the ordering of pointers:

	if (p1 < p2)		// error: undefined behavior
	    ...
	
since, again, the garbage collector can move objects around in memory."

Logically, it would hook up an AA implementation that doesn't rely on an 
ordering.

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
Mar 09 2005