Re: Why is there a space leak here?

29 May 2001

      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: 
To: 
Cc: 
Sent: Tuesday, May 29, 2001 12:49 AM
Subject: Re: Why is there a space leak here?
...
David Bakin  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