[MLton-user] Sockets+Monads in SML?

[Matthew Fluet]

On Fri, 15 Feb 2008, Vesa Karvonen wrote:
>>  Also, I am concerned by MLton's closure conversion.  With this style of
>>  programming, there are a *lot* of bound variables which pile up towards
>>  the end of the event chain.  As I understand it, the closure of MLton
>>  is converted into a datatype which represents the function to call +
>>  it's free variables.  The longer these chains of event handlers get,
>>  the more free variables in the later functions.  My concern is that it
>>  will cost me a lot to convert these datatypes.  I am under the
>>  impression MLton will flatten them out into one record at each step
>>  rather -> O(n^2) cost for n steps of function nesting (if nearly all n
>>  variables are used in the last step, which is quite typical).  Should I
>>  be worried?
>
> I don't know enough about the specifics of MLton's closure conversion,
> but I would personally be more worried if MLton wouldn't be doing
> something like that to avoid space leaks.

I wouldn't worry about closure conversion unless you have code that 
demonstrates a problem.  It is true that MLton's current closure 
conversion will create a flat tuple of free variables for each lambda.  In 
particular, nested lambdas that share free variables with outer lambdas 
may duplicate some of the free-variable structure of the outer lambda.
Things could be improved (see links on http://www.mlton.org/Projects).
But, given the speed of allocation, I'm not sure that you would notice a 
difference between O(n) and O(n^2) allocation for the values of n that 
would likely arise in practice; >25 levels of function nesting will be 
pretty unwieldy in source code.

As Vesa notes, space safety requires that inner lambdas only keep alive 
their free variables.  While you may desire the inner lambda to simply 
keep a pointer to the outer lambda's closure (avoiding the copy), if the 
outer lambda's closure includes free variables that are not free in the 
inner lambda, then there will be a space leak.

At best, you want the outer lambda to represent its closure with a 
distinguished sub-component that precisely corresponds to the closure that 
the inner lambda would want to share.  However, I don't believe that there 
are optimal solutions to representing/sharing closures.  (At the very 
least, it's probably an NP-hard problem.)  Plus, even if you did optimize 
the sharing, that only ends up optimizing the closure allocation 
time/space (and possibly only for the nested lambdas).  You may end up 
penalizing closure invocation time, because running the closure may 
require lots of indirections to access the variables buried in shared 
closures.