续体 - Wikiwand

在電腦科學中，續體（英語：continuation，也譯作計算續體、續延、延續性），是實化電腦程式的控制狀態的一種抽象表示。程式在運算過程中給定一個點，其「剩餘將要執行的部分」，即為「續體」。藉助程式語言中的續體特性，程式設計師不但能模組化地自訂迴圈、break陳述句、continue陳述句等基本控制結構；此外還能以更加簡練的方式實現更加複雜的控制結構或計算模式，例如：異常處理、生成器、協程、回溯、非確定性計算、概率編程、^[1]反向傳播演算法、可微分編程等^[2]。

概述

對一段程式 1 * (2 + 3) - 4 而言，若當前正在計算 2 + 3，這部份則稱為可約表達式（英語：redex; reducible expression）^[3]；而其餘的部分 1 * $[\cdot ]$ - 4 即是續體。這裡的符號 $[\cdot ]$ 被稱為「洞」，表示可約表達式之計算結果將要回填的地方，可視為佔位符。 ^[4]

續體的種類

續體的概念在任何程式語言中都會出現，而不同的程式語言之間的差別在於是否提供構造或是算子，以供顯示地捕捉跟恢復續體。不同種類的算子，亦有相異的抽象程度與表達能力。

頭等續體

若能將捕捉到的續體實化作為一般的值儲存與傳遞，便會稱其為頭等續體（英語：first-class continuations）。而當被捕捉的續體被呼叫時，程式的流程控制將會恢復到續體被捕捉時所在的地方。這賦予程式語言強大的執行順序控制能力。它可以跨越多個呼叫堆疊來返回結果，或者跳轉到此前已經退出了的函式。可以認為其儲存了程式的控制流程上下文，而需要注意的是這與行程映像（英語：System image）不同，它不儲存程式資料，只儲存控制流程上下文。這經常採用「續體三明治」譬喻來說明：

你正站在冰箱前，想要做一個三明治。
你就把這個情況變成一個續體，放入口袋裡。
接著，從冰箱裡拿出火雞肉和麵包做一個三明治，並坐到桌案前。
你啟用了口袋裡的續體。
這時發現自己再次站到了冰箱之前，想要一個三明治。
幸運的是，在桌案上就有一個三明治，而用於做三明治的材料都沒有了。你可以吃三明治了。^[5]

在這個譬喻中，三明治是一部份程式資料，比如在分配堆上一個對象，並非去呼叫「製做三明治」常式並等它返回，這裡呼叫「以當前續體製做三明治」常式，它建立一個三明治並在已脫離執行的續體所儲存的地方繼續執行。

多發及單發恢復

能夠恢復多次的多發續體（英語：multi-shot continuations），其表達能力比僅能恢復一次的單發續體（英語：one-shot continuations）還要強。單發續體能夠直接表達迴圈、例外處理、迭代器、生成器、協程等控制結構，而多發續體不僅僅是具備單發續體的能力，此外還能用在非確定性、回溯法、布林可滿足性問題、反向傳播這些單發續體無法直接表達的問題。 ^[6] ^[7]

然而，多發恢復的續體在編譯器及執行期系統的實現面臨著工程上的挑戰。為了實現多發恢復的語意，通常需要以複製呼叫堆疊實現，這也為多發續延帶來了一些效能負擔。考慮到這個原因，部分程式語言僅提供單發恢復，例如OCaml的Effect^[8]；也有程式語言實現提供了單發化版本的控制算子，例如Chez Scheme提供了call/1cc。^[9]而如何更高效地實現多發恢復，在近年來（2025）仍然是學者積極探討的問題。^[10]^[11]^[12]

學界也探討了單發有界續體與協程的關係。有堆疊的非對稱式協程，例如Lua所提供的協程，可以對應到單發有界續體。^[13]^[14]^[15]^[16]

Remove ads

歷史

Gerald J. Sussman和Guy L. Steele Jr.在1976年論文《Lambda之終極指令式》中，提及了John C. Reynolds（英語：John C. Reynolds）在1972年的論文《高階程式語言的定義性直譯器》中採用了術語「續體」^[17]，並認定Alonzo Church在1941年著作《Lambda轉換的演算》裡^[18]，已經清晰的理解了「續體」的使用，這是用純λ演算徹底完成所有事情即邱奇編碼的唯一方式，並舉出其中有序對定義所對應的Scheme表示為例^[19]：

(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年的論文《續體的發現》中給出了發現續體的完整歷史^[20]。Reynolds認為續體的最早描述由Adriaan van Wijngaarden在1964年9月作出。van Wijngaarden在奧地利的維也納附近巴登召開的關於「形式語言描述語言」的IFIP（英語：International Federation for Information Processing）工作會議上，在關於ALGOL 60 預處理器的公式化（英語：Formulation）的論文《語法和語意的遞迴定義》中，倡導通過將真正（proper）過程變換成續體傳遞風格而消除標籤和goto語句^[21]，但是他沒有使用「續體」這個名字。

Christopher Strachey、Christopher P. Wadsworth和John C. Reynolds（英語：John C. Reynolds），在指稱語意領域的工作中突出了術語「續體」，此間廣泛利用續體來允許使用函數式程式設計語意來分析順序程式。

Steve Russell為他給IBM 704的LISP實現的一個使用者，發明了續體來解決雙重遞迴（英語：Double recursion）問題^[22]，但是他沒有為其命名。

Scheme是支援續體的第一個完全的生產系統，它最初提供了源自Maclisp的用於例外處理的命名catch/throw^[23]，在1985年，Daniel P. Friedman、Mitchell Wand（英語：Mitchell Wand）和William Clinger（英語：William Clinger (computer scientist)）提供了頭等續體算子call-with-current-continuation（英語：call-with-current-continuation）（簡寫為call/cc）^[24]。

在1991年，Bruce Duba等人將callcc介入到了SML/NJ： val callcc : ('a cont -> 'a) -> 'a，這裡的'a cont是接受類型為'a的參數的續體的類型；callcc f應用f到當前續體，如果f以參數x呼叫這個續體，則如同(callcc f)返回x作為結果^[25]。

Remove ads

續體傳遞風格

續體的概念主要起源於計算模型研究，比如λ演算^[26]、指稱語意^[17]和演員模型^[27]。這些模型仰仗於編程者或語意工程師書寫數學函式時採用「續體傳遞風格」（continuation-passing style，簡寫為CPS）^[28]。續體傳遞風格（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函式原語^[29]，比如將前面的階乘函式寫為：

(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)…)))^[30]。此外，Haskell提供了函式複合算子。

Remove ads

以當前續體呼叫

小步語意

C[\operatorname {callcc} (\lambda k.\,e)]\;\to \;C[(\lambda k.\,e)(\lambda x.\,C[x])]

C[\operatorname {throw} (\lambda x.\,k)\,v]\;\to \;(\lambda x.\,k)\,v

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

Scheme程式語言範例

立即返回

下面的例子中，使用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應用於聚集（aggregate）即這裡的列表'(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)）常數。

協程

call/cc還可以表達其他複雜的原始運算。下面的代碼使用續體達成協同運作式多工的使用者級執行緒，亦稱為協程：

(define *ready-list* '())

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

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

(define (schedule)
  (let loop ()
    (if (not (null? *ready-list*)) (begin
      (yield)
      (loop)))))

這裡的全域變數*ready-list*是就緒執行緒列表，它儲存處於脫離狀態的就緒執行緒的重入續體；在選擇重入執行緒的時候，將就緒執行緒列表頭部的續體從列表中取出，並應用它以重入對應執行緒。退讓過程yield，擷取對應於呼叫者的當前續體，將其追加到就緒執行緒列表的尾部，取出並應用就緒執行緒列表頭部的續體而使本執行緒脫離執行。

分叉過程fork，接受一個函式fn和相應的參數列args，它首先擷取自身的當前續體並將其添加到就緒執行緒列表的頭部；然後呼叫退讓過程yield，從而建立了一個用來建立工人（worker）執行緒的執行緒，接著取出並應用就緒執行緒列表頭部的續體而使本執行緒脫離執行；由於分叉過程自身的續體已經添加到了就緒執行緒列表頭部，重入它而隨即結束分叉過程的這次呼叫。當重入這個建立工人執行緒的執行緒之時，呼叫函式fn，預期這個函式在自身之中呼叫退讓過程yield，從而建立重入函式fn內部的工人執行緒。當工人執行緒最終並未呼叫退讓過程而從函式fn直接退出回到分叉過程之時，必須接著以取出並應用就緒執行緒列表頭部的續體的方式來結束這個工人執行緒，因為對分叉過程的呼叫早已結束。

排程過程schedule，持續檢測就緒執行緒列表，只要有任何其他執行緒等待就呼叫退讓過程yield，取出並應用就緒執行緒列表頭部的續體而使本執行緒脫離執行，最終在無就緒者等待之時結束。排程過程在每一輪並行執行迴圈中只執行一次。排程過程在所有分叉過程之後呼叫，它起到的根本作用是充當會合點，即並行執行的多個執行緒中的最終剩下的唯一執行緒，防止出現不介入排程過程轉而完全由工人執行緒自行排程，會有可能最終會合於某個不處在最後的分叉過程的非預期情況。

上述代碼的簡單用例：

(import (srfi 28))

(define (echo-string-n-times str n)
  (let loop ((i 0))
    (if (< i n) (begin
      (display (format "~a ~a~%" str i))
      (yield)
      (loop (+ i 1))))))

(define (main)
  (fork echo-string-n-times "This is AAA" 3)
  (fork echo-string-n-times "Hello from BBB" 2)
  (schedule))

(main)

其輸出為：

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

最後演示對上述協程代碼的一種變化：將退讓過程yield改成具有返回值，呼叫了退讓過程的分叉過程fork也相應更改；將排程過程schedule改為採用彈跳床（英語：trampoline (computing)）策略，它與前面代碼的區別在於將排程過程自身的續體添加到就緒執行緒列表的頭部；並為排程過程增加了一個函式參數fn，用這個函式來處理工人執行緒的返回值。這種排程過程也可以改名為分派過程dispatch：

(define *ready-list* '())

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

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

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

下面是其用例：

(import (srfi 28))

(define (echo-string-n-times str n)
  (let loop ((i 0))
    (if (< i n) (begin
      (yield (format "~a ~a~%" str i))
      (loop (+ i 1))))))

(define (main)
  (fork echo-string-n-times "This is AAA" 3)
  (fork echo-string-n-times "Hello from BBB" 2)
  (schedule display))

(main)

程式語言的直接支援

很多程式語言以各種名義體現出頭等續體，特別是：

Common Lisp：cl-cont^[31]，還可以使用客製化宏

Factor：callcc0和callcc1
Haskell：在Control.Monad.Cont中的續體單子^[32]
Haxe：haxe-continuation^[33]
Icon / Unicon：suspend，coexpression：create與@算子^[34]
Java：Lightwolf^[35]和javaflow^[36]
Kotlin：Continuation
Parrot：Continuation PMC，對所有控制流程使用續體傳遞風格
Perl：Coro^[37]和Continuity^[38]
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表達式書寫的一個簡單函式。需要支援適當尾呼叫，因為在續體傳遞風格下沒有函式會返回，所有呼叫都是尾呼叫。

參見

續體傳遞風格
有界續體（英語：Delimited continuation）
Chicken：基於續體傳遞風格底層機制而實現的Scheme，它具有叫做F-operator的包含有界續體（英語：Delimited continuation）算子的蛋擴充^[39]。

參照與注釋

Loading content...

延伸閱讀

Loading content...

外部連結

Loading content...

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads