Dynamic Binding in Common Lisp

2
votes

This question is an extension of Common Lisp scoping (dynamic vs lexical)

I have read and (hopefully) understood the concepts of scoping and extent in Common Lisp (link: https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node43.html), but I am unable to get my head around the following three examples. All examples are run on a fresh lisp session in SBCL/Slime/Emacs.

Example 1: Prints 5 & 5

(defvar x 100)
(defun fun1 (x)
   (print x)
   (fun2))

(defun fun2 ()
   (print x))
     
(fun1 5)

Example 2: Prints 5 & 100

 (defun fun1 (x)
   (print x)
   (fun2))

 (defun fun2 ()
   (print x))
    
 (defvar x 100)
 
 (fun1 5)

Example 3: Prints 5 & 5 & 100

(defvar x 100)

(defun fun1 (x)
  (print x)
  (fun2))

(defun fun2 ()
  (print x))

(defvar x 100)
     
(fun1 5)

x

I understand why fun1 always prints 5 (due to lexical scope, but please correct if I'm wrong). What I don't understand is why fun2 prints 5 in Example 1, 100 in Example 2 and again 5 in Example 3?

  • Example 1: x, a variable with indefinite scope, is set to 5 in fun1 and accordingly fun2 access this value. Is this a correct interpretation?
  • Example 2: x is set to 100 by defvar, but why is not being re-set to 5 when fun1 is called? I thought the bindings took place when the functions are called or is it when they are defined? It appears that x is not yet bound when fun1 is defined, and therefore the binding of x in fun1 (which is lexically scoped) is not seen by the rest of the program and then the "global" binding takes place with the subsequent defvar. Is the behaviour x in the function call then due to lexical shadowing in fun1 but no dynamic shadowing for fun2? I.e. there are two different instances of x here since fun1 defined its x first and did not see a "global" x at the time.
  • Example 3: It appears here that since x is set globally first, both fun1 and fun2 are referencing the same instance of x and hence its value is updated during fun1 and applied also during fun2 (both are 5)? Furthermore I get 100 when I ask for the value of x at the end (why? when fun2 is returning 5?)

It has something to do with the following extract from Guy Steel's Common Lisp book, but I cannot get my head around it:

"Constructs that use lexical scope effectively generate a new name for each established entity on each execution. Therefore dynamic shadowing cannot occur (though lexical shadowing may). This is of particular importance when dynamic extent is involved."

Is the following statement always true (source: https://courses.engr.illinois.edu/cs421/sp2010/lectures/dynamicscope.pdf):

The binding rule in Lisp is this: a use of a name is bound to the most recent declaration of that name that is still live.

I'm starting to understand some of the parts, but cannot get a wholistic understanding of all three parts, so it would be very helpful if you could help.

3
lispcommon-lisp
Notice that 'returns' is probably the wrong word. You mean 'prints'. 'returning' means in the functional paradigm the return value of an expression. – Rainer Joswig
Many thanks Rainer, I have updated this – Ashok Khanna
I think it's really important to note that Example 2's behaviour is undefined in CL: a reference to a free variable from a function where there is both no apparent special declaration nor any visible lexical binding of that variable at the time the function is defined is undefined behaviour. Rainer Joswig's answer points this out explicitly. – user5920214
@tfb Thanks, you are very correct. His and Sylwester's answer touch upon this quite well. That said, the answer I accepted helped me the most in understanding the concepts as it stepped through a bit more slowly through the ideas of scope and extent. Ideally, we should add the notes you just mentioned to the accepted answer, but I am very much a beginner on Stack Overflow, so not sure what is the correct way and etiquette – Ashok Khanna
@AshokKhanna: I think the accepted answer is fine, and since Rainer's answer (which won't go away, unlike comments) mentions it everything is fine. I just wanted to be sure that you hadn't missed the slightly subtle issue, really. – user5920214

3 Answers

5
votes

Some annotations to your code:

Example 1

(defvar x 100)    ; declares X to be special, globally and locally
                  ; also sets X to 100

(defun fun1 (x)   ; X is a dynamically bound variable
  (print x)       ; lookup of dynamic binding of X
  (fun2))        

(defun fun2 ()
  (print x))      ; lookup of dynamic binding of X
     
(fun1 5)

Example 2

 (defun fun1 (x)  ; X is a lexical local variable
   (print x)      ; lexical reference to X
   (fun2))

 (defun fun2 ()
   (print x))     ; X is undeclared/undefined
                  ; the exact behaviour is undefined in Common Lisp
                  ; many implementations assume dynamic lookup of X
                  ; most compilers will show a warning
                  ; CMUCL also by default declared X globally to be special
                  ; -> don't use this in your code
    
 (defvar x 100)   ; declares X to be special, globally and locally 
                  ; also sets X to 100     
 (fun1 5)

Example 3

(defvar x 100)    ; declares X to be special, globally and locally
                  ; also sets X to 100

(defun fun1 (x)   ; X is a dynamically bound variable
  (print x)       ; lookup of dynamic binding of X
  (fun2))

(defun fun2 ()
  (print x))      ; lookup of dynamic binding of X

(defvar x 100)    ; does nothing
                  ;  -> X is already declared special
                  ;  -> X already has a value
                  ;     see also: DEFPARAMETER
     
(fun1 5)

x                 ; lookup of global (or thread local) value of X
4
votes

Example 1: x, a variable with indefinite scope, is set to 5 in fun1 and accordingly fun2 access this value. Is this a correct interpretation?

Mostly, let me expand on that.

When x is declared by defvar, the variable is being declared as special, and from now on x is always seen as a special variable, and bound dynamically. When you call:

(fun1 5)

The binding in fun1 is done dynamically, meaning both the return value of fun1 and fun2 are based on the current dynamic binding of x.

Example 2: [...] I.e. there are two different instances of x here since fun1 defined its x first and did not see a "global" x at the time.

Yes, but this is not true in all interpreters (see Sylwester's answer). When you define fun1, x is not known to be special; that means the scope at this point for parameter x is lexical. Later, when defvar is evaluated, the binding of x in fun1 is still lexical, and as such calling fun1 does not modify the dynamic binding of global variable x.

Example 3: [...] Furthermore I get 100 when I ask for the value of x at the end (why? when fun2 is returning 5?

Special variable have indefinite scope, they are visible everywhere, but their bindings has dynamic extent, which means a binding lives only as long as the form that establishes it.

Here, when you ask for x at the toplevel, you have the value that is globally bound to x, 100; the value of 5 is only temporarily bound to x while the call to fun1 is in effect.

If you used SETF to mutate a binding, then you could mutate the global binding, but this is not what happens during function application or let bindings.

3
votes

Your trick works differently in different implementations. Eg. in CLISP, which doesn't compile their functions on the fly, will behave the exact same in the two first examples and exactly the same as your output if you compile the functions as you go.

Dynamic scope means lexical scope doesn't apply:

(defparameter *test* 100)

(defun print-test ()
  (print *test*))

(defun call-print-test-with (*test*)
  (print-test))

(print-test)         ; prints 100
(call-print-test 10) ; prints 10

Because *test* is dynamic (global) changing a local variable with the same name temporarily overwrites it until the scope that overwrites it is gone. This is what dynamic means.

If *test* was lexically scoped both would print 100.

This is why you should always use *earmuffs* on globals. If you have defined a variable somewhere with defvar or defparameter using the same as a parameter or local variable somewhere you might change the variable temporarily without knowing and it might be very hard to find where it happens! When people see *earmuffs* in parameters and let they understand this is the intent. eg.

(with-output-to-string (*standard-output*)
  (some-function-whose-printed-output-you-want))
; ==> a string with the actual output

The function which is called is non the wiser. It thinks it is printing to stdout but you have wrapped it and changed the output stream during its execution.