Books of Note

Practical Common
LispThe best intro to start your journey. Excellent coverage of CLOS.

ANSI Common
LispAnother great starting point with a different focus.

Paradigms of Artificial Intelligence
ProgrammingA superb set of Lisp examples. Not just for the AI crowd.

Saturday, May 01, 2004

Special vs. lexical variables 

David Steuber spawned this thread the other day on comp.lang.lisp. The thread started off asking about multi-threading in SBCL but degenerated into a discussion of special (aka "dynamic") vs. lexical variables. I, myself, had spawned a huge thread earlier this year that covered much of the same ground. In the process, I managed to step on the toes of just about every comp.lang.lisp guru, including Erik Naggum and Erann Gat. Yup, sometimes I don't know when to shut up... ;-)

Well, special variables are a difficult concept; they are very different than anything I have encountered in my decades of programming. Coming from a language like C, you're likely to think of special variables as globals, which they are on one level, but with some special properties. Further, the distinction between binding and assignment is also different than what you first expect and the distinction impacts how special variables act.

The easiest way that I have found to think about special variables is to imagine each global variable as a stack of slots storing values. The top of the stack represents the value that is returned if the variable is evaluated. You create a special variable binding using DEFVAR or LET/LAMBDA with a (DECLARE SPECIAL ...) form. The first such form creates the conceptual stack of value slots. Now, when you assign to a special variable, using SETQ or SETF, you are just changing the value of the top slot on the stack. The interesting part is when you create a new binding for the variable using LET (or LAMBDA since LET is just syntactic sugar for introducing another LAMBDA form). The LET form has the effect of pushing a new value slot onto the stack and setting it's value (conceptually, that is, the implementation is probably radically different). From that point on in the dynamic execution of the program "beneath" the LET form, an evaluation of the variable will retrieve the new value represented by the top of the value stack. Setting the variable with SETQ/SETF (simple assignment) sets the value of the top slot and does not push/pop the stack. As soon as the LET form terminates, however, it pops the stack and the variable is returned to the old value that it had prior to the execution of the LET form.

Another way to think about this is that each activation record created by the thread of execution has a list of bindings that are created in that context. When the system needs to retrieve or set of a special variable, it searches backwards through the activation records to find the last dynamic binding. It stops upon finding the last previous binding and performs the appropriate action (retrieving or setting the value).

Now, the thing that is really strange is when you have a Lisp with multiple threads of execution. This is what David Steuber and I both had trouble with initially. There is no standard for multi-threaded Lisp; the ANSI spec doesn't consider threading at all. With a single thread of execution, it's relatively easy to understand special variables once you get a good conceptual model for how they work. Now, when we extend the model to multiple threads, most Lisps seem to implement the behavior as each thread conceptually having its own "value stack" for each special variable. That is, when a thread is created, it's as if all the dynamic variables associated with the original thread are duplicated (this is obviously optimized in an implementation) with their initial values set to the current values in the original thread (UPDATE: Dan Barlow wrote and told me that this is SBCL's behavior, but many other Lisps set the inital values to the original value of the special variable, ignoring all the subsequent dynamic binding). Rebindings of a special variable in a given thread only affect the values seen by that particlular thread; other threads have their own sets of special variables that are separate from all other threads. Now, this effectively gives each thread a set of local variables, much like you could create manually under various other threading systems (Windows, Java, etc.).

In the old days, they say (I wasn't there), many Lisps had only special variables (are they really that special when they're all you have?). The problem is that bugs associated with the dynamic/special behavior are quite difficult to debug. You can have one part of the program affect another part and it isn't clear what the connection between the two is unless you're looking at the call graph.

Scheme and Common Lisp seemed to push the Lisp community toward lexical variables which were much easier to handle. Indeed, it seems the convention of adding "*" characters to special variable names was done specifically to highlight their special properties and reduce the chance that a programmer would write a clashing "(LET ((VARNAME ...)))" form by accident. Any time you say "(LET ((*VARNAME* ...)))," you know you are dealing with a special variable and are creating another dynamic binding.

Yes, I know that it's confusing. Understand the semantics, however, as they are important. For starters, you can just think of special variables as roughly similar to global variables in a language like C, and that's true as long as you simply set them and never rebind them using a LET/LAMBDA. You'll soon want to understand the differences, though, as the special nature of these variables can be very helpful in some situations.

A great resource that might help you understand more is Erann Gat's Idiot's Guide to Special Variables.

Post a Comment

Links to this post:

Create a Link

This page is powered by Blogger. Isn't yours?