Multiple variables of one name or multiple bindings of one variable in Lisp

Question

I am confused/unsure about how the term variable or binding is used. I think my unsureness can be boiled down to three related simple questions.

(let ((hi 'outer))
  (let ((hi 'inner))
    (print hi))
  (print hi))

Question A: In above code, which of the following is right?

1. There is only one variable. There are two bindings of one variable: an outer binding, and an inner binding.

2. There are two variables of one name: an outer variable, and an inner variable.

When I read about local variables on the Internet, sometimes the articles seem to choose 1, and sometimes 2. Are the two equally right?

(let ((hi 0))
  (print hi)
  (setq hi 1)
  (print hi)
  (setq hi 2)
  (print hi))

Question B: which of the following is right for the above code?

1. There is one binding that is being reused.

2. There are three bindings.

I have never seen any material that uses the word binding in a way that would choose 2 as answer, but on the other hand, one might still think "the name hi is bound three times. Three bindings happened. The code does three bindings." So I am not sure.

(defun fac (n)
  (if (> n 1)
      (* n (fac (1- n)))
    1))
(fac 4)

Question C: when the recursive function is being executed, which is right?

1. There will be several bindings of one variable at the same time.

2. There will be several variables of one name at the same time.

This might seem similar to Question A, but question A involves two let forms, each of which is executed just once, while this question is more like one let form that is being executed in several instances at the same time.

Are these questions like angles on the head of a pin? I am wondering about these questions because there are many articles on that famous gotcha about using closures within a loop, and I think understanding those articles require knowing what one variable is and what one binding is.

Answer 1

According to the Common Lisp glossary: (other Lisps may or may not differ in terminology)

• variable: a binding in the ``variable'' namespace.
• binding: an association between a name and that which the name denotes.
• assign: to change the value of the variable in a binding that has already been established.

So the answers would be:

• A: two variables (and two bindings)
• B: one binding (being assigned two times)
• C: several bindings (and several variables) of one name

Answer 2

I think that Lars Brinkhoff's answer answers this most directly by appealing to the HyperSpec. You also might have a look at Chapter 6. Variables in Peter Seibel's Practical Common Lisp.

However, let's also consider what could we do to test this? One of the advantages of languages with lexical scoping and lexical closures is that the same binding can be shared between closures.

One binding referenced by multiple closures

For instance, we can bind a single variable x (there's no question that there's only one x here) and return two closures that access it:

(defun incrementer-and-getter (value)
  (let ((x value))
    (values (lambda ()
              (setq x (+ 1 x)))
            (lambda () 
              x))))

Then, we can see that they refer to the same binding when we use the closures:

(multiple-value-bind (inc get) 
    (incrementer-and-getter 23)
  (list (funcall get)
        (funcall inc)
        (funcall get)))
; => (23 24 24)

Multiple bindings with nested lets

Now we can do something similar to test how many bindings there are in the cases that you gave:

(defun test2 ()
  (let (get-outer
        set-outer
        get-inner
        set-inner)
    (let ((hi 'outer))
      (setq get-outer (lambda () hi)
            set-outer (lambda (new) (setq hi new)))
      (let ((hi 'inner))
        (setq get-inner (lambda () hi)
              set-inner (lambda (new) (setq hi new)))))
    (values get-outer
            set-outer
            get-inner
            set-inner)))

(multiple-value-bind (get-outer set-outer get-inner set-inner)
    (test2)
  (list (funcall get-outer)             ; retrieve outer
        (funcall get-inner)             ; retrieve inner
        (funcall set-outer 'new-outer)  ; update outer
        (funcall set-inner 'new-inner)  ; update inner
        (funcall get-outer)             ; retrieve outer
        (funcall get-inner)))           ; retrieve inner
; => (OUTER INNER NEW-OUTER NEW-INNER NEW-OUTER NEW-INNER)

The inner and outer bindings are different.

A single binding updated with setq

Now for the multiple setq case:

(defun test3 ()
  (let (get-first
        set-first
        get-second
        set-second)
    (let ((hi 'first))
      (setq get-first (lambda () hi)
            set-first (lambda (new) (setq hi new)))
      (setq hi 'second)
      (setq get-second (lambda () hi)
            set-second (lambda (new) (setq hi new))))
    (values get-first
            set-first
            get-second
            set-second)))
(multiple-value-bind (get-first set-first get-second set-second)
    (test3)
  (list (funcall get-first)
        (funcall get-second)
        (funcall set-first 'new-first)
        (funcall get-first)
        (funcall get-second)
        (funcall set-second 'new-second)
        (funcall get-first)
        (funcall get-second)))
    (multiple-value-bind (get-first set-first get-second set-second)
        (test3)
      (list (funcall get-first)
            (funcall get-second)
            (funcall set-first 'new-first)
            (funcall set-second 'new-second)
            (funcall get-first)
            (funcall get-second)))
; => (SECOND SECOND NEW-FIRST NEW-FIRST NEW-FIRST NEW-SECOND NEW-SECOND NEW-SECOND)

Here, both get-first and get-second return the same value, and both set-first and set-second update that value. The closures close over the same binding.

Each call to a function establishes new bindings

For the recursive case, we have to be a bit sneakier, but we can still check this:

(defparameter *closures* '())

(defun recurse (n)
  (push (lambda () n) *closures*)
  (push (lambda (new) (setq n new)) *closures*)
  (unless (zerop n)
    (recurse (1- n))))

(recurse 1) ; put four closures into *closures*

Now we can take those back out and see what happens:

;; remember we pushed these in, so they're in backwards
;; order, compared to everything else we've done.
(destructuring-bind (set-y get-y set-x get-x)
    *closures*
  (list (funcall get-x)
        (funcall get-y)
        (funcall set-x 'new-x)
        (funcall set-y 'new-y)
        (funcall get-x)
        (funcall get-y)))
; => (1 0 NEW-X NEW-Y NEW-X NEW-Y)

There is a new binding for each invocation of the function, so the closures reference different bindings.

Common confusions in iteration constructs

For what it's worth, it's not too hard to get used to this behavior (if it's at all surprising in the first place). However, even seasoned Lisp veterans can get tripped up on the behavior in iteration constructs. These kind of cases suddenly make it very important to know whether, e.g., do establishes a new binding for each iteration, or whether it updates the same binding. What should the following code print, 10987654321 or 0000000000?

(let ((closures '()))
  (do ((x 10 (1- x)))
      ((zerop x))
    (push (lambda () x) closures))
  (map nil (lambda (closure)
             (print (funcall closure)))
       closures))

In the case of do, it's 0000000000, because (emphasis added):

All the step-forms, if supplied, are evaluated, from left to right, and the resulting values are assigned to the respective vars.

This comes up a lot in loop where it's implementation dependent, but people expect different behavior from other iteration macros, too. See, for instance, this StackOverflow question:

• Unexpected behavior with loop macro and closures

or these threads on comp.lang.lisp:

• I like(d) loop, but .. (about loop)
• something very strange (to me). Please help! (about do)