您能解释一下这个 LISP 函数以及为什么动态 vs.lexical 范围会出现问题吗？

Question

在此处 From LISP 1 to LISP 1.5 阅读一些 lisp 历史时，我遇到了这个函数：

(define (testr x p f u)
  (if (p x)
      (f x)
      (if (atom? x)
          (u)
          (testr (cdr x)
                 p
                 f
                 (lambda ()
                   (testr (car x) p f u))))))

根据麦卡锡的说法，"The difficulty was that when an inner recursion occurred, the value of car[x] wanted was the outer value, but the inner value was actually used. In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained."

我不太明白他指的 "outer value" 和 "inner value" 是什么，我也看不出这个函数在使用动态范围评估时有何异常行为。我可以理解 lambda 是否有阴影 'x' 但它是零参数的函数。

（实际上很难找到这个函数，因为它似乎在网页本身中缺失。只有在浏览 images.tex 文件后：http://www-formal.stanford.edu/jmc/history/lisp/images.tex 我才找到它） .

Answer 1

让我们用 Lisp 来做吧，这里是 Common Lisp。在 Common Lisp 中，很容易在动态绑定和词法绑定之间切换。

词法作用域

这个例子使用词法绑定。

(defun testr (x p f u)
  (if (funcall p x)
      (funcall f x)
      (if (atom x)
          (funcall u)
          (testr (cdr x)
                 p
                 f
                 (lambda ()
                   (testr (car x) p f u))))))

函数应该做什么？它应该在 P 为 true.

的嵌套列表中找到最右边的元素

CL-USER 36 > (testr '(1 (2 3) 3 (7 6 6))
                    (lambda (y) (and (numberp y) (oddp y)))
                    #'identity
                    nil)
7

CL-USER 37 > (testr '(1 (2 3) 3 (6 6 6))
                    (lambda (y) (and (numberp y) (oddp y)))
                    #'identity
                    nil)
3

如您所见，返回值符合预期。

动态范围

如果我们使用动态绑定，那么会发生这种情况：

(defun testr (x p f u)
  (declare (special x p f u))       ; use dynamic binding
  (if (funcall p x)
      (funcall f x)
      (if (atom x)
          (funcall u)
          (testr (cdr x)
                 p
                 f
                 (lambda ()
                   (testr (car x) p f u))))))

CL-USER 38 > (testr '(1 (2 3) 3 (6 6 6))
                    (lambda (y) (and (numberp y) (oddp y)))
                    #'identity
                    nil)

Stack overflow (stack size 15998).

如果我们像 car 一样定义 ecar，但当项目不是 cons 时发出错误信号：

(defun ecar (item)
  (if (consp item)
      (car item)
    (error "Item ~a not a cons" item)))

(defun testr (x p f u)
  (declare (special x p f u))
  (if (funcall p x)
      (funcall f x)
      (if (atom x)
          (funcall u)
          (testr (cdr x)
                 p
                 f
                 (lambda ()
                   (testr (ecar x) p f u))))))

CL-USER 52 > (testr '(1 2)
                    (lambda (y)
                      (and (numberp y) (oddp y)))
                    #'identity
                    nil)

Error: Item NIL not a cons

在列表的末尾，x 是 nil 而不是 cons，因此 (ecar x) 表示错误。

问题

(defun testr (x p f u)
  (declare (special x p f u))       ; use dynamic binding
  (if (funcall p x)
      (funcall f x)
      (if (atom x)
          (funcall u)      ; INNER: here the lambda function is called
                           ; with dynamic binding, the value of X
                           ; is the current binding of X from
                           ; the current call.
                           : at the end of a list, X would be NIL.
                           ; Inside the lambda function then X would be NIL, too.
                           ; (car x)  -> returns NIL
                           ; then we are in an endless recursion



                           ; OUTER: with lexical binding, the value
                           ; of X would be the value of some
                           ; binding where the function was
                           ; defined and called earlier.
          (testr (cdr x)              
                 p
                 f
                 (lambda ()            ; our lambda function
                   (testr (car x)      ; the reference to X
                          p f u))))))

简单追踪

让我们看看它是如何访问元素的：

词汇：

CL-USER 42 > (testr '(1 (2 3) 4 (6 8 10))
                    (lambda (y)
                      (print (list :test y))
                      (and (numberp y) (oddp y)))
                    #'identity
                    nil)

(:TEST (1 (2 3) 4 (6 8 10))) 
(:TEST ((2 3) 4 (6 8 10))) 
(:TEST (4 (6 8 10))) 
(:TEST ((6 8 10))) 
(:TEST NIL)             ; it has reached the end of the top list
(:TEST (6 8 10))        ; it recurses down the rightmost sublist
(:TEST (8 10)) 
(:TEST (10)) 
(:TEST NIL)             ; end of the rightmost sublist
(:TEST 10)              ; checks the elements of the rightmost sublist           
(:TEST 8) 
(:TEST 6) 
(:TEST 4)               ; back up, next element of the top list
(:TEST (2 3))           ; next sublist of the top list
(:TEST (3))            
(:TEST NIL)             ; end of that sublist
(:TEST 3)               ; checks right element, found
3

动态：

CL-USER 40 > (testr '(1 (2 3) 4 (6 8 10))
                    (lambda (y)
                      (print (list :test y))
                      (and (numberp y) (oddp y)))
                    #'identity
                    nil)

(:TEST (1 (2 3) 4 (6 8 10))) 
(:TEST ((2 3) 4 (6 8 10))) 
(:TEST (4 (6 8 10))) 
(:TEST ((6 8 10)))      
(:TEST NIL)            ; it reaches the end of the top list
(:TEST NIL)            ; it goes into the endless recursion
(:TEST NIL) 
(:TEST NIL) 
(:TEST NIL) 
(:TEST NIL) 
...

您能解释一下这个 LISP 函数以及为什么动态 vs.lexical 范围会出现问题吗？

Can you explain this LISP function and why issues arise with dynamic vs.lexical scoping?

lisp

scoping

dynamic-scope

lexical-scope