Why is there a space leak here?
Mark Tullsen
tullsen@cs.yale.edu
Tue, 05 Jun 2001 18:54:31 -0400
Tom Moertel wrote:
>
> Mark Tullsen wrote:
> >
> > You have to realize that Alastair Reid is one of the truly
> > great Haskell programmers on planet earth. I'm serious.
> > So, when he says "incredibly subtle space leak" I wouldn't
> > expect the solution to be simple.
>
> Whoops. Now don't I feel foolish.
>
> > As far as I can tell, your argument would also apply to foo2,
> > which doesn't have a space leak.
>
> Hmmm... Let's see.
>
> foo2 m
> = take m v
> where
> v = 1 : flatten (map single v)
> single x = [x]
>
> v = 1 : flatten (map single v)
> = 1 : flatten (map single (1 : flatten (map single v)))
> = 1 : flatten (single 1 : map single (flatten (map single v)))
> = 1 : flatten ([1] : map single (flatten (map single v)))
> = 1 : 1 : flatten (map single (flatten (map single v)))
> = Aaaarrggggh! You're right.
>
> Now don't I feel double foolish. :P
>
> Okay, then, what is the *right* way to reason about these things?
>
> Cheers,
> Tom
Tom,
I don't know if this approach is the *right* way but it's one
way. This approach is very brute force, and I'm sure there are experts
out there who can think and reason at a much higher level than
this. But the brute force approach is this:
Start evaluating your program symbolically
You can do this at the source level using a CBN (call-by-need)
calculus.
If the program (the program in CBN includes the "heap") starts
growing in size faster than expected then you have a space leak.
Simple, but a bit tedious. It would be great if we had a tool that
could output such a trace.
- Mark