On this page:
25.1 Announcements
25.2 Types in Java
25.3 Returning to the code from last time
25.4 Equality and Parameterized Types
25.5 Comparing different kinds of things
25.5.1 equals and hash Code
5.3.2.3

25 More about Equality

25.1 Announcements
25.2 Types in Java

What sorts of things count as types in Java?

What should be a part of the contract and purpose in Java? Well, we don’t need to write down things that are already part of the type. If the contract corresponds to the type, you don’t have to repeat it. However, some contracts can’t be checked by the type system—you should still write those down.

25.3 Returning to the code from last time

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.

25.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
25.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:

25.5.1 equals and hashCode

The fundamental rules for overriding equal:

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;

}