Upgrade to Pro — share decks privately, control downloads, hide ads and more …

The trouble with subtyping: An introduction to ...

The trouble with subtyping: An introduction to typebounds and variance

Many people come to Scala from object-oriented languages with class-based inheritance. Nevertheless the complexity inherent in subtyping is often one of the biggest hurdles for them. In this talk I will explain type bounds, covariance, and contravariance from the ground up.

This talk was held at Scala Love Conference 2020.

Daniel Westheide

April 18, 2020
Tweet

More Decks by Daniel Westheide

Other Decks in Programming

Transcript

  1. 1 1 8 . 0 4 . 2 0 2

    0 S C A L A L O V E C O N F E R E N C E The trouble with subtyping An introduction to type bounds and variance Daniel Westheide Twitter: @kaffeecoder
  2. About me 2 • senior consultant at INNOQ • co-organizer

    of ScalaBridge Berlin • I like writing about Scala
  3. 3 • Scala from Scratch: Exploration: – Ebook: https://leanpub.com/scala-from-scratch- exploration/

    – Hardcover: https://www.blurb.com/b/9959223-scala- from-scratch-exploration • Scala from Scratch: Understanding: – Ebook with discount for Scala Love attendees: http://leanpub.com/scala-from-scratch-u nderstanding/c/scalalove2020
  4. Subclassing 5 class A { def magic(x: Int): Int =

    x * x } class B extends A • class-oriented • subclassing is – code sharing – nominal subtyping: B is-an A
  5. 6

  6. In this talk... 7 • learn about type bounds and

    variance in Scala • demystifying covariant and contravariant positions • strategies for avoiding the complexity of variance • any changes in Scala 3?
  7. Modelling caffeinated beverages 9 abstract class CaffeinatedBeverage { def caffeineContent:

    Int } final case class FilterCoffee(override val caffeineContent: Int, region: String) extends CaffeinatedBeverage final case class BlackTea(override val caffeineContent: Int) extends CaffeinatedBeverage final case class CuteMate(override val caffeineContent: Int) extends CaffeinatedBeverage
  8. Choosing a beverage 10 object CaffeinatedBeverage { def choose(x: CaffeinatedBeverage,

    y: CaffeinatedBeverage): CaffeinatedBeverage = if (x.caffeineContent >= y.caffeineContent) x else y } • choose the beverage with the highest caffeine content • we lose precision in the return type • we can mix different subtypes of CaffeinatedBeverage
  9. Parametric polymorphism? 11 object CaffeinatedBeverage { def choose[A](x: A, y:

    A): A = if (x.caffeineContent >= y.caffeineContent) x else y } • choose should abstract over the type of beverage • doesn‘t compile • choose implementation makes certain assumptions about A
  10. Upper type bounds 12 object CaffeinatedBeverage { def choose[A <:

    CaffeinatedBeverage](x: A, y: A): A = if (x.caffeineContent >= y.caffeineContent) x else y } • Adds a constraint to the type parameter A • The assumptions needed to implement choose are satisfied
  11. Upper type bounds in action (1) 13 scala> val guji

    = FilterCoffee(69, "Ethiopia") guji: FilterCoffee = FilterCoffee(69,Ethiopia) scala> val blueBatak = FilterCoffee(75, "Indonesia") blueBatak: FilterCoffee = FilterCoffee(75,Indonesia) scala> val chosen = CaffeinatedBeverage.choose(guji, blueBatak) chosen: FilterCoffee = FilterCoffee(75,Indonesia)
  12. Upper type bounds in action (2) 14 scala> val guji

    = FilterCoffee(69, "Ethiopia") guji: FilterCoffee = FilterCoffee(69,Ethiopia) scala> val mate = CuteMate(95) mate: CuteMate = CuteMate(95) scala> val chosen: FilterCoffee = CaffeinatedBeverage.choose(guji, mate) ^ error: type mismatch; found : CuteMate required: FilterCoffee scala> val chosen = CaffeinatedBeverage.choose(guji, mate) chosen: Product with CaffeinatedBeverage with java.io.Serializable = CuteMate(95)
  13. Modelling caffeine sources 16 abstract class CaffeineSource[A <: CaffeinatedBeverage] {

    def pull(): A } class CuteMateSource extends CaffeineSource[CuteMate] { override def pull(): CuteMate = CuteMate(85) } class FilterCoffeeSource extends CaffeineSource[FilterCoffee] { override def pull(): FilterCoffee = FilterCoffee(69, "Ethiopia") }
  14. Using caffeine sources 17 • example: Agile Fragile, a consulting

    company • not picky • they can turn caffeine from any source into code object AgileFragile { val caffeineSource: CaffeineSource[CaffeinatedBeverage] = ??? }
  15. Oh no! 18 scala> val source: CaffeineSource[CaffeinatedBeverage] = new FilterCoffeeSource

    ^ error: type mismatch; found : FilterCoffeeSource required: CaffeineSource[CaffeinatedBeverage] Note: FilterCoffee <: CaffeinatedBeverage (and FilterCoffeeSource <: CaffeineSource[FilterCoffee]), but class CaffeineSource is invariant in type A. You may wish to define A as +A instead.
  16. A covariant caffeine source 20 abstract class CaffeineSource[+A <: CaffeinatedBeverage]

    { def pull(): A } scala> val source: CaffeineSource[CaffeinatedBeverage] = new FilterCoffeeSource source: CaffeineSource[CaffeinatedBeverage] = FilterCoffeeSource@336a1b7d
  17. Covariance in Scala collections 21 • immutable collection types are

    usually covariant • examples: – Seq[+A] – List[+A] – Option[+A]
  18. How others see programmers... 23 final case class Deliverable(description: String)

    class Programmer[A <: CaffeinatedBeverage] { def transform(caffeine: A, feature: String): Deliverable = Deliverable(feature) }
  19. How they deliver at Startupr 24 object Startupr { def

    deliver( feature: String, programmer: Programmer[CuteMate], caffeineSource: CaffeineSource[CuteMate] ): Deliverable = programmer.transform(caffeineSource.pull(), feature) val cto = new Programmer[CaffeinatedBeverage] val caffeineSource: CaffeineSource[CuteMate] = new CuteMateSource def main(args: Array[String]): Unit = deliver("emojis", cto, caffeineSource) } • Does not compile! • expected Programmer[CuteMate], found Programmer[CaffeinatedBeverage]
  20. A contravariant programmer 26 class Programmer[-A <: CaffeinatedBeverage] { def

    transform(caffeine: A, feature: String): Deliverable = Deliverable(feature) } scala> val cto = new Programmer[CaffeinatedBeverage] cto: Programmer[CaffeinatedBeverage] = Programmer@76e78d0 scala> val resource: Programmer[CuteMate] = cto resource: Programmer[CuteMate] = Programmer@76e78d0
  21. Covariant positions 28 scala> val pullFilterCoffee = () => FilterCoffee(69,

    "Ethopia") pullFilterCoffee: () => FilterCoffee = $ $Lambda$5188/0x00000008019ff440@50695810 scala> val pullBeverage: () => CaffeinatedBeverage = pullFilterCoffee pullBeverage: () => CaffeinatedBeverage = $ $Lambda$5188/0x00000008019ff440@50695810 • FilterCoffee is-a CaffeinatedBeverage • a function returning FilterCoffee is-a function returning CaffeinatedBeverage
  22. Covariant return types 29 trait Function0[+R] { def apply(): R

    } • Scala has covariant return types (just like Java) • example: Function0 is covariant in its return type R • the same principle applies to methods
  23. Covariance: The rules of the game 30 • If a

    class or trait is covariant in a type parameter A, it can only be used in covariant positions: – as a return type of a method – as a type of an immutable field – as a lower type bound for the type of a method parameter
  24. Contravariant positions 31 def hasMoreCaffeineContent( x: CaffeinatedBeverage, y: CaffeinatedBeverage ):

    Boolean = x.caffeineContent > y.caffeineContent val filterCoffees: List[FilterCoffee] = List( FilterCoffee(69, "Ethiopia"), FilterCoffee(75, "Indonesia") ) val sortedCoffees = filterCoffees.sortWith(hasMoreCaffeineContent) • FilterCoffee is-a CaffeinatedBeverage • a function expecting CaffeinatedBeverage is-a function expecting FilterCoffee
  25. Contravariant input types 32 trait Function1[-T1, +R] { def apply(v1:

    T1): R } • Scala functions are contravariant in their input types • the same principle applies to methods
  26. Contravariance: The rules of the game 33 • If a

    class or trait is contravariant in a type parameter A, it can only be used in contravariant position • it can only occur as a type of a method parameter
  27. A mutable caffeine source? 35 abstract class CaffeineSource[+A <: CaffeinatedBeverage]

    { def pull(): A def refill(a: A): Unit = () } • This doesn‘t compile! • The covariant type A occurs in contravariant position
  28. A mutable caffeine source! 36 abstract class CaffeineSource[A <: CaffeinatedBeverage]

    { def pull(): A def refill(a: A): Unit = () } • If a type parameter occurs in both covariant and contravariant positions, it must be invariant • This means that mutable classes must be invariant in their type parameters
  29. Motivating invariance 37 String[] strings = new String[] { "one",

    "two" }; Object[] objects = strings; // because arrays are covariant objects[1] = 42; // java.lang.ArrayStoreException: java.lang.Integer • Java arrays are covariant • The compiler allows you to sneak values of the wrong type into an array • Scala plays it safe: Array[A] is invariant
  30. Prepending elements to a list 39 scala> val strings =

    "a" :: "b" :: "c" :: Nil strings: List[String] = List(a, b, c) sealed abstract class List[+A] { def ::(elem: A): List[A] = new ::(elem, this) } • This doesn‘t compile! • List is covariant in A • A occurs in contravariant position in the :: method
  31. Prepending with lower type bounds 40 sealed abstract class List[+A]

    { def ::[B >: A](elem: B): List[B] = new ::(elem, this) } scala> val coffees = FilterCoffee(69, "Ethiopia") :: Nil coffees: List[FilterCoffee] = List(FilterCoffee(69,Ethiopia)) scala> val beverages: List[CaffeinatedBeverage] = CuteMate(95) :: coffees beverages: List[CaffeinatedBeverage] = List(CuteMate(95), FilterCoffee(69,Ethiopia)) • We need to add a type parameter B to the prepend method • The type B of prepended elements must be a super type of A • A is no longer used in contravariant position • The result is a List[B]
  32. Common subclassing use cases 42 • Modules – trait UserRepository

    – class PostgresUserRepository extends UserRepository • Typeclass hierarchies – trait Semigroup[A] – trait Monoid[A] extends Semigroup[A] • Algebraic data types
  33. Algebraic data types 43 sealed abstract class User extends Product

    with Serializable object User { final case class Authenticated(id: Long, name: String) extends User final case class Anonymous(sessionId: String) extends User } • Subclassing is an implementation detail of algebraic data types in Scala • Other languages don‘t use subclassing for this – Haskell: data constructors – Rust: variants
  34. Can‘t we use an invariant List? 44 sealed trait LinkedList[A]

    { def ::(a: A): LinkedList[A] = LinkedList.::(a, this) } object LinkedList { final case class ::[A](head: A, tail: LinkedList[A]) extends LinkedList[A] final case class Nil[A]() extends LinkedList[A] } scala> val users = User.Anonymous("1ABC") :: User.Authenticated(1, "hans") :: Nil() ^ error: type mismatch; found : User.Anonymous required: User.Authenticated
  35. Hiding the subclasses 45 sealed abstract class User extends Product

    with Serializable object User { final case class Authenticated(id: Long, name: String) extends User final case class Anonymous(sessionId: String) extends User def authenticated(id: Long, name: String): User = Authenticated(id, name) def anonymous(sessionId: String): User = Anonymous(sessionId) } scala> val users = User.anonymous("1ABC") :: User.authenticated(1, "hans") :: Nil() users: LinkedList[User] = ::(Anonymous(1ABC),::(Authenticated(1,hans),Nil()))
  36. Algebraic data types in Scala 3 47 enum User {

    case Authenticated(id: Long, name: String) case Anonymous(sessionId: String) } scala> val users = User.Anonymous("1ABC") :: User.Authenticated(1, "hans") :: Nil() val users: LinkedList[User] = ::(Anonymous(1ABC),::(Authenticated(1,hans),Nil())) • Scala 3 enums generate subclasses • The generated apply factory methods hide the subclass type • Friendlier towards classes that are invariant in their type parameters
  37. Thank you! Questions? 48 Daniel Westheide [email protected] Twitter: @kaffeecoder Website:

    https://danielwestheide.com Krischerstr. 100 40789 Monheim am Rhein Germany +49 2173 3366-0 Ohlauer Str. 43 10999 Berlin Germany +49 2173 3366-0 Ludwigstr. 180E 63067 Offenbach Germany +49 2173 3366-0 Kreuzstr. 16 80331 München Germany +49 2173 3366-0 Hermannstrasse 13 20095 Hamburg Germany +49 2173 3366-0 Gewerbestr. 11 CH-6330 Cham Switzerland +41 41 743 0116 innoQ Deutschland GmbH innoQ Schweiz GmbH www.innoq.com