3

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.

Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353
Wei Peng 彭巍
  • 99
  • 3
  • This is certainly an interesting topic, and there are lots of resources out there for anyone interested in it, but as it's not a question about a specific programming question, it's probably off topic for stack overflow. You might have better luck with it on http://programmers.stackexchange.com, however, which is about conceptual software development questions. – Joshua Taylor Aug 29 '13 at 20:28
  • 2
    This question appears to be off-topic because it is an invitation to discussion, rather than an easily-answerable question. – Vatine Aug 31 '13 at 08:01

1 Answers1

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:

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).

Community
  • 1
  • 1
Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353
  • Thanks for the comments and links, Joshua. I did not find these answers before asking mine. They are quite relevant to my question. – Wei Peng 彭巍 Aug 29 '13 at 20:44