Multiple dispatch and Symmetric methods - Where Does That Code Live?
Hi all.
I am stuck with the above problem, which looks to be a very common and fundamental one. Supposing I have some sort of relation or operation to be performed on various different pairs (or n-tuples) of classes of object. Where does this code belong, given that it is not sole property of any one of the classes, but a kind of property of the collection of classes?
An bad example for me to bring up, but one that neatly illustrates the point, is the equals method. In order to retain the symmetric and transitive properties of the equals method, and object can only make judgement calls about it being equal to another object of it's own type. This prevents the concept of equivalency from crossing between types.
In order to compare a with b (if a and b are of different types), b must supply some sort of representation of itself as an a, then the comparison statement a.equals(b.asA()); must be called.
This of course means b must supply an 'asXXX()' method for each class XXX it wishes to equate itself to. Furthermore, by an extension of the equals contract for symmetricality, the method AsB() in class A (if it exists) must be such that, if a.AsB() .equals (b), then b.AsA.equals( a ).
This sort of design is unfeasible for obvious reasons, the main reason being that it is impossible to anticipate evey case where an instance of class A could reasonably be compared to an instance of some other class X.
The other annoyance is all that hard work of providing methods to equate A with something else, would go unused for 99% of the time.
With this in mind, I was thinking. Suppose in some program environment, we have only 3 classes, A, B, and C, such that:
{A,B} can be meaningfully compared
{B, C} and {A, C} cannot.
It would be OK to supply code (somewhere) for comparing A's with B's. We also know that under no circumstances will an A or a B, and a C, ever need to be compared for equality.
Supposing an extension of this environment were created, introducing class D.
{D, A} and {D, B} can be meaningfully compared.
Now, neither A nor C knows what a D is, or how to compare themselves to it. But D was developed with A, B and C in mind, and contains logic for the various comparisons (with A and with B). An obvious idea for this is to let D bring it's new code into play, byregistering these new comparison functions in the environment somehow.
Supposing instead that equality comparison was delegated to some third party, instead. This third party contains a table of pairs of classes, which act as keys to look up a comparison object.
So, when class A is loaded, something of the sort happens:
publicclass A{
static{
Equals.comparer.addEntry(A.class, B.class,new EqualsMethod(){
// details of the EqualsMethod interface implementation go here
});
}
}
publicclass B{
static{
// since equals is symmetric, this method clashes with the above in A
// This could happen...
Equals.comparer.addEntry(B.class, A.class,new EqualsMethod(){
// ... different approach to the above
});
}
}
publicclass D{
static{
Equals.comparer.addEntry(D.class, A.class,new EqualsMethod(){
// ...
});
Equals.comparer.addEntry(D.class, B.class,new EqualsMethod(){
// ...
});
}// Ds can now be compared with Bs and As. They can now be compared with Ds
}
There is a problem with the above. As can clearly be seen, there are 3 unique situations that might occur between two classes (call them X and Y).
o One of X or Y contains code to compare them both.
o Neither X nor Y contain code to compare the two. X equals Y is always false
oBoth X and Y contain code to compare the two.
The third causes the problem. What if X and Y disagree on how to compare themselves? Which method gets chosen? The only solution would be to let whosever static initialiser gets called first be the one to supply the code.
I said before that equals was a bad example to bring up. this is because the usage of equals and the concept of equality in java is already well defined, and works just fine. However, in my own pet project at the moment, I have run into the same problems as outlined above.
I am currently assembling a generic pattern API for use in various other applications I am writing (I was finding that I was writing code for matching objects to patterns, in different guises, quite frequently, so I made the decision to refactor it into its own package). An important part of the API is the section that handles the logic for combining patterns, ie with AND, OR and NOT operations.
The Pattern interface is this:
interface Pattern<E>{
publicboolean match(E toMatch);
public Pattern<E> not();
public Pattern<E> or(Pattern<E> other);
public Pattern<E> and(Pattern<E> other);
}
There are a few basic Patterns:
TruePattern<E> - a pattern that always returns true no matter what E is passed for it toMatch
FalsePattern<E> - self-explanatory.
ExactValuePattern<E> - true if and only if the E that it is passed toMatch is .equal to the E that this pattern was constructed with.
NotPattern<E> - a pattern that contains another pattern, and returns true for any E that returns does not match it's contained pattern. Used for when the contained pattern cannot be logically reduced to one pattern under the NOT method in the Pattern interface
AndPattern<E> - a pattern that contains 2 other patterns, and returns true for some E iff both contained patterns return true for that E. Used for when the 2 patterns cannot be logically reduced into one pattern via the AND method in the Pattern interface
OrPattern<E> - self explanatory
RangePattern<E extends Comparable ><E>> - a pattern for comparing if some Comparable lies between two other comparables.
Every pattern has the opportunity to provide a reduction, when combined with another pattern through And or Or. For example, any pattern AND a FalsePattern can be reduced just the FalsePattern. any pattern OR a TruePattern can be reduced to just the TruePattern.
The methods AND and OR from the Pattern interface present the same problems as the .equals() example I was using before.
o AND and OR are symmetric operations
o There exist situations where two patterns of unrelated class could be meaningfully combined (and reduced) under these two operations.
Example: The pattern on Integers '0 < X < 3' and 'X is 5' can be reduce to the FalsePattern
Example: The pattern on Doubles '0 < X <= 10' or 'X is 5.5' or 'X is 7.2' can be reduced to '0 < X <= 10'.
Example: The pattern on Integers ('0 <= X <= 5' and 'X is not 0') or ('X is 6') or ('x is 7') can be reduced to '1<=X<=7'.
So the question is, where does the code belong? a.and(b) should return the same as b.and(a), but both b and a may well disagree as to what happens when they are combined under and. At present, both a and b need to supply their own separate implementations. Clearly though, the code for combining patterns A and B belongs to neither A alone, not B alone, but to A and B as a whole.
Thanks in advance, and sorry for this overlong post.
