Skip to content
Scroll to top↑

Delimited Continuation

如果不指定捕获的边界,call/cc捕获的延续称为Undelimited Continuation,CPS一文的第三个例子其实揭示了Undelimited Continuation的一些缺陷[1]

scheme
(define k null)

(+ 1 (call/cc (lambda (cc)
           (set! k cc)
              999)))

(k (k (k 1))) ; 2

一旦最里层的(k 1)被调用,当前延续(k (k ?))将被丢弃。这指明捕获的延续虽然看起来像函数,但实质上不是函数,因为它不能组合,一旦调用,会“替换”掉当前延续。我们期望的是一种“接续”的延续,在调用被捕获的延续后还能继续执行当前延续,表现地和嵌套函数一样。

Racket确实有这样的机制,叫做call-with-composable-continuation,别名call/comp,顾名思义,它捕获的延续可以进行组合。

scheme
(define k null)

(+ 1 (call/comp (lambda (cc)
           (set! k cc)
              999)))

(k (k (k 1)))

(k (k (k 1)))会依次打印2,3,4,因为k实质是(<write-to-stdout> (+ 1 ?)),故每次对k的调用都会回到这个时间点,然后将加1之后的新值提供给它。而我们的诉求只要打印最终的值4,即希望捕获的延续到(+ 1 ?)为止,不要把剩余的计算(<write-to-stdout> ?)也包括在内,这提示了Undelimited Continuation的第二个缺点,也是Undelimited意义的由来:我们不能自由划定捕获延续的边界

为了解决这个问题,我们希望在执行流的某处打个标记,当延续捕获到这里时就停止,不要再把外围的计算包括在内。这个标记就像某种“帧定界符(Frame Delimiter)”,我们把计算的一个最小(不能再展开为嵌套计算)单位称为延续的帧。在(foo (bar (baz ...)))中,假定foobarbaz都是一个延续帧,如果在baz处捕获延续,将得到(foo (bar ?)),如果能在bar处打一个标记,(foo (capture-barrier (bar (baz ...)))),使得baz处捕获的延续到capture-barrier为止,只有(bar ?),这种延续称为Delimited Continuation。这时Undelimited Continuation可以看成是使用默认定界符的一个特例,即(capture-barrier (foo (bar (baz ...))))

这种带有标记的Delimited Continuation也称为Prompt。要实现上述目标,需借助call-with-continuation-prompt,别名call/prompt。它接受两个重要参数,第一个参数代表被边界包裹的计算,第二个参数代表要打的标记,call/prompt会将标记用作此处的定界。而call/compcall/cc其实可以接受一个额外的参数,类型是一个帧定界符,作用是使它们捕获的当前延续只到被标记的最近一个Prompt为止。在下面的例子中,make-continuation-prompt-tag创建一个标记,我们把capture-barrier放置在(- 1 (+ 1 ...))之间,从而call/comp捕获的延续只到(+ 1 ?)为止。

scheme
(define (capture-barrier body)
  (let ([tag (make-continuation-prompt-tag)])
    (call/prompt 
      (lambda ()
        (body tag))
      tag)))

(- 1 (capture-barrier
       (lambda (tag)
         (+ 1 (call/comp
                (lambda (cc) (set! k cc) 999)
                tag)))))

(k (k (k 1))) ; 4

call/comp的第二个参数tag去掉能够更深刻领会到定界的含义:如果去掉,(k (k (k 1)))会依次打印-1, 1, -1, -1,因为此时捕获的k(<write-to-stdout> (- 1 (+ 1 ?))),代入1并计算三次得到-1, 1, -1,最后一个-1则来自将最终结果<write-to-stdout>的行为。

实例:实现break

之前提到过,我们可以用call/cc实现各种程序控制流,就像下面的break

scheme
(define-syntax while
  (lambda (stx)
    (syntax-case stx ()
                 [(_ cond body ...)
                  #'(letrec ([loop (lambda ()
                      (if cond
                        (begin
                          body ...
                          (loop))
                        (void)))])

                      (call/cc (lambda (cc)
                                 (set! break cc)
                                 (loop))))])))

(define break null)

; 输出0~5
(let ([i 0])
  (while (< i 10)
         (sleep 0.3)
         (println i)
         (if (= i 5) 
           (break)
           (set! i (+ i 1)))))

但是这个实现与我们通常所说的break相比还有BUG,因为无法处理嵌套的while,内层whilebreak一旦调用,把整个计算延续都给丢弃了。这是一个典型的延续捕获定界的问题,因此可借助Delimited Continuation,把每一个whilecapture-barrier包裹起来,然后将相应的延续标记丢给call/cc,让call/cc捕获延续的时候注意边界:

scheme
(define-syntax while
  (lambda (stx)
    (syntax-case stx ()
                 [(_ cond body ...)
                  #'(capture-barrier ; 设置边界
                      (lambda (tag)
                        (letrec ([loop (lambda ()
                                         (if cond
                                           (begin
                                             body ...
                                             (loop))
                                           (void)))])

                        (call/cc (lambda (cc) 
                                     (set! break cc)
                                     (loop))
                                     tag))))]))) ; 传入tag提醒call/cc

(define break null)

; 循环打印0~5
(while #t
       (let ([i 0])
         (while (< i 10)
               (sleep 0.3)
               (println i)
               (if (= i 5) 
                 (break)
                 (set! i (+ i 1))))))

最后才是原定为本文主角的控制原语prompt/controlreset/shift,它们能实现的控制流都可以用call/prompt配合call/cccall/comp实现。Racket文档上给出了这些原语的实质,promptreset其实都是call/prompt的变体,只是controlshift的实现上我感觉还需要宏的帮助。

推荐阅读

https://andrebask.github.io/thesis/,特别是其中关于TopLevelhandler的讨论。


  1. https://okmij.org/ftp/continuations/against-callcc.html ↩︎