bairui wrote:Lutz... I would love to hear more about this. I am a struggling convert to the world of functional programming and dynamic scope bewilders me. :-/
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.
Code: Select all
(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.
Code: Select all
(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 langauges. 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.
(λx. x x) (λx. x x)