## Sunday, January 12, 2014

### A solution to the object-equality problem

As I mentioned in my last post, there are certain methods that require transitivity — and that means both objects must agree on a single implementation of those methods. For instance, if a `Ball` expects to compare itself against another `Ball` using only its radius, a `WeightedBall` cannot use radius and weight, even if it's being compared to another `WeightedBall`. If it did, transitivity could break when a plain, unweighted `Ball` joins the party.

My solution in Effes is to define `compiletime` methods, which look like normal instance methods but are in fact similar to `Comparator` objects whose instances are picked at compile time. This is basically an implementation of the strategy pattern.

To see this in action, consider the following snippet:

``````type Eq:
[compiletime] == (other: This) -> Bool

data type Ball(radius: Int):
is Eq
[override compiletime] (== other):

type WeightedBall:
is Ball -- also inherits Eq
weight -> Int:
[override compiletime] (== other):
radius == other.radius && weight == other.weight

[override compiletime] (== other): (this: Ball) == other``````

First we define an `Eq` type, with a `compiletime` method named `==`. This method takes one argument, which must be of the same type as the declaring class (the `This` class is a reserved class name, just as `this` is a reserved variable name in many OO languages, including Effes). The `This` restriction is re-applied in each specific type, so `Ball ==` must take a `Ball` argument (not just a `Eq`).

The `WeightedBall` subtype of `Ball` redefines `==` to include the two balls' weights. But it also defines a "variant" called `ByRadius`, which only compares radii. It does this by casting itself down to a plain `Ball`, and then calling `==`, such that this call to `==` has a most specific implementation of `(Ball ==)`.

To someone trying to compare two objects, the `==` method looks like a normal method call. But under the hood, Effes delegates it to a strategy object. Here's a simple set implementation which maintains a list of elements and just checks each new element as it comes in, to make sure it's not already in the list:

``````type ListSet[T:Eq]:
val values : List[T] = Empty
add elem:T -> ListSet[T]: if values contains T
then this
else values' = values push elem
contains (needle : T): case of:
Nothing: False
needle: True
_: tail contains elem``````

The `==` magic happens in the last three lines. The `case head of` statement tries to match `head` against `needle`, using `==`. If they match, the answer is `True`; otherwise, we try recursively on the tail list.

As you can see, `contains` takes one argument, the `needle` we're looking for. But under the hood, it actually takes two arguments: the `needle`, and an "equality strategy" that holds some implementation of `==`. This object is picked at compile time, ensuring that runtime polymorphism doesn't screw up transitivity.

For instance, let's try to add a `heavyBall : WeightedBall` to two `ListSet`s, one typed to `Ball` and the other to `WeightedBall`:

``````plainSet : ListSet[Ball] = getSomeListSet
weightedSet : ListSet[WeightedBall] = getSomeListSet
s1 = plainSet add heavyBall
s2 = weightedSet add heavyBall``````

Note that both variables are initially assigned to identical sets, meaning that both have all `WeightedBall` elements. But, `plainSet` is typed to `ListSet[Ball]`. The last two lines are internally translated to something like:

``````s1_ = plainSet add heavyBall (Ball ==)
s2_ = weightedSet add heavyBall (WeightedBall ==)``````

At the `==` call site (in `ListSet contains`), the `case head of ... needle` snippet is translated to something like `if (_equalityTester head needle)`, where `_equalityTester` is the strategy object.

If we wanted the set to contain `WeightedBalls`, but only restrict to unique radii, we would write:

``````uniqueRadii : ListSet[WeightedBall:ByRadius] = getSomeListSet

The `WeightedBall:ByRadius` bit tells the compiler to pick the `ByRadius` variant we defined above:

``s3_ = uniqueRadii add heavyBall (WeightedBall:ByRadius ==)``

There's one important bit to note here. Comparing two objects by radius is going to give you a different result than comparing them by radius and weight; there could be more duplicates. So when we cast the result of `getSomeListSet` to `ListSet[Ball]`, that's not the relatively light operation that a cast usually is. We have to actually rebuild the `ListSet` so that it knocks out those extra duplicates. I'm still working on the mechanism for this; maybe the casting is only allowed if the type defines a method for it, something like:

``````type ListSet[T:Eq]:
@cast ListSet[T2]: ListSet[T2]() addAll values``````

The signatures of these `compiletime` methods are a bit deceitful. They look like instance methods, and even define `this` but they're actually just normal two-arg methods. This is of course the same for all instance methods (`this` is always just an implicit argument), but it feels like more of a lie here. I think it's because the `this` argument isn't even semantically special; the use case for `compiletime` methods is precisely that `this` and `other` are on the same footing!

The reason I went for the cheat is simply that it feels more natural to me, even if it's a bit inaccurate. It lets us write things like `a == b` (instead of `== a b`, as would be the case for a non-instance method) without tricky rules for declaring methods as inline. My goal from the beginning was to try to get the best of both worlds that Java offers: the correctness of `Comparators` with the natural feel of `this.equals`. I think this approach succeeds in that goal, at the cost of pretty minimal sugar/lies.