Last updated on Friday, December 13, 2024

Week 3 debrief: `calculator`, `find-hof` callback, and debugging

Congrats on completing your third week of CS-214! Here is a round-up of interesting questions, tips for exercises and labs, and general notes about the course.

Administrivia

Tuesday help sessions

We have new help sessions on Tuesdays 4-7PM in INF 1, 2, 3: they are the perfect opportunity to get help with labs or exercises in person, which is often easier than online.

Feedback Poll this week

Please fill out the feedback poll for the first 4 weeks of the course! Your feedback will help us gain insights on the state of the course and adjust to future weeks.

Callbacks and labs: grading

Labs and callbacks are both graded. More details about grading, including how scores are distributed between labs and callbacks, are in our course policies.

The debugging lecture contains a guide on how to ask questions on Ed, and on how to debug. Please follow these guides when asking questions on Ed: learning to debug is an objective of this class, and asking good questions shows respect for the time and efforts of our student assistants. Thanks!

Interesting questions on Ed

Scala syntax:

Using sbt:

Invoking sbt commands with arguments directly from the command line

Debugging `calc`

The calc lab is designed to exercise your debugging abilities. If you run into an issue (for example an incomplete simplification), use the debugging guide! The key aspect here is to simplify and minimize: do not spend time attempting to understand a very large and complex random test.

Instead:

Simplify the test by repeatedly removing parts of it, until you converge to a minimal test.
Confirm that you understand what the code is supposed to do:

a. Start by computing by hand what should happen (not by following your code; by following the problem statement).

b. Then, confirm that this is the expected test result: if not, you misunderstood the problem statement.
Debug your code:

a. Confirm that you understand what it does by running it by hand, comparing the result to what it produces in a worksheet. If the two do not match, you misunderstood how Scala works.

b. Compare the execution of your code with the notes you made in step 2. Where do things diverge?
Fix the issue: step 3 should tell you precisely where things go wrong.

If you need help, ask on Ed or in person, but make sure to show us what you attempted.

If your recursive functions run too slowly…

Consider the following function:

/** Returns the maximum value of the list. */
def max(l: IntList): Int = l match
  case IntNil                                  => 0
  case IntCons(head, tail) if head > max(tail) => head
  case IntCons(head, tail)                     => max(tail)

exponential.worksheet.sc

We write some code that uses it:

object IntList:
  def repeat(num: Int, times: Int): IntList =
    if times == 0 then IntNil else IntCons(num, repeat(num, times - 1))

val list = IntList.repeat(5, 50)
val maxOfList = max(list) // runs forever

exponential.worksheet.sc

And max runs seemingly forever, even for a small list of 50 elements! Can you find out why it does? (Hint: Use substitution method to find out how many recursive calls to max do we make)

Answer

We call max on a list of 50 elements, which calls max twice on a list of 49 elements, each calling max twice on a list of 48 elements (for a total of 4 times), … so the total number of calls to max is $$ \sum\limits_{k = 0}^{50} 2^{50 - k} = 2^{51} - 1 $$ The number of calls is exponential to the number of elements! There is some cost in performing a function call itself, but also each call will need to do some redundant computations, further adding to the running time.

We can compute the same result while recursing fewer times by computing max(tail) only once and remembering the result in a val. This means max will be called only once per element in the list.

/** Returns the maximum value of the list. */
def maxLinear(l: IntList): Int = l match
  case IntNil => 0
  case IntCons(head, tail) =>
    val tailMax = maxLinear(tail)
    if head > tailMax then head else tailMax

exponential.worksheet.sc

We will see similar analyses in week 6.

Two classic debugging stories

Here is an interesting debugging story from OpenOffice:

Open Office doesn’t print on Tuesdays

And here is another amusing debugging story:

We can’t send mail more than 500 miles

(The lecture slides have additional links to good resources on debugging.)