電腦科學中,續體(英語:continuation,也譯作計算續體、續延、延續性),是對電腦程式控制狀態的一種抽象表示。續體實化了程式控制狀態。可以理解為,續體是一種數據結構,它表示在行程執行中給定點上的計算過程,所建立的數據結構可以被程式語言訪問,而不是被執行時環境所隱藏掉。這對實現程式語言的某些控制機制,比如例外處理協程生成器非常有用。

「當前續體」從執行代碼的角度看來,是可以從程式執行的當前點匯出的續體。續體還被用來提及「頭等續體」,它是一種構造,賦予程式語言儲存在任何點上的執行狀態的能力,並在程式中後來的點上可能多次返回到這一點。

歷史

Gerald J. SussmanGuy 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 704LISP實現的一個用戶,發明了續體來解決雙重遞歸英語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/NJval callcc : ('a cont -> 'a) -> 'a,這裏的'a cont是接受類型為'a的參數的續體的類型;callcc f應用f到當前續體,如果f以參數x呼叫這個續體,則如同(callcc f)返回x作為結果[8]

程式語言支援

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

在支援閉包和適當尾呼叫的任何程式語言中,都可能以續體傳遞風格書寫程式並手工實現call/cc。在續體傳遞風格下,call/cc成為了可以用lambda表達式書寫的一個簡單函數。需要支援適當尾呼叫,因為在續體傳遞風格下沒有函數會返回,所有呼叫都是尾呼叫。

續體傳遞風格

續體被用於計算模型,包括λ演算[19]指稱語意[20]演員模型[21]行程演算。這些模型仰仗於編程者或語意工程師書寫數學函數時採用「續體傳遞風格」(continuation-passing style,簡寫為CPS)[22]。這意味着每個函數都消費一個表示有關於這個函數呼叫的餘下計算的函數。要返回一個值,這個函數以此返回值呼叫這個續體函數;要中止這個計算,它返回一個值。以續體傳遞風格書寫程式的函數式程式設計者,獲得了以任意方式操縱控制流程的表達能力。代價是他們必須手工維護控制和續體的不變條件,這通常是高度複雜的任務。

以續體傳遞風格(CPS)書寫的函數接受一個額外的實際參數:顯式的續體,它是有一個實際參數的函數。當CPS函數已經計算出來其結果值的時候,它通過以這個值作為實際參數呼叫續體函數來「返回」它。這意味着在呼叫CPS函數的時候,呼叫者函數需要提供一個過程接受這個次常式的「返回」值。以這種形式表達代碼使得在直接風格中隱含的一些事物顯露出來。這包括了:過程返回變成了對續體的呼叫,中間值都有了給定名字,實際參數求值的次序變為顯見,而尾呼叫成為簡單的將傳遞給這個呼叫者的續體不修改的傳遞給被呼叫過程。

CPS的關鍵在於:所有函數都接受稱為其續體的一個額外實際參數,並且在函數呼叫中的所有實際參數必須要麼是一個變數,要麼是一個λ表達式而非更複雜的表達式。這具有將表達式「從內至外」翻轉的效果,由於表達式最內部份必須首先求值,因此CPS使得求值次序以及控制流程變得明確了。下面是在Scheme語言中僅使用其基本形式的幾個例子,對比了直接風格代碼和對應的CPS代碼,這裏約定了將續體函數表示為名為k的形式參數:

More information 直接風格, 續體傳遞風格 ...
直接風格
續體傳遞風格
(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))
Close

注意在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

參照與註釋

延伸閱讀

外部連結

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.