Path-Dependent Types in Scala

1. Overview

Scala has a strong type system that allows us to write code with more restrictions and checks at compile time. By encoding logic in the type system, we can detect errors at compile-time without introducing them to the runtime.

One feature, in particular, is a kind of dependent typing called path-dependent types. In this article, we’re going to introduce path-dependent types and their use cases.

2. Path-Dependent Types

2.1. Type Members and Path-Dependent Types

In Scala, traits can have a type member:

trait Input {
  type Output
  val value: Output
}

Here the Input trait has the Output type member. The type of value is Output, which is path-dependent. This means that the type of value varies based on the implementation of the Input trait.

Dependent types can be used as type parameters. The following function is a dependent function because the output of our function is dependent on its input:

def dependentFunc(i: Input): i.Output = i.value

Let’s create some instances from the Input trait and examine our dependentFunc behavior:

def valueOf[T](v: T) = new Input {
  type Output = T
  val value: T = v
}

val intValue    = valueOf(1)
val stringValue = valueOf("One")

assert(dependentFunc(intValue) == 1)
assert(dependentFunc(stringValue) == "One")

As we can see, the output type of dependentFunc varies between different inputs.

2.2. Inner Classes and Path-Dependent Types

In Scala, classes can have other classes as members:

class Foo {
  class Bar
}

val f1 = new Foo 
val b1: f1.Bar = new f1.Bar 
val f2 = new Foo 
val b2: f2.Bar = new f2.Bar
assert(b1 != b2) 

3. Examples

3.1. Typed Key-Value Datastore

Assume we have a key-value data store. All keys are String, but the ValueType of each Key may differ from others. We can encode the ValueType of each key-value in the Key type. When setting the key-value, we can encode the value with the proper encoder of the key.ValueType. Thus making key.ValueType a path-dependent type.

First, let’s create an abstract class that contains the name of the key and the value type:

abstract class Key(val name: String) {
  type ValueType
}

Whenever we have an instance of Key, we can access the value type of that key by referencing the ValueType member.

Now let’s introduce two general operations of common key-value stores, set and get, in the Operations tait:

trait Operations {
  def set(key: Key)(value: key.ValueType)(implicit enc: Encoder[key.ValueType]): Unit
  def get(key: Key)(implicit decoder: Decoder[key.ValueType]): Option[key.ValueType]
}

In addition to the key parameter, the set method has a second parameter group, where we get the value type of the key, key.ValueType. Also, in the third parameter section, we’re getting the Encoder as an implicit parameter. In this case, the encoder is dependent on the ValueType of key-value (Decoder[key.ValueType]).

The get method has a subtle difference, the output type of the get method is Option[k.ValeType], making the output dependent on the key value. The set method is a dependent function.

Now, it’s time to implement them in our Database class and other utilities that we need:

case class Database() extends Operations {

  private val db = mutable.Map.empty[String, Array[Byte]]

  def set(k: Key)(v: k.ValueType)(implicit enc: Encoder[k.ValueType]): Unit =
    db.update(k.name, enc.encode(v))

  def get(
    k: Key
  )(implicit decoder: Decoder[k.ValueType]): Option[k.ValueType] = {
    db.get(k.name).map(x => decoder.encode(x))
  }

}

Let’s add a helper function to create keys in the companion object:

object Database {
  def key[Data](v: String) =
  new Key(v) {
    override type ValueType = Data
  }
}

To store values in a key-value store, we need an Encoder type-class to encode values to a Byte[Array]:

trait Encoder[T] {
  def encode(t: T): Array[Byte]
}

We need a String and Double instance of Encoder, let’s define it in Encoder companion object:

object Encoder {
  implicit val stringEncoder: Encoder[String] = new Encoder[String] {
    override def encode(t: String): Array[Byte] = t.getBytes
  }

  implicit val doubleEncoder: Encoder[Double] = new Encoder[Double] {
    override def encode(t: Double): Array[Byte] = {
      val bytes = new Array[Byte](8)
      ByteBuffer.wrap(bytes).putDouble(t)
      bytes
    }
  }
}

Also, let’s define the Decoder type-class and it’s instances to convert back values from Byte[Array] to its original T type:

trait Decoder[T] {
  def encode(d: Array[Byte]): T
}

object Decoder {
  implicit val stringDecoder: Decoder[String] = (d: Array[Byte]) =>
    new String(d)
  implicit val intDecoder: Decoder[Double] = (d: Array[Byte]) =>
    ByteBuffer.wrap(d).getDouble
}

Now, we are ready to create our key-value database and test our put and get operations:

val db = Database()
import Database._
val k1 = key[String]("key1")
val k2 = key[Double]("key2")

db.set(k1)("One")
db.set(k2)(1.0)
assert(db.get(k1).contains("One"))
assert(db.get(k2).contains(1.0))

In this example, using dependent-typing prevents us from writing duplicate and unnecessary codes, and it helps us to apply ad-hoc polymorphism to the set and get API.

3.2. Parental Award and Punishment Discipline

In this section, we are going to introduce another use case of dependent typing. Assume we want to model parental disciplines of punishment and reward. All parents can reward any child, but they can’t punish the children of others:

case class Parent(name: String) {
  class Child

  def child = new this.Child

  def punish(c: this.Child): Unit =
    println(s"$name is punishing $c")

  def reward(c: Parent#Child): Unit =
    println(s"$name is rewarding $c")
}

The argument of punish method is dependent on this.Child type, making it a type-dependent argument. Therefore, if we have two Parent instances, john, and scarlet, john can punish his own children, but he cannot punish scarlet’s children:

val john = Parent("John")
val scarlet = Parent("Scarlet")

john.punish(john.child)
// john.punish(scarlet.child) //Compile time error

Using dependent typing on the punish argument helps us to prevent running a punish on an irrelevant object at compile time.

4. Conclusion

In this article, we looked at path-dependent types in Scala. The path-dependent types in Scala are good ways to reduce these bugs in runtime and encode the logic in the type system. This reduces the extra effort in writing manual tests.

As always, the code is available over on GitHub.