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

Question

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

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

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

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

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

Заранее спасибо !!

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

если вы сделаете композицию явной.

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

Answer 2

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

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

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

Удачи!