[racket] metacircular interpreter, lexical scope, environment

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