Thinking About Variable Scope In newLISP
rick, 2013-03-23
Updated: 2013-10-04

In the following I’m writing to user bairui on the newLISP forum. Good times! :)

Hello bairui,

I’m going to try to explain how dynamic scope of variables and static (lexical) scope of variables differ. If you don’t understand it after reading this, I will bet money that it is the fault of my bad explanation. :)

Free and bound variables

To answer this question, we should first look at a simple classification of variables: free variables versus bound variables. To explain what free and bound variables are, consider this code snippet which is at the top-level in newLISP.

(define x 42)  ; <-- 0
(+ x y)  ; <-- 1
(let (y 1) (+ x y))  ; <-- 2
(let (x 42 y 1) (+ x y))  ; <-- 3
(lambda (y) (+ x y))  ; <-- 4
(define (dumb-sum y) (+ x y)) ; <-- 5

Expression 1 has two variables: x and y. Both of them are free. Expression 2 has the same variables, but only x is free – y is bound. Why? Because the let is responsible for binding y (and BTW this is why the second item of any let form is called “the let bindings”).

Here’s a good idea to keep in the mind in determining whether a variable is free or bound in an expression: every variable is free until it is bound by something – that is, until something puts binds, or fetters, on it. That’s what let did to y in Expression 2. (Bad let!) :))

[Aside: BTW, it is not conventional to say that (non-lambda) top-level defines (as in Expression 0) “bind” variables. Hence, while associating x to 42, x is not considered bound there. In short, ignore non-lambda top-level defines.]

Expression 3 has x and y both bound, i.e. they are both bound variables and no variables in that expression are free.

When you write a lambda form, the parameter list tells you which variables are going to be bound by lambda. So, Expression 4 has y as bound and x as free. Expression 5, while being a top-level define, defines a lambda, and as we said about lambdas, they bind variables. So, in Expression 5, as we saw in Expression 4, y is bound and x is free.

The following are “binders” (in maths they are called quantifiers) of variables: let, lambda, local, etc. (I’d have to look at the manual to get an exhaustive list, but hopefully you get the idea).

Dynamic scope versus static (or lexical) scope

Now, consider the following code snippet, again at the top level.

(define x 42)

(define (f y) (let ((x 13)) (g y)))
(define (g z) (list x z))

(define (h x y) (list x y))

Notice that f calls g before it can “return” a value. It calls g with its own parameter y. Now the question is, with these definitions, what should be the value of the expression (f 3)?

Clearly, this depends on what the value of x. Why? Because x is free in g; that is, x is free in this expression: (lambda (z) (list x z)). Well then, x can take on one of two values: either 42 or 13. So, that means that the value of (f 3) is either (42 3) or (13 3). So which is it?

The answer has to do with the type of variable scoping that prevails in the language. The value of (f 3) in Scheme (which has static scope) is (42 3) but in newLISP (dynamic scope), it’s (13 3). That’s because Scheme only “sees” the value of x due to the top level definition, but newLISP sees the x binding up the call stack (as f calls g, there’s that intervening let).

Finally, let’s not forget the function h defined above. What is the value of (h 1 2)? The answer is that it is the list (1 2), both in dynamically scoped languages AND in statically scoped languages. Why this is so easy to resolve and why this point is important, is because there are no free variables in h!

So, the question of what is the value of such-and-such in dynamic scope versus lexical scope, only depends on how the free variables are resolved (or evaluated) in the greater expression being evaluated. At the heart of the variable scoping scheme (whether it be dynamic or static) is this issue of “how the free variables are resolved.” That’s pretty much it.

That’s why it is good programming practice to not have free variables in your expressions when you don’t need them. (In order words, think about the “boundness” of your variables and don’t be a lazy programmer. :)) However, there are times when you need to have a free variable in the expression on purpose, like if you want to wire in a run-time switch in your code (Lutz mentioned this earlier in this thread), but in general, when you code you should be dealing in bound variables only. This practice/discipline will really help eliminate many problems that could creep up in your code without it. (Inadvertent free variables tend to be less of a problem with lexical variable scope; however, being mindful of the “boundness” of variables should be observed as a practice with lexically scoped languages also).

I hope this helps a little.