Call by Name vs. Call by Value in Scala6 min read

Substitution Model

In Scala, expressions are evaluated based on the substitution model, the idea is that all evaluation does is reduce an expression into a single value like what we would do to simplify an expression in algebra.

What I mean by that is in Scala, the evaluation of an expression is treated as a mathematical expression, for example, we know that in simple algebra, a simple expression such as 2 + 3 * 4 + 5, the first evaluation would be 2 + 12 + 5, and then 14 + 5 and finally, it gives us 19. The same rule applied to expressions in Scala, generally, the process of evaluating an expression including non-primitive expressions in Scala is as follow:

  • Take the leftmost operator, subject to the rules of precedence
  • Evaluate its operands from left to right
  • Then apply the operator to the values of the operands.

A name (a variable) is evaluated by replacing it with its right-hand-side value.

The evaluation process terminates once it hits into a single value, or otherwise, evaluation fails which indicates we have an infinite loop.

However, a note you need to remember is the substitution model only works with expressions that have no side-effect.

What is the side-effect? A function or an expression is said to have a side effect when besides its returning value (main effect), some non-local variables such as a static or global variable are modified at the same time (side effect) by this function or expression.

Here is a simple example of side effect in Java (Scala doesn’t let you do that):

static int x = 5;

public static int increment() {
     return ++x;
}

Let’s move back to the substitution model in Scala, for example, we have a simple expression:

val pi = 3.14159
val radius = 5

val perimeter = (2 * pi) * radius

Here is how this expression would be evaluated:

(2 * pi) is evaluated first, pi is replaced with its RHS value

=> (2 * 3.14159) * radius

=> 6.28318 * radius

radius is replaced with its RHS value

=> 6.28318 * 5

=> 31.4159

The substitution model is formalized in lambda calculus, which gives a foundation for functional programming.

Function Evaluation Strategies

We now know how an expression is evaluated in Scala, but how the substitution model is applied to function application? It turns out that when invoking a function with parameter(s), the substitution model is further divided into two different strategies, which are call-by-value and call-by-name.

def sumOfSquares(a: Int, b: Int) = square(a) + square(b)

def square(num: Int) = num * num

Call by Value

In call-by-value strategy, basically, function arguments will be reduced to a single value before rewriting the function application (i.e executing the function body). For instance, if we call sumOfSquares(10, 5 + 7), the body of this function is only invoked when the argument is reduced to a single value:

sumSquare(10, 5 + 7)
sumSquare(10, 12)
square(10) + square(12)
10 * 10 + square(12)
100 + square(12)
100 + 12 * 12
100 + 144
244

The advantage of call-by-value is that it evaluates every argument only once.

Call by name

Alternatively, another strategy for function application is to directly apply unreduced arguments to the function call, and this evaluation strategy is called “call-by-name“, for instance:

sumOfSquares(10, 5 + 7)
square(10) + square(5 + 7)
10 * 10 + square(5 + 7)
100 + (5+7) * (5+7)
100 + 12 * (5+7)
100 + 12 * 12
100 + 144
244

Call-by-name has an advantage is that a function argument is not evaluated if the corresponding function parameter is not used in the function body.

Call by name, Call by value, and Termination

The number of reduction steps to reach the final value of the call-by-value strategy is terser compared with call-by-name, hence call-by-value is used as a default evaluation strategy in Scala.

As we can see through some of the previous examples, both call-by-name and call-by-value strategies reduce to the same value as long as both evaluations terminate, however, there are some cases the termination is not guaranteed. These things hold:

  • If CBV evaluation of an expression e terminates, then CBN evaluation of this expression e also terminates, too.
  • The reverse direction is not true.

For example, we define a function takeFirst, and a recursive function that calls itself forever:

def takeFirst(x: Int, y: Int) = x

def eternity: Int = eternity

Now, let’s consider if we pass a number and a non-terminating computation as the second argument of the takeFirst function, takeFirst(5, eternity):

  • In case CBV, we need to reduce both of the arguments before rewriting the function, since eternity just reduces to itself every time, we cannot make any progress there and the function evaluation is never terminated.
  • On the other hand, if CBN is utilized, this function call will give us the value of 5 in the first step since it’s what needs to be returned, and the second parameter eternity is never evaluated because we never use it in the function body.

In fact, CBV is exponentially efficient than CBN with respect to the number of steps to reach the final value because it avoids the recomputation of argument expressions in which CBN entails, this is why Scala uses CBV by default.

However, in some situation where the termination of an argument is non-deterministic, call-by-name can be enforced by using the => symbol in front of the parameter type:

def eternity: Int = eternity

// the first argument is enforced call-by-name
def getSecond(x: => Int, y: Int) = y
getSecond(eternity, 5) // gives us 5

// the second argument is enforced call-by-name
def longLasting(x: Int, y: => Int) = y
longLasting(5, eternity) // never stops evaluating because the second parameter appeared in the function body

Here is another example:

def squareFirst(x: Int, y: Int) = x * x

The second parameter doesn’t show up in the function body, so in this case, we can tell Scala to evaluate the second parameter as call-by-name to avoid redundant computation:

def squareFirst(x: Int, y: => Int) = x * x

squareFirst(5, 100) // 25
squareFirst(10, eternity) // 100

Wrapping up

There are 2 evaluation strategies in Scala, namely call-by-value and call-by-name. In CBV strategy, an expression is reduced to a single value before executing the function body whether the function needs it or not, whereas in CBN, unreduced arguments are passed directly to the function call and unused parameter in the function body doesn’t have to be evaluated.

Typically, CBV is the standard evaluation strategy in Scala because it’s radically faster than CBN for the most part. Yet, depends on your need, CBN can be enforced by using => symbol.

Categories

Archives