Call By Value vs Call By Name

TIL the difference between Call By Value and Call by Name expression evaluation strategies implemented by languages such as Scala.

I’m in the middle of a very good Coursera course about Functional Programming taught by Martin Odersky, one of the creators of Scala.

In the first week of the course he goes in depth in to how the Scala interpreter evaluates expressions, and how different evaluation strategies can lead to different program results.

Call by Value

Call by Value (CBV) is Scala’s default method of evaluating expressions. This strategy evaluates expressions as soon as they are encountered, instead of waiting to see if the expression will be used or not. It is also the evaluation strategy used when the Scala interpreter encounters a variable defined as ‘val’: the expression assigned to the variable is evaluated immediately, and evaluation is not deferred until absolutely needed. If expressions are passed to a function as parameters, then those expressions will be evaluated before the function body is substituted with the function call, and formal parameters swapped with actual parameters (see example below).

Example 1:

//Imagine we have the following function
def square(x, y) = x * x

//this is how the value will be resolved from a function call with CBV evaluation

square(2*2, 2+3) //function call
square(4, 2+3) //reduction 1
square(4, 5) //reduction 2
4 * 4 //reduction 3
16 //reduction 4

Note above that parameter y was never used in the body of the function, but the result of the expression that was passed to it was evaluated anyways. This is wasted computation.

Call by Name

Contrast CBV with Call by Name (CBN): expression evaluation is deferred until the value is absolutely needed. Take the example I used above and see how the reduction differs:

Example 2:

//Imagine we have the following function
def square(x, y) = x * x

//this is how the value will be resolved from a function call with CBN evaluation

square(2*2, 2+3) //function call
(2 * 2) * (2 * 2) //reduction 1
4 * (2 * 2) //reduction 2
4 * 4 //reduction 3
16 //reduction 4

Notice that the expression 2+3 is never calculated, but the expression (2 * 2) is calculated twice, which is also wasted computation if the expression is used many times throughout a function body or program. Although the default is CBV, it is possible in Scala to pass a parameter that is evaluated with CBN evaluation strategy. Just pass it in with an => and evaluation of the expression will be deferred until needed.

Assertions on Termination

The following assertion can be made about the termination of programs following CBV and CBN evaluation strategies:

If a program terminates under CBV then it will also terminate under CBN… however the opposite is not always true

Let’s see an example of why CBN terminating does not always mean CBV will terminate. Take the example of the square function we defined above, only this time instead of passing 2 + 3 as its second parameter, pass in a function called loop that recursively calls itself ad infinitum:

Example 3:

//Imagine we have the following functions
def square(x, y) = x * x
def loop() = loop //infinite loop...

//and the following function call using CBN evaluation
square(2*2, loop)

//The function will resolve like it did before, and terminate,
//since the loop expression does not need to be evaluated as it is never used!

//Contrast this with the same function call under CBV evaluation
square(2*2, loop)
square(4, loop) //reduction 1
square(4, loop) //reduction 2
square(4, loop) //reduction 3...

Loop always evaluates to itself, which will cause an infinite loop and the program won’t terminate.

Which is preferred?

Both have their place, but Scala defaults expression evaluation to CBV. CBV is, in general, EXPONENTIALLY more efficient than CBN, since it can significantly reduce the number of redundant expression evaluations that occur in your program.

Seriously… take this course by Odersky… its worthwhile