lisp - 您能解释一下这个 LISP 函数以及为什么动态与词法范围界定会出现问题吗？

Question

在这里阅读一些 lisp 历史 From LISP 1 to 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))))))

按照 McCarthy 的说法，“困难在于当发生内部递归时，想要的 car[x] 的值是外部值，但实际使用的是内部值。在现代术语中，需要词法作用域，并且动态范围界定已获得。”

我不太明白他指的是什么“外在值(value)”和“内在值(value)”，也看不出这个函数在使用动态范围评估时如何表现不佳。我能理解 lambda 是否有一些阴影 'x' 但它是零参数的函数。

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

Answer 1

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

词法作用域

这个例子使用词法绑定(bind)。

(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

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

动态作用域

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

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