Some Notes in Hostility Toward Subtyping

What follows is a session of thinking out loud, so it’s not to be taken too seriously.

The more I think about it, the more I convince myself that the idea of subtyping and class hierarchies is a mistake. “Inheritance” is a good way to lock down a design so that it becomes rigid and brittle. If you remember your (now scorched, I trust) GoF book, its main cargo was “composition over inheritance”. So why do we want this mechanism at all? Because we want type substitution. We say that if X is a subtype of Y, then X can be substituted wherever Y is expected. Informally, we want to say that an X is a Y. But what does this mean? It means that the set of all values in X is a subset of all the values in Y. So if you have a value x in X, then x is also in Y. In other words, X implies Y, or (X => Y). Hang on. This is just the type signature for a function.

When we observe this, we realise that we can substitute functions for subtyping. Moreover, we can make those functions implicit (as in Scala) and then type substitution will work just as if we were using subtypes (hopefully without loss of type inference). As a bonus, our implicit type substitutions have scope, while subtyping is a global declaration.

For example, take a look at the function type (A => B), recalling that this conceptually the same as saying “A implies B”, or even “A is a subtype of B”. Using subtyping, we could have types Foo and Bar, and say “Bar extends Foo”. But instead of subtyping, in Scala we could have an implicit function:

implicit def fooBar(b: Bar): Foo = b.foo

The easiest way to implement this is to have Bar wrap a value of type Foo by accepting it in its constructor. Then the Bar.foo method simply returns this value. But it can really be implemented any way we want. For example, if both Foo and Bar take a parameter of type Int, then we can extract it from one when constructing the other.

There’s a slight problem with implicit functions like this. Somebody else may have defined a function with the same type already, with a totally different intent. To remedy that, we can create a type for a specific kind of conversion to Foo; one that implies the relation we want to express. Something like…

trait IsAFoo[A] {
  def apply(a: A): Foo
}

This is now unambiguous. This kind of construct is a typeclass. IsAFoo classifies all types that imply type Foo. We can supply an implicit instance of this typeclass for Bar:

implicit val bar_is_a_foo = new IsAFoo[Bar] {
  def apply(b: Bar) = b.foo
}

And wherever we want to accept something that “is a” Foo, we accept an implicit parameter as evidence that it is indeed a Foo.

implicit def doSomethingWithFoo[A](implicit foo: IsAFoo[A])(a: A) = foo(a).methodOnFoo

We can call this method with a value of type Bar, because of the existence of the implicit instance bar_is_a_foo. In fact, Scala has an even nicer syntax for this, using “view bounds”. I leave it to you to check that out. What I want to impress on you is how flexible typeclasses are. We’re not constrained to using this mechanism to substitute for subtyping. We can use it to do the converse, i.e. supertyping an existing type. Or we can have the conversion go both ways to express isomorphisms between types. The pattern here is that we want to be able to state any kind of relation between types.

If Scala had the ability to state functional dependencies, the typeclass mechanism truly could obviate subtyping, with the added bonus that we could state any kind of type-level relation that we want, rather than just type order. I could talk about the downside of this, but… I could go on forever.

Variance of Functors

So, speaking of type order, there’s a tie-in here with variance. This is one of the things that trips people up when thinking about class hierarchies. I know it trips me up. But variance is much easier to reason about if we think of the subtype/supertype relation as just a function.

To compare, here’s what Wikipedia has to say about variance in class hierarchies:

If class B is a subtype of class A, then all member functions of B must return the same or narrower set of types as A; the return type is said to be covariant. On the other hand, the member functions of B must take the same or broader set of arguments compared with the member functions of A; the argument type is said to be contravariant. The problem for instances of B is how to be perfectly substitutable for instances of A. The only way to guarantee type safety and substitutability is to be equally or more liberal than A on inputs, and to be equally or more strict than A on outputs.

OK, but why is it the case that this is the only way to guarantee substitutability and type-safety? To understand that, it helps to throw away the notion of “subtype”, and simply think only in terms of functions, instead of the mixed notions of “subtype” and “member function”. Try translating that snippet from Wikipedia so that it’s worded in terms of functions. It gets pretty convoluted.

Proceeding from the premise that functions and subtype relations are interchangeable, we can derive a definition of co- and contravariance simply from the definition of substitutability. We start with this:

If B is a subtype of A, then every subtype of B is also a subtype of A, and every supertype of A is also a supertype of B.

Now, if we take (A <: B) to mean “A is a subtype of B”, and (A => B) to mean “function from A to B”, or equivalently “A implies B”, we can write this property as:

(A <: B) <==> ((B <: C) => (A <: C)) and ((C <: A) => (B <: C))

Remember that you can substitute functions for subtyping and vice versa, so any (=>) sign above can be replaced with the (<:) sign, or the other way around, and the meaning stays intact. So let’s restate this property purely in terms of functions: If there exists a function from B to A, then for every function from C to B there exists a function from C to A, and for every function from A to C there exists a function from B to C. (B => A) <==> ((C => B) => (C => A)) and ((A => C) => (B => C))

Moving (B => A) to the left of the <==> sign, we can infer two properties of (B => A):

(B => A) => (C => B) => (C => A)
and
(B => A) => (A => C) => (B => C)

Recalling that function application is logical implication, both of these properties evaluate to true, for all A, B, and C. Let’s use Wolfram Alpha to confirm this for us.
See here and here.

Let’s now say that C is a fixed type. Remembering what we did above with typeclasses, this gives rise to two such typeclasses, representing (C => A) and (A => C), respectively, for all A:

trait FromC[A] {
  def fromC(c: C): A
}

trait ToC[A] {
  def toC(a: A): C
}

To restate the properties above:

(B => A) => FromC[B] => FromC[A]
(B => A) => ToC[A] => ToC[B]

In other words, mapping a function (B => A) over FromC[B] results in FromC[A]. So the implication is preserved across the mapping. Mapping a function (B => A) over ToC[A] results in ToC[B]. So the implication is reversed across the mapping. This means that FromC is a covariant functor and ToC is a contravariant functor, by the definition of co- and contravariance. So now we have anchored the notion of substitutability to the variance of functors. For reference, here’s my off-the-cuff definition of co- and contravariance, along with some preliminaries:

Definition of Higher-Order Function
A higher-order function (HOF) is a function that takes another function as its argument.

Definition of covariance
A unary type constructor T[_] is a covariant functor if and only if there exists a HOF with the following type, for all A and B:
(A => B) => T[A] => T[B].

Definition of contravariance
A type constructor T[_] is a contravariant cofunctor if and only if there exists a HOF with the following type, for all A and B:
(B => A) => T[A] => T[B].

Note that these last two are exactly the properties above that we got for FromC and ToC, which we derived directly from the definition of subtype and supertype.

Conclusion

The benefits of subtyping, namely type substitution, can be expressed more naturally with a mechanism for classifying types.

Advertisement