续体 - 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）的論文《語法和語意的遞歸定義》中^[21]，倡導通過將真正（proper）過程變換成續體傳遞風格而消除標籤和goto陳述式^[22]，但是他沒有使用「續體」這個名字。

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

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

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

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

Remove ads

續體傳遞風格

續體的概念主要起源於計算模型研究，比如λ演算^[27]、指稱語意^[17]和演員模型^[28]。這些模型仰仗於編程者或語意工程師書寫數學函數時採用「續體傳遞風格」（continuation-passing style，簡寫為CPS）^[29]。續體傳遞風格（CPS）意味着編程中用到的每個函數，都接納並於結束時應用一個表示有關於這個函數呼叫的餘下計算的函數。表達式（英語：Expression (computer science)）的最內部份必須首先求值，將表達式轉換為續體傳遞風格等價者，比如Michael J. Fischer（英語：Michael J. Fischer）在1972年所舉的例子^[27]：將 ${\textstyle \;(f\ (g\ (h\ a)))\;}$ 變換成 ${\textstyle \;({\hat {h}}\ (\lambda x\ .\ ({\hat {g}}\ (\lambda y\ .\ (f\ y))\ x))\ a)\;}$ ，具有將表達式「從內至外」翻轉的效果，從而使求值次序以及控制流程變得更加明確。

下面是Standard ML中的高階函數 foldr和map的續體傳遞風格實現，和達成一個整數列表的合計函數的簡單用例^[30]：

fun foldr' f b l = let
    fun cf ([], k) = k b
      | cf (a :: r, k) = cf (r, fn x => k (f (a, x)))，
    in
        cf (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

所有CPS函數比如這裏的cf，都接受一個額外的實際參數比如這裏的k，它被稱為續體。在CPS函數呼叫中的所有實際參數，必須要麼是一個λ表達式比如這裏fn x => k (f (a, x))，它將續體k應用於函數f的部份應用，要麼是一個變量比如這裏的l和r，而不能是更複雜的表達式。當CPS函數已經計算出來其結果值的時候，它通過以結果值作為實際參數呼叫續體函數來返回它，比如這裏的cf ([], k) = k b，在計算的任何步驟中只要直接返回結果值就會終止整個計算。一個函數比如這裏的foldr'，要呼叫CPS函數比如這裏的cf，就必須提供一個函數比如這裏的fn x => x，用來接受它所呼叫的CPS函數的結果值。

對於輸入[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)…)))。此外，建立在惰性求值和柯里化之上的Haskell提供了函數複合算子。

下面是在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))

對於函數式程式設計者而言，以續體傳遞風格表達代碼使得在直接風格中隱含的一些事物顯露出來，這包括了：過程返回變成了對續體的呼叫，中間值都有了給定名字，實際參數求值的次序變為顯見，而尾呼叫變成將傳遞給這個呼叫者的續體不加修改的傳遞給被呼叫過程。

這裏翻轉條件表達式的方式類似於Smalltalk中遵循邱奇布林值編碼的條件執行控制結構：

result := a > b
  ifTrue: [ 'greater' ]
  ifFalse: [ 'less or equal' ]

注意在CPS版本的代碼中，使用的函數原語（functional primitive）^[31]，比如這裏的*&、+&、-&、=&和sqrt&，自身也是CPS而非直接風格，所以要使得上述例子在Scheme系統中執行，就必須寫出這些函數原語的CPS版本，例如=&定義為：

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

一般編程在寫CPS函數之時，經常不採用CPS函數原語^[32]，比如將前面的階乘函數寫為：

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

要在REPL或直接風格函數中呼叫CPS函數，必須提供接受CPS函數計算結果的一個續體，比如恆等函數：

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

採用續體傳遞風格使函數式程式設計者能獲得以任意方式操縱控制流程的表達能力，代價是手工維護控制續體通常是高度複雜的任務。終極解決方案是用Scheme寫一組轉換常式，將Scheme的直接風格表達式（英語：Expression (computer science)）轉換成CPS表達式^[33]，下面的例子僅將直接風格函數原語轉換成CPS函數原語：

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

這裏的reverse函數反轉LISP列表所用的單向鏈結串列，其首次應用將原來尾部元素反轉到了首部，接着取出這個元素應用並再次應用reverse函數將餘下諸元素反轉成原來次序。apply（英語：apply）函數的應用(apply f args)，以args列表的諸元素作為實際參數呼叫f函數^[34]，eval函數和apply函數是元循環求值器的兩大中心構件^[35]。

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）。call/cc所建立的續體是頭等對象，具有函數應用（英語：Function application）作為其唯一的運算，這種續體有着無限制的時效範圍（英語：Extent）（extent）^[36]，可以被儲存在變量或數據結構之中，它可以按需要多次呼叫。

在call/cc的呼叫(call/cc f)中的函數f，接受當前續體作為其唯一實際參數。在後續執行中將這個續體應用於一個實際參數之時，此刻生效的續體被捨棄，轉而使用所應用的這個續體，控制流程將在這個續體被擷取的那一點上繼續，而傳遞給這個續體的實際參數則變成這個call/cc呼叫的返回值。

Scheme程式語言範例

立即返回

下面的例子中，使用call/cc來模擬C風格語言中的return陳述式：

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

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

(call/cc f)
=> 2

第一個演示，以恆等函數(lambda (x) x)作為實際參數呼叫函數f，函數f將繫結到形式參數return上的恆等函數應用於2，接着執行最後一個表達式3，從而函數f返回3。第二個演示，將call/cc應用於函數f，函數f將繫結到形式參數return上的續體應用於2，這在控制流程上等價於非局部跳轉回到呼叫(call/cc f)的那一點上，將其代換（英語：Substitution (logic)）為返回值2。

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*是就緒線程列表，它儲存處於脫離（detached）狀態的就緒線程的重入續體；在選擇重入線程的時候，將就緒線程列表頭部的續體從列表中取出，並應用它以重入對應線程。退讓過程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
      (fn (call/cc (lambda (return)
        (let ((cont (car *ready-list*)))
          (set! *ready-list* (cons return (cdr *ready-list*)))
          (cont #f)))))
      (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^[37]，還可以使用客製化宏

Factor：callcc0和callcc1
Haskell：在Control.Monad.Cont中的續體單子^[38]
Haxe：haxe-continuation^[39]
Icon / Unicon：suspend，coexpression：create與@算子^[40]
Java：Lightwolf^[41]和javaflow^[42]
Kotlin：Continuation
Parrot：Continuation PMC，對所有控制流程使用續體傳遞風格
Perl：Coro^[43]和Continuity^[44]
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

參見

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

參照與註釋

Loading content...

延伸閱讀

Loading content...

外部連結

Loading content...

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads