Running out of memory in a simple monad

[Alastair Reid]

"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/