Last updated on Wednesday, January 21, 2026

Week 12: Futures and Property-based testing

Welcome to week 12 of CS-214 — Software Construction!

As usual, ⭐️ indicates the most important exercises and questions and 🔥 indicates the most challenging ones.

You do not need to complete all exercises to succeed in this class, and you do not need to do all exercises in the order they are written.

Futures

Predicting future runtimes ⭐️

Let’s start our exploration of future with a series of check-yourself questions: can you predict the runtime of various combinations of futures?

We assume the following two utility functions:

def sleep(durationSec: Int): Future[Unit] =
  Future(Thread.sleep(durationSec * 1000))

def wait[T](message: String)(f: Future[T]): Unit =
  val start = System.currentTimeMillis
  Await.result(f, Duration.Inf)
  val elapsed = (System.currentTimeMillis - start) / 1000.0
  println(f"    $message: ${elapsed}%.0f seconds")

The first sleeps for durationSec sections; the second measures how long f takes to exit and then prints message along with the elapsed time.

Given these, can you predict the output of each of the lines below?

@main def predictionMain(): Unit =
  println("Single operators:")

  println("  flatMap:")

  wait("2flatMap4"):
    sleep(2).flatMap(_ => sleep(4))
  wait("4flatMap2"):
    sleep(4).flatMap(_ => sleep(2))

  println("  zip:")
  wait("2 zip 4"):
    sleep(2).zip(sleep(4))
  wait("4 zip 2"):
    sleep(4).zip(sleep(2))

  println("  sequence (;):")
  wait("2 ; 4"):
    sleep(2); sleep(4)
  wait("4 ; 2"):
    sleep(4); sleep(2)

  println("Combinations:")

  wait("2flatMap4 zip 1flatMap6"):
    sleep(2).flatMap(_ => sleep(4))
      .zip(sleep(1).flatMap(_ => sleep(6)))

  wait("2zip1 flatMap 4zip6"):
    sleep(2).zip(sleep(1)).flatMap(_ =>
      sleep(4).zip(sleep(6))
    )

  wait("2zip1 flatMap (4;6)"):
    sleep(2).zip(sleep(1)).flatMap(_ =>
      sleep(4); sleep(6)
    )

  wait("2zip1 flatMap (6;4)"):
    sleep(2).zip(sleep(1)).flatMap(_ =>
      sleep(6); sleep(4)
    )

  println("Early start:")

  wait("A=2 B=4 AflatMapB"):
    val a = sleep(2)
    val b = sleep(4)
    a.flatMap(_ => b)

  wait("A=2 B=4 AzipB"):
    val a = sleep(2)
    val b = sleep(4)
    a.zip(b)

Single operators:
  flatMap:
    2flatMap4: 6 seconds
    4flatMap2: 6 seconds
  zip:
    2 zip 4: 4 seconds
    4 zip 2: 4 seconds
  sequence (;):
    2 ; 4: 4 seconds
    4 ; 2: 2 seconds
Combinations:
    2flatMap4 zip 1flatMap6: 7 seconds
    2zip1 flatMap 4zip6: 8 seconds
    2zip1 flatMap (4;6): 8 seconds
    2zip1 flatMap (6;4): 6 seconds
Early start:
    A=2 B=4 AflatMapB: 4 seconds
    A=2 B=4 AzipB: 4 seconds

Making new friends ⭐️

In this exercise, we will explore different styles of writing asynchronous code in Scala: the “callback” style, the Future “monadic” style, and the Future “direct” style.

The Social Network

Consider a directed graph where nodes are users of a social network, and edges represent friendship. In our model, friendship is a symmetric relation: if a is friends with b, then b is friends with a.

Let Database be a trait that provides methods to get and update users:

trait Database:
  /** Gets a user by its id asynchronously.
    *
    * @param id
    *   Id of the user.
    * @return
    *   A `Future` that will resolve to the queried [[User]].
    */
  def getUser(id: String): Future[User]

  /** Updates a user in the database asynchronously.
    *
    * @param currentValue
    *   Current value of the user.
    * @param newValue
    *   New value of the user.
    * @return
    *   A `Future` that will resolve to `true` if the operation was successful,
    *   or `false` otherwise.
    */
  def updateUser(currentValue: User, newValue: User): Future[Boolean]

  /** Gets a user by its id asynchronously.
    *
    * @param id
    *   Id of the user.
    * @param callback
    *   Callback to call with the queried [[User]].
    */
  def getUserWithCallback(id: String)(callback: User => Unit): Unit

  /** Updates a user in the database asynchronously.
    *
    * @param currentValue
    *   Current value of the user.
    * @param newValue
    *   New value of the user.
    * @param callback
    *   Callback to call with the result of the operation. The result will be
    *   `true` if the operation was successful, or `false` otherwise.
    */
  def updateUserWithCallback(currentValue: User, newValue: User)(callback: Boolean => Unit): Unit

Your task is to write a function makeFriends. The function should take two user identifiers user1Id: String anduser2Id: String, and a db: Database as parameters, and update the list of friends of both users to add the other user asynchronously. This means that the function should return immediately, and the friend list should be updated eventually.

In order to achieve this, you will call asynchronous functions to get and update users.

The User class is defined as follows:

case class User(id: String, friends: List[String])

To make two users friends, you will need to:

1. Get the first user from the database.
2. Add the second user to the first user’s friend list.
3. Update the first user in the database.
4. Get the second user from the database.
5. Add the first user to the second user’s friend list.
6. Update the second user in the database.
7. Notify the caller that the operation is complete.

user.copy(friends = ???)

Sequential execution

In the first versions of makeFriends, we will perform the operations sequentially, one after the other:

In this representation, the arrows represent dependencies between operations. If there is an arrow from a to b, it means that b should only be executed after a has completed.

Callback style

The “callback” style was mostly used in the past, and is still used in some libraries. In this style, each asynchronous operation takes an additional callback function as a parameter, which is called with the desired result when the operation completes.

In this style, the makeFriendsWithCallback function takes an additional parameter callback: (Boolean, Boolean) => Unit which is called when the operation completes:

def makeFriendsWithCallback(
    user1Id: String,
    user2Id: String,
    db: Database
)(
    callback: ((Boolean, Boolean)) => Any
): Unit =
  ???

The result of the operation is a pair of booleans, indicating whether the updates of the two users were successful.

Implement makeFriendsWithCallback by calling getUserCallback and updateUserCallback appropriately.

Testing

To test your code, copy your implementations along with the scaffold code in your favorite editor and run makeFriendsMain with the appropriate version identifier, here callbacks:

sbt:futures> runMain makeFriendsMain callbacks

The main function runs with a mock database where each operation takes 1 second to complete. As you implemented the operations sequentially, the total time to complete the operation should be 4 seconds.

A correct implementation should print the following:

[info] running makeFriendsMain callbacks
Using callbacks
Waiting for callback to complete...
Get user aisha
Update user aisha
Get user carlos
Update user carlos
Aihsa and Carlos are now friends!
result: (true,true)
Completed in: 4 seconds

def makeFriendsWithCallback(
    user1Id: String,
    user2Id: String,
    db: Database
)(
    callback: ((Boolean, Boolean)) => Any
): Unit =
  db.getUserWithCallback(user1Id): user1 =>
    db.updateUserWithCallback(user1, user1.copy(friends = user2Id :: user1.friends)): res1 =>
      db.getUserWithCallback(user2Id): user2 =>
        db.updateUserWithCallback(user2, user2.copy(friends = user1Id :: user2.friends)): res2 =>
          callback((res1, res2))

Monadic style, with flatMap and map

Let’s now use Futures, in the “monadic” style. In this style, each asynchronous operation returns a Future object, which represents the result of the operation. We can then use methods such as map and flatMap on the Future to transform and combine it with other Futures.

In this style, we never await on a Future directly, except at the very end of the program; your implementation must not call Await.result, Await.ready or await.

Complete the makeFriendsMonadicFlatMap function by calling the getUser and updateUser, and combining the resulting Futures using flatMap and map:

def makeFriendsMonadicFlatMap(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  ???

Testing

You can test your implementation by running the runMain makeFriendsMain monadic-flatmap. A correct implementation should print the following:

Using monadic style and flatMap
Waiting for future to complete...
Get user aisha
Update user aisha
Get user carlos
Update user carlos
Aihsa and Carlos are now friends!
result: (true,true)
Completed in: 4 seconds

def makeFriendsMonadicFlatMap(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  db.getUser(user1Id).flatMap: user1 =>
    db.updateUser(user1, user1.copy(friends = user2Id :: user1.friends)).flatMap: res1 =>
      db.getUser(user2Id).flatMap: user2 =>
        db.updateUser(user2, user2.copy(friends = user1Id :: user2.friends)).map: res2 =>
          (res1, res2)

Monadic style, with for-comprehensions

As you have learned, combinations of flatMap and map can be written more concisely using for-comprehensions. Rewrite the previous solution using for-comprehensions:

def makeFriendsMonadicFor(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  ???

Testing

You can test your implementation by running the runMain makeFriendsMain monadic-for. It should complete in 4 seconds.

def makeFriendsMonadicFor(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  for
    user1 <- db.getUser(user1Id)
    res1 <- db.updateUser(user1, user1.copy(friends = user2Id :: user1.friends))
    user2 <- db.getUser(user2Id)
    res2 <- db.updateUser(user2, user2.copy(friends = user1Id :: user2.friends))
  yield (res1, res2)

Direct style

Finally, let’s consider Futures in the “direct” style, which is a more recent style that is gaining popularity in many languages. In this style, we also use Futures, but we allow calling await from inside Futures whenever we want. This is the future of Futures in Scala, but it is not yet ready for production use for the reasons explained in the lecture.

In this style, the makeFriends function also returns a Future[(Boolean, Boolean)]:

def makeFriendsDirect(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  ???

Implement it by calling the getUser and updateUser functions appropriately.

We also provide you with the following await extension method on Future that you can use to block until the result of a future is available:

extension [T](self: Future[T])
  def await: T = Await.result(self, 3.seconds)

In the direct style, you can call await, as long as you are inside a Future, so that you don’t block the main thread.

Testing

You can test your implementation by running the runMain makeFriendsMain direct. It should complete in 4 seconds.

def makeFriendsDirect(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  Future:
    val user1 = db.getUser(user1Id).await
    val res1 = db.updateUser(user1, user1.copy(friends = user2Id :: user1.friends)).await
    val user2 = db.getUser(user2Id).await
    val res2 = db.updateUser(user2, user2.copy(friends = user1Id :: user2.friends)).await
    (res1, res2)

Parallel execution

Can we make the makeFriends function faster by executing some of the operations in parallel? Yes, we can!

Updating the two users can be done in parallel, since they are independent. Only the final operation, notifying the caller, depends on the two updates:

Monadic style

Implement makeFriendsMonadicParallel:

def makeFriendsMonadicParallel(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  ???

Testing

You can test your implementation by running the runMain makeFriendsMain monadic-flatmap-par. It should complete in 2 seconds.

def makeFriendsMonadicParallel(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  val res1Future =
    db.getUser(user1Id).flatMap: user1 =>
      db.updateUser(user1, user1.copy(friends = user2Id :: user1.friends))
  val res2Future =
    db.getUser(user2Id).flatMap: user2 =>
      db.updateUser(user2, user2.copy(friends = user1Id :: user2.friends))
  res1Future.zip(res2Future)

def makeFriendsMonadicParallelFor(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  val res1Future =
    db.getUser(user1Id).flatMap: user1 =>
      db.updateUser(user1, user1.copy(friends = user2Id :: user1.friends))
  val res2Future =
    db.getUser(user2Id).flatMap: user2 =>
      db.updateUser(user2, user2.copy(friends = user1Id :: user2.friends))
  for res1 <- res1Future; res2 <- res2Future yield (res1, res2)

Direct style

Implement makeFriendsDirectParallel:

def makeFriendsDirectParallel(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  ???

Testing

You can test your implementation by running the runMain makeFriendsMain direct-par. It should complete in 2 seconds.

def makeFriendsDirectParallel(
    user1Id: String,
    user2Id: String,
    db: Database
): Future[(Boolean, Boolean)] =
  val res1Future = Future:
    val user1 = db.getUser(user1Id).await
    db.updateUser(user1, user1.copy(friends = user2Id :: user1.friends)).await
  val res2Future = Future:
    val user2 = db.getUser(user2Id).await
    db.updateUser(user2, user2.copy(friends = user1Id :: user2.friends)).await
  Future:
    (res1Future.await, res2Future.await)

Reimplementing parallel collections ⭐️

Remember parallel collections? How could you implement your own parallel collections using Futures?

In this exercise, you will implement ParList, a wrapper around a List that provides map, flatMap and filter methods that execute their argument functions in parallel.

def map[U](f: T => U): ParList[U] =
  ???

def flatMap[U](f: T => ParList[U]): ParList[U] =
  ???

def filter(p: T => Boolean): ParList[T] =
  ???

def map[U](f: T => U): ParList[U] =
  val futures = data.map: t =>
    Future(f(t))
  val result = Await.result(Future.sequence(futures), Inf)
  ParList(result)

def flatMap[U](f: T => ParList[U]): ParList[U] =
  ParList(map(f).data.map(_.data).flatten)

def filter(p: T => Boolean): ParList[T] =
  flatMap: t =>
    if p(t) then ParList(List(t))
    else ParList(Nil)

Task manager

In this exercise, you will implement a simple command-line task manager. To start the REPL of the task manager, run runMain tasksMain in the sbt console.

Adding tasks

The first command to implement is add. It has the form of add <time> <text>, which runs a task that first waits for <time> seconds then prints out <text>. Right now the tasks run synchronously. The REPL is blocked while the task is running, and you can only enter a new command after the task has completed.

sbt:futures> runMain tasksMain
[info] compiling 1 Scala source to /Users/linyxus/Workspace/course-material/exercises/futures/target/scala-3.3.1/classes ...
> add 10 hello
Started task
Finished task: hello
> 

Now your task is to make the tasks run asynchronously, by modifying the following definition:

case ADD_RE(duration, result) =>
  println(s"Started task")
  Thread.sleep(duration.toLong * 1000)
  println(s"Finished task: $result")
  loop()

Start by taking a look at the code in managerRepl.scala to get familiar with how the following is used throughout the program:

val tasks = collection.mutable.ArrayBuffer.empty[Future[String]]

Try numbering the tasks to distinguish them. The REPL should now work like the following:

sbt:futures> runMain tasksMain
[info] running tasksMain 
> add 5 hello
> Started task #0
add 6 world
> Started task #1
Finished task #0: hello
Finished task #1: world

Tasks with dependencies

Implement another command addafter <depid> <time> <text>, which creates a task that waits for <time> seconds then prints out <text>, but starts running only after the task with id <depid> has completed.

sbt:futures> runMain tasksMain
[info] running tasksMain 
> add 5 hello
> Started task #0
addafter 0 1 world
> Finished task #0: hello
Started task #1
Finished task #1: world

In this example, we start a task (numbered 0) that prints hello after 5 seconds, then start another task (numbered 1) which runs after the first one and prints world after 1 second. Task #1 starts only after #0 has completed.

Complete the following sketch.

case ADD_AFTER_RE(after, duration, result) =>
  ???

case ADD_RE(duration, result) =>
  val taskId = tasks.size
  val future =
    Future:
      println(s"Started task #$taskId")
      Thread.sleep(duration.toLong * 1000)
      println(s"Finished task #$taskId: $result")
      result
  tasks += future
  loop()

case ADD_AFTER_RE(after, duration, result) =>
  if after.toInt < 0 || after.toInt >= tasks.size then
    println(s"Invalid task number: $after")
    loop()
  else
    val taskId = tasks.size
    val dependency = tasks(after.toInt)
    val future = dependency.flatMap: _ =>
      Future:
        println(s"Started task #$taskId")
        Thread.sleep(duration.toLong * 1000)
        println(s"Finished task #$taskId: $result")
        result
    tasks += future
    loop()

Utility methods of future ⭐️

Implement the following utility methods of Future:

extension [T](self: Future[T])
  def map[U](f: T => U): Future[U] =
    ???

extension [T](self: Future[T])
  def flatMap[U](f: T => Future[U]): Future[U] =
    ???

extension [T](self: Future[T])
  def zip[U](other: Future[U]): Future[(T, U)] =
    ???

def sequence[T](futures: List[Future[T]]): Future[List[T]] =
  ???

def race[T](futures: List[Future[T]]): Future[T] =
  ???

You can play with your implementation by running runMain futuresTest in the sbt console.

extension [T](self: Future[T])
  def map[U](f: T => U): Future[U] =
    val promise = Promise[U]()
    self.onComplete:
      // Neat syntax trick:
      // `onComplete { case …` is the same as
      // `onComplete { x => x match case …`
      case Success(v) =>
        promise.complete(Try(f(v)))
      case Failure(e) =>
        promise.complete(Failure(e))
    promise.future

extension [T](self: Future[T])
  def flatMap[U](f: T => Future[U]): Future[U] =
    val p = Promise[U]()
    self.onComplete:
      case Success(v) =>
        Try(f(v)) match
          case Success(fvFuture) => fvFuture.onComplete(p.complete)
          case Failure(e)        => p.complete(Failure(e))
      // This branch duplicates the previous one, which is not great.
      // See below for a different solution.
      case Failure(e) => p.complete(Failure(e))
    p.future

  def flatMap2[U](f: T => Future[U]): Future[U] =
    val p = Promise[U]()
    self.onComplete: r => // More succinct version of above
      r.flatMap(v => Try(f(v))) match // This is `flatMap` on `Try`
        case Success(fvFuture) => fvFuture.onComplete(p.complete)
        case Failure(e)        => p.complete(Failure(e))
    p.future

extension [T](self: Future[T])
  def zip[U](other: Future[U]): Future[(T, U)] =
    self.flatMap: a =>
      other.map: b =>
        (a, b)

def sequence[T](futures: List[Future[T]]): Future[List[T]] =
  futures match
    case f :: fs =>
      f.flatMap: a =>
        sequence(fs).map: as =>
          a :: as
    case Nil => Future(Nil)

def race[T](futures: List[Future[T]]): Future[T] =
  val p = Promise[T]()
  futures.foreach(_.onComplete(res => if !p.isCompleted then p.complete(res)))
  p.future

GitHub contributors ⭐️

In this exercise, you will implement a function that retrieves the list of contributors of a GitHub repository, and display their names and location:

sbt:futures> runMain showContributorsMain nasa marsapi 3
[info] running (fork) showContributorsMain nasa marsapi 3
[info] Getting contributors of nasa/marsapi
[info] John from Lausanne, Switzerland
[info] Mary from somewhere
[info] James from Bangalore, India
[info] Patricia from Sydney
[info] Someone from Tokyo

The arguments to the showContributorsMain function are:

1. The name of a GitHub organization.
2. The name of a GitHub repository.
3. The number of contributors to get per page when querying the GitHub API (see below).

GitHub API

In order to get the list of contributors of a GitHub repository, we will use the GitHub REST API, in particular the list contributors endpoint and the get user endpoint:

1. The first enables us to get the list of contributors of a repository. For example, we can get the list of contributors of the lampepfl/gears repository by sending a request to https://api.github.com/repos/lampepfl/gears/contributors.
2. The second enables us to get the details of a user. For example, we can get the details of the user odersky by sending a request to https://api.github.com/users/odersky.

Pagination

The GitHub API paginates the results of most endpoints that return sequences to avoid returning too much data at once.

You can control pagination using two URL parameters:

1. per_page: the number of results to return per page. This will be the pageSize parameter of the showContributorsMain and showContributors functions.
2. page: the page number to return.

Try it with the lampepfl/gears repository!

• https://api.github.com/repos/lampepfl/gears/contributors?per_page=2
• https://api.github.com/repos/lampepfl/gears/contributors?per_page=2&page=2
• https://api.github.com/repos/lampepfl/gears/contributors?per_page=2&page=3
• https://api.github.com/repos/lampepfl/gears/contributors?per_page=2&page=4

Scala API

To call the GitHub API, we provide you with a get function that handles the JSON parsing for you. It takes a URL and returns a Future[Response[T]]:

def get[T](
    /** The URL to call. */
    uri: Uri
)(
    /** The HTTP backend used to send requests. */
    using backend: HttpBackend
)(
    /** Used to decode the response JSON to a `T`. */
    using Reader[T]
): Future[Response[T]] =

The Response contains the following 2 members that you will need to use:

1. a body field of type T, which contains the parsed JSON response.
2. a header(String) method, which returns the value of the given HTTP header.

You can for example use it as follows to query the contributors of the nasa/marsapi repository:

// The `uri` interpolator is used to create a `Uri` from a string.
val url = uri"$API_URL/repos/nasa/marsapi/contributors?per_page=3"

// `get[T]` returns a `Future[T]`.
get[List[Contributor]](url)
  // We `map` over the `Future` to access the response.
  .map(res =>
    // res.body` is a `List[RepoContributor]`:
    assertEquals(
      res.body,
      List(
        Contributor(f"$API_URL/users/john"),
        Contributor(f"$API_URL/users/mary"),
        Contributor(f"$API_URL/users/james")
      )
    )
    // Each `Response` contains a `Link` header with a link to the next
    // page. You can use the `getNextPageUrl` function to extract the link.
    // It returns an `Option[String]`:
    assertEquals(
      getNextPageUrl(res.header("Link")),
      Some(f"$API_URL/repos/0/contributors?per_page=3&page=2")
    )
  )

Contributor is defined as:

case class Contributor(
    /** API URL of the corresponding user. */
    url: String
) derives ReadWriter

To query the details of a user, you can use the get function as follows:

val url = uri"$API_URL/users/jennifer"
get[User](url)
  .map(res =>
    assertEquals(
      res.body,
      User(Some("Jennifer"), Some("Nairobi"))
    )
  )

User is defined as:

case class User(
    /** Full name of the user. */
    name: Option[String],
    /** Location of the user. */
    location: Option[String]
) derives ReadWriter:
  override def toString(): String =
    val n = name.getOrElse("Someone")
    val l = location.getOrElse("somewhere")
    f"$n from $l"

Stub API

The GitHub API is rate-limited to 60 unauthenticated requests per minute.

To avoid hitting this limit and simplify testing, we provide you with a stub API that you can use instead of the real GitHub API. You can use it by providing githubStubBackend as the HttpBackend parameter to the get function.

The examples of the previous section use the stub API.

See also how we use it in the showContributorsMain implementation:

@main def showContributorsMain(
    org: String,
    repo: String,
    perPage: Int
): Unit =
  // given HttpBackend = sttp.client4.HttpClientFutureBackend
  given HttpBackend = githubStubBackend
  given Window = ConsoleWindow
  println(f"Getting contributors of $org/$repo")
  Await.result(showContributorsDirect(org, repo, perPage), 2.seconds)

Our stub API only handles requests to the user and contributors endpoints, and only for two fake repositories: nasa/marsapi and sleepysloths/lazyloader which respectively have 5 and 2 stub contributors. All other requests will fail with a 404 Not Found error.

If you want to use the real GitHub API, you can set the given HttpBackend to HttpClientFutureBackend().

Order of execution

The crucial part of this exercise is the order in which the requests are executed and the results printed.

The following diagram illustrates the order in which the requests should be executed. If there is an arrow from A to B, it means that B should only be executed after A has completed.

When two requests are independent, they can and must be executed in parallel. For example, the requests to get the details of users $1, $2 and $3, and the request to get the second page of contributors should all be executed in parallel.

Note also that the details of users should be printed per page, as soon as the details of all users on that page have been retrieved.

Implementation

Your task is to write a showContributors method that takes 5 parameters:

1. org: the name of the GitHub organization.
2. repo: the name of the GitHub repository.
3. pageSize: the number of contributors to get per page when querying the GitHub API.
4. an implicit HttpBackend to use to query the GitHub API.
5. an implicit Window object which contains a single println method, that you should use to print the results.

Write two versions:

1. A version in monadic style, where you use the zip, flatMap and map methods of Future, and Future.sequence to combine multiple futures.
2. A version in direct style: where you use the provided await extension method on Future to block until the result of a future is available.

def showContributors(
    /** The organization that owns the repository. */
    org: String,
    /** The name of the repository. */
    repo: String,
    /** The number of contributors per page. */
    perPage: Int
)(using
    /** The HTTP backend used to send requests, used by `get`. */
    HttpBackend,
    /** Used to print the results. */
    Window
): Future[Unit] =
  def showNextPage(
      pageUri: Uri,
      prevPagePrinted: Future[Unit]
  ): Future[Unit] =
    ???
  val url = uri"$API_URL/repos/$org/$repo/contributors?per_page=$perPage"
  showNextPage(url, Future.successful(()))

def showContributorsDirect(
    org: String,
    repo: String,
    perPage: Int
)(using HttpBackend, Window): Future[Unit] =
  def showNextPageDirect(
      pageUri: Uri,
      prevPagePrinted: Future[Unit]
  ): Future[Unit] =
    Future:
      ???

  val url = uri"$API_URL/repos/$org/$repo/contributors?per_page=$perPage"
  showNextPageDirect(url, Future.successful(()))

def showContributors(
    /** The organization that owns the repository. */
    org: String,
    /** The name of the repository. */
    repo: String,
    /** The number of contributors per page. */
    perPage: Int
)(using
    /** The HTTP backend used to send requests, used by `get`. */
    HttpBackend,
    /** Used to print the results. */
    Window
): Future[Unit] =
  def showNextPage(
      pageUri: Uri,
      prevPagePrinted: Future[Unit]
  ): Future[Unit] =
    val repoContributors = get[List[Contributor]](pageUri)
    val contributors =
      repoContributors.map(_.body.map(c => get[User](uri"${c.url}")))
    val pagePrinted =
      prevPagePrinted
        .zip(contributors.flatMap(Future.sequence))
        .map(_._2.foreach(c => Window.println(c.body.toString())))
    repoContributors.flatMap(res =>
      getNextPageUrl(res.header("Link")) match
        case Some(nextPageUri) =>
          showNextPage(uri"$nextPageUri", pagePrinted)
        case None =>
          pagePrinted
    )
  val url = uri"$API_URL/repos/$org/$repo/contributors?per_page=$perPage"
  showNextPage(url, Future.successful(()))

def showContributorsDirect(
    org: String,
    repo: String,
    perPage: Int
)(using HttpBackend, Window): Future[Unit] =
  def showNextPageDirect(
      pageUri: Uri,
      prevPagePrinted: Future[Unit]
  ): Future[Unit] =
    Future:
      val repoContributors = get[List[Contributor]](pageUri).await
      val contributors =
        repoContributors.body.map(c => get[User](uri"${c.url}"))
      val pagePrinted =
        Future:
          prevPagePrinted.await
          contributors
            .map(_.await)
            .foreach(c => Window.println(c.body.toString()))
      getNextPageUrl(repoContributors.header("Link")) match
        case Some(nextPageUri) =>
          showNextPageDirect(uri"$nextPageUri", pagePrinted).await
        case None =>
          pagePrinted.await

  val url = uri"$API_URL/repos/$org/$repo/contributors?per_page=$perPage"
  showNextPageDirect(url, Future.successful(()))

Property-based testing

Most of the tests we have worked with so far have checked whether a program behaves correctly on a given set of example inputs, where we specify what the “correct behavior” is for each input (e.g. by checking the observed output against the hard-coded expected output). But often, we have a more abstract understanding of what it means for the program to be correct: we want the program’s output to satisfy certain properties for all inputs. In practice, the set of all possible inputs may be too large to be worth testing exhaustively (or even infinite), so we instead run the program on some randomly generated inputs. This technique is called property-based testing (PBT).

Note that PBT does not give us a 100% guarantee that the program satisfies the stated properties, because the randomly generated inputs cover only a fraction of the whole space of possible inputs. However, it still increases our confidence in the correctness of the program, and has only a moderate cost in terms of time and effort, making it a valuable component of the software correctness toolkit.

For the following exercises, we will use ScalaCheck, a Scala PBT library.

mSort

Problem 1 in the 2024 midterm gave you the implementation of an algorithm mSort and asked, “for each of the following properties, indicate whether it is true for all lists ls of type List[Int]”. Below is the implementation of mSort. The implementations of some helper functions were summarized with require-ensuring clauses in the midterm, but they are included in full below.

def mSort(ls: List[Int]): List[Int] =
  ls match
    case Nil            => Nil
    case a :: Nil       => a :: Nil
    case a :: b :: tail =>
      val (ll, lr) = split(tail)
      merge(mSort(ll), mSort(lr))

    /** Check if a given list is sorted */
def isSortedAscending(ls: List[Int]): Boolean =
  ls == ls.sortWith(_ < _)

/** Given two sorted lists, merge them into a new sorted list */
def merge(ll: List[Int], lr: List[Int]): List[Int] = {
  require(isSortedAscending(ll) && isSortedAscending(lr))

  (ll, lr) match
    case (Nil, _) => lr
    case (_, Nil) => ll
    case (lh :: lt, rh :: rt) =>
      if lh < rh then lh :: merge(lt, lr)
      else rh :: merge(ll, rt)
}.ensuring { l =>
  l == (ll ++ lr).sortWith(_ < _)
}

/** Split a list into two lists containing the first and second halves
  * respectively
  */
def split[A](ls: List[A]): (List[A], List[A]) = {
  val (ll, lr) = ls.splitAt(ls.length / 2)
  (ll, lr)

}.ensuring { case (ll, lr) =>
  ls == ll ++ lr && ll.length == ls.length / 2
}

And here are the properties under consideration:

// Property 1
mSort(ls).length <= 1

// Property 2
mSort(ls).length <= 2

// Property 3
isSortedAscending(mSort(ls))

// Property 4
mSort(ls).length == ls.length

// Property 5
mSort(ls).length <= ls.length

1. Specify those properties in MSortTests.scala using ScalaCheck. If you are not sure how to use the library, consult its documentation. Change their names from “Property X” to a more descriptive but concise phrase.

   property("Property 1") =
     ???
   
   property("Property 2") =
     ???
   
   property("Property 3") =
     ???
   
   property("Property 4") =
     ???
   
   property("Property 5") =
     ???
   

   property-based-testing/src/test/scala/pbt/MSortTests.scala

2. Run the tests with test in SBT and see if the properties hold. If a property fails, you will see a message like:

   failing seed for MyTest.myproperty is 8BrWGTql0mzLgIvMVGiNy0ElC7pOMWhVE3xcntwGbOF=
   [info] ! MyTest.myproperty: Falsified after 8 passed tests.
   [info] > ARG_0: List("0", "0")
   [info] > ARG_0_ORIGINAL: List("-1375979208", "2147483647")
   

   • The “seed”, 8BrW…, is for the pseudorandom input generator. It is printed so that you can reproduce the failure with the “same” random inputs if needed: testOnly -- -initialSeed 8BrW….
   • ARG_0 refers to the first (zero-indexed) argument to the property. ARG_0_ORIGINAL is the original input that triggered the failure; ScalaCheck tries to automatically simplify and minimize such inputs for easier debugging, and ARG_0 is the minimal input it could find.

3. If a property doesn’t hold, decide whether it should hold for a correct implementation or the property itself is incorrect. Fix the implementation of mSort so that the right properties hold.

Quadtrees ⭐️

A few weeks ago, we tried to improve boids with a new data structure:

In an attempt at making a boids callback better, we have implemented a quadtree data structure to hold boid collections. Quadtrees are a two-dimensional analogue of binary search trees: they are used to organize point clouds in a way that supports quick filtering and lookups (in boids, this would allow us to quickly determine which boids are close to each other, in much less time than a linear filter of all boids).

We implemented a number of methods on the quadtree: size, insert, contains, filter, iterator and a fromCollection. Sadly, under release deadline pressure, our implementation was buggy. Your task in this exercise is to identify the bugs using property-based tests, find and fix them in the code, and finally (to finish the task we started) patch boids to use the quadtree.

Here is the type definition of a quadtree:

enum QuadTree[+T] extends Iterable[T]:
  case Empty
  case Leaf(t: List[WithPos[T]])
  case Quad(center: Vector2, nw: QuadTree[T], ne: QuadTree[T], sw: QuadTree[T], se: QuadTree[T])

Which properties?

First, write down, on paper, the properties that you think a quadtree with the methods mentioned above should satisfy. For example, what can you say about the size of a quadtree? How does the size change after inserting an element, or after filtering the quadtree with various predicates?

PBT with custom types

PBT works by generating random inputs of the right types for the properties being tested. ScalaCheck has predefined generators for standard types like Int and List, but not for the custom types we’ve defined, like Vector2 and QuadTree, so you will have to write those generators. Here is an example for Vector2:

case class PosBounds(xMin: Double, xMax: Double, yMin: Double, yMax: Double):
  val xRange = xMax - xMin
  val yRange = yMax - yMin
  def transformX(x: Double): Double = x * xRange + xMin
  def transformY(y: Double): Double = y * yRange + yMin
given PosBounds(-100, 100, -100, 100)

def position(using bounds: PosBounds): Gen[Vector2] =
  for
    x <- Gen.double
    y <- Gen.double
  yield Vector2(bounds.transformX(x), bounds.transformY(y))

Gen.double uniformly samples the interval [0, 1), which we linearly transform to the interval specified in bounds. There is a default given instance of PosBounds, but code that calls position may pass in more specific instances.

Note that the generator does not explicitly use any randomness or specify the order in which random inputs are generated—it just generates one random input, delegating the randomness to Gen.double. In general, all the generators you write will be composed of these constructors (such as Gen.const) and combinators (such as Gen.listOfN) provided by ScalaCheck. Read the ScalaCheck user guide to learn how to use them. If you need even more details, consult the API documentation.

1. Implement the generator for the WithPos class.

   def withPos(using bounds: PosBounds): Gen[WithPos[Double]] =
     ???
   

   property-based-testing/src/test/scala/pbt/QuadTreeTests.scala

2. Implement the generator for an Empty quadtree.

   val genEmpty: Gen[QuadTree[Double]] =
     ???
   

   property-based-testing/src/test/scala/pbt/QuadTreeTests.scala

3. Implement the generator for a Leaf quadtree. Respect the invariant that a leaf can only have up to 4 elements.

   def genLeaves(using bounds: PosBounds): Gen[QuadTree[Double]] =
     ???
   

   property-based-testing/src/test/scala/pbt/QuadTreeTests.scala

4. Implement the generator for a Quad quadtree. Use the bounds parameter to respect the invariant that all elements in the nw quadtree should be to the northwest of the pivot of the Quad, etc.

   def genQuads(using bounds: PosBounds): Gen[QuadTree[Double]] =
     ???
   

   property-based-testing/src/test/scala/pbt/QuadTreeTests.scala

5. Implement the generator for a QuadTree. Hint: “Generating case classes” in the ScalaCheck user guide.

   val genQuadTree: Gen[QuadTree[Double]] =
     ???
   

   property-based-testing/src/test/scala/pbt/QuadTreeTests.scala

case class PosBounds(xMin: Double, xMax: Double, yMin: Double, yMax: Double):
  val xRange = xMax - xMin
  val yRange = yMax - yMin
  def transformX(x: Double): Double = x * xRange + xMin
  def transformY(y: Double): Double = y * yRange + yMin
given PosBounds(-100, 100, -100, 100)

def position(using bounds: PosBounds): Gen[Vector2] =
  // we don't use Gen.chooseNum because it prioritizes "special values" like 0, MAX, etc. and this produces duplicate positions, which we don't support
  for
    x <- Gen.double
    y <- Gen.double
  yield Vector2(bounds.transformX(x), bounds.transformY(y))

def withPos(using bounds: PosBounds): Gen[WithPos[Double]] =
  for
    pos <- position
    value <- Gen.double
  yield WithPos(pos, value)

val genEmpty: Gen[QuadTree[Double]] =
  const(QuadTree.Empty)

def genLeaves(using bounds: PosBounds): Gen[QuadTree[Double]] =
  for
    n <- Gen.choose[Int](1, QuadTree.MAX_LEAF_SIZE)
    ts <- listOfN(n, withPos)
  yield QuadTree.Leaf(ts)

def genQuads(using bounds: PosBounds): Gen[QuadTree[Double]] =
  sized: maxDepth =>
    if maxDepth <= 0 then genLeaves
    else
      for
        center <- position
        nw <- Gen.resize(maxDepth / 4, genQuads(using bounds.copy(xMax = center.x, yMax = center.y)))
        ne <- Gen.resize(maxDepth / 4, genQuads(using bounds.copy(xMin = center.x, yMax = center.y)))
        sw <- Gen.resize(maxDepth / 4, genQuads(using bounds.copy(xMax = center.x, yMin = center.y)))
        se <- Gen.resize(maxDepth / 4, genQuads(using bounds.copy(xMin = center.x, yMin = center.y)))
      yield QuadTree.Quad(center, nw, ne, sw, se)

val genQuadTree: Gen[QuadTree[Double]] =
  oneOf(genEmpty, genLeaves, genQuads)

Implementing properties

Now that we have generators for our custom types, implement the properties you previously identified.

def insertAll[T](t0: QuadTree[T])(ws: Iterable[WithPos[T]]) =
  ws.foldLeft(t0)(_.insert(_))

property("sizePossibleValues") =
  forAll: (t: QuadTree[Double]) =>
    t.size >= 0

property("insertSize") =
  forAll: (t: QuadTree[Double], w: WithPos[Double]) =>
    t.insert(w).size == t.size + 1

property("insertContains") =
  forAll: (t: QuadTree[Double], w: WithPos[Double]) =>
    t.insert(w).contains(w)

property("insertMultipleContains") =
  forAll: (t: QuadTree[Double], w: WithPos[Double], ws: List[WithPos[Double]]) =>
    insertAll(t.insert(w))(ws).contains(w)

property("filterAllTrueSize") =
  forAll: (t: QuadTree[Double]) =>
    t.filter(
      xmin = Double.MinValue,
      xmax = Double.MaxValue,
      ymin = Double.MinValue,
      ymax = Double.MaxValue,
      pred = _ => true
    ).size == t.size

property("filterAllFalseSize") =
  forAll: (t: QuadTree[Double]) =>
    t.filter(
      xmin = Double.MaxValue,
      xmax = Double.MinValue,
      ymin = Double.MaxValue,
      ymax = Double.MinValue,
      pred = _ => false
    ).size == 0

property("filterArbitrarySize") =
  forAll: (t: QuadTree[Double], f: Double => Boolean) =>
    t.filter(
      xmin = Double.MinValue,
      xmax = Double.MaxValue,
      ymin = Double.MinValue,
      ymax = Double.MaxValue,
      pred = f
    ).size <= t.size

property("filterWOnInsert") =
  forAll: (t: QuadTree[Double], w: WithPos[Double], f: Double => Boolean) =>
    t.insert(w).filter(
      xmin = w.pos.x,
      xmax = w.pos.x,
      ymin = w.pos.y,
      ymax = w.pos.y,
      pred = elem => if elem == w.t then true else f(elem)
    ).contains(w)

property("filterNotWOnInsert") =
  forAll: (t: QuadTree[Double], w: WithPos[Double], f: Double => Boolean) =>
    !t.insert(w).filter(
      xmin = w.pos.x,
      xmax = w.pos.x,
      ymin = w.pos.y,
      ymax = w.pos.y,
      pred = elem => if elem == w.t then false else f(elem)
    ).contains(w)

property("fromCollectionSize") =
  forAll: (ts: List[Double], pos: Double => Vector2) =>
    QuadTree.fromCollection(ts, pos).size == ts.size

property("fromCollectionContainsAll") =
  forAll: (ts: List[Double], pos: Double => Vector2) =>
    val tree = QuadTree.fromCollection(ts, pos)
    ts.forall(t => tree.contains(WithPos(pos(t), t)))

property("fromSetIteratorSet") =
  forAll: (ts: Set[Double], pos: Double => Vector2) =>
    val tree = QuadTree.fromCollection(ts, pos)
    ts == tree.iterator.toSet

property("emptyInsertMultipleIterator") =
  forAll: (ts: Set[Double], pos: Double => Vector2) =>
    ts.foldLeft[QuadTree[Double]](QuadTree.Empty)((t, w) => t.insert(WithPos(pos(w), w))).iterator.toSet == ts

property("treeInsertMultipleIterator") =
  forAll: (tree: QuadTree[Double], ts: Set[Double], pos: Double => Vector2) =>
    insertAll(tree)(ts.map(w => WithPos(pos(w), w))).iterator.toSet == (tree.iterator.toSet | ts)

property("Filtering respects the given boundary") =
  forAll: (ws: List[WithPos[Double]], xmax: Double, xmin: Double, ymax: Double, ymin: Double) =>
    val tree = insertAll(QuadTree.Empty)(ws)
    val filtered = tree.filter(xmin, xmax, ymin, ymax, x => true)
    def inBounds(v: WithPos[Double]): Boolean =
      v.pos.x >= xmin && v.pos.x <= xmax &&
        v.pos.y >= ymin && v.pos.y <= ymax
    ws.forall(x => inBounds(x) == filtered.contains(x))

Fixing the bugs

Run the tests and see if the properties you wrote hold. If they don’t, either fix the implementation of the quadtree so that they do, or fix the properties to better reflect how a “correct” quadtree should behave.

🔥 There is one bug that is nearly unreachable with PBT, that causes an infinite recursion. Post on Ed if you are able to find it with PBT or with some other technique! And come to the verification lecture to find out how to do even better than PBT and eliminate such bugs entirely.

  override def size: Int =
    this match
      case Empty =>
        0
      case Leaf(ts) =>
        ts.length
      case Quad(center, nw, ne, sw, se) =>
        nw.size + ne.size + sw.size + se.size

  def insert[U >: T](t: WithPos[U]): QuadTree[U] =
    this match
      case Empty    => Leaf(List(t))
      case Leaf(ts) =>
        // 🔥 Why should we have this require clause?
        // No solution provided; ask on Ed if you want to check your answer.
        require(!ts.exists(_.pos == t.pos))
        if this.size >= QuadTree.MAX_LEAF_SIZE then
          // See write-up for explanation of infinite loop bug
          val items = scala.util.Random.shuffle(ts)
          val pivot = items.head.pos
          val q: QuadTree[U] = Quad(pivot, Empty, Empty, Empty, Empty)
          items.foldLeft(q)(_.insert(_)).insert(t)
        else
          // This is needlessly inefficient. It should be replaced by
          // Leaf(t :: ts1)
          // But PBT won't help detect this, as it is a performance issue,
          // not a correctness issue.
          Leaf(ts ++ List(t))
      case Quad(center, nw, ne, sw, se) =>
        val pos = t.pos
        if pos.y <= center.y then
          if pos.x <= center.x then
            Quad(center, nw.insert(t), ne, sw, se)
          else
            Quad(center, nw, ne.insert(t), sw, se)
        else if pos.x <= center.x then
          Quad(center, nw, ne, sw.insert(t), se)
        else
          Quad(center, nw, ne, sw, se.insert(t))

  def contains[U >: T](w: WithPos[U]): Boolean =
    this match
      case Empty => false
      case Leaf(ts) =>
        ts.contains(w)
      case Quad(center, nw, ne, sw, se) =>
        val pos = w.pos
        if pos.y <= center.y then
          if pos.x <= center.x then
            nw.contains(w)
          else
            ne.contains(w)
        else if pos.x <= center.x then
          sw.contains(w)
        else
          se.contains(w)

  def filter(xmin: Double, xmax: Double, ymin: Double, ymax: Double, pred: T => Boolean): QuadTree[T] =
    this match
      case Empty => Empty
      case Leaf(ts) =>
        Leaf(ts.filter(wp => wp.pos.inBounds(xmin, xmax, ymin, ymax) && pred(wp.t)))
      case Quad(center, nw, ne, sw, se) =>
        Quad(
          center,
          if xmin > center.x || ymin > center.y then Empty
          else nw.filter(xmin, xmax, ymin, ymax, pred),
          if xmax <= center.x || ymin > center.y then Empty
          else ne.filter(xmin, xmax, ymin, ymax, pred),
          if xmin > center.x || ymax <= center.y then Empty
          else sw.filter(xmin, xmax, ymin, ymax, pred),
          if xmax <= center.x || ymax <= center.y then Empty
          else se.filter(xmin, xmax, ymin, ymax, pred)
        )

  def iterator: Iterator[T] =
    this match
      case Empty    => Iterator.empty
      case Leaf(ts) => ts.iterator.map(_.t)
      case Quad(center, nw, ne, sw, se) =>
        nw.iterator
          .concat(ne.iterator)
          .concat(sw.iterator)
          .concat(se.iterator)

object QuadTree:
  def fromCollection[T](ts: Iterable[T], pos: T => Vector2) =
    ts.foldLeft(Empty: QuadTree[T])((qt, t) =>
      qt.insert(WithPos(pos(t), t))
    )

  val MAX_LEAF_SIZE = 4

// see https://float.exposed/0x46293e5939a08cea
val a = 1.0e30
val b = 1.0000000000000002e30
val c = 1.0000000000000003e30

val q = QuadTree.Leaf(List(
  WithPos(Vector2(a, c), 1.0),
  WithPos(Vector2(b, c), 2.0),
  WithPos(Vector2(b, b), 3.0),
  WithPos(Vector2(b, a), 4.0)
))
// ensure a split on the next insert
assertEquals(q.size, QuadTree.MAX_LEAF_SIZE)

// centroid coincides with southeastern-most point
val centroidX = (a + b + b + b) / 4
val centroidY = (c + c + b + a) / 4
assertEquals(Vector2(centroidX, centroidY), Vector2(b, c))

// infinite recursion bug on this insert
val qq = q.insert(WithPos(Vector2(0.9e29, 0.9e29), 5.0))
assertEquals(qq.size, q.size + 1)

© 2023–2025 EPFL. All rights reserved.