How to Explain Lexical vs Dynamic Binding?

Question

I read a relevant post on binding, however still have questions.

Here are the following examples I found. Can someone tell me if the conclusions are correct?

Dynamic Binding of x in (i):

(defun j ()
 (let ((x 1))
    (i)))

(defun i ()
   (+ x x))

> (j)
2

Lexical Binding of x in i2:

(defun i2 (x)
       (+ x x))

(defun k ()
   (let ((x 1))
       (i2 2)))

> (k)
4

No Global Lexical Variables in ANSI CL so Dynamic Binding is performed:

(setq x 3)

(defun z () x)

> (let ((x 4)) (z))
4

Dynamic Binding, which appears to bind to a lexically scoped variable:

(defvar x 1)
(defun f (x) (g 2))
(defun g (y) (+ x y))
> (f 5)
7

Based on the above tests, CL first tries lexical binding. If there is no lexical match in the environment, then CL tries dynamic binding. It appears that any previously lexically scoped variables become available to dynamic binding. Is this correct? If not, what is the behavior?

Answer 1

(defun j ()
 (let ((x 1))
    (i)))

(defun i ()
   (+ x x))

> (j)
2

This is actually undefined behavior in Common Lisp. The exact consequences of using undefined variables (here in function i) is not defined in the standard.

CL-USER 75 > (defun j ()
               (let ((x 1))
                 (i)))
J

CL-USER 76 > (defun i ()
               (+ x x))
I

CL-USER 77 > (j)

Error: The variable X is unbound.
  1 (continue) Try evaluating X again.
  2 Return the value of :X instead.
  3 Specify a value to use this time instead of evaluating X.
  4 Specify a value to set X to.
  5 (abort) Return to top loop level 0.

Type :b for backtrace or :c <option number> to proceed.
Type :bug-form "<subject>" for a bug report template or :? for other options.

CL-USER 78 : 1 > 

As you see, the Lisp interpreter (!) complains at runtime.

Now:

(setq x 3)

SETQ sets an undefined variable. That's also not fully defined in the standard. Most compilers will complain:

LispWorks

;;;*** Warning in (TOP-LEVEL-FORM 1): X assumed special in SETQ
; (TOP-LEVEL-FORM 1)
;; Processing Cross Reference Information
;;; Compilation finished with 1 warning, 0 errors, 0 notes.

or SBCL

; in: SETQ X
;     (SETQ X 1)
; 
; caught WARNING:
;   undefined variable: COMMON-LISP-USER::X
; 
; compilation unit finished
;   Undefined variable:
;     X
;   caught 1 WARNING condition


(defvar x 1)
(defun f (x) (g 2))
(defun g (y) (+ x y))
> (f 5)
7

Dynamic Binding, which appears to bind to a lexically scoped variable

No, x is globally defined to be special by DEFVAR. Thus f creates a dynamic binding for x and the value of x in the function g is looked up in the dynamic environment.

Basic rules for the developer

• never use undefined variables
• when using special variables always put * around them, so that it is always visible when using them, that dynamic binding&lookup is being used. This also makes sure that one does NOT declare variables by accident globally as special. One (defvar x 42) and x will from then on always be a special variable using dynamic binding. This is usually not what is wanted and it may lead to hard to debug errors.

Answer 2

In summary: no, CL never 'tries one kind of binding then another': rather it establishes what kind of binding is in effect, at compile time, and refers to that. Further, variable bindings and references are always lexical unless there is a special declaration in effect, in which case they are dynamic. The only time when it is not lexically apparent whether there is a special declaration in effect is for global special declarations, usually performed via defvar / defparameter, which may not be visible (for instance they could be in other source files).

There are two good reasons it decides about binding like this:

• firstly it means that a human reading the code can (except possibly in the case of a global special declaration which is not visible) know what sort of binding is in use – getting a surprise about whether a variable reference is to a dynamic or lexical binding of that variable is seldom a pleasant experience;
• secondly it means that good compilation is possible – unless the compiler can know what a variable's binding type is, it can never compile good code for references to that variable, and this is particularly the case for lexical bindings with definite extent where variable references can often be compiled entirely away.

An important aside: always use a visually-distinct way of writing variables which have global special declarations. So never say anything like (defvar x ...): the language does not forbid this but it's just catastrophically misleading when reading code, as this is the exact case where a special declaration is often not visible to the person reading the code. Further, use *...* for global specials like the global specials defined by the language and like everyone else does. I often use %...% for nonglobal specials but there is no best practice for this that I know of. It's fine (and there are plenty of examples defined by the language) to use unadorned names for constants since these may not be bound.

The detailed examples and answers below assume:

• Common Lisp (not any other Lisp);
• that the code quoted is all the code, so there are no additional declarations or anything like that.

Here is an example where there is a global special declaration in effect:

;;; Declare *X* globally special, but establish no top-level binding
;;; for it
;;;
(defvar *x*)

(defun foo ()
  ;; FOO refers to the dynamic binding of *X*
  *x*)

;;; Call FOO with no binding for *X*: this will signal an
;;; UNBOUND-VARIABLE error, which we catch and report
;;;
(handler-case
    (foo)
  (unbound-variable (u)
    (format *error-output* "~&~S unbound in FOO~%"
            (cell-error-name u))))

(defun bar (x)
  ;; X is lexical in BAR
  (let ((*x* x))
    ;; *X* is special, so calling FOO will now be OK
    (foo)))

;;; This call will therefore return 3
;;;
(bar 3)

Here is an example where there are nonglobal special declarations.

(defun foo (x)
  ;; X is lexical
  (let ((%y% x))
    (declare (special %y%))
    ;; The binding of %Y% here is special.  This means that the
    ;; compiler can't know if it is referenced so there will be no
    ;; compiler message even though it is unreferenced in FOO.
    (bar)))

(defun bar ()
  (let ((%y% 1))
    ;; There is no special declaration in effect here for %Y%, so this
    ;; binding of %Y% is lexical.  Therefore it is also unused, and
    ;; tere will likely be a compiler message about this.
    (fog)))

(defun fog ()
  ;; FOG refers to the dynamic binding of %Y%.  Therefore there is no
  ;; compiler message even though there is no apparent binding of it
  ;; at compile time nor gobal special declaration.
  (declare (special %y%))
  %y%)

;;; This returns 3
;;;
(foo 3)

Note that in this example it is always lexically apparent what binding should be in effect for %y%: just looking at the functions on their own tells you what you need to know.

---

Now here are come comments on your sample code fragments.

(defun j ()
 (let ((x 1))
   (i)))

(defun i ()
  (+ x x))

> (j)
<error>

This is illegal in CL: x is not bound in i and so a call to i should signal an error (specifically an unbound-variable error).

(defun i2 (x)
  (+ x x))

(defun k ()
  (let ((x 1))
    (i2 2)))

> (k)
4

This is fine: i2 binds x lexically, so the binding established by k is never used. You will likely get a compiler warning about unused variables in k but this is implementation-dependent of course.

(setq x 3)

(defun z () x)

> (let ((x 4)) (z))
<undefined>

This is undefined behaviour in CL: setq's portable behaviour is to mutate an existing binding but not to create a new bindings. You are trying to use it to do the latter, which is undefined behaviour. Many implementations allow setq to be used like this at top-level and they may either create what is essentially a global lexical, a global special, or do some other thing. While this is often done in practice when interacting with a given implementation's top level, that does not make it defined behaviour in the language: programs should never do this. My own implementation squirts white-hot jets of lead from hidden nozzles in the general direction of the programmer when you do this.

(defvar x 1)
(defun f (x) (g 2))
(defun g (y) (+ x y))
> (f 5)
7

This is legal. Here:

• defvar declares x globally special, so all bindings of x will be dynamic, and establishes a top-level binding of x to 1;
• in f the binding of its argument, x will therefore be dynamic, not lexical (without the preceding defvar it would be lexical);
• in g the free reference to x will be to its dynamic binding (without the preceding defvar it would be a compile-time warning (implementation-dependent) and a run-time error (not implementation-dependent).