[Haskell-cafe] Laziness leaks

[Albert Y. C. Lai]

Ronald Guida wrote:
> I was looking at the real time queues in [1] and I wanted to see what
> would happen if I tried to write one in Haskell.  The easy part was
> translating the real time queue from [1], p43 into Haskell.
> 
> The hard part is testing to see if the rotations really happen what
> they should.  Basically, I decided to use Debug.Trace.trace to see
> when rotations were actually occurring.
> 
> I pushed the numbers 1 to 10 into the queue, and then I popped the
> queue ten times.  What I found is that none of the rotations would
> actually take place until the first time I actually tried to /display
> the value/ of a popped element.  What I realized is that my test
> driver is lazy.  I figured out that I could put a bunch of 'seq'
> functions in the test driver to get the rotations to happen.
> 
> My demonstration code is in:
> http://hpaste.org/8080
> 
> This leads to two questions:
> 
> 1. If I find a laziness leak, is 'seq' the appropriate way to plug it?
> 
> 2. Is there any way to systematically search for or detect laziness
>    leaks?
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 

I want to point out several non-causes of laziness. For a no-magic, 
no-surprise understanding, it is important to know both what causes 
laziness and what does not.

A. The lazy list at rtqRear, which is originally a strict list. It is an 
invariant that every thunk you put there is [] or x:y. (As a result, it 
is unnecessary to make RTQueue a strict record, since you want two of 
the fields to be lazy, and the remaining field rtqRear is de facto strict.)

B. rtqueue's thunked call to rotate, i.e.,

    rtqueue f r []    = let f' = rotate f r [] in RTQueue f' [] f'

Originally f' is forced before the record is returned (SML convention). 
In Haskell the rotate call is thunked as f' and the record is returned. 
But there will not be an accumulation of such rotate thunks. For example 
if you snoc twice in succession and the first instance builds a rotate 
thunk:

    snoc p (snoc q (RTQueue f r []))
-> snoc p (rtqueue f (q:r) [])
-> snoc p (RTQueue f' [] f')  where f' = thunk
-> rtqueue f' p:[] f'  where f' = thunk
-> f' is now forced by rtqueue's pattern matching on the 3rd param

So if one snoc builds a rotate thunk, the next snoc kills it. And 
similarly any interleaving of queue operations. (head and tail add their 
extra pattern matching.) Thus it can be proved that Haskell lags behind 
the original by just one step in this regard. This is ok unless you're 
done with reducing asymptotic cost and start looking at constant factor 
cost.

A true cause of laziness is in accumulating a chain of tail's and snocs 
without intermediate forcing, as observed.