Chapter 20. Type-Level Programming
Topics in This Chapter L3
Why use Scala instead of Java on the JVM? Sure, the Scala syntax is more concise and more regular than Java, but in the end, it is all about the types. Types help us express what we expect our programs to do. Type mismatches help detect programming errors early, when they are cheap to fix. You have already seen many instances where the Scala type system is richer than Java. This chapter introduces you to advanced techniques of “programming with types”—analyzing and generating types at compile time. These type manipulations are the foundation of some of the most powerful Scala libraries. The details are undeniably complex, and only of interest for advanced library creators. This overview should enable you to understand how those libraries work, and what is involved in their implementation.
The key points of this chapter are:
Match types express types that vary with another type.
A heterogeneous list has elements of different types.
You can make compile-time computations with literal integer types.
With inline functions, you can conditionally inject code at compile time.
A type class defines behavior that classes can declare to support in an ad-hoc fashion.
The mirror API provides support for analyzing types at compile time. An important application is the automatic derivation of type class instances.
A higher-kinded type has a type parameter that is itself a parameterized type.
A type lambda denotes a transformation of a type into another type.
Macros programmatically generate and transform code at compile time.
20.1 Match Types
At times, it can be useful to perform pattern matching on the type level. Scala has match types for this purpose. Here is the canonical introductory example:
type Elem[C] = C match
case String => Char
case Iterable[t] => t
case Any => CThe type Elem[String] is Char, but Elem[List[Int]] is Int. Note that the type variables, like any variables in a match expression, are lowercase.
Given this type, we can now define a function yielding the initial element of different types:
def initial[C <: Matchable](c: C): Elem[C] =
c match
case s: String => s(0)
case i: Iterable[t] => i.head
case _: Any => c
CAUTION
The match clause must have the exact same shape as the match type. The clauses must come in the same order. You cannot add other clauses. In our example, it might be tempting to add a clause such as case "" => 'u0000', but that is a compile-time error.
Match types can be recursive. Given a list of lists, we may want the initial element of the initial list:
type FlatElem[C] = C match
case String => Char
case Iterable[t] => FlatElem[t] // Recursion
case Any => CNow FlatElem[List[List[Int]]] is Int.
There is a wrinkle when working with this match type. The compiler cannot tell whether the element type t is Matchable. You finesse that with a cast:
def flatInitial[C](c: C): FlatElem[C] =
c.asInstanceOf[c.type & Matchable] match
case s: String => s(0)
case i: Iterable[t] => flatInitial(i.head)
case x: Any => xThe Scala API has a slightly prettier mechanism for the same purpose. With the statement
import compiletime.asMatchableyou can call asMatchable on any object to add the Matchable trait:
def flatInitial[C](c: C): FlatElem[C] =
c.asMatchable match
case s: String => s(0)
case i: Iterable[t] => flatInitial(i.head)
case x: Any => xNow you can call
flatInitial(List(List(1, 7), List(2, 9))) // 120.2 Heterogeneous Lists
A List[T] collects elements of type T. What if we want to collect elements of different types? Of course, we can use a List[Any], but then we lose all type information. In this section, we will build a heterogeneous list class that holds elements of different types.
A list is either empty, or it has a head of type H and a tail that is again a HList:
abstract sealed class HList :
def ::[H, T >: this.type <: HList](head: H): HNonEmpty[H, T] = HNonEmpty(head, this)
case object HEmpty extends HList
case class HNonEmpty[H, T <: HList](head: H, tail: T) extends HListWith the :: operator, you can build up heterogeneous lists:
val lst = "Fred" :: 42 :: HEmpty//Type is HNonEmpty[String, HNonEmpty[Int, HEmpty.type]]
CAUTION
There is a subtlety in the type parameters of the :: method. If you define
def ::[H](head: H): HNonEmpty[H, this.type] = HNonEmpty(head, this)then the type of lst has an unwanted wildcard: HNonEmpty[String, ? <: HNonEmpty[Int, HEmpty.type]].
The problem is that this.type is not the type of the right-hand side (that is, not HNonEmpty[Int, HEmpty.type]]). Instead, it is the singleton type consisting only of the right-hand side object. You need an additional type variable to obtain the list type.
The Scala compiler can determine the type of each list element. Try evaluating the following expressions:
lst.head //Type is Stringlst.tail.head //Type is Intlst.tail.tail //Type is HEmpty
Consider the following function that concatenates two heterogeneous lists:
def append(a: HList, b: HList): HList =
a match
case HEmpty => b
case ne: HNonEmpty[?, ?] => HNonEmpty(ne.head, append(ne.tail, b))Unfortunately, the function is not very useful because it doesn’t have a precise return type:
val lst2 = append(lst, lst) // Type is HListYou can’t even ask for lst2.head because a HList doesn’t have a head method. Only HNonEmpty does, but the compiler has no way of knowing that lst2 is nonempty.
Note
If you try these instructions in the REPL, you will find that lst2 has the value
HNonEmpty(Fred,HNonEmpty(42,HNonEmpty(Fred,HNonEmpty(42,HEmpty))))However, that is only known at runtime.
To accurately determine the return type at compile time, use a match type:
type Append[A <: HList, B <: HList] <: HList = A match
case HEmpty.type => B
case HNonEmpty[h, t] => HNonEmpty[h, Append[t, B]]This match type recursively computes the type of the concatenation. Let’s look at the example of the computation append(lst, lst). Both A and B are HNonEmpty[String, HNonEmpty[Int, HEmpty]]. Then you can work out Append[A, B]. After a couple of recursive steps, it is
HNonEmpty[String, HNonEmpty[Int, B]]which is
HNonEmpty[String, HNonEmpty[Int, HNonEmpty[String, HNonEmpty[Int, HEmpty]]]]That is the type that we need to use for the return type of append. Here is the correct function:
def append[A <: HList, B <: HList](a: A, b: B): Append[A, B] =
a match
case _: HEmpty.type => b
case ne: HNonEmpty[?, ?] => HNonEmpty(ne.head, append(ne.tail, b))Since the types of a and b can vary, the append function needs type parameters A and B, both subtypes of HList. The return type is accurately computed as Append[A, B].
Now the compiler can determine the types of expressions such as
lst2.head //Type is Stringlst2.tail.tail.tail.tail //Type is HEmpty
CAUTION
The match clause must exactly mirror the match type. You must write
case _: HEmpty.type => bin the function since the type has
case HEmpty.type => BIt would be an error to write
case HEmpty => b Note
The HList example shows you how to carry out type-level programming. If you want to use heterogeneous lists in your Scala code, you don’t need to implement your own HList class. Just use tuples. They are implemented with the same techniques that this chapter covers. For example, the Scala compiler knows that the type of ("Fred", 42) ++ ("Fred", 42) is (String, Int, String, Int).
20.3 Literal Type Arithmetic
Chapter 18 introduced literal types, such as the type 3 that holds a single value, namely the integer 3.
Why have values at the type level? It allows for checks and computations at compile time. For example, we can define a Vec[N] as a vector with N components, where N is a compile-time constant integer. Then we can check at compile time that a Vec[3] can be added to another Vec[3] but not a Vec[4]:
class Vec[N <: Int] :private val xs: Array[Double] = ...def +(other: Vec[N]) = ... //Must have the same size
Note that the type parameters must be compile-time constants. You can declare a Vec[3] but not a Vec[n], where n is a variable of type n.
The bound N <: Int is not enough to guarantee that N is a singleton type. To fix that, add a using parameter of type ValueOf[N], like this:
class Vec[N <: Int](using n: ValueOf[N]) :
private val xs: Array[Double] = Array.ofDim[Double](n.value)
def +(other: Vec[N]) = // Must have the same size
val result = Vec[N]()
for i <- 0 until xs.length do
result.xs(i) = xs(i) + other.xs(i)
result
...A given instance of ValueOf[S] exists for all singleton types whose single occupant is known to the compiler. It has a method value that produces the single value, forming a bridge from the world of types to the world of values. In the code snippet above, the value is used to construct the array of vector coordinates.
CAUTION
The using parameter is required. It is not enough to constrain the type of N to Int & Singleton. The following does not work:
class Vec[N <: Int & Singleton] :
private val xs: Array[Double] =
Array.ofDim[Double](summon[ValueOf[N]].value)Here, the compiler has insufficient information to infer the single value of N.
Now consider the operation of concatenating a Vec[N] with a Vec[M]. The result is a vector with N + M components. Of course, N and M are types. Can you add two types?
If you import scala.compiletime.ops.int.*, you can. That package defines types with names +, -, and so on, which carry out arithmetic at the type level. If N and M are singleton integer types, the type N + M is the type whose sole inhabitant is the sum of the inhabitants of N and M.
Here is how to define the concatenation:
def ++[M <: Int](other: Vec[M])(using ValueOf[N + M]) =
val result = Vec[N + M]()
for i <- 0 until xs.length do
result.xs(i) = xs(i)
for i <- 0 until other.xs.length do
result.xs(i + xs.length) = other.xs(i)
result CAUTION
In Scala 3.2, the singleton type inference is rather fragile. If the using parameter has type ValueOf[M], the Scala compiler does not infer that both N and M are singletons that can be combined with +.
As a final use of type-level arithmetic, let us provide a middle method that yields the middle component of a vector, provided the number of components is odd.
The scala.compiletime.ops.any package defines == and != type operators. The type N % 2 != 0 is the literal type true when N is inhabited by an odd integer.
def middle(using N % 2 != 0 =:= true) = xs(n.value / 2)A call v.middle yields a compile-time error if v has an even number of components. In that case, N % 2 != 0 is false, and it is impossible to summon a given false =:= true instance.
20.4 Inline Code
In the preceding section, you saw how to carry out computations at the type level—to ensure that two integer type parameters match, or to form their sum, or to ensure that one is odd. These computations happen when the program is compiled.
For more complex compile-time computations, you can use the Scala facilities for generating inline code. In this section, you will see basic examples that don’t involve type-level programming. Section 20.6, “Mirrors,” on page 328 puts the features to work for automatically generating code for case classes.
Even more complex compile-time transformations are possible with macros—see Section 20.10, “A Brief Introduction into Macros,” on page 335. However, programming with macros is quite a bit more complex. The inline code generation was designed to avoid that complexity in common use cases.
This example nicely shows off the mechanics of inline code generation:
inline def run[T](inline task: => T, profile: Boolean) =
var start: Long = 0
inline if profile then start = System.nanoTime()
val result = task
inline if profile then
val end = System.nanoTime()
println(f"Duration of ${codeOf(task)}: ${(end - start) * 1E-9}%.3f")
resultThe function runs some task, and if the profile flag is true, the running time is printed. Read the code, skipping over the inline keywords. You see that there is a by-name parameter task that is executed. The result, of type T, is returned. A typical call would be:
println(run(Thread.sleep(1000), true))The output is something like
Duration of Thread.sleep(1000L): 1.001
()Note the message that is generated by the println statement inside the run function, indicating the time that elapsed. The () that follows is from the println around the call to run, printing the Unit return value.
The call
println(run(Thread.sleep(1000), false))simply prints
()That is not remarkable by itself. To see what is special about the inline code generation, look at the generated bytecodes—see Exercise 4 on page 339. There is no separate run function. Instead, the code of run is placed inside the fuction that calls run. The first copy of the code, when profile is true, contains the calls to System.nanoTime and the string formatter, in addition to the Thread.sleep call. The second copy of the code only calls Thread.sleep.
Note the three uses of the inline keyword:
The
inlinefunction causes the function code to be placed into the location of the function call.The
inlineparameter causes the call expression to be placed inside the function code.inline ifdiscards the code in nonmatching branches.
CAUTION
Each use of an inline parameter is expanded. The implementation
inline def run[T](inline task: => T, profile: Boolean) =
var start: Long = 0
if profile then
start = System.nanoTime()
val result = task
val end = System.nanoTime()
println(f"Duration of ${codeOf(task)}: ${(end - start) * 1E-9}%.3f")
result
else
taskwould inline the code for task twice.
Finally, note the nifty codeOf(task) that yields a string representing the inline expression. The string comes from the parse tree for the expression, not the source code. Note that the output is Thread.sleep(1000L), whereas the source code is Thread.sleep(1000) without the L. The codeOf function is in the scala.compiletime package.
An inline match, similar to an inline if, generates code only for the matching branch:
inline def sizeof[T <: Matchable] =
inline erasedValue[T] match
case _: Boolean => 1
case _: Byte => 1
case _: Char => 2
case _: Short => 2
case _: Int => 4
case _: Float => 4
case _: Long => 8
case _: Double => 8
case _ => error("Not a primitive type")For example, sizeof[Int] is replaced with 4.
The scala.compiletime.erasedValue method is needed because T is a type, but the selector of a match expression needs to be a value. It pretends to produce a value of the given type, that then is matched against one of the case branches. Actually, the compiler just matches the types, but this way, no new syntax for type matching had to be invented.
The scala.compiletime.error method reports a compile-time error with the given message.
When each branch of an inline match returns a different type, you may want to declare the function as transparent inline. Then the compiler doesn’t use the common supertype as the return type. Here is an example:
transparent inline def defaultValue[T <: Matchable] =
inline erasedValue[T] match
case _: Boolean => false
case _: Byte => 0.asInstanceOf[Byte]
case _: Char => 'u0000'
case _: Short => 0.asInstanceOf[Short]
case _: Int => 0
case _: Float => 0.0f
case _: Long => 0L
case _: Double => 0.0
case _ => error("Not a primitive type")Now the type of defaultValue[Int] is Int. Without the transparent keyword, it would be AnyVal.
There are no inline loops, but inline functions can be recursive. This function concatenates the elements of a tuple:
inline def mkString[T <: Tuple](inline args: T, separator: String): String =
inline args match
case EmptyTuple => ""
case t1: (? *: EmptyTuple) => t1.head.toString
case t2: NonEmptyTuple =>
t2.head.toString + separator + mkString(t2.tail, separator)For example, mkString(("Fred", 42), ", ") is first reduced to "Fred".toString + ", " + mkString((42), ", ") and then to "Fred".toString + ", " + 42.toString.
20.5 Type Classes
If a class wants to compare its elements in a standard fashion, it can extend the Comparable trait. Dozens of Java classes do just that. Inheritance is the object-oriented way of acquiring a capability.
But that mechanism is inflexible. Consider a List[T] type. It can’t extend Comparable because the element type might not be comparable. That’s a shame because there is a natural comparison for lists with comparable element types.
In Chapter 19, you saw a different approach. We provided given Comparator instances for numbers, strings, and any class extending Comparable. Then we synthesized Comparator instances for those lists whose element types have a given Comparator. Algorithms such as sorting make use of the comparison with a using parameter.
This selective synthesis is much more flexible than the object-oriented approach. In order to compare instances, it is not necessary to modify the class at all. Instead, one provides a given instance.
A trait such as Comparator is called a type class. A type class defines some behavior, and a type can join the class by providing that behavior. The term comes from Haskell, and “class” is not used in the same way as in object-oriented programming. Think of “class” as in a “class action”—types banding together for a common purpose.
To see how a type joins a type class, let us look at a simple example. We want to compute averages, (x1 +...+ xn) / n. To do that, we need to be able to add two values and divide a value by an integer. There is a type class Numeric in the Scala library, which requires that values can be added, multiplied, and compared. But it doesn’t have any requirement that values can be divided by an integer. Therefore, let’s define our own:
trait Averageable[T] :
def add(x: T, y: T): T
def divideBy(x: T, n: Int): TNext, to make sure that the type class is useful out of the gate, let’s include some common types. That’s easy to do by providing given objects in the companion object:
object Averageable :
given Averageable[Double] with
def add(x: Double, y: Double) = x + y
def divideBy(x: Double, n: Int) = x / n
given Averageable[BigDecimal] with
def add(x: BigDecimal, y: BigDecimal) = x + y
def divideBy(x: BigDecimal, n: Int) = x / nNow we are ready to put the type class to use. In the average method, we need an instance of the type class so that we can call add and divideBy. (Note that these are methods of the type class, not the type of the average parameters.)
Here, we’ll just compute the average of two values. The general case is left as an exercise. There are two ways in which we can supply the type class instance: as a using parameter, or with a context bound. Let’s do the latter:
def average[T : Averageable](x: T, y: T) =
val ev = summon[Averageable[T]]
ev.divideBy(ev.add(x, y), 2)Finally, let’s see what a type needs to do to join the Averageable type class. It must provide a given object, just like the given instances for Double and BigDecimal that we provided out of the gate. Here is how Point can join:
case class Point(x: Double, y: Double)
object Point :
given Averageable[Point] with
def add(p: Point, q: Point) = Point(p.x + q.x, p.y + q.y)
def divideBy(p: Point, n: Int) = Point(p.x / n, p.y / n)Here we added the given object to the companion object of Point. If you can’t modify the Point class, you can put the given object elsewhere and import it as needed.
The standard Scala library provides useful type classes, such as Equiv, Ordering, Numeric, Fractional, Hashing, IsIterableOnce, IsIterable, IsSeq, IsMap, FromString. As you have seen, it is easy to provide your own.
The important point about type classes is that they give you an “ad-hoc” way of providing polymorphism that is less rigid than inheritance.
20.6 Mirrors
In this section, we will use a type class that provides a JSON representation for any object:
trait JSON[A] :
def stringify(a: A): StringHere are given instances for common types:
object JSON :
given jsonDouble: JSON[Double] with
def stringify(x: Double) = x.toString
given jsonString: JSON[String] with
def escape(s: String) = s.flatMap(
Map('' -> "\\", '"' -> "\"", '
' -> "\n", '
' -> "\r").withDefault(
_.toString))
def stringify(s: String): String = s""${escape(s)}""Given any case class, we can define a given instance that stringifies the fields:
case class Person(name: String, age: Int)
given jsonPerson: JSON[Person] with
def stringify(p: Person) =
val name = summon[JSON[String]].stringify(p.name)
s"""{"name": $name, "age": $p.age}"""But that is clearly tedious. In Java, one could use reflection to automatically stringify arbitrary instances at runtime. In Scala, we can do better, and generate the converter code at compile time.
To analyze types at compile time, we need to use mirrors. Every case class T gives rise to a type Mirror.Product[T]. (Recall from Chapter 14.10 that case classes extend the Product trait.) The mirror describes the following features of the class:
MirroredElemTypes, a tuple of the field typesMirroredElemLabels, a tuple of the field namesMirroredLabel, the name of the class
Note that all of these are types. For example, if m is the given Mirror.Product[Person], then m.MirroredElemTypes is the tuple type (String, Int), m.MirroredElemLabels is a tuple type of two singleton types ("name", "age"), and m.mirroredLabel is the singleton type Person.
In the JSON representation, we need to use the field names. But we need them as string objects, not singleton types.
The scala.compiletime package has three methods for turning singleton types into values:
constValue[T]yields the sole value of the singleton typeT.constValueOpt[T]yields anOptionwith the sole value ifTis a singleton type,Noneotherwise.constValueTuple[T]yields a tuple of singleton values, whereTis a tuple type of singleton types.
You can move from types to objects as follows:
val fieldNames = constValueTuple[m.MirroredElemLabels] // A tuple of stringsFor JSON formatting, we don’t need the class name, but if you need it, it is
val className = constValue[m.MirroredLabel]We need to obtain the given JSON instances for each of the field types. There are three methods for summoning given instances in an inline function:
summonInline[T]summons the given instance of typeT.summonAll[T], whereTis a tuple type, summons a tuple of all given instances of the element types ofT.summonFromattempts to summon instances given in acaseclause; for example,summonFrom { case given Ordering[T] => TreeSet[T](); case _ => HashSet[T]() }
Here is one way to summon the given JSON instances:
inline def summonGivenJSON[T <: Tuple]: Tuple =
inline erasedValue[T] match
case _: EmptyTuple => EmptyTuple
case _: (t *: ts) => summonInline[JSON[t]] *: summonGivenJSON[ts]The result is a tuple of JSON instances, such as JSON[String] and JSON[Int] if T is Person. Note that again we go from a tuple of types to a tuple of values.
You will see more elegant ways of collecting such type class instances in Section 20.8, “Higher-Kinded Types,” on page 332 and Section 20.9, “Type Lambdas,” on page 334.
At this point, we have all the tools to produce a JSON instance for an arbitrary Product. Every case class is a subclass of Product.
inline given jsonProduct[T](using m: Mirror.ProductOf[T]): JSON[T] =
new JSON[T] :
def stringify(t: T): String =
val fieldNames = constValueTuple[m.MirroredElemLabels]
val jsons = summonGivenJSON[m.MirroredElemTypes]
"{ " + fieldNames.productIterator.zip(jsons.productIterator)
.zip(t.asInstanceOf[Product].productIterator).map {
case ((f, j), v) => s""""$f": ${j.asInstanceOf[JSON[Any]].stringify(v)}"""
}.mkString(", ") + " }"The cast j.asInstanceOf[JSON[Any]] is necessary since jsons is only known to be a Tuple.
CAUTION
With Scala 3.2, you cannot use the with syntax with inline given.
Now any case class instance can be formatted as JSON:
case class Item(description: String, price: Double)
summon[JSON[Item]].stringify(Item("Blackwell Toaster", 19.95))
// { "description": "Blackwell Toaster", "price": 19.95 }20.7 Type Class Derivation
In the preceding section, you saw how to automatically obtain a JSON instance for any product type. You can do the same for sum types. Recall that a sum type is given by a sealed class or an enum class, such as
sealed abstract class Amount
case class Dollar(value: Double) extends Amount
case class Currency(value: Double, unit: String) extends Amountor
enum BinaryTree[+A] :
case Node(value: A, left: BinaryTree[A], right: BinaryTree[A])
case EmptyAnalogous to the process of the preceding section, here is how to produce a JSON instance for a sum type:
inline given jsonSum[T](using m: Mirror.SumOf[T]): JSON[T] =
new JSON[T] :
def stringify(t: T): String =
val index = m.ordinal(t)
val jsons = summonGivenJSON[m.MirroredElemTypes]
jsons.productElement(index).asInstanceOf[JSON[Any]].stringify(t)With a Mirror.SumOf, m.MirroredElemTypes is a tuple of all subtypes, and the call m.ordinal(t) yields the index of the type t in that tuple.
Summoning a JSON[Amount] will summon JSON instances of all subtypes, namely JSON[Dollar] and JSON[Currency]. These are case classes, and the instances are generated using jsonProduct.
However, if you try summon[JSON[BinaryTree[String]]], you run into a problem. The subclass BinaryTree[String].Node yields an error since the compiler doesn’t yet know how to deal with the fields of type BinaryTree.
This can be finessed through type class derivation. BinaryTree declares that it is an instance of the JSON type class, with the syntax
enum BinaryTree[+A] derives JSON :
case Node(value: A, left: BinaryTree[A], right: BinaryTree[A])
case EmptyThe JSON companion object must provide a method or value called derived that yields the type class instance. Here is a suitable method:
inline def derived[T](using m: Mirror.Of[T]): JSON[T] =
inline m match
case s: Mirror.SumOf[T] => jsonSum(using s)
case p: Mirror.ProductOf[T] => jsonProduct(using p)Keep in mind that few programmers will implement their own type classes. Libraries for interacting with JSON, SQL, and so on, will define appropriate type classes. Users of such libraries indicate with the derives syntax that a particular class is an instance of such a type class.
20.8 Higher-Kinded Types
The generic type List has a type parameter T and produces a type. For example, given the type Int, you get the type List[Int]. For that reason, a generic type such as List is sometimes called a type constructor, denoted as List[_]. In Scala, you can go up another level and have type parameters that are type constructors.
To see why this can be useful, consider the summonGivenJSON method from Section 20.6, “Mirrors,” on page 328. If we want to collect elements of another type class, we have to write the method all over again, just with the other type class instead of JSON. It would be nice if we could pass the type class as a parameter. That is a typical use for a higher-kinded type:
inline def summonGiven[T <: Tuple, C[_]]: Tuple =
inline erasedValue[T] match
case _: EmptyTuple => EmptyTuple
case _: (t *: ts) => summonInline[C[t]] *: summonGiven[ts, C]Now the call summonGiven[m.MirroredElemTypes, JSON] gathers up all given JSON[t] instances.
We say that summonGiven is higher-kinded because it has a type parameter that itself has a type parameter. (There is a theory of kinds that describes the complexity of type parameters. The details are not important for most programmers because situations that are more complex than the one you are seeing here are very uncommon.)
This example is concise, but rather specialized. For another example, let’s start with the following simplified Iterable trait:
trait Iterable[E] :
def iterator(): Iterator[E]
def map[F](f: E => F): Iterable[F]Now consider a class implementing this trait:
class Buffer[E] extends Iterable[E] :
def iterator(): Iterator[E] = ...
def map[F](f: E => F): Buffer[F] = ...For a buffer, we expect that map returns a Buffer, not a mere Iterable. That means we cannot implement map in the Iterable trait itself, which we would like to do. A remedy is to parameterize the Iterable with a type constructor, like this:
trait Iterable[E, C[_]] :
def iterator(): Iterator[E]
def build[F](): C[F]
def map[F](f: E => F): C[F]Now an Iterable depends on a type constructor for the result, denoted as C[_]. This makes Iterable a higher-kinded type.
The type returned by map may or may not be the same as the type of the Iterable on which map was invoked. For example, if you invoke map on a Range, the result is not generally a range, so map must construct a different type such as a Buffer[F]. Such a Range type is declared as
class Range extends Iterable[Int, Buffer]Note that the second parameter is the type constructor Buffer.
To implement map in Iterable, we need a bit more support. An Iterable needs to be able to produce a container that holds values of any type F. Let’s define a Container trait—it is something to which you can add values:
trait Container[E : ClassTag] :
def +=(e: E): UnitWe require the ClassTag context bound since some containers need to be able to construct a generic Array[E].
The build method is required to yield such an object:
trait Iterable[E, C[X] <: Container[X]] :
def build[F : ClassTag](): C[F]
...The type constructor C has now been constrained to be a Container, so we know that we can add items to the object that build returns. We can no longer use a wildcard for the parameter of C since we need to indicate that C[X] is a container for the same X.
The map method can be implemented in the Iterable trait:
def map[F : ClassTag](f: E => F): C[F] =
val res = build[F]()
val iter = iterator()
while iter.hasNext do
res += f(iter.next())
resIterable classes no longer need to supply their own map. Here is the Range class:
class Range(val low: Int, val high: Int) extends Iterable[Int, Buffer] :
def iterator() = new Iterator[Int] :
private var i = low
def hasNext = i <= high
def next() = { i += 1; i - 1 }
def build[F : ClassTag]() = Buffer[F]Note that a Range is an Iterable: You can iterate over its contents. But it is not a Container: You can’t add values to it.
A Buffer, on the other hand, is both:
class Buffer[E : ClassTag] extends Iterable[E, Buffer] with Container[E] :private var capacity = 10private var length = 0private var elems = Array[E](capacity) //See notedef iterator() = new Iterator[E] :private var i = 0def hasNext = i < lengthdef next() = { i += 1; elems(i - 1) }def build[F : ClassTag]() = Buffer[F]def +=(e: E) =if length == capacity thencapacity = 2 * capacityval nelems = Array[E](capacity) //See notefor i <- 0 until length do nelems(i) = elems(i)elems = nelemselems(length) = elength += 1
This example showed a typical use of higher-kinded types. An Iterable depends on Container, but Container isn’t a type—it is a mechanism for making types.
20.9 Type Lambdas
We can think of a type constructor such as List[_] as a type-level function, mapping a type X to the type List[X]. This can be expressed with a special syntax, called a type lambda:
[X] =>> List[X]In this simple case, the type lambda syntax is not necessary, but it is useful for expressing more complex type-level mappings.
CAUTION
The [] are required around the type arguments. For example, X =>> List[X] is not a valid type lambda.
Here is another example. Recall the integer type arithmetic from Section 20.6, “Mirrors,” on page 328. Now we want a general mechanism to check for conditions such as “a compile-time constant is even.” Here it is:
def validate[V <: Int, P[_ <: Int] <: Boolean](
using ev: P[V] =:= true, v: ValueOf[V]) = v.valueV is a singleton integer type and P a type constructor turning integers to Booleans—that is, a condition. If the condition is fulfilled at the type level, P[V] =:= true can be summoned, and the value is retrieved.
You can specify P as a type lambda. Here is how to check that a value is even:
validate[10, [V <: Int] =>> V % 2 == 0]Note the type lambda. Without it, you would need to define a named type
type Even[V <: Int] = V % 2 == 0and call
validate[10, Even]Finally, let us use the concept of type lambdas to make one more simplification of the summonGivenJSON function of Section 20.6, “Mirrors,” on page 328. We handcrafted a transformation from a tuple of types to a tuple of given instances. There is a function summonAll in the scala.compiletime package that will summon the given instances from a tuple of types. But we couldn’t use it because we didn’t have a tuple of the right types. We had a tuple (String, Int) but need to summon the instances of (JSON[String], JSON[Int]). If we could just map [X] =>> JSON[X], we would be all set.
That is exactly what the Tuple.Map type does. It applies a type-level transformation to a tuple of types. The type
type ElemTypesJSON = Tuple.Map[m.MirroredElemTypes, [X] =>> JSON[X]]is the tuple of JSON type classes of the field types.
You don’t actually need the type lambda here. Simply summon the instances as:
val jsons = summonAll[Tuple.Map[m.MirroredElemTypes, JSON]]20.10 A Brief Introduction into Macros
In this chapter, you have seen several techniques for carrying out compile-time computations. Macros provide a far more general mechanism for arbitrary code transformation at compile time. However, writing macros is complex and requires significant insight into the compilation process. Macro programming is a very specialized skill that is only needed to implement advanced libraries with seemingly magical powers.
This section covers a couple of use cases for macros and briefly shows you the implementation. Hopefully, that will give you a flavor of what is possible with macros, so that you have a basic understanding how the implementors of those advanced libraries achieve their magical results.
Let us start with a simple example. When debugging, it is common to write print statements such as
println("someVariable = " + someVariable)It is annoying that one has to write the variable name twice: once to print the name, and again to get the value. That problem can actually be solved with an inline function:
inline def debug1(inline expr: Any): Unit = println(codeOf(expr) + " = " + expr)You already saw the codeOf function in Section 20.4, “Inline Code,” on page 323. It prints the code of an inline value. Here is an example:
val x = 6
val y = 7
debug1(x * y) // Prints x.*(y) = 42But suppose we also want to see the type of the expression. There is no library function for that. Instead, we need to write a macro.
Macros permit manipulation of syntax trees. If e is a Scala expression of type T, then ’{e} is the syntax tree of type Expr[T]. There are methods for analyzing and generating syntax trees.
Conversely, if you have a value s of type Expr[T], you can use the expression that it represents inside a Scala expression, using the syntax ${s}.
The ' and $ operations are called quote and splice.
In our debug1 example, we will produce a syntax tree for a call to println:
'{println(${...} + ": " + ${...} + " = " + ${...})}In general, the idea is to do as much as possible in Scala syntax, and use the syntax tree API only when necessary. Here, we use Scala syntax for the concatenation and the invocation of println.
Here is the complete implementation:
inline def debug1[T](inline arg: T): Unit = ${debug1Impl('arg)}
private def debug1Impl[T : Type](arg: Expr[T])(using Quotes): Expr[Unit] =
'{println(${Expr(arg.show)} + ": " + ${Expr(Type.show[T])} + " = " + $arg)}For technical reasons, a macro must be called from an inline function; here, debug1, using a top-level splice and quoting its arguments. It is customary to use an Impl suffix for the macro function.
Note that 'arg is the same as '{arg}. No braces are required with a variable name.
The macro function receives arguments of type Expr, and it needs to use a given Quotes instance.
The call arg.show yields a string representation of the syntax tree of arg. To splice it in, we need to turn it to an Expr.
Similarly, Type.show[T], which yields a string representation of the type parameter, is turned into an Expr.
Finally, the arg variable, which is itself a syntax tree, is spliced in. Again, since it is a variable, no braces are required.
The debug1 function prints a single expression. It would be nice to print more than one:
debugN("Test description", x, y, x * y)There is no easy way of printing the types. Instead, let us not print the expressions for literal values. It would look silly to print Test description = Test description.
The implementation is a bit more complex:
inline def debugN(inline args: Any*): Unit = ${debugNImpl('args)}
private def debugNImpl(args: Expr[Seq[Any]])(using q: Quotes): Expr[Unit] =
import q.reflect.*
val exprs: Seq[Expr[String]] = args match
case Varargs(es) =>
es.map { e =>
e.asTerm match
case Literal(c: Constant) => Expr(c.value.toString)
case _ => '{${Expr(e.show)} + " = " + $e}
}
'{println(${exprs.reduce((e1, e2) => '{$e1 + ", " + $e2})})}As before, the debugN function calls the debugNImpl macro, passing the quoted arguments, now as an Expr[Seq[Any]]. And as before, we need to use a given Quotes instance.
Now some more knowledge of Scala internals is required. The args parameter is actually an instance of Varargs, which we destructure to get its elements. Each element is either a literal, or an expression for which both the description and value are printed.
In the first case, we produce an Expr with the string representation of the literal. In the second case, we concatenate the expression’s string representation e.show and the string " = " at compile time, and produce an expression to concatenate with the expression’s value at runtime.
The call to reduce concatenates the values of the expressions. Note the nested quote and splice to compute the concatenation of e1 and e2. It is a good idea to look at the generated byte codes to understand the intricacies of the macro expansion (see Exercise 27 on page 341).
As a final example, let us expand on the type checking that you saw in Section 20.3, “Literal Type Arithmetic,” on page 322. We were able to check at compile time that two vectors have the same length, or that the length is odd. Suppose we want to check strings instead. For example, we might want to verify at compile time that a string literal contains only digits before parsing it as an integer.
Such a check requires invoking a method, such as String.matches, at compile time, which is not possible with an inline function. Again, a macro is required.
Specifically, we will define a type StringMatching[regex] for literal strings that match a regular expression, also specified as a literal string. For example, the declaration
val decimal: StringMatching["[0-9]+"] = "1729"will succeed, but
val octal: StringMatching["[0-7]+"] = "1729"will not compile.
Here is the StringMatching type:
opaque type StringMatching[R <: String & Singleton] = StringIn the companion object, we define an implicit conversion:
inline given string2StringMatching[S <: String & Singleton, R <: String & Singleton]:
Conversion[S, StringMatching[R]] = str =>
inline val regex = constValue[R]
inline if matches(str, regex)
then str.asInstanceOf[StringMatching[R]]
else error(str + " does not match " + regex)The matches call is a macro:
inline def matches(inline str: String, inline regex: String): Boolean =
${matchesImpl('str, 'regex)}
def matchesImpl(str: Expr[String], regex: Expr[String])(
using Quotes): Expr[Boolean] =
Expr(str.valueOrAbort.matches(regex.valueOrAbort))It would have been nicer to use quotes and splices '{$str.matches($regex)}, but that does not inline. Therefore, the matchesImpl method manually converts the expression trees to values, invokes String.matches, and produces an Expr of the Boolean result.
This chapter has given you an overview of techniques that make some of the most advanced Scala libraries possible. You have now reached the end of this book. I hope that you found it useful as a rapid introduction into all aspects of the Scala language, and that you will find it equally effective as a reference in the future.
Exercises
1. Using a recursive match type and union types, define a type Interval[MIN <: Int, MAX <: Int] <: Int that describes an interval of integers, with membership checked at compile time. For example, a variable of type Interval[1, 10] can be set to any constant integer between 1 and 10, and not to any other value.
2. Define an opaque type IntMod[N] for integers modulo N, with operators +, -, * that only combine integers with the same modulus.
3. Define a zip function that takes two HList of the same length and yields an HList of corresponding pairs. You will also need a recursive match type Zip.
4. Look at the bytecodes that are generated when you call the run function of Section 20.4, “Inline Code,” on page 323. Compile the Section5 class from the companion code with the Scala compiler, then run javap -c -private on the class file that is called from the @main method. How can you tell that the code of the run function was inlined?
5. Verify that the code in the Caution note of Section 20.4, “Inline Code,” on page 323 inlines the code for the task parameter twice.
6. How does the codeOf(task) string appear in the bytecodes that are generated when you call the run function of Section 20.4, “Inline Code,” on page 323? Try invoking run with two different tasks.
7. Explain why Ordering is a type class and why Ordered is not.
8. Generalize the average method in Section 20.5, “Type Classes,” on page 326 to a Seq[T].
9. Make String a member of the Averageable type class in Section 20.5, “Type Classes,” on page 326. The divBy method should retain every nth letter, so that average("Hello", "World") becomes "Hlool".
10. Why can’t you implement the debugN function from Section 20.10, “A Brief Introduction into Macros,” on page 335 as an inline function? Could you do it if you pass the arguments as a tuple, for example debugN((x, y + z))?
11. Write a recursive inline function that computes the sum of the elements of a Vec from Section 20.3, “Literal Type Arithmetic,” on page 322.
12. Write a recursive inline function that yields the element with index n of a HList with return type Any.
13. Improve upon the preceding exercise with an accurate return type. For example, elem(("Fred", 42), 1) should have type Int. Hint: Use a recursive match type Elem[T, N]. You may still need a cast in the implementation. If you are stuck, look into the source code of the Scala Tuple class.
14. Create a fluent API for reading integers, floating-point numbers, and strings from the console. For example: Read in aString askingFor "Your name" and anInt askingFor "Your age" and aDouble askingFor "Your weight". Return a Tuple of the appropriate type, such as (String, Int, Double) in this example.
15. Rewrite the average function in Section 20.5, “Type Classes,” on page 326 with the using syntax.
16. Rewrite the average function in Section 20.5, “Type Classes,” on page 326 to compute the average of any number of arguments.
17. Define a Fraction class and make it an instance of the standard Fractional type class.
18. Define a type class Randomized for producing a random instance of a type. Provide given instances for Int, Double, BigDecimal, and String.
19. Implement an inline function that makes a binary or a linear search through an array, depending on whether the component type admits an ordering.
20. Change the summonGivenJSON function in Section 20.6, “Mirrors,” on page 328 so that it returns a List[JSON[Any]] instead of a Tuple. Can you then avoid invoking asInstanceOf in jsonProduct?
21. The automatic derivation in Section 20.6, “Mirrors,” on page 328 does not work for the Person class. How can you fix that?
22. Extend the JSON type class in Section 20.6, “Mirrors,” on page 328 so that it can handle Boolean values and arrays.
23. Add a parse method to the JSON type class in Section 20.6, “Mirrors,” on page 328 and implement parsing for case classes.
24. Confirm that the cast asInstanceOf[Product] can be avoided in the jsonProduct function of Section 20.6, “Mirrors,” on page 328 if one adds the very sensible bound <: Product to the type parameter. What problem does that cause in Section 20.7, “Type Class Derivation,” on page 330?
25. A (potentially infinite) set of elements of type T can be modelled as a function T => Boolean that is true whenever the argument is an element of the set. Declare a type Set in two ways, with a type parameter and with a type lambda.
26. The result of "abc".map(_.toUpper) is a String, but the result of "abc".map(_.toInt) is a Vector. Find out how that is implemented in the Scala library.
27. Write a program that uses the debugN macro of Section 20.10, “A Brief Introduction into Macros,” on page 335. (You need to put the macro and the code using it into separate source files.) Use javap -c -private to analyze the class file. Can you correlate the string concatenations with the quote and splice levels? What happened to the calls to map and reduce?