Схема продолжения - нужно пояснение
Следующий пример включает в себя переход в продолжение и выход. Может кто-нибудь объяснить поток функции. Я двигаюсь по кругу вокруг продолжения и не знаю точек входа и выхода функции.
(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 ответа
Процедура перебирает список, умножая ненулевые элементы и возвращая результат каждый раз, когда обнаруживается ноль. 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 вызывается, затем цикл продолжается с остальной частью списка. В этом суть продолжения, все остальное - базовая рекурсия.
Вы можете достичь того же самого таким образом:
(define (prod-iter lst) (fold * 1 (remove zero? lst)))
... хотя он может работать лучше, пройдя только один раз.
Для продолжения напомним (предназначено для каламбура), что все, что делает call/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))
То, что вам нужно иметь в виду, это то, что (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 похожи и заставят выполнение идти вперед и назад между такими двумя продолжениями. Ручной анализ может быть немного сложным, вы должны знать, что такое контекст выполнения при восстановлении продолжения.