[Haskell-beginners] Bug or Intended behavior? ( Exception: stack overflow )

[Daniel Fischer]

On Monday 24 January 2011 11:59:15, Seung Soo, Ha wrote:
> my setup: phenom II quadcore, 4GB mem Ubuntu Maverick
>
> While implementing my own reverse in  "99 haskell questions",
>
> I made the following mistake:
> (Caution: stack over flow causing code below)
>
>
> reverse'::[a] -> [a]
> reverse' [] = []
> reverse' [x] = [x]
> reverse' xs = last xs : init (reverse' xs)
>
> The last line is the wrong part. It should be
> reverse' xs = last xs : reverse' (init xs)
>
> anyway, the original code seems to cause an infinite recursion
>  by repeating the last part forever.

Yes. In

loop :: [Int]
loop = 1 : init loop

the evaluation goes

loop = 1 : init loop
-- now it must be checked whether init loop
-- a) gives an error because loop is empty (which it isn't, so no error)
-- b) is empty because loop is one element long
-- c) is nonempty because loop contains at least two elements

~> 1 : init (1 : init loop)
-- same problem in the parentheses

~> 1 : init (1 : init (1 : init loop))
-- ad infinitum

To see whether loop has a second element, we first must see whether loop 
has a second element.

the structure is the same as for your last line of reverse', only there you 
have function calls instead of named values (1, loop).


>  When I try this out on ghci:
>
>
> *Main> reverse' [1,2,3,4,5]
> [5*** Exception: stack overflow
> *Main>
>
> The problem is, unless I manually exit ghci, the "stack" does not seem
> to be freed (garbage collected?) and memory remains fully occupied by
> ghci.

GHC used to not return any memory it has allocated to the OS (in case it is 
needed again later), thus ghci wouldn't return any memory either.
I think¹ that as of GHC-7, GHC now returns memory to the OS after memory 
usage has dropped (not immediately, of course, it waits until memory usage 
has been lower for a bit).

¹ I may be wrong, it may have already been in some 6.12.
With ghci-7.0.1, after ^C-ing the computation at 24% memory, according to 
top, it dropped to 4%, didn't wait to check whether more memory would be 
released later.

>
> I tried waiting a bit, but it stayed the same.
>
> Is this expected behavior?

I think so. At least for GHC < 7.

> Shouldn't the GC kick in?
> Is this orthogonal of the GC?

The GC would free the memory but keep it for the process to reuse.
If you can run space consuming things afterwards without ghci's memory 
usage going up, that's what's happening.

> I think this would help me understand haskell and GHC much better.
>