A Subtyping Polymorphism Misfortune

The type system in Scala is based, among other things, on subtyping polymorphism, which is also known as inheritance in the object-oriented community’s parlance. Wikipedia defines it as:

Subtyping (also called subtype polymorphism or inclusion polymorphism): when a name denotes instances of many different classes related by some common superclass.

Many programmers and developers see it as a great concept that helps with organizing source code. However, there are also serious downsides to it.

consider the following Scala REPL session:

Welcome to Scala 2.12.4 (OpenJDK 64-Bit Server VM, Java 1.8.0_151).
Type in expressions for evaluation. Or try :help.

scala> val m = Map[String, Int]("Lorem" -> 1, "ipsum" -> 2)
val m = Map[String, Int]("Lorem" -> 1, "ipsum" -> 2)
m: scala.collection.immutable.Map[String,Int] = Map(Lorem -> 1, ipsum -> 2)

scala> val s = Set("dolor", "sit", "amet")
val s = Set("dolor", "sit", "amet")
s: scala.collection.immutable.Set[String] = Set(dolor, sit, amet)

scala> s ++ m
s ++ m
res0: scala.collection.immutable.Set[java.io.Serializable] = Set(sit, amet, (Lorem,1), dolor, (ipsum,2))

What is the result here? It is a set of serializables, i.e. a set of non-sense. In other words, in Scala one can add a Map of Strings to Integers to a Set of Strings, even though that operation doesn’t make any sense at all. This is perfectly valid code according to the type system in Scala, which is a static type system. The question is why is it valid. It is valid because of subtyping and more precisely, because of variance, which exists in type system such as Scala’s where parametric polymorphism and subtyping are combined. In this particular case, is the outcome of the session above any better than in programming languages with a uni-type type system such as Python and Ruby? The answer is no.

This kind of misfortune with subtyping can lead to deceitful bugs in your code. One would hope that an advanced static type system such as the one in Scala would catch a bug like this, i.e., that you would be made aware of the bug at compile-time.

Let’s consider a programming language with a type system based on parametric polymorphism, but not on subtyping. Haskell and Idris have type systems that fit this description. For the purposes of this post, I don’t need dependent types, hence I will focus on Haskell, because it has a simpler type system than Idris. Here is an equivalent session to the one above, but this time with the Glasgow Haskell Compiler:

GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/marko/.ghci
Prelude> import qualified Data.Map as Map
Prelude Map> m = Map.fromList [("Lorem", 1), ("ipsum", 2)]
Prelude Map> m
fromList [("Lorem",1),("ipsum",2)]
Prelude Map> import qualified Data.Set as Set
Prelude Map Set> s = Set.fromList ["dolor", "sit", "amet"]
Prelude Map Set> s
fromList ["amet","dolor","sit"]
Prelude Map Set> s `Set.union` m

<interactive>:7:15: error:
    • Couldn't match expected type ‘Set.Set [Char]’
                  with actual type ‘Map.Map [Char] Integer’
    • In the second argument of ‘Set.union’, namely ‘m’
      In the expression: s `Set.union` m
      In an equation for ‘it’: it = s `Set.union` m

Therefore, if you try to add a map to a set in Haskell, its type system will simply reject it as ill-typed. The program above does not compile in Haskell. The GHC compiler will prevent us from introducing the bug that the Scala Compiler happily accepts.

Functional programming heavily relies on type systems with parametric polymorphism. On the other hand, object-oriented programming is often accompanied by subtyping polymorphism. Martin Odersky, the main author of Scala, likes to say that Scala is an example that shows that functional programming and object-oriented programming are not at odds. With the example above I would argue against that: the interaction between subtyping and parametric polymorphism asks for trouble.