Existential Types – Make OOP Great Again!

Julien Richard-Foy

Scala Days – June 1st, 2017


http://julienrf.github.io/2017/existential-types

Outline

1 Existential types Abstract type members in a nutshell

1.1 Introduction

Expression

A problem well put is half-solved

John Dewey.

Complexity

Breaking down problems into simpler problems

Breaking down problems into simpler problems

Modularization and generalization

Means of abstraction

def identity[A](a: A): A

1.2 Square of abstraction

Scala square of abstraction (1)

value type
parameter
abstract member

Value parameters

class Disc(radius: Double) {

  def area: Double = Pi * radius * radius

}
def printArea(disc: Disc): Unit = println(disc.area)
val disc = new Disc(123)
printArea(disc)

Scala square of abstraction (2)

value type
parameter (x: Int) (f: Int => Int)
abstract member

Abstract value members

abstract class Disc {

  def radius: Double

  def area: Double = Pi * radius * radius

}
def printArea(disc: Disc): Unit = println(disc.area)
val disc = new Disc { val radius = 123 }
printArea(disc)

Scala square of abstraction (3)

value type
parameter (x: Int) (f: Int => Int)
abstract member def x: Int def f(y: Int): Int

Parameters vs abstract members

Type parameters

trait Invertible[A] {
  def invert(a: A): A
}
def invertLaw[T](t: T)(implicit invertible: Invertible[T]): Unit =
  assert(invertible.invert(invertible.invert(t)) == t)
implicit val invertibleInt: Invertible[Int] =
  new Invertible[Int] { def invert(n: Int) = -n }

invertLaw(42)

Scala square of abstraction (4)

value type
parameter (x: Int) (f: Int => Int) [A] [F[_]]
abstract member def x: Int def f(y: Int): Int

Abstract type members

trait Invertible {
  type A
  def invert(a: A): A
}
def invertLaw[T](t: T)(implicit invertible: Invertible { type A = T }): Unit =
  assert(invertible.invert(invertible.invert(t)) == t)
implicit val invertibleInt: Invertible { type A = Int } =
  new Invertible { type A = Int; def invert(n: Int) = -n }

invertLaw(42)

Scala square of abstraction (5)

value type
parameter (x: Int) (f: Int => Int) [A] [F[_]]
abstract member def x: Int def f(y: Int): Int type A type F[_]

2 Use cases

2.1 Encapsulation

Scala interface for *nix files API

object UnixFiles {
  def open(path: String): Int = …
  def read(file: Int): String = …
  def close(file: Int): Int = …
}
def readSomething(): Unit = {
  UnixFiles.read(42) // I can forge a file descriptor!
}

Hiding the File type

trait UnixFiles {
  type File
  def open(path: String): File
  def read(file: File): String
  def close(file: File): Int
}
def readSomething(files: UnixFiles): Unit = {
  files.read(42)
  //         ^^
  // Error: Type mismatch;
  //  found: Int
  //  required: files.File
}

Hiding the File type

def readSomething(files: UnixFiles): Unit = {
  val file = files.open("/foo")
  files.read(file) // I have no other choice than
                   // calling the `open` method to
                   // get a `File` instance
}

Why is it different from using an opaque type?

object UnixFiles {

  sealed trait File
  private case class FileImpl(value: Int) extends File

  def open(path: String): File = {
    …
    FileImpl(…)
  }

  def read(file: File): String = file match {
    case FileImpl(fileImpl) => …
  }

}

Why is it different from using an opaque type?

Encapsulation – summary

When to use this technique?

2.2 Modularization

User interface Component 

trait Component[State] {
  def view(state: State): Html
}

Counter component

object Counter extends Component[Int] {

  def view(state: Int): Html =
    <span>value = { state }</span>

  // … other methods defining how to update the state

}

Container component

class Container[State](child: Component[State]) extends Component[State] {
  
  def view(state: State): Html =
    <div class="container">{ child.view(state) }</div>

}

Tabs component

Tabs component

class Tabs(children: List[(String, Component[_]]))
  extends Component[Tabs.State[_]] {

  def view(state: Tabs.State[_]): Html = …

}

object Tabs {

  case class State[S](child: Component[S], childState: S)

}

Tabs component implementation

class Tabs(children: List[(String, Component[_]]))
  extends Component[Tabs.State[_]] {

  def view(state: Tabs.State[_]): Html =
    <div class="tabs">
      <ul>{ for ((label, _) <- children) yield <li>{ label }</li> }</ul>
      <div>
        { state.child.view(state.childState) }
      </div>
    </div>

}

Tabs component implementation

class Tabs(children: List[(String, Component[_]]))
  extends Component[Tabs.State[_]] {

  def view(state: Tabs.State[_]): Html =
    <div class="tabs">
      <ul>{ for ((label, _) <- children) yield <li>{ label }</li> }</ul>
      <div>
        { state.child.view(state.childState) }
//                         ^^^^^^^^^^^^^^^^
// type mismatch;
//  found   : state.childState.type (with underlying type _$1)
//  required: _$1
      </div>
    </div>

}

Tabs component implementation

class Tabs(children: List[(String, Component[_]]))
  extends Component[Tabs.State[_]] {

  def view(state: Tabs.State[_]): Html = {

    def helper[A](s: Tabs.State[A]): Html =
      s.child.view(s.childState)

    <div class="tabs">
      <ul>{ for ((label, _) <- children) yield <li>{ label }</li> }</ul>
      <div>{ helper(state) }</div>
    </div>
  }

}

Redesign Component with abstract type members

trait Component {

  type State

  def view(state: State): Html

}

Counter (again)

object Counter extends Component {

  type State = Int

  def view(state: State): Html = <span>value = { state }</span>

  // … other methods defining how to update the state
  
}

Container (again)

trait Container extends Component {

  val child: Component

  type State = child.State

  def view(state: State): Html =
    <div class="container">{ child.view(state) }</div>

}

Tabs – state (1)

class Tabs(children: List[(String, Component])) extends Component {

  case class State(child: Component)(childState: child.State)

}

Tabs – state (2)

class Tabs(children: List[(String, Component])) extends Component {

  trait State {
    val child: Component
    def childState: child.State
  }

}

Tabs – view implementation

class Tabs(children: List[(String, Component])) extends Component {

  def view(state: State): Html =
    <div class="tabs">
      <ul>{ for ((label, _) <- children) yield <li>{ label }</li> }</ul>
      <div>
        { state.child.view(state.childState) }
      </div>
    </div>

}

Modularization – summary

When to use this technique?

2.3 Type families

Type families

Type families

Naive solution

trait Plot {
  def setDataset(dataset: Dataset): Unit
  def getDataset: Dataset
}

trait Dataset

Naive solution – XYPlot 

trait XYPlot extends Plot {
  private var _dataset: XYDataset = _
  def setDataset(dataset: Dataset) = _dataset = dataset.asInstanceOf[XYDataset]
  def getDataset = _dataset
}

case class XYDataset(series: List[Series]) extends Dataset
case class Series(values: List[(Double, Double)])

Solution with abstract type members

trait Plot {
  type Dataset
  def setDataset(dataset: Dataset): Unit
  def getDataset: Dataset
}

XYPlot (again) 

trait XYPlot extends Plot {

  case class Dataset(series: List[Series])
  case class Series(values: List[(Double, Double)])

  private var _dataset: Dataset = _

  def setDataset(dataset: Dataset) = _dataset = dataset
  def getDataset = _dataset

}

Type families – summary

When to use this technique?

3 Summary

Summary

4 Questions?

5 Bonus

5.1 Embedding languages

Defining a language as a data type

sealed trait Expr
case class Lit(x: Double) extends Expr
case class Add(lhs: Expr, rhs: Expr) extends Expr
val twoPlusThree = Add(Lit(2), Lit(3))

Evaluating programs

def eval(expr: Expr): Double =
  expr match {
    case Lit(x)        => x
    case Add(lhs, rhs) => eval(lhs) + eval(rhs)
  }

Pretty-printing programs

def show(expr: Expr): String =
  expr match {
    case Lit(x)        => x.toString
    case Add(lhs, rhs) => print(lhs) ++ " + " ++ print(rhs)
  }

Generalizing interpreters

def fold[A](lit: Double => A, add: (A, A) => A): Expr => A = {
  case Lit(x)        => lit(x)
  case Add(lhs, rhs) => add(lhs, rhs)
}
val eval = fold[Double](identity, _ + _)

val show = fold[String](_.toString, _ ++ " + " ++ _)

Alternative encoding: language definition

trait ExprDsl {
  type Expr
  def lit(x: Double): Expr
  def add(lhs: Expr, rhs: Expr): Expr
}
trait Program extends ExprDsl {
  val twoPlusThree = add(lit(2), lit(3))
}

Alternative encoding: evaluation interpreter

trait ExprDsl {
  type Expr
  def lit(x: Double): Expr
  def add(lhs: Expr, rhs: Expr): Expr
}
trait Eval extends ExprDsl {
  type Expr = Double
  def lit(x: Double) = x
  def add(lhs: Double, rhs: Double) = lhs + rhs
}

Alternative encoding: interpreting programs

new Program with Eval {
  println(twoPlusThree) // 5
}
new Program with Show {
  println(twoPlusThree) // "2 + 3"
}

Alternative Finally tagless encoding

See also [C. Hofer et al. 2008], [J. Carette et al. 2009] and [B. Oliveira 2012]

Finally tagless encoding – extensibility

trait MulDsl extends ExprDsl {
  def mul(lhs: Expr, rhs: Expr)
}
trait MulEval extends Mul with Eval {
  def mul(lhs: Double, rhs: Double) = lhs * rhs
}

Type parameters vs type members (1)

trait HttpEndpoints[Req, Resp, Headers, Url] {
  …
}
trait Program[Req, Resp, Headers, Url]
  extends HttpEndpoints[Req, Resp, Headers, Url] {
  …
}

Type parameters vs type members (2)

trait HttpEndpoints {
  type Req
  type Resp
  type Headers
  type Url
  …
}
trait Program extends HttpEndpoints

Type parameters vs type members (3)

trait HttpEndpoints {
  type Req <: ReqLike
  type Resp
  type Headers
  type Url
  …
}
trait Program extends HttpEndpoints

Finally tagless encoding – summary

When to use this technique?