[racket] metacircular interpreter, lexical scope, environment

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 <hendrik at 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".

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.

-- hendrik