[racket] metacircular interpreter, lexical scope, environment

On 12/1/10 2:26 PM, YC wrote:
> Hi all -
>
> a question for those who have experiences with metacircular interpreters:
>
> How do you represent the lexical variables?  Since lexical variables can
> be optimized away so they won't show up on a call to eval, it seems
> putting them into the environment (I am using a struct holding an
> immutable hash for environment) isn't the right approach.  It feels like
> I need my own call-stack to represent them, but that sounds "heavy" for
> a metacircular interpreter.
>
> Any thoughts are appreciated, thanks.

An evaluator can implement function application using substitution, i.e. 
you can evaluate ((lambda (x) e) v) by evaluating the substitution of v 
for x in e.

Or, you can be lazy and defer the substitution.  In that case, you 
evaluate ((lambda (x) e) v) by evaluating e; you just have to remember 
that v should have been substituted for x should you ever get to 
evaluating x.  The data structure you use to remember those deferred 
substitutions is an environment.  A simple list of variable, value pairs 
is a suitable representation.

You can read all of this and more in any decent PL book that covers 
writing evaluators.  See, e.g., chapters 3-5 of PLAI.

    http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/

David