Last updated on

Week 2 debrief: Schedule changes, boids lab, and equational reasoning

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

Administrivia

Interesting links and Ed questions

Reflecting on recursion and HOF exercises

What should product and allEven return for empty lists?

Here are two ways to think of these:

Simplicity

You could make these functions throw an exception for empty lists. Here is what this would look like for product:

def product(l: IntList):
  if l.isEmpty then throw new InvalidArgumentException("Empty!")
  else if l.tail.isEmpty then l.head
  else l.head * product(l.tail)

But! Perhaps we could make this nicer if we allowed ourselves to return a different value for empty lists. What should this value be?

def product(l: IntList):
  if l.isEmpty then ???
  else l.head * product(l.tail)

Let’s see by substitution:

product(IntCons(3, IntNil))
3 * product(IntNil)
3 * ???

So ??? should be such that 3 * ??? = 3. Hence, product(IntNil) should be 1!

Desirable properties

Another way to think of this issue is to think of what properties we want our functions to have:

Using equational reasoning to simplify allPositiveOrZero

In the recursion exercise set, some of you ended up with the following definition for allPositiveOrZero:

def allPositiveOrZero(l: IntList): Boolean =
  if !l.isEmpty then
    if l.head < 0 then false
    else allPositiveOrZero(l.tail)
  else true

equational.worksheet.sc

That’s pretty heavy! There are two nested if ... then ... else ... blocks in there. Let’s see how we might improve this a bit, using equational reasoning.

What is equational reasoning? In Algebra, if we know that the following identity is true: $$ (a + b)^2 = a^2 + 2ab + b^2 $$ then we can immediately know that $$ (xz + y^2)^2 = (xz)^2 + 2xzy^2 + (y^2)^2 $$ is also true, by substituting in $a \mapsto xz$ and $b \mapsto y^2$. We can do the same thing when writing functional programs!

Here are a few identities that we can show, with Boolean values:

  1. !!c = c
  2. if c then t else e = if !c then e else t
  3. !(x < 0) = x >= 0
  4. if c then false else e = !c && e
  5. if c then e else true = ??? (try to fill in the blank!)

Do you know how to prove these? (Hint: remember truth tables, from ICC?)

Now, back to allPositiveOrZero. Can you use any of the identities above to simplify the code?

Step 1 
if l.head < 0 then false
else allPositiveOrZero(l.tail)

equational.worksheet.sc

is exactly our identity (4), if we substitute c with l.head < 0 and e with allPositiveOrZero(l.tail). We can then immediately rewrite our equation into !(l.head < 0) && allPositiveOrZero(l.tail).

What’s the next step?

Step 2

Going one step further, identity (2) now also applies to !(l.head < 0), so we can further rewrite the function into

def allPositiveOrZero2(l: IntList): Boolean =
  if !l.isEmpty then
    l.head >= 0 && allPositiveOrZero2(l.tail)
  else true

equational.worksheet.sc

Can you simplify it further, eliminating the remaining if expression?

Step 3

Identity (5) can be written as if c then e else true = !c || e. Substituting c with !l.isEmpty and e with (l.head >= 0 && allPositiveOrZero(l.tail)) (notice the ()! One should always be careful about substitutions, in order to not introduce some confusion between operators, just like in algebra), and we get !!l.isEmpty || (l.head >= 0 && allPositiveOrZero(l.tail)).

One more step?

Step 4

We can apply (1) as well, resulting in our final code

def allPositiveOrZero3(l: IntList): Boolean =
  l.isEmpty || (l.head >= 0 && allPositiveOrZero3(l.tail))

equational.worksheet.sc

Pretty short and sweet! And think of what this code says… it’s exactly the English spec! “A list is all positive or zero if either it is empty, or its first element is positive or zero, and all remaining elements are all positive or zero.”

A note on side effects

A recurring question in the find lab was: why does my code print too much, or too little?

To explore this, here is a puzzle. Can you find an input for which the following two programs behave differently?

def allPositiveOrZeroPrint(l: IntList): Boolean =
  l.isEmpty || {
    val headPositive = l.head >= 0
    val tailPositive =
      println("checking tail!")
      allPositiveOrZeroPrint(l.tail)
    tailPositive && headPositive
  }

equational.worksheet.sc

def allPositiveOrZeroPrintInlined(l: IntList): Boolean =
  l.isEmpty || {
    l.head >= 0 && {
      println("checking tail!")
      allPositiveOrZeroPrintInlined(l.tail)
    }
  }

equational.worksheet.sc

Solution

Due to the short-circuiting behavior of the || operator, the first program will print “checking tail” when l.head is negative, whereas the second one will not.

Bonus question: what would happen if the vals were replaced by defs in the first program?

When rewriting code using equational rewriting, mind what assumptions you’re making about the code! In many cases, equations are valid only if you only care exclusively about the value of the expression, and not what other “side effects” it does during the computation, such as printlning to the screen, updating vars, etc. We will say much more about side effects in week 10.

© 2023, 2024 EPFL. All rights reserved.