Running out of memory in a simple monad

[David Bergman]

You are right,

After writing that e-mail I looked at a lot of cases in Hugs, and also
encountered this CAF problem. And, as I pointed out elsewhere, the "last
call optimisation" is not very interesting in the lazy evaluation
scenario...

One problem, though, is that I would like not to get rid of the CAF,
since I (presumably wrongly) assume that CAFs are implemented more
efficiently in Hugs than "normal" definitions. Am I right in this
assumption?

Thanks,

David

> -----Original Message-----
> From: haskell-admin@haskell.org 
> [mailto:haskell-admin@haskell.org] On Behalf Of Alastair Reid
> Sent: Monday, December 16, 2002 9:18 AM
> To: David Bergman
> Cc: 'Richard Uhtenwoldt'; haskell@haskell.org
> Subject: Re: Running out of memory in a simple monad
> 
> 
> 
> "David Bergman" <davidb@home.se> writes:
> > Note: In an unoptimized scenario, such as
> > with Hugs, you do indeed run out of memory in your "loop" 
> (after some 
> > 40000 iterations) not having the recursion in the last call. Even 
> > loops not constructing cons cells do, such as
> 
> > 	loop 0 = return () 
> >       loop n = do { print n; loop (n-1) } -- print n >> loop (n-1) 
> >       main = loop 50000
> 
> > (you see Hugs die after some 25000 iterations...)
> 
> I'm afraid your diagnosis is way off base here.
> 
> The problem is nothing to do with a 'last call optimization' 
> or with the do syntactic sugar and can be worked around not 
> by changing how you _write_your code (which would obviously 
> be a large burden) but by how you _call_ your code (a much 
> smaller burden).
> 
> The problem is to do with garbage collection of Constant 
> Applicable Forms (or CAFs).  CAFs are definitions like:
> 
>   nil = []
>   one = 1 :: Int
>   primes = ...
>   main = loop 50000
> 
> GHC and Hugs differ in how they treat CAFs.  Hugs treats CAFs 
> as a special case and never garbage collects a CAF - the only 
> way to discard its value is to unload the module that defines 
> it.  GHC treats CAFs the same as normal definitions and 
> garbage collects them when they can no longer contribute to 
> future execution.
> 
> The difference between these behaviours can be seen when the 
> CAF grows very large as in your example.
> 
> The workaround is simple enough: add a dummy argument to the 
> CAF (so that it is not a CAF any more):
> 
>    main _ = loop 50000
> 
> and then specify the extra argument when invoking it:
> 
>    main ()
> 
> (This is a pretty standard optimisation technique: we're 
> trading time to recompute a result for the space taken to 
> store the result.  Coming from other languages where actions 
> (i.e., monadic computations) are not first class values, this 
> is a bit surprising but, from a Haskell perspective, it is 
> completely uniform.)
> 
> 
> Note that this workaround is necessary with GHC too if you 
> have a large CAF which does not die.  For example, if you 
> wanted to benchmark your code, you might want to run it 10 
> times using:
> 
> > main1 = loop 50000
> > main = sequence_ (replicate 10 main1)
> 
> Now main1 will not be garbage collected until the last time 
> it is executed.  The solution is the same as for Hugs: add a 
> dummy argument.
> 
> --
> Alastair Reid                 alastair@reid-consulting-uk.ltd.uk  
> Reid Consulting (UK) Limited  
> http://www.reid-consulting-uk.ltd.uk/alastair/
> 
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
>