Last updated on Friday, December 13, 2024

Contextual Abstraction

As before, exercises or questions marked ⭐️ are the most important, 🔥 are the most challenging, and 🧪 are most useful for this week’s lab.

Implicit Context (week 10) ⭐️

You have seen in previous lab and exercises an enum for arithmetic expressions. Let’s augment it with a Let form:

enum Expr:
  case Num(value: Int)
  case Var(name: String)
  case Let(name: String, value: Expr, body: Expr)
  case Add(e1: Expr, e2: Expr)
  case Sub(e1: Expr, e2: Expr)
  case Mul(e1: Expr, e2: Expr)

Write an eval function for expressions of this type. You should not use any mutable or global variables or mutable collections.

def evaluate(e: Expr): Int =
  def recur(e: Expr)(using ctx: Map[String, Int]): Int = e match
    case _ => ???

  recur(e)(using Map.empty)

Let(”x”, e1, e2) should be evaluated like {val x = e1; e2}. You can assume that every Var(x) occurs in the body b of an enclosing Let(x, e, b).

For example, the following expression should evaluate to 4:

val e3 = Let("x", Let("y", Num(1), Add(Var("y"), Var("y"))), Mul(Var("x"), Var("x")))
evaluate(e3)

Serialization with implicits (week 10) 🧪

In the webapp lab, we are using type class WireFormat[T] to represent encoding and decoding between JSON and a data type T.

In the original implementation, the type classes for different data types are defined as regular classes, which means, to use the instance of a type, we have to construct its format manually at every place.

In this exercise, your task is to use contextual abstractions to define instances of the type class WireFormat. They are defined in webapp/lib/shared/shared/src/main/scala/wires/Wires.scala.

First, you need to define the general encode and decode functions for wires at the top of the file:

def encodeWire[T](t: T)(using wt: WireFormat[T]): ujson.Value =
  ???

def decodeWire[T](js: ujson.Value)(using wt: WireFormat[T]): Try[T] =
  ???

With these two functions, you can call encode and decode functions without naming the using parameters.

Then, you need to modify the different instances of WireFormat. For example, the WireFormat[Boolean] was defined as:

object OldBooleanWire extends WireFormat[Boolean]:
  def encode(t: Boolean): Value = Bool(t)
  def decode(js: Value): Try[Boolean] = Try(js.bool)

It can be transformed to:

given WireFormat[Boolean] with
  def encode(t: Boolean): Value = Bool(t)
  def decode(js: Value): Try[Boolean] = Try(js.bool)

If you encounter any ambiguity error (this may happen when using decodeWire in a complex expression), you can specify the type argument explicitly. Try not to use summon to get the instance of a type class explicitly.

See Importing Givens for details about how to import given instances.

Ordering (week 13) ⭐️

In mathematics, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial indicates that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. For example, the set of strings is partially ordered by the substring operator. There are pairs of strings that are not comparable by substring, e.g. “abc” and “def” are not substrings of each other.

A total order or linear order is a partial order in which any two elements are comparable. For example, the set of integers is totally ordered by the <= operator.

See Partially ordered set and Total order for more details.

In Scala, the partial order is represented by scala.math.PartialOrdering, and the total order is represented by scala.math.Ordering (as a subtype of PartialOrdering).

Ordering is a type class that represents the result of comparing two values of a type. It describes both an equivalence relation and a total order on such equivalence classes:

• Equivalence relation: {(a, b) | compare(a, b) == 0}
• Total order: {(a, b) | compare(a, b) <= 0}

The sign of the result of compare indicates the ordering of the two values, where the exact values do not matter:

• Negative: a < b
• Zero: a == b
• Positive: a > b

To ensure the result is total ordering, the following properties must hold for all a, b, and c on compare:

def inverse[T](x: T, y: T)(using ord: Ordering[T]): Boolean =
  sign(ord.compare(x, y)) == -sign(ord.compare(y, x))

def transitive[T](x: T, y: T, z: T)(using ord: Ordering[T]): Boolean =
  !(ord.compare(x, y) > 0 && ord.compare(y, z) > 0) || ord.compare(x, z) > 0

def consistent[T](x: T, y: T, z: T)(using ord: Ordering[T]): Boolean =
  ord.compare(x, y) != 0 || sign(ord.compare(x, z)) == sign(ord.compare(y, z))

(where the helper function sign represents the sign of the result).

Implement the Ordering typeclass for pairs

Implement an instance of the Ordering type class for pairs of type (A, B), where A and B have Ordering instances defined on them.

It should be implemented as a lexicographic ordering, where the first component is ordered first, and the second component is ordered second. That is, (a, b) <= (c, d) if and only if:

• a < c, or
• a == c and b <= d.

// TODO: you should modify this signature according to the requirements
given pairOrdering[A, B]: Ordering[(A, B)] with
  def compare(x: (A, B), y: (A, B)): Int = ???

Example use case: Consider a program for managing an address book. We would like to sort the addresses by zip codes first and then by street name. Two addresses with different zip codes are ordered according to their zip code, otherwise (when the zip codes are the same) the addresses are sorted by street name. E.g.

type Address = (Int, String)
val addressBook: List[Address] = List(
  (1020, "Av. d'Epenex"),
  (1015, "Rte des Noyerettes"),
  (1015, "Rte Cantonale"))

val sortedAddressBook = addressBook.sorted(using Orderings.pairOrdering)

Mapping ordering

Suppose we have a data structure to store students’ information:

case class Student(name: String, year: Int)

If we want to sort a list of students by their years of admission first and names second, we can create an ordering for Student as follows:

given studentOrdering1: Ordering[Student] with
  def compare(x: Student, y: Student): Int =
    val cmp1 = x.year.compare(y.year)
    if cmp1 != 0 then cmp1 else x.name.compare(y.name)

However, we already have orderings for Int, String, and pairs, so we can use them to create an ordering for Student.

Your task is to implement a general function “mapping” a known ordering for B to a new ordering for A. It is defined as a function orderingBy, that takes a function f: A => B and an ordering for B and returns an ordering for A. The mapping function f should be constructed carefully such that the resulting ordering follows the law of total ordering as well.

def orderingBy[A, B](f: A => B)(using ord: Ordering[B]): Ordering[A] =
  ???

With orderingBy, we can create an ordering for Student:

given studentOrdering2: Ordering[Student] = orderingBy((s: Student) => (s.year, s.name))

Abstract Algebra with Type Classes (week 13)

Recall the SemiGroup and Monoid type classes from the lecture:

trait SemiGroup[A]:
  extension (x: A) def combine(y: A): A

trait Monoid[A] extends SemiGroup[A]:
  def unit: A

The laws for SemiGroup and Monoid are:

def associative[T](x: T, y: T, z: T)(using sg: SemiGroup[T]): Boolean =
  x.combine(y).combine(z) == x.combine(y.combine(z))

def identity[T](x: T)(using m: Monoid[T]): Boolean =
  m.unit.combine(x) == x && x.combine(m.unit) == x

(since Monoid is also a SemiGroup, the associative law is also required for Monoid)

Generalize reduce

We have seen a version of reduce for a list of T where T has a SemiGroup instance:

def reduceSemiGroup[T: SemiGroup](xs: List[T]): T =
  xs.reduceLeft(_.combine(_))

When we try to generalize reduce to work with any list, we run into a problem: we don’t have a default or fallback value to return when the list is empty.

Your task is to generalize reduce to work on lists of T where T has a Monoid instance such that it also works for empty lists.

def reduce[T: Monoid](xs: List[T]): T =
  xs.foldLeft(???)(???)

A general way to lift a SemiGroup to a Monoid

There are some types that have a SemiGroup instance but not a Monoid instance. For example, the set of integers (BigInt) forms a SemiGroup through min. However, there is no corresponding identity element to form a Monoid.

given SemiGroup[BigInt] with
  extension (x: BigInt) def combine(y: BigInt): BigInt = x.min(y)

To show that BigInt does not form a Monoid through min, suppose there exists an identity element u in BigInt such that min(a, u) == a for all a: BigInt. However, we can always find a v = u + 1 such that u < v and min(v, u) == u != v. Hence, there is no such identity element u in BigInt.

By adding an extra “positve infinity” element to the set and define it as the greatest element, we can form a Monoid through min.

In Scala, we usually use Option to represent the default/fallback value. Therefore, we can use Option[BigInt] to represent the integer set with “positive infinity”:

• None represents the “positive infinity” element
• Some(a) represents the integer a
• None.combine(Some(a)) is Some(a) for all a: BigInt, since a < +infinity.
• Some(a).combine(Some(b)) is Some(min(a, b)) for all a, b: BigInt

The properties of Monoid[Option[BigInt]] correspond to the properties of Monoid[Option[A]] where A has a SemiGroup instance.

Your task is to implement a Monoid instance for Option[A] given a SemiGroup instance for A.

given [A: SemiGroup]: Monoid[Option[A]] = ??? // you can modify `=` to `with`

With the Monoid instance for Option[A], we can lift a list of BigInt to a list of Option[BigInt] and then apply the general reduce function to it to find the minimum element.

val bigints = List(BigInt(-8), BigInt(2), BigInt(0), BigInt(4), BigInt(100))
reduceSemiGroup(bigints)
val posInfinity: Option[BigInt] = None
val liftedBigints = posInfinity :: bigints.map(Option(_))
// adding a positive infinity value to the list should not change the result
reduce(liftedBigints)

Reimplementing boundary/break (week 13) 🔥

Remember the boundary and break constructs from week 10? It turns out that there’s nothing magic about them: they’re just an elegant application contextual abstraction. In this exercise, we’ll recreate them from scratch.

A naive implementation

Our first implementation is simple: we define an exception Break, which will be thrown by calls to break():

/** Exception thrown by `break` internally. */
private final class Break[T](val label: Label[T], val value: T) extends RuntimeException(
      /*message*/ null, /*cause*/ null, /*enableSuppression=*/ false, /*writableStackTrace*/ false
    )

And we define a type Label which indicates where we want to jump to:

/** Labels are targets indicating which boundary will be exited by a `break`. */
private final class Label[-T]

This will allow us to write programs like the following:

val x = naiveBoundary: label =>
  for x <- 1 to 10 do
    if x > 5 then naiveBoundary.break(x)(label)
    println(x)
  10

val x2 = naiveBoundary: label =>
  for x <- 1 to 10
      _ = naiveBoundary: _ =>
        for y <- 1 to 10 do
        if y > 3 then naiveBoundary.break(y)(label)
  do if x > 5 then naiveBoundary.break(x)(label)
     println(x)
  10

Implement break and apply:

object naiveBoundary:
  /** Abort current computation and instead return `value` as the value of the
    * enclosing `boundary` call that created `label`.
    */
  def break[T](value: T)(label: Label[T]): Nothing =
    ???

  /** Run `body` with freshly generated label as argument. Catch any breaks
    * associated with that label and return their results instead of `body`'s
    * result.
    */
  inline def apply[T](inline body: Label[T] => T): T =
    ???

Reducing the label boilerplate

Our first implementation is cumbersome: we need to pass labels around explicitly, unlike the traditional boundary / break. We would like to be able to write code like this instead:

val y = boundary:
  for x <- 1 to 10 do
    if x > 5 then break(x)
    println(x)
  10

… while still being able to name labels explicitly if needed:

val y2 = boundary: label ?=>
  for x <- 1 to 10
      _ = boundary:
        for y <- 1 to 10 do
        if y > 3 then break(y)(using label)
  do if x > 5 then break(x)
     println(x)
  10

Read the documentation of context functions, and use them to recreate the original construct:

object boundary:
  /** Abort current computation and instead return `value` as the value of the
    * enclosing `boundary` call that created `label`.
    */
  def break[T](value: T)(using label: Label[T]): Nothing =
    ???

  /** Run `body` with freshly generated label as implicit argument. Catch any
    * breaks associated with that label and return their results instead of
    * `body`'s result.
    */
  inline def apply[T](inline body: Label[T] ?=> T): T =
    ???

Acknowledgement

The monoid exercise is adapted from the documentation of the Cats library.

© 2023, 2024 EPFL. All rights reserved.