• Stewart Gordon (34/34) Jul 05 2004 I seem to have found the underlying cause of the failures of sort and
• Ivan Senji (3/37) Jul 05 2004 I want to be unable to compare uncomparable objects too!
• Ben Hinkle (25/62) Jul 05 2004 Not a bad idea.

Stewart Gordon <smjg_1998 yahoo.com> writes:

I seem to have found the underlying cause of the failures of sort and 
associative arrays to work 'properly' with struct or class types.

Currently, the implementations are rather down and dirty, and rely on 
TypeInfo.  The problems with it are:
- no TypeInfo is automatically generated for struct types, leading to 
the linker errors
- class types just use the functions of TypeInfo_C, which in turn use 
Object.opEquals(Object) and Object.opCmp(Object) rather than 
self-specific versions.

But for any type, the behaviour of sort and AAs ought to be consistent 
with the behaviour of the comparison operators, at least whenever the 
types involved are the same.

I therefore suggest that we do away with the current implementations 
using TypeInfo and rewrite them to use templates.  This should be easy 
to do, as it only means translating existing algorithms into the D 
template system.  This means that we can use the type's comparison 
operators directly, and so the correct comparison is always carried out.

This raises a few questions.  When this is done, how much of TypeInfo is 
really still needed?  The very fact that sort and AAs are currently 
implemented in terms of TypeInfo seems to reflect the fact (?) that 
templates were a more recent addition to the language.  Obviously we 
still need TypeInfo itself for such things as typeid and hence variadic 
functions.  But can we sensibly deprecate (if not remove) 
TypeInfo.equals and TypeInfo.compare?

This would enable us to deprecate the Object.opCmp(Object) wart, and 
then to hook up separate AA implementations for comparable and 
non-comparable key types.  It would also enable the compiler to catch 
attempts to compare incomparable objects, something that C++ manages 
without difficulty, and Java manages to an extent.

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the 
unfortunate victim of intensive mail-bombing at the moment.  Please keep 
replies on the 'group where everyone may benefit.

"Ivan Senji" <ivan.senji public.srce.hr> writes:

"Stewart Gordon" <smjg_1998 yahoo.com> wrote in message
news:ccbd2c$1m30$1 digitaldaemon.com...
 I seem to have found the underlying cause of the failures of sort and
 associative arrays to work 'properly' with struct or class types.

 Currently, the implementations are rather down and dirty, and rely on
 TypeInfo.  The problems with it are:
 - no TypeInfo is automatically generated for struct types, leading to
 the linker errors
 - class types just use the functions of TypeInfo_C, which in turn use
 Object.opEquals(Object) and Object.opCmp(Object) rather than
 self-specific versions.

 But for any type, the behaviour of sort and AAs ought to be consistent
 with the behaviour of the comparison operators, at least whenever the
 types involved are the same.

 I therefore suggest that we do away with the current implementations
 using TypeInfo and rewrite them to use templates.  This should be easy
 to do, as it only means translating existing algorithms into the D
 template system.  This means that we can use the type's comparison
 operators directly, and so the correct comparison is always carried out.

 This raises a few questions.  When this is done, how much of TypeInfo is
 really still needed?  The very fact that sort and AAs are currently
 implemented in terms of TypeInfo seems to reflect the fact (?) that
 templates were a more recent addition to the language.  Obviously we
 still need TypeInfo itself for such things as typeid and hence variadic
 functions.  But can we sensibly deprecate (if not remove)
 TypeInfo.equals and TypeInfo.compare?

 This would enable us to deprecate the Object.opCmp(Object) wart, and
 then to hook up separate AA implementations for comparable and
 non-comparable key types.  It would also enable the compiler to catch
 attempts to compare incomparable objects, something that C++ manages
 without difficulty, and Java manages to an extent.

I want to be unable to compare uncomparable objects too!

 Stewart.

 --
 My e-mail is valid but not my primary mailbox, aside from its being the
 unfortunate victim of intensive mail-bombing at the moment.  Please keep
 replies on the 'group where everyone may benefit.

Ben Hinkle <bhinkle4 juno.com> writes:

Stewart Gordon wrote:

 I seem to have found the underlying cause of the failures of sort and
 associative arrays to work 'properly' with struct or class types.
 
 Currently, the implementations are rather down and dirty, and rely on
 TypeInfo.  The problems with it are:
 - no TypeInfo is automatically generated for struct types, leading to
 the linker errors
 - class types just use the functions of TypeInfo_C, which in turn use
 Object.opEquals(Object) and Object.opCmp(Object) rather than
 self-specific versions.
 
 But for any type, the behaviour of sort and AAs ought to be consistent
 with the behaviour of the comparison operators, at least whenever the
 types involved are the same.
 
 I therefore suggest that we do away with the current implementations
 using TypeInfo and rewrite them to use templates.  This should be easy
 to do, as it only means translating existing algorithms into the D
 template system.  This means that we can use the type's comparison
 operators directly, and so the correct comparison is always carried out.
 
 This raises a few questions.  When this is done, how much of TypeInfo is
 really still needed?  The very fact that sort and AAs are currently
 implemented in terms of TypeInfo seems to reflect the fact (?) that
 templates were a more recent addition to the language.  Obviously we
 still need TypeInfo itself for such things as typeid and hence variadic
 functions.  But can we sensibly deprecate (if not remove)
 TypeInfo.equals and TypeInfo.compare?
 
 This would enable us to deprecate the Object.opCmp(Object) wart, and
 then to hook up separate AA implementations for comparable and
 non-comparable key types.  It would also enable the compiler to catch
 attempts to compare incomparable objects, something that C++ manages
 without difficulty, and Java manages to an extent.
 
 Stewart.
 


Not a bad idea. 
Off the top of my head one difference would be on code size - not that the
AA or sorting algorithms are very big. Is D (or the linker or whatever)
smart enough to use only one version of a template when the types are
reference types? One benefit of TypeInfo is that it factors out the
"dynamic" part of the algorithm nicely.
I wonder if there is a performance benefit to using templates, too, since
the hashing and comparisons can be inlined. 

So if I understand you correctly if Foo is some class then writing something
like

 int[Foo] x;
 x[y] = 10;

would translate to

 _AA!(int,Foo).T x;
 *(_AA!(int,Foo).get(x,y)) = 10;

where _AA is

 template _AA(Value_T, Key_T) {
   struct aaA { ... plug in aaA from src/phobos/internal/aaA.d }
   typedef aaA*[] T;
   Value_T* get(T x, Key_T y) {
     ... plug in code from src/phobos/internal/aaA.d 
         but replace calls to key TypeInfo with Key_T
   }
 }