progfun1-4-5.md

% Subtyping and Generics
%
%

Polymorphism
============

Two principal forms of polymorphism:

 - subtyping
 - generics

In this session we will look at their interactions.

Two main areas:

 - bounds
 - variance

Type Bounds
===========

Consider the method `assertAllPos` which

 - takes an `IntSet`
 - returns the `IntSet` itself if all its elements are positive
 - throws an exception otherwise

What would be the best type you can give to `assertAllPos`? Maybe:
->
      def assertAllPos(s: IntSet): IntSet

In most situations this is fine, but can one be more precise?

Type Bounds
===========

One might want to express that `assertAllPos`
takes `Empty` sets to `Empty` sets and `NonEmpty` sets to `NonEmpty` sets.

A way to express this is:

     def assertAllPos[S <: IntSet](r: S): S = ...

Here, "`<: IntSet`" is an \red{upper bound} of the type parameter `S`:

It means that `S` can be instantiated only to types that conform to `IntSet`.

Generally, the notation

  - `S <: T` means: _`S` is a subtype of `T`_, and
  - `S >: T` means: _`S` is a supertype of `T`_, or _`T` is a subtype of `S`_.

Lower Bounds
============

You can also use a lower bound for a type variable.

\example

       [S >: NonEmpty]

introduces a type parameter `S` that can range only over \red{supertypes}
of `NonEmpty`.

So `S` could be one of `NonEmpty`, `IntSet`, `AnyRef`, or `Any`.

We will see later on in this session where lower bounds are useful.

Mixed Bounds
============

Finally, it is also possible to mix a lower bound with an upper bound.

For instance,

        [S >: NonEmpty <: IntSet]

would restrict `S` any type on the interval between `NonEmpty` and `IntSet`.

Covariance
==========

There's another interaction between subtyping and type parameters we
need to consider. Given:

       NonEmpty <: IntSet

is

       List[NonEmpty] <: List[IntSet]    ?
->
Intuitively, this makes sense: A list of non-empty sets is a special case of a list of arbitrary sets.

We call types for which this relationship holds \red{covariant}
because their subtyping relationship varies with the type parameter.

Does covariance make sense for all types, not just for `List`?

Arrays
======

For perspective, let's look at arrays in Java (and C#).

Reminder:

 - An array of `T` elements is written `T[]` in Java.
 - In Scala we use parameterized type syntax `Array[T]` to refer to the same type.

Arrays in Java are covariant, so one would have:

        NonEmpty[] <: IntSet[]

Array Typing Problem
====================

But covariant array typing causes problems.

To see why, consider the Java code below.

\begin{lstlisting}
  NonEmpty[] a = new NonEmpty[]{
    new NonEmpty(1, new Empty(), new Empty())};
  IntSet[] b = a;
  b[0] = new Empty();
  NonEmpty s = a[0];
\end{lstlisting}

It looks like we assigned in the last line an `Empty` set to a
variable of type `NonEmpty`!

What went wrong?

The Liskov Substitution Principle
================================

The following principle, stated by Barbara Liskov, tells us when a
type can be a subtype of another.

\begin{quote}
If \verb`A <: B`,
then everything one can to do with a value of type \verb`B` one should also
be able to do with a value of type \verb`A`.
\end{quote}

[The actual definition Liskov used is a bit more formal. It says:

\begin{quote}
Let \verb`q(x)` be a property provable about objects \verb`x` of type \verb`B`.
Then \verb`q(y)` should be provable for objects \verb`y` of type \verb`A` where \verb`A <: B`.
\end{quote}
]

Exercise
========

The problematic array example would be written as follows in Scala:

      val a: Array[NonEmpty] = Array(NonEmpty(1, Empty(), Empty()))
      val b: Array[IntSet] = a
      b(0) = Empty()
      val s: NonEmpty = a(0)

When you try out this example, what do you observe?

\begin{tabular}{ll}
   \verb`  O         ` &       A type error in line 1
\\ \verb`  O         ` &       A type error in line 2
\\ \verb`  O         ` &       A type error in line 3
\\ \verb`  O         ` &       A type error in line 4
\\ \verb`  O         ` &       A program that compiles and throws an exception at run-time
\\ \verb`  O         ` &       A program that compiles and runs without exception
\end{tabular}
->
\quiz