关于
本文是系列文章中的第七篇，
在上一篇中，我们对比了动态作用域和词法作用域，并实现了一个支持词法作用域的Lisp方言。
我们看到，动态作用域和词法作用域的区别就在于“函数体在什么环境中被求值”。
动态作用域中的函数，在函数调用的环境中被求值。
而词法作用域中的函数，在被定义时的环境中求值。
从实现的角度来看，闭包就是一个数据结构，
它保存了函数的参数列表，函数体和被定义时的环境，并没有什么神秘的地方。
上一篇文章中，我们还对比了闭包与对象，它们都是有内部状态的实体。
引出了我们let over lambda的优雅断言。
Continuation
这一篇文章，我们将学习新的概念了，它不过是一个“坑”。
之所以这么说，一方面，这个概念极难理解，普通人被坑数月也不为过。
另一方面，它的表现形式好像是一个“坑”，它可以看成一个“有去无回”的单参函数。
1. 什么是后续的计算
我们先看一个小例子吧。
(+ 1 (* 2 3))
求值结果是7，它是怎么得来的呢？
是先求值(* 2 3)得到6，然后求值(+ 1 6)得到了7。
值得注意的是，乘法那一步得到了运算结果，而加法那一步，使用了这个运算结果。
如果乘法得到的不是6，而是10，
加法运算使用10这个运算结果，那么最终结果是多少？
是(+ 1 10)，即11了。
更进一步，如果乘法得到的不是6，而是x，最终结果是多少？
我们知道了，将会是(+ 1 x)。
因此，一旦我们有了乘法的值，整个计算结果就知道了。
而当乘法值尚未确定的时候，我们只能用一个单参函数来表示“后续的计算”，
(define cont
(lambda (x)
(+ 1 x)))
计算完乘法的值后，只要调用这个单参函数，就能拿到整个程序的计算结果了。
因此，我们称这个单参函数为乘法表达式的continuation。
2. 未来要做的事情是一个单参函数
如图，我们不但关心表达式的值是怎样得出来了，
还关心表达式的值是怎样被使用的，
于是，每个表达式都对应了一个“它的”continuation。
一旦我们用表达式的值，填充了它的continuation，整个程序就算跑完了。
程序的未来，就是这个单参函数。
call-with-current-continuation
在所有语言中，我们都可以引入continuation这个概念，
但是Lisp更强大，它们的continuation是first-class的。
1. first-class
什么叫first-class的呢？
某个东西是first-class的，就是说这个东西可以当做函数的参数，也可以当做函数的返回值。
有了高阶函数之后，函数就是first-class的了。
现在我们来看continuation变成first-class会有什么好玩的事情发生。
2. 例子
Racket提供了call/cc，来拿到(call/cc ...)表达式本身的continuation，
即，current continuation，看一个例子吧。
(+ 1 (call/cc
(lambda (cont)
(cont 2))))
结果是3，其中cont就是(call/cc ...)这个表达式的continuation，
不就是这个函数吗？
(define cont
(lambda (x)
(+ 1 x)))
是的，因此，(cont 2)的结果就是整个计算结果，(cont 2)得到3。
3. 语法规则
（1）call/cc接受一个单参函数fn作为参数。
这里fn指的就是上面的(lambda (cont) ...)
（2）求值(call/cc ...)表达式，会使用(call/cc ...)表达式的continuation调用fn。
因此，fn的形参cont就是(call/cc ...)表达式的continuation。
（3）另外，我们规定，fn的continuation就是call/cc的continuation。
即，如果fn中没有调用cont，则(call/cc ...)的值就是函数的返回值。
(+ 1 (call/cc
(lambda (cont)
2)))
结果也是3。
4. 这有何难？
可能看了上面的例子，会对continuation付之一笑，这还要坑几个月？怎么可能？
那好吧，我们看一个稍微复杂点的例子。
((call/cc (lambda (cont) cont)) (lambda (x) "hi"))
谁能告诉我，结果为什么是"hi"？
实际上，执行过程是这样的：
（1）这是一个函数调用表达式，形如(f a)，因此先求值f，再求值a。
（2）求值(call/cc (lambda (cont) cont))，因为cont没有被调用，
所以，(call/cc ...)表达式的值就是cont了，f的值是cont了。
（3）(lambda (x) "hi")求值为一个函数对象#<procedure>，
a的值是#<procedure>了。
（4）开始用cont调用这个函数对象，
注意了啊。。因为cont是(call/cc ...)表达式的continuation，
会导致程序从(call/cc ...)求完值后的位置再次执行，
即，看起来好像(call/cc ...)又返回了。
并且，(call/cc ...)的值就是这个函数对象。
因为用谁调用cont，(call/cc ...)的值就是谁嘛。
（5）(call/cc ...)求完值后要做什么呢？那就是第（3）步了啊，
(lambda (x) "hi")又求值为一个函数对象#<procedure>，
a的值是#<procedure>了。
（6）然后进行函数调用了，((lambda (x) "hi") (lambda (x) "hi"))，
结果为"hi"。
5. 我彻底凌乱了
是不是有些凌乱啊，下面这个阴阳谜题难度更大。
(let* [(yin ((lambda (foo) (newline) foo)
(call/cc (lambda (bar) bar))))
(yang ((lambda (foo) (display "*") foo)
(call/cc (lambda (bar) bar))))]
(yin yang))
结果会无限输出，
先输出一个星号，换行输出两个星号，换行输出三个星号，等等。
这里把值得注意的几个点，重点表述一下，
（1）什么时候cont被调用，就相当于对应于这个cont的(call/cc ...)表达式返回了，
并且该(call/cc ...)表达式的值，就是用来调用cont的值，
即，(cont v)则(call/cc ...)的值就是v。
（2）不同位置，或者相同位置不同时间调用的(call/cc ...)产生的continuation是不同的，不同的cont被调用，会返回到“历史上”的某个位置。
call/cc的威力
说了这么多call/cc，有什么卵用？
我们知道很多动态语言有generator这个概念，
伴随generator有一个yield，很诡异。
它居然可以让一个函数返回多次，没错，它无非就是continuation嘛。
1. python中的generator
def gen(x):
yield x
yield x+1
yield x+2
iter=gen(1)
print(iter.next()) #1
print(iter.next()) #2
print(iter.next()) #3
我们看到gen()返回一个迭代器iterator，
不断的调用next()会导致gen从yield位置继续向下执行。
相似的例子，可参考ES6的generator和Ruby的Fiber。
2. 用call/cc实现yield
(define (gen x)
(define k-body #f)
(define k-yield #f)
(define (yield x)
(call/cc (lambda (k2)
(set! k-yield k2)
(k-body x))))
(lambda ()
(call/cc (lambda (k1)
(if (eq? k-body #f)
(begin
(set! k-body k1)
(yield x)
(yield (+ x 1))
(+ x 2))
(k-yield))))))
(define iter (gen 1))
(iter) ;1
(iter) ;2
(iter) ;3
后续文章我们还会发现，我们可以定义宏（macro），让上述表达方式更简练。
宏，才是Lisp语言的精髓。
3. 用宏做语法糖
(make-generator (gen x y)
(yield x)
(yield y)
(+ x y))
(define iter (gen 1))
(iter) ;1
(iter) ;2
(iter) ;3
其中，make-generator是一个宏，按下面的方法定义，感兴趣的可以一试。
(define-syntax make-generator
(lambda (form)
(syntax-case form ()
[(keyword (name ...) . body)
(syntax-case (datum->syntax #'keyword 'yield) ()
[yield
#'(define (name ...)
(define k-body #f)
(define k-yield #f)
(define (yield . args)
(call/cc (lambda (k2)
(set! k-yield k2)
(apply k-body args))))
(lambda ()
(call/cc (lambda (k1)
(if (eq? k-body #f)
(begin
(set! k-body k1) . body)
(k-yield))))))])])))
下文
本文介绍了continuation，还介绍了Lisp中的first-class continuation，
最后，用call/cc实现了yield。
然而，只停留在使用层面的话，神秘感是无法抹除的，
下一篇文章，我们来实现call/cc，你准备好了吗？
参考
Python: Iterators & Generators
Continuation
The Scheme Programming Language, 4th Edition
Practical Common Lisp
网友评论