Scheme Continuations - 需要解释

Question

下面的例子涉及到跳入和退出continuation。有人可以解释一下函数的流程吗？我围绕continuation画了一个圆圈，不知道函数的进入点和退出点在哪里。

(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

感谢您的选择。

- hrishikeshp19

Answer 1

该程序遍历一个列表，将非零成员相乘，并在每次找到零时返回结果。 Resume-visit 存储了处理列表其余部分的继续执行，并且 return-result 拥有迭代器调用点的继续执行。一开始，resume-visit 被定义为处理整个列表。每当找到一个零时，就会捕获一个继续执行的操作，该操作在调用时会对此时的 lst 执行 (process-list (rest lst) 1)。当列表耗尽时，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) 的结构时，我们首先执行带有 k 绑定到连续的 first 表达式。它是一个过程，当调用时，执行 rest 表达式。在这种情况下，该连续性被存储，并调用另一个连续性，将累积结果 p 返回给 iter 的调用者。下一次调用 iter 时将调用该连续性，然后循环将继续处理列表中剩余的部分。这就是连续性的关键点，而其他所有内容都是基本递归。

- Juho Östman

---

谢谢您的回答，但仍然不太清楚。您能否逐步详细解释一下？ - hrishikeshp19

这比之前的好多了。我读了几遍后终于明白了。现在，我正在尝试实现它。顺便说一下，非常感谢你。它帮了我很大的忙。再次感谢。 - hrishikeshp19

Answer 2

你需要记住的是，对 (call/cc f) 的调用将会将作为参数传递给 call/cc 的函数 f 应用于当前的 continuation。如果在函数 f 中使用某个参数 a 调用该 continuation，则执行将转到相应的 call/cc 调用，并且参数 a 将作为该 call/cc 的返回值返回。

你的程序将“在iter中调用call/cc的继续”存储在变量return-result中，并开始处理列表。它在遇到第一个0之前，将列表的前3个非零元素相乘。当它看到0时，“处理列表元素0”的继续被存储在resume-visit中，并通过调用(return-result p)将值p返回给继续return-result。这个调用会使执行回到iter中的call/cc，并且该call/cc返回传递的p值。因此，你会看到第一个输出6。

其余对iter的调用类似，并且会在这两个继续之间来回执行。手动分析可能有点费脑筋，你必须知道在恢复继续时执行上下文是什么。

- pjhades

Answer 3

你可以以这种方式实现相同的效果：

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

尽管只遍历一次可能会表现更好，但是这样做也可以。

对于continuations（延续），请记住（双关语），所有的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

这使得一个 continuation 可以通过将其保存在变量中来返回多次。Continuation 只是返回它们被应用到的值。

Closure 是一种函数，它们在参数绑定之前携带它们的环境变量。它们是普通的 lambda 函数。

Continuation-passing style 是一种将闭包作为参数传递以便稍后应用的方法。我们称这些闭包参数为 continuations。以下是我的数独生成器/求解器的当前代码的一半，作为演示如何使用 continuation-passing style 简化算法的示例：

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

- Samuel Duclos

---

以下是一个具体的例子，其中延续传递风格是将命名闭包传递到主体中应用的最佳方式： - Samuel Duclos