计算续体

在计算机科学和程序设计中，计算续体或简称续体（英語：continuation，也译作续延、延續性），是对计算机程序的控制状态的一种抽象表现。续体实化了程序状态信息。可以理解为，一个续体以数据结构的形式表现了程序在运行过程中某一点的计算状态，相应的数据内容可以被编程语言访问，而不是被运行时环境所隐藏掉。这对实现编程语言的某些控制机制，比如异常处理、协程、生成器非常有用。

续体包含了当前程序的栈（包括当前周期内的所有数据，也就是局部变量），以及当前运行的位置。一个续体的实例可以在将来用在控制流上，被调用时它从所表达的状态开始恢复执行。

头等续体[编辑]

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

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

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

Scheme是支持续体的第一个完全的生产系统，它最初提供了源自Maclisp的命名的catch/throw^[2]，后来提供了call/cc（英语：call-with-current-continuation）^[3]。Bruce Duba将callcc/throw介入到了SML/NJ^[4]。

续体还被用于计算模型，包括指称语义、演员模型、进程演算和lambda演算。这些模型依赖于编程者或语义工程师以所谓的续体传递风格（英语：continuation-passing style）书写数学函数。这意味着每个函数都消费表示与这个函数调用有关的余下计算的一个函数。要返回一个值，这个函数以一个返回值调用这个续体函数，来中止这个返回一个值的计算。

以续体传递风格（英语：continuation-passing style）书写程序的函数式编程者获得了以任意方式操纵控制流程的表达能力。代价是他们必须手工维护控制和续体的不变量，这通常是高度复杂的任务。

用例[编辑]

Scheme编程语言包括了控制算子call-with-current-continuation（英语：call-with-current-continuation）（简写为call/cc），Scheme程序可以通过它操纵控制流程：

 (define the-continuation #f)

 (define (test)
   (let ((i 0))
     ; call/cc调用它的第个实际参数，
     ; 将表示程序中此点的一个续体变量
     ; 作为实际参数传递给这个函数。
     ;
     ; 在这个案例下，函数实际参数将这个续体
     ; 赋值给变量the-continuation。
     ;
     (call/cc (lambda (k) (set! the-continuation k)))
     ;
     ; 下次调用续体的时候，在此处开始。
     (set! i (+ i 1))
     i))

下面使用上述定义的函数test，它设置the-continuation为自身的将来执行状态：

 > (test)
 1
 > (the-continuation)
 2
 > (the-continuation)
 3
 > ; 将当前续体（下次会打印4）存储起来
 > (define another-continuation the-continuation)
 > (test) ; 重置the-continuation
 1
 > (the-continuation)
 2
 > (another-continuation) ; 使用以前存储的续体
 4

协程[编辑]

Scheme实现协程是很轻易的，只需维护一个续体的队列。下面是使用续体将协程实现为独立线程的用例^[5]：

 ;;; 用于线程调度的一个朴素的队列。它持有“等待运行”的协程的列表。
   (define *queue* '())
   (define (empty-queue?)
     (null? *queue*))
   (define (enqueue x)
     (set! *queue* (append *queue* (list x))))
   (define (dequeue)
     (let ((x (car *queue*)))
       (set! *queue* (cdr *queue*))
       x))
   ;;; (fork prpc)启动一个新线程来运行(proc)。
   (define (fork proc)
     (call/cc
      (lambda (k)
        (enqueue k)
        (proc))))
   ;;; (yield)将处理器让给下一个线程，如果有的话。
   (define (yield)
     (call/cc
      (lambda (k)
        (enqueue k)
        ((dequeue)))))
   ;;; (thread-exit)终止当前线程，或整个程序如果没有其他线程剩下的话。
   (define (thread-exit)
     (if (empty-queue?)
         (exit)
         ((dequeue))))

上述定义的函数允许通过协作多任务定义和执行线程，线程yield控制权给队列中下一个线程：

   ;;; 干活的典型Scheme线程函数体。
   (define (do-stuff-n-print str)
     (lambda ()
       (let loop ((n 0))
         (format #t "~A ~A\n" str n)
         (yield)
         (loop (+ n 1)))))
   ;;; 建立两个线程，并启动运行它们。
   (fork (do-stuff-n-print "This is AAA"))
   (fork (do-stuff-n-print "Hello from BBB"))
   (thread-exit)

上述代码不停的产生如下这样的输出：

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

编程语言支持[编辑]

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

Common Lisp：cl-cont^[6]，还可以使用定制宏
C# / VB.NET：async和await^[7]
Factor：callcc0和callcc1
Haskell：在Control.Monad.Cont中的续体单子^[8]
Haxe：haxe-continuation^[9]
Icon / Unicon：create, suspend, @算子（coexpression）
Java：Lightwolf^[10]和javaflow^[11]
Kotlin：Continuation
JavaScript Rhino：Continuation
Parrot：Continuation PMC，对所有控制流程使用续体传递风格（英语：continuation-passing style）
Perl：Coro^[12]和Continuity^[13]
Pico（英语：Pico (programming language)）：call(exp())和 continue(aContinuation, anyValue)
Python：PyPy的_continuation.continulet^[14]
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 of New Jersey：SMLofNJ.Cont.callcc

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

引用[编辑]

^ 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）.
^ Haynes, C. T., Friedman, D. P., and Wand, M. 1984. Continuations and coroutines. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (Austin, Texas, United States, August 06–08, 1984). LFP '84. ACM, New York, NY, 293-298.
^ cl-cont. [2021-10-11]. （原始内容存档于2012-03-30）.
^ "sign up the rest of method as the continuation, and then return to your caller immediately; the task will invoke the continuation when it completes." Asynchronous Programming for C# （页面存档备份，存于互联网档案馆）
^ Control.Monad.Cont. [2021-10-11]. （原始内容存档于2012-03-23）.
^ haxe-continuation. [2021-10-11]. （原始内容存档于2021-12-25）.
^ 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）.

延伸阅读[编辑]

Peter Landin. A Generalization of Jumps and Labels Report. UNIVAC Systems Programming Research. August 1965. Reprinted in Higher Order and Symbolic Computation, 11(2):125-143, 1998, with a foreword by Hayo Thielecke.
Drew McDermott and Gerald Sussman. The Conniver Reference Manual MIT AI Memo 259. May 1972.
Daniel Bobrow: A Model for Control Structures for Artificial Intelligence Programming Languages IJCAI 1973.
Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
Christopher Strachey and Christopher P. Wadsworth. Continuations: a Mathematical semantics for handling full jumps Technical Monograph PRG-11. Oxford University Computing Laboratory. January 1974. Reprinted in Higher Order and Symbolic Computation, 13(1/2):135—152, 2000, with a foreword by Christopher P. Wadsworth.
John C. Reynolds. Definitional Interpreters for Higher-Order Programming Languages Proceedings of 25th ACM National Conference, pp. 717–740, 1972. Reprinted in Higher-Order and Symbolic Computation 11(4):363-397, 1998, with a foreword.
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）.
Gerald Sussman and Guy Steele. 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.
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.

外部链接[编辑]

ACM SIGPLAN Workshop on Continuations 2011 （页面存档备份，存于互联网档案馆） at the ICFP.
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
On-line proceedings of the Fourth ACM SIGPLAN Workshop on Continuations （页面存档备份，存于互联网档案馆）
On-line proceedings of the Second ACM SIGPLAN Workshop on Continuations
Continuation, functions and jumps （页面存档备份，存于互联网档案馆）
http://okmij.org/ftp/continuations/ （页面存档备份，存于互联网档案馆） by Oleg Kiselyov
https://wiki.haskell.org/Continuations
Rhino With Continuations
Continuations in pure Java from the RIFE web application framework
Debugging continuations in pure Java （页面存档备份，存于互联网档案馆） from the RIFE web application framework
Comparison of generators, coroutines, and continuations, source of the above example （页面存档备份，存于互联网档案馆）

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

[2] 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)))

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

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

[5] Haynes, C. T., Friedman, D. P., and Wand, M. 1984. Continuations and coroutines. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (Austin, Texas, United States, August 06–08, 1984). LFP '84. ACM, New York, NY, 293-298.

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

[7] "sign up the rest of method as the continuation, and then return to your caller immediately; the task will invoke the continuation when it completes." Asynchronous Programming for C# （页面存档备份，存于互联网档案馆）

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

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

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

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

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

[13] Continuity

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]