On 10 Mar 2002, Jyrinx wrote:
In the case expression at the end of countAll, each of the values looks to me like a recursive tail call - I should think (hope?) that it would be optimized by GHC into a goto statement (a la Scheme). Instead, my program eats up memory (I've got 256 MB) until the RTS whines about a stack overflow.
It is tail recusive. unfortunately, that's not the problem. apparently ghc is not smart enough to realize that countAll' should really be strict in basically all arguments. (hell, I'm not quite sure I can claim to be smart enough to say that!) One way you could fix it up would be to do as Hal did and sprinkle seq and/or $! throughout your code. That would have been my solution as well, but I then realized this happens just too often to have been ignored by the haskell literati. I decided to muck around in the haskell manual and I think I may have found another way. Never fear, -fall-strict is here! Anyway compiling with that ghc option seams to make the problem go away. I just ran your code compiled with it over a 47M file and the heap size hits a max of 16 and stays constant throughout execution. I wish I knew more about what -fall-strict really means. The ghc 5.00 manual hardly explains it. It doesn't have the semantics I would have thought it should have. for instance: main = print foo where foo = let a = error "do I happen?" b = 3 in "foo" ++ show b I would have thought that the execution of that code compiled with the all-strict flag would have raised the error. a strict language would do that, right? Perhaps it is something to do purely with function application. I dont know. Anyway, I guess a fix would be to put in a pragma into your code to quote Malcolm Wallace <Malcolm.Wallace@cs.york.ac.uk>
ghc and nhc98 already support this. ghc's mechanism is {-# OPTIONS -fglasgow-exts ... etc #-} at the top of the file - but there are quite a few restrictions on what flags are accepted in that pragma. nhc98's mechanism is {-# OPTIONS_COMPILE -nkpat ... etc #-} anywhere in the file, which has no restrictions on the options it accepts - you can use anything that can appear on the commandline.
o just maybe you could exchange -fall-strict for -fglasgow-exts and pray to the haskell gods that it happens to be an acceptable option? Jay Cox