Re: Implementing Closures

"Armel" <armelasselin@hotmail.com> wrote in message
> "Andrew Tomazos" <andrew@tomazos.com> a icrit dans le message de news:
>> What are some of the approaches a compiler author could use to
>> implement such a language feature?
>
> The approach we used for our ECMAScript engine is to consider that a
> function is an object built around two things: the text to execute and the
> scope for it.
>
> during the compiling phase, a map is built of the outer automatic
> variables
> referenced inside each function.
>
> during the execution phase, an automatic variable is built from the
> current
> scope/refined through the above map + the pointer to the text to execute,
> which bares the name of the function.
> thus when executing "return my_local_function" you actually return the
> complex object 'scope+text pointer'.


> I read the C++0x specification in the wikipedia (next generation of
> c++ build specified) some time ago, there are interesting things
> about closures there, although I don't remember anything specific
> from a low-level implementation point of view. e.g. there are
> notations about what to import, what to copy/what to reference...


one thing I can think of is that a compiler could keep track of what all
variables are "captured" by a sub-function, and then allocated them in a way
which they could be easily captured at runtime (such as in special
heap-allocated or GC'ed memory), and if captured at runtime (such as a
closure being created), then they are left on the heap, otherwise they are
freed when the function returns.


another possibility is CPS and heap-allocated frames, but this is likely to
be a notable performance impact (I had designed such a scheme before, and
even with tight control and optimization, it still did not look so good...).


allocating storage for potentially-captured variables, OTOH, is much less
likely to be a problem (after all, there is no overhead if it is not used)




some internal compiler trickery could be used to help distinguish the plain
nested-function case from the closure case (while still keeping it safe to
use with plain C code), namely that a few special flags could be kept in
(potential) closures, and whenever passing them to a sub-function they are
marked as "potentially unsafe", and the leaf function (from the POV of
closure passing), if it knows itself that its usage is safe, will remark the
closure as safe or unsafe (the unsafe status is sticky...).


on return, if marked safe, it may continue to be used as before (and kept
safe if known safe at return). if however, a callee returns and the closure
is still 'potentially unsafe', it is marked unsafe.


when it gets back to the function of origin, if it is still 'safe', then
storage may be reclaimed, otherwise then it is upgraded to being a
full-fledged closure at this point.




the issue then is what to do if passed around through plain C code which may
then decide to use a longjmp or similar... (then again, in this case, even
if the flags are in an inconsistent state, if we longjmp through the
function of origin, the captured bindings will remain intact...).


OTOH, it could also be possible to upgrade a function to a closure just as
soon as the safety of the callee can't be determined, which could be done
(approximately) even at compile time (thus eliminating the need for keeping
track of or setting flags). this static approach is actually a lot closer to
how some of my past VMs had managed this problem...


(if we can't statically determine that it is safe, it is probably not safe
anyways...).

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