Last updated on Thursday, September 18, 2025

Good to understand (week 1)

This Good to understand document provides answers to commonly asked questions.

This document does not contain new material. We encourage you to check out the table of contents and choose the sections that interest you.

Other than that, you are not required to read the entire document, as its content is already covered in the lectures, exercises or labs.

Sections marked with 📘 are alternative explanations of course material that is already covered in lectures, exercises or labs. Sections marked with 🚀 are here to satisfy your curiosity, but you will not be graded on them.

How to deal with stack overflows and never-ending programs 📘

When dealing with recursive functions, it’s easy to run into an infinite loop and obtain a never-ending test, or an error such as:

java.lang.StackOverflowError
	at factorial(file.scala:9)
	at factorial(file.scala:9)
	at factorial(file.scala:9)
	at factorial(file.scala:9)
	at factorial(file.scala:9)
  ...

This error means that your program exhausted the call stack, a designated memory area where your program stores information about the function currently executing. Every time you make a recursive call, an entry get added to the call stack: if you recurse too deep, it runs out of space, and your program throws a StackOverflowError.

Sometimes, the compiler can optimize away uses of recursion. This is called “tail recursion elimination”; we will study it in week 10.

If you run into this issue, look out for the following points:

Make sure that your function can stop at some point: It needs a base case. For example, the length function stops when encountering an empty list:
```
def length(l: IntList): Int =
    if l.isEmpty then 0 // base case, this is where the method stops
    else 1 + length(l.tail) // recursive call
```
2025-09-14/code/stackOverflow.worksheet.sc
Starting to write your recursive method by asking “What happens in this trivial case (0, Nil, etc.)?” can help you think about the whole problem.
Check that the recursive call is decreasing: for the whole function to terminate, each call must get a bit closer to the end of the problem. Here is an obviously bad example:
```
def badLength(l: IntList): Int =
    if l.isEmpty then 0
    else 1 + badLength(l) // Woops, nondecreasing call!
```
2025-09-14/code/stackOverflow.worksheet.sc
Sometimes, a function that looks fine may have incorrect behavior for unexpected inputs. What happens if the function below is called on -1?
```
def factorial(n: Int): Int =
  if n == 0 then 1 else n * factorial(n - 1)
```
2025-09-14/code/stackOverflow.worksheet.sc
There are various strategies in this case. You can extend the scope of the base case:
```
def factorialDefault(n: Int): Int =
  if n <= 0 then 1 else n * factorialDefault(n - 1)
```
2025-09-14/code/stackOverflow.worksheet.sc
… or you can rule out illegal values:
```
def factorialRequire(n: Int): Int =
  require(n >= 0, "Illegal negative value passed to factorial.") // check for illegal values
  def rec(n: Int): Int =
    if n == 0 then 1 else n * rec(n - 1)
  rec(n)
```
2025-09-14/code/stackOverflow.worksheet.sc

You can use `if` inside `val`! 📘

Remember that, in Scala, if is an expression. This means that you can use it in all contexts:

(if b1 then 1 else 2) + (if b2 then 10 else 20)

2025-09-14/code/find.worksheet.sc

val result =
  if x == y then
    println("They are equal!")
    true
  else false
println(result)

2025-09-14/code/find.worksheet.sc

What is the meaning of and `if` without an `else`? 📘

In Scala everything is an expression, so is the if ... then ... else statement. If has the same return type for both then and else branches, e.g. the following code

if someCond then 3 else 5

2025-09-14/code/ifElse.worksheet.sc

will return an Int. An if without an else is similar, but it will always return a Unit. If the condition is satisfied, it will execute the code in the then branch, but return a Unit instead of the expression. When the condition isn’t satisfied, a Unit is returned.

if someCond
then
  println("condition met!") // this will be printed if the condition is met
  3 // a `()` will be returned instead of `3`

2025-09-14/code/ifElse.worksheet.sc

How can the Scala compiler be written in Scala? 🚀

Scala compiler is written in Scala. How is that possible? It’s thanks to a process called “bootstrapping”. Take a minute to think about it before reading on!

Spoilers!

In short, to write a Scala compiler in Scala, we:

First, we write a compiler for a very small subset of Scala (call it nanoScala), in another language (for example, Java or C).
Then, we write a compiler for nanoScala in nanoScala itself. Using the compiler in the previous step, we can now compile this compiler. Additionally, we can now use this compiled compiler to compile itself. At this point, we can stop using Java or C — it’s all nanoScala.
Then, we start adding features to our nanoScala. We modify the compiler nanoScala compiler to accept a larger language, let’s say µScala. Since this compiler is still written in nanoScala, we can use the binary from the previous step to compile it. At this point we have a compiler that can compile µScala, so we can start using µScala features in our compiler… which is now written in µScala.
Rinse and repeat, until we have implemented all features of Scala!

This is exactly how the Scala 3 compiler was written: from scratch, starting with a Scala 2 codebase.

Having a compiler compile itself leads to all sorts of fascinating questions and challenges, not least of which is the questions of trusting trust.

And it’s not just compilers! Build systems also have this chicken-and-egg problem. SBT is written in Scala: how is it compiled?

Debugging with the substitution model 📘

The substitution model that we studied in class is a great debugging tool. As an example, let’s try to walk through one of the problematic implementations of collectEven in recursion exercise.

Being a good CS-214 student, we’ve thought about the approach on paper. We’ve written down some pseudocode for what we want to do, given a list l (unfortunately, that pseudocode is wrong!):

If l is empty, there’s nothing to do, we just return an empty list.
If l is non-empty, we consider its head element. a. If the head is odd, we can collect even numbers from the tail, and then add back the head with IntCons. b. Otherwise, we can just call ourselves on the same list.

So we write some code:

def collectEven0(l: IntList): IntList =
  if l.isEmpty then IntNil()
  else
    if l.head % 1 == 0 then IntCons(l.head, collectEven0(l.tail))
    collectEven0(l)

2025-09-14/code/collectEven.worksheet.sc

Unfortunately this implementation doesn’t pass the tests. In fact, it even hangs forever! What to do?

Let’s first skim through the code to check for easy typos. Here, we want to check whether l.head is even, but mistakenly tried to find the remainder modulo 1 instead of 2! Nice catch, fixed:

def collectEven1(l: IntList): IntList =
  if l.isEmpty then IntNil()
  else
    if l.head % 2 == 0 then IntCons(l.head, collectEven1(l.tail))
    collectEven1(l)

2025-09-14/code/collectEven.worksheet.sc

Unfortunately, that’s not enough: the code still loops forever… and we can’t spot anything obvious. Time to use the substitution model to help us understand what’s going on. Let’s pick an example, say IntCons(2, IntCons(3, IntNil())). We’ll write it as [2 3] for succinctness. Let’s write down every step of our algorithm.

Going through the steps...

collectEven([2 3])

Substitute the function body…

if [2 3] is empty then IntNil()
else
  if [2 3].head is even
  then IntCons([2 3].head, collectEven([2 3].tail))
  else collectEven([2 3])

[2 3] is not empty, so we can reduce the if expression by the else branch

if [2 3].head is even
then IntCons([2 3].head, collectEven([2 3].tail))
else collectEven([2 3])

[2 3].head is just 2, which is even, so we reduce to the then branch…
```
IntCons(2, collectEven([2 3].tail))
```
[2 3].tail is [3]:
```
IntCons(2, collectEven([3]))
```

Let’s substitute the function body again.

IntCons(2, {
  if [3] is empty then IntNil()
  else
    if [3].head is even
    then IntCons([3].head, collectEven([3].tail))
    else collectEven([3])
})

[3] is not empty, reduce if.

IntCons(2, {
  if [3].head is even
  then IntCons([3].head, collectEven([3].tail))
  else collectEven([3])
})

[3].head is 3, which is odd, so we reduce to the else branch…
```
IntCons(2, collectEven([3]))
```
… wait, we’ve seen this before!

After a few steps, we run into an infinite loop. Looking at our hand written algorithm again, we see that in the odd number case, we should just drop the head, and recursively continue with just the tail. Making some fixes…

def collectEven2(l: IntList): IntList =
  if l.isEmpty then IntNil()
  else
    if l.head % 2 == 0 then IntCons(l.head, collectEven2(l.tail))
    collectEven2(l.tail)

2025-09-14/code/collectEven.worksheet.sc

Good news: The tests finish! But they are still not passing… Looking at the tests shows stat with input [2 3] we return [], an empty list.

Let’s try the substitution method again, with the same input.

Going through the steps...

collectEven([2 3])

Substitute the function body…

if [2 3] is empty then IntNil()
else
  if [2 3].head is even
  then IntCons([2 3].head, collectEven([2 3].tail))
  else collectEven([2 3].tail)

[2 3] is not empty, so we can reduce the if expression by the else branch

if [2 3].head is even
then IntCons([2 3].head, collectEven([2 3].tail))
else collectEven([2 3].tail)

[2 3].head is just 2, which is even, so we reduce to the then branch…
```
IntCons(2, collectEven([2 3].tail))
```
[2 3].tail is [3]:
```
IntCons(2, collectEven([3]))
```

Let’s substitute the function body again.

IntCons(2, {
  if [3] is empty then IntNil()
  else
    if [3].head is even
    then IntCons([3].head, collectEven([3].tail))
    else collectEven([3].tail)
})

[3] is not empty, reduce if.

IntCons(2, {
  if [3].head is even
  then IntCons([3].head, collectEven([3].tail))
  else collectEven([3].tail)
})

[3].head is 3, which is odd, so we reduce to the else branch…
```
IntCons(2, collectEven([3].tail))
```
[3].tail is the empty list [].
```
IntCons(2, collectEven([]))
```

Let’s substitute the function body again.

IntCons(2, {
  if [] is empty then IntNil()
  else
   if [].head is even
   then IntCons([].head, collectEven([].tail))
   else collectEven([].tail)
})

This time, [] is empty, so we have the else branch substituted:
```
IntCons(2, IntNil())
```

The result is [2], which should be correct, but our Scala code is not agreeing. This means that we must have misunderstood something about Scala itself. And indeed, once we look carefully, we notice a missing else in front of collectEven!

def collectEven2(l: IntList): IntList =
  if l.isEmpty then IntNil()
  else
    if l.head % 2 == 0 then IntCons(l.head, collectEven2(l.tail))
    collectEven2(l.tail)

2025-09-14/code/collectEven.worksheet.sc

In Scala, an if without an else is not an early return, so the results of the first two lines are simply ignored: we always return l.tail.

With better tests, we would have found the problem even faster: for example, collectEven(IntNil()) would have raised an exception when executing l.tail. We fix the problem, and…

def collectEven3(l: IntList): IntList =
  if l.isEmpty then IntNil()
  else
    if l.head % 2 == 0 then IntCons(l.head, collectEven3(l.tail))
    else collectEven3(l.tail)

2025-09-14/code/collectEven.worksheet.sc

Hooray, our tests are passing now! 🎉 The substitution model has helped us:

Spot the bug in our thinking, and
Spot the bug in our understanding of Scala syntax!

We picked a difficult case here (tests were hanging!), but usually a failing test will tell you which input is failing as well.

However, try to come up with inputs on your own as well! It will help to think about edge cases (negative numbers, empty lists, …)… and you won’t always have CS-214 staff to provide you with good test cases!

What is the difference between `val` and `def`? 📘

The difference between val and def is in the way they are evaluated. val is evaluated once in the place where it is defined, this is called call-by-value. def isn’t evaluated immediately at definition, but rather is evaluated each time at the call side, this is called call-by-name.

Let’s look at an example, can you guess what this snippet will print?

val byValue = 
  println("wow")
  1

if byValue + byValue == 2
then println("ok")
else println("not ok")

2025-09-14/code/valVsDef.worksheet.sc

What if we change val to def?

def byName =
  println("wow")
  1

if byName + byName == 2
then println("ok")
else println("not ok")

2025-09-14/code/valVsDef.worksheet.sc

Spoilers!

First snippet will print:

wow
ok

byValue is evaluated once in the place it is defined.

The second snippet will print:

wow
wow
ok

byName is evaluated twice, when it’s called in the if statement.

Note: for pure expressions (without side effects) there is no difference in the output of the program, but there may be a difference in performance.

Good to understand (week 1)

How to deal with stack overflows and never-ending programs 📘

You can use if inside val! 📘

What is the meaning of and if without an else? 📘

How can the Scala compiler be written in Scala? 🚀

Debugging with the substitution model 📘

What is the difference between val and def? 📘

You can use `if` inside `val`! 📘

What is the meaning of and `if` without an `else`? 📘

What is the difference between `val` and `def`? 📘