Little Schemer: зачем заключать (mk-length в mk-length) в функцию?

Question

В книге "Маленький интриган", в главе 9, при создании length Для произвольного длинного ввода предлагается следующее (на страницах 170-171), что приведено в следующем фрагменте кода (на самой странице 168):

((lambda (mk-length)
   (mk-length mk-length))                      
 (lambda (mk-length)
   ((lambda (length)                           
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l)))))))   
    (mk-length mk-length))))                   

часть (mk-length mk-length), никогда не вернется и будет бесконечно применять себя к себе:

Потому что мы просто продолжаем применять mk-length себе снова и снова и снова...

а также

Но теперь, когда мы извлекли (mk-length mk-length) от функции, которая делает length он больше не возвращает функцию.

Теперь, чтобы вылечить это, книга предлагает:

Включите приложение mk-length к себе в нашей последней правильной версии length в функцию.

Вот так:

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   ((lambda (length)
     (lambda (l)
       (cond
         ((null? l) 0 )
         (else 
           (add1 (length (cdr l)))))))
   (lambda (x)
     ((mk-length mk-length) x)))))

Я озадачен тем, что:

1. Если (mk-length mk-length)

   не возвращает функцию

   как мы можем применить результат (mk-length mk-length) что-то, как будто это функция?

   (lambda (x)
     ((mk-length mk-length) x))
   

2. Как упаковка (mk-length mk-length) в функцию решает проблему "никогда не возвращаться" (т. е. бесконечной рекурсии)? Я понимаю, что в:

   (lambda (x)
     ((mk-length mk-length) x))
   

x будет просто передан бесконечно рекурсивной функции, которая никогда не вернется.

Answer 1

Вы, вероятно, скопировали неправильный фрагмент кода, предшествующий тому, о котором вы на самом деле говорите. Первый код, который вы показали, полностью в порядке. Что петли, скорее, это:

   ((lambda (mk-length)
      (mk-length mk-length))                      ; (1)
    (lambda (mk-length)
      ((lambda (length)                           ; (2)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))    ; (4)
       (mk-length mk-length))))                   ; (3)

Это уже здесь ответили: приложение (1) запускает приложение (2) который запускает приложение (3) сразу, что эквивалентно (1)! Итак, зацикливание.

Оборачивание в лямбду (ata eta-extension) задерживает приложение (3) до вызова к построенному length сделано в (4)и это вполне нормально (вы также скопировали это с некоторыми опечатками):

   ((lambda (mk-length)
      (mk-length mk-length))                      ; (1)
    (lambda (mk-length)                                   ; (5)
      ((lambda (length)                           ; (2)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))    ; (4)
       (lambda (x)                                ; (3)
         (mk-length mk-length) x))))

(3) является лямбда-выражением сейчас, а не приложением. Оценка этого лямбда-выражения производит анонимную функцию. Эта лямбда-функция будет выполнять приложение (mk-length mk-length) позже, когда length называется.

(более длинное объяснение:) (3) просто сразу возвращает лямбда-функцию, которая привязывается к length, а также (lambda (l) ...) счастливо возвращается так, что когда это (lambda (l) ...) будет применен к некоторому списку, возможно, вызывая это length¹ будет вызван (4)только тогда приложение (mk-length mk-length) внутри лямбды (3) будет фактически выполнен - ​​давая нам новый (lambda (l) ...) в конечном итоге анонимная функция, которая будет применяться к (cdr l) там.

¹length является (lambda (x) ((mk-length mk-length) x)) Который означает, что (length (cdr l)) такой же как ((mk-length mk-length) (cdr l)) (с mk-length привязан ко всему лямбда-выражению (5)) и, в конце концов, ((lambda (l) ...) (cdr l)),

Нина

Answer 2

Этот звонок

(mk-length mk-length)

позвоню mk-length только однажды.

Если mk-length случается так называть себя, тогда тело mk-length будет оцениваться снова - но mk-length не всегда называет себя

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

Пример показывает, что, хотя используются только анонимные функции, можно писать рекурсивные функции. Вместо того, чтобы называть функцию напрямую (используя define), функция передается в качестве аргумента другой функции - и эта функция имеет имена для своих аргументов.