Point by Point Comparison of Lisp and Scheme | Hacker News Reader

Point by Point Comparison of Lisp and Scheme

groups.google.com

29 pointspchristensen8 comments

There's actually a common misconception about Scheme being lexically scoped only. You have to dig very deep into the Scheme literature to find it, but Scheme actually requires both dynamic and lexical scoping of variables depending upon the way they are defined.

Almost all variables in Scheme are lexically scoped, the exceptions are variables created by a "(define ...)" statement. The reason for this (which is spelled out in "The Art of the Interpreter") is to support defining recursive functions.

So, for instance, the following should work in pretty much any Scheme REPL:

    > (define foo 1)
    > (define (bar n) (+ foo n))
    > (bar 2)
    3
    > (define foo 2)
    > (bar 2)
    4

If "(define ...)" statements actually created lexical variables, then both calls to "bar" would return the same result.

I don't think I quite understand how the two interact, but wouldn't your example work with either lexical or dynamic bindings?

    > (let ((foo 1)) ; foo is lexical
    >   (define (bar n) (+ foo n))
    >   (bar 2)      ; => 3
    >   (set! foo 2)
    >   (bar 2))     ; => 4

(Naturally, if instead of set! you do (let ((foo 2)) ...), it gives 3 again. But that's creating a new lexical scope, whereas in your example both definitions of foo are in the same scope, as is the definition of bar. I think.)

OTOH,

    > (define (bar n) (+ foo n))
    > (let ()      ; create a new lexical scope
    >   (define foo 1)
    >   (bar 2))   ; error: unbound variable 'foo'

My understanding of dynamic variables is that bar would see the value of foo just defined, and return 3. Am I confused?

(Tested with guile 1.6.7, which I gather is pretty old. Maybe that's the problem?)

edit: tested this in perl as well, with local to create dynamic variables.

    sub bar { print($foo + shift(), "\n"); }
    sub a { my $foo = 1; bar(2); }
    a(); # prints 2, or errors if use strict is on.
    sub b { local  $foo = 1; bar(2); }
    b(); # prints 3.

Well, dynamic scoping does allow a form of destructive update, but define statements are not just an assignment; they also allocate a new memory location. So in my example the two foo's could represent completely different memory locations and it would still work.

Now for your second example; nested define statements do not allocate a top-level memory location. Instead they allocate a local memory location. Consider the following example:

    > (define foo 1)
    > (let ((bar (lambda (n) (+ foo n))))
        (define foo 2)
        (bar 1))
    2
    > foo
    1
    > (let ((bar (lambda (n) (+ foo n))))
        (set! foo 2)
        (bar 1))
    3
    > foo
    2

Here we see that the define and set! methods operated on two different memory locations. When a reference has no matching local declaration, it defaults to looking for a top-level declaration. These top-level declarations are resolved at run time, which is what makes them dynamically scoped.

Hmm. According to cltl (I didn't have time to look this up earlier), 'dynamic scope' is a misnomer/helpful abbreviation. It refers to two things: indefinite (as opposed to lexical) scope, and dynamic (as opposed to indefinite) extent.

Scope refers to where a binding can be accessed. Indefinitely scoped variables can be seen from anywhere in the program. My understanding of that is that in effect, there's only one dynamic scope. It may or may not override the current lexical scope, and there may be a mechanism to shadow and unshadow variables as they come in and out of extent. But it shouldn't make a difference where in the source code a binding is made. So I would expect your first example in that post to give 3, if define creates indefinite scope.

Extent refers to when it can be referenced. Dynamic extent means that once the binding has been unmade, the variable is no longer available.

    > (define bar nil)
    > (let ()
    >   (define foo 1)
    >   (set! bar (lambda (n) (+ foo n))))
    > (bar 2) ; => 3
    > foo     ; error: unbound variable 'foo'

That doesn't seem to hold up either. The binding is lost, but the object remains.

(Incidentally, if you (set! bar) before you (define foo), you get an error: bad define placement. I'm not sure what, if anything, that signifies, but it seemed interesting.)

ref: http://www.supelec.fr/docs/cltl/clm/node43.html

"in my example the two foo's could represent completely different memory locations and it would still work."

My understanding of closing is that once you create a lambda, it holds a reference to the lexical scope it was created in. You can modify that lexical scope and the lambda will still 'see' the changes, even if you were adding a new binding rather than just modifying an old one. So I don't see a conflict with define being lexical here.

The problem (which you are right to point out) is that only top-level defines are dynamically scoped. That's why my first example doesn't return a 3 and why the binding from a nested define statement disappears.

The top-level defines do fit the description of "indefinite scope", since they can be accessed anywhere in the program (even before they are defined). I don't know of anyway to remove a top-level define without shadowing it with another top-level define, so it would seem that they also fit the definition of "dynamic extent".

Nested defines are very strange, so I think it is understandable that they don't quite fit in with either CLTL's definitions or with the classical definition of static scoping.

could'nt have said it better:

Schemer: "Buddha is small, clean, and serious."

Lispnik: "Buddha is big, has hairy armpits, and laughs." —Nikodemus Siivola

Just curious: will there ever be something like a Common Scheme? (Hardened by common practice?)

R6RS is a first attempt at doing something like that. It's an attempt to standardize things that are continually recreated (differently) by each implementation (hash-tables, modules, structures, IO).

Reply on news.ycombinator.com