Схема продолжения - нужно пояснение - PullRequest
3 голосов
/ 14 декабря 2011

Следующий пример включает в себя переход в продолжение и выход. Может кто-нибудь объяснить поток функции. Я двигаюсь по кругу вокруг продолжения и не знаю точек входа и выхода функции.

(define (prod-iterator lst)
  (letrec ((return-result empty)
        (resume-visit (lambda (dummy) (process-list lst 1)))
        (process-list
         (lambda (lst p)
           (if (empty? lst)
               (begin
                 (set! resume-visit (lambda (dummy) 0))
                 (return-result p))
               (if (= 0 (first lst))
                   (begin
                     (call/cc ; Want to continue here after delivering result     
                      (lambda (k)
                        (set! resume-visit k)
                        (return-result p)))
                     (process-list (rest lst) 1))
                   (process-list (rest lst) (* p (first lst))))))))
    (lambda ()
      (call/cc
       (lambda (k)
         (set! return-result k)
         (resume-visit 'dummy))))))

(define iter (prod-iterator '(1 2 3 0 4 5 6 0 7 0 0 8 9)))
(iter) ; 6                                                                        
(iter) ; 120                                                                      
(iter) ; 7                                                                        
(iter) ; 1                                                                        
(iter) ; 72                                                                       
(iter) ; 0                                                                        
(iter) ; 0

Спасибо.

Ответы [ 3 ]

4 голосов
/ 14 декабря 2011

Процедура перебирает список, умножая ненулевые элементы и возвращая результат каждый раз, когда обнаруживается ноль. Resume-visit хранит продолжение для обработки остальной части списка, а return-result имеет продолжение call-сайта итератора. В начале, resume-visit определяется для обработки всего списка. Каждый раз, когда обнаруживается ноль, захватывается продолжение, которое при вызове выполняет (process-list (rest lst) 1) для любого значения lst, которое было в то время. Когда список исчерпан, resume-visit становится фиктивной процедурой. Более того, каждый раз, когда программа вызывает iter, она выполняет следующее:

(call/cc
   (lambda (k)
     (set! return-result k)
     (resume-visit 'dummy)))

То есть он фиксирует продолжение вызывающей стороны, вызывая его, возвращая вызывающей стороне значение. Продолжение сохраняется, и программа переходит к обработке остальной части списка. Когда процедура вызывает resume-visit, цикл вводится, когда вызывается return-result, цикл завершается.

Если мы хотим рассмотреть process-list более подробно, давайте предположим, что список не пуст. То процедура использует базовую рекурсию, накапливая результат, пока не будет найден ноль. В этот момент p - это накопленное значение, а lst - список, содержащий ноль. Когда у нас есть конструкция, подобная (begin (call/cc (lambda (k) first)) rest), мы сначала выполняем first выражений с k, привязанными к продолжению. Это процедура, которая при вызове выполняет rest выражений. В этом случае это продолжение сохраняется и вызывается другое продолжение, которое возвращает накопленный результат p вызывающей стороне iter. Это продолжение будет вызвано при следующем вызове iter, затем цикл продолжится с остальной частью списка. В этом суть продолжения, все остальное - базовая рекурсия.

1 голос
/ 03 января 2012

Вы можете добиться того же:

(define (prod-iter lst) (fold * 1 (remove zero? lst)))

... хотя он мог бы работать лучше, пройдя только один раз.

Для продолжения напомните (каламбур предназначен), что все вызовы / cc ждут, пока "k" будет применен следующим образом:

(call/cc (lambda (k) (k 'return-value)))
  => return-value

Хитрость в том, что вы можете позволить call / cc возвращать свое собственное продолжение, чтобы его можно было применить в другом месте после возврата call / cc следующим образом:

;; returns twice; once to get bound to k, the other to return blah
(let ([k (call/cc (lambda (k) k))]) ;; k gets bound to a continuation
  (k 'blah)) ;; k returns here
  => blah

Это позволяет продолжению возвращаться более одного раза, сохраняя его в переменной. Продолжения просто возвращают значение, к которому они применяются.

Замыкания - это функции, которые переносят свои переменные окружения вместе с ними до того, как аргументы будут ограничены. Они обычные лямбды.

Стиль передачи продолжения - это способ передачи замыканий в качестве аргументов для последующего применения. Мы говорим, что эти аргументы замыкания являются продолжением. Вот половина текущего кода из моего генератора / решателя судоку в качестве примера, демонстрирующего, как стиль передачи продолжения может упростить ваши алгоритмы:

#| the grid is internally represented as a vector of 81 numbers
example: (make-vector 81 0)

this builds a list of indexes |#
(define (cell n) (list (+ (* (car 9) (cadr n))))
(define (row n) (iota 9 (* n 9)))
(define (column n) (iota 9 n 9))
(define (region n)
  (let* ([end (+ (* (floor-quotient n 3) 27)
                 (* (remainder n 3) 3))]
         [i (+ end 21)])
    (do ([i i
          (- i (if (zero? (remainder i 3)) 7 1))]
         [ls '() (cons (vector-ref *grid* i) ls)])
      ((= i end) ls))))

#| f is the continuation

usage examples:
(grid-ref *grid* row 0)
(grid-set! *grid* region 7) |#
(define (grid-ref g f n)
  (map (lambda (i) (vector-ref g i)) (f n)))
(define (grid-set! g f n ls)
  (for-each (lambda (i x) (vector-set! g i x))
    (f n) ls))
1 голос
/ 19 декабря 2011

Необходимо помнить, что при вызове (call/cc f) функция f, переданная в качестве аргумента для call/cc, будет применена к текущему продолжению. Если это продолжение вызывается с некоторым аргументом a внутри функции f, выполнение переходит к соответствующему вызову call/cc, и аргумент a будет возвращен как возвращаемое значение этого call/cc.

Ваша программа сохраняет продолжение «вызов call/cc в iter» в переменной return-result и начинает обработку списка. Он умножает первые 3 ненулевых элемента списка перед тем, как встретить первые 0. Когда он видит 0, продолжение «обработка элемента списка 0» сохраняется в resume-visit, а значение p возвращается в продолжение return-result по телефону (return-result p). Этот вызов вернет выполнение к call/cc в iter, и call/cc вернет переданное значение p. Итак, вы видите первый вывод 6.

Остальные вызовы iter аналогичны и заставят выполнение идти вперед и назад между такими двумя продолжениями. Ручной анализ может быть немного сложным, вы должны знать, что такое контекст выполнения при восстановлении продолжения.

...