2

在从 LISP 1 到 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))))))

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

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

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

4

1 回答 1

5

让我们用 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).

如果我们定义ecarlike car，但在项目不是 a 时发出错误信号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

在列表的末尾，xisnil和 that 不是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) 
...
于 2017-01-11T09:20:35.403 回答