“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”.
When we (at least I) think about compilation, we oftentimes only think of it as a “static” process of checking that things have been wired up properly (e.g., right arguments at the right places). However, some compilers actually compute things while “compiling”, and they are able to help you in tremendous ways. Scala is one of them.
We are going to see examples for Scala 3, since it is the future, a future that is actually already there.
“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)The code that we wrote ensures that, when the run-time program passes through it, it does reasonable things. In this case, it won’t take the square root of a negative number. By throwing an exception, the function stops the program, and keeps it from continuing with an “illegal” state (note: in Scala, math.sqrt returns NaN for negative numbers, instead of crashing). In a production setting, this would be bad. But let’s leave that aside for a moment.
In Scala (3), this idea of checking the legality of a state of a run-time variable actually has an analogue when compiling. But what are the “run-time” variables at that time? Generic Types! Scala is a statically typed language, meaning that all types are known at compile time. Exactly the same way as “regular” variables are known at run-time. In theory (but as we’ll see, also in practice), this implies that the compiler can compute types, or check that types satisfy some properties.
“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).
Every Scala developper knows the List type. Lists have a type parameter, call it A, representing the type of the elements that the list will contain at run-time. For example, List[Int] will contain integers at run-time. There are many things that we can do, no matter what the generic type is. For example, taking the length of the list, getting the head or the tail. But some things can only be done if A has a certain shape. Lists have a toMap method, which is supposed to turn a list containing “pairs” into a Map from the first element of the pair to the second. However, in order for it to make sense, the generic type A would need to be exactly a pair (K, V), for two other types K and V. We could do the following at run-time (deliberately ugly):
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
Everything compiles, and we could verify the following:
@ 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")
This is silly, though, because since the generic type A is known when the program compiles, the compiler should be able to tell us before the run-time that we are doing something wrong!
The actual signature of the toMap method for list is this:
def toMap[K, V](using ev: A <:< (K, V)): Map[K, V]The A <:< (K, V)is merely a type saying that “the type A must be a subtype of the type (K, V)”. Meaning: if the compiler manages to give us an (implicit/given) instance of this funny type, it means that A is actually a pair, and we can safely create our Map. Intuitively, the compiler is doing
[imaginary language]
if A is a pair then "let the thing compile"
else "crash, aka, compile error"which is exactly the same as our sqrt method was doing before, only much better since we have it even before running the program!
To sum up what the analogy that we saw, we have the following:
- variables at run-time correspond to types at compile time
- “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.
Imagine you have a trait (a typeclass, if you know the name) Printer[A] which have a method def print(a: A): String. An instance of this trait would print an instance of an A in a certain fashion (could be simply toString, could be some Json/XML representation, or something else entirely, it doesn’t matter). We could for example have an instance unitPrinter with type Printer[Unit]. The Unit type is special because there is only one instance of it, and hence we could say that it’s useless to specify the argument. The =:= method allows us to do that, simply by creating a method
def print()(using ev: Unit =:= A): String = print(ev(()))which allows to do unitPrinter.print() instead of unitPrinter.print(()). As you may have noticed, the instance ev is (among other things) a function from Unit to A. In this regard, the operator =:= is not strictly symmetric.
Another usage in this setting could be to print pairs in a special way. We could create a method
def printAsPair[K, V](a: A)(using ev: A =:= (K, V)): String =
val (key, value) = ev(a)
s"$key: $value"A last thing that we could do would be to enable printing … Nothing! As you may know, Nothing in Scala is a type which have no instance. As such, it is impossible to use the print(a: A)method because it would require us to give an instance of Nothing, which does not exist! So, how to print nothing? Like this:
def print()(using A =:= Nothing): String = "Nothing there!"I will admit that this last example is more than anecdotical, but, as a mathematician, I will certainly not be the one reluctant to do things simply because they are beautiful…
Note that in this case we don’t need the ev instance, we simply need to ask that it exists.
Note: the provided instances are often called
ev(orevNif you need several of them). It stands for “evidence”, because we are asking the compiler for a piece of evidence that our types satisfy some predicate.
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).
In Scala 2, the “solution” was quite tricky and used what are called “ambiguous implicits”. In Scala, when we require an implicit and the compiler actually finds two of them, it does not compile. Which suggests the solution to create two implicits for the specific type we don’t want, and only one for the others. This solution however has a catch, but it is beyond the scope of this blog post.
In Scala 3, there is a much better solution, coming from a new feature: match types. Match types allow you to create types based on the value of others. When we think about it, what we want the compiler to do is
[imaginary language]
if A != Foo then "let it go"
else "crash, aka don't compile"As we saw, we can’t do this because we don’t have !=:=. However, we can create a type IsNotFoo[A]which will basically say A != Foo. Then, we will be able to do a thing which makes me cringe when I see it in usual codebases, and that is someBoolean == true. This idea is implemented as:
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
Note that the true that you see there is not the run-time value true, but the type true (which is a subtype Boolean, and has only one possible run-time value).
The nice thing with this solution is that it is easily generalisable if you want to prevent several types. Trying to use mapError with Nothing will result in the following nice compile error message:
val ioNothing: IO[Nothing, Int] = ???
ioNothing.mapError(_ => 2)
// [error] 18 | ioNothing.mapError(_ => 2)
// [error] | ^
// [error] |Cannot prove that IsNotNothing[Nothing] =:= (true : Boolean).Note: as we said for evidence earlier, we see that the compiler uses the mathematical nomenclature of “proving” things.
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.
- Asking a function argument: An easy way, that you can actually do in any language, would be to simply define functions with the constraints that you want. For example, in order to turn a List into a Map, you can do
def listToMap[K, V](ls: List[(K, V)]): Map[K, V] - 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] = ???Even though they might seem more “beginner friendly”, there are several drawbacks to these ways of working:
- you don’t have access to private members of the elements you manipulate
- 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.
I hope that this blog post will give you ideas for your own projects or, otherwise, will help you better understand some of the power you already wield with the libraries you use every day (including the standard library!).
