Можете ли вы объяснить эту функцию LISP и почему возникают проблемы с динамическим vs.lexical scoping?

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

Согласно Маккарти, «Трудность была, что, когда произошла внутренняя рекурсии, стоимость автомобиля [х] хотел был внешнее значение, но фактически использовалось внутреннее значение. В современной терминологии было предложено лексическое определение области обзора, и была получена динамическая шкала ».

Я не могу понять, что такое «внешнее значение» и «внутреннее значение», на которое он ссылается, и я не могу увидеть, как эта функция ошибочно работает при оценке с динамическим охватом. Я мог бы понять, если лямбда какая-то, как затененная «х», но она является функцией нулевых аргументов.

(Было довольно сложно найти эту функцию, поскольку она, кажется, отсутствует на самой веб-странице. Только после изучения файла 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 is 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 

Как вы видите, возвращаемые значения ожидаются.

Dynamic Scope

Если мы будем использовать динамическое связывание, то это происходит:

(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 

Dynamic:

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