Re: How to implement lexical closures?

grom <grom358@gmail.com> writes:


> I'm working on a toy interpreter (http://code.google.com/p/zemscript/)
> and trying to implement lexical closures (http://code.google.com/p/
> zemscript/source/browse/#svn/branches/lexical_scope) . Currently when
> the function is created it copies the symbol table.


> However since it copies the symbol table the following does *not*
> work:
> create = function() {
> x = 0;
> return {
> "get" : function() { return x; },
> "set" : function(v) { x = v; }
> };
> };
>
> o = create();
> o["set"](42);
> println(o["get"]()); // Should print 42
>
> What I can't work out is how I can get the second example to work
> without breaking the first example.


The simple answer is that symbol tables should not contain the values of
variables, but only their addresses. This way, you can safely copy the
symbol table. When accessing a variable, you need to go through an
extra indirection, though, so this is a bit slower than keeping the
values in the symbol tables. If variables can not be assigned to, you
can freely copy the value, so you don't need the extra indirection.
This is exploited on many functional languages where most variables are
immutable. Immutable variables have their values in closures, but
mutable variables require the extra indirection. Since this is the
exception rather than the rule, the overall cost is not too bad.


An alternative to copying symbol tables when you create a closure is to
create the symbol table once and let all closures share this by pointing
to it. It still costs an extra indirection, this time to get to the
symbol table instead of when accessing individual variables. If you
have multiple nested scopes, you will need to have a linked list of
symbol tables, so you may have to follow multiple indirections (static
links). But closures are smaller than if you create a flat symbol table
by copying references to individual variables when you create the symbol
table for a new scope. You can get memory leaks, though, as a closure
will preserve all variables in scope (even those not accessed by the
closure), so they can not be GC'ed. If you only copy the variable
references that you actually need, the rest can be GC'ed once the
original scope is exited.


Torben

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