Evaluation strategies in Scala

Evaluation strategies are one of the most important traits of programming languages. Hence, I chose this topic for the current blog post. We are going to have a quick introduction to evaluation strategies and then look at the evaluation strategies supported by Scala.

Programming languages use evaluation strategies to determine when and how the arguments of a function call are evaluated. There are many evaluation strategies, but most of them end up in two categories:

  • Strict evaluation, in which the arguments are evaluated before the function is applied. Examples of programming languages that use strict evaluation strategies are Java, Scheme, JavaScript etc.
  • Non-strict evaluation, which will defer the evaluation of the arguments until they are actually required/used in the function body. Haskell is probably the most popular functional programming language that uses non-strict evaluation.

There are also languages that support both strict and non-strict evaluation strategies and Scala is one of them.

Knowing what evaluation strategy a programming language uses gives a clearer expectation on the program execution outcome.

We are not going name all of the evaluation strategies (which by the way can be found here) but rather focus on the ones supported by Scala. Scala supports two evaluation strategies out-of-the-box: call by value and call by name. Also, we are going to have a look at call by need as it can be achieved/simulated with a small workaround and it will also be the subject of my next blog post.

Call by value

Call by value is a strict evaluation strategy which is the most commonly used by programming languages. In call by value, the expression is evaluated and bound to the corresponding parameter before the function body is evaluated. It is also the default evaluation strategy in Scala.

The example bellow uses the call-by-value strategy:

// FYI you can use Seq.fill, this is just for this blog post purposes
def times[T](t: Int)(elem: T): Seq[T] = {
  println("inside times")
  (1 to t).map(_ => elem)
}

Let's call the method with zero and a non-zero t:

times(0) {
  println("call-by-value")
  1
}

times(2) {
  println("call-by-value")
  "boo"
}
// both print:
// call-by-value
// inside times

As we can see the arguments are evaluated before the function body.

Call by name

Call by name is a non-strict evaluation strategy which will defer the evaluation of the expression until the program needs it. To make a parameter call-by-name just add => before the type, as shown bellow:

def times2[T](t: Int)(elem: => T): Seq[T] = {
  println("inside times")
  (1 to t).map(_ => elem)
}

And again, let's call this method with the same parameters:

times2(0) {
  println("call-by-name")
  1
}
// prints just:
//*inside times*

times2(2) {
  println("call-by-name")
  "boo"
}
// prints:
// inside times
// call-by-name
// call-by-name

The drawback of this evaluation strategy is that the arguments are evaluated on every use in the function body. Multiple occurrences of this argument means multiple evaluations (see the second invocation which prints "call-by-name" twice). In this case it is crucial the expression passed as a by-name argument to have no side effects, otherwise it may lead to unexpected behavior.

var someState = 0

times2(3) {
  someState += 1
  42
}

// someState is 3 now

While most of the languages support a single evaluation strategy, Scala doesn't only support multiple evaluation strategies but also allows to combine them in the same function.

Call by need & lazy values

Call by need is the memoised version of call by name which makes the function argument to be evaluated only once (on the first use).

Memoisation is an optimisation technique which consists of caching the results of function calls and return the cached result when the function is called with the same input again.

Does Scala support call by need evaluation? Well ... sort of ... Scala has lazy (by need) values but no lazy arguments (see the workaround bellow).

In Scala you can define lazy values by using the lazy keyword:

lazy val foo = // ... could be some very costly computation

foo will be evaluated at most once: only once if the value is used somewhere in the code (regardless how many times) or not at all if the value is not involved in the computation.

Note: Under the hood, lazy val uses locks which means some overhead is added. Also, under certain circumstances it can lead to deadlocks. Nevertheless, for simple use cases it should work fine with a slight performance downgrade.

With a small workaround we can emulate the call-by-need arguments. Both use lazy values:

def foo(cond: Boolean)(bar: => String) = {
    lazy val lazyBar = bar
    if (cond) lazyBar + lazyBar
    else ""
}

foo(true){ // some computation ... }

or:

def foo(cond: Boolean)(bar: => String) = {
  if (cond) bar + bar
  else ""
}

lazy val bar = { // ... }

foo(true)(bar)

Even though this seems to be working, it requires taking into account too many things which makes it not so easy to use.

In the next post I'm going to present a macro annotation that takes away some of the boilerplate, so stay tuned.

Happy Hacking!