[MLton] callcc and space use

[Matthew Fluet]

On Tue, 22 Jan 2008, Daniel Spoonhower wrote:
> My concern is that variables which are allocated to the stack but *not* live 
> at the point at which callcc is invoked are nonetheless captured by the 
> continuation.  I believe this leads to a space leak in some cases. Does this 
> sound plausible?

Plausible.

> For example, consider:
>
>   fun f x =
>      let val y = ... x ... in
>        (* no more occurrences of x *)
>        callcc (fn k => (enq (fn () => ... k ...);
>                         raise Continue))
>      end
>
> Assuming that "x" is allocated on the stack, there will be a reference to it 
> when callcc copies the current thread.  Of course the reference on the 
> original thread will go away when the exception is raised, but the one in the 
> copy seems to persist.

If "x" isn't live at the callcc point, then it shouldn't be traced from 
the stack frame.  If you have SML code that demonstrates the issue, we can 
look at the IL code.

On the other hand, if you have some other function g:

   fun g y = let
                val () = f y
                val () = f y
             in
                ()
             end

When you capture the continuation in the first invocation of f, f's x 
won't be live, but g's y will be live.  Now, the callcc will throw an 
exception that leaves g (and makes g's y dead), but in the copied thread, 
g's stack frame will keep y alive.  Indeed, in the copied thread, throwing 
to the captured continuation will return to g, where y needs to have 
been kept alive.  But, in any case, even if f were written like:

   fun f x =
      let val y = ... x ... in
        (* no more occurrences of x *)
        callcc (fn k => (enq (fn () => ... k ...);
                         raise Continue))
        ; raise Foo
      end

and the captured continuation will necessarily throw an exception that 
leaves g (and makes g's y dead), we can't propagate that kind of 
liveness information down the stack.