续体 - Wikiwand

在电脑科学中，续体（英语：continuation，也译作计算续体、续延、延续性），是实化电脑程序的控制状态的一种抽象表示。程序在运算过程中给定一个点，其“剩余将要执行的部分”，即为“续体”。借助编程语言中的续体特性，程序员不但能模块化地自定义循环、break陈述句、continue陈述句等基本控制结构；此外还能以更加简练的方式实现更加复杂的控制结构或计算模式，例如：异常处理、生成器、协程、回溯、非确定性计算、概率编程、^[1]反向传播算法、可微分编程等^[2]。

概述

对一段程序 1 * (2 + 3) - 4 而言，若当前正在计算 2 + 3，这部分则称为可约表达式（英语：redex; reducible expression）^[3]；而其余的部分 1 * $[\cdot ]$ - 4 即是续体。这里的符号 $[\cdot ]$ 被称为“洞”，表示可约表达式之计算结果将要回填的地方，可视为占位符。 ^[4] ^[5] 续体被用于计算模型，比如λ演算^[6]、指称语义^[7]和演员模型^[8]。这些模型仰仗于编程者或语义工程师书写数学函数时采用“续体传递风格”（continuation-passing style，简写为CPS）^[9]。

续体的概念在任何编程语言中都会出现，而不同的编程语言之间的差别在于是否提供构造或是算子，以供显示地捕捉跟恢复续体。不同种类的算子，亦有相异的抽象程度与表达能力。例如能够恢复多次的多发续体（英语：multi-shot continuations），其表达能力比仅能恢复一次的单发续体（英语：one-shot continuations）还要强。若能将捕捉到的续体实化作为一般的值存储与传递，便会称其为头等续体（英语：first-class continuations）。而当被捕捉的续体被调用时，程序的流程控制将会恢复到续体被捕捉时所在的地方。

Remove ads

历史

Gerald J. Sussman和Guy L. Steele Jr.在1976年论文《Lambda之终极指令式》中，提及了John C. Reynolds（英语：John C. Reynolds）在1972年的论文《高阶编程语言的定义性解释器》中采用了术语“续体”^[7]，并认定Alonzo Church在1941年著作《Lambda转换的演算》里^[10]，已经清晰的理解了“续体”的使用，这是用纯λ演算彻底完成所有事情即邱奇编码的唯一方式，并举出其中有序对定义所对应的Scheme表示为例^[11]：

(define (cons m n)
  (lambda (a) (a m n)))
(define (car a)
  (a (lambda (b c) b)))
(define (cdr a)
  (a (lambda (b c) c)))

John C. Reynolds（英语：John C. Reynolds）在1993年的论文《续体的发现》中给出了发现续体的完整历史^[12]。Reynolds认为续体的最早描述由Adriaan van Wijngaarden在1964年9月作出。van Wijngaarden在奥地利的维也纳附近巴登召开的关于“形式语言描述语言”的IFIP（英语：International Federation for Information Processing）工作会议上，在关于ALGOL 60 预处理器的公式化（英语：Formulation）的论文《语法和语义的递归定义》中，倡导通过将真正（proper）过程变换成续体传递风格而消除标签和goto语句^[13]，但是他没有使用“续体”这个名字。

Christopher Strachey、Christopher P. Wadsworth和John C. Reynolds（英语：John C. Reynolds），在指称语义领域的工作中突出了术语“续体”，此间广泛利用续体来允许使用函数式编程语义来分析顺序程序。

Steve Russell为他给IBM 704的LISP实现的一个用户，发明了续体来解决双重递归（英语：Double recursion）问题^[14]，但是他没有为其命名。

Remove ads

续体传递风格

续体传递风格（CPS）意味着编程中用到的每个函数都消费一个表示有关于这个函数调用的余下计算的函数。要返回一个值，这个函数以此返回值调用这个续体函数；要中止这个计算，它返回一个值。以续体传递风格书写程序的函数式编程者，获得了以任意方式操纵控制流程的表达能力。代价是他们必须手工维护控制和续体的不变条件，这通常是高度复杂的任务。

以续体传递风格（CPS）书写的函数接受一个额外的实际参数：显式的续体，它是有一个实际参数的函数。当CPS函数已经计算出来其结果值的时候，它通过以这个值作为实际参数调用续体函数来“返回”它。这意味着在调用CPS函数的时候，调用者函数需要提供一个过程接受这个子例程的“返回”值。以这种形式表达代码使得在直接风格中隐含的一些事物显露出来。这包括了：过程返回变成了对续体的调用，中间值都有了给定名字，实际参数求值的次序变为显见，而尾调用成为简单的将传递给这个调用者的续体不修改的传递给被调用过程。

CPS的关键在于：所有函数都接受称为其续体的一个额外实际参数，并且在函数调用中的所有实际参数必须要么是一个变量，要么是一个λ表达式而非更复杂的表达式。这具有将表达式“从内至外”翻转的效果，由于表达式最内部分必须首先求值，因此CPS使得求值次序以及控制流程变得明确了。

下面是在Scheme语言中仅使用其基本形式的几个例子，对比了直接风格代码和对应的CPS代码，这里约定了将续体函数表示为名为k的形式参数：

更多信息 直接风格, 续体传递风格 ...

直接风格	续体传递风格
(define (pythag x y) (sqrt (+ (* x x) (* y y))))	(define (pythag& x y k) (& x x (lambda (a) (& y y (lambda (b) (+& a b (lambda (c) (sqrt& c k))))))))
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))	(define (factorial& n k) (=& n 0 (lambda (t) (if t (k 1) (-& n 1 (lambda (n-1) (factorial& n-1 (lambda (acc) (*& n acc k)))))))))
(define (factorial n) (define (loop n acc) (if (= n 0) acc (loop (- n 1) (* n acc)))) (loop n 1))	(define (factorial& n k) (define (loop& n acc k) (=& n 0 (lambda (t) (if t (k acc) (-& n 1 (lambda (n-1) (& n acc (lambda (nacc) (loop& n-1 n*acc k))))))))) (loop& n 1 k))

注意在CPS版本的代码中，使用的函数原语（functional primitive）如这里的*&、+&、-&、=&和sqrt&自身也是CPS而非直接风格，所以要使得上述例子在Scheme系统中运行，就必须写出这些函数原语的CPS版本，例如=&定义为：

(define (=& x y k)
  (k (= x y)))

更通用的方式是写一个转换例程：

(define (cps-prim f)
  (lambda args
    (let ((r (reverse args)))
      ((car r) (apply f (reverse (cdr r)))))))

(define =& (cps-prim =))
(define *& (cps-prim *))
(define +& (cps-prim +))
(define -& (cps-prim -))
(define sqrt& (cps-prim sqrt))

要在REPL或直接风格函数中调用CPS函数，必须提供接收CPS函数计算结果的一个续体。上述例子在所需CPS函数原语均已提供的条件下，可以指定其续体为恒等函数：

(pythag& 3 4 (lambda (x) x))
(factorial& 4 (lambda (x) x))

一般的编程经常不采用CPS函数原语^[15]，比如将前面的阶乘函数写为：

(define (factorial& n k)
  (if (= n 0)
    (k 1)
    (factorial& 
      (- n 1) 
      (lambda (acc) (k (* n acc))))))

下面是Standard ML中的高阶函数 foldr和map的续体传递风格实现，和达成一个整数列表的合计函数的简单用例：

fun foldr' f b l = let
    fun f2 ([], k) = k b
      | f2 (a :: r, k) = f2 (r, fn x => k (f (a, x)))
    in
        f2 (l, fn x => x)
    end

fun map' f l = foldr' (fn (x, y) => (f x) :: y) [] l 

fun sum l = foldr' (fn (x, y) => (x + y)) 0 l

对于输入[e₁, e₂, …, e_n]，sum函数等价于将函数复合(fn x => x)∘(fn x => e₁ + x)∘(fn x => e₂ + x)∘…∘(fn x => e_n + x)，应用于0之上，它得到(e₁ + (e₂ + (… + (e_n + 0)…)))^[4]。此外，Haskell提供了函数复合算子。

Remove ads

头等续体

头等续体赋予编程语言强大的执行顺序控制能力。它可以跨越多个调用堆栈来返回结果，或者跳转到此前已经退出了的函数。可以认为其保存了程序的控制流程上下文，而需要注意的是这与进程映像（英语：System image）不同，它不保存程序数据，只保存控制流程上下文。这经常采用“续体三明治”譬喻来说明：

你正站在冰箱前，想要做一个三明治。
你就把这个情况变成一个续体，放入口袋里。
接着，从冰箱里拿出火鸡肉和面包做一个三明治，并坐到桌案前。
你启用了口袋里的续体。
这时发现自己再次站到了冰箱之前，想要一个三明治。
幸运的是，在桌案上就有一个三明治，而用于做三明治的材料都没有了。你可以吃三明治了。^[16]

在这个譬喻中，三明治是一部分程序数据，比如在分配堆上一个对象，并非去调用“制做三明治”例程并等它返回，这里调用“以当前续体制做三明治”例程，它创建一个三明治并在已脱离执行的续体所保存的地方继续执行。

Scheme是支持续体的第一个完全的生产系统，它最初提供了源自Maclisp的用于例外处理的命名catch/throw^[17]，在1985年，Daniel P. Friedman、Mitchell Wand（英语：Mitchell Wand）和William Clinger（英语：William Clinger (computer scientist)）提供了头等续体算子call-with-current-continuation（英语：call-with-current-continuation）（简写为call/cc）^[18]。

在1991年，Bruce Duba等人将callcc介入到了SML/NJ： val callcc : ('a cont -> 'a) -> 'a，这里的'a cont是接受类型为'a的参数的续体的类型；callcc f应用f到当前续体，如果f以参数x调用这个续体，则如同(callcc f)返回x作为结果^[19]。

Remove ads

编程语言的直接支持

很多编程语言以各种名义体现出头等续体，特别是：

Common Lisp：cl-cont^[20]，还可以使用定制宏

Factor：callcc0和callcc1
Haskell：在Control.Monad.Cont中的续体单子^[21]
Haxe：haxe-continuation^[22]
Icon / Unicon：suspend，coexpression：create与@算子^[23]
Java：Lightwolf^[24]和javaflow^[25]
Kotlin：Continuation
Parrot：Continuation PMC，对所有控制流程使用续体传递风格
Perl：Coro^[26]和Continuity^[27]
Pico（英语：Pico (programming language)）：call(exp())和continue(aContinuation, anyValue)
Racket：call-with-current-continuation（英语：call-with-current-continuation）（通常简写为call/cc）
Ruby：callcc
Scala：scala.util.continuations提供了shift/reset
Scheme：call-with-current-continuation（英语：call-with-current-continuation）（通常简写为call/cc）
Smalltalk：Continuation currentDo:，在多数现代Smalltalk环境中续体不需要额外的VM支持就能实现
新泽西Standard ML：SMLofNJ.Cont.callcc

在支持闭包和适当尾调用的任何编程语言中，都可能以续体传递风格书写程序并手工实现call/cc。在续体传递风格下，call/cc成为了可以用lambda表达式书写的一个简单函数。需要支持适当尾调用，因为在续体传递风格下没有函数会返回，所有调用都是尾调用。

Remove ads

以当前续体调用

Scheme编程语言包括了控制流程算子call-with-current-continuation（英语：call-with-current-continuation）（简写为call/cc），Scheme程序可以通过它操纵控制流程。在电脑科学中，使这种类型的隐含程序状态可见为对象，术语上叫做实化。在Scheme中，续体对象是头等值并被表示为函数，具有函数应用（英语：Function application）作为其唯一的运算。Scheme在应用续体和函数二者之间不做语法上的区分。

在Scheme中，出现在一个表达式中的(call/cc f)，接受一个函数f作为它的唯一实际参数，并把它应用到这个表达式的当前续体上。当一个续体对象被应用于一个实际参数的时候，现存的续体被消除，而应用的续体在其所在位置上被恢复，所以程序流程将在续体被捕获的那一点上继续，而“续体的实际参数”则变成call/cc调用的“返回值”。call/cc建立的续体可以被多于一次调用，甚至可以从这个call/cc应用的动态时效范围（extent）的外部来调用。

例如在表达式(g (call/cc f))中，在概念上给出f所应用到的当前续体的方式，是通过将(call/cc f)替代为以lambda抽象绑定的一个变量比如叫做cc，故而它的当前续体是(lambda (cc) (g cc))。对它应用函数f，得到最终结果(f (lambda (cc) (g cc)))。而在表达式((call/cc f) g)中，子表达式的(call/cc f)的续体是(lambda (cc) (cc g))，故而整个表达式等价于(f (lambda (cc) (cc g)))。

Remove ads

立即返回

下面的例子中，使用call/cc来模拟C风格语言中的return语句：

(define (f return)                                                                                                                               
  (return 2)                                                                                                                                     
  3)

(f (lambda (x) x))
=> 3

(call/cc f)
=> 2

首先以正规函数实际参数(lambda (x) x)调用f，它将绑定到形式参数return上的这个函数应用于值2，接着执行下一个表达式返回3。但是，在f被传递给call/cc的时候，将绑定了续体的形式参数应用于2，将程序执行强制为跳转到调用call/cc那一点上，并导致call/cc返回值2。这个结果接着被顶层续体用display函数打印出来。

Remove ads

生成器

下面是生成器的实现代码：

(define (generator lst)
  (define (iterator yield)
    (for-each (lambda (item)
      (set! yield (call/cc (lambda (resume)
        (set! iterator resume)
        (yield item)))))
      lst)
    (yield 'stop-iteration))
  (lambda () (call/cc iterator)))

在这里call/cc被用到了两处：一处是(call/cc iterator)，它以当前取用遍历返回值续体调用生成器所生成的迭代器；另一处是(call/cc (lambda (resume) ……))，它在迭代器遍历目标列表之时捕获当前位置，用于下次重入迭代器之时于此处恢复执行。下面是上述代码的简单用例：

(define generate-digit
  (generator '(0 1 2)))

(define (display-two-digits)
  (display (generate-digit)) (newline)
  (display (generate-digit)) (newline))

(display-two-digits) ;; 分两行打印 0 和 1
(display-two-digits) ;; 分两行打印 2 和 stop-iteration

在定义变量generate-digit之时，将其定义为函数generator应用于列表'(0 1 2)上，而得到的一个闭包（lambda () (call/cc iterator))。

在第一次执行(generate-digit)之时，执行(call/cc iterator)，进而执行(iterator yield)，它将取用遍历返回值续体绑定到形式参数yield之上；然后开始遍历列表的元素进行迭代的(for-each (lambda (item) ……) lst)，在求值(set! yield (……))的第二个实际参数之时，进行每一次迭代步骤(call/cc (lambda (resume) ……))，其中的(set! iterator resume)，将绑定到变量resume上的当前续体，重新绑定到函数名字iterator之上用于以后恢复执行，最后执行(yield item)返回当前列表项目。

在下一次执行(generate-digit)之时，(call/cc iterator)将iterator所绑定的续体应用于当前取用遍历返回值续体之上，从而在上次迭代的(set! yield (call/cc ……))之处恢复执行，这个函数的实际参数求值完毕，它的执行将新传入的取用遍历返回值续体绑定到变量yield上，此后继续这一次的迭代步骤。在遍历了列表的元素之后迭代结束，最终执行(yield 'stop-iteration)，返回一个约定的文字（英语：Literal (computer programming)）常量。

Remove ads

协程

call/cc还可以表达其他复杂的原始运算。下面的代码使用续体达成协作式多任务的用户级线程，亦称为协程：

(define *ready-list* '())

(define (fork fn arg)
  (call/cc (lambda (return)
    (set! *ready-list* (cons return *ready-list*))
    (fn arg)
    (let ((cont (car *ready-list*)))
      (set! *ready-list* (cdr *ready-list*)) 
      (cont #f)))))

(define (yield)
  (call/cc (lambda (return)
    (let ((cont (car *ready-list*)))
      (set! *ready-list*
        (append (cdr *ready-list*) (list return)))
      (cont #f)))))

(define (schedule)
  (let loop ()
    (if (not (null? *ready-list*)) (begin
      (call/cc (lambda (return)
        (let ((cont (car *ready-list*)))
          (set! *ready-list* 
            (append (cdr *ready-list*) (list return)))
          (cont #f))))
      (loop)))))

这里的调度过程也可以选用冗余但普适的弹跳床（英语：trampoline (computing)）方式实现：

(define (schedule)
  (let loop ()
    (if (not (null? *ready-list*)) (begin
      (call/cc (lambda (return)
        (let ((cont (car *ready-list*)))
          (set! *ready-list* 
            (cons return (cdr *ready-list*)))
          (cont #f))))
      (loop)))))

上述代码的简单用例：

(import (srfi 28))

(define (do-stuff-n-print str)
  (let loop ((n 0))
    (if (< n 3) (begin
      (display (format "~a ~a~%" str n))
      ;; 调用退让过程，它捕获调用者的当前续体，
      ;; 将其追加到等待线程的列表，本线程暂停。
      (yield)
      (loop (+ n 1))))))

(define (main)
  ;; 调用分叉过程，它接受一个函数和相应的一个参数，
  ;; 创建一个新线程运行这个函数。
  (fork do-stuff-n-print "This is AAA")
  (fork do-stuff-n-print "Hello from BBB")
  ;; 调用调度过程，只要有任何其他线程等待，
  ;; 就取其中第一个线程运行，最终无等待者时结束。
  (schedule))
  
(main)

其输出为：

This is AAA 0
Hello from BBB 0
This is AAA 1
Hello from BBB 1
This is AAA 2
Hello from BBB 2

参见

续体传递风格
分界续体（英语：Delimited continuation）

引用与注释

Loading content...

延伸阅读

Loading content...

外部链接

Loading content...

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads