Does "Call by name" slow down Haskell?

Question

I assume it doesn't.

My reason is that Haskell is pure functional programming (without I/O Monad), they could have made every "call by name" use the same evaluated value if the "name"s are the same.

I don't know anything about the implementation details but I'm really interested.
Detailed explanations will be much appreciated :)

BTW, I tried google, it was quite hard to get anything useful.

Answer 1

First of all, Haskell is a specification, not an implementation; the report does not actually require use of call-by-name evaluation, or lazy evaluation for that matter. Haskell implementations are only required to be non-strict, which does rule out call-by-value and similar strategies.

So, strictly (ha, ha) speaking, evaluation strategies can't slow down Haskell. I'm not sure what can slow down Haskell, though clearly something has or else it wouldn't have taken 12 years to get the next version of the Report out after Haskell 98. My guess is that it involves committees somehow.

---

Anyway, "lazy evaluation" refers to a "call by need" strategy, which is the most common implementation choice for Haskell. This differs from call-by-name in that if a subexpression is used in multiple places, it will be evaluated at most once.

The details of what qualifies as a subexpression that will be shared is a bit subtle and probably somewhat implementation-dependent, but to use an example from GHC Haskell: Consider the function cycle, which repeats an input list infinitely. A naive implementation might be:

cycle xs = xs ++ cycle xs

This ends up being inefficient because there is no single cycle xs expression that can be shared, so the resulting list has to be constructed continually as it's traversed, allocating more memory and doing more computation each time.

In contrast, the actual implementation looks like this:

cycle xs = xs' where xs' = xs ++ xs'

Here the name xs' is defined recursively as itself appended to the end of the input list. This time xs' is shared, and evaluated only once; the resulting infinite list is actually a finite, circular linked list in memory, and once the entire loop has been evaluated no further work is needed.

---

In general, GHC will not memoize functions for you: given f and x, each use of f x will be re-evaluated unless you give the result a name and use that. The resulting value will be the same in either case, but the performance can differ significantly. This is mostly a matter of avoiding pessimizations--it would be easy for GHC to memoize things for you, but in many cases this would cost large amounts of memory to gain tiny or nonexistent amounts of speed.

The flip side is that shared values are retained; if you have a data structure that's very expensive to compute, naming the result of constructing it and passing that to functions using it ensures that no work is duplicated--even if it's used simultaneously by different threads.

You can also pessimize things yourself this way--if a data structure is cheap to compute and uses lots of memory, you should probably avoid sharing references to the full structure, as that will keep the whole thing alive in memory as long as anything could possibly use it later.

Answer 2

Yes, it does, somewhat. The problem is that Haskell can't, in general, calculate the value too early (e.g. if it would lead to an exception), so it sometimes needs to keep a thunk (code for calculating the value) instead of the value itself, which uses more memory and slows things down. The compiler tries to detect cases where this can be avoided, but it's impossible to detect all of them.