Newer
Older
In this session we will look at their interactions.
- 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?
One might want to express that `assertAllPos`
takes `Empty` sets to `Empty` sets and `NonEmpty` sets to `NonEmpty` sets.
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`.
- `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`_.
You can also use a lower bound for a type variable.
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.
Finally, it is also possible to mix a lower bound with an upper bound.
would restrict `S` any type on the interval between `NonEmpty` and `IntSet`.
There's another interaction between subtyping and type parameters we
need to consider. Given:
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`?
For perspective, let's look at arrays in Java (and C#).
- 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:
Array Typing Problem
====================
\begin{lstlisting}
NonEmpty[] a = new NonEmpty[]{
new NonEmpty(1, new Empty(), new Empty())};
IntSet[] b = a;
b[0] = new Empty();
NonEmpty s = a[0];
It looks like we assigned in the last line an `Empty` set to a
variable of type `NonEmpty`!
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}
->