26 Extensional Equality in Java
26.1 Posn
26.2 Equality in Java
|
class Posn { |
Integer x; |
Integer y; |
Posn(Integer x, Integer y) { |
this.x = x; |
this.y = y; |
} |
|
public Boolean isEqual(Posn p) { |
return this.x == p.x |
&& this.y == p.y; |
} |
} |
|
interface LoP { |
Boolean isEmpty(); |
Posn getFirst(); |
LoP getRest(); |
} |
|
class MT implements LoP { |
MT() {} |
|
public Posn getFirst() { |
return null; |
} |
|
public LoP getRest() { |
return ????; |
} |
|
public Boolean isEmpty() { |
return true; |
} |
|
public Boolean isEqual(LoP lop) { |
return lop.isEmpty(); |
} |
} |
|
class Cons implements LoP { |
Posn first; |
LoP rest; |
|
Cons(Posn first, LoP rest) { |
this.first = first; |
this.rest = rest; |
} |
|
public Boolean isEmpty() { |
return false; |
} |
|
public Boolean isEqual(LoP lop) { |
return (!lop.isEmpty()) |
&& this.first.isEqual(lop.getFirst()) |
&& this.rest.isEqual(lop.getRest()); |
} |
|
public Posn getFirst() { |
return this.first; |
} |
|
public LoP getRest() { |
return this.rest; |
} |
|
|
} |
|
26.3 List of Posn
interface LoP { |
Boolean isEmpty(); |
Posn getFirst(); |
LoP getRest(); |
Boolean isEqual(); |
} |
|
class MT implements LoP { |
MT() {} |
|
public Posn getFirst() { |
return ????; |
} |
|
public LoP getRest() { |
return ????; |
} |
|
public Boolean isEmpty() { |
return true; |
} |
|
public Boolean isEqual(LoP lop) { |
return lop.isEmpty(); |
} |
} |
|
class Cons implements LoP { |
Posn first; |
LoP rest; |
|
Cons(Posn first, LoP rest) { |
this.first = first; |
this.rest = rest; |
} |
|
public Boolean isEmpty() { |
return false; |
} |
|
public Boolean isEqual(LoP lop) { |
return (!lop.isEmpty()) |
&& this.first.isEqual(lop.getFirst()) |
&& this.rest.isEqual(lop.getRest()); |
} |
|
public Posn getFirst() { |
return this.first; |
} |
|
public LoP getRest() { |
return this.rest; |
} |
|
|
} |
|
How did we get into this situation? Let’s look at isEqual again:
public Boolean isEqual(LoP lop) { |
return (!lop.isEmpty()) |
&& this.first.isEqual(lop.getFirst()) |
&& this.rest.isEqual(lop.getRest()); |
} |
After the first conjunct, we know that lop is a Cons, and so we want to get the first and rest. But Java doesn’t know that, and so we created the getFirst and getRest methods.
If we return null, then we create problems for all possible clients of the getFirst method. So instead we raise an error:
public Posn getFirst() { |
throw new RuntimeException("Can't take the first of an empty list.") |
} |
|
public Posn getRest() { |
throw new RuntimeException("Can't take the rest of an empty list.") |
} |
But if we think about isEqual again, can we help Java do something smarter? Let’s try taking getFirst and getRest out of the interface. If we do that, we get an error message about not finding those methods in the interface. But can we persuade Java that lop is really a Cons? Yes:
public Boolean isEqual(LoP lop) { |
return (!lop.isEmpty()) |
&& this.first.isEqual(((Cons)lop).getFirst()) |
&& this.rest.isEqual(((Cons)lop).getRest()); |
} |
This is called casting, and it’s crucial for (some kinds of) programming using the Java type system. However, it’s important to remember that we’re cheating the type system here. The cast is turned into a runtime check, and we could write anything down that we want. It’s only when running the program that Java can check whether lop is really a Cons.
26.4 Equality and Parameterized Types
We try writing a parameterized version of Listof<X> with equality.
It doesn’t work, because X doesn’t have an isEqual method.
Fix: restrict X to implement the IEqual interface.
Question about structural vs nominal typing.
Discussion about polymorphism/bounds/extends/etc.
The class language version:
;; An [IEqual X] implements ;; =? : X -> Boolean ;; A [Listof X] implements ;; empty?: -> Boolean ;; and implements [IEqual [Listof X]] ;; where X implements [IEqual X]
If we unroll our definitions a little, we get:
;; An [IEqual X] implements ;; =? : X -> Boolean ;; A [Listof X] implements ;; empty? : -> Boolean ;; =? : [Listof X] -> Boolean ;; where X implements ;; =? : X -> Boolean
26.5 Comparing different kinds of things
This works:
(equal? 5 "fred")
This doesn’t work:
new Posn(3,4).isEqual("fred")
The reason this doesn’t work is that we’re violating the contract on isEqual, which is enforced by the type system.
So let’s create a different isEqual method:
public Boolean isEqualPosn(Posn p) { |
return this.x == p.x |
&& this.y == p.y; |
} |
|
public Boolean isEqual(Object o) { |
return (o instanceof Posn) |
&& this.x == p.x |
&& this.y == p.y; |
} |
This doesn’t typecheck, so we have to add casts again.
public Boolean isEqual(Object o) { |
return (o instanceof Posn) |
&& this.x == ((Posn)p).x |
&& this.y == ((Posn)p).y; |
} |
Or, we can use our way of comparing Posns.
public Boolean isEqual(Object o) { |
return (o instanceof Posn) |
&& this.isEqualPosn((Posn)o); |
} |
But why would we want to compare things of different types? It turns out that Java has a built-in notion of equality, called the equals method. And this method expects its input to be an Object.
We can reuse this implementation:
public Boolean equals(Object o) { |
return (o instanceof Posn) |
&& this.isEqualPosn((Posn)o); |
} |
There are two big problems with this:
If we extend Posn, then equals will behave differently in different directions.
We forgot to override hashCode.
26.5.1 equals and hashCode
The fundamental rules for overriding equal:
If you override equals, you must override hashCode.
o.equals(p) implies o.hashCode() == p.hashCode()
The rule of hashCode: if two objects have differnet hash codes, they are different. hashCode is a fast way to check if two objects are different.
Here’s a quick and correct implementation of hashCode:
public int hashCode() { |
return 0; |
} |