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