Code Termination

In this lesson, we will learn how some expressions might terminate under CBN, but not under CBV.

Both CBV and CBN will reduce an expression to the same value as long as the expression is guaranteed to terminate. But what if a piece of code is not guaranteed to terminate?

  • If the CBV evaluation of an expression terminates, then the CBN evaluation of the same expression will also terminate.
  • If the CBN evaluation of an expression terminates, then the CBV evaluation of the same expression is not guaranteed to terminate.

Let’s look at an example of an expression which terminates under CBN, but not under CBV.

Press + to interact
def loop :Int = loop
def accessFirst(x: Int, y: => Int) = x
val result = accessFirst(1,loop)
println(result)

In the code above, we start with a function loop which has zero parameters and simply returns itself; this function will infinitely run and never terminate.

On line 3 we define another function accessFirst which has two parameters and simply returns the first one. However, we have enforced the second parameter to be evaluated using CBN by inserting => after the name of the second parameter.

Finally, on line 5 we are calling accessFirst with 1 as the first parameter and the function loop as the second.

When you run the code above it will give you a warning that loop is simply returning itself resulting in an infinite loop. Ignore the warning and look at the output. You will see the number 1. This is because CBN only evaluates the parameters which are required by the function body, hence, loop is never evaluated, and the compiler isn’t stuck in an infinite loop.

How would the same code work with CBV? Let’s take a look.

Press + to interact
def loop :Int = loop
def accessFirst(x: Int, y: Int) = x
val result = accessFirst(1,loop)
println(result)

If you run the code above, you will get a runtime error Execution Timed Out!. The error is a result of the code not terminating. CBV reduces each expression, regardless of whether the function body will use it or not. This causes the compiler to get stuck in an infinite loop as the loop function never terminates.

In the next lesson, we will learn how to call a function within its own function body.