Re: Implementing Closures

Andrew Tomazos <andrew@tomazos.com> writes:




> What are some of the approaches a compiler author could use to
> implement such a language feature?


This depends on how local variables are otherwise stored in the
runtime system and whether you can update variables after their
creation. If you can't, you can copy variables into a closure.


If you store local variables in activation records, a reference to the
activation record of the scope where the function is defined together
with a code pointer to the function is all that is needed.


However, you must limit the lifetime of the closure to the lifetime of
the activation record. If activation records are stack allocated, you
can't return closures from functions nor store them in variables
outside the scope. This is the solution chosen by Pascal.


If you want to return functions as results or otherwise have them live
beyond the lifetime of their scope, you must either heap allocate the
relevant parts of the activation records or copy the relevant parts
into a heap-allocated closure. Copying, however, requires that the
copied value is not afterwards assigned to (as the copy would not be
updated by the assignment). Mostly-functional languages like SML
handle this by heap allocating all variables that can be destructively
updated, so activation records hold references to imperative variables
and values of non-imperative variables. So when creating a closure,
you can freely copy variables from the activation record. The
advantage of copying variables when creating a closure instead of just
heap allocating activation records is that the closure will only hold
the variables actually needed by the closure, where the activation
record holds all variables in scope. This, as another poster
mentioned, can lead to space leaks. Also, the copying-style closures
only cost when you actually use higher-order functions: As long as you
use only first-order functions, the cost is the same as in a
first-order langauge (with the exception that you must heap allocate
imperative variables).


If you use the copying apporach, you can stack allocate the closure
and when you return from the function, you copy the entire closure to
the destination activation record. Since closures have different
sizes, it requires that the activation record can handle
variable-sized stack-allocated data. It also costs more to copy a
full closure than to just copy a reference to a heap-allocated
closure, but you can avoid heap allocation entirely (if you don't have
imperative variables).


Another alternative to heap allocation of closures is to statically predict
the lifetime of a closure and allocate it so far down the stack that
it won't be unstacked until after the lifetime expires. This requires
allocation deep in the stack, so you need a stack of expandable
regions. This is the approach of region analysis (which can also
replace heap allocation of other data, such as lists).


You can also do closure conversion: Transform the source program so
all building of closures is done at the source level. For
heap-allocated activation records, this requires (part of) the
activation record to be made explicit in the source program. Closures
that contain copies of variables can be built only by referring to
variables that are already in scope in the source, so this is a bit
simpler.


Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.