How is Lexical Scoping implemented?

To get correct lexical scoping and closures in an interpreter, all you need to do is follow these rules.

To get correct lexical scoping and closures in an interpreter, all you need to do is follow these rules: In your interpreter, variables are always looked up in an environment table passed in by the caller/kept as a variable, not some global env-stack. That is, eval(expression, env) => value. When interpreted code calls a function, the environment is NOT passed to that function.

Apply(function, arguments) => value. When an interpreted function is called, the environment its body is evaluated in is the environment in which the function definition was made, and has nothing whatsoever to do with the caller. So if you have a local function, then it is a closure, that is, a data structure containing fields {function definition, env-at-definition-time}.

To expand on that last bit in Python-ish syntax: x = 1 return lambda y: x + y gets executed as if it were x = 1 return makeClosure(, {"x": x}) where the second dict argument may be just the current-env rather than a data structure constructed at that time. (On the other hand, retaining the entire env rather than just the closed-over variables can cause memory leaks. ).

There is no single right way to do this. The important thing is to clearly state the semantics that you are looking to provide, and then the data structures and algorithms will follow.

Sure. I can always try to derive the whole thing myself. :-) But for many well understood programming tasks, there are usually existing solutions that are already known and widely taught and adopted, no?

– interstar Mar 5 '10 at 3:32 The book referenced in the comment to your question, or the famous book with the dragon on the cover, will take care of that. – bmargulies Mar 5 '10 at 12:31.

Read The implementation of Lua 5.0 for instance.

There are many different ways to implement lexical scoping. Here are some of my favorites: If you don't need super-fast performance, use a purely functional data structure to implement your symbol tables, and represent a nested function by a pair containing a pointer to the code and a pointer to the symbol table. If you need native-code speeds, my favorite technique is described in Making a Fast Curry by Simon Marlow and Simon Peyton Jones.

If you need native-code speeds, but curried functions are not that important, consider closure-passing style.

Stroustrup implemented this in the first C++ compiler simply with one symbol table per scope, and a chaining rule that followed scopes outwards until a definition is found. How this works exactly depends on your precise semantics. Make sure you nail those down first.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.