Scheme continuation

在 Scheme 中，continuation 是一个非常强大的特性，利用它可以操纵控制流，它可以实现异步、返回、生成器等。

基本使用

call/cc，这个函数会捕获当前位置的 continuation，然后作为参数传给一个过程，也就是说，call/cc 需要一个接受一个参数的过程。我们可以这样玩

> (call/cc (lambda (k) (k '())))

这里的 k 就是 continuation，对一个 continuation 进行调用就会回到原来的上下文，并把参数作为结果，所以这行代码的结果就是一个空列表。我们也可以对一个 continuation 调用 call/cc，那么当前的 continuation 就会作为结果，然后控制流回到原来的上下文，这个会在后边看到例子。

例子

非本地退出（Non-local exit）

利用 continuation 的特性，我们可以实现其他语言的 return，提前结束执行流程。

(define (search-zero ls)
  (call/cc (lambda (return)
    (for-each (lambda (ele)
      (if (zero? ele)
        (return 'found-zero)
        (begin
          (display ele)
          (display " "))))
    ls))))

这个遍历会在第一次遇到 0 的时候结束。

> (search-zero '(1 2 3 0 2 1))
> 1 2 3 found-zero

生成器

在例如 Python、JS、C#这些语言中，都有生成器，语法都大同小异，yield 关键字总是不会缺席。本质都是遍历集合每一个元素的时候就切换到原来的上下文中，然后下次再次调用获取元素的时候，再跳转回到遍历的控制流中，所以说遍历要脱离上下文的时候，我们要保护好现场，以便回来的时候和之前一致，保证遍历正常。

; 生成器
(define (generate-one-element-at-a-time ls)
  (define (control-state return)
    (for-each (lambda (ele)
      (call/cc (lambda (resume-here)
        (set! control-state resume-here)
        (return ele))))
      ; control-state变成了continuation，然后下次再从这里继续，也就是for-each的下一个元素迭代
    ls)
  (set! control-state control-endpoint) ; 重置
  (return 'end))

  (define control-endpoint control-state) ; 保存原始的入点

  ; return the generator
  (lambda () (call/cc control-state)))

调用过程

> (define gen (generate-one-element-at-a-time '(1 2 3)))
> (gen)
> 1
> (gen)
> 2
> (gen)
> 3
> (gen)
> end

返回的迭代器每次都会调用 control-state 这个过程，我们在 for-each 里调用 call/cc，捕获到上下文，然后利用 set!做破坏性的修改，control-state 就由原来开始的一个普通 procedure 变成了一个 continuation，然后 for-each 结束之后我们再把 control-state 恢复到原来的 procedure，也就是其他语言里的重置。我们可以自己再写一个迭代器，判断遇到 end 这个 symbol 结束，这样就轻松完成了一个语言特性！借助能保存上下文信息的特性，我们可以实现协程的效果！请看接下来的例子。

生产者 - 消费者

这是我们在学习其他编程语言多线程的时候必然遇到的经典问题，那么来看看 Scheme 利用 continuation 的实现，关键点是让对方都持有自己的上下文信息。

(define dish '())
(define (put! fruit) (set! dish (list fruit)))
(define (get!) (let ([fruit (car dish)]) (set! dish '()) fruit))

(define (consumer back)
  (let loop()
    (if (pair? dish)
      (let ((fruit (get!)))
        (printf "C: get a ~a~%" fruit)
        (set! back (call/cc back)) ; focus on this line
        (printf "resume from producer: ~a~%" fruit)
        (loop)))))

(define (producer back)
  (for-each (lambda (fruit)
    (put! fruit)
    (printf "P: put a ~a~%" fruit)
    (set! back (call/cc back)) ; focus on this line
    (yield back)
    (printf "resume from consumer: ~a~%" fruit))
  '("apple" "strawberry" "peach" "grape")))

调用

> (producer consumer)

输出

P: put a apple
C: get a apple
resume from consumer: apple
P: put a strawberry
resume from producer: apple
C: get a strawberry
resume from consumer: strawberry
P: put a peach
resume from producer: strawberry
C: get a peach
resume from consumer: peach
P: put a grape
resume from producer: peach
C: get a grape
resume from consumer: grape

关键代码是有注释的两行一样的代码，还记得先前说过的点吗？调用 continuation 会把参数作为结果，然后回到原来的上下文，搭配 call/cc 使用会把当前的 continuation 当作结果返回到原来的上下文中了，这样就实现了在生产者和消费者之间相互传递 continuation，实现了两者的交替执行。

其他有意思的例子

1

(define (get-cc)
  (call/cc (lambda (k) k)))

> (define x (get-cc))
> (x 10)
> x
> 10
> number? x
> #t

x 到底经历什么？x 先是一个 continuation，代表者给 x 赋值的 define 运算，然后执行(x 10)的时候，因为 x 是 continuation，所以 10 作为结果，返回到了原来的上下文中，也就是返回之后要执行的运算是(define x 10)，这时候 x 变成了 10。

2

(let ([x (get-cc)]) (x (lambda (unused) "woc")))

乍一看可能有点糊涂，我们先去掉 let 语法糖转换成 lambda

((lambda (x) (x (lambda (unused) "woc"))) (get-cc))

然后一步一步展开执行。x 作为一个 continuation 被调用，参数是(lambda (unused) "woc")，回到原来的控制流中。

((lambda (x) (x (lambda (unused) "woc"))) (lambda (unused) "woc"))

然后用(lambda (unused) "woc")替换 x

((lambda (unused) "woc") (lambda (unused) "woc"))

最后的结果是

> "woc"

x 参数先是作为一个 continuation，在 lambda 函数里调用，(lambda (unused) "woc")作为参数，返回到原来的控制流。所以参数名才叫 unused 哈哈哈。

总结

continuation 的“原始”让我们看到了计算机/PL 的各种概念，保存上下文进入其他执行流我们可以想到中断、线程切换、异步，非本地退出我们可以想到 return。虽然 continuation 特性很强大，然而代码不容易看懂，这是因为代码来回跳转还带上下文信息。所以看 continuation 代码的时候重要的是找到下一个运算是什么，调用 continuation 会回到这个运算，结果作为这个运算的参数，这样我们才不会在控制流的跳转中迷失自我。