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: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED]] On Behalf Of Alastair Reid > Sent: Monday, December 16, 2002 9:18 AM > To: David Bergman > Cc: 'Richard Uhtenwoldt'; [EMAIL PROTECTED] > Subject: Re: Running out of memory in a simple monad > > > > "David Bergman" <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED] > Reid Consulting (UK) Limited > http://www.reid-consulting-uk.ltd.uk/alastair/ > > _______________________________________________ > Haskell mailing list > [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell > _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell