Recitation 4: Subtypes and Exceptions

What is a Subtype?

Type A is a subtype of type B if A's specification implies B's specification. Subtypes must satisfy the substitution principle, which means that any code that relies on B's specification will function properly if A's implementation is substituted for B. Users can write and reason about code just using the specification of B. In order to satisfy substitutability, three properties must hold:

Signature rule. The subtype must have all the methods of the supertype, with compatible signatures. The signatures for a method are compatible if:
- the subtype's method returns the same or a subtype of the type returned by the supertype's method,
- the subtype's argument types are the same or supertypes of the supertype's arguments, and
- the subtype throws no more exceptions than the supertype
Java actually enforces even stricter rules about signature compatibility in subclasses. It allows a subclass to be declared to throw a subset of the exceptions or to throw subclasses of the exceptions thrown by the superclass, but otherwise subclass and superclass must have identical method signatures.
Methods rule. A subtype's specification for any method must be at least as strong as its supertype's specification. So, a subtype method can weaken the precondition and can strengthen the postcondition. This is different from the signature rule because this has to do with specifications, while the methods rules only involves method signatures (the signatures rule could be checked by the compiler, but the methods rule could not).
Properties rule. The subtype must preserve all properties that can be proved about the supertype. Invariants that are guaranteed in the supertype must also be guaranteed by the subtype.

Subclasses vs. Subtypes

A subclass in Java does not have to be a true subtype. In order to be a subtype, the methods of the subclass must satisfy the superclass's specifications. However, this cannot be checked by the compiler, so it is possible to create a subclass that is not a subtype. This should be avoided, because it means that you cannot reason about your code without knowing what particular subclasses of a class may be used. For example, an argument to a method may be declared of one class A, but the method may be called with an argument of some subclass B. If we do not know if B is a true subtype of A, then we cannot assume that the behavior guaranteed by A is actually guaranteed by B, and so we cannot reason locally about this method.

Exceptions

For many methods, it only makes sense to take input in a certain range. For example, it does not make sense to compute the factorial of a negative number. There are a few different ways this situation is usually handled:

Put a requires clause in the method to require that the argument is non-negative. This requires the caller to check that this condition is satisfied before calling the method, and if there is an erroneous call to the method, anything could happen.
Return a special value. In the factorial case, the method could return -1 to signify the error. This is no better since it requires the caller to check the return value to check for the error, or if it does not make this check, it could continue execution without noticing the error. Another problem with this approach is that in some cases there is no special value of the return type -- every possible return value may be valid.
Call System.exit(-1) to halt execution of the program. If you do this, there is no way for the caller to recover from the error (which exceptions allow).

A fourth approach is to throw an "exception" in an error situation. Exceptions allow a method to terminate normally by returning a result, or to terminate exceptionally by throwing an exception. There are two types of exceptions: checked exceptions and unchecked exceptions. In Java, checked exceptions are subclasses of Exception, and unchecked exceptions are subclasses of RuntimeException,. There are a few differences between how Java handles checked and unchecked exceptions:

If code calls a method that may throw a checked exception, the calling code must handle the exception. It can handle the exception by either catching it or by declaring in its own signature that it may throw that exception type. Unchecked exceptions do not have to be handled by calling code.
If a method might throw a checked exception, it must be declared in the signature of the method (as throws <exception_type>). Unchecked exceptions do not have to be listed in the method header (but they may).

Defining Exception Types

A new exception can be declared as follows:

public class NegativeException extends Exception {
   public NegativeException() { super(); }
   public NegativeException(String s) { super(s); }
}

This exception is a checked exception, because it extends Exception, not RuntimeException. As you can see from this example, a new exception type only has to define constructors. All of the other functionality of the exception can be inherited from its superclass.

Throwing Exceptions

A method can terminate by throwing an exception, using the throw statement. For example,

// effects: if n < 0 throws a NegativeException; else returns n!
public static int fact(int n) throws NegativeException {
  if (n < 0) {
    throw new NegativeException("fact");
  }
  ...
}

This example shows how to throw an exception, as well as how to declare that a method may throw a checked exception. The string argument that is passed to the exception's constructor can be retrieved using the toString method of the exception. This allows a user to get an English description of what went wrong if the program cannot handle the exception.

Handling Exceptions

Calling code can deal with exceptions in two ways -- using the try statement, or by propagating the exception. The following code uses a try statement to handle NegativeException:

try {
  x = Num.fact(y);
}
catch (NegativeException e) {
  // code that handles exception, which can use e
}

If the call to fact throws a NegativeException, the catch clause is executed. The exception that is thrown by fact is bound to the variable e, which can be used by the code in the catch clause.

Several catch clauses can be attached to a try statement, so that different exceptions can be handled differently. The syntax for this is:

try { 
  // code that may throw a SomeException or a SomeOtherException
}
catch (SomeException e) { 
  // code fragment a 
}
catch (SomeOtherException e) { 
  // code fragment b
}

In this case, if the code in the try block throws a SomeException, then code fragment a is executed; if it throws a SomeOtherException, then code fragment b is executed. Otherwise, execution continues normally after the catch blocks.

You can also use a try statement to catch any exception that is a subclass of some type of exception. For example, the java.io package contains numerous exceptions which all subclass IOException, such as FileNotFoundException, InterruptedIOException, and EOFException. One way to handle all of these different types of IOExceptions is to write code like:

try { 
  ... 
}
catch (FileNotFoundException e) { 
  ... 
}
catch (InterruptedIOException) { 
  ... 
}
catch (EOFException e) { 
  ... 
}
... // catch blocks for other exceptions

Or, to catch any exception that inherits from IOException, we can use the code:

try { 
  ... 
}
catch (IOException e) { 
  ... 
}

If the code in the try block throws any exception that inherits from IOException, the code in the catch block is executed. Using this construction avoids the code duplication that would be necessary if each type of exception were handled in a different catch block.

You can also handle exceptions by propagating them. If a method m() calls code that is declared to throw a checked exception, the method may declare the exception or a superclass of the exception in its throws clause and delegate the responsibilty to catch the exception to the code that calls m(). For the sake of code clarity, it is actually preferrable to catch the exception in m(), and then rethrow the exception. For example:

void m() throws NegativeException {
  try {
    int x = Num.fact(y);
  }
  catch (NegativeException e) {
    throw e;
  }
  ...
}

rethrows the exception e. This makes it clearer to a reader of the code where the NegativeException declared in the throws clause may be thrown from.

Problems

1. Graphical Objects

Design a type hierarchy for graphical objects. This hierarchy should include classes for curves, shapes, ellipses, circles, triangles, rectangles, squares, and bitmaps. Discuss possible operations such as scaling, rotating, and setting the color of an object, and in which classes it makes sense to declare these methods.

2. Bicycles

Say we want to model bicycles in some program. We have written specification for three bicycles -- Bicycle, a generic bicycle that costs $100; LightedBicycle, a subclass of Bicycle that represents a bicycle with a light on it, which costs $150; and RacingBicycle, another subclass of Bicycle that represent a racing bike. Below are the partial specifications for the three classes:

class Bicycle {
   
   // returns: 100
   float cost();
   
   // requires: windspeed < 20 mph && daylight
   // effects: transports the rider from work to home
   void goHome();
}

class RacingBicycle extends Bicycle {
   
   // requires: windspeed < 20 mph && daylight
   // effects: transports the rider from work to home in
   //    an elapsed time of < 10 minutes
   void goHome();
}

class LightedBicycle extends Bicycle {
   
   // returns: 150
   float cost();

   // requires: windspeed < 20 mph
   // effects: transports the rider from work to home
   void goHome();
}

Which of these subclasses is a true subtype of Bicycle? Which changes in the specification break the subtyping relationship, and how can this be avoided? Why do some of the changes in the specification not break the subtype relationship?

3. Collection Class Hierarchy

The interface java.util.Collection defines operations for the collection classes like LinkedList and Set. The interface contains many optional operations, which implementors of Collection may not implement; instead, they may throw an exception when that method is called. Some of the optional operations are add and remove. These operations are optional because, for example, an immutable collection does not need an add method. An alternative design for this is to have a deeper hierarchy for collection classes, with interfaces that have no optional operations. For instance, some interface GrowableCollection would extend Collection, and any growable collection would implement GrowableCollection.

Design a type hierarchy that allows for some collection classes to be growable (to support adding elements) and some to be shrinkable (to support deleting elements). Include in this type hierarchy the classes SortedSet, which implements Set, and GrowableList, which allows the user to add elements, but not to remove elements. Discuss the tradeoffs between this design and the design that is actually used in java.util.

4. SortedVector

The java.util library does not include a sorted vector. We want to implement a sorted vector, which takes a comparator at creation time, and maintains a sorted list of Objects. We need to decide whether this class should extend java.util.Vector. Some of the operations to consider in Vector are:

void add(int index, Object elt), which inserts an element at the specified position
void addElement(Object elt), which adds the specified element to the end of the vector
Object elementAt(int index), which returns the element at the specified index
Object remove(int index), which removes the element at the specified index, and returns that element
void setElementAt(Object obj, int index), which sets the component at the specified index to be the specified object

Discuss whether SortedVector should extend Vector. If so, which of these methods should be overriden, and which do you think could inherit their implementation?

5. Subclassing vs. Composition

We are writing a program that involves people and their cars. We have two interfaces, Person and Car. We want to implement a CarOwner. Car is immutable, and has operations to get the make and model, to get the color, to paint a new color, and to get the license plate number. Person is immutable also, and has operations to get the person's name, phone number, and birthdate. CarOwner will have operations to get the person's name, phone number, birthdate, and his car's make and model. We are considering implementing CarOwner as:

class CarOwner implements Person, Car {
  ...
}

Is this a good way to implement CarOwner? List some alternative designs and the advantages and disadvantages of them.

6. Satisfying Specifications in a Subclass

Consider the classes A and B:

class A {
   
   int m() {
      int x = p();
      return f(x);
   }

   int p() {
      ...
   }

   int f(int x) {
      ...
   }
}

class B extends A {
   
   int p() {
      ...
   }

   int f(int x) {
      ...
   }
}

Suppose that you find that the method m in class B does not satisfy the specification in A, but that in A, m does satisfy the specification. How is it possible that the contract is broken in B, when it inherits the implementation from A? What is necessary to guarantee that B.m satisfies the specification for m?