[MLton] callcc and space use

[Matthew Fluet]

On Wed, 6 Feb 2008, Daniel Spoonhower wrote:
> After some investigation, I think I have an answer to my problem.  In the 
> end, it seems the problem had nothing to do with callcc, but with part of the 
> analysis used in the reference flattening optimization 
> (http://mlton.org/RefFlatten).
>
> As the documentation says, to be safe for space, this optimization must 
> ensure that it does not extend the lifetime of any objects of unbounded size. 
> I don't claim to totally understand this code, but I believe that the 
> analysis isn't sufficiently conservative.  First, it doesn't seem to consider 
> vectors to be objects of unbounded size.  Second, though individual instances 
> of a datatype may have bounded size, an instance of a *recursive* datatype 
> may refer to an unbounded amount of heap space. For example, flattening a 
> reference into a tuple that contains a list may extend the lifetime of the 
> entire list.
>
> I attached a patch that fixes the leaks that I've observed.  Can someone take 
> a look and tell me if I'm missing something?

I agree that the analysis does not seem to yield the result that it claims 
to -- namely, to identify types that may correspond to values (that would 
keep live data) of unbounded size.

It is a fairly simple exercise to modify the example program to use a 
vector rather than a list, and the modified program also shows a space 
leak.

I've checked in a version of your patch, extended to compute a dependency 
graph amongst datatypes and force (mutually) recursive datatypes to be 
considered of unbounded size.

In addition, I dropped the dependency of the size of a type on the size of 
(the pointed-to type of) a weak type component.  Since a weak pointer 
doesn't keep the pointed-to object alive, a weak type need never be 
considered of unbounded size.  Similarly recursive datatypes whose 
recursion only go through weak pointers don't need to be considered of 
unbounded size.

Thanks for investigating and the patch!