How are the "lexical and special variable" semantics implemented under the hood in general?

Question

CLtL2 has clarified the distinction between scope and extent. My take on it, in relation to lexical and special variables, is that lexical variables are “lexically scoped with indefinite extent” while special variables are “indefinitely scoped with dynamic extension.”

My question is: How are the “lexical and special variable” semantics implemented under the hood in general? By “in general,” I mean that a general idea suffices. Given the long history of Lisp, there must be numerous optimizations that have been applied to implementing these basic concepts.

To kickstart the discussion, I venture my guess below.

All start with environments. An environment is a sequence of frames, with each frame being a table that maps names to places (the value of which can be retrieved and stored); each such mapping is a binding of a name to a place. Frames are linked by the enclosing relationship; a name in an inner frame can shadow the same name in an outer frame. Also, bindings in Common Lisp default to be lexical unless declare-d/declaim-ed/proclaim-ed to be special.

There are two aspects of the semantics: name lookup and creation of a new binding.

• Create a new binding. lambda expressions, let/let*, labels/flet, macrolet, and macros using them create bindings. A lexical binding is created by creating a new frame and having the current lexical environment to be the newly created frame's enclosing environment. A special binding (which must be explicitly declared) pushes a new place to the top of the stack created for the name in the current package (the stack can be located perhaps by a hash-table on names)—the stack is used for implementing the dynamic extent so that when the constructing form exits, the binding can be deconstructed by popping the stack (a question is that how to ensure so, perhaps with something like unwind-protect under the hood?).

• Name lookup. Unless explicitly declared to be special, name lookup defaults to looking up in the lexical environment—through the frame link that was established during binding creation. The first matched name in the lookup process wins. For special names (which must be explicitly declared so), the lookup is served by looking at the top of the stack.

Answer 1

I think this question will probably get migrated to programmers.stackexchange.com, but there are some other questions on StackOverflow that provide answers to some of these questions, though none that I've found so far are exact duplicates. Have a look at:

• How is Lexical Scoping implemented?
• Is it possible to have hard real-time with lexical scope?
• Lexical vs dynamic scoping in terms of SICP's Environment Model of Evaluation

Also, for what it's worth, you'll probably find that in compiled languages, the lexical environment “lookup” actually doesn't require much lookup, and can compiled into a constant time memory reference into the lexical environment (which is still a sort of lookup, but all the work is determined beforehand, and only the retrieval needs to happen at runtime).