Language shapes the way we think

Sat, 10 Aug 2002 14:53:00 +0000

Language shapes the way we think. This is easy to believe after several days reading and writing x86 assembler.

So we’re talking about the new bind vop and related bits. The issue here is dynamic variable bindings: please skip the next two paras if you feel like it.

In Common Lisp – as in most languages, variables are usually lexically bound. That is, they’re declared in the current function, or in the function textually enclosing it, or in that function’s enclosing that, ad global. The alternative, dynamic binding, is that when a variable is not found in the current environment, we look at the environment of the caller, and if we can’t find it there we work our way up the call stack. Lexical bindings make it a whole lot easier to see statically what’s going on (your function behaves the same no matter who called it) which is generally considered better for everyone concerned (humans and compilers)

Which is not to say that dynamic binding is pointless. If you want to do something like pretty-print a tree using a recursive function, you might have a whole bunch of variables describing where to draw the next subtree (left edge, right edge, scaling factor, etc etc) which change as you descend a branch and which you need to restore as you unwind back up the tree. Dynamic binding gives you this behaviour For Free (as does using lots and lots of function arguments, but that gets kind of unwieldy when you realise you need to add another argument at every call site). So, CL (like Perl, in fact) provides both kinds of variable in the language . For historical reasons, we call the dynamic variables specials, and usually we mark their names with asterisks (like-so) to alert the programmer to what’s going on. All clear?

OK, break over. Settle down, class.

If we want to implement dynamic binding in a fashion that makes variable lookup reasonably fast, we do it with a slot in each symbol that stores the current value, and a stack of (variable → previous value) pairs. To rebind the variable (this is what the bind vop is for) we push the current value on the stack. To unbind, we pop the stack and set the value slot to whatever it was. That’s unbind.

For a single-thread implementation this is great. You can code symbol value lookup as

(storew value symbol symbol-value-slot other-pointer-lowtag)
which translates to something dead simple like “store value in the location given by symbol+5” (FSVO 5 equal to symbol-value-slot*4+other-pointer-lowtag).

Obviously this doesn’t work when you have many threads all wanting to bind the same symbols. If you have userland threads you can make the thread switch unwind and rewind the binding stack. If the kernel is doing the context switch you can’t really make it do this for you, though. If the machine is SMP, there may not even be a context switch to happen: you could actually have two cpus executing lisp code simultaneously. So, you need some kind of per-thread storage area and a slot in the symbol to store an offset into this area

So, we have three options

Now I have to stop writing x86 assembler for a while, and start writing English prose – or some approximation thereto, anyway. The ILC people are probably expecting a paper some time between now and Thursday