[racket] metacircular interpreter, lexical scope, environment

On Wed, Dec 01, 2010 at 09:09:04PM -0500, David Van Horn wrote:
> On 12/1/10 9:03 PM, YC wrote:
>> Thanks - I have read the substitution part of PLAI and thought of using
>> substitution as well, but it seems that substitution does not constitute
>> the full solution:
>>
>>     * it only work with side-effect free code
>
> This is not entirely true, but substitution and effects are subtle.

The actual prblem is that the parameter is reevaluated every time it's 
used in teh called function.  THis lacke efficiency, but occasionally 
(as in Algol 60's call-by-name it's exactly what you need,)

>
>>     * it does not address closure
>
> You don't need closures in a substitution model.

No, as long as you take care to use systematic renaming of variables.

If you substiture A for x in (lambda y ...y.y.y...) and A contains a y, 
then you have to pick a brand new variable name (I'll call it z), 
replace y by z, and fo on substituting A for x in (lambra z ...z.z.z...) 
instead.  Doing this, you achieve the same effect as closures.  But 
closures can be a lot faster if done right.
 
>
>> Maybe I am looking too far ahead, but it seems like I cannot get away
>> from needing my own call stack?  Or am I missing something?
>
> I'm not exactly sure what you mean about your own call stack.  The  
> environment and the control stack are separate issues.

That's right.  You need your own environment.  Each funtion value 
contains the code to be executed, and the name-bindings for names that 
were around where the lambda-expression was evaluated that led 
to the function value.

You actually have quite some freedom as to how you go about evaluating 
the pambda-expression.  You can leave it mostly alone, and let the 
function value be a pair (lambda-body, environment-name-value-pairs), 
and then call the interpreter on the lambda-body after setting up an 
environment consiting of the functions environment and additional 
bindings for th parameters.

Or you can actually compile it to machine code at run-time.  But even 
that machine code will have to be able to find the bindings from the 
environment.  (it might even contain them).

Or you can precompile the functino body and essentially pass it the 
environment as an extra parameter.

Now it often happens, at least in many programming languages (Pascal is 
an example, but Scheme is not), that functions are imprisoned within the 
block they are declared in.  Once that block has been exited, it's 
impossible ever to call the function value.  In that case, and that case 
only, it's valid to put the environment on the stack.  THis is 
efficient, but only if the language has this function-lifetime 
restriction.

-- hendrik


>
> David
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users