Why is there a space leak here?
Tue, 29 May 2001 01:31:56 -0700
That's a very nice visualization - exactly the kind of thing I was hoping
for. I grabbed your papers and will look over them for more information,
thanks very much for taking the trouble! The animations you sent me - and
the ones on your page - are really nice; it would be nice to have a system
like HOPS available with GHC/GHCi (I understand it is more than the
visualization system, but that's a really useful part of it).
(I also found out that Hood didn't help for this particular purpose - though
now that I see how easy it is to use I'll be using it all the time. But it
is carefully designed to show you ("observe") exactly what has been
evaluated at a given point in the program. Thus you can't use it (as far as
I can tell) to show the data structures that are accumulating that haven't
been processed yet - which is what you need to know to find a space
----- Original Message -----
Sent: Tuesday, May 29, 2001 12:49 AM
Subject: Re: Why is there a space leak here?
> David Bakin <email@example.com> writes:
> > Which of the various tools built-in or added to Hugs, GHC, NHC, etc.
> > help me visualize what's actually going on here? I think Hood would
> > a newer Hugs, of course, I'm going to try it). What else?
> I just used my old ghc-4.06 add-in ``middle-end'' ``MHA'' to generate
> a HOPS module from David's message (slightly massaged, appended below),
> and then used HOPS to generate two animations:
> Hold down the space key in ghostview to get the animation effect!
> The left ``fan'', present in both examples, is the result list,
> and only takes up space in reality as long as it is used.
> The right ``fan'', visible only in foo1, contains the cycle
> of the definition of v, and represents the space leak.
> The take copies cons node away from the cycle.
> The HOPS input was generated automatically by an unreleased
> GHC ``middle end'' that is still stuck at ghc-4.06.
> The homepage of my term graph programming system HOPS is:
> > module Bakin where
> -- This has a space leak, e.g., when reducing (length (foo1 1000000))
> > foo1 :: Int -> [Int]
> > foo1 m
> > = take m v
> > where
> > v = 1 : flatten (map triple v)
> > triple x = [x,x,x]
> -- This has no space leak, e.g., when reducing (length (foo2 1000000))
> > foo2 :: Int -> [Int]
> > foo2 m
> > = take m v
> > where
> > v = 1 : flatten (map single v)
> > single x = [x]
> -- flatten a list-of-lists
> > flatten :: [[a]] -> [a]
> > flatten  = 
> > flatten (:xxs) = flatten xxs
> > flatten ((x':xs'):xxs) = x' : flatten' xs' xxs
> > flatten'  xxs = flatten xxs
> > flatten' (x':xs') xxs = x': flatten' xs' xxs