Jan 1, 0001

continuation

References

TODO

Intro

Scheme 是第一个提供 conitnuation 的语言。

对于 Scheme 在整个表达式求值的过程中，任何一个子表达式都对应一个 contination ，其表示该子表达式求值完成后继续完成整个表达式的求值的过程。

Scheme 提供过程 call/cc 以捕获任何表达式对应的 continuation ，使用方法为 (call/cc p) ，其中 p 为一个过程，接收 call/cc 捕获的 current continuation （简称 cc）作为入参，调用 call/cc 时，其捕获 cc 并应用在 p 上，将应用 cc 到 p 上求得的值作为其自身应用求得的值（前提是 cc 没被应用）。捕获到的 cc 是一个过程，可以应用一个参数 v 到 cc 上，若如此则程序的 current continuation 会替换为 cc ，并将 v 作为捕获 cc 时对应的子表达式的返回值。

注意到 contination 是一个过程，同时可以作为参数被传递，contination 在 Scheme 中是 first-class 的。

During the evaluation of a Scheme expression, the implementation must keep track of two things:

what to evaluate and

what to do with the value.

We call “what to do with the value” the continuation of a computation.

The continuation represents an entire (default) future for the computation.

在 Scheme 中 continuation 的实现要求 Scheme 过程调用保存为一颗树（而不是基于栈帧语言的线性关系），如果某个节点被 call/cc 捕获，则这个节点不能及时回收，所以要求垃圾回收机制。

continuation 的类型 TODO

continuation 可以实现 monad TODO

Examples

非本地退出（Non-local exit）

非本地退出：在 p 中应用了传入的 cc 。

for break

(define (test element cc)
  (if (zero? element)
      (cc 'found-zero) ;; non-local exist
      #f))

(define (search-zero test lst)
  (call/cc
   (lambda (return)
     (for-each (lambda (element)
                 (test element return))
               lst)
     #f)))

(search-zero test '(-3 -2 -1 0 1 2 3))

使用 cc 保存 break 时跳转到的位置。

generator

 (define (for-each proc items)
  (define (iter things)
    (cond ((null? things))
        (else
            (proc (car things))
            (iter (cdr things)))))
 (iter items))


(define (generate-one-element-at-a-time lst)
  ;; Hand the next item from a-list to "return" or an end-of-list marker
  (define (control-state return)
    (for-each
     (lambda (element)
       (call/cc
        (lambda (resume-here)
          ;; Grab the current continuation
          (set! control-state resume-here) ;; !!!
          (return element)))) ;; return elem
     lst)
    (return 'end))

  (define (generator)
    (call/cc control-state)) ;; return point as cc
  ;; Return the generator
  generator)

(define generate-digit (generate-one-element-at-a-time '(0 1 2)))

(generate-digit)

这个 case 使用了两个cc，一个保存 generator 的返回地点用于非本地退出，一个保存下次 generator 该从 for-each 的哪次迭代中恢复，注意到 control-state 第一次是原始的过程，后面则变成了 contination。

非引用透明性

(define (get-cc) (call/cc (lambda (c) c)))
(define x (get-cc))
(x 10)
((get-cc) 10)

(define (get-cc) (call/cc (lambda (c) c)))
(let ([x (get-cc)]) (x (lambda (unused) "message")))

(define (get-cc) (call/cc (lambda (c) c)))
(((get-cc) (lambda (x) x)) "message")

任务切换

SPSC

(define dish #f)

(define (put! fruit) (set! dish fruit))
(define (get!) (let ([fruit dish]) (set! dish #f) fruit))

(define (consumer do-other-stuff)
  (let loop ()
    (when dish
      (display  (get!)) (newline)
      (set! do-other-stuff (call/cc do-other-stuff))
      (loop))))

(define (producer do-other-stuff)
  (for-each (lambda (fruit)
              (put! fruit)
              (set! do-other-stuff (call/cc do-other-stuff)))
            '("apple" "strawberry" "peach"  "grape")))

(producer consumer)

Multi-tasks

(define lwp-list '())
(define lwp
  (lambda (thunk)
    (set! lwp-list (append lwp-list (list thunk)))))

(define start
  (lambda ()
    (let ([p (car lwp-list)])
      (set! lwp-list (cdr lwp-list))
      (p))))

(define pause
  (lambda ()
    (call/cc (lambda (k) (lwp (lambda () (k #f))) (start)))))

(lwp (lambda () (let f () (pause) (display "h") (f))))
(lwp (lambda () (let f () (pause) (display "e") (f))))
(lwp (lambda () (let f () (pause) (display "y") (f))))
(lwp (lambda () (let f () (pause) (display "!") (f))))
(lwp (lambda () (let f () (pause) (newline) (f))))

(start)

TODO

阴阳谜题

(define (get-cc) (call/cc (lambda (c) c)))
(define foox (lambda (foo) (display "@") foo))
(define fooy (lambda (foo) (display "*") foo))
(let *((yin (foox (get-cc)))
       (yang (fooy (get-cc))))
  (yin yang))

可以在纸上推导一下，这里 tricky 的地方在于，每次 yin 的 get-cc 被调用时，会产生一个“新”的环境，这个环境中 yin 的值为嵌套多次的 yang 的 cc ，然后开始反复的 (yangcc-old yangcc-new) 直到 yangcc-old 转变为 yincc 开始新的一轮循环。

TODO: 这里为什么内存不会溢出，尾递归是如何起作用的？