View mode: basic / threaded / horizontal-split · Log in · Help
April 18, 2008
Re: A Fresh Look at Comparisons, Take 2
Janice Caron Wrote:

> On 18/04/2008, Jason House <jason.james.house@gmail.com> wrote:
> >  I'm sure you could say that foo must now declare its parameters as explicit, but requiring all functions that compare A's to have explicit parameters really starts to kill the whole utility of having a base class to begin with.
> 
> That's a good point, but again, nothing /requires/ explicit
> parameters. It's like anything else - if you desire the behavior, use
> it; if you don't, don't.
> 
> But that is a very good observation, yes. Well spotted.

That's not the only problem, just an example.  The types of problems are the same as virtual functions vs. non-virtual functions.  I think that if you can't rework the proposal to remove the use of "explicit", then there are likely going to be gotchas floating around somewhere.

It seems like proper execution of comparison operators is a lot like the double dispatch problem http://en.wikipedia.org/wiki/Double_dispatch
April 18, 2008
Re: A Fresh Look at Comparisons, Take 2
"Yigal Chripun" wrote
> Steven Schveighoffer wrote:
>> Huh?  I think maybe you meant C to inherit from B?  If so I see what you 
>> are
>> trying to explain :)
>>
>> I don't really agree that opEquals or opCmp should not be inherited.  I
>> think normal inheritance the way it is now is just fine.
>>
> as Janice showed and I completely agree with her, this is a bad default.
> We are talking about the D default behavior here and it can be
> overridden. The programmer can define an opCmp that is not explicit and
> than all derived classes will inherit that opCmp as well, so your
> desired behavior is still available, it's just not the default anymore.

I think the whole goal of this exercise is to avoid having to take 'Object' 
as the parameter to opCmp and opEquals.

Why can't one just provide opCmp(MySpecificClass) as an overload to opCmp? 
If the compiler sees it at compile time, it calls the more specific one.

Maybe in that case, the default opCmp in Object can do the casting for you:

int opCmp(Object o)
{
  /* search through vtable for opCmp that takes most derived compatible 
type, call it with o*/
  /* if no such function exists, throw exception */
}

If you want to define a more efficient opCmp, then override opCmp(Object o) 
that will call just the functions you want.  It's not any different than 
today.

I don't know how one would write this in D directly, but it could 
theoretically be done.

Adding a new 'explicit' keyword may also solve this problem, but it also 
appears to introduce a lot of other problems that I don't think we want to 
have.

>> You need to have opEquals in Object in order to support hashing.
>>
> I'm not sure I fully understand you on this. the suggestion states that
> unless opEquals is defined, the compiler defaults to identity
> comparison.  This is equivalent to having an opEquals in Object that
> does the same thing (which is the current implementation, I think). I
> don't care if it's implemented inside the compiler, or via opEquals in
> Object, what's important is the semantics. i.e. unless there's a user
> defined opCmp for a class, (a == b) will be true iff (a is b) is true [
> for two instances a and b of that class].

"unless opEquals is defined, the compiler defaults to identity comparison."

This is the current implementation.  I'm not sure why we need special 
handling of it.

>> The default opCmp should be redefined to throw an exception.  An 
>> alternative
>> is that opCmp is defined in an interface.  Or you could do both.  The
>> rationale is that opCmp doesn't have a default.  Some objects just cannot 
>> be
>> expected to have a well-defined order.
>>
>> -Steve
>>
>>
>>
> since D is relatively a new language, we can benefit by learning from
> previous design errors in similar languages. Java implements that idea
> of a method in Object that throw by default and that proved to be a very
> fragile design. Object should provide only the methods that all objects
> contain, and since not all classes are fully ordered, opCmp should not
> be in Object.
> I agree with you that providing a "Comparable" interface is a good
> design. If D was only OOP like java, than this would have been my
> favorite solution. indeed, Java contains such an interface and you are
> expected to implement it if your class is comparable. if i remember
> correctly, there are two interfaces in Java which facilitate the subtle
> difference between an opEquals and opCmp comparison.
> as Janice said, this interface is not strictly necessary with her
> proposal, however such an interface can help document the fact that a
> class is comparable, so it still could be added.

My preference is the interface.  But I'm willing to accept an 'exception 
throwing' default (or the 'find the right overload' default as defined 
above) if that is what Walter wants.  This is all I'm saying.

-Steve
April 18, 2008
Re: A Fresh Look at Comparisons, Take 2
"Janice Caron" wrote
> On 18/04/2008, Steven Schveighoffer wrote:
>>  >>  >>  You need to have opEquals in Object in order to support hashing.
>>> > Please could you elaborate, as I don't understand why this is so?
>> ...
>>  It is not necessary in Object
>
> Ah! That would explain why I didn't understand why it was so! :-)
>
> I am confused about one point though. I know that one can implement an
> AA using hashing. I also know that one can implement an AA using
> comparison. However, it seems to me that one does not need /both/. How
> are D AA's implemented - do they use hashing, or do they use
> comparison? And why do the docs say we need both?

That is a good question...

I assume that one should override both opEquals and opCmp because if one 
doesn't, then if opCmp(x) == 0 can return different results than 
opEquals(x).

I'm guessing that the buckets of the hash are somehow sorted lists, maybe 
they are RB trees (that seems terribly inefficient) or just sorted arrays? 
I have no idea.  But strictly speaking, opCmp is not required for a basic 
hash implementation.  only opEquals to see if you got the right element or 
not.

I'd be interested to know why opCmp is required.

-steve
April 19, 2008
Re: A Fresh Look at Comparisons, Take 2
Janice Caron wrote:
> On 18/04/2008, Yigal Chripun <yigal100@gmail.com> wrote:
>>  may I ask you to please
>>  add this suggestion to there as an enhancement request
> 
> Not yet. I'm not sure there's a consensus at this stage. I tend to
> throw idea out and see how well they float, and there may be problems
> no one's thought of yet. Let's wait and see how it pans out. But yeah
> - if it pans out, I can do that eventually.

The discussion has gone back and forth so much that if you do get 
consensus it's likely to be a consensus of 2 or 3 people.  If you want a 
wider audience I suggest writing up the proposal in its final form.

This is not only relevant for this particular thread, but in general if 
you want to get consensus on these long threads, then you should 
condense the contents down and make an official proposal out of it.

Perhaps you might find these guidelines from Python PEP process useful:
http://www.python.org/dev/peps/pep-0001/#what-belongs-in-a-successful-pep

Not many people are going to read a big long thread to try to piece 
together what the proposal actually is.  Especially the one person who 
really matters here, Walter.  So if you think it's a super idea then you 
should write it up in a condensed format.  For now you can post it to 
the NG.  Or on a wiki page somewhere.  Anything that gives the proposal 
a specific single-page URL for future reference instead of "check out 
this thread".

Just the 2c of someone who, like Walter, is not likely to re-read the 
entirety of this thread to see if he agrees or not.

--bb
April 19, 2008
Re: A Fresh Look at Comparisons, Take 2
On 19/04/2008, Bill Baxter <dnewsgroup@billbaxter.com> wrote:
>  Not many people are going to read a big long thread to try to piece
> together what the proposal actually is.  Especially the one person who
> really matters here, Walter.

I get that, but the trouble is, even /I/ don't think it's a great idea
at this stage, despite the fact that I suggested it. Partly, that's
because it's ugly. You have to admit that

   struct S
   {
       explicit bool opEquals(explicit ref const(S) s) const {...}
       explicit int opCmp(explicit ref const(S) s) const {...}
   }

is not terrifically "friendly" looking. But the /main/ thing that
concerns me is that two posters have pointed out that static-typing
isn't good enough. That means, you need run-time typing, and that, in
turn, means you need double-dispatch (or multimethods), which in turn
means it just plain won't work with the suggested syntax.

The simplest workarounds are, in fact /current D/. The simplest
workaround for inheritance is to supply a function which throws an
exception; the simplest workaround for double-dispatch is to accept an
Object parameter and do all the tests at run-time.

The things that people /really/ care about (e.g. that opEquals should
return bool, that opEquals and opCmp should be const) have already
been complained about in bugzilla.

In summary, enough objections to the other stuff have been brought up
on this thread to make me think it's not workable. At least, not yet.
In order to be workable, we must first solve (1) annotations, and (2)
multiple dispatch. And those are separate subjects.


> So if you think it's a super idea then you
> should write it up in a condensed format.

Of course. But I don't any more, and I wouldn't have learned that if
we hadn't discussed it here first.
April 19, 2008
Re: A Fresh Look at Comparisons, Take 2
"Janice Caron" <caron800@googlemail.com> wrote:
> On 18/04/2008, Henning Hasemann <hhasemann@web.de> wrote:
> >  - You can still not build partially ordered classes at all? (Ie
> >   something similar to complex numbers) Is there a rationale for
> > this?
> 
> Only that Paul said it wasn't necessary, and, on reflection, his logic
> is reasonable.
> 
> Basically, I think the reasoning is... what's the point? After all, if
> c and d are complex numbers, then
> 
>     if (c < d)
> 
> could easily be rewritten as
> 
>     if (c.im == 0 && d.im == 0 && c.re < d.re)

so 2i >= 5 would hold?
The point is that you might want to create structures that are more
complex and not that linear ordered. Think of sets or something.
Naturally one can get around this by building up just "normal methods"
for comparsion, but there might be casess where its just more beautiful
to do it with comparsion operators.

> >  - You can still have opCmp say two objects are equal and opEqual
> > say they're not? (or vice versa, respectively)
> 
> Sure. You can also define opAdd() to do subtraction. Sometimes, you
> just have to rely on common sense.

Sure but then a + b is (for a and b always your type) always
substraction. I don't really see a problem in that you can do stuff
which doesnt make much sense, I just want to say that this shows that
the current notation is not only redundant (regarding ==) but also not
as powerful as it could be (regarding partial ordering).

> (Also, there are rare circumstances where you might want to do that
> deliberately, so that, for example, an AA can contain duplicate
> "equal" keys).

Well I think circumstances where you want partial ordering are more
common ;)

Henning

-- 
GPG Public Key:
http://pgpkeys.pca.dfn.de/pks/lookup?op=get&search=0xDDD6D36D41911851
April 19, 2008
Re: A Fresh Look at Comparisons, Take 2
On 19/04/2008, Henning Hasemann <hhasemann@web.de> wrote:
>  >     if (c.im == 0 && d.im == 0 && c.re < d.re)
>
> so 2i >= 5 would hold?

No. That assertion is false.

   2i < 5 is false
   2i == 5 is false
   2i > 5 is false

In general, for complex c and d, if you want to less for >=, you would do

   if (c.im == 0 && d.im == 0 && c.re >= d.re)

Basically the rule is, if both numbers are not completely real, then
they are not comparable, and > and < will both always yield false.
(And I'm talking math here - implementation in a programming language
might be different - e.g. you might throw an exception instead of
returning false, or you might decide to make them incomparable
regardless of the real subset).


>  The point is that you might want to create structures that are more
>  complex and not that linear ordered.

I assume you mean "partially ordered"?

Yes, that's true. But remember, partially ordered types cannot be used
as AA keys (at least, not if the AA is implemented as a binary tree
with total ordering), so we've got a problem right there. How do we
tell AAs "Yes, we've implemented opCmp(), but you're not allowed to
use it because it's partial"?
April 19, 2008
Re: A Fresh Look at Comparisons, Take 2
Bill Baxter wrote:
> <snip>
> This is not only relevant for this particular thread, but in general
> if you want to get consensus on these long threads, then you should
> condense the contents down and make an official proposal out of it.
>
> Perhaps you might find these guidelines from Python PEP process useful:
> http://www.python.org/dev/peps/pep-0001/#what-belongs-in-a-successful-pep
>
> </snip>
That's a superb idea, and I think D needs a similar process to Python's
PEPs. D needs an official place on its website where proposals can be
added and managed. Also, a similar concept is present in other languages
as well - Java for example.

-- Yigal
April 19, 2008
Re: A Fresh Look at Comparisons, Take 2
Janice Caron wrote:
> On 19/04/2008, Bill Baxter <dnewsgroup@billbaxter.com> wrote:
>>  Not many people are going to read a big long thread to try to piece
>> together what the proposal actually is.  Especially the one person who
>> really matters here, Walter.
> 
> I get that, but the trouble is, even /I/ don't think it's a great idea
> at this stage, despite the fact that I suggested it. 

Ah, ok.  I wasn't getting that.   Don't mind me, then.

--bb
April 19, 2008
Re: A Fresh Look at Comparisons, Take 2
> Yes, that's true. But remember, partially ordered types cannot be used
> as AA keys (at least, not if the AA is implemented as a binary tree
> with total ordering), so we've got a problem right there. How do we
> tell AAs "Yes, we've implemented opCmp(), but you're not allowed to
> use it because it's partial"?

By using a syntax different to opCmp ;)

-- 
GPG Public Key:
http://pgpkeys.pca.dfn.de/pks/lookup?op=get&search=0xDDD6D36D41911851
1 2 3 4
Top | Discussion index | About this forum | D home