Помогите понять продолжение в схеме

Я работал вместе с The Little Schemer, чтобы узнать Схему и использовать PLT-Scheme для моей среды.

Маленький Schemer очень помог мне с рекурсией (сейчас это прямо для меня), но я застрял на части книги, которая вводит "коллекционеры" и называет функцию в целом продолжением.

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

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

;; Build a nested list of even numbers by removing the odd ones from its
;; argument and simultaneously multiply the even numbers and sum the odd
;; numbers that occur in its argument.
(define (even-only-collector l col)
  (cond
    ((null? l)
      (col (quote ()) 1 0))
    ((atom? (car l))
      (cond
        ((even? (car l))
          (even-only-collector (cdr l)
            (lambda (newl p s)
              (col (cons (car l) newl)
                (* (car l) p) s))))
         (else
           (even-only-collector (cdr l)
             (lambda (newl p s)
               (col newl
                 p (+ (car l) s)))))))
    (else
      (even-only-collector (car l)
        (lambda (al ap as)
          (even-only-collector (cdr l)
            (lambda (dl dp ds)
              (col (cons al dl)
                (* ap dp)
                (+ as ds)))))))))

;; The collector function
(define (collector newl product sum)
  (cons sum
    (cons product newl)))

Спасибо заранее!

Ответы

Ответ 1

Попробуйте что-то более простое, чтобы увидеть, как это работает. Например, здесь существует версия функции list-sum, которая получает аргумент продолжения (который часто называют k):

(define (list-sum l k)
  (if (null? l)
    ???
    (list-sum (cdr l) ???)))

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

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) ???)))

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

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) k)))

явно неверно - это означает, что k в конечном итоге получит сумму (cdr l) вместо всех l. Вместо этого используйте там новую функцию, которая суммирует первый элемент l вместе со значением, которое он получает:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (sum) (+ (car l) sum)))))

Это становится все ближе, но все еще неправильно. Но хорошо подумать о том, как все работает - мы вызываем list-sum с продолжением, которое сам получит общую сумму и добавит первый элемент, который мы видим сейчас. Недостающая часть очевидна в том, что мы игнорируем k. Нам нужно написать k с помощью этой функции, поэтому мы выполняем ту же операцию суммирования, а затем отправляем результат на k:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (compose k (lambda (s) (+ s (car l)))))))

который, наконец, работает. (Кстати, помните, что каждая из этих функций lambda имеет свою собственную "копию" l.) Вы можете попробовать это с помощью:

(list-sum '(1 2 3 4) (lambda (x) x))

И, наконец, обратите внимание, что это то же самое, что:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (s) (k (+ s (car l)))))))

если вы сделаете состав явным.

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

Ответ 2

Вот один из способов помочь вам "получить более конкретную идею". Представьте, если коллекционер был определен таким образом:

(define (collector l p s)
  (display l)
  (newline)
  (display p)
  (newline)
  (display s)
  (newline))

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

Удачи!