您能否解释一下这个 LISP 函数，以及为什么动态与词法范围会出现问题

Question

在这里阅读一些Lisp历史时 从 LISP 1 到 LISP 1.5，我遇到了这个函数：

(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))))))

根据麦卡锡的说法，"困难在于，当发生内部递归时，car[x]想要的值是外部值，但实际上使用了内部值。在现代术语中，需要词汇范围界定，并获得动态范围界定。

我不太清楚他指的是什么"外部价值"和"内部价值"，也看不出这个函数在使用动态范围评估时是如何行为不端的。我可以理解 lambda 是否有些阴影"x"，但它是零参数的函数。

（实际上很难找到此功能，因为它似乎在网页本身中缺失。只有在浏览了图像.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为真。

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).

如果我们定义ecar像 car ，但是在项目不是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，这不是缺点，因此(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) 
...