[Haskell-cafe] Re: Laziness leaks
apfelmus at quantentunnel.de
Wed Jun 4 05:42:40 EDT 2008
Ronald Guida wrote:
> So I just thought of something. If laziness leads to laziness leaks,
> then is there such a thing as a strictness leak? I realized that the
> answer is yes.
> A lazy leak is a situation where I'm wasting resources to delay a
> sequence of calculations instead of just doing them now. But in a
> strict language, I might waste resources to compute things that I'll
> never need. I would call that a strictness leak.
> Now I could ask the dual question, "How do I detect strictness leaks,"
> and I would probably get the same answers: profiling, looking at
> object code, and being explicit about the evaluation strategy.
> Both types of leaks share a lot in common. In both cases, I'm wasting
> resources. If I have a real-time system, then either type of leak can
> cause me to a miss a deadline.
I haven't heard the terms "laziness leak" and "strictness leak" before,
imho they sound a bit spooky because it's not clear to me what the
situation without leak would be. (Time vs Space? Is an O(n) algorithm a
strictness leak compared to an O(log n) algorithm?)
Note that lazy evaluation never wastes time; evaluating a term with lazy
evaluation will always take less reduction steps than doing so eagerly
or partly eagerly. But it can waste space (-> "space leak"), for
instance by accumulating a big expression like
(..) -> ((..)+1) -> (((..) + 1) + 1) -> etc.
instead of evaluating x+1 immediately
5 -> 6 -> 7 -> etc.
However, this would be wasted time in case the whole expression will not
be evaluated but just thrown away. So, it's a trade-off.
The effect you have in mind only appears in real-time systems, where
lazy evaluation procrastinates everything by default. So, trying to
implement a real-time system in a lazy language is more or less a
paradox :) as Okasaki already points out in his book.
Eager evaluation may "waste" both time and space compared to alternative
course of reduction.
PS: The reduction strategies we compare to don't evaluate under lambdas.
More information about the Haskell-Cafe