MLton not quite safe-for-space

[Stephen Weeks]

> 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.)

I think you CPS converted incorrectly.  Here is the correct CPS conversion of
the program.

fun f (depth, k) =
   if depth = 0
      then k ()
   else f (depth - 1,
	   fn _ =>
	   let fun spin k = spin k
	   in spin k
	   end)

The point is that you did not CPS convert spin.  The continuation passed to f is 
indeed closed over k.  You performed a useless variable optimization and
eliminated spin's argument.  It is correct, but not required.

> 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 find this example more plausible.  Suppose that CPS conversion in the presence 
of exceptions adds two arguments to every function, one continuation to be
called in the case of normal returns and one continuation to be called in the
case of exceptional returns.  Then, the CPS conversion of g looks like:

fun g (depth, k, k') =
   if depth = 0
      then k ()
   else g (depth - 1,
	   fn _ => k' ???,
	   k')

So, both the normal and exception continuations don't refer to k, and g should
execute in constant space. 

> 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?

You hit the nail right on the head in that the problem is that there is no way
for a frame to refer to just the exception continuation.  I think your solution
isn't too costly.  It would certainly be possible to add an extra bit in the
frame info table for each frame.  The analysis to determine which continuations
never return in the CPS IL is dead simple and linear time.

I would prefer to have a solution that expressed the information in the CPS IL,
but I can't see one right now.

Anyways, it's on the todo list, but very low, unless it's really biting you.

Hmmm, now that I think about it, the information about what frames never return
is known at compile time, so you could emit code just before such frames are
pushed that slides the frame down to just above the toplevel handler.  Then the
gc wouldn't have to get involved at all.  I guess this optimization would
address your first example as well.