Last updated on

Debugging

The best way to improve your debugging skills is to apply the debugging guide to your own code in the labs. For more focused training, however, we provide a few exercises below. Happy hacking!

These exercises cover the first two debugging lessons: you won’t be able to complete the tracing exercises before the second lecture!

As usual, ⭐️ indicates the most important exercises and questions; 🔥, the most challenging ones; and 🔜, the ones that are useful to prepare for future lectures.

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.

It may sound surprising for a debugging exercise set, but even here, we strongly encourage you to think about the exercises on paper first, in groups. Only then should you start working with the actual code. For that, you can download the scaffold code (ZIP).

Encoding issues ⭐️

Prof. Pit-Claudel recently received a spam email with the following title:

Re: Design Query for √âcole polytechnique f√(c)d√(c)rale de ...

Explain what happened.

Debugging warnings

When Prof. Pit-Claudel demoed sbt new in class, the following appeared on screen:

SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder".
SLF4J: Defaulting to no-operation (NOP) logger implementation
SLF4J: See http://www.slf4j.org/codes.html#StaticLoggerBinder for further details.

What happened?

Debugging with the substitution model ⭐️

In case you forgot how to debug with the substitution model, refer to the week 1 debrief!

Lists

removeDuplicates

  1. removeDuplicates takes a list and produces a new list with all duplicated elements removed, keeping only the first one. For simplicity, we use 1 :: 2 :: 3 :: IntNil to denote IntCons(1, IntCons(2, IntCons(3, IntNil))). For example, for a list 1 :: 2 :: 4 :: 2 :: 3 :: 3 :: IntNil, the second 2 and 3 are duplicated elements, so the returned list should be 1 :: 2 :: 4 :: 3 :: IntNil.

    The following is an (incorrect) implementation of removeDuplicates, using a function contains(l, x) that checks whether list l contains value x:

    def removeDuplicates(l: IntList): IntList =
  l match
    case IntNil() => IntNil()
    case IntCons(hd, tl) =>
      if contains(tl, hd) then removeDuplicates(tl)
      else IntCons(hd, removeDuplicates(tl))

    src/main/scala/debugging/ListOps.scala

    1. What is the expected return value of this program for the input 1 :: 2 :: 1 :: IntNil?

    2. Write down, step by step, the evaluation of removeDuplicates(IntCons(1, IntCons(2, IntCons(1, IntNil())))), using the substitution model. You may assume that contains correctly computes its result and substitute calls to it in a single step.

      (Consider using an erasable surface, such as a whiteboard, tablet, or writing slate, to reduce repetition).

      Where does the computation diverge from the expected result?

    3. Fix the implementation.

Binary search trees

isBST

A Binary Search Tree (BST) is a binary tree such that the value carried by each node is greater than all values in the left subtree and smaller than all values in the right subtree. For example, the following is a binary search tree:

       8
      / \
     3   10
    / \   \
   1   6   14

  1. Can a binary search tree contain duplicate values?

  2. Is the following tree a BST?

    val t0 =
  IntBranch(5,
    IntBranch(2, IntEmptyTree(), IntEmptyTree()),
    IntBranch(10,
      IntBranch(4, IntEmptyTree(), IntEmptyTree()),
      IntEmptyTree())))

  3. The function isBST takes a binary tree and returns true if the tree is a binary search tree, false otherwise. Here is one candidate implementation of it:

    def isBST(t: IntTree): Boolean =
  t match
    case IntEmptyTree() => true
    case IntBranch(v, l, r) =>
         (l == IntEmptyTree() || v > l.value)
      && (r == IntEmptyTree() || v < r.value)
      && isBST(l)
      && isBST(r)

    src/main/scala/debugging/TreeOps.scala

    1. There is something wrong with this implementation. But what? Using the substitution method, show what isBST(t0) evaluates to (t0 refers to the tree above):

      For succinctness, we recommend writing IntEmptyTree as ε, IntBranch(v, l, r) as [v, l, r], and IntBranch(v, IntEmptyTree, IntEmptyTree) as [v], so that this input is written as follows:

      isBST([5 [2] [10 [4] ε]])

  4. Fix the implementation.

insert

Binary search trees are convenient to represent sets of values. To use them in this way, e need a contains function and an insert function.

Let’s focus on the insert function. insert takes a binary search tree representing a set of values $V$ and a new value $v_1$, and returns a new binary search tree representing the set $V \cup {v_1}$.

The following is an attempt at implementing insert:

def insert(t: IntTree, v1: Int): IntTree =
  t match
    case IntEmptyTree() => IntBranch(v1, IntEmptyTree(), IntEmptyTree())
    case IntBranch(v0, l, r) =>
      if v1 < v0 then IntBranch(v0, insert(l, v1), r)
      else IntBranch(v0, l, insert(r, v1))

src/main/scala/debugging/TreeOps.scala

  1. Find a counterexample: an binary search tree t and an input v1 such that insert(t, v1) produces an incorrect result.

  2. Fix the implementation.

Debugging expressions with side effects 🔜

We will study stateful code in depth in week 10. Since some of you have already started using vars, however, here is an exercise on this topic.

Pure expressions can be evaluated in any order. Given def f(x: Int) = x + 1, you can substitute f(1) with 1 + 1 whenever you like and it doesn’t affect the final result.

On the other hand, the evaluation order matters for expression with side effects. Think about a function g that prints a message: in the program g("Hello "); g("world!"), it’s important that g("Hello ") be evaluated before g("world!"), otherwise "world!Hello " will printed instead of "Hello world!".

Reminder: Scala uses the call-by-value evaluation strategy by default.

upgradeUserToVip

Someone is writing a user-management program for a supermarket like Aligro. It maintains two global lists: users contains all users, vipUsers contains the VIP users. Any VIP user is in the users list as well.

var users: IntList = IntCons(101, IntCons(102, IntCons(103, IntNil())))
var vipUsers: IntList = IntCons(102, IntNil())

src/main/scala/debugging/ListOps.scala

createNewUser takes a user ID and creates a new user using this ID. It returns true if the new user was successfully created, and false if the ID was already in use (in that case, the user database is left unmodified).

def createNewUser(id: Int): Boolean =
  if contains(users, id) then false
  else
    users = IntCons(id, users)
    true

src/main/scala/debugging/ListOps.scala

createNewVipUser is similar to createNewUser, but it creates a new VIP user if it’s not already a VIP. Like createNewUser, it returns true if a new VIP user was successfully created.

def createNewVipUser(id: Int): Boolean =
  if contains(vipUsers, id) then false
  else
    vipUsers = IntCons(id, vipUsers)
    true

src/main/scala/debugging/ListOps.scala

Finally, upgradeUserToVip takes a user ID, and if this ID indeed belongs to a user and this user is not a VIP yet, it upgrades the user to VIP. It returns true if the upgrade was successful.

def upgradeUserToVip(id: Int): Boolean =
  val canCreateNewVipUser = createNewVipUser(id)
  contains(users, id) && canCreateNewVipUser

src/main/scala/debugging/ListOps.scala

  1. This program contains a bug. What’s the bug?

  2. Fix the bug.

Tracing code execution

Wait until the tracing and tests lecture to tackle this!

Polish notation (from week 1) ⭐️

Use tracing to gain a better understanding of the following function, which computes the value of a polish-notation expression:

enum Operand[+T]:
  case Add extends Operand[Nothing]
  case Mul extends Operand[Nothing]
  case Num(t: T)

type OpStack[T] = List[Operand[T]]

src/main/scala/debugging/Tracing.scala

def polishEval(ops: OpStack[Int]): (Int, OpStack[Int]) =
  ops match
    case Nil => throw IllegalArgumentException()
    case op :: afterOp =>
      op match
        case Operand.Num(n) =>
          (n, afterOp)
        case Operand.Add =>
          val (l, afterL) = polishEval(afterOp)
          val (r, afterR) = polishEval(afterL)
          (l + r, afterR)
        case Operand.Mul =>
          val (l, afterL) = polishEval(afterOp)
          val (r, afterR) = polishEval(afterL)
          (l * r, afterR)

src/main/scala/debugging/Tracing.scala

McCarthy ⭐️

What does the following function do? Use tracing annotations to figure it out!

def mc(n: Int): Int =
  if n > 100 then n - 10
  else mc(mc(n + 11))

src/main/scala/debugging/Tracing.scala

Takeuchi 🔥

What do the following functions do? Use tracing annotations to figure it out!

def t(x: Int, y: Int, z: Int): Int =
  if x <= y then y
  else
    t(
      t(x - 1, y, z),
      t(y - 1, z, x),
      t(z - 1, x, y)
    )

src/main/scala/debugging/Tracing.scala

This function and the previous one were both important in the development of computer-assisted proofs, as they exhibit complex, nested recursion patterns. [This 1991 paper](https://arxiv.org/pdf/cs/9301113.pdf) discusses the two examples above (and the problems it lists as “open problems” have now been solved!).

Tree folds

Two functions pairs and foldt are defined below. Use examples, pictures, the substitution method, refactoring, or tracing to figure out what foldt does.

extension [T](l: List[T])
  def pairs(op: (T, T) => T): List[T] = l match
    case a :: b :: tl => op(a, b) :: tl.pairs(op)
    case _            => l
  def foldt(z: T)(op: (T, T) => T): T = l match
    case Nil       => z
    case List(t)   => t
    case _ :: tail => l.pairs(op).foldt(z)(op)

src/main/scala/debugging/Tracing.scala

Armed with that knowledge, can you figure what algorithm the function ms below implements? Is it efficient? How does it differ from another version of the same algorithm that you saw previously?

extension (l: List[Int])
  def ms: List[Int] =
    l.map(List(_)).foldt(Nil)(merge)

src/main/scala/debugging/Tracing.scala

(merge is the usual function that takes two sorted lists and merges them in sorted order:)

def merge(l1: List[Int], l2: List[Int]): List[Int] =
  (l1, l2) match
    case (Nil, l) => l
    case (l, Nil) => l
    case (h1 :: t1, h2 :: t2) =>
      if h1 <= h2 then h1 :: merge(t1, l2)
      else h2 :: merge(l1, t2)

src/main/scala/debugging/Tracing.scala

Tracing performance issues

Sometimes, tracing can even help find performance issues: the longer a calculation takes, and the slower tracing statements will appear on screen. Can you use this insight to demonstrate that something is wrong with each of the following functions?

  1. Reverse
def badReverse[T](l: List[T], acc: List[T] = Nil): List[T] =
  l match
    case Nil    => acc.reverse
    case h :: t => badReverse(t, acc ++ List(h))

src/main/scala/debugging/Tracing.scala

  1. Map
def badMap[T1, T2](l: List[T1], f: T1 => T2): List[T2] =
  if l.length == 0 then Nil
  else f(l.head) :: badMap(l.tail, f)

src/main/scala/debugging/Tracing.scala

© 2023, 2024 EPFL. All rights reserved.