Skip to content
Snippets Groups Projects
progfun1-4-5.md 4.13 KiB
Newer Older
% Subtyping and Generics
Martin Odersky's avatar
Martin Odersky committed
%
%

Polymorphism
============
Martin Odersky's avatar
Martin Odersky committed

Two principal forms of polymorphism:
Martin Odersky's avatar
Martin Odersky committed

 - subtyping
 - generics
Martin Odersky's avatar
Martin Odersky committed

In this session we will look at their interactions.
Martin Odersky's avatar
Martin Odersky committed

Two main areas:
Martin Odersky's avatar
Martin Odersky committed

 - bounds
 - variance
Martin Odersky's avatar
Martin Odersky committed

Type Bounds
===========
Martin Odersky's avatar
Martin Odersky committed

Consider the method `assertAllPos` which
Martin Odersky's avatar
Martin Odersky committed

 - takes an `IntSet`
 - returns the `IntSet` itself if all its elements are positive
 - throws an exception otherwise
Martin Odersky's avatar
Martin Odersky committed

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

In most situations this is fine, but can one be more precise?
Martin Odersky's avatar
Martin Odersky committed

Type Bounds
===========
Martin Odersky's avatar
Martin Odersky committed

One might want to express that `assertAllPos`
takes `Empty` sets to `Empty` sets and `NonEmpty` sets to `NonEmpty` sets.
Martin Odersky's avatar
Martin Odersky committed

A way to express this is:
Martin Odersky's avatar
Martin Odersky committed

     def assertAllPos[S <: IntSet](r: S): S = ...
Martin Odersky's avatar
Martin Odersky committed

Here, "`<: IntSet`" is an \red{upper bound} of the type parameter `S`:
Martin Odersky's avatar
Martin Odersky committed

It means that `S` can be instantiated only to types that conform to `IntSet`.
Martin Odersky's avatar
Martin Odersky committed

Generally, the notation
Martin Odersky's avatar
Martin Odersky committed

  - `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`_.
Martin Odersky's avatar
Martin Odersky committed

Lower Bounds
============
Martin Odersky's avatar
Martin Odersky committed

You can also use a lower bound for a type variable.
Martin Odersky's avatar
Martin Odersky committed

\example
Martin Odersky's avatar
Martin Odersky committed

       [S >: NonEmpty]
Martin Odersky's avatar
Martin Odersky committed

introduces a type parameter `S` that can range only over \red{supertypes}
of `NonEmpty`.
Martin Odersky's avatar
Martin Odersky committed

So `S` could be one of `NonEmpty`, `IntSet`, `AnyRef`, or `Any`.
Martin Odersky's avatar
Martin Odersky committed

We will see later on in this session where lower bounds are useful.
Martin Odersky's avatar
Martin Odersky committed

Mixed Bounds
============
Martin Odersky's avatar
Martin Odersky committed

Finally, it is also possible to mix a lower bound with an upper bound.
Martin Odersky's avatar
Martin Odersky committed

For instance,
Martin Odersky's avatar
Martin Odersky committed

        [S >: NonEmpty <: IntSet]
Martin Odersky's avatar
Martin Odersky committed

would restrict `S` any type on the interval between `NonEmpty` and `IntSet`.
Martin Odersky's avatar
Martin Odersky committed

Covariance
==========
Martin Odersky's avatar
Martin Odersky committed

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

       NonEmpty <: IntSet
Martin Odersky's avatar
Martin Odersky committed

Martin Odersky's avatar
Martin Odersky committed

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

We call types for which this relationship holds \red{covariant}
because their subtyping relationship varies with the type parameter.
Martin Odersky's avatar
Martin Odersky committed

Does covariance make sense for all types, not just for `List`?
Martin Odersky's avatar
Martin Odersky committed

Arrays
======
Martin Odersky's avatar
Martin Odersky committed

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

Reminder:
Martin Odersky's avatar
Martin Odersky committed

 - 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.
Martin Odersky's avatar
Martin Odersky committed

Arrays in Java are covariant, so one would have:
Martin Odersky's avatar
Martin Odersky committed

        NonEmpty[] <: IntSet[]
Martin Odersky's avatar
Martin Odersky committed

Array Typing Problem
====================
Martin Odersky's avatar
Martin Odersky committed

But covariant array typing causes problems.
Martin Odersky's avatar
Martin Odersky committed

To see why, consider the Java code below.
Martin Odersky's avatar
Martin Odersky committed

\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}
Martin Odersky's avatar
Martin Odersky committed

It looks like we assigned in the last line an `Empty` set to a
variable of type `NonEmpty`!
Martin Odersky's avatar
Martin Odersky committed

What went wrong?
Martin Odersky's avatar
Martin Odersky committed

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

The following principle, stated by Barbara Liskov, tells us when a
type can be a subtype of another.
Martin Odersky's avatar
Martin Odersky committed

\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}
Martin Odersky's avatar
Martin Odersky committed

[The actual definition Liskov used is a bit more formal. It says:
Martin Odersky's avatar
Martin Odersky committed

\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
========
Martin Odersky's avatar
Martin Odersky committed

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}
->