MLton not quite safe-for-space
Henry Cejtin
henry@sourcelight.com
Wed, 15 Nov 2000 13:47:36 -0600
Currently MLton is not quite safe-for-space. The problem case is a non-tail
function call where the continuation `obviously' never returns. I.e.,
fun f depth =
if depth = 0
then ()
else (f (depth - 1);
let fun spin () = spin ()
in spin ()
end)
The point is that in a compile using full CPS, I would claim that the
continuation passed to f in the recursive calls would NOT include the
continuation passed in to the outer f. I.e., the CPS version of f would be
fun f (depth, k) =
if depth = 0
then k ()
else let fun k' _ =
let fun spin () = spin ()
in spin ()
end
in f (depth - 1, k')
end
Note that k' is NOT closed over k. (This is NOT an optimization. It is the
fact that the function spin never returns and hence is NOT closed over its
continuation.)
Thus a safe-for-space implementation must execute f in constant space, but
MLton requires space proportional to argument to f. Fixing this (if it is
worth fixing) is slightly non-trivial because of exceptions. On the other
hand, exceptions also are an argument that it IS worth fixing because it
isn't only non-termination that can cause you to not refer to your
continuation. I.e., consider
fun g depth =
if depth = 0
then ()
else (g (depth - 1);
raise ???)
Again, the continuation to the recursive call to g is NOT closed over the
continuation passed in to the outer g.
I think a not too bad fix for this would be to simply mark a frame (in the
live-variables thing) as indicating that it will never return. Then the GC
would realize that this means that all frames below it up to the next
exception handler are garbage. The advantage here is that it has no effect
on any thing except the GC.
Is this too horrible to contemplate?