Scheme是一种Lisp方言,在Scheme中可以采用continuation
来实现非常强大的程序流控制,而且代码异常简洁优雅,下面介绍并讲解一种有栈协程的实现。
先贴代码(改编自The Scheme Programming Language, 4th Edition p.64):
(define lwp-list '())
(define lwp
(lambda (thunk)
(set! lwp-list (append lwp-list (list thunk)))))
(define start
(lambda ()
(if (pair? lwp-list)
(let ([p (car lwp-list)])
(set! lwp-list (cdr lwp-list))
(p))
#t)))
(define pause
(lambda ()
(call/cc
(lambda (k)
(lwp (lambda ()
(k #f)))
(start)))))
(define lwp-test
(lambda (n name)
(let f ([n n])
(if (= n 0)
(start)
(begin
(pause)
(display name)
(display n)
(newline)
(f (- n 1))
)))))
(lwp (lambda () (lwp-test 3 "a")))
(lwp (lambda () (lwp-test 2 "b")))
(lwp (lambda () (lwp-test 1 "c")))
(start)
上述代码创建了三个名为a,b,c的协程,并且每个协程输出的次数分别为3,2,1。其中,pause
函数类似于yield
,表示当前协程主动放弃占用CPU,让渡给下一个待执行的协程运行。
在Chez Scheme上运行Scheme代码,得到输出:
a3
b2
c1
a2
b1
a1
#t
可见协程a,b,c依次输出,并且分别输出3,2,1次。
上面的代码仅用三个短小精悍的函数lwp,start,pause
便实现了协程,甚至和协程运行的函数lwp-test
代码行数相当,不得不感慨Scheme的简洁优雅。而其中实现的关键便是pause
中的call/cc
函数。
call/cc
函数只能紧跟一个单参数的lambda函数,它会将call/cc
自身所在的continuation
打包给这个参数。那么什么是continuation
呢?这个在The Scheme Programming Language书中解释的非常迷惑,其实所谓的continuation
就是一个包含PC和调用堆栈的数据结构(ref),我们可以将其当做一个函数进行调用,当我们调用一个continuation
时,我们将回到call/cc
函数的位置,并在原来的调用堆栈上继续运行,好像什么也没有发生一样。于是,带参数调用continuation
便可以实现一种类似于break
或者return k
的效果,即从call/cc
的内部立即返回这个参数值,不再运行后面的代码,如下面这个例子所示。
((lambda ()
(call/cc
(lambda (k)
(display "should reach here")
(k #t)
(display "should not reach here")))))
运行会得到输出should reach here#t
。
一个更实用的例子,计算一个列表的乘积,当遇到0时,立即返回0(因为但凡有一个0,则乘积结果一定是0):
(define product
(lambda (ls)
(call/cc
(lambda (break)
(let f ([ls ls])
(if (null? ls)
1
(let ([x (car ls)])
(if (= x 0)
(break 0)
(* x (f (cdr ls)))))))))))
同时,由于continuation
保存了函数的PC和调用堆栈,这其实就是保存了当前程序的上下文,于是我们还可以实现一种类似于“断点”的效果,通过不断切换不同的程序上下文,以此来实现协程。
其实一旦理解了continuation
的本质,上面这个有栈协程的实现就很容易理解了,此时我们回过头来,具体分析协程的实现代码:
(define lwp-list '())
(define lwp
(lambda (thunk)
(set! lwp-list (append lwp-list (list thunk)))))
(define start
(lambda ()
(if (pair? lwp-list)
(let ([p (car lwp-list)])
(set! lwp-list (cdr lwp-list))
(p))
#t)))
(define pause
(lambda ()
(call/cc
(lambda (k)
(lwp (lambda ()
(k #f)))
(start)))))
其中:
lwp-list
是一个队列,包含着所有协程的最新断点(上下文)- 函数
lwp
用于向lwp-list
加入一个新的协程 - 函数
start
首先通过pair?
判断lwp-list
是否还有断点,然后弹出并调用队首的continuation
(也就是从这个断点恢复了所代表协程的上下文,继续执行协程),如果队列中没有断点了,则返回#t
代表所有协程执行完毕 - 函数
pause
首先将当前断点保存至lwp-list
,用于后续恢复当前协程,然后再调用start
,让渡给下一个协程执行(yield) - 函数
lwp-test
就是一个简单的尾递归迭代函数,每次打印name
之后调用pause
,让渡给其他协程执行,共打印n
次