續體

在電腦科學中，續體（英語：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（英語：Adriaan van Wijngaarden）在1964年9月作出。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]