continuation的formalization在Wes的课和这里都得到了很好的阐述,我这里就 the yin/yang problem 再来多说两句。
cont实在是太强大了,好在
The captured continuation is itself packaged up as a procedure, also of one argument. That’s so that you can’t muck around with the continuation itself in any data-structure-like way. There are only two things you can do with captured continuations–capture them and resume them.
—An Introduction to Scheme and its Implementation
下面是一个简化版的yin/yang problem(以下沿用Wes的记号):
((call/cc call/cc) (call/cc call/cc))
((cc1 cc2) (cc3 cc4)) 中的4个cc均为无法继续求值的函数,但(cc cc)是个application因此可以求值。
我们先来evaluate (cc1 cc2):
cc1 traps its surrounding context H1 and passes it to cc2.
cc2 traps its surrounding context H2.
Now this is the tricky bit: what does cc2 do next?
cc2 calls H2, and passes H1 as the argument!
H2被调用的时候,控制瞬间返回到H2被保存的地方,并被替换为了H1。
于是变成了(cc1 H1),再变为H1,即current continuation
也就是说,(call/cc call/cc) is equivalent to (call/cc (lambda (n) n)).
如果你定义一个x为 (define x (call/cc call/cc)),那么x就capture了定义x的那个cont,也就是当时的top level cont。注意这个(x x)和((cc cc)(cc cc))的效果是不同的,因为第二个(cc cc)所capture的context与第一个不同,而(x x)的两个x是相同的,其结果就是把x赋值给了自身。
再看个有趣的例子:
(define y (x x))
想知道y是什么东西?哈哈,没问,因为(x x)就把当前的context强制换成了x所保存的context,y就没有定义了!
再看一个(x 3) 等于把x的那个空填上了,变成了3。而x自己也变成了3,成了一个固定值。
想看更奇怪的?
(define x (call/cc call/cc))
(define y (call/cc call/cc))
(x y)
(x 3)
(x 5)
x和y的值都是什么?呵呵
下面回到原来的问题 ((cc1 cc2) (cc3 cc4))。
我们知道了第一个application得到H1,第二个application得到了H3。
现在apply (H1 H3)。
什么是(H1 H3)呢? H1=[ (. (cc3 cc4)) ], H3=[ ((cc1 cc2) .) ]
(H1 H3) => (H3 (cc3 cc4)) => ((cc1 cc2) (cc3 cc4))
又变回来了!
最后,试验一下以下的程序:
(define call/cc call-with-current-continuation)
(let* ((yin ((lambda (foo) (newline) foo)
(call/cc call/cc)))
(yang ((lambda (foo) (write-char #\*) foo)
(call/cc call/cc))))
(yin yang))
(let* ((yin ((lambda (foo) (newline) foo)
(call/cc call/cc)))
(yang ((lambda (foo) (write-char #\*) foo)
(call/cc call/cc))))
(yang yin))
(let ((yin ((lambda (foo) (write-char #\^) (newline) foo)
(call/cc call/cc))))
(let ((yang ((lambda (foo) (write-char #\*) foo)
(call/cc call/cc))))
(yin yang)))
(let ((yin ((lambda (foo) (newline) foo)
(call/cc call/cc)))
(yang ((lambda (foo) (write-char #\*) foo)
(call/cc call/cc))))
(yin yang))