Running out of memory in a simple monad

[David Bergman]

Richard,

I assumed that the compiler had, through strictness analysis, used a
call stack in the compiled code, instead of the usual call frames in the
heap (equivalent to "hey, I thought this was the Standard ML mail
group?") ;-)

Actually, you are right in that the "last call optimization" is not
vital in most call-by-need scenarios, since both (the implicit) call
stack and data structures are often consumed as generated, and the GC
can reclaim the thunks. 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...)

Sorry about the over-simplification, but I wanted people to not forget
that the "do" is just syntactic sugar...

Thanks,

David

-----Original Message-----
From: 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