Future與promise

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

電腦科學中,futurepromisedelaydeferred,是在某些並行程式語言中,指稱用於同步程式執行英語Execution (computing)的一種構造。由於某些計算尚未結束,故而需要一個對象來代理這個未知的結果。這種構造起源於函數式程式設計和相關範式邏輯編程,其目的是將值與其運算過程解耦,從而允許更靈活地進行計算,特別是通過將其並列化來進行。後來它在分散式計算中得到了應用,用來減少網路通訊往返的延遲。再後來async/await語法機制使其變得更有用,籍此允許以直接風格編寫非同步程式,而不再採用續體傳遞風格

術語[編輯]

在1976年Daniel P. Friedman和David Wise提出了術語「promise」[1],同年Peter Hibbard稱之為「eventual」[2]。1977年Henry Baker英語Henry Baker (computer scientist)Carl Hewitt英語Carl Hewitt在一篇論文中介紹了一個類似的概念「future」[3]

術語「future」、「promise」、「delay」和「deferred」通常用來稱謂同樣一種機制,在特定實現中可能只選用其中之一。在這種情況下,值與其運算過程是一起建立並且相互關聯的:future若指稱推遲設定的一個值[4],設定它的函式就可稱謂為promise;promise若指稱推遲設定的一個值[5],設定它的函式就可稱謂為resolver;promise若指稱一個非同步函式[1],它的結果值所設定的就可稱謂為future。設定一個推遲值也稱為「決定/解決」(resolve)、「履行/實現」(fulfil)或「繫結」(bind)它。

推遲值及其設定者也存在區分稱謂而同時使用的情況,二者的這種用法在不同實現中的差異將在專門章節中討論。具體來說,future指稱一個「唯讀」的變數的預留位置視圖,而promise指稱一個可寫的單賦值容器,使用其「成功」方法來設定這個future的值[6]。尤其是在定義future之時,無須指定設定其值的promise;並且可能有不同的promise,設定同一個future的值;但是對於一個給定future,僅可以進行一次設定。

歷史[編輯]

future及/或promise構造,首先實現於程式語言例如MultiLisp英語MultiLisp[4]Act 1之中。在並行邏輯編程英語Concurrent logic programming語言中,使用非常類似於future的邏輯變數進行通訊[7]。這種語言開始於1982年的「Prolog with Freeze」和「IC Prolog」,並且在後來的語言中變成了真正的並行原語,比如Concurrent PrologParlog英語Parlog守衛霍恩子句(GHC)、Strand英語Strand (programming language)Janus英語Janus (concurrent constraint programming language)Oz(Mozart)和Alice ML英語Alice (programming language)[8][9]。叫做「I-變數」的單賦值變數,非常類似於並行邏輯變數,它起源於資料流程編程語言Id英語Id (programming language)的「I-結構」元件[10],並且包含在Reppy的Concurrent ML[11]

在1988年Barbara Liskov和Liuba Shrira,發明了promise管線技術來克服傳輸延遲[5];Liskov和Shrira在論文中使用了術語「promise」,但是他們採用了現在少見的名稱「call-stream」來提及管線機制。在大約1989年Mark S. Miller英語Mark S. Miller、Dean Tribble和Rob Jellinghaus,於Xanadu專案中也獨立發明了此技術[12]

Liskov和Shrira的論文中描述的設計,以及Xanadu中的promise管線的實現,都有一個限制,即promise值不是頭等的:call或send的參數或返回值,不能直接是promise。在Liskov和Shrira論文中使用的程式語言Argus,直至大約1988年停止開發,似乎都未曾在任何公開發布中實現promise和call-stream[13][14]。Xanadu實現的promise管線,僅在1999年Udanax Gold的原始碼發布時才公開發布[15],並且在任何已發布的文件中都沒有解釋過[16]

一些早期的演員語言,包括Act系列[17][18],支援並列訊息傳遞和管線式訊息處理,但不支援promise管線。Joule英語Joule (programming language)E語言的後續實現,支援完全頭等的promise和resolver,還有promise管線。

2000年之後,由於訊息模式英語Messaging pattern請求-回應模型,在使用者介面回應力英語ResponsivenessWeb開發中的應用,future和promise重新引起了人們的興趣。現在一些主流語言對future和promise有了語言支援,最著名的是2004年發行的Java 5中的FutureTask[19],以及2012年發行的.NET框架 4.5中的async/await結構[20][21],它在很大程度上受到可追溯到2007年的「F#非同步編程模型」的啟發[22][23]async/await隨後被其他語言採用,特別是2014年的Dart 1.9[24]、2014年發行的HackHHVM)、2015年的Python 3.5[25]ECMAScript 2017、2019年的Rust 1.39和C++20等。

實現列表[編輯]

程式語言支援[編輯]

下面列出支援future、promise和並行邏輯變數、資料流程變數或I-變數的語言,包括直接在語言中支援還有在標準庫中支援:

還支援promise管線的語言套件括:

非標準庫的實現[編輯]

自行實現[編輯]

future可以用協程生成器實現[25],從而具有相同的求值策略(例如協同多工或延遲求值)。

future還可以很容易地用通道實現:future是一個單元素的通道,而promise是一個傳送到通道,實現future的過程。這允許future在支援通道(如CSPGo)的並行程式語言中實現[103]。由此產生的future是顯式的,因為它們必須通過從通道讀取而不是僅僅通過求值來取得。

程式語言典型範例[編輯]

Python[編輯]

Pythonconcurrent.futures模組,提供了非同步英語Asynchrony (computer programming)執行英語Execution (computing)可呼叫對象的高層介面。非同步執行可以使用執行緒池執行器ThreadPoolExecutor,通過多個執行緒來進行;或使用行程英語Pool (computer science)執行器ProcessPoolExecutor,通過分立的多個行程來進行。concurrent.futures.Future封裝了可呼叫對象的非同步執行,其實例由執行器抽象類Executor的這兩個子類的submit()方法建立[41]

在下面的例子中,定義了load_url(),用來檢索一個URL所指定的單一網頁並報告其內容。使用with語句指定採用執行緒池執行器,這確保了執行緒由它及時清理。用這個執行器的submit()方法啟動所有的裝載操作任務,並使用字典推導式為其建立的每個future標記上對應的URL。採用模組函式as_completed(),在指定的Future類的諸實例「已齊全」(completed)之時,建立在其上的迭代器

import concurrent.futures
import urllib.request

URLS = [
    'https://www.python.org/',
    'https://pypi.org/search/',
    'https://no-such-url'
    ]

def load_url(url, timeout):
    with urllib.request.urlopen(url, timeout=timeout) as conn:
        return conn.read()

with concurrent.futures.ThreadPoolExecutor() as executor:
    future_to_url = {executor.submit(load_url, url, 60) : url for url in URLS}
    for future in concurrent.futures.as_completed(future_to_url):
        url = future_to_url[future]
        try:
            data = future.result()
        except Exception as exc:
            print(f'{url!r} generated an exception: {exc!s}')
        else:
            print(f'{url!r} page is {len(data):d} bytes')

CPython中,由於全域直譯器鎖(GIL),保證一時只有一個執行緒可以執行Python位元組碼;一些擴充模組被設計為在進行計算密集任務時釋放GIL,還有在進行I/O時總是釋放GIL。執行緒池執行器的max_workers參數的預設值是min(32, os.cpu_count() + 4),這個預設值為I/O踴躍英語I/O bound任務保留至少5個worker執行緒,為釋放GIL的CPU踴躍任務利用最多32個CPU邏輯核心。想要更好利用多核心機器的計算資源,可以使用行程池執行器或多行程模組multiprocessing。對於同時執行多個I/O踴躍英語I/O bound任務,仍然適合採用執行緒池執行器或執行緒模組threading

Python的非同步I/O模組asyncio,是採用async/await語法編寫並行代碼的庫[104]asyncio模組基於低層事件迴圈,提供的高層API包括了:並行執行Python協程並擁有在其執行上的完全控制,進行網路IOIPC,控制子行程,通過佇列分布任務英語Task (computing)同步並行代碼。asyncio模組的同步原語,在設計上類似於threading模組的同步原語,但與之相比有兩個重要差異:asyncio模組的同步原語不是執行緒安全的,故而不能用於OS執行緒同步;這些同步原語的方法不接受逾時英語Timeout (computing)實際參數。

asyncio模組提供的低層API中有asyncio.Future對象,用來橋接低層基於回呼的代碼和高層採用async/await語法的代碼,它在設計上模仿了concurrent.futures.Future對象。這兩個模組的Future對象的set_result()方法標記這個Future對象為「已完畢」(done)並設定它的結果,而set_exception()方法標記這個Future對象為已完畢並設定一個例外;done()方法在這個Future對象已完畢時返回Trueresult()方法返回這個Future對象所設定的結果,或者引發其所設定的例外

二者的關鍵差異包括了:asyncio.Future是可期待(awaitable)對象,而concurrent.futures.Future對象不可以被期待(awaited)。asyncio.Future.result()不接受逾時實際參數,如果此刻這個Future對象的結果仍不可獲得,它引發一個InvalidStateError例外;而concurrent.futures.Future.result(),可接受逾時英語Timeout (computing)timeout)實際參數,如果此刻結果仍未「完全」(completed),它等待指定時間後若仍未完全則引發TimeoutError例外,如果逾時未指定或指定為None,則對等待時間沒有限制。

JavaScript[編輯]

JavaScript中,Promise對象表示一個非同步英語Asynchrony (computer programming)運算的最終完成或失敗,及其結果值或失敗理由。Promise對象是對一個值的代理(proxy),這個值在建立這個promise之時不必需已知。promise允許為非同步行動的最終成功值或失敗理由關聯上處理器,這使得非同步方法像同步方法那樣返回值:並非立即返回最終值,非同步方法返回一個promise來在將來的某一點上提供這個值。

在JavaScript生態系統中,Promise對象在成為語言本身的一部份之前很久就有了多種實現[105]。儘管各有不同的內部表示,至少幾乎所有類似Promise的對象都實現了「可接續」(thenable)介面[59]。可接續對象實現了.then()方法,Promise對象就是可接續的。

一個promise被稱為已落定(settled),如果它要麼已履行(fulfilled)要麼已拒絕(rejected),而不再待定(pending)。Promise實例的.then()方法,接受一到二個實際參數,它們是作為處理器非同步執行的回呼函式,分別針對了這個promise的已履行和已拒絕情況;此方法返回一個新的promise,它決定(resolve)出其所呼叫處理器的返回值,或者在原來這個promise未被處理的情況下,仍決定出其已落定的值。Promise實例的.catch()方法,實際上就是置空針對已履行情況的回呼函式,而只有針對已拒絕情況的回呼函式的.then()方法。

Promise()構造子建立Promise對象,它主要用於包裝仍基於回呼的API所提供的非同步英語Asynchrony (computer programming)運算,要注意它只能通過new算子來構造:new Promise(executor)Promise()構造子的實際參數叫做「執行器」(executor),它是由這個構造子同步執行的一個函式,它有可自行指定名字的兩個函式形式參數,比如指定為resolveFuncrejectFunc,這兩個函式接受任何類型的單一實際參數。

Promise()構造子返回的Promise對象,在要麼resolveFunc函式要麼rejectFunc函式被呼叫之時,它就成為「已決定」(resolved)的。要注意如果在呼叫這兩個函式之一的時候,將另一個Promise對象作為實際參數傳遞給它,則這個Promise對象可以稱為已決定但仍未落定。在執行器中有任何錯誤丟擲,都會導致這個promise成為已拒絕狀態,而返回值會被忽略。

Promise類提供四個靜態方法來實施非同步任務英語Task (computing)並行,其中的Promise.allSettled()方法,接受有多個promise的可迭代對象作為輸入,當所有輸入的promise都已落定之時,返回一個單一的已履行的Promise對象,它決定出描述每個輸入promise的結果的一個對象陣列;其中每個對象都有status屬性,它是字串"fulfilled"或者"rejected";還有在status"fulfilled"時出現的屬性value,或者在status"rejected"時出現的屬性reason

在下面例子中,全域fetch()方法,啟動從網路上取回一個資源的過程,並返回一旦回應可獲得就履行的一個promise;這個promise決定出表示對這個請求回應的一個Response對象,它只在遇到網路錯誤之時拒絕。Response.text()方法返回一個promise,它決定出這個回應的主體的一個文字表示。

const urls = [
  'https://developer.mozilla.org/',
  'https://javascript.info/promise-api',
  'https://no-such-url'
];

const fetchPromises = urls.map((url) => fetch(url));

Promise.allSettled(fetchPromises)
  .then((results) => { 
    results.forEach((result, num) => {
      if (result.status == "fulfilled") {
        if (result.value.ok) { 
          result.value.text()
            .then((data) => {
              console.log(`${urls[num]}: ${data.length} bytes`);
            })
            .catch((err) => {
              console.error(err);
            });
        } 
        else {
          console.log(`${urls[num]}: ${result.value.status}`);
        }
      }
      else if (result.status == "rejected") {
        console.error(`${urls[num]}: ${result.reason}`);
      }
    });
  });

JavaScript是天然的單執行緒的,所以在給定時刻只有一個任務英語Task (computing)執行英語Execution (computing),但控制可以在不同的promise之間轉移,使得多個promise表現為並行執行。在JavaScript中並列執行只能通過分立的worker後台執行緒來完成[106]

同基於promise的代碼合作的一種更簡單的方式,是使用async/await關鍵字。在函式開始處增加async,使其成為非同步函式,非同步英語Asynchrony (computer programming)函式總是返回一個promise。在非同步函式中,可以在對返回一個promise的函式的呼叫之前,使用await關鍵字;這使得代碼在這一點上等待直到這個promise已落定下來,然後在這一點上promise的已履行的值被當作返回值,而已拒絕的理由被作為例外丟擲。可以使用try...catch塊進行例外處理,就如同這個代碼是同步的一樣。

唯讀視圖[編輯]

在某些程式語言(如OzEAmbientTalk英語AmbientTalk)中,可以獲得推遲值的「唯讀視圖」,允許在解決(resolve)出這個值之後通過它來讀取,但不允許通過它來解決這個值:

  • 在Oz語言中,!!運算子用於獲得唯讀視圖。
  • 在E語言和AmbientTalk中,推遲值由一對稱為「promise/resolver對」的值表示。promise表示唯讀視圖,需要resolver來設定推遲值。
  • 在C++11中,std::future提供了一個唯讀視圖。該值通過使用std::promise直接設定,或使用std::packaged_taskstd::async設定為函式呼叫的結果。
  • 在Dojo Toolkit的1.5版本的Deferred API中,「僅限consumer的promise對象」表示唯讀視圖。[107]
  • Alice ML英語Alice (programming language)中,future提供「唯讀視圖」[27],而promise包含future和解決future的能力[108]
  • 在.NET 4.0中,System.Threading.Tasks.Task<T>表示唯讀視圖。解決值可以通過System.Threading.Tasks.TaskCompletionSource<T>來完成。

對唯讀視圖的支援符合最小特權原則,因為它使得設定值的能力僅限於需要設定該值的主體。在同樣支援管線的系統中,非同步訊息(具有結果)的傳送方接收結果的唯讀promise,訊息的目標接收resolver。

有關結構[編輯]

「future」是事件同步原語的特例,它只能完成一次。通常,事件可以重設為初始的空狀態,因此可以根據需要多次完成。[109]

「I-var」是具有下面定義的阻塞語意的future。它起源於Id語言中包含I-var的「I-structure」資料結構。可以使用不同值多次設定的有關同步構造稱為「M-var」。M-var支援take(採取)或put(放置)當前值的原子性操作,這裡採取這個值還將M-var設定回其初始的「空」狀態。[110]

「並行邏輯變數」與future類似,但是通過合一更新,與邏輯編程中的「邏輯變數」相同。因此,它可以多次繫結到可合一的值,但不能設定回到空或未解決狀態。Oz的資料流變數充當並行邏輯變數,並且還具有上面提到的阻塞語意。

「並行約束變數」是並行邏輯變數的一般化,以支援約束邏輯編程:約束可以多次「縮小」,表示可能值的較小集合。通常,有一種方法可以指定每當約束進一步縮小時應該執行的thunk英語thunk;這是支援「約束傳播」所必需的。

隱式與顯式future[編輯]

對future的使用可以是「隱式」的,任何對future的使用都會自動獲得它的值,它就像是普通的參照一樣;也可以是「顯式」的,使用者必須呼叫函式來取得值,例如Java中的Future[32]或CompletableFuture[33]get方法。獲得一個顯式的future的值可以稱為「刺激」(stinging)或「強迫」(forcing)。顯式future可以作為庫來實現,而隱式future則通常作為語言的一部分來實現。

最初的Baker和Hewitt論文描述了隱式future,它們在演員模型和純物件導向程式設計語言(如Smalltalk)中自然得到支援。Friedman和Wise的論文只描述了顯式的future,可能反映了在老舊硬體上有效實施隱式future的困難。難點在於老舊硬體不能處理原始資料類型(如整數)的future。例如,add指令不會處理3 + future factorial(100000) 。在純演員模型或物件導向語言中,這個問題可以通過向future factorial(100000)傳送訊息+[3]來解決,它要求future自己加3並返回結果。請注意,無論factorial(100000)何時完成計算,訊息傳遞方法都可以工作,而且不需要任何「刺激」或「強迫」。

阻塞與非阻塞語意[編輯]

如果future的值是非同步訪問的,例如通過向它傳送訊息,或者通過使用類似於E語言中的when的構造顯式地等待它,那麼在訊息可以被接收或等待完成之前,推遲直到future得到解決(resolve)是沒有任何困難的。這是在純非同步系統(如純演員語言)中唯一需要考慮的情況。

然而,在某些系統中,還可能嘗試「立即」或「同步」訪問future的值。這樣的話就需要做出一個設計選擇:

  • 訪問可能會阻塞當前執行緒或行程,直到future得到解決(可以具有逾時)。這是Oz語言中「資料流變數」的語意。
  • 嘗試的同步訪問總是會引發訊號指示錯誤,例如丟擲異常。這是E語言中遠端promise的語意。[111]
  • 潛在的,如果future已經解決,則訪問可能成功,但如果未解決,則發出訊號指示錯誤。這樣做的缺點是引入了不確定性和潛在的競爭條件,這似乎是一種不常見的設計選擇。

作為第一種可能性的範例,在C++11中 ,需要future值的執行緒可以通過呼叫wait()get()成員函式來阻塞,直到它可獲得為止。還可以使用wait_for()wait_until()成員函式指定等待逾時,以避免無限期阻塞。如果future對std::async的呼叫,那麼阻塞等待(沒有逾時)可能導致函式的同步呼叫以計算等待執行緒上的結果。

promise管線[編輯]

分散式系統中使用推遲值可以顯著地減少傳輸延遲。例如,指稱推遲值的promise,成就了「promise管線」[112][113],就像在E語言和Joule英語Joule (programming language)語言中實現的那樣,它在Argus語言中稱為「call-stream」[5]

考慮一個涉及常規遠端程序呼叫的表達式,例如:

 t3 := (x.a()).c(y.b())

可以展開為

 t1 := x.a();
 t2 := y.b();
 t3 := t1.c(t2);

每個語句需要傳送一條訊息,並在下一個語句可以繼續之前收到一個答覆。例如,假設xyt1t2都位於同一台遠端機器上。在這種情況下,在開始執行第三條語句之前,必須對該機器進行兩次完整的網路往返。然後,第三條語句將引起另一個到同一個遠端機器的往返。

上面的表達式可以使用E語言的語法寫為:

 t3 := (x <- a()) <- c(y <- b())

其中x <- a()表示將訊息a()非同步傳送給x。它可以展開為:

 t1 := x <- a();
 t2 := y <- b();
 t3 := t1 <- c(t2);

所有三個變數都會立即為其結果分配promise,執行過程將繼續進行到後面的語句。之後嘗試解決t3的值可能會導致傳輸延遲;但是,管線操作可以減少所需的往返次數。如果與前面的範例一樣,xyt1t2都位於相同的遠端機器上,則管線實現可以用一次往返來計算t3,不必用三次。由於所有三條訊息都指向同一遠端電腦上的對象,因此只需要傳送一個請求,只需要接收一個包含結果的回應。另請注意,即使t1t2位於不同機器上,或者位於與xy不同的機器上,傳送t1 <- c(t2)也不會阻塞。

promise管線應與並列非同步訊息傳遞區分開來。在支援並列訊息傳遞但不支援管線操作的系統中,上面範例中的訊息傳送x <- a()y <- b()可以並列進行,但傳送t1 <- c(t2)將不得不等到t1t2都被接收,即使xyt1t2在同一個遠端機器上。在涉及許多訊息的更複雜情況下,管線的相對傳輸延遲優勢變得更大。

promise管線操作也不應與演員系統中的管線式訊息處理相混淆,在這種系統中,演員可以在完成當前訊息的處理之前,指定並開始執行下一個訊息的行為。

有特定執行緒的future[編輯]

某些語言比如Alice ML英語Alice (programming language),定義的future可以關聯著計算這個future值的特定執行緒[27]。這種計算可以通過spawn exp,在建立future時及早地開始;或者通過lazy exp,在首次需要其值時懶惰地開始。在延遲計算的意義上,懶惰的future類似於thunk 。

Alice ML還支援可由任何執行緒解決的future,並稱謂它們為「promised future」[108]。這裡的promise是給future的顯式把柄(handle),它通過多型庫函式Promise.promise來建立,所有promise都關聯的一個future,建立一個新promise也就建立了一個新鮮的future;這個future通過Promise.future來提取,並且通過顯式的應用Promise.fulfill於對應的promise來消除,即在全域中將這個future替代為一個值。Alice ML不支援promise管線,轉而對於future,包括關聯著promise的future,管線是自然而然地發生的。

在沒有特定執行緒的future(如Alice ML所提供的)中,通過在建立這個future的同時建立一個計算這個值的執行緒,可以直接實現及早求值的有特定執行緒的future。在這種情況下,最好將唯讀視圖返回給客戶,以便僅讓新建立的執行緒能夠解決這個future。

要在沒有特定執行緒的future中,實現隱式惰性的有特定執行緒的future,需要一種機制來確定何時首次需要future的值(例如,Oz中的WaitNeeded構造[114] )。 如果所有值都是對象,那麼有實現透明轉發對象的能力就足夠了,因為傳送給轉發器的首條訊息表明需要future的值。

假定系統支援訊息傳遞,在有特定執行緒的future中,通過讓解決執行緒向future自己的執行緒傳送訊息,可以實現沒有特定執行緒的future。然而這可能被視為不必要的複雜性。在基於執行緒的程式語言中,最具表現力的方法似乎是提供一種混合:沒有特定執行緒的future、唯讀視圖、以及要麼有WaitNeeded構造要麼支援透明轉發。

傳future呼叫[編輯]

求值策略而言,「傳future呼叫」是非確定性的:future的值將在建立future和使用其值之間的某個時間進行求值,但確切的時間不確定的,一次執行和另一次執行的求值時間會不一樣。計算可以在建立future時開始(及早求值),或者僅在實際需要值時開始(懶惰求值),並且可以在中途暫停,或在一次執行中執行。一旦future被賦值,它就不會在訪問future的時候重新計算;這就像傳需求呼叫時使用的記憶化

「懶惰」future是確定性的具有惰性求值語意的future:future值的計算在首次需要時開始,與傳需要呼叫一樣。懶惰future使用在求值策略預設不是懶惰求值的語言中。例如,在C++11中,可以通過將std::launch::deferred啟動策略傳遞給std::async以及計算值的函式來建立這種惰性future。

演員模型中的future語意[編輯]

在演員模型中,形式為future <Expression>的表達式,以它對具有環境E和客戶C的Eval訊息的回應方式來定義:future表達式通過向客戶C傳送新建立的演員F(計算<Expression>的回應的代理)作為返回值來回應Eval訊息,與之並行的向<Expression>傳送具有環境E和客戶F的Eval訊息。F的預設行為如下:

  • 當F收到請求R時,它會檢查是否已經收到來自求值<Expression>的回應(可以是返回值或丟擲異常),處理過程如下所示:
    1. 如果它已經有了回應V,那麼
      • 如果V是返回值,那麼向它傳送請求R。
      • 如果V是一個異常,那麼就把這個異常拋給請求R的客戶。
    2. 如果它還沒有回應,那麼將R儲存在F內的請求佇列中。
  • 當F接收到來自求值<Expression>的回應V時,那麼將V儲存在F中,並且
    • 如果V是返回值,那麼將所有排隊的請求傳送到V。
    • 如果V是一個異常,那麼就會把這個異常丟擲給每個排隊請求的客戶。

但是,一些future可以通過特殊方式處理請求以提供更大的並列性。例如,表達式1 + future factorial(n)可以建立一個新的future,其行為類似於數字1+factorial(n) 。這個技巧並不總是有效。例如,以下條件表達式:

if m>future factorial(n) then print("bigger") else print("smaller")

掛起,直到factorial(n)這個future已回應詢問m是否大於其自身的請求。

參見[編輯]

參照[編輯]

  1. ^ 1.0 1.1 Daniel Friedman; David Wise. The Impact of Applicative Programming on Multiprocessing. International Conference on Parallel Processing: 263–272. 1976. We have proposed a new semantics for cons and its extractor functions first and rest which avoids the construction of those portions of structures that are never accessed. ……
    Using the function cons as a paradigm of structure-creating functions, we briefly explain its semantics. When cons is invoked by the user, the value returned is a pointer to a newly built structure. Rather than evaluate the arguments to cons and create the complete structure, we create a structure consisting of two suspensions. A suspension consists of a reference to the form whose evaluation was deferred and a reference to the environment of variable bindings in which the suspension was originally created. ……
    When either of the functions first or rest is invoked, the following events occur. A designated field of the argument is checked to determine if it contains a suspension (suspensions are flagged and easily distinguished); if not, then its contents is returned. If a suspension is present, then the evaluator is invoked upon the designated form within the preserved environment. The result is stored back in the designated field in place of the suspension (for next time); and the value is returned as a final result. ……
    As a result of suspending, evaluations are delayed as long as possible. ……
    A fortunate side-effect of suspending the creation of data structures is the ability to deal with infinite structures. Consider the list defined (but never completely constructed) by the invocation of <terms[O]> where
      <terms[n]> ≡ <cons[<recip[<square[n]>]>
                         <terms[<addl[n]>]> ]> .
    That list, the reciprocals of the squares of all the positive integers, might be familiar since its sum, excluding the first term, converges to π2/6. Suppose that z were bound to the result of <terms[O]>; in fact, because of the suspending cons, z is initially bound only to a "promise" of this result.
     
  2. ^ Hibbard, Peter. Parallel Processing Facilities. New Directions in Algorithmic Languages, (ed.) Stephen A. Schuman, IRIA, 1976. 1976. 
  3. ^ Henry Baker; Carl Hewitt. The Incremental Garbage Collection of Processes. Proceedings of the Symposium on Artificial Intelligence Programming Languages,. ACM Sigplan Notices 12, 8: 55–59. August 1977. In this paper we consider an "eager beaver" evaluator for an applicative programming language which starts evaluating every subexpression as soon as possible, and in parallel. This is done through the mechanism of futures, which are roughly Algol-60 "thunks" which have their own evaluator process ("thinks"?). (Friedman and Wise [10] call futures "promises", while Hibbard [13] calls them "eventuals".) When an expression is given to the evaluator by the user, a future for that expression is returned which is a promise to deliver the value of that expression at some later time, if the expression has a value. A process is created for each new future which immediately starts to work evaluating the given expression. ……
    The intuitive semantics associated with a future is that it runs asynchronously with its parent's evaluation. This effect can be achieved by either assigning a different processor to each future, or by multiplexing all of the futures on a few processors. Given one such implementation, the language can easily be extended with a construct having the following form: "(EITHER <e1> <e2> … <en>)" means evaluate the expressions <ei> in parallel and return the value of "the first one that finishes".
     
  4. ^ 4.0 4.1 4.2 Halstead, Robert H. Jr. MultiLisp: A Language for Concurrent Symbolic Computation. ACM Transactions on Programming Languages and Systems. October 1985, 7 (4): 501–538. S2CID 1285424. doi:10.1145/4472.4478可免費查閱. Multilisp's principal construct for both creating tasks and synchronizing among them is the future. The construct (future X) immediately returns a future for the value of the expression X and concurrently begins evaluating X. When the evaluation of X yields a value, that value replaces the future. The future is said to be initially undetermined; it becomes determined when its value has been computed. An operation (such as addition) that needs to know the value of an undetermined future will be suspended until the future becomes determined, but many operations, such as assignment and parameter passing, do not need to know anything about the values of their operands and may be performed quite comfortably on undetermined futures. ……
    The future construct in Multilisp, for example, offers a way to introduce parallelism that fits very nicely with the principal program operation of Multilisp — expression evaluation. Also, no special care is required to use a value generated by future. Synchronization between the producer and the users of a future’s value is implicit, freeing the programmer’s mind from a possible source of concern.
     
  5. ^ 5.0 5.1 5.2 Barbara Liskov; Liuba Shrira. Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems. Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation; Atlanta, Georgia, United States. ACM: 260–267. 1988. ISBN 0-89791-269-1. doi:10.1145/53990.54016. Promises were designed to support an efficient asynchronous remote procedure call mechanism for use by components of a distributed program. A promise is a place holder for a value that will exist in the future. It is created at the time a call is made. The call computes the value of the promise, running in parallel with the program that made the call. When it completes, its results are stored in the promise and can then be 「claimed」 by the caller. ……
    Call-streams allow a sender to make a sequence of calls to a receiver without waiting for replies. The stream guarantees that the calls will be delivered to the receiver in the order they were made and that the replies from the receiver will be delivered to the sender in call order. ……
    The design of promises was influenced by the future mechanism of MultiLisp[5]. Like futures, promises allow the result of a call to be picked up later. However, promises extend futures in several ways: Promises are strongly typed and thus avoid the need for runtime checking to distinguish them from ordinary values. They allow exceptions from the called procedure to be propagated in a convenient manner. Finally, they are integrated with the call-stream mechanism and address problems such as node failures and network partitions that do not arise in a single-machine environment. ……
    There are two reasons for using stream calls instead of RPCs: they allow the caller to run in parallel with the sending and processing of the call, and they reduce the cost of transmitting the call and reply messages. RPCs and their replies are sent over the network immediately, to minimize the delay for a call. Stream calls and their replies, however, are buffered and sent when convenient; in the case of sends, normal replies can be omitted. Buffering allows us to amortize the overhead of kernel calls and the transmission delays for messages over several calls, especially for small calls and replies.
      Also published in ACM SIGPLAN Notices 23(7).
  6. ^ Kisalaya Prasad, Avanti Patil, Heather Miller. Futures and Promises. 
  7. ^ Domenico Talia. Survey and comparison of PARLOG and Concurrent Prolog. 1990. Concurrent logic languages are born from a new interpretation of Horn clauses, the process interpretation. According to this interpretation, an atomic goal ← C can be viewed as a process, a conjunctive goal ← C1, …, Cn, as a process network, and a logic variable shared between two clauses can be viewed as a communication channel between two processes. 
  8. ^ Gert Smolka. Concurrent Constraint Programming Based on Functional Programming. 1998. As base language we choose a dynamically type language DML that is obtained from SML by eliminating type declarations and static type checking. ……
    A state is a finite function σ mapping addresses a to so-called units u. Units are either primitive values other than names or representations of records, variants, reference cells, functions, and primitive operations …… A match Match is a sequence of clauses (p1 ⇒ e1 | … | pk ⇒ ek). ……
    We now extend DML with logic variables, one of the essentials of logic programming. Logic variables are a means to represent in a state partial information about the values of addresses. Logic variables are modelled with a new unit lvar. The definition of states is extended so that a state may map an address also to lvar or an address. ……
    A match …… blocks until the store contains enough information to commit to one of the clauses or to know that none applies.
     
  9. ^ 9.0 9.1 Jan Schwinghammer. A Concurrent Lambda Calculus with Promises and Futures. 2002. General logic variables stem from the class of logic programming languages such as Prolog [Pro85, SS94, JL87]. Initially, when freshly introduced, they carry no value. Therefore they allow for the stepwise construction of values, using further logic variables for the construction of subvalues if necessary. They are transient, in that they are identified with their value as soon as this becomes available. This provides a mechanism for implicit synchronization of concurrent threads that share a logic variable: A thread reading the variable automatically suspends while sufficient information is not available.
    We will be concerned with futures and promises, which differ from general logic variables in that a distinction is made between reading and writing them. Bidirectional unification can be replaced by (single-) assignment.
     
  10. ^ 10.0 10.1 Rishiyur S. Nikhil. ID Reference Manual (PDF). 1991. A component of a data structure may have I-structure semantics (as opposed to functional or M-structure semantics). For such a component, no value is specified when the data structure is created; instead, a separate assignment statement is used. An I-structure component may be in one of two states: be full (with a value), or empty. all components begin in the empty state (when the data structure is allocated).
    An I-structure component has a single assignment restriction, i.e. it can only be assigned once, at which point its state goes from empty to full. Any attempt to assign it more than once is caught as a runtime error. The component can be read an arbitrary number of times.
    ……
    An M-structure component can be assigned with a put operation and read with a take operation. A value can be put only into an empty component — it is a runtime error if it is already full. Many take's may be attempted concurrently on a component.
     
  11. ^ 11.0 11.1 The Concurrent ML Reference Manual — The SyncVar structure. The SyncVar structure provides Id-style synchronous variables (or memory cells). These variables have two states: empty and full. An attempt to read a value from an empty variable blocks the calling thread until there is a value available. An attempt to put a value into a variable that is full results in the Put exception being raised. There are two kinds of synchronous variables: I-variables are write-once, while M-variables are mutable. 
  12. ^ Promise, Sunless Sea, [2018-12-31], (原始內容存檔於2007-10-23) 
  13. ^ Argus, MIT, [2018-12-31], (原始內容存檔於2018-04-27) 
  14. ^ Liskov, Barbara, Distributed computing and Argus, Oral history, IEEE GHN, [2018-12-31], (原始內容存檔於2014-11-22) 
  15. ^ Gold, Udanax, [2018-12-31], (原始內容存檔於2008-10-11) 
  16. ^ Pipeline, E rights, [2018-12-31], (原始內容存檔於2018-10-22) 
  17. ^ Henry Lieberman. A Preview of Act 1. MIT AI memo 625. June 1981. 
  18. ^ Henry Lieberman. Thinking About Lots of Things at Once without Getting Confused: Parallelism in Act 1. MIT AI memo 626. June 1981. 
  19. ^ Future and FutureTask in java. 
  20. ^ 20.0 20.1 Async in 4.5: Worth the Await – .NET Blog. April 3rd, 2012. 
  21. ^ 21.0 21.1 21.2 Asynchronous Programming with Async and Await (C# and Visual Basic). Msdn.microsoft.com. [2014-05-13]. (原始內容存檔於2014-05-27). 
  22. ^ Don Syme; Tomas Petricek; Dmitry Lomov. The F# Asynchronous Programming Model, PADL 2011. 2010-10-21. This paper describes the asynchronous support in F# 2.0. While the core idea was released and published in book form 2007, the model has not been described in the conference literature. 
  23. ^ Tomas Petricek. Asynchronous C# and F# (I.): Simultaneous introduction. 2010-10-29 [2018-12-31]. (原始內容存檔於2018-12-31). Currently, you can run the operation on a background thread or using a Task, but coordinating multiple such operations is difficult. …… This problem has been the main motivation for including asynchronous workflows in F# about 3 years ago. In F#, this also enabled various interesting programming styles - for example creating GUI using asynchronous workflows ……. The C# asynchronous programming support and the await keyword is largely inspired by F# asynchronous workflows ……. 
  24. ^ 24.0 24.1 Gilad Bracha. Dart Language Asynchrony Support: Phase 1. October 2014 [2018-12-31]. (原始內容存檔於2016-07-02). 
  25. ^ 25.0 25.1 PEP 0492 – Coroutines with async and await syntax. [2018-12-31]. (原始內容存檔於2019-01-05). 
  26. ^ Kenjiro Taura; Satoshi Matsuoka; Akinori Yonezawa. ABCL/f: A Future-Based Polymorphic Typed Concurrent Object-Oriented Language – Its Design and Implementation.. In Proceedings of the DIMACS workshop on Specification of Parallel Algorithms, number 18 in Dimacs Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society: 275–292. 1994. CiteSeerX 10.1.1.23.1161可免費查閱. 
  27. ^ 27.0 27.1 27.2 Alice manual — Future. 
  28. ^ Dart SDK dart async Completer. [2018-12-31]. (原始內容存檔於2016-03-04). 
  29. ^ Task. [2018-12-31]. (原始內容存檔於2018-12-31). 
  30. ^ GHC User’s Guide — 6. Language extensions — 6.15. Parallel and Concurrent. 
  31. ^ Steve Dekorte. Io, The Programming Language. 2005 [2018-12-31]. (原始內容存檔於2019-01-04). 
  32. ^ 32.0 32.1 java.util.concurrent.Future. 
  33. ^ 33.0 33.1 java.util.concurrent.CompletableFuture. 
  34. ^ Using promises. Mozilla Developer Network. [23 February 2021]. 
  35. ^ Making asynchronous programming easier with async and await. Mozilla Developer Network. [23 February 2021]. 
  36. ^ Rich Hickey. changes.txt at 1.1.x from richhickey's clojure. 2009 [2018-12-31]. (原始內容存檔於2016-02-18). 
  37. ^ Parallelism with Futures. 
  38. ^ Task Parallel Library (TPL). 
  39. ^ Future – Kotlin Programming Language. 
  40. ^ Seif Haridi; Nils Franzen. Tutorial of Oz. Mozart Global User Library. [2011-04-12]. (原始內容存檔於2011-05-14). 
  41. ^ 41.0 41.1 The Python Standard Library — Concurrent Execution — concurrent.futures — Launching parallel tasks. 
  42. ^ Python 3.2 发布. Python.org. [2018-12-31]. (原始內容存檔於2018-12-31). 
  43. ^ PEP 3148 – futures - execute computations asynchronously. The proposed design of this module was heavily influenced by the Java java.util.concurrent package [1]. The conceptual basis of the module, as in Java, is the Future class, which represents the progress and result of an asynchronous computation. The Future class makes little commitment to the evaluation mode being used e.g. it can be used to represent lazy or eager evaluation, for evaluation using threads, processes or remote procedure call.
    Futures are created by concrete implementations of the Executor class (called ExecutorService in Java). The reference implementation provides classes that use either a process or a thread pool to eagerly evaluate computations.
     
  44. ^ Python 3.5.0 发布. Python.org. [2018-12-31]. (原始內容存檔於2019-01-05). 
  45. ^ class Promise. raku.org. [2022-08-19]. 
  46. ^ Future in std::future - Rust. doc.rust-lang.org. [2023-12-16]. 
  47. ^ scala.concurrent包頁面存檔備份,存於網際網路檔案館
  48. ^ Blackbird promise library - Blackbird. orthecreedence.github.io. [2018-12-31]. (原始內容存檔於2017-11-10). 
  49. ^ Eager Future2. common-lisp.net. [2019-01-04]. (原始內容存檔於2018-12-31). 
  50. ^ - Common Lisp的並列編程庫[永久失效連結]
  51. ^ PCall. marijnhaverbeke.nl. [2018-12-31]. (原始內容存檔於2020-08-06). 
  52. ^ Chapter 30. Thread 4.0.0. [2013-06-26]. (原始內容存檔於2019-10-16). 
  53. ^ Dlib C++ Library #thread_pool. [2013-06-26]. (原始內容存檔於2019-10-16). 
  54. ^ QtCore 5.0: QFuture Class. Qt Project. [2013-06-26]. (原始內容存檔於2013-06-01). 
  55. ^ Seastar. Seastar project. [2016-08-22]. (原始內容存檔於2016-08-20). 
  56. ^ GitHub – facebook/folly: An open-source C++ library developed and used at Facebook.. [2018-12-31]. (原始內容存檔於2019-03-22). 
  57. ^ Threads Slides of POCO (PDF). [2018-12-31]. (原始內容存檔 (PDF)於2020-05-08). 
  58. ^ Groovy GPars. [2018-12-31]. (原始內容存檔於2013-01-12). 
  59. ^ 59.0 59.1 Promises/A+. promisesaplus.com. [2019-01-04]. (原始內容存檔於2018-12-29). 
  60. ^ Promises/A+ Conformant Implementations. 
  61. ^ cujoJS: Javascript architectural toolkit. cujojs.com. [2019-01-04]. (原始內容存檔於2012-03-17). 
  62. ^ A solid, fast Promises/A+ and when() implementation, plus other async goodies.: cujojs/when. 2018-12-25 [2018-12-31]. (原始內容存檔於2019-01-16) –透過GitHub. 
  63. ^ Dojo Deferreds and Promises - Archived Tutorial - Dojo Toolkit. dojotoolkit.org. [2019-01-04]. (原始內容存檔於2018-12-31). 
  64. ^ manage asynchronous tasks. MochiKit.Async. [2019-01-04]. (原始內容存檔於2018-12-31). 
  65. ^ jQuery. [2018-12-31]. (原始內容存檔於2012-02-29). 
  66. ^ Deferred Object. 
  67. ^ CommonJS Promises/A頁面存檔備份,存於網際網路檔案館
  68. ^ AngularJS — Superheroic JavaScript MVW Framework. angularjs.org. [2019-01-04]. (原始內容存檔於2015-06-23). 
  69. ^ kriskowal/q. 
  70. ^ A lightweight library that provides tools for organizing asynchronous code: tildeio/rsvp.js. 2019-01-03 [2018-12-31]. (原始內容存檔於2019-01-17) –透過GitHub. 
  71. ^ :bird: :zap: Bluebird is a full featured promise library with unmatched performance.: petkaantonov/bluebird. 2019-01-04 [2018-12-31]. (原始內容存檔於2018-12-28) –透過GitHub. 
  72. ^ promise頁面存檔備份,存於網際網路檔案館
  73. ^ JDeferred. JDeferred. [2019-01-04]. (原始內容存檔於2019-01-08). 
  74. ^ Asynchronous Java made easier. Contribute to linkedin/parseq development by creating an account on GitHub. 2018-12-29 [2018-12-31]. (原始內容存檔於2018-06-10) –透過GitHub. 
  75. ^ Proxying futures library for Objective-C. Contribute to mikeash/MAFuture development by creating an account on GitHub. 2019-01-01 [2018-12-31]. (原始內容存檔於2019-02-13) –透過GitHub. 
  76. ^ mikeash.com: Friday Q&A 2010-02-26: Futures. www.mikeash.com. [2019-01-04]. (原始內容存檔於2018-12-31). 
  77. ^ An Objective-C Class which implements the Promises/A+ specification.: couchdeveloper/RXPromise. 2018-12-26 [2018-12-31]. (原始內容存檔於2018-06-11) –透過GitHub. 
  78. ^ Futures, for Objective-C, that automatically collapse so it's nearly impossible to mix up the level of future nesting despite the lack of generics.: Strilanc/ObjC-CollapsingFutures. 2018-12-07 [2018-12-31]. (原始內容存檔於2018-06-11) –透過GitHub. 
  79. ^ Promises for Swift & ObjC. Contribute to mxcl/PromiseKit development by creating an account on GitHub. 2019-01-03 [2019-01-04]. (原始內容存檔於2019-01-08) –透過GitHub. 
  80. ^ Objective-C Promises in the CommonJS style. Contribute to mproberts/objc-promise development by creating an account on GitHub. 2018-09-11 [2018-12-31]. (原始內容存檔於2018-06-11) –透過GitHub. 
  81. ^ OAPromise is an API separating async operations and their callbacks, adding consistency and useful features like fall-through errors and progress reports.: oleganza/OAPromise. 2017-03-29 [2018-12-31]. (原始內容存檔於2013-10-27) –透過GitHub. 
  82. ^ Lazy. caml.inria.fr. [2018-12-31]. (原始內容存檔於2015-07-06). 
  83. ^ Future - represent an operation awaiting completion - metacpan.org. metacpan.org. [2019-01-04]. (原始內容存檔於2019-01-01). 
  84. ^ Promises - An implementation of Promises in Perl - metacpan.org. metacpan.org. [2018-12-31]. (原始內容存檔於2018-12-31). 
  85. ^ Reflex - Class library for flexible, reactive programs. - metacpan.org. metacpan.org. [2019-01-04]. (原始內容存檔於2019-01-04). 
  86. ^ Promises/A implementation for PHP. Contribute to reactphp/promise development by creating an account on GitHub. 2019-01-04 [2018-12-31]. (原始內容存檔於2019-04-07) –透過GitHub. 
  87. ^ promise — Ultra-performant Promise implementation in Python. 
  88. ^ Deferred Reference. twistedmatrix.com. 
  89. ^ 89.0 89.1 Bengtsson, Henrik. future: Unified Parallel and Distributed Processing in R for Everyone. 2018-10-17 [2018-12-31]. (原始內容存檔於2019-10-16) –透過R-Packages. 
  90. ^ promise - RubyGems.org - your community gem host. rubygems.org. [2019-01-04]. (原始內容存檔於2018-12-31). 
  91. ^ Ruby bindings for libuv. Contribute to cotag/libuv development by creating an account on GitHub. 2018-10-16 [2018-12-31]. (原始內容存檔於2018-06-11) –透過GitHub. 
  92. ^ Celluloid: Actor-based Concurrent Objects for Ruby. celluloid.io. [2019-01-04]. (原始內容存檔於2018-12-31). 
  93. ^ Wait on resources being set in the future. Contribute to adhearsion/future-resource development by creating an account on GitHub. 2013-12-27 [2018-12-31]. (原始內容存檔於2018-06-11) –透過GitHub. 
  94. ^ Zero-cost asynchronous programming in Rust. Contribute to rust-lang-nursery/futures-rs development by creating an account on GitHub. 2019-01-04 [2019-01-04]. (原始內容存檔於2019-02-26) –透過GitHub. 
  95. ^ Util. twitter.github.io. [2018-12-31]. (原始內容存檔於2018-12-23). 
  96. ^ al45tair / Async. bitbucket.org. [2018-12-31]. (原始內容存檔於2018-12-31). 
  97. ^ A Swift based Future/Promises Library for IOS and OS X.: FutureKit/FutureKit. 2018-12-31 [2018-12-31]. (原始內容存檔於2018-08-10) –透過GitHub. 
  98. ^ Dispatch - Apple Developer Documentation. developer.apple.com. [2019-01-04]. (原始內容存檔於2018-12-31). 
  99. ^ FutureLib is a pure Swift 2 library implementing Futures & Promises inspired by Scala.: couchdeveloper/FutureLib. 2018-10-15 [2018-12-31]. (原始內容存檔於2018-06-12) –透過GitHub. 
  100. ^ Work with values that haven't been determined yet.: bignerdranch/Deferred. 2019-01-02 [2019-01-04]. (原始內容存檔於2018-06-10) –透過GitHub. 
  101. ^ Write great asynchronous code in Swift using futures and promises: Thomvis/BrightFutures. 2019-01-03 [2018-12-31]. (原始內容存檔於2018-06-11) –透過GitHub. 
  102. ^ tcl-promise. SourceForge. [2018-12-31]. (原始內容存檔於2018-12-31). 
  103. ^ Futures in Go, no package required. 
  104. ^ The Python Standard Library — Networking and Interprocess Communication — asyncio — Asynchronous I/O. 
  105. ^ Kris Zyp. Promise API Proposal. 2009-05-25. 
    CommonJS — Promises. 
  106. ^ Web Workers API. 
    Worker threads API. 
    threads.js — Make web workers & worker threads as simple as a function call. 
  107. ^ Robust promises with Dojo deferred, Site Pen, 2010-05-03 [2018-12-31], (原始內容存檔於2018-12-31) 
  108. ^ 108.0 108.1 Alice Manual — Promise. 
  109. ^ 500 lines or less, "A Web Crawler With asyncio Coroutines" by A. Jesse Jiryu Davis and Guido van Rossum頁面存檔備份,存於網際網路檔案館) says "implementation uses an asyncio.Event in place of the Future shown here. The difference is an Event can be reset, whereas a Future cannot transition from resolved back to pending."
  110. ^ Control Concurrent MVar, Haskell, [2018-12-31], (原始內容存檔於2009-04-18) 
  111. ^ Promise, E rights, [2018-12-31], (原始內容存檔於2018-12-31) 
  112. ^ Promise Pipelining. www.erights.org. [2018-12-31]. (原始內容存檔於2018-10-22). 
  113. ^ Promise Pipelining on the C2 wiki. [2018-12-31]. (原始內容存檔於2005-09-25). 
  114. ^ WaitNeeded, Mozart Oz, [2018-12-31], (原始內容存檔於2013-05-17) 

外部連結[編輯]