你能解释一下这个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',但它是零参数的函数.

(实际上很难找到这个功能,因为它似乎从网页本身中遗漏了.只是在浏览了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是真实的.

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