Lexical Closures without true Garbage Collection
Scott
discuss implementing lexical closures in the absence of true garbage
collection. Perhaps some clever reference counting strategy using
weak references in important places. (I've googled for a day or two,
but I'm not finding too much. Maybe it's not possible...)
Thanks in advance!
Cheers,
-Scott
Jon Harrop
You can classify closures as downward closures and upward closures. Upward
closures are returned from functions and carry values back up the call
stack, resulting in statically-unbounded value lifetimes and, consequently,
requiring a real GC. In contrast, downward closures are only available to
deeper function calls so they may be stack allocated and do not require a
garbage collector.
Some languages (e.g. Ada) restrict themselves to only downward closures
because they can be implemented without undermining determinism, even if
that means wasted memory.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
George Neuner
wrote:
Take a look at region based memory management. Here's a few papers to
get you started: http://www.it-c.dk/research/mlkit/papers.html
George
Scott
>
> You can classify closures as downward closures and upward closures. Upward
> closures are returned from functions and carry values back up the call
> stack, resulting in statically-unbounded value lifetimes and, consequently,
> requiring a real GC. In contrast, downward closures are only available to
> deeper function calls so they may be stack allocated and do not require a
> garbage collector.
>
Upward closures are what I'm interested in, but I'm wondering if there
are any ways to make do without having a true garbage collector. For
example, if you place the restriction that your closure can not be
bound to a location which is reachable from the closure, then you
would not have any reference cycles and could use reference counting.
I'm wondering if there different tricks with perhaps different
restrictions along these lines.
Cheers,
-Scott
Torben Ægidius Mogensen
You can do it if you use copying semantics instead of sharing: You
copy the values of the free variables into the closure and return the
full closure on the stack rather than just a pointer to it.
Since closures can have different sizes, you need to store the size of
the closure as its first word, which again requires variable-size
activation records (frames) etc.
Torben
Scott
wrote:
>
> You can do it if you use copying semantics instead of sharing: You
> copy the values of the free variables into the closure and return the
> full closure on the stack rather than just a pointer to it.
>
That would work, but I was hoping to have mutable variables that could
be shared (and that updates to free variables would be visible outside
of the closure). I think George Neuner's list has some promising
stuff on region based allocation that looks promising, but I don't
understand it very well just yet.
Cheers,
-Scott
Waldek Hebisch
Well, obvious alternative to garbage collection is explicit
deallocation and clearly one can use explicit deallocation
for closures.
It seems that you want garbage collection for closures
"in the absence of true garbage collection". Note that
closures can be used to implement cons cells. So your question
seem to be about garbage collection "in the absence of true
garbage collection" -- there is rich related literature.
Restricting problem to closures does not really change it.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Scott
>
> It seems that you want garbage collection for closures
> "in the absence of true garbage collection". Note that
> closures can be used to implement cons cells. So your question
> seem to be about garbage collection "in the absence of true
> garbage collection" -- there is rich related literature.
> Restricting problem to closures does not really change it.
>
Yeah, that clicked after I thought about it for a while. Using
closures to implement mutable cons cells is an existence proof that
closures are really full featured objects and therefore a real (not
just reference counting) garbage collector is required in the general
case.
Thanks for the reply though.
Cheers,
-Scott