This lesson covers:
According to Pierce: “A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute.”
Types allow you to denote function domain & codomains. For example, from mathematics, we are used to seeing:
f: R -> N
this tells us that function “f” maps values from the set of real numbers to values of the set of natural numbers.
In the abstract, this is exactly what concrete types are. Type systems give us some more powerful ways to express these sets.
Given these annotations, the compiler can now statically (at compile time) verify that the program is sound. That is, compilation will fail if values (at runtime) will not comply to the constraints imposed by the program.
Generally speaking, the typechecker can only guarantee that unsound programs do not compile. It cannot guarantee that every sound program will compile.
With increasing expressiveness in type systems, we can produce more reliable code because it allows us to prove invariants about our program before it even runs (modulo bugs in the types themselves, of course!). Academia is pushing the limits of expressiveness very hard, including value-dependent types!
Note that all type information is removed at compile time. It is no longer needed. This is called erasure.
Scala has a very powerful type system, allowing for very rich expression. Some of its chief features are:
Polymorphism is used in order to write generic code (for values of different types) without compromising static typing richness.
For example, without parametric polymorphism, a generic list data structure would always look like this (and indeed it did look like this in Java prior to generics):
scala> 2 :: 1 :: "bar" :: "foo" :: Nil res5: List[Any] = List(2, 1, bar, foo)
Now we cannot recover any type information about the individual members.
scala> res5.head res6: Any = 2
And so our application would devolve into a series of casts (“asInstanceOf[]”) and we would lack typesafety (because these are all dynamic).
Polymorphism is achieved through specifying type variables.
scala> def drop1[A](l: List[A]) = l.tail drop1: [A](l: List[A])List[A] scala> drop1(List(1,2,3)) res1: List[Int] = List(2, 3)
Suppose you had some function
def toList[A](a: A) = List(a)
which you wished to use generically:
def foo[A, B](f: A => List[A], b: B, c: Int) = (f(b), f(c))
This does not compile, because all type variables have to be fixed at the invocation site.
A traditional objection to static typing is that it has much syntactic overhead. Scala alleviates this by providing type inference.
The classic method for type inference in functional programming languages is Hindley-Milner, and it was first employed in ML.
Scala’s type inference system works a little differently, but it’s similar in spirit: infer constraints, and attempt to unify a type.
In Scala, for example, you cannot do the following:
scala> { x => x }
<console>:7: error: missing parameter type
{ x => x }
Whereas in OCaml, you can:
# fun x -> x;; - : 'a -> 'a = <fun>
In scala all type inference is local. For example:
scala> def id[T](x: T) = x
id: [T](x: T)T
scala> val x = id(322)
x: Int = 322
scala> val x = id("hey")
x: java.lang.String = hey
scala> val x = id(Array(1,2,3,4))
x: Array[Int] = Array(1, 2, 3, 4)
Types are now preserved, The Scala compiler infers the type parameter for us. Note also how we did not have to specify the return type explicitly.
Scala’s type system has to account for class hierarchies together with polymorphism. Class hierarchies allow the expression of subtype relationships. A central question that comes up when mixing OO with polymorphism is: if T’ is a subclass of T, is Container[T’] considered a subclass of Container[T]? Variance annotations allow you to express the following relationships between class hierarchies & polymorphic types:
| covariant | C[T’] is a subclass of C[T] |
| contravariant | C[T] is a subclass of C[T’] |
| invariant | C[T] and C[T’] are not related |
The subtype relationship really means: for a given type T, if T’ is a subtype, can you substitute it?
scala> class Covariant[+A]
defined class Covariant
scala> val cv: Covariant[AnyRef] = new Covariant[String]
cv: Covariant[AnyRef] = Covariant@4035acf6
scala> val cv: Covariant[String] = new Covariant[AnyRef]
<console>:6: error: type mismatch;
found : Covariant[AnyRef]
required: Covariant[String]
val cv: Covariant[String] = new Covariant[AnyRef]
^
scala> class Contravariant[-A]
defined class Contravariant
scala> val cv: Contravariant[String] = new Contravariant[AnyRef]
cv: Contravariant[AnyRef] = Contravariant@49fa7ba
scala> val fail: Contravariant[AnyRef] = new Contravariant[String]
<console>:6: error: type mismatch;
found : Contravariant[String]
required: Contravariant[AnyRef]
val fail: Contravariant[AnyRef] = new Contravariant[String]
^
Contravariance seems strange. When is it used? Somewhat surprising!
trait Function1 [-T1, +R] extends AnyRef
If you think about this from the point of view of substitution, it makes a lot of sense. Let’s first define a simple class hierarchy:
scala> class A defined class A scala> class B extends A defined class B scala> class C extends B defined class C scala> class D extends C defined class D
scala> val f: (B => C) = ((b: B) => new C)
f: (B) => C = <function1>
scala> val f: (B => C) = ((a: A) => new C)
f: (B) => C = <function1>
scala> val f: (B => C) = ((a: A) => new D)
f: (B) => C = <function1>
scala> val f: (B => C) = ((a: A) => new C)
f: (B) => C = <function1>
scala> val f: (B => C) = ((c: C) => new C)
<console>:8: error: type mismatch;
found : (C) => C
required: (B) => C
val f: (B => C) = ((c: C) => new C)
^
^
Scala allows you to restrict polymorphic variables using bounds. These bounds express subtype relationships.
scala> class F { def foo = "F" }
defined class F
scala> class E extends F { override def foo = "E" }
defined class E
scala> def callFoo[T](foos: Seq[T]) = foos map (_.foo) foreach println
<console>:8: error: value foo is not a member of type parameter T
def callFoo[T](foos: Seq[T]) = foos map (_.foo) foreach println
scala> def callFoo[T <: F](foos: Seq[T]) = foos map (_.foo) foreach println
callFoo: [T <: F](foos: scala.collection.mutable.Seq[T])Unit
scala> callFoo(Seq(new E, new F))
E
F
Lower type bounds are also supported. They go hand-in-hand with contravariance. Let’s say we had some class Node:
scala> class Node[T](x: T) { def sub(v: T): Node[T] = new Node(v) }
But, we want to make it covariant in T:
scala> class Node[+T](x: T) { def sub(v: T): Node[T] = new Node(v) }
<console>:6: error: covariant type T occurs in contravariant position in type T of value v
class Node[+T](x: T) { def sub(v: T): Node[T] = new Node(v) }
^
Recall that method arguments are contravariant, and so if we perform our substitution trick, using the same classes as before:
class Node[B](x: B) { def sub(v: B): Node[B] = new Node(v) }
is not a subtype of
class Node[A](x: A) { def sub(v: A): Node[A] = new Node(v) }
because A cannot be substituted for B in the argument of “sub”. However, we can use lower bounding to enforce correctness.
scala> class Node[+T](x: T) { def sub[U >: T](v: U): Node[U] = new Node(v) }
defined class Node
scala> (new Node(new B)).sub(new B)
res5: Node[B] = Node@4efade06
scala> ((new Node(new B)).sub(new B)).sub(new A)
res6: Node[A] = Node@1b2b2f7f
scala> ((new Node(new B)).sub(new B)).asInstanceOf[Node[C]]
res7: Node[C] = Node@6924181b
scala> (((new Node(new B)).sub(new B)).sub(new A)).sub(new C)
res8: Node[A] = Node@3088890d
Note also how the type changes with subsequent calls to “sub”.
Sometimes you do not care to be able to name a type variable, for example:
scala> def count[A](l: List[A]) = l.size count: [A](List[A])Int
Instead you can use “wildcards”:
scala> def count(l: List[_]) = l.size count: (List[_])Int
This is shorthand for:
scala> def count(l: List[T forSome { type T }]) = l.size
count: (List[T forSome { type T }])Int
Note that quantification can get tricky:
scala> def drop1(l: List[_]) = l.tail drop1: (List[_])List[Any]
Suddenly we lost type information! To see what’s going on, revert to the heavy-handed syntax:
scala> def drop1(l: List[T forSome { type T }]) = l.tail
drop1: (List[T forSome { type T }])List[T forSome { type T }]
We can’t say anything about T because the type does not allow it.
You may also apply bounds to wildcard type variables:
scala> def hashcodes(l: Seq[_ <: AnyRef]) = l map (_.hashCode)
hashcodes: (Seq[_ <: AnyRef])Seq[Int]
scala> hashcodes(Seq(1,2,3))
<console>:7: error: type mismatch;
found : Int(1)
required: AnyRef
Note: primitive types are not implicitly converted to AnyRef.
You can safely force boxing by casting x.asInstanceOf[AnyRef].
hashcodes(Seq(1,2,3))
^
scala> hashcodes(Seq("one", "two", "three"))
res1: Seq[Int] = List(110182, 115276, 110339486)