This is the first article in a series that will examine, as the title suggests, Scala’s type system, and, as a secondary concern, concepts and ideas that are related to types and type systems.
The best way to emphasize theoretical notions is to give examples. Accordingly, I chose the Scala as the instrument for this endeavor.
According to the official website, Scala is a “general purpose programming language designed to express common programming patterns in a concise, elegant, and type-safe way”.
For getting the most out of the article, basic familiarity with Scala’s syntax is required. Also object-oriented concepts like inheritance, subtyping or polymorphism should not be foreign.
Types
Computer programming theory defines a type as a means of classification identifying an abstract concept, along with additional characteristics like the operations that can be done on values of that type, the way values of that type can be stored in memory, and so on.
For example, an Int type can be defined as a bounded set of integers, along
with the operations that can be performed on an integer, like addition,
subtraction, division, and so on. Additionally, Ints can be described by
characteristics like memory representation (for example, 32-bit integers in some
programming languages).
An Int, alongside other useful types, is a kind of type called a ‘data type’
and it is present by default in most of the programming languages.
Many programming languages allow the programmer to create types. Sometimes these types denote abstractions in the problem domain. And most of the times these types are aggregates of other types.
The type system
A type becomes an essential property that is used by the compiler to determine the correctness of your code. The compiler incorporates a component called ‘type checker’ that will ensure that, given a set of constraints, no violations of these constraints exist.
The set of constraints that are verified by the type checker is also called a ‘type system’.
Unsurprisingly, a type is also a constraint. A type checker essentially associates types with computed values. By examining the flow of these values, the type checker attempts to prove that no type errors can occur.
This way, instead of having errors that manifest at runtime, the
compiler will not accept any programs that violate type restrictions. In Scala,
the way to define a type is by either defining a class, an object or by using
the type keyword directly.
Type parametrization
Type parameters allow you to define methods or types in terms of another type(s). A type parameter is a type definition that’s taken in as a parameter when calling a method, constructing a type, or extending a type. It can also be said that type parameters ‘capture’ types.
It shouldn’t be too surprising to find out that type parameters are also constraints and that they can also be validated by the type checker. In Scala, type parameters are defined by using angle brackets.
trait Box[T] {
def put(t: T)
def get: T
}In this example, a type, Box is defined. As the name suggests, a
Box is a sort of container, therefore things can be put into and retrieved from
it. Also, this is a box that can hold many different things. We can call it
generic Box. To model this generic box, type parameters are used.
Now someone can create and use boxes that contain different things :
val integerBox = new Box[Int] {
override def put(t: Int): Unit = ???
override def get: Int = ???
}
val stringBox = new Box[String] {
override def put(t: String): Unit = ???
override def get: String = ???
}Variance
So what makes type parameters useful and interesting?
Type parameters become important in the context of variance.
Once two types are in a subtyping relationship, the question of variance - how
they relate to each other in view of their type parameters - becomes essential.
Concretely, considering a Box[T], if Int is a subtype of Number, can
Box[Int] be used where Box[Number] is expected or the other way around?
Variance also describes how type parameters can be altered to create conformant
(assignable) types. In type theory, given a parameterized type T, T[A]
conforms to T[B] if you can assign T[B] to T[A] without errors.
Variance is yet another type of constraint that can be enforced with the help of the type checker. Type variance is complementary to type parameterization and specifies constraints like invariant, covariant and contravariant to the type system.
For this part I will focus only on invariance, leaving the other two forms for the next articles.
Invariance
Invariance refers to the unchanging nature of the type parameter.
Formally, if a type is invariant, then, assuming existing types T, A, B,
if T[A] conforms to T[B] then A must be the equivalent type of B.
The type from the previous example, Box, is invariant.
For a more concrete illustration, imagine a programmer developing a warehousing solution. He will create a few types and a method for packaging things in boxes.
trait CanBePacked
trait Furniture extends CanBePacked
trait Books extends CanBePacked
def packFurnitureIntoBox(b: Box[CanBePacked]) = {
// work hard to pack things
}
val bBox: Box[Books] = new Box[Books] {
override def put(t: Books): Unit = ???
override def get: Books = ???
}
// disallowed
// packFurnitureIntoBox(bBox)As noted, the method call packFurnitureIntoBox(bBox) will not be allowed by
the compiler.
The reason is straightforward. Imagine the Box type was not invariant. Then an
unsuspecting programmer could try to pack furniture in book boxes, as the
example underlines.
Closing remarks
In the next article I will demonstrate that it’s actually possible to relax the
invariance restriction placed upon the type Box, I will discuss the forces
that could lead to such a venture, and of course I will also clarify things with
an example.