Why is there a space leak here?

[David Bakin]

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
problem.)

-- Dave


----- Original Message -----
From: <kahl@heraklit.informatik.unibw-muenchen.de>
To: <davidbak@cablespeed.com>
Cc: <haskell-cafe@haskell.org>
Sent: Tuesday, May 29, 2001 12:49 AM
Subject: Re: Why is there a space leak here?


>
> David Bakin <davidbak@cablespeed.com> writes:
>
>  > Which of the various tools built-in or added to Hugs, GHC, NHC, etc.
would
>  > help me visualize what's actually going on here?  I think Hood would
(using
>  > 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:
>
> http://ist.unibw-muenchen.de/kahl/MHA/Bakin_foo1_20.ps.gz
> http://ist.unibw-muenchen.de/kahl/MHA/Bakin_foo2_20.ps.gz
>
> 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:
>
> http://ist.unibw-muenchen.de/kahl/HOPS/
>
>
> Wolfram
>
>
>
>
> > 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
>