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?