Running out of memory in a simple program
{- Hi! I have a problem with monads. When a monadic function calls itself many times (see below) Hugs and GHCi runs out of memory/stack, and I can't see why. This is my program (well, I've kind of sipmlified it a lot :): -} newtype M a = M (Int -> (a,Int)) instance Monad M where return x = M $ \i -> (x,i) M f >>= k = M $ \i -> let (x,i2) = f i M f2 = k x in f2 i2 inc 0 = return () inc n = do inc'; inc (n-1) where inc' = M $ \i -> ((), i+1) runM :: M () -> IO () runM (M m) = print (m 0) -- in print i run n = runM (inc n) -- crashes for large n !! {- Shouldn't `run n' work for any n? But if I use n over 20 000 (or something) Hugs says "error: couldn't retreive enough memory when garabae-collecting" (or something), and other times Windows 2000 says "unknown software exception 0xc000000fd at 0x00040ec01". I tested to add "continuation passing style" (I don't really know what I should do) but that didn't work either. Does anyone have an idea of what the error is and what I should do / not do? Best regards, Magnus Lindberg -}
Magnus Lindberg <f98mali@dd.chalmers.se> writes:
I have a problem with monads. When a monadic function calls itself many times (see below) Hugs and GHCi runs out of memory/stack,
A little heap profiling shows that the memory is being filled with unevaluated function applications. The effect of your 'inc' computation is to build a huge lambda expression whose size is directly proportional to the integer argument. Each recursive call of 'inc' simply builds an unevaluated application of the previous lambda by wrapping another lambda around the outside. You probably hoped that lazy evaluation would build only enough of the lambda expression as was immediately needed, delaying the construction of the "tail" of the function (i.e. the right-hand-side of the >>=) until later. Unfortunately, graph reduction doesn't work like that. The function in an application must be fully evaluated before it is entered, hence the build-up of thunks. Regards, Malcolm
newtype M a = M (Int -> (a,Int))
instance Monad M where return x = M $ \i -> (x,i) M f >>= k = M $ \i -> let (x,i2) = f i M f2 = k x in f2 i2
inc 0 = return () inc n = do inc'; inc (n-1) where inc' = M $ \i -> ((), i+1)
runM :: M () -> IO () runM (M m) = print (m 0) -- in print i
run n = runM (inc n) -- crashes for large n !!
Hi again! Thanks for your help, Malcolm. I added `seq' at two places to prevent laziness and now I never run out of memory. instance Monad M where return x = M $ \i -> (x,i) M f >>= k = M $ \i -> let (x,i2) = i `seq' f i M f2 = x `seq' k x in f2 i2 (however, I think that just one of the two `seq' should do but if I remove any single `seq' then I still run out of memory :( ) Kind regards Magnus
Hmmm, I generally try to avoid using seq. It's a hack and often one can refrain from using it. Here's how I would solve the problem: First of all your monad constains an int which is passed around. Typically we want this to be computed strictly. The way to do this is to add a strictness annotation. A naive try would be this: newtype M a = M (Int -> (a,!Int)) Unfortunately we cannot have stricness annotation in this way. So to achieve this effect we make a new data type for pairs with a strict int: data PairInt a = P a !Int Secondly, your bind is lazy. This can be usedful but usually one wants it to be strict because then we get tail-recursion. The lack of tail-recursion is the second problem in this example. Strictness is achieved be converting let to case like this: M f >>= k = M $ \i -> case f i of P x i2 -> case k x of M f2 -> f2 i2 This version doesn't have any problems with spaceleaks. It can now swallow pretty large numbers, I've tried with 1000000. I hope this sheds some light on the problem. /Josef On Fri, 15 Nov 2002, Magnus Lindberg wrote:
Hi again! Thanks for your help, Malcolm. I added `seq' at two places to prevent laziness and now I never run out of memory.
instance Monad M where return x = M $ \i -> (x,i) M f >>= k = M $ \i -> let (x,i2) = i `seq' f i M f2 = x `seq' k x in f2 i2
(however, I think that just one of the two `seq' should do but if I remove any single `seq' then I still run out of memory :( )
Kind regards Magnus _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
participants (3)
-
Josef Svenningsson -
Magnus Lindberg -
Malcolm Wallace