Hendrik Boom wrote:
On Wed, Dec 01, 2010 at 08:12:17PM -0800, YC wrote:
Thanks Hendrik for both responses - please see inline.
On Wed, Dec 1, 2010 at 7:23 PM, Hendrik Boom <hend...@topoi.pooq.com> wrote:
The immutable hash table doesn't work well for lexically scoped
variables.
You can end up with multiple simultaneous bindings of the same
variable in different contexts. Look up the Knuth Man-or-boy problem,
for example, in http://en.wikipedia.org/wiki/Man_or_boy_test
But isn't that what's called for in a chained environment? The inner can
see the outer bindings if not shadowed, but not vice versa.
Subsituting them away is a correct, but slow way of implementing lexical
scoping. It was invented in the days when mathematicians were inventing
formal logic, and computers weren't around yet -- more as a way of
preciely defining concepts tha a way of being practical. It had a clear
meaning before side-effects became commonplace.
So what would be a fast way?
But the activation frame doesn't have to be on the stack. It could,
say, be om the heap.
Yes agreed - I don't mean the frames need to be held on "the stack" - I
don't even know if racket's frames are on "the stack".
examples
In Scheme, call frames and environment frames are on the heap, unless
optimisation analysis makes it celar that that's not necessary in
individual cases.
I just mean that I
need to maintain my own stack of frames instead of relying on racket to do
so.
Yes, that's the fast way. It can be made faster in a compiler, where
you can compile the exact list steps through the chain of frames instead
of looking up names at run-time.
It's easy to "compile away" the name lookup even in an interpreter by
having a pre-pass* replace variable references with their "lexical
addresses" (see also "rib-cage environment"). That seems to be a very
common exercise in interpreter-based PL classes.
In fact, lexical variables are so easy to analyze that you can try other
representations too. For example, you can annotate every lambda
expression with its free lexical variables and create flat closures. But
beware of variable mutation in that case!
Ryan
*Arguably, this is a very small, simple compiler.
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
