dynamic and lexical scoping - anyone help me understand it?

[cormullion]

I decided it was time for me to learn about this, since I've avoided it hitherto (no mention of it in 'Introduction to newLISP"... :-))

Apparently newLISP is bad because it has dynamic scoping... Can someone explain in words of one syllable why that's bad? And what's lexical scoping (which newLISP also has, but not enough to make it less bad)?

(I have read the manual. But it was very condensed...)

The Wikipedia article is a start, but the examples were in C and Perl, so it wasn't easy to translate them into newLISP...

[newdep]

Actualy good question...I personaly dont care what i use,
but im intrested in a good explenation too ;-)

[m i c h a e l]

Hi cormullion!

This link has a simple explanation:

Dynamic Scope

In a dynamically scoped language, e.g. most versions of Lisp, an identifier can be referred to, not only in the block where it is declared, but also in any function or procedure called from within that block, even if the called procedure is declared outside the block.

m i c h a e l

[rickyboy]

Here's a short example which hopefully will illustrate the difference. Say you have the following definitions entered into your newLISP session.

Code: Select all

> (define x 42)
> (define (f x) (g (+ x 2)))
> (define (g y) (+ y x))

Now, can you guess the value of (f 1) before evaluating it at the newLISP prompt?

The answer will either be 45 (i.e. y + x = 3 + 42) or 4 (i.e. y + x = 3 + 1); that is, the answer depends on which x you are referring to.

It turns out that the answer is 4. But not so with Scheme, for instance:

Code: Select all

$ scsh
Welcome to scsh 0.6.6 (King Conan)
Type ,? for help.
> (define x 42)
> (define (f x) (g (+ x 2)))
> (define (g y) (+ y x))
> (f 1)
45

But what is happening? In Scheme, which has lexical variable scope, g can only see the x at the top level (or any level above it in a nested definition). In newLISP, g sees the x defined "through" the running application of f (hence, the term "dynamic"), since that x is f's formal parameter.

Hope that helps and doesn't confuse.

[cormullion]

Thanks, Ricky. Light is dawning... :-)

My initial reaction is that dynamic scoping is problematic, because it seems that:

Code: Select all

 (define (g y) (+ y x))

will give different answers, depending on where you call it from, since x may or may not be a global x or an x inside a calling function.

So the apparent problem with DS is that if you're a sloppy programmer and use symbols that aren't defined in your functions you won't know whether a symbol is 'global' or is inherited from a calling function... And that other people will use your functions and pick up the wrong values for symbols... unless you bother to read their code first...

OK - so how do I avoid it using contexts?

[rickyboy]

OK - so how do I avoid it using contexts?

Easy. If g were in a context with the top level x from the previous example, then you'd get the same answer as in Scheme:

Code: Select all

> (define (f x) (g (+ x 2)))
> (context 'g)
g> (define x 42)
g> (define (g:g y) (+ y x))
g> (context MAIN)
> (f 1)
45

But most of the time, I write functions which don't have free variables (not counting primitives like +); so I don't have to resort to making contexts just for my functions.

For instance, note that the body of g has two variables x and y. y is a bound variable in g, since it is a formal parameter of g. However, x is unbound, i.e. "free".

If I ever notice free variables in the body of my functions, it is usually due to either an oversight (e.g. I meant it to be a local variable and I forgot to bind it by a let(n) or a local) or it is free on purpose (i.e. it's supposed to refer to a global variable). Usually the former case prevails and I have to fix the problem, but when the latter case holds, it's still not a problem due to the naming convention I have for globals (to put asterisks around the name like *this-is-a-global*) which doesn't conflict with names I choose for the non-globals I use (i.e. the ones that show up on the stack).

[cormullion]

If I ever notice free variables in the body of my functions, it is usually due to either an oversight (e.g. I meant it to be a local variable and I forgot to bind it by a let(n) or a local) or it is free on purpose (i.e. it's supposed to refer to a global variable).

This seems a useful way of thinking about the problem... so thanks!

You can spot free variables lexically - if it's not in a let or a local list inside a block or function definition, it must be global/dynamically scoped... ?

Interesting idea to use asterisks - looks familiar... ;-)

[Lutz]

But most of the time, I write functions which don't have free variables (not counting primitives like +); so I don't have to resort to making contexts just for my functions.

Yes, that is the best practice, and most experienced programmers work like this anyway in any programming language and in the spirit of structured programming.

it's still not a problem due to the naming convention I have for globals (to put asterisks around the name like *this-is-a-global*)

... which is a commonly used convention for Lisp programmers and most people from other Lisps will immedeately understand you mean a global.

Or what I sometimes do, is putting all globals into a context, e.g.:

Code: Select all

(set 'Setup:data-path "/home/data")
(set 'Setup:language "english")
(set 'Setup:n-records 12345)

This has also the advantage that all your globals and/or constants can be saved/loaded to a file in one swoop:

Code: Select all

(save "setup.lsp" 'Setup)

; or when reloading

(load "setup.lsp")

As Rickyboy was showing, contexts give you the the lexical fence. This is why a multiprogrammer/bigger project in newLISP always should be divided in context modules, so nobody steps on each others feet.

newLISP gives you the best of both worlds: you can make use of dynamic scoping but also build lexical fences using contexts to avoid the dangers of it.

Lutz

[Jeff]

I personally prefer dynamic scoping because it forces you to write functions without side effects. I like the idea of having multiple, named, dynamic scopes, though, a-la python modules.

[cormullion]

I'm still puzzled - but for different reasons, now! ;-) If - as I understand it - dynamic scoping is the way that otherwise unassigned symbols are evaluated in functions called by other functions, I can't see what the fuss is about. People seem to think that dynamic scoping is the devil's work... :-)

I'm not much of a programmer, but I don't think I tend to refer to symbols without knowing what they are and where they're defined, except by mistake. I use global variables a lot - but not without knowing that they're global... There are plenty of more common pitfalls awaiting programmers in every language than that, I would have thought...

Thanks for the explanations...!

[Jeff]

Dynamic namespaces are better for non-object oriented languages, particularly procedural or functional languages. Lexical namespaces are kind of a way of protecting sloppy programmers (in my not-so-humble opinion).

If you take rickyboy's example, the lambda f is redefining x as whatever is passed to it. Now, since lambda g is called from inside lambda f, lamba f's scope takes precedence over the global.

With lexical namespaces, the scope from which lambda g is called is irrelevant. Only the scope in which it is defined matters.

This book has an excellent intro to dynamic scoping: http://www.cs.cmu.edu/~dst/LispBook/book.pdf

It is a bit dated (in that it teaches ansi common lisp as it was in the 80s, I believe), but since common lisp has not changed that much since then, it's still relevant, and it gives an excellent foundation in lisp technique.

[cormullion]

thanks, jeff

your blog (http://artfulcode.blogspot.com/) looks like interesting reading too, btw!

[Jeff]

Thanks. It's new. I got sick of everyone giving me that glazed look when I talked about what I do, so I thought I'd see if it was a universal effect ;)

[cormullion]

One more question - to see if I've got this sorted out yet. In the following code, is the width symbol in the right-justcontext statically or lexically scoped, and is the w symbol in the dolist dynamically scoped?

Code: Select all

(context 'right-just) 
(set 'width 30)
(define (right-just:right-just str)
  (slice (string (dup " " width) str) (* width -1)))

(context MAIN)

(set 'width 1) ; just a test

(dolist (w (symbols))
  (println (right-just w)))

I'm wondering whether it's the terminology that's confusing me rather than the actual behaviour itself...

thanks if you can dispel the gloom!

[Jeff]

Technically, they are all dynamically scoped - the entire language is. All variables obey the same rules for scoping. However, contexts allow you to wall off a scope to provide newlisp with some of the features of lexical scopes. Contexts are their own, isolated, dynamic scopes.

There is a difference between global versus local scope and dynamic versus lexical scope.

Both dynamic and lexical scopes have both global and local scopes. More accurately, there are dynamic and lexical namespaces. These determine the rules for how symbols may be accessed within global and local scopes.

Contexts let you create additional namespaces. When you use a function, it creates its own local scope internally. This means that when you access a symbol, the interpreter will first look at the local scope. If it cannot find the symbol there, it will then look to the scope the next outside scope. For example:

Code: Select all

(set 'a-list '(foo bar baz))
(set 'b "Hello there")
(dolist (b a-list)
  (= b "Hello there")) ; => evaluates to nil, because b is locally declared in the dolist

That is an example of local scope overriding a globally declared symbol. What dynamic/lexical namespaces do are determine the parent scope of a local scope. So,

Code: Select all

(set 'a 50)
(define (foo)
  (println a))
(define (bar)
  (let ((a 10))
    (foo)))
(bar)

When we run bar at the bottom, it first enters the bar lambda. It then enters the let scope. It then runs foo.

With dynamic namespaces, foo's outer scope search will proceed through let, bar, then global. In lexical, foo will search for 'a in foo, then global. Lexical is literally that - based on its lexical location.

Dynamic is determined by where it is called. Because foo is called form within bar and let, those are its parent scopes. In a lexically scoped language, because foo is defined outside of bar, it has no internal relationship with bar.

[cormullion]

thanks jeff - i'll work this a few times today to see if it makes sense. I'm grateful that you've spent some time trying to help...

One thing, though - the word lexical to me (and the OED) means "Pertaining or relating to the words or vocabulary of a language. Often contrasted with grammatical." What do computer programmers mean when they use the word?

[rickyboy]

One thing, though - the word lexical to me (and the OED) means "Pertaining or relating to the words or vocabulary of a language. Often contrasted with grammatical." What do computer programmers mean when they use the word?

They mean "of, or related to, program text." Wikipedia has a nice blurb about it:

With static scope, a variable always refers to its nearest enclosing binding. This is a property of the program text and unrelated to the runtime call stack. Because matching a variable to its binding only requires analysis of the program text, this type of scoping is sometimes also called lexical scoping.

Hope that helps! --Rick[y]

[cormullion]

yes that was a good bit... But you can see why i get confused -

Generally, certain blocks are defined to create bindings whose lifetime is the execution time of the block; this adds a hint of lexicality to the scoping.

[rickyboy]

yes that was a good bit... But you can see why i get confused -

Generally, certain blocks are defined to create bindings whose lifetime is the execution time of the block; this adds a hint of lexicality to the scoping.

Yes, I agree that part is confusing -- it was a poor choice of words.