Scala

Literal Types: A Case Study

Future versions of Scala will be equipped with a new language feature called literal types. Originally only available in Dotty, Miles Sabin went at great lengths to implement this feature in Typelevel Scala and in mainline Scala. His pull request was recently merged, whereby literal types will officially become part of Scala 2.13, expected to be released in spring 2018.

This article is a case study of literal types, inspired from our experience with Pine which is a functional library for HTML/XML. To aid adoption, we decided to migrate our code base to it and were pleasantly surprised by the results. Although IDE support for literal types is still spotty, I figured it is a feature many users can already benefit from. This article explains how literal types can help improve the expressiveness of your code and reduce boilerplate.

Literal Types

I will start with a couple of basic examples to get some intuition of what a singleton type is. To run those examples, I recommend Typelevel Scala's REPL which itself is based on Ammonite:

% curl -s https://raw.githubusercontent.com/typelevel/scala/typelevel-readme/try-typelevel-scala.sh | bash
@ repl.compiler.settings.YliteralTypes.value = true

Alternatively, follow the sbt instructions here. Note that it is possible to use Typelevel Scala with support for multiple platforms (JVM, JavaScript and LLVM) and versions (2.11, 2.12).

With literal types enabled, any literal like a string, integer, boolean etc. now becomes a valid type:

@ 42: 42
res1: Int = 42

@ 42: 41
cmd2.sc:1: type mismatch;
 found   : Int(42)
 required: 41
val res2 = 42: 41
           ^
Compilation Failed

As the result shows, 42 continues to be an integer, but it also has a more concrete type which is 42.

A concrete example where this could be a useful property is a function that should only take a particular string:

def f(value: "a"): Unit = {}

f("a")  // Works
f("b")  // Fails

If you would like to create an immutable variable (val) from a literal value, you will find that the literal type is not retained:

val str = "hello"
str: "hello"  // Fails

The solution is to use the final modifier:

final val str = "hello"
str: "hello"  // Works

Another useful property is that literal values inherit from Singleton:

"hello": Singleton              // Works
"hello": Singleton with String  // Works

We can use this property to constrain a type parameter. For example, we may want to create a list of literal values where every list item is equivalent:

class SingletonList[T <: Singleton](values: List[T])

new SingletonList(List(1, 1))  // Works
new SingletonList(List(1, 2))  // Fails

We can further narrow down the type of the singleton values. In the following example, we only allow string literals:

class StringSingletonList[T <: Singleton](values: List[T with String])
new StringSingletonList(List("a", "a"))  // Works
new StringSingletonList(List(1, 1))      // Fails

Note that the following will not work due to this issue:

class StringSingletonList[T <: Singleton with String](values: List[T])

Another useful feature is the ValueOf implicit. It allows us to retrieve the value of a literal:

def text[T <: Singleton with String](implicit vo: ValueOf[T]): String = vo.value
text["test"]  // "test"

Strongly-typed ASTs

Now, we will look at a common example: defining a strongly-typed Abstract Syntax Tree (AST). As an example, we will consider HTML. As it is a constantly evolving standard with many extensions, any modeling effort is prone to fail. Let us look at a solution that strives for maximum type safety:

sealed trait Node
object Node {
  case class Text(text: String) extends Node
  abstract class Tag(val name      : String,
                     val children  : List[Node],
                     val attributes: Map[String, String]) extends Node {
    type Self <: Tag
    def update(children  : List[Node],
               attributes: Map[String, String]): Self
    def attr(name: String): Option[String] = attributes.get(name)
    def attr(name: String, value: String): Self =
      update(children, attributes + (name -> value))
  }
}

object Html {
  case class A(children  : List[Node]          = List.empty,
               attributes: Map[String, String] = Map.empty
              ) extends Node.Tag("a", children, attributes) {
    override type Self = A
    override def update(children  : List[Node],
                        attributes: Map[String, String]): Self =
      copy(children, attributes)
    def href: Option[String] = attr("href")
    def href(value: String): Self = attr("href", value)
  }
}

As you can see, there is a fair amount of boilerplate in defining a new tag type. We always need to define the case class parameters, override Self and define update.

On the upside, you can now conveniently instantiate an <a> node:

val node = Html.A().href("http://google.com/")  // : Html.A

Since we used call site type polymorphism, href returns back an Html.A object instead of Tag. If we define more attributes and call them in a chain, we will retain the original type in the end.

By design, there is no other way to instantiate the same node given that Tag is abstract: A function taking a Tag.Script cannot be called with a Tag.A argument. This gives us additional type safety, but if you wanted to construct a tag dynamically, you would need a match that is aware of all the available classes and then performs a dynamic dispatch:

def create(name      : String,
           children  : List[Node],
           attributes: Map[String, String]): Node.Tag =
  name match {
    case "a" => Html.A(children, attributes)
    ...
  }

Unfortunately, such a solution is far from extensible. Adding custom tags will require to either change create() or to define a custom function.

To summarise, there are two issues with this approach:

  • Boilerplate: For better type safety, we need to repeat a few definitions for each tag that we want to define.
  • Extensibility: For each unsupported tag, we need to create a separate class and define a function that performs dynamic dispatch.

A possible solution using literal types

Instead of introducing separate classes for tags, we will restrict ourselves to only one with the key difference that the tag name becomes a literal type. This allows us to greatly simplify our earlier solution:

sealed trait Node
object Node {
  case class Text(text: String) extends Node
  case class Tag[T <: Singleton](
    name      : T with String,
    children  : List[Node]          = List.empty,
    attributes: Map[String, String] = Map.empty
  ) extends Node {
    def attr(name: String): Option[String] = attributes.get(name)
    def attr(name: String, value: String) =
      copy(attributes = attributes + (name -> value))
    def as[U <: Singleton with String](
      implicit vo: ValueOf[U]
    ): Tag[U] = {
      assert(name == vo.value)
      this.asInstanceOf[Tag[U]]
    }
  }
}

object Html {
  type A = Node.Tag["a"]
  val  A = Node.Tag("a")

  type B = Node.Tag["b"]
  val  B = Node.Tag("b")
}

Now we can write:

Html.A.attr("href", "http://google.com/")
  // : Node.Tag["a"] = Tag("a", List(), Map("href" -> "http://google.com/"))

Since the tag name is encoded in every Tag instance as a type parameter, we retain the type safety from our earlier example that used sub-typing:

def renderNode(n: Html.A): String = ""
renderNode(Html.A)  // Works
renderNode(Html.B)  // Fails

Since Html.A is just an alias for Node.Tag("a"), we do not need the dynamic dispatch anymore and can instantiate nodes without any overhead. A side-effect is that our literal-based solution is more extensible:

val customTag = Node.Tag("custom-tag")

In the definition of Tag, we used the ValueOf type class for implementing a safe runtime cast. It can be used as follows:

val dynamicTagName: String = "a"

val tag = Node.Tag(dynamicTagName)  // : Node.Tag[dynamicTagName.type]
tag.as["a"]                         // : Node.Tag["a"]
tag.as["b"]                         // Fails

One last thing which the solution above left out were attributes. Earlier, we defined two href functions on the A object. This is obviously not possible anymore, but Scala offers a convenient alternative: implicits. Those can be used in conjunction with singleton types.

implicit class AttributesA(node: Html.A) {
  def href: Option[String] = node.attr("href")
  def href(value: String): Html.A = node.attr("href", value)
}

val node = Html.A.href("http://google.com/")

Let us revisit the two problems we identified with the inheritance-based approach and see how literal types compare:

  • Boilerplate: Defining a new tag merely consists of creating a type and a def, as well as an implicit class for the attributes. The boilerplate code has been reduced to a minimum.
  • Extensibility: We do not have to define a separate class for each tag. Tags can now be instantiated directly without the need for dynamic dispatch.

IDE support

In the beginning, I mentioned IDE support as problematic. One reason we defined the type alias A is better IDE support: "a" is not recognised as a valid type yet by IntelliJ. Another issue currently is that implicits are not resolved properly.

Summary

We have seen how literal types clearly outperform an approach based on sub-typing. I hope I piqued your interest in trying out literal types yourself. If you would like to learn more about literal types, please refer to the official documentation.

How do you plan to use literal types in your projects? Let me know below in the comments.