Re: safe-for-space

On Thu, Apr 24, 2003 at 10:32:32AM +0100, Matthias Radestock wrote:
> There is a discussion going on in c.l.s. about "Proper Tail Recursion" 
> that is related to the "space leaks" email I sent the other day.
> 
> SISC is properly tail recursive, but it's not safe-for-space. For it to 
> be safe-for-space we'd need to ensure that when closures are created 
> they only hang on to lexical references that they are referring to.
> 
> One way to achieve this is to copy these bindings into the new LE when a 
> closure is created. Thus a closure's LE would no longer need to refer to 
> the parent LE, allowing that to be gc-ed. This doesn't work when set! is 
> used to mutate lexical bindings captured by closures. However, this can 
> be detected by the compiler and resolved by boxing such lexical 
> references. A new BoxedLexicalReferencExp would be emitted to access 
> these lexicals.
> 
> I have no idea what the above would do to performance, but I think 
> safe-for-spaceness would be a cool property to have, so it's worth a try.

I've been doing a lot of thinking on this, and I think that it would 
have a minor performance penalty on closure creation which *may* be 
offset by gains in lexical reference speed.  There would also obviously 
be a penalty for set! and referencing set!'d variables, but thats good, 
in a way.  

The biggest downside is that it would require the compiler to have two 
passes.  The first would have to find out which variables are set!, 
which are lexical, and which are local.  The difference between lexical 
and local is best illustrated as:

(lambda (a)
  (lambda (b)
    (+ a b))

'b' is a local, 'a' is a lexical.   The first pass would annotate the 
incoming code with this information, so that the second could figure out 
how to allocate the lexicals to ribs, above we'd have:

+-+-+
|b|a|
+-+-+

Obviously it could be more complicated.  

Due to the complexity, I'd like to postpone this to 1.9, but it has 
obvious benefits in space efficiency, and possible benefits in 
efficiency for code which uses closures more than it makes them.

	Scott

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+reYcr9IW4v3mHtQRAhSVAJ45ZRyKrV2SCUffy93p0ICgmh8wmwCfaDpo
XRXNzyAvJZhjJvBcAWJ9RtQ=
=wHu8
-----END PGP SIGNATURE-----