Print4D

计算的延续(二):Continuation 实现分析

27 Oct 2018

看过《Essentials of Programming Languages》之后,才明白 scheme 中的 continuation 为什么会具有那些特点。这里试着从解释器实现的角度,解释一下 continuation 是如何工作的。


零,Continuation-Passing Interpreters

假设有一种叫 BLAH 的程序语言,语法简单直观,与 JavaScript 相似,我们用 scheme 为它编写一个解释器 demo,以观察 continuation 的工作方式。

这是 BLAH 语言中两个函数调用:

iszero(add(1, 2))

针对这段代码,在任何一门解释器入门课程中,给出的处理方法大致是这样:

(define value-of
  (lambda (exp env)
    (cases expression exp
       (iszero-exp iszero-body
              (= 0 (value-of iszero-body env)))
       (add-exp add-body1 add-body2
              (+
                (value-of add-body1 env)
                (value-of add-body2 env)))
       )))

除了直接在 value-of 中计算求值,还有另一种处理方式:解释器在执行代码时,会构建一个代码执行上下文(control context),作为解释函数的第三个参数,往下一层一层传递,直到必要时再求值。我们给这种新的解释器函数取名叫 value-of/k

(define value-of/k
  (lambda (exp env cont)
    (cases expression exp
       (iszero-exp iszero-body
              (value-of/k iszero-body env
                  (build-iszero-cont cont)))
       (add-exp add-body1 add-body2
              (value-of/k add-body1 env
                  (build-add-cont add-body2 cont)))
       )))

其中 cont 参数即执行上下文,可以发现,value-of 由于需要立即求值所以不得不递归地调用自身,从而导致运行时堆栈的增长。value-of/k 中虽然也会调用自己,但都是尾递归。

value-of/k 之所以能避免递归求值,正是因为其将求值的步骤放入了 cont 中。不难猜到构建 cont 大致的方式

(define iszero-cont
  (lambda (v)
    (= v 0)))

(define add-cont
  (lambda (v1)
    (lambda (v2)
      (+ v1 v2))))

cont 构建好了之后应该何时被执行呢?cont 返回一个函数,该函数接受一个参数。它表示的含义为『我期待一个 value,当 value 准备好了我会对它进行计算』。所以当 value-of/k 遇到 value 时,就将它传给 cont 进行计算。

(define apply-cont                                          ;; new stuff
  (lambda (cont val)
    (cont val)))

(define value-of/k
  (lambda (exp env cont)
    (cases expression exp
           (const-exp val                                 ;; new stuff
                      (apply-cont cont val))
           (iszero-exp iszero-body
                       (value-of/k iszero-body env
                                   (build-iszero-cont cont)))
           (add-exp add-body1 add-body2
                    (value-of/k add-body1 env
                                (build-add-cont add-body2 cont)))
           )))

相应地,cont 中的求值结果也应该传给上一个 cont 继续进行计算。两个 build-cont 函数的完整实现如下:

(define build-iszero-cont
  (lambda (cont)
    (lambda (v)
      (apply-cont cont (= v 0)))))

(define build-add-cont
  (lambda (add-body2 env cont)
    (lambda (v1)
      (value-of/k add-body2 env
                  (lambda (v2)
                    (apply-cont cont (+ v1 v2)))))))

cont 其实就是 continuation,这样的解释器被称为 Continuation-Passing Interpreters。这种设计除了可以避免 value-of 运行堆栈的增长,还有一个更重要的作用,为实现 exception 和 thread 等机制提供了便利。


一,Exception

BLAH 代码如下:

let foo = function (n) {
  if (iszero(n)) {
    throw -100
  } else {
    return add(n, 1)
  }
}
let bar = function (x) {
  try {
    return add(foo(x), 2)
  } catch (e) {
    return add(e, 100)
  }
}
add(bar(y), 3)

如果代码顺利执行(没有抛出异常),y 会先加 1,然后再加上 2,最后加上 3。continuation 为:

(lambda (v1)
  (lambda (v2)
    (lambda (v3)
      (+ (+ (+ y v1) v2) v3))))  ;; 实际参数 1、2、3 会被依次传入

如果 n 为零程序抛出异常,加 1 和加 2 的动作会被忽略,程序进入 catch block,转而执行加 100 再加 3 的步骤。continuation 为:

(lambda (v1)
  (lambda (v2)
    (+ (+ y v1) v2)))           ;; 实际参数 100、3 会被依次传入

两种情况对应的执行流程并不相同,所以我们给 value-of/k 添加第四个参数 catch-cont,表示出现异常时程序的执行流程:

(define value-of/k
  (lambda (exp env cont catch-cont)
    (cases expression exp
           (const-exp val
                      (apply-cont cont val))
           (iszero-exp iszero-body
                       (value-of/k iszero-body env
                                   (build-iszero-cont cont) catch-cont))
           (add-exp add-body1 add-body2
                    (value-of/k add-body1 env
                                (build-add-cont add-body2 cont) catch-cont))
           (try-exp try-body catch-var catch-body
                    (value-of/k try-body env
                                (build-try-cont ... )
                                (build-catch-cont ... )))
           (throw-exp throw-body
                      (value-of/k raise-body env
                                  (build-throw-cont ... ) catch-cont))
           )))

catch-cont 是指 BLAH 代码抛出异常时对应的处理逻辑,除了 try catch block 以外,value-of/k 在处理其他表达式时,都是将 catch-cont 原样传下去。也就是说,如果目标代码没有使用 try catch 捕获异常,那么 catch-cont 就是第一次调动 value-of/k 时传入的值,也就是程序默认对异常的处理逻辑(一般来说是打印堆栈信息然后错误退出)。

同样地,除了 catch-cont,在第一次调用 value-of/k 时还需要传入 cont 的初始值。这个值的含义为,当整个 BLAH 代码求值完毕后,所得到的值应该如何处理。一些程序语言会将它打印到标准输出,有的会将它忽略。作为 demo 代码,为了观察方便,我们将其打印出来。

(value-of/k the-whole-exp init-env end-cont end-catch-cont)

(define end-cont
  (lambda (val)
    (display (format "End of computation. final value: ~s ~%" val))))

(define end-catch-cont
  (lambda (val)
    (display (format "Exception occurred. exception value: ~s ~%" val))))

接下来,还有三个构建 continuation 的函数。

build-try-cont

try-cont 的构建比较容易,它属于程序正常执行的流程(没有抛出异常)。可以这样想,如果没有异常抛出,那么 catch 代码块根本不会执行,try catch 语句其实是可以去掉的。上面 BLAH 代码中的 bar 函数,可以简写成这样:

let bar = function (y) {
  return add(foo(y), 2)
}

所以 build-try-cont 不需要多余的动作,直接将 try-body 的求值结果(val)和原始执行流程(cont)传给 apply-cont 即可。

build-catch-cont

catch-cont 为捕获异常后,代码的执行逻辑。异常本身也是一个 value,抛出后被 catch 代码块捕获,并绑定到变量上。之后对 catch 代码块的表达式求值,最后将求值结果作为整个 try catch 代码块的值返回给上层。

对应 BLAH 代码为例。foo 函数抛出 value 为 -100 的异常,传入 bar 函数的 catch 代码块,绑定到变量 e 上。接着对 add(e, 100) 求值,最后将求值结果传给 add(_, 3)

build-throw-cont

value-of/k 遇到 throw 语句,说明代码需要抛出一个异常。value-of/k 先对 throw 后的表达式求值,然后将结果传给异常处理流程(catch-cont)。注意是传给 catch-cont 而不是 cont,因为代码执行流程直接跳到了上层的 catch 语句块(如果有的话,没有程序就直接退出),所以正常的执行流程 cont 被丢弃了。

完整的代码:

(define value-of/k
  (lambda (exp env cont catch-cont)
    (cases expression exp
           ...
           (try-exp try-body catch-var catch-body
                    (value-of/k try-body env
                                (build-try-cont cont)
                                (build-catch-cont catch-var catch-body env cont)))
           (throw-exp throw-body
                      (value-of/k raise-body env
                                  (build-throw-cont catch-cont) catch-cont))
           )))

(define build-try-cont
  (lambda (cont)
    (lambda (val)
      (apply-cont cont val))))

(define build-catch-cont
  (lambda (var catch-exp env cont)
    (lambda (val)
      (value-of/k catch-exp
                  (extend-env var val env)  ;; 绑定新的变量(var)和值(val)到 environment。
                  cont                      ;; 原始的 cont 依然需要,
                                               ;; 就像示例代码中抛出了异常后也依然会执行加 4 操作。
                  end-catch-cont))))        ;; catch 中的代码如果没有放入新的 try catch 代码块,
                                               ;; 那当再次抛出异常时,将不会被捕获,
                                               ;; 所以这里设置 catch-cont 为默认的 end-catch-cont。

(define build-throw-cont
  (lambda (catch-cont)                      ;; 正常的执行流程(cont)被丢弃了,
    (lambda (val)                              ;; 所以当抛出异常后,try 语句块中的代码将不再执行。
      (apply-catch catch-cont val))))


二,Thread

这里的 thread 更像是 lua 的 coroutine,是程序运行时的执行流程切换。执行流程的切换其实就是 continuation 之间的切换。

BLAH 程序代码如下:

let x = 0
spawn(function () {x = add(x, 1)})      // thread 1
spawn(function () {x = add(x, 2)})      // thread 2
x = add(x, 100)

spawn 接受一个函数,将该函数作为一个新的线程执行。

最简单的实现:将所有线程放入一个线程池(thread-queue),且不考虑线程间切换的问题,即主线程执行完后再执行子线程,一个子线程执行完后再执行下一个子线程,直到线程池为空后程序退出。

原本处理程序最终返回值的逻辑(end-cont)是在主线程执行完后打印结果并退出,现在改为主线程结束后执行子线程:

(value-of/k the-whole-exp init-env end-main-thread-cont)

(define end-main-thread-cont                           ;; 原来的 end-cont 函数。
  (lambda (val)
    (display (format
              "End of main thread, final value: ~s. Start to run sub-threads ~%"
              val))                                    ;; 为了简单,在执行子线程之前就把结果打印出来了。
    (run-next-thread)))

(define run-next-thread
  (lambda ()
    (if (null? thread-queue)
        "No threads. End of computation."              ;; 如果线程池为空,退出。
        (let ((first-thread (car thread-queue))
              (other-threads (cdr thread-queue)))
          (set! thread-queue other-threads)
          (first-thread)))))

spawn 创建的线程都是异步执行,spawn 自身也不返回有意义的值。可以这样认为,它除了新建一个线程加入线程池外,本身对整个代码的执行上下文没有任何影响。所以 value-of/k 遇到 spawn 语句时,构建的 contbuild-try-cont 一样,直接传给 apply-cont

(define value-of/k
  (lambda (exp env cont)
    (cases expression exp
           ...
           (spawn-exp spawn-body
                      (value-of/k spawn-body env (build-spawn-cont cont)))
           )))

(define build-spawn-cont
  (lambda (cont)
    (lambda (func)
      (add-to-thread-queue
       (lambda ()
         (apply-call func "dummy"                 ;; 线程对应函数都没有参数,这里随意传入一个值。
                         end-subthread-cont)))         ;; apply-call 的第四个参数,
                                                          ;; 表示函数调用完成后该做什么。
      (apply-cont cont "dummy"))))                    ;; 这个 dummy 可以看成是 spawn 函数的返回值,
                                                          ;; 为了保持所有函数都有返回值这个简单统一的模型,
                                                          ;; 这里也随意传入一个值。

(define end-subthread-cont
  (lambda (dummy)
    (run-next-thread)))                               ;; 当一个子线程执行结束,再执行下一个子线程。

(define add-to-thread-queue
  (lambda (thread)
    (set! thread-queue
          (cons thread thread-queue))))

apply-call 处理所有函数调用。func 为函数的结构体,包含函数的形参、函数体、以及 env。arg 为实际参数。

apply-call 会对函数体求值,所以需要传入 cont,告诉 value-of/k 求完值之后干什么。

(define apply-call
  (lambda (func arg cont)
    (let ((var (get-func-var func))
          (body (get-func-body func))
          (env (get-func-env func)))
      (value-of/k body
                  (extend-env var arg env)                ;; 绑定函数的实参和形参。
                  cont))))

这个线程模型虽然可以工作,但有些简单。比如缺少了线程间通信和加锁的机制,以及与 continuation 更相关且更重要的线程间切换机制。

线程间切换

上面的简单模型中,主线程子线程依次执行,最终实现的效果和下面这段不使用线程的代码是完全等价的。

let x = 0
x = add(x, 100)
x = add(x, 1)
x = add(x, 2)

程序代码中之所以使用多线程,是为了充分利用 CPU 资源。当一个线程处于 I/O 等待时,让 CPU 继续执行其他的线程,从而避免 CPU 资源的浪费。

我们尝试加入一种简单的切换模型,每个线程执行 5 步(即 5 次 apply-cont),然后切换到下一个线程。设置一个计数器(time-remaining),在每次执行 apply-cont 时检查这个计数器,如果为 0 即切换到下一个线程,否则继续执行并减小计数器的值。

(define apply-cont
  (lambda (cont val)
    (if (= time-remaining 0)
        (begin
          (add-to-thread-queue
           (lambda () (apply-cont cont val)))                 ;; 下次开始执行时继续执行 apply-cont。
          (run-next-thread))
        (begin
          (set! time-remaining (- time-remaining 1))
          (cont val)))))

thread-queue 取得新的线程执行前,需要将 time-remaining 重新设为 5。

(define run-next-thread
  (lambda ()
    (if (null? thread-queue)
        "No threads. End of computation."
        (let ((first-thread (car thread-queue))
              (other-threads (cdr thread-queue)))
          (set! thread-queue other-threads)
          (set! time-remaining 5)                                ;; new stuff
          (first-thread)))))

模型虽然简单,但基本的方法就是这样,不同的切换方式只是选择在哪里执行 run-next-thread。像 golang 会在进入阻塞式系统调用时切换 goroutine,也很有道理,如果一个 goroutine 中没有系统调用,说明它可能在做纯计算的任务,CPU 也没闲着。

主动切换线程

除了由解释器判断是否切换线程外,还可以提供一种机制让程序主动地在线程间切换。这里使用 yield 关键字显式地声明切换到下一线程。

虽然 BLAH 代码使用了 JavaScript 的语法,但这里的 yield 和 JavaScript 的 yield 并不相同。

let x = 0

spawn(function () {
  x = add(x, 1)
  yield
  x = add(x, 1)
})                      // thread 1

spawn(function () {
  x = add(x, 2)
  yield
  x = add(x, 2)
})                      // thread 2

x = add(x, 100)

yield 语句用于告知解释器切换到下一个线程。当 value-of/k 遇到 yield 时应当:


(define value-of/k
  (lambda (exp env cont)
    (cases expression exp
           ...
           (yield-exp
                      (apply-cont
                       (build-yield-cont cont)
                       "dummy"))
           )))

(define build-yield-cont
  (lambda (cont)
    (begin
      (add-to-thread-queue                 ;; 将当前的执行上下文保存到线程池。
       (lambda ()
         (apply-cont cont "dummy")))
      (run-next-thread))))                 ;; 取出下一个线程并执行。

因为 yield 语句不接受参数也不返回值,所以用 “dummy” 占位。


Generators

python 的 generator 也可以看成两个线程之间来回切换。

def my_gen():
    n = 1
    while True:
        yield n
        n += 1

def my_caller():
    g = my_gen()
    print(next(g))   # output: 1
    print(next(g))   # output: 2
    print(next(g))   # output: 3

my_caller()

第一次调用 next(g)my_caller 所在的线程被挂起,my_gen 作为一个新的线程开始执行。遇到 yield 后切换回 my_caller 继续执行,并将 n 返回给 my_caller。当 my_caller 再一次调用 next(g),则又切换到 my_gen

BLAH 中实现的 yield 和 python 的 yield 已经很相近了,还有两点不同:

根据这两点不同,我们修改一下解释器代码:

(define value-of/k
  (lambda (exp env cont)
    (cases expression exp
           ...
           (generator-exp g
                          (build-generator-cont cont g))
           (yield-exp yield-body
                      (value-of/k yield-body env (build-yield-cont cont))
           )))

(define build-generator-cont
  (lambda (cont g)
    (begin
      (set! caller-thread                     ;; 保存当前线程(调用线程)。
            (lambda (val)                     ;; 因为 yield 会返回一个值到调用线程,
                                                 ;; 这里的 val 参数用于接收这个值。
              (apply-cont cont val)))
      (run-thread g))))                       ;; 执行 generator 对应的线程。

(define build-yield-cont
  (lambda (cont)
    (lambda (val)
      (begin
        (set! generator-thread               ;; 保存 generator 线程
              (lambda ()
                (apply-cont cont "dummy")))
        (caller-thread val)))))              ;; 将结果返回给调用线程。

build-yield-cont 中保存 generator 线程时,依然传入了 "dummy"。因为这里的 cont 指的是 generator 内部的上下文,而 yield 是将值返回给调用它的线程,在它自身的 generator 线程内,它是不返回值的。用 python 举一个例子:

def my_gen():
    n = 1
    while True:
        print(yield n)
        n += 1

def my_caller():
    g = my_gen()
    next(g)
    next(g)

my_caller()             # output: None

执行这段代码会输出一个 None。因为 yield n 会将 n 返回给 my_caller,但在 my_gen 内部它不返回值,所以 print 得到了 None


三,call/cc

在大多数解释器实现中,continuation 被表示为数据结构,而不是函数。但我们仍然选择将 continuation 表示为函数,除了简单之外,更因为这样可以直观地展示出『continuation 可以被调用』这个特点。

continuation 是一个匿名函数,接受一个值,表示它将如何处理这个值。在我们的解释器代码中,continuation 总是在解释器内部被调用。能不能提供一种机制,把 continuation 暴露给程序代码,让用户自己控制如何处理 continuation?

在 scheme 中这种机制就是 call/cc。call/cc 接受一个函数作为参数,这个函数也接受一个参数,这个参数会被解释器绑定为当前的 continuation。

比如这段 scheme 代码:

(define f '())

(+ 1
   (call/cc
    (lambda (c)
      (set! f c)
      0)))

(+ 4 (f 2))    ;; => 3

解释器遇到 call/cc 后,会将当前 continuation 作为参数,调用 call/cc 中的函数。代码中 f 被绑定到了 call/cc 所在位置的 continuation。

执行 (+ 4 (f 2)) 后会返回 3,不是 7。即代码执行了 1 + 2,加 4 的步骤被忽略了。至于为什么会这样,我们将 call/cc 引入 BLAH:

let f = null

add(1, callcc(
  function(c) {
    f = c
    return 0
  }))

add(4, f(2))

value-of/k 中对 callcc 函数特殊处理:

(define value-of/k
  (lambda (exp env cont)
    (cases expression exp
           ...
           (callcc-exp body
                       (value-of/k body env (build-callcc-cont cont)))
           )))

(define build-callcc-cont
  (lambda (cont)
    (lambda (func)
      (apply-call func cont cont))))

(define apply-call                                    ;; apply-call 被扩展为处理普通的函数调用和 cont 调用。
  (lambda (func arg cont)
    (if (is-a-cont func)
        (apply-call-cont func arg cont)               ;; 当 func 是 continuation 时,
                                                         ;; apply-cont 的第三个参数 cont 会被丢弃。
        (apply-call-function func arg cont))))

(define apply-call-function
  (lambda (func arg cont)
    (let ((var (get-func-var func))
          (body (get-func-body func))
          (env (get-func-env func)))
      (value-of/k body (extend-env var arg env) cont))))

(define apply-call-cont
  (lambda (cont arg)
    (apply-cont cont arg)))

调用 build-callcc-cont 传入的参数 cont 最终会在 apply-call-function 中通过 extend-env 被绑定到 func 的参数上,也就是 BLAH 代码的参数 c,这个 cont 为:

(lambda (val)
  (end-cont (+ 1 val)))

因为 continuation 的调用方式和普通函数一致,apply-call 被扩展成了处理普通函数调用与 continuation 的调用。和普通函数调用不同的是,调用一个 continuation 时不会再传入当前的 continuation,即当前的 continuation 会被丢弃。

当代码 add(4, f(2)) 中的 f 被调用时,这时当前的 continuation 为:

(lambda (val)
  (end-cont (+ 4 (f val))))

f 被调用,apply-call 进入了 apply-call-cont,因而当前的 continuation 被丢弃了。所以程序最后执行 ((lambda (val) (end-cont (+ 1 val))) 2),返回 3。


四,play with call/cc

从实现可以看出,continuation 之所以可以方便的实现 Exceptions 和 Threads,因为它将复杂的控制流程抽象为一种数据结构。

现在可以忘了 BLAH,回到 scheme 中再看看 call/cc,看它是如何在代码层面实现那些原本应该在解释器中实现机制:计算的延续(一):Continuation 介绍

(完)

参考链接: