Can dynamic scoping implement lexical scoping?

2
votes

Old Lisp, including Common Lisp at some point and elisp before emacs 24.1, is dynamically scoped, and among resources I've read, the consensus seems to be that lexical scope is just better to program in.

I'm getting the sense that dynamic scope is legitimately easier to understand. Dynamic scope can be entirely thought of in terms of symbols and their values. Lexical scopes require a new concept of "bindings" which as far as I understand currently, ruins some of the simplicity/elegance of the Lisp language.

I've been thinking about how to ask this question, "does lexical scoping break some of the elegance?" more rigorously and my best idea is to see if they are equivalent i.e. if one can implement the other.

Is it possible to implemented lexically scoped lisp as a simple extension in dynamically scoped list? And is it possible to do so without the interpreter introducing new ad-hoc symbols?

More specifically can let, which creates lexical scoping, be implemented in dynamically scoped lisp?

2
lispcommon-lisplexical-scope
This is not an answer, so I'm writing it as a comment. Dynamic scope is very much not easier to understand. On one hand, you don't need to know about closures (which is the term that you should have used in that sentence rather than bindings), which means that it's easier to implement, and superficially easier to understand. However, with dynamic scope any reference to a free variable requires running the code to know what value you get -- and running the code is (in a very deep and very real sense) much harder to understand than just reading it. – Eli Barzilay
Common Lisp, at least as far in the past as CLtL1, has always been lexically scoped by default. – acelent

2 Answers

4
votes

Dynamic scope is easier to implement and perhaps easier to understand but it makes code more difficult to read:

(setf y 11)

(defun add-some (x)
  (+ x y))

(defun add-ten (x)
  (let ((y 10))
    (add-some x)))

In a lexical lisp you see that y in add-some is the global variable y. The result of (add-ten 89) would be 100 since y is 10 in add-some and the local y inside add-ten doesn't do anything.

If it was a dynamic Lisp the answer would be 99 and the body of lambdas can have references to variables that are not in global scope. The result of them becomes magical and hard to predict. Bugs might forget to bind them or multiple functions will override it so the end result is very buggy software.

In Common Lisp you have dynamic variables and to not make errors one uses *earmuffs* to identify them.

In the original Lisp paper John McCarthy uses the same variable x in both the original higher order function maplist and a anonymous function he uses to implement diff. The result is that his example didn't work. We are talking about 6 lines of code and reuse of variables introduces hard to find bugs in a dynamically scoped language.

Making a lexical Lisp from a dynamically scoped one

let with dynamic scope lives until the code is finished execuing inside it and references to the variables in the let is available for all the functions that were called unless they were themselves overridden. You won't get closures so if you want closures in a dynamically scoped lisp you need to make the frames yourself.

Scheme was originally written as an interpreter under a dynamically scoped Lisp (MacLisp). With macros (and perhaps reader-macros) you can make a dynamically bound Lisp work like a lexically bound one (or the other way around), but it won't be as efficient as if it was made lexically bound to begin with.

2
votes

In simple Lisp code it makes not much of a difference. Dynamic binding might be more in the spirit of early Lisp dialects. Lexical binding is more in the spirit of Functional Programming, where we often use higher-order functions in combination with closures.

There are a few situations which speak in favor of lexical binding.

Let's look at dynamic binding and special variables.

free variables get their bindings at runtime

Sylvester has described one problem in his answer: free variables can get their values at runtime via dynamic binding.

CL-USER 27 > (defun foo (x)
               (declare (special x y))
               (+ x y))
FOO

CL-USER 28 > (let ((y 10)) (declare (special y)) (foo 32))
42

CL-USER 29 > (foo 32)

Above can lead to situations which can only debugged at runtime. From the source it is hard to reconstruct which values y will have, since the binding can happen at arbitrary places in the calling chain. Richard Stallman liked that feature - he thought that it was a good choice for an extension language of an editor. Common Lisp uses special variables for many things, for example in its I/O system. For example streams don't need to be passed all the time via parameters.

free variables may not get their bindings at runtime

CL-USER 29 > (foo 32)

Error: The variable Y is unbound.

If we don't define top-level defaults for the free special variables, we can't just call the function...

Not Closures

CL-USER 31 > (let ((x 10)) (declare (special x))
               (lambda (y) (declare (special y x)) (+ y x)))
#<anonymous interpreted function 40600011F4>

Unfortunately this is not a closure.

Note that the variable * holds the last result, here the function above.

CL-USER 32 > (let ((x 22)) (declare (special x)) (mapcar * '(1 2 3)))
(23 24 25)

The function uses the dynamic binding.

CL-USER 33 > (let ((x 10)) (declare (special x)) (lambda (y) (declare (special y x)) (+ y x)))
#<anonymous interpreted function 406000C304>

CL-USER 34 > (mapcar * '(1 2 3))

Error: The variable X is unbound.

Again, it is not a closure and we can't just pass it around...

Summary

We really want a language where we can work with closures by default, where the compiler can warn about unbound variables and where most of the bindings are easy to spot in the source code.