“If” statements at compile time

A while ago, I watched a talk from Netflix from the Scala days 2019, and the speaker Jeremy Smith said that a Scala program is actually made of two programs. The one that everybody knows, but also the one which happens at “compile time”.

Justin Luebke on unspash

“If” statements at run-time

When writing usual programs (think: a small script), we sometimes need to use “if” statements to ensure that the program does reasonable things. For example, a function which takes the square root of a number, could only run on positive numbers. This would result in an implementation like this:

def sqrt(x: Double): Double =
if x < 0 then throw new IllegalArgumentException("can't take square root of negative numbers")
else math.sqrt(x)

“If” statements at compile time

What kind of legality check would we want to do on generic types? Let’s have a look at an example (from the standard collection library).

trait RuntimeList[+A]:
def toMap[K, V]: Map[K, V]
class NonEmptyRuntimeList[+A](head: A, tail: Run-timeList[A]) extends RuntimeList[A]:
def toMap[K, V]: Map[K, V] = (head match {
case h: (K, V) => Map(h._1 -> h._2)
case _ => throw new RuntimeException("elements of the list must be pairs!")
}) ++ tail.toMap[K, V]
object EmptyRuntimeList extends RuntimeList[Nothing]:
def toMap[K, V]: Map[K, V] = Map.empty
@ new NonEmptyRuntimeList(3, EmptyRuntimeList).toMap[Int, String]
java.lang.RuntimeException: elements of the list must be pairs!
@ new NonEmptyRuntimeList((3, "hello"), EmptyRuntimeList).toMap[Int, String]
res2: Map[Int, String] = Map(3 -> "hello")
def toMap[K, V](using ev: A <:< (K, V)): Map[K, V]
[imaginary language]
if A is a pair then "let the thing compile"
else "crash, aka, compile error"
  • “if” statements about the run-time values corresponds to asking for given values of special types representing types equality or type inheritance relations at compile type

An equality check

In the previous section, we (re-)discovered the <:< “operator” on types. This one furiously resemble a “less than” operator which, as we saw, actually behaves like a “less than or equal to” operator (technical term: it is reflexive). What about an “equal to” operator? This one would be =:=, and here is an example of a usage.

def print()(using ev: Unit =:= A): String = print(ev(()))
def printAsPair[K, V](a: A)(using ev: A =:= (K, V)): String =
val (key, value) = ev(a)
s"$key: $value"
def print()(using A =:= Nothing): String = "Nothing there!"

What about “not equal”?

In some (probably rare) cases, you might want to forbid access to a given method for a specific type. You might expect a !=:= operator of sorts, but you might be disappointed discovering that it does not exist. Never fear, though, as we have options. Imagine that you have some “functional effect”IO[E, A]with two type parameters, E representing the type of error that can happen. You probably want to define a method def mapError[F](f: E => F): IO[F, A] . However, you might want to help your users by forbidding them to use this function if the error type is Nothing (indeed, if E =:= Nothing, then the user knows that the functional effect cannot fail, and it would be a pity for them to artificially re-introduce an error in the type system).

[imaginary language]
if A != Foo then "let it go"
else "crash, aka don't compile"
type IsNotNothing[A] <: Boolean = A match {
case Nothing => false
case _ => true
}
trait IO[E, A]:
// elided content ...
def mapError[F](f: E => F)(using IsNotNothing[E] =:= true): IO[F, A] = ??? // do your thing
val ioNothing: IO[Nothing, Int] = ???
ioNothing.mapError(_ => 2)
// [error] 18 | ioNothing.mapError(_ => 2)
// [error] | ^
// [error] |Cannot prove that IsNotNothing[Nothing] =:= (true : Boolean).

Other alternatives

Asking the compiler for evidence of a given type is not the only way to achieve such goal. In my opinion, however, it is still the best and I will argue why.

  • Using extension method: In Scala, you have the ability to do type safe monkey patching by adding methods to elements after their definition. Imagining that the `toMap` method on Lists does not exist, you could add it with
extension [K, V](ls: List[(K, V)])
def toMap: Map[K, V] = ???
  • your IDE will have a hard time helping you discover these methods. In the end, a language must help the developper be more productive, and learn faster. With the evidence pattern, your IDE will always show you that the method exists when browsing methods from the variable you manipulate (even if the evidence can’t be provided by the compiler)
  • if you generate Scala doc for your classes, they wont be where they belong: alongside your class definitions

Related works

At the beginning, we said that the compile phase is a proper program running. A program should be able to do more than “if” statements. Below, we mention some related topics going in that direction.

Typeclass derivations

The Scala compiler is able to derive automatically, and in a completely type-safe way, typeclasses. For example, if you have a typeclass generating JSON representations of Scala classes, all you will have to do will be to define how to do it for “primitive” types, and the compiler will compute, at compile time, the typeclasses for any case class (and more generally, any ADT). Examples of library allowing you to do that are [Magnolia] and [Shapeless]. And there even is [something built in Scala 3 itself]!

Counting at compile time

You can also make the compiler do integer computations. Check out [this blog post]. The opening sentence says it all: “Counting at compile time is one of the world’s simple pleasures”.

Derivatives at compile time

Since we mentioned Jeremy Smith from Netflix at the beginning of this blog post, it seems about right to mention the work he was referring to. His GitHub repo [baudrillard] exposes a proof of concept where you can define mathematical functions in the type system, and ask the compiler to compute their derivatives!

Closing words

The Scala compiler is amazing. With other similar technologies, you often have the feeling that you, as a programmer, “know better” (which, probably, explains why dynamically typed languages are still popular). Scala is different. You genuinely have the feeling that the compiler is there to help you, and even to guide you writing your code.

Mathematician, Scala enthusiast, father of two.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store