Re: Implementing Closures

Torben Fgidius Mogensen <torbenm@pc-003.diku.dk> wrote:
+---------------
| 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).
+---------------


Actually, even assignment/updating/mutation is o.k., as long as the
binding of a mutated variable is either not shared by more than one
lexical contour [environment] or not captured in a closure which
escapes the dynamic lifetime of the function which creates the
closure.


+---------------
| 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.
+---------------


This conversion of mutable variable bindings to immutable bindings of
references to mutable heap objects is sometimes called "boxing" or
"box conversion". Both PLT Scheme and CMU Common Lisp use this
technique.


+---------------
| 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.
+---------------


In his book "Lisp in Small Pieces", Queinnec calls this the "flat"
style of closure environments [as opposed to the "linked list of
activation records" style]. It allows the closure's environment to be
a single compact vector.


+---------------
| This, as another poster mentioned, can lead to space leaks.
+---------------


Not only that, but the "linked list of activation records" style
requires traversing the environment list for each access of a
closed-over variable, whereas in the "flat" environment style variable
access is O(1) -- either a single vector reference or a single vector
reference followed by an indirect "box" access.


+---------------
| 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).
+---------------


But, again, heap allocation is only necessary if the imperative
[mutated] variables are both shared by multiple environments and
closed over by closures which escape the dynamic extent of the
closure-creating function call. So, in practice, given the access-time
advantages, copying-style closures ["flat" closure environments] are
usually much cheaper on average than linked-activation-record style,
although the former require slightly more effort during program
analysis.




-Rob


-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

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