Re: LSP and Equal()......

From: Dmitry A. Kazakov (mailbox_at_dmitry-kazakov.de)
Date: 06/16/04 

Date: Wed, 16 Jun 2004 15:36:25 +0200

On 16 Jun 2004 02:30:52 -0700, Nicholls.Mark@mtvne.com (Mark Nicholls)
wrote:

>> >You need to define dispatching...I'm loosing it.
>>
>> Dispatching = run-time polymorphism. A subroutine is dispatching in a
>> parameter if it has many implementations of the body. The types of the
>> actual parameters (tags) determine a body to select, when the
>> subroutine is called.
>>
>> For example virtual functions of C++ are dispatching in the first
>> parameter. The dispatching table in C++ is called vtable. Type tags in
>> C++ are stored in objects and usually are pointers to vtable.
>
>OK, I am familiar with v-tables.
>
>>
>> >> > I think if you have symetry and transitivity for a relation R (and
>> >> > LSP) then basically it means the 'extension' of S to T can have no
>> >> > bearing on it's outcome. So S == T (or at least homomorphic) i.e.
>> >>
>> >> See my comment above. The relation R is not defined on Point.
>> >> Mathematically, equality is something that satisfies a definite set of
>> >> axioms. That is the contract. It tells nothing about concrete types.
>> >
>> >Mathematically, equality is something that satisfies a definite set of
>> >axioms - yes, it is not defined in isolation, it is an operator that
>> >has to be defined on a set, if you change the set, you change the
>> >meaning.
>> >
>> >i.e. like my previous example.
>> >
>> >4.5 == 3 * 1.5
>> >
>> >If my set are the reals and my equals is defined on that set in the
>> >normal way then this is meaningful. If my equals is defined on the
>> >integers then this becomes meaningless - the equals are *not* the
>> >same, I can create an injective mapping between operators from the
>> >real equals to the integer equals but *not* backwards.
>>
>> First of all, you should clarify whether the domain set of Integer is
>> a subset of the domain set of Real. Because you are [correctly]
>> talking about mappings, we are in agreement that they are not same.
>> Thus == of Reals is *not* applicable to Integer, never. See?
>>
>
>This is a problem I have with (most people interpretation of) OO, in
>maths the integers are NOT a subset of the reals! there is a mapping
>into the reals but they are not the same set. OO does this IS-A thing
>and people talk about sets theory BUT as soon as they do that they are
>doing something strange to the interpretation of the
>methods/operators.

What is worse is that what they mean is not "x IS-A y", but actually
"the thery of x IS-A theory of y".

>Maybe this is what you mean by dispatching in the parameter i.e. the
>interpretaion of which == to choose.

It is about avioding sloppy OO terms. I'll try explain it more
detailed. Each object has *a* type. Each subroutine is defined on *a*
type [in one parameter] in the sense that it accepts actuals of the
given type. Period.

Now what to do with polymorphic subroutines which seem to be defined
on many different types [in one parameter]? Well, they are not. They
are still defined on one exact type. It works as follows, for any type
T there is a type T'Class which values are constructed from the values
of T and all its descendants. Each such value consists of the value of
a specific type (T or its descendant S) + the tag indicating that type
(In C++ the tag is burried in any T anyway, but there could be better
approaches). Now a polymorphic operation is defined on T'Class. When
called it looks at the actual type tag (or many tags in case of
multiple dispatch = many dispatching parameters) and then selects an
appropriate implementation of the body according to it. That is what
dispatching formally is.

So you have a choice, either you define Equality on T or on T'Class.
In the latter case the contract of Equality cannot be expressed in
terms of T. The operation is not defined on T!

>> What the compiler does when Integer *inherits* equality from Real is
>> defining it for Integer as a composition:
>>
>> Real.Equality o Convert_Integer_To_Real
>
>OK, I agree this is the explicit mapping.
>
>> Yes, you cannot define an equality for Reals this way when you
>> *inherit* it from Integer. So what? You can override it then. This is
>> why == should be dispatching.
>
>"== should be dispatching" I still don't understand what you mean by
>this, even though I did understand what you meant above.
>
>if I have a a real and b and integer.
>
>a.Equals(b) does actually call a diferent method to b.Equals(a).....

Why should it? Probably you mean C++:

class Integer
{
public :
   virtual bool Equal (const Integer Right) const;
};

In the terms I gave above it means that Equal is defined as:

Equal : Integer'Class x Integer -> bool

That obviously contradicts to mathematical meaning of equality, which
is symmetric. So it cannot be implemented consistently.

>thus isn't Equals dispatching?

It is not dispatching in the parameter Right. A correct definition
should be:

Equal : Integer'Class x Integer'Class -> bool

>(I'd rather talk about methods than operators in the OO sense as it's
>easier to agree whats going on).

Methods = dispatching subroutines.
Operators = subroutines with comic names like +,-, etc (:-)) allowing
using in infix expressions.
 
>> >*It tells nothing about concrete types.*
>> >
>> >!!, but my concrete types are constrained by their common supertype.
>>
>> That would be an abstract type Comparable or Point'Class, but not
>> plain Point.
>
>I also find this "Point'Class" thing confusing....

We shall separate T and a closure of its descendants (T'Class) to
reach firm ground.

>I generally work in concrete classes and interfaces (i.e. completely
>abstract), if we talk about abstract classes in general it will muddy
>the waters...so....
>
>I am saying there is a method Equals on the polymorphic interface
>IPoint that has a contract that defines the constraints by which all
>classes that implement that interface must obey. i.e.
>
>interface IPoint
>{
>single GetX();
>single GetY();
>bool Equals(IPoint); // contract - return false if x!=x or y!=y

That is not a mathematical equality, which contract could be:

"whathever parts compared objects have, equality of them is eqivalent
(<=>) to equality the objects."

[ The word "whatever" implies T'Class. You do not know which they are
and specific T cannot help here. ]

Further in this case there is no need to make Equals a method of
IPoint. The contract as stated allows a direct implementation of
Equals in terms of IPoint'Class:

bool Equals (const IPoint& Left, const IPoint& Right)
{
   return Left.GetX() == Right.GetX() && Left.GetY() == Right.GetY();
}

This is a "class-wide" subroutine. It has one body for all descendants
of IPoint. It is not a method it is not dispatching and it cannot
violate LSP.

>> >If we're talking 2D points, I can define 2 concrete implementations of
>> >this i.e. cartesian and polar BUT they are both constrained by the
>> >constraints I apply to Point i.e. that of cartesian geometry.
>>
>> But cartesian geometry does not define the meaning of equality.
>> Mathematically there is one supertype more.
>
>OK...
>I am defining a new space NichollsianGeometry that is isomorphic to
>cartesian geometry and has a new operator Equals....
>
>I don't see what the problem is, we do this all the time in OO and all
>the time in maths as long as the new operator doesn't contradict any
>of axioms of Cartesian geometry there should be no objection.
>
>I now formally define this binary operator
>
>NichollsianGeometry.Equals(a,b)
>true: a.x == b.x and a.y == b.y
>false: else
>
>This is perfectly valid mathematics.

You have not specified the types involved, so it is not clear which
components have a and b. Do you want to make it dependent on the
number of components? After all, why not:

MyGeometry.Equals(a,b)
true: &a == &b
false: else

>> >This seems to be the point, now if I define a ColouredPoint my
>> >constraints on Point define how ColouredPoint.Equals behaves and this
>> >brings about the problem that I cannot consider colour sensibly or I
>> >must define Equals to mean ...return false if a.x!=b.x and b.y!=b.y
>> >(thanks to Daniel T),
>>
>> I should repeat it again. The contract of mathematical equality cannot
>> be defined in the terms of the base type. Probably you are trying to
>> define something else...
>
>I have defined my operator on the base type - it may well be a
>definition that causes all sorts of problems but I see no problem.

The problem is that you have defined it on (in terms of) the base
type. This automatically excludes adding any new components when the
components are part of the contract (visible, accessible etc).

>> >I cannot absolutely specify when it should
>> >return true without making ColouredPoint breach LSP if it considers
>> >colour.
>>
>> It is much worse than you think! (:-)) Actually [absolute] LSP
>
>You've inserted the word absolute - I was talking about behaviour as
>defined by the definition, not the implementation.

Right, we have to specify it more precisely: anything that is not
private is a contract.

>If you use a method rather than an operator it is clear which equals
>method should be used.

But that contradicts to even more fundamental thing: equality is a
dyadic operation. It cannot have only one argument.

>You could define Equals to be an operator and double dispatch the
>operator on the Points....but thats a different question.....it would
>seem if the example were
>
>interface INichollsianPoint // as cartesian but with Equality
>{
>single GetX();
>single GetY();
>bool Equsls(NichollsianPoint); // true if X==X and Y==Y else false
>}
>class PolarPointImplementation : INichollsianPoint
>{
> bool Equsls(NichollsianPoint p)
> {
> return ((this.GetX() == p.GetX()) && (this.GetY() == p.GetY()))
> }
>}
>class CartesianPointImplementation : INichollsianPoint
>{
> bool Equsls(NichollsianPoint p)
> {
> return ((this.GetX() == p.GetX()) && (this.GetY() == p.GetY()))
> }
>}
>Why would I double dispatch?

Because GetX and GetY for a polar representation might be troublesome,
so Equals will be less efficient and less precise.

>The implementation are identical, they simply define different
>implementation of exactly the same thing i.e. like 3*4 and 2*6 being
>different implementations of 12.

They are not, if you don't mean some sort of symbolic evaluation, like
Evaluate ("3*4"). In this case "3`*4" and "2*6" are indeed two
different representations of an integer. BTW, would Equal inherited
from String work properly? (:-))
 
>> How a concrete language support this or not, is not a LSP problem. If
>> you know Ada, here is an implementation of double-dispatching
>> equality: http://www.dmitry-kazakov.de/ada/components.htm
>
>I am a big visitor fan and I can see there may well be an application
>for double dispatching such operators to supply and implicit mapping
>between domains where there does exist a meaningful mapping from one
>to the other and you want the operator to be symetric (by mapping to
>the common base of both types)...if you want your operator to be
>transitive as well, you get....
>
>P(0,0) == P(0,0,Red) and P(0,0) == P(0,0,Blue) so P(0,0,Blue) ==
>P(0,0,Red)

Or else P(0,0) != P(0,0,Red). 

--
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Relevant Pages

  • Re: LSP and Equal()......
    ... >> I would rather consider any mappings and exclude any semantics ... >> Equals. ... In Ada it will not dispatch. ... Integer as the contract tells. ...
    (comp.object)
  • Re: LSP and Equal()......
    ... > By contract, I mean the guarantee that the method provides. ... Though can I just note wrt to Equals you go on to say almost by (and ... sensible) definition Equals in this context breaks LSP, ... it checks GetType is beside the point - I find this worrying, if LSP ...
    (comp.object)
  • Re: collection framework: using the good interface
    ... The word object's class would implement Comparable, and should have equals and hashCode consistent with compareTo, but I would not make two words equal unless they are, in all respects, the same word. ... I'm more and more convinced that equality should involve all aspects of the Word class, but I'm still uncomfortable with mixing lexicographic information (allowing to compare objects in different collections) and information about frequency, distribution, cooccurrents. ...
    (comp.lang.java.help)
  • Re: Bruijn babbles bullshit
    ... error allowed in equality". ... Is there a BEST 'like' and can it be identified with common equality? ... to agree with Brouwer's Continuity Theorem. ... only the "best like = equals" has been programmed in the end. ...
    (sci.math)
  • Re: ArrayList.contains()
    ... at least one instance variable in a class, you can define an equality relation based on the field values. ... statefulness is not required -- an equality relation based on field values is trivial if there aren't any such values. ... I don't see equals() having any bearing on searching for objects in a DB, ... For one thing, it produces an inheritance problem: if you override equals() on class A in the manner you describe, then no subclass of A can add instance variables, implement your approach to equals, and also retain the symmetric nature that equalsis supposed to have. ...
    (comp.lang.java.programmer)