[racket] metacircular interpreter, lexical scope, environment

On Wed, Dec 01, 2010 at 05:00:51PM -0800, YC wrote:
> On Wed, Dec 1, 2010 at 4:13 PM, Hendrik Boom <hendrik at topoi.pooq.com> wrote:
> 
> >
> > I'm not sure I understand the question, though I suspect I may know the
> > answer.  Could you be a bit more specific?
> >
> 
> Yes - definitely.  See below.
> 
> 
> > I'm not sure what you mean by "optimized away so they won't show up on a
> > call to eval".  And what, spoecifically, are "lexical variables"?
> > Variables that have scope determined lexically?
> >
> 
> Yes I mean variables with scopes determined lexically - I thought that's
> what they are called - is there another term for them?  lexically-scoped
> variable/identifier, local variable?

Your terminology is OK.  It's just that it's occasionally misused.

> 
> So what I am trying to do is to build an interpreter, hopefully a
> metacircular one so I can leverage racket as much as possible, but without
> using the built-in eval, i.e. I need to construct my own lambda, etc.
> 
> In this interpreter, identifiers are resolved against a custom environment
> made of an immutable hash table.  This works well for toplevel calls, but
> when coming to lexically-scoped variables the choice isn't as certain.

The immutable hash table doesn't work well for lexically scoped 
variables.

> 
> The simplest approach I can think of is to put it into the same environment.
>  This also work nicely w.r.t. shadowing since they effective overwrite the
> local copy of the environment (it's an immutable hash table so other
> references are not affected).

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 what I've read about lexical scoping is that the variables do not really
> exist since they are substituted away - they do not leave trace on the
> namespace:
> 
> (let ((a 2))
>     (eval 'a))
> ;; => Error: reference to undefined identifier: a

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 I am trying to figure out what is a better representation.
> 
> What I can think of so far all involve some sort of activation frame for
> holding the values.

Yes.

>  That basically means I will need to maintain my own
> stack, and I was trying to see if there are simpler ways to approach the
> problem.

But the activation frame doesn't have to be on the stack.  It could, 
say, be om the heap.

> 
> Please let me know if this is still being unclear.  Thanks.
> yc

YOu've become quite clear.  I've given more details in another post in 
this thread.

-- hendrik