Call-by-name in Scala vs lazy evaluation in Haskell?

Question

Haskell's lazy evaluation will never take more evaluation steps than the eager evaluation.

On the other hand, Scala's call-by-name evaluation may require more evaluation steps than call-by-value (if the short-circuit benefits are more than offset by the cost of repeated calculations).

I thought call-by-name is roughly equivalent to lazy evaluation. Why then such a difference in the time guarantee?

I am guessing that maybe Haskell language specifies that memoization must be used during evaluation; but in that case, why doesn't Scala do the same?

Answer 1

There is some breadth in the names given to the evaluation strategies, but they come down to roughly this:

• call by name an argument is pretty much just substituted into the function body in whatever (unevaluated) form it was in when the function was called. That means it may need to be evaluated multiple times in the body.

  In Scala, you write this as:

  scala> def f(x:=> Int): Int = x + x
  scala> f({ println("evaluated"); 1 })
  evaluated
  evaluated
  2
  

  In Haskell you have no built in way of doing this, but you could always represent call-by-name values as functions of type () -> a. This is a bit more blurry though, because of referential transparency - you won't be able to test this out the way you would with Scala (and the compiler might optimize away the "by name" part of your call).

• call by need (lazy... sort of) an argument is not evaluated when the function is called, but on the first time is is needed. At that moment, it is also cached. Afterwards, whenever the argument is needed again, the cached value is looked up.

  In Scala, you don't declare your function arguments to be lazy, you make a declaration lazy:

  scala> lazy x: Int = { println("evaluated"); 1 }
  scala> x + x
  evaluated
  2
  

  In Haskell this is how all functions work by default.

• call by value (eager, what almost every language does) arguments are evaluated when the function is called, even if the function doesn't end up using those arguments.

  In Scala this is how functions work by default.

  scala> def f(x: Int): Int = x + x
  scala> f({ println("evaluated"); 1 })
  evaluated
  2
  

  In Haskell, you can force this behaviour with bang patterns on function arguments:

  ghci> :{
  ghci> f :: Int -> Int
  ghci> f !x = x
  ghci> :}
  

So if call by need (lazy) does as much or less evaluation (as either of the other strategies), why use anything else?

Lazy evaluation is tough to reason about unless you have referential transparency, because then you need to figure out exactly when your lazy value was evaluated. Since Scala is built to interoperate with Java, it needs to support imperative, side-effectful programming. As a consequence, it is in many cases not a good idea to use lazy in Scala.

Furthermore, lazy has a performance overhead: you need to have an extra indirection to check if the value has been already evaluated or not. In Scala, that translates to a bunch more objects, which puts an even greater strain on the garbage collector.

Finally, there are cases where having lazy evaluation leaves "space" leaks. For example, in Haskell, folding a large list of numbers from the right by adding them together is a bad idea because Haskell will build up this gigantic series of lazy calls to (+) before evaluating them (when in reality you just need it to have an accumulator. A famous example of space issues you get even in simple contexts is foldr vs foldl vs foldl'.