Running out of memory in a simple monad

[David Bergman]

So,

Should I imply that the IO monad is "pretty damned useless" in Hugs
then, since the loop does not run in constant space there?

There are a lot of algorithms that cannot be run in constant space (due
to either recursion depth or structure generation), even in the most
optimized setting. This does not make them useless.

/David

-----Original Message-----
From: haskell-admin@haskell.org [mailto:haskell-admin@haskell.org] On
Behalf Of Richard Uhtenwoldt
Sent: Saturday, November 30, 2002 11:53 PM
To: David Bergman
Cc: haskell@haskell.org
Subject: RE: Running out of memory in a simple monad

David Bergman writes:

>It is easy to get the feeling that the recursive call in
>
>	recurse = do
>	   		f x
>         		recurse
>
>is the last one, but this is just an illusion of the iterative layout
of
>"do". Sometimes the monads lure us into old iterative thought
>patterns...
>
>Taking away the syntactic sugar, we end up with
>
>	recurse = f x >> recurse
>
>This reveals the fact that there can be no last call optimization,
>because the last call is ">>".

What do you mean by this?  Do you mean that that an implementation
cannot execute arbitrarily many iterations/recursions of that last
loop/definition in constant space?

If that's what you mean, you are wrong.  GHC does that.  The IO monad
would be pretty damned useless for actual work if implementations did
not do that!

Even if we replace the (>>) with a (:) as the "main operator"/"last
call" of the loop, the result can execute in constant space because
of optimizations.

E.g., the program

  loop n=n:loop (n+1)
  main = print (loop 0)

executes in constant space when compile by GHC 5.02.


Details: 

Specifically, I let it run till it printed 2,500,000 at which time top
reported the "RSS" to be 1,500 with no increase having occurred in a
long time.  top's manpage says that "RSS" is "the total amount of
physical memory used by the task, in kilobytes".

The statement about (>>) is true when the (>>) is in the IO monad.  I
did not check to see what happens in a "user-defined" monad.
_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell