Subtyping in Object Oriented Languages
======================================

These notes cover a few of the issues related to subtyping in OOP languages. To start consider
the cliched example of an Animal class hierarchy. The code below is (approximately) in Java.

class Animal {
   // Every animal has a weight so this method is meaningful for all animals.
   // The method should maybe be abstract since it's unclear what its default could be.
   public double getWeight( ) { ... }
}

// "Cat is a subtype of Animal." Meaning: "A Cat is-a Animal."
class Cat extends Animal {
   // ...
}

// "PersianCat is a subtype of Cat." Meaning: "A PersianCat is-a Cat."
class PersianCat extends Cat {
   // ...
}

// "Dog is a subtype of Animal." Meaning: "A Dog is-a Animal."
class Dog extends Animal {
   Dog(String name);  // Constructor allows us to build a specific instance.
   // ...
}

Remember: A type is a set of values and a set of operations that can be applied to those values.
Consider, for example, the type int:

  values = { ... -2, -1, 0, 1, 2, ... }
  operations = { +, -, *, /, ... }

Now consider class Dog. There are many values of class Dog depending on how many ways we can run
the constructor. In this case there is a Dog for every possible name, meaning infinitely many.

  values = { new Dog("Fido"), new Dog("Rover"), ... }
  operations = { methods on class Dog } UNION { methods on class Animal }

What about Animal?
  values = values_of_Dog UNION values_of_Cat

The set of values of Cat is a SUBSET of the set of values of Animal. Thus Cat is a SUBTYPE of
Animal. Notice, however, that the set of operations on Cat is a SUPERSET of the set of
operations on Animal since Cats can do everything Animals can do plus possibly special
Cat-specific things.

IMPORTANT! IMPORTANT! IMPORTANT!
*****
The value of a SUBTYPE can be used where a value of a SUPERTYPE is expected.
The value of a Cat can be used where a value of Animal is expected.
A Cat is-a Animal.
*****

Notation: "T <: U" means "T is a subtype of U."
Cat <: Animal  (true)
Dog <: Animal  (true)
Cat <: Dog     (false)
Dog <: Cat     (false)

Question:
   If T <: U then is (Array of T) <: (Array of U) ??

For example since Cat <: Animal. Does that mean Cat[] <: Animal[]? Consider the method below
that accepts an array of animals and computes their total weight

public double zooWeight(Animal[] zoo)
{
  double totalWeight = 0.0;

  for(int i = 0; i < zoo.length; ++i ) {
    totalWeight += zoo[i].getWeight( );
  }

  return totalWeight;
}

Now suppose I create an array of Cats like this:

Cat[] cattery = new Cat[100];

... and try to send the cattery to zooWeight

total = zooWeight(cattery); // Only works if it's okay to use Cat[] where Animal[] is expected.
                            // Only works if Cat[] <: Animal[]
                            // It is true that Cat <: Animal. Is that good enough?
                            // Is Array "covariant?"

This doesn't seem like it would be a problem. Since Cats have a getWeight method (either
inherited from Animal or overridden), computing the totalWeight inside zooWeight should be
perfectly sensible. Thus it seems like we should allow arrays to be covariant.

If Array was covariant then
Cat[] <: Animal[]  (true)
Dog[] <: Animal[]  (true)
Cat[] <: Dog[]     (false)
Dog[] <: Cat[]     (false)

In Java Arrays ARE covariant. The code above compiles. In Scala, however, Arrays are
"invariant." The code above (after converting to Scala) would NOT compile.

Actually covariant arrays are problematic (which is why they are not allowed in Scala). To
understand the issue take a look at this:

public void g(Animal[] zoo)
{
   if (zoo.length >= 1 ) {
      zoo[0] = new Cat(); // In Java an exception will be thrown here if the array type is wrong.
   }
}

Since a Cat is-a Animal the compiler should allow us put a Cat into an array of animals.
However, are we sure zoo is actually an array of Animal? It might be something else.

Dog[] kennel = new Dog[100];

g(kennel);

Here we pass g an array of Dog. Inside g, however, the array is treated as an array of animals
and a Cat is added to what is actually an array of Dog!

for(int i = 0; i < kennel.length; ++i) {
   kennel[i].bark( );
}

The code above is now trying to make a Cat bark (calling an invalid method). Java avoids this by
adding a runtime check at the place where the Cat is added to the array. At runtime it is
verified that the array has an appropriate type; if not an exception is thrown.

The *REAL PROBLEM* is that arrays are mutable! If arrays were immutable, the issue goes away
and allowing covariant arrays would be fine.

In Scala, an OOP/Functional hybrid language
  Arrays are mutable   and invariant.
  Lists  are immutable and covariant.

In Scala Cat <: Animal implies that List[Cat] <: List[Animal] TRUE. Lists are covariant. It's
okay because list are immutable. (Note that Scala uses [] syntax for generic type parameters).

-------

In a functional language, functions are "first class" (meaning they can be treated like any
other object). The question is: how do function types behave in this context.

T -> U  (Means "function taking type T and returning type U" or...
               "function from T to U")

(T -> U) <: (S -> V)  What does this mean???

The question is: "Can I use a function of type T -> U where a function of type S -> V is
expected?" If I can, then (T->U) <: (S->V) is true; otherwise it is false.

Here's an example using Haskell syntax.

f :: T -> U
g :: S -> V

... (g x) ...

What if I replace g with f?

... (f x) ...

For this to make sense the type returned by f (namely U) has to be usable in a context where the
type returned by g (namely V) is expected. In other words

     U <: V

However it is also necessary for the type of g's parameter (namely S) be usable where the type
of f's parameter (namely T) is expected.

     S <: T

Putting this together we have

     (T -> U) <: (S -> V) if and only if U <: V and S <: T

Said a different way the return types must be covariant and the parameter types must
"contravariant."