Механизм анонимной функции для вызова себя в Scheme?

Question

Я читаю The Little Schemer и смущаюсь из- за следующего кода:

((lambda (len)
   (lambda (l)
      (cond
         ((null? l) 0)
         (else 
            (+ 1 (len (cdr l)))))))
   eternity)

(define eternity
    (lambda (x)
         (eternity x)))

Код должен определить пустой список, иначе он никогда не останавливается.

Почему " len не рекурсия?

Answer 1

Хотя применение текстовой подстановки к формам Lisp может быть опасным (поскольку существует опасность многократной оценки и т. Д.), В этом случае может оказаться полезным взглянуть на эту форму и увидеть, как она совмещается:

((lambda (len) 
   (lambda (l)
     ...))
 eternity)

это приложение, т. е. вызов функции. Вызываемая функция принимает один аргумент, называемый len и возвращает другую функцию, которая принимает один аргумент l, Вызываемая функция вызывается с eternity, Когда вызов завершается, результатом является эта функция:

(lambda (l)
  (cond
    ((null? l) 0)
    (else (+ 1 (eternity (cdr l))))))

Теперь эта функция принимает список l и если он пуст, возвращает 0, В противном случае он вычисляет (cdr l) (остальная часть списка) и звонки eternity с этим значением. Когда это вернется, 1 добавляется к результату, и это возвращаемое значение всей функции. Проблема, конечно, в том, что eternity

(define eternity
  (lambda (x)
    (eternity x)))

который также может быть записан как

(define (eternity x)
  (eternity x))

просто принимает аргумент x, а затем звонит eternity с x, Это бесконечный цикл. Выше я написал "Когда это вернется", но на самом деле (eternity (cdr l)) никогда не вернется. Так,

((lambda (len)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (+ 1 (len (cdr l)))))))
 eternity)

это вызов функции, который возвращает функцию (lambda (l) …) это возвращает 0 если вызывается с пустым списком и переходит в бесконечный цикл с непустым списком.

С точки зрения анализа программы, стоит отметить, что существуют другие значения, для которых это не войдет в бесконечный цикл. Например, если вы вызываете его со строкой, то (cdr l) будет ошибка.

Answer 2

Как вы говорите, это определение функции длины как частичной функции, которая завершается только для пустого списка. Но это еще не дошло до части y-combinator, это не пример анонимной функции, вызывающей себя.

l список атомов, это аргумент функции, возвращаемый при (lambda (len) ...) оценивается.

len является функцией, переданной во внешнюю лямбду в качестве аргумента

Внешнее выражение создает лямбду с eternity передал в качестве аргумента. Внешняя лямбда возвращает функцию, созданную путем вычисления внутренней лямбды, возвращаемая функция - это то, что принимает eternity в качестве аргумента.

Если коду передан пустой список (то есть обернуть всю первую часть, а затем '() в другом наборе паренов) тогда оно будет оцениваться до 0, конечно. len никогда не оценивается.

Если код передан непустым латом, он попытается оценить len аргумент, и вы получите бесконечную рекурсию.