[mercury-users] Quick Recursion Question

[Jeff Schultz]

On Fri, Apr 20, 2012 at 04:42:21PM -0500, Charles Shuller wrote:
> main_loop(Data, ListenFd, !IO) :-
>     await_conn(ListenFd, ConnFd, !IO),
>     handle_conn(Data, ConnFd, !IO),
>     main_loop(Data, ListenFd, !IO).
>
> And the first thing I think of is that the stack will be consumed without 
> bounds as every recursion into main_loop consumes more memory.
>
> Then I thought that perhaps Mercury predicates didn't work quite the same 
> way as a function in C.

Yes.  C is broken ;-)  (It doesn't have to be, but implementations are
permitted to have this bug, and most do.)


> So will the above simply consume ever more ram as every request calls 
> main_loop again?

Execution frames (in languages that have them) hold data that will be
used in the future.  Like anything else that is kept around to be used
in the future, it's good to get rid of it when it will no longer be
used.

If the last thing a function f does is call another g, returning as
its result whatever g returns, and there is no memory in f's execution
frame that is needed during the execution of g, then f's frame is
dead.  Conceptually, if the frames are on a stack, f's can be popped
before the call to g.  In practice, this can be messy for other
reasons quite unrelated to correctness.

In your example, the Mercury compiler does not allocate anything in
the frame of main_loop that is still in use at the instant of the
recursive call, so the frame is popped.  (It's probably actually
explicitly reused, but that's an implementation detail.)


As you observe, not doing this when it is possible can lead to
incorrect behaviour, with correct programs failing due to resource
exhaustion.


    Jeff Schultz
--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------