Kika's
Blog
图片简介 | CC BY 4.0 | 换一张

用Scheme实现一个有栈协程

2024-11-28

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