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'.

Answer 2

I don't know why Scala doesn't have^{Turns out it does} “proper” lazy evaluation – likely it's just not so simple to implement, especially when you want the language to interact smoothly with the JVM.

Call-by-name is (as you've observed) not equivalent to lazy evaluation, but to replacing an argument of type a with an argument of type () -> a. Such a function contains the same amount of information as a plain a value (the types are isomorphic), but to actually get at that value you always need to apply the function to the () dummy argument. When you evaluate the function twice, you'll get twice the same result, but it must each time be calculated anew (since automatically memoising functions is not feasible).

Lazy evaluation is equivalent to replacing an argument of type a with an argument of a type that behaves like the following OO class:

class Lazy<A> {
  function<A()> computer;
  option<A> containedValue;
 public:
  Lazy(function<A()> computer):
       computer = computer
     , containerValue = Nothing
     {}
  A operator()() {
    if isNothing(containedValue) {
      containedValue = Just(computer());
    }
    return fromJust(containedValue);
  }
}

This is essentially just a memoisation-wrapper around the specific call-by-name–function type. What's not so nice is that this wrapper relies in a fundamental way on side-effects: when the lazy value is first evaluated, you must mutate the containedValue to represent the fact that the value is now known. Haskell has this mechanism hard-baked at the heart of its runtime, well-tested for thread-safety etc.. But in a language that tries to use an imperative VM as openly as possible, it would probably cause massive headaches if these spurious mutations were interleaved with the explicit side-effects. Especially, because the really interesting applications of lazyness don't just have a single function argument lazy (that wouldn't buy you much) but scatter lazy values all through the spine of a deep data structure. In the end, it's not just one delay-function that you evaluate later than entering the lazy function, it's a whole torrent of nested calls to such functions (indeed, possibly infinitely many!) as the lazy data structure is consumed.

So, Scala avoids the dangers of this by not making anything lazy by default, though as Alec says it does offer a lazy keyword that basically adds a memoised-function wrapper like the above to a value.

Answer 3

This may be useful and doesn't really fit in a comment.

You can write a function in Scala which behaves like Haskell's call-by-need (for arguments) by making the arguments call-by-name and evaluating them lazily at the start of the function:

def foo(x: => Int) = {
  lazy val _x = x
  // make sure you only use _x below, not x
}