续体

在电脑科学中，续体（英语：continuation，也译作计算续体、续延、延续性），是对电脑程序的控制状态的一种抽象表示。续体实化了程序控制状态。可以理解为，续体是一种数据结构，它表示在进程执行中给定点上的计算过程，所建立的数据结构可以被编程语言访问，而不是被运行时环境所隐藏掉。这对实现编程语言的某些控制机制，比如例外处理、协程、生成器非常有用。

“当前续体”从运行代码的角度看来，是可以从程序执行的当前点导出的续体。续体还被用来提及“头等续体”，它是一种构造，赋予编程语言保存在任何点上的执行状态的能力，并在程序中后来的点上可能多次返回到这一点。

历史

Gerald J. Sussman和Guy L. Steele Jr.在1976年论文《Lambda: The Ultimate Imperative》中，认定Alonzo Church在1941年著作《The Calculi of Lambda-Conversion》里^[1]，已经清晰的理解了“续体”的使用，这是用纯λ演算彻底完成所有事情即邱奇编码的唯一方式，并举出其中有序对定义所对应的Scheme表示为例^[2]：

(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年的论文《The Discoveries of Continuations》中给出了发现续体的完整历史。Reynolds认为续体的最早描述由Adriaan van Wijngaarden在1964年9月作出。Van Wijngaarden在奥地利的维也纳附近巴登召开的关于“形式语言描述语言”的IFIP（英语：International Federation for Information Processing）工作会议上，在关于ALGOL 60 预处理器的公式化（英语：Formulation）的论文《Recursive Definition of Syntax and Semantics》中，倡导通过将真正（proper）过程变换成续体传递风格而消除标签和goto语句^[3]，但是他没有使用“续体”这个名字。

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

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

头等续体

头等续体对一门语言而言是能完全控制指令执行次序的能力。它们可以用来跳转到产生对当前函数调用的那个函数，或者跳转到此前已经退出了的函数。人们可以认为头等续体保存了程序执行状态，注意到真正的头等续体不同于进程映像（英语：System image）是很重要的，它不保存程序数据，只保存执行上下文。这经常采用“续体三明治”譬喻来说明：

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

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

Scheme是支持续体的第一个完全的生产系统，它最初提供了源自Maclisp的用于例外处理的命名catch/throw^[6]，后来提供了头等续体算子call-with-current-continuation（英语：call-with-current-continuation）（简写为call/cc）^[7]。

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

编程语言支持

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

Common Lisp：cl-cont^[9]，还可以使用定制宏
C# / VB.NET：async/await^[10]
Factor：callcc0和callcc1
Haskell：在Control.Monad.Cont中的续体单子^[11]
Haxe：haxe-continuation^[12]
Icon / Unicon：suspend，coexpression：create与@算子^[13]
Java：Lightwolf^[14]和javaflow^[15]
Kotlin：Continuation
Rhino (JavaScript引擎)：Continuation
Parrot：Continuation PMC，对所有控制流程使用续体传递风格
Perl：Coro^[16]和Continuity^[17]
Pico（英语：Pico (programming language)）：call(exp())和continue(aContinuation, anyValue)
Python：PyPy的_continuation.continulet^[18]
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表达式书写的一个简单函数。需要支持适当尾调用，因为在续体传递风格下没有函数会返回，所有调用都是尾调用。

续体传递风格

续体被用于计算模型，包括λ演算^[19]、指称语义^[20]、演员模型^[21]和进程演算。这些模型仰仗于编程者或语义工程师书写数学函数时采用“续体传递风格”（continuation-passing style，简写为CPS）^[22]。这意味着每个函数都消费一个表示有关于这个函数调用的余下计算的函数。要返回一个值，这个函数以此返回值调用这个续体函数；要中止这个计算，它返回一个值。以续体传递风格书写程序的函数式编程者，获得了以任意方式操纵控制流程的表达能力。代价是他们必须手工维护控制和续体的不变条件，这通常是高度复杂的任务。

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

CPS的关键在于：所有函数都接受称为其续体的一个额外实际参数，并且在函数调用中的所有实际参数必须要么是一个变量，要么是一个λ表达式而非更复杂的表达式。这具有将表达式“从内至外”翻转的效果，由于表达式最内部分必须首先求值，因此CPS使得求值次序以及控制流程变得明确了。下面是在Scheme语言中仅使用其基本形式的几个例子，对比了直接风格代码和对应的CPS代码，这里约定了将续体函数表示为名为k的形式参数：

直接风格

续体传递风格

(define (pyth x y)
  (sqrt (+ (* x x) (* y y))))

(define (pyth& 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 (n*acc)
            (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))

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

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

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

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

以当前续体调用

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）的外部来调用。

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

立即返回

下面的例子中，使用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函数打印出来。

生成器

在下面的生成器代码中，call/cc被使用了两处：一处用于生成立即返回续体，而另一处用于遍历一个成员列表的迭代在暂停时保存恢复位置：

(define (generator-factory lst)
  (define (control-state return)
    (for-each 
      (lambda (element)
        (set! return (call/cc (lambda (resume-here)
          (set! control-state resume-here)
          (return element)))))
      lst)
    (return 'fell-off-the-end))
  (define (generator)
    (call/cc control-state))
  generator)

上述代码的简单用例：

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

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

(display-two-digits) ;; 分两行打印 0 和 1
(display-two-digits) ;; 分两行打印 2 和 fell-off-the-end

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

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

在下一次执行(generate-digit)之时，(call/cc control-state)将control-state所绑定的续体应用当前续体上，从而在迭代的(set! return (call/cc ……))之处恢复执行，它将传入的立即返回续体绑定到变量return上，此后继续这一次的迭代步骤。在遍历了列表的元素之后迭代结束，最终执行(return 'fell-off-the-end)，返回一个约定的文字（英语：Literal (computer programming)）常量。

协程

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)))))

上述代码的简单用例^[24]：

(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")
  ;; 调用调度过程，它采用FIFO，只要有任何其他线程等待，
  ;; 就取其中第一个线程运行，最终无等待者时结束。
  (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

引用与注释

^ Alonzo Church. The Calculi of Lambda-Conversion. Annals of Mathematics studies, no. 6. Lithoprinted. Princeton University Press, Princeton. 1941 [2021-09-24]. （原始内容存档于2022-05-19）.
^ Gerald J. Sussman, Guy L. Steele Jr. Lambda: The Ultimate Imperative. 1976 [2021-11-11]. （原始内容存档于2022-04-10）. “ Reynolds uses the term "continuation" in [Reynolds 72]. Church clearly understood the use of continuations; it is the only way to get anything accomplished at all in pure lambda calculus! For example, examine his definition of ordered pairs and triads on page 30 of [Church 41]. In SCHEME notation. this is:
  [M, N] means (LAMBDA (A) (A M N))
  2₁ means (LAMBDA (A) (A (LAMBDA (B C) B)))
  2₂ means (LAMBDA (A) (A (LAMBDA (B C) C)))
where 2₁ e.g. selects the first element of a pair. (Note that these functions are isomorphic to CONS, CAR, and CDR!) ”
^ Adriaan van Wijngaarden. Recursive Definition of Syntax and Semantics (PDF). 1966 [2024-02-24]. （原始内容存档 (PDF)于2024-02-24）.
^ IT History Society — Mr. Steve (Slug) Russell. [2024-02-24]. （原始内容存档于2024-02-24）.
^ Palmer, Luke. undo()? ("continuation sandwich" example). perl.perl6.language (newsgroup). June 29, 2004 [2009-10-04]. （原始内容存档于2013-06-06）.
^ Kent M. Pitman（英语：Kent Pitman）. The Revised Maclisp Manual. 1983, 2007 [2021-10-15]. （原始内容存档于2021-12-21）. Historically, (CATCH form) evolved to handle the fact that programmers were using (ERRSET (...(ERR)...)) to accomplish non-local returns since there was once no other way to get that functionality. CATCH and THROW were introduced so that programmers could write (CATCH (...(THROW val)...)) instead where there was really no error condition. However, it was found that confusion would often result using unlabelled CATCH/THROW because an unlablled CATCH could catch a throw it hadn't intended to. This is why named CATCH was invented. 请检查|date=中的日期值 (帮助)
Gerald J. Sussman, Guy L. Steele Jr.. Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 （英文）. CATCH － This is the "escape operator" which gives the user a handle on the control structure of the interpreter. The expression:
(CATCH <identifier> <expression>)
evaluates <expression> in an environment where <identifier> is bound to a continuation which is "just about to return from the CATCH"; that is, if the continuation is called as a function of one argument, then control proceeds as if the CATCH expression had returned with the supplied (evaluated) argument as its value. ……
As another example, we can define a THROW function, which may then be used with CATCH much as they are in LISP:
(DEFINE THROW (LAMBDA (TAG RESULT) (TAG RESULT)))
^ William Clinger, Daniel P. Friedman, Mitchell Wand. A scheme for a higher-level semantic algebra (PDF). 1985 [2021-10-14]. （原始内容存档 (PDF)于2022-01-21）.
^ Bruce Duba, Robert Harper, David MacQueen. Typing first-class continuations in ML (PDF). 1991 [2021-10-11]. （原始内容存档 (PDF)于2022-01-29）.
^ cl-cont. [2021-10-11]. （原始内容存档于2012-03-30）.
^ C# guide — Task asynchronous programming model — Threads. [2024-01-20]. （原始内容存档于2024-03-06）. Async methods are intended to be non-blocking operations. An await expression in an async method doesn't block the current thread while the awaited task is running. Instead, the expression signs up the rest of the method as a continuation and returns control to the caller of the async method.
^ Control.Monad.Cont. [2021-10-11]. （原始内容存档于2012-03-23）.
^ haxe-continuation. [2021-10-11]. （原始内容存档于2021-12-25）.
^ S. B. Wample, R. E. Griswold（英语：Ralph Griswold）. Co-expression in Icon*. The Computer Journal, Volume 26, Issue 1, Pages 72–78. 1983.
^ Lightwolf. [2021-10-11]. （原始内容存档于2021-10-26）.
^ javaflow （页面存档备份，存于互联网档案馆） (requires bytecode manipulation at runtime or compile time)
^ Coro. [2021-10-11]. （原始内容存档于2013-08-06）.
^ Continuity
^ _continuation.continulet. [2021-10-11]. （原始内容存档于2016-04-13）.
^ Michael J. Fischer（英语：Michael J. Fischer）. Lambda Calculus Schemata. In Proceedings of an ACM Conference on Proving Assertions about Programs (1972) 104–109. 1972. Definition 4.3: A schema p is safe if for every subformula of the form q = (q₀, q₁, …, q_n), either q₀∈ ${\mathcal {F}}$ or for all i, 0≤i≤n, q_i is a lambda-function, a constant or a variable.
Thus, in a safe schema, we prohibit the value returned by an application or conditional from being passed on to another function as an argument. It follows that such a value can never be evaluated and must eventually propagate to the top level to become the final result of the whole evaluation. One can then show:
Lemma 4.2: Let f be a safe lambda-function. Then fcn_d(f) = fcn_r(f).
We are now in a position to state the main theorem in precise terms.
Theorem I: Let f be any lambda function. We can effectively find a lambda-function f' such that fcn_d(f') = fcn_r(f') = fcn_r(f) for all interpretations.
Proof (sketch): By assumption, f = (λx₁…x_n.p) for some schema p with free variables x₁, …, x_n. Using well-known techniques, we can first find a schema p₁ such that …… .
We now define a function Φ to translate p₁ into a safe form p₂, and p₂ will be such that fcn_r((λx₁…x_n.p)) = fcn_d((λx₁…x_n.(p₂ (λx.x)))). We then take f' = (λx₁…x_n.(p₂ (λx.x))). ……
Thus, our idea is to modify the schema so that for any sub-lambda-function g, instead of g passing its result back to the caller, the caller is passed to g as an additional functional argument, g then applies the new argument to the result it used to return, thereby avoiding the necessity of returning immediately. ……
In the definition of Φ, we also use the auxiliary function Ψ which adds the new argument to a lambda-function and translates its body. ……
Examples:
⑴ Φ[x] = (λf.(f x)), x∈ ${\mathcal {X}}$ .
⑵ Φ[(x y)] = (λf.((λf.(f x)) (λh.((λf.(f y)) (λx.(h f x)))))), x,y∈ ${\mathcal {X}}$ .
⑶ Φ[(λx.a)] = (λf.(f (λgx.((λf.(f a)) g)))), x∈ ${\mathcal {X}}$ , a∈ $\mathrm {C}$ .
⑷ Ψ[(λx.a)] = (λgx.((λf.(f a)) g)), x∈ ${\mathcal {X}}$ , a∈ $\mathrm {C}$ .
^ John C. Reynolds. Definitional Interpreters for Higher-Order Programming Languages. 1972 [2024-02-24]. （原始内容存档于2024-02-24）. Now suppose we define an expression to be serious if there is any possibility that its evaluation might not terminate. Then a sufficient condition for order-of-application independence is that a program should contain no serious operands or declaring expressions.
Next, suppose that we can divide the functions which may be applied by our program into serious functions, whose application may sometimes run on forever, and trivial functions, whose application will always terminate. …… Then an expression will only be serious if its evaluation can cause the application of a serious function, and a program will be independent of order-of-application if no operand or declaring expression can cause such an application. ……
As can be seen with a little thought, the condition implies that whenever some function calls a serious function, the calling function must return the same result as the called function, without performing any further computation. But any function which calls a serious function must be serious itself. Thus by induction, as soon as any serious function returns a result, every function must immediately return the same result, which must therefore be the final result of the entire program.
Nevertheless, there is a method for transforming an arbitrary program into one which meets our apparently restrictive condition. …… Basically, one replaces each serious function f_old (except the main program) by a new serious function f_new which accepts an additional argument called a continuation. The continuation will be a function itself, and f_new is expected to compute the same result as f_old, apply the continuation to this result, and then return the result of the continuation, i.e.,
f_new(x₁, …, x_n, c) = c(f_old(x₁, …, x_n)).
This introduction of continuations provides an additional "degree of freedom" which can be used to meet our condition for order-of-evaluation independence. Essentially, instead of performing further actions after a serious function has returned, one imbeds the further actions in the continuation which is passed to the serious function.
^
Carl Hewitt, Peter Bishop, Irene Greif, Brian Smith, Todd Matson, Richard Steiger. Actor induction and meta-evaluation. 1973 [2022-11-15]. （原始内容存档于2022-11-15）. “For some years we have been constructing a series of languages to express our evolving understanding of the above semantic issues. The latest of these is called PLANNER-73. ……
We shall assume that the reader is familiar with advanced pattern matching languages such as SNOBOL4, CONVERT, PLANNER-71, QA4, and POPLER.
We shall use (%A M%) to indicate sending the message M to the actor A. We shall use [s1 s2 … sn] to denote the finite squence s1, s2, … sn. ……
Identifiers can be created by the prefix operator =. ……
An expression (=> pattern body) is an abbreviation for (receive(message pattern) body) where receive is a more general actor that is capable of bindinq elements of the action in addition to the message.
Evaluating
(%(=> pattern body) the-message%), i.e. sending
(=> pattern body) the-message,
will attempt to match the-message against pattern, If the-message is not of the form specified by pattern, then the actor is NOT-APPLICABLE to the-message. If the-message matches pattern, the body is evaluated.
……
Conceptually at least a new actor is created every time a message is sent. Consider sending to a target T a message M and a continuation C.
```
(send T
    (message M
        [#continuation C]))
```
The transmission (%T M%) is an abbreviation for the above where C is defaulted to be the caller. If target T is the following:
```
(receive
    (message the-body
        [#continuation =the-continuation])
    the-body)
```
then the the-body is evaluated in an environment where the-message is bound to M and the-continuation is bound to C.
……
Many actors who are executing in parallel can share the same continuation. They can all send a message [“return”] to the same continuation. ”
^ Gerald J. Sussman, Guy L. Steele Jr. Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 （英文）. It is always possible, ……to perform any calculation in this way: rather than reducing to its value, it reduces to an application of a continuation to its value (cf. [Fischer]). That is, in this continuation-passing programming style, a function always "returns" its result by "sending" it to another function.
^ Gerald J. Sussman, Guy L. Steele Jr. Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 （英文）. We believe that functional usage, where applicable (pun intended), is more perspicuous than continuation-passing.

^ 这组代码也可以选用冗余但普适的弹跳床（英语：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)))))

延伸阅读

Peter Landin. A Generalization of Jumps and Labels (PDF). Report. UNIVAC Systems Programming Research. Reprinted in Higher Order and Symbolic Computation, 11(2):125-143, 1998, with a foreword by Hayo Thielecke. August 1965.
Daniel Bobrow. A Model for Control Structures for Artificial Intelligence Programming Languages (PDF). IJCAI. 1973.
Carl Hewitt, Peter Bishop , Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence (PDF). IJCAI. 1973.
Christopher Strachey, Christopher P. Wadsworth. Continuations: a Mathematical semantics for handling full jumps. Technical Monograph PRG-11. Oxford University Computing Laboratory. Reprinted in Higher Order and Symbolic Computation, 13(1/2):135—152, 2000, with a foreword by Christopher P. Wadsworth. January 1974.
John C. Reynolds. Definitional Interpreters for Higher-Order Programming Languages. Proceedings of 25th ACM National Conference, pp. 717–740. Reprinted in Higher-Order and Symbolic Computation 11(4):363-397, 1998, with a foreword. 1972.
John C. Reynolds. On the Relation between Direct and Continuation Semantics. Proceedings of Second Colloquium on Automata, Languages, and Programming. LNCS Vol. 14, pp. 141–156. 1974.
Reynolds, John C. The Discoveries of Continuations (PDF). Lisp and Symbolic Computation. 1993, 6 (3/4): 233–248 [2021-10-11]. （原始内容存档 (PDF)于2022-03-20）.
Michael J. Fischer（英语：Michael J. Fischer）. Lambda-Calculus Schemata (PDF). LISP AND SYMBOLIC COMPUTATION: An International Journal, 6, 259–288. 1993 [2021-11-10]. （原始内容 (PDF)存档于2022-03-02）.
Gerald J. Sussman, Guy L. Steele Jr. Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. AI Memo 349, MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, December 1975. Reprinted in Higher-Order and Symbolic Computation 11(4):405-439, 1998, with a foreword. 1975 （英文）.
Robert Hieb, R. Kent Dybvig, Carl Bruggeman. Representing Control in the Presence of First-Class Continuations. Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 66–77.
Will Clinger, Anne Hartheimer, Eric Ost. Implementation Strategies for Continuations. Proceedings of the 1988 ACM conference on LISP and Functional Programming, pp. 124–131, 1988. Journal version: Higher-Order and Symbolic Computation, 12(1):7-45, 1999.
Christian Queinnec. Inverting back the inversion of control or, Continuations versus page-centric programming. SIGPLAN Notices 38(2), pp. 57–64. 2003.

外部链接

Continuations for Curmudgeons （页面存档备份，存于互联网档案馆） by Sam Ruby
Teach Yourself Scheme in Fixnum Days （页面存档备份，存于互联网档案馆） by Dorai Sitaram features a nice chapter on continuations.
Continuations and Stackless Python （页面存档备份，存于互联网档案馆） by Christian Tismer
Continuation, functions and jumps （页面存档备份，存于互联网档案馆）
http://okmij.org/ftp/continuations/ （页面存档备份，存于互联网档案馆） by Oleg Kiselyov
Haskell Continuation （页面存档备份，存于互联网档案馆）
Rhino With Continuations （页面存档备份，存于互联网档案馆）
Continuations in pure Java （页面存档备份，存于互联网档案馆） from the RIFE2 web application framework
Comparison of generators, coroutines, and continuations, source of the above example （页面存档备份，存于互联网档案馆）

[1] Alonzo Church. The Calculi of Lambda-Conversion. Annals of Mathematics studies, no. 6. Lithoprinted. Princeton University Press, Princeton. 1941 [2021-09-24]. （原始内容存档于2022-05-19）.

[lambda_paper_2-2] Gerald J. Sussman, Guy L. Steele Jr. Lambda: The Ultimate Imperative. 1976 [2021-11-11]. （原始内容存档于2022-04-10）. “ Reynolds uses the term "continuation" in [Reynolds 72]. Church clearly understood the use of continuations; it is the only way to get anything accomplished at all in pure lambda calculus! For example, examine his definition of ordered pairs and triads on page 30 of [Church 41]. In SCHEME notation. this is:
[M, N] means (LAMBDA (A) (A M N))
2₁ means (LAMBDA (A) (A (LAMBDA (B C) B)))
2₂ means (LAMBDA (A) (A (LAMBDA (B C) C)))
where 2₁ e.g. selects the first element of a pair. (Note that these functions are isomorphic to CONS, CAR, and CDR!) ”

[3] Adriaan van Wijngaarden. Recursive Definition of Syntax and Semantics (PDF). 1966 [2024-02-24]. （原始内容存档 (PDF)于2024-02-24）.

[4] IT History Society — Mr. Steve (Slug) Russell. [2024-02-24]. （原始内容存档于2024-02-24）.

[cont-sandwich-5] Palmer, Luke. undo()? ("continuation sandwich" example). perl.perl6.language (newsgroup). June 29, 2004 [2009-10-04]. （原始内容存档于2013-06-06）.

[6] Kent M. Pitman（英语：Kent Pitman）. The Revised Maclisp Manual. 1983, 2007 [2021-10-15]. （原始内容存档于2021-12-21）. Historically, (CATCH form) evolved to handle the fact that programmers were using (ERRSET (...(ERR)...)) to accomplish non-local returns since there was once no other way to get that functionality. CATCH and THROW were introduced so that programmers could write (CATCH (...(THROW val)...)) instead where there was really no error condition. However, it was found that confusion would often result using unlabelled CATCH/THROW because an unlablled CATCH could catch a throw it hadn't intended to. This is why named CATCH was invented. 请检查|date=中的日期值 (帮助)
Gerald J. Sussman, Guy L. Steele Jr.. Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 （英文）. CATCH － This is the "escape operator" which gives the user a handle on the control structure of the interpreter. The expression:
(CATCH <identifier> <expression>)
evaluates <expression> in an environment where <identifier> is bound to a continuation which is "just about to return from the CATCH"; that is, if the continuation is called as a function of one argument, then control proceeds as if the CATCH expression had returned with the supplied (evaluated) argument as its value. ……
As another example, we can define a THROW function, which may then be used with CATCH much as they are in LISP:
(DEFINE THROW (LAMBDA (TAG RESULT) (TAG RESULT)))

[7] William Clinger, Daniel P. Friedman, Mitchell Wand. A scheme for a higher-level semantic algebra (PDF). 1985 [2021-10-14]. （原始内容存档 (PDF)于2022-01-21）.

[8] Bruce Duba, Robert Harper, David MacQueen. Typing first-class continuations in ML (PDF). 1991 [2021-10-11]. （原始内容存档 (PDF)于2022-01-29）.

[9] -cont. [2021-10-11]. （原始内容存档于2012-03-30）.

[10] C# guide — Task asynchronous programming model — Threads. [2024-01-20]. （原始内容存档于2024-03-06）. Async methods are intended to be non-blocking operations. An await expression in an async method doesn't block the current thread while the awaited task is running. Instead, the expression signs up the rest of the method as a continuation and returns control to the caller of the async method.

[11] Control.Monad.Cont. [2021-10-11]. （原始内容存档于2012-03-23）.

[12] xe-continuation. [2021-10-11]. （原始内容存档于2021-12-25）.

[13] S. B. Wample, R. E. Griswold（英语：Ralph Griswold）. Co-expression in Icon*. The Computer Journal, Volume 26, Issue 1, Pages 72–78. 1983.

[14] Lightwolf. [2021-10-11]. （原始内容存档于2021-10-26）.

[15] vaflow （页面存档备份，存于互联网档案馆） (requires bytecode manipulation at runtime or compile time)

[16] Coro. [2021-10-11]. （原始内容存档于2013-08-06）.

[17] Continuity

[18] _continuation.continulet. [2021-10-11]. （原始内容存档于2016-04-13）.

[19] Michael J. Fischer（英语：Michael J. Fischer）. Lambda Calculus Schemata. In Proceedings of an ACM Conference on Proving Assertions about Programs (1972) 104–109. 1972. Definition 4.3: A schema p is safe if for every subformula of the form q = (q₀, q₁, …, q_n), either q₀∈ ${\mathcal {F}}$ or for all i, 0≤i≤n, q_i is a lambda-function, a constant or a variable.
Thus, in a safe schema, we prohibit the value returned by an application or conditional from being passed on to another function as an argument. It follows that such a value can never be evaluated and must eventually propagate to the top level to become the final result of the whole evaluation. One can then show:
Lemma 4.2: Let f be a safe lambda-function. Then fcn_d(f) = fcn_r(f).
We are now in a position to state the main theorem in precise terms.
Theorem I: Let f be any lambda function. We can effectively find a lambda-function f' such that fcn_d(f') = fcn_r(f') = fcn_r(f) for all interpretations.
Proof (sketch): By assumption, f = (λx₁…x_n.p) for some schema p with free variables x₁, …, x_n. Using well-known techniques, we can first find a schema p₁ such that …… .
We now define a function Φ to translate p₁ into a safe form p₂, and p₂ will be such that fcn_r((λx₁…x_n.p)) = fcn_d((λx₁…x_n.(p₂ (λx.x)))). We then take f' = (λx₁…x_n.(p₂ (λx.x))). ……
Thus, our idea is to modify the schema so that for any sub-lambda-function g, instead of g passing its result back to the caller, the caller is passed to g as an additional functional argument, g then applies the new argument to the result it used to return, thereby avoiding the necessity of returning immediately. ……
In the definition of Φ, we also use the auxiliary function Ψ which adds the new argument to a lambda-function and translates its body. ……
Examples:
⑴ Φ[x] = (λf.(f x)), x∈ ${\mathcal {X}}$ .
⑵ Φ[(x y)] = (λf.((λf.(f x)) (λh.((λf.(f y)) (λx.(h f x)))))), x,y∈ ${\mathcal {X}}$ .
⑶ Φ[(λx.a)] = (λf.(f (λgx.((λf.(f a)) g)))), x∈ ${\mathcal {X}}$ , a∈ $\mathrm {C}$ .
⑷ Ψ[(λx.a)] = (λgx.((λf.(f a)) g)), x∈ ${\mathcal {X}}$ , a∈ $\mathrm {C}$ .

[Reynolds72-20] John C. Reynolds. Definitional Interpreters for Higher-Order Programming Languages. 1972 [2024-02-24]. （原始内容存档于2024-02-24）. Now suppose we define an expression to be serious if there is any possibility that its evaluation might not terminate. Then a sufficient condition for order-of-application independence is that a program should contain no serious operands or declaring expressions.
Next, suppose that we can divide the functions which may be applied by our program into serious functions, whose application may sometimes run on forever, and trivial functions, whose application will always terminate. …… Then an expression will only be serious if its evaluation can cause the application of a serious function, and a program will be independent of order-of-application if no operand or declaring expression can cause such an application. ……
As can be seen with a little thought, the condition implies that whenever some function calls a serious function, the calling function must return the same result as the called function, without performing any further computation. But any function which calls a serious function must be serious itself. Thus by induction, as soon as any serious function returns a result, every function must immediately return the same result, which must therefore be the final result of the entire program.
Nevertheless, there is a method for transforming an arbitrary program into one which meets our apparently restrictive condition. …… Basically, one replaces each serious function f_old (except the main program) by a new serious function f_new which accepts an additional argument called a continuation. The continuation will be a function itself, and f_new is expected to compute the same result as f_old, apply the continuation to this result, and then return the result of the continuation, i.e.,
f_new(x₁, …, x_n, c) = c(f_old(x₁, …, x_n)).
This introduction of continuations provides an additional "degree of freedom" which can be used to meet our condition for order-of-evaluation independence. Essentially, instead of performing further actions after a serious function has returned, one imbeds the further actions in the continuation which is passed to the serious function.

[21] Carl Hewitt, Peter Bishop, Irene Greif, Brian Smith, Todd Matson, Richard Steiger. Actor induction and meta-evaluation. 1973 [2022-11-15]. （原始内容存档于2022-11-15）. “For some years we have been constructing a series of languages to express our evolving understanding of the above semantic issues. The latest of these is called PLANNER-73. ……
We shall assume that the reader is familiar with advanced pattern matching languages such as SNOBOL4, CONVERT, PLANNER-71, QA4, and POPLER.
We shall use (%A M%) to indicate sending the message M to the actor A. We shall use [s1 s2 … sn] to denote the finite squence s1, s2, … sn. ……
Identifiers can be created by the prefix operator =. ……
An expression (=> pattern body) is an abbreviation for (receive(message pattern) body) where receive is a more general actor that is capable of bindinq elements of the action in addition to the message.
Evaluating
(%(=> pattern body) the-message%), i.e. sending
(=> pattern body) the-message,
will attempt to match the-message against pattern, If the-message is not of the form specified by pattern, then the actor is NOT-APPLICABLE to the-message. If the-message matches pattern, the body is evaluated.
……
Conceptually at least a new actor is created every time a message is sent. Consider sending to a target T a message M and a continuation C.

(send T (message M [#continuation C]))

The transmission (%T M%) is an abbreviation for the above where C is defaulted to be the caller. If target T is the following:

(receive (message the-body [#continuation =the-continuation]) the-body)

then the the-body is evaluated in an environment where the-message is bound to M and the-continuation is bound to C.
……
Many actors who are executing in parallel can share the same continuation. They can all send a message [“return”] to the same continuation. ”

[22] Gerald J. Sussman, Guy L. Steele Jr. Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 （英文）. It is always possible, ……to perform any calculation in this way: rather than reducing to its value, it reduces to an application of a continuation to its value (cf. [Fischer]). That is, in this continuation-passing programming style, a function always "returns" its result by "sending" it to another function.

[23] Gerald J. Sussman, Guy L. Steele Jr. Scheme: An Interpreter for Extended Lambda Calculus. 维基文库. 1975 （英文）. We believe that functional usage, where applicable (pun intended), is more perspicuous than continuation-passing.

[24] 这组代码也可以选用冗余但普适的弹跳床（英语：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)))))

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]