call/cc 总结 | Scheme

时间：2022-05-15 05:09:19

call/cc 总结 | Scheme

来源 https://www.sczyh30.com/posts/Functional-Programming/call-with-current-continuation/

Continuation

Continuation 也是一个老生常谈的东西了，我们来回顾一下。首先我们看一下 TSPL4 中定义的表达式求值需要做的事：

During the evaluation of a Scheme expression, the implementation must keep track of two things: (1) what to evaluate and (2) what to do with the value.

Continuation 即为其中的(2)，即表达式被求值以后，接下来要对表达式做的计算。R5RS 中 continuation 的定义为：

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

比如 (+ (* 2 3) (+ 1 7)) 表达式中，(* 2 3)的 continuation 为：保存 (* 2 3) 计算出的值 6，然后计算 (+ 1 7) 的值，最后将两表达式的值相加，结束；(+ 1 7) 的 continuation 为：保存 (+ 1 7) 的值 8，将其与前面计算出的 6 相加，结束。

Scheme 中的 continuation 是 first-class 的，也就是说它可以被当做参数进行传递和返回；并且 Scheme 中可以将 continuation 视为一个 procedure，也就是说可以调用 continuation 执行后续的运算。

call/cc

每个表达式在求值的时候，都会有一个对应的 current continuation，它在等着当前表达式求值完毕然后把值传递给它。那么如何捕捉 current continuation 呢？这就要用到 Scheme 中强大的 call/cc了。call/cc 的全名是 call-with-current-continuation ，它可以捕捉当前环境下的 current continuation 并利用它做各种各样的事情，如改变控制流，实现非本地退出(non-local exit)、协程(coroutine)、多任务(multi-tasking)等，非常方便。注意这里的 continuation 将当前 context 一并打包保存起来了，而不只是保存程序运行的位置。下面我们来举几个例子说明一下 call/cc 的用法。

current continuation

我们先来看个最简单的例子 —— 用它来捕捉 current continuation 并作为 procedure 调用。call/cc 接受一个函数，该函数接受一个参数，此参数即为 current continuation。以之前 (+ (* 2 3) (+ 1 7)) 表达式中 (* 2 3) 的 continuation 为例：

1
2
3
4
5
(define cc #f)
(+ (call/cc (lambda (return)
(set! cc return)
(* 2 3)))
(+ 1 7))

我们将 (* 2 3) 的 current continuation (用(+ ? (+ 1 7))表示) 绑定给 cc 变量。现在 cc 就对应了一个 continuation ，它相当于过程 (define (cc x) (+ (x) (+ 1 7)))，等待一个值然后进行后续的运算：

1
2
3
4
5
6
> cc
#<continuation>
> (cc 10)
18
> (cc (* 2 3))
14

这个例子很好理解，我们下面引入 call/cc 的本质 —— 控制流变换。在 Scheme 中，假设 call/cc 捕捉到的 current continuation 为 cc(位于 lambda 中)，如果 cc 作为过程 直接或间接地被调用（即给它传值），call/cc 会立即返回，返回值即为传入 cc 的值。即一旦 current continuation 被调用，控制流会跳到 call/cc 处。因此，利用 call/cc，我们可以摆脱顺序执行的限制，在程序中跳来跳去，非常灵活。下面我们举几个 non-local exit 的例子来说明。

Non-local exit

Scheme 中没有 break 和 return 关键字，因此在循环中如果想 break 并提前返回的话就得借助 call/cc。比如下面的例子寻找传入的 list 中是否包含 5：

1
2
3
4
5
6
7
8
9
10
11
12
(define (do-with element return)
(if (= element 5)
(return 'find-five)
(void)))
(define (check-lst lst)
(call/cc (lambda (return)
(for-each (lambda (element)
(do-with element return)
(printf "~a~%" element))
lst)
'not-found)))

测试：

1
2
3
4
5
6
7
8
9
> (check-lst '(0 2 4))
2
4
'not-found
> (check-lst '(0 3 5 1))
3
'find-five

check-lst 过程会遍历列表中的元素，每次都会将 current continuation 传给 do-with 过程并进行调用，一旦do-with 遇到 5，我们就将结果传给 current continuation (即 return)，此时控制流会马上跳回 check-lst 过程中的 call/cc 处，这时候就已经终止遍历了（跳出了循环）。call/cc 的返回值为 'find-five，所以最后会在控制台上打印出 'find-five。

我们再来看一个经典的 generator 的例子，它非常像 Python 和 ES 6 中的 yield，每次调用的时候都会返回 list 中的一个元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(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)
(set! return (call/cc
(lambda (resume-here)
;; Grab the current continuation
(set! control-state resume-here)
(return element)))))
lst)
(return 'you-fell-off-the-end))
;; This is the actual generator, producing one item from a-list at a time
(define (generator)
(call/cc control-state))
;; Return the generator
generator)
(define generate-digit
(generate-one-element-at-a-time '(0 1 2)))

调用：

1
2
3
4
5
6
7
8
> (generate-digit)
> (generate-digit)
1
> (generate-digit)
2
> (generate-digit)
'you-fell-off-the-end

注意到这个例子里有两个 call/cc，大家刚看到的时候可能会有点晕，其实这两个 call/cc 各司其职，互不干扰。第一个 call/cc 负责保存遍历的状态（从此处恢复），而 generator 中的 call/cc 才是真正生成值的地方（非本地退出）。其中一个需要注意的地方就是 control-state，它在第一次调用的时候还是个 procedure，在第一次调用的过程中它就被重新绑定成一个 continuation，之后再调用 generator 生成器的时候，控制流就可以跳到之前遍历的位置继续执行下面的过程，从而达到生成器的效果。

阴阳谜题

continuation 环境嵌套。后面有时间专开一篇分析～

1
2
3
4
5
(let* ((yin
((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
(yang
((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
(yin yang))

call/cc与数理逻辑

这里简单提一下 call/cc 与类型系统和数理逻辑的联系。call/cc 的类型是 ((P → Q) → P) → P，通过 Curry-Howard 同构，它可以对应到经典逻辑中的 Peirce’s law：

((P→Q)→P)→P((P→Q)→P)→P

Peirce’s law 代表排中律 P∧¬PP∧¬P，这条逻辑无法在 λ演算所对应的直觉逻辑中表示（直觉逻辑中双重否定不成立），因此 call/cc 无法用 λ表达式定义。通常我们用扩展后的 λμ calculusλμ calculus 来定义 call/cc，λμ calculusλμ calculus 经 Curry-Howard 同构可以得到经典逻辑。

References

call/cc的类型是什么

原文：https://blog.csdn.net/nklofy/article/details/48999417

这篇来自我在某问答网站上的一个回答。但我觉得这个问题很有价值，我思考和写作的时间花费了很久。所以我觉得应该保存起来。

问题是，call/cc的类型是什么。我们知道，(call/cc (lambda (k) p))有两种用法，一种是(call/cc (lambda (k) (k a)))，例如(+ 1(call/cc (lambda (k) (k 2))))；一种是(call/cc (lambda (k) k))，例如(let a (call/cc (lambda (k) k))) 或 (define (get-cc) (call/cc (lambda (c) c))) 。第一种返回a，并送入continuation计算；第二种直接返回一个continuation。

所以很明显，call/cc不是只有一种返回类型。两种用法对应两种不同类型。第一个类型是((T1 -> T2) -> T1) -> (T1 -> T2) -> T1，第二种是( (T1 -> T2) -> (T1 -> T2) ) -> (T1 -> T2) -> (T1 -> T2)。

一个简单的联想是，假设x类型是T1->T2, a类型是T1，那么 ((λ(k) (k a) ) x)和 (λ(k) (k) ) x)分别返回什么类型？前者是T2，后者是T1->T2。这就是所谓函数一等公民。

回到call/cc。首先要分析整个程序到call/cc之前的位置，按照TAPL的表达方式，此时的continuation类型是：
λ k: T1 . T1 -> T2

从这个位置开始，call/cc被调用，evaluation rules可表示为:
call/cc [k |-> continuation ] λ k. k a --> a。                    E-APP1 (第一种情况) 
call/cc [k |-> continuation ] λ k. k --> continuation。       E-APP2 (第二种情况)

第一种情况下，type rule为：

Γ├ continuation: T1->T2 Γ├ a: T1 Γ├ λ k: T1 -> T2 . k a
-------------------------------------------------------------------------------------- T-APP1
Γ├ (call/cc ( λ k . k a )) continuation : T1

call/cc过程返回类型T1。原因是evaluation rule对应的是E-APP1。

第二种情况下type rule：

Γ├ continuation: T1->T2 Γ├ λ k: T1 -> T2 . k
-------------------------------------------------------------------------------------- T-APP2 
Γ├ (call/cc ( λ k . k)) continuation : T1->T2

即该情况下应该返回T1->T2。

所以结论就是，两种情况下，返回的类型是不一样的。call/cc有两种可能的返回类型，返回哪一种根据不同的(λ (k) process)匹配。一种匹配 k a，另一种匹配 k。是的，这就类似于(λ x . x a ) 与(λ x . x ) 的区别，返回类型不一样很正常。

在第二种情况下process 直接返回k，但其实程序中call/cc 前后通常会有个let、set!或者其他赋值函数，将这个continuation保存到某个变量x，程序后面会调用(x a)的形式。对于(x a)或者之前的(continuation a)，都回到了(T1 -> T2) -> T1 -> T2的套路上，程序最终运行完时两种情况殊途同归。

PS，在我看来，call/cc更接近于宏而非函数，往往纯用于结构跳转而非求值，例如call/cc (lambda (k) (if(something) (k #t)))...)这种用法。它的精华放在(k #t)以外的地方，控制运行还是跳转。还有，scheme本来就是动态类型系统，类型可以任意的变，分析起来非常痛苦。若当作宏来看就顺眼多了，(...call/cc ...)这个括号里的内容整体用k一个符号代替。然后无论哪种用法，遇到k a或k b时，从整个程序中挖掉call/cc括号内容后，a或b代入k所在位置就能得到结果。

参考文献：<types and programming languages>

================= End

相关文章