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