Re: Representing Closures in C

"Johan Tibell" <johan.tibell@gmail.com> wrote:
# > > [There's certainly been a lot of work on this. Seems to me you basically
# > > want to carry a symbol table along with each expression. -John]
#
# I threw together a crude and probably incorrect interpreter tonight. I
# store bound variables in a linked list that's carried along with the
# closure.


A closure is a dynamic stack of scopes; a scope is a mapping (or
dictionary) from identifiers to values. There are many ways to
implement a scope mapping: linked list of identifiers, self organizing
list, sorted tree, hash table, etc. If you don't need a sorted
traversal, you can get a hash table implementation out of a library on
many systems.


The stacked scopes is just the innermost scope defining an identifier
is used. You can maintain an actual stack of scopes; or you can have a
scope be a dictionary of an identifier to a stack of values, or you
can smash the scope stack. One advantage of a stack of scopes is ease
of sharing outer scopes amongst closures: you then end up with a tree
of scopes, each closure being a path from a leaf to the root. This
also means you can safely use reference counts to decide when a scope
is garbage.


The really big issue is when the identifier value is a variable on the
procedure stack, because procedure stack frames are automatically
recoverred on procedure exit of most languages unless you change the
language implementation. This doesn't occur in applicative language
because the identifier value is never a variable. Algol-68 could have
supported closures because you can use heap variables instead of local
variables.
--
SM Ryan http://www.rawbw.com/~wyrmwif/
What kind of convenience store do you run here?

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