Future与promise

在電腦科學中，**future**、**promise**、**delay** 和 **deferred** 是指用於在某些並行程式語言中同步程式執行的構造。由於某些計算（或者網路請求）尚未結束，我們需要一個物件來代理這個未知的結果，於是就有了上述這些構造（future、promise 等）。

「promise」一詞由丹尼爾・福瑞得曼和 David Wise 在 1976 年提出，
Peter Hibbard 稱之為「eventual」。
1977 年 Henry Baker 和 Carl Hewitt 在一篇論文中介紹了一個類似的概念「future」。

術語「future」、「promise」、「delay」和「deferred」通常可以互換使用，而「future」與「promise」之間的使用差異，我們將在下面討論。具體來說，當區分使用時，future 是變數的「唯讀」預留位置視圖，而 promise 是可寫的單賦值容器，用於設定 future 的值。 值得注意的是，無須指定可以設定其值的 promise 就可以定義 future，並且不同的 promise 可以設定同一個 future 的值，儘管對於給定的 future 僅可以執行一次。在其他情況下，future 和 promise 是一起建立的，並且相互關聯：future 是值，promise 是設定值的函式 —— 本質上是非同步函式（promise）的返回值（future）。設定 future 的值的過程也稱為「resolve」（解析）、「fulfil」（實現）或「bind」（繫結）它。

## 應用

future 和 promise 起源於函式語言程式設計和相關範例（如邏輯編程 ），目的是將值（future）與其計算方式（promise）分離，從而允許更靈活地進行計算，特別是通過並列化。後來，它在分散式計算中得到了應用 ，減少了通信往返的延遲。再後來，它變得更有用了，因為它允許以直接風格編寫非同步程式，而不是以連續傳遞風格的方式。

## 隱式與顯式

對 future 的使用可能是「隱式的」（任何對 future 的使用都會自動獲得它的值，它就像是普通的參照一樣）或「顯式的」（使用者必須呼叫函式來取得值，例如 Java 中的 Future 或 CompletableFuture 的 `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)` 何時完成計算，訊息傳遞方法都可以工作，而且不需要任何 sting 或 force。

## promise 管線

在分散式系統中使用 future 可以顯著地減少延遲。例如，future 讓「promise 管線」成為了可能， 就像在 E 語言和 Joule 語言中實現的那樣，在 Argus 語言中這也被稱為「call-stream」。

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

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

可以擴充為

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

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

使用 future，上面的表達式可以寫成

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

可以擴充為

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

這裡使用的語法是 E 語言的語法，其中 `x <- a()` 表示將訊息 `a()` 非同步傳送給 `x`。所有三個變數都會立即為其結果分配 future，執行過程將繼續進行到後面的語句。之後嘗試解決 `t3` 的值可能會導致延遲；但是，管線操作可以減少所需的往返次數。如果與前面的範例一樣，`x`、`y`、`t1` 和 `t2` 都位於相同的遠端機器上，則管線實現可以用一次往返來計算 `t3`，不必用三次。由於所有三條訊息都指向同一遠端電腦上的物件，因此只需要傳送一個請求，只需要接收一個包含結果的回應。另請注意，即使 `t1` 和 `t2` 位於不同機器上，或者位於與 `x` 或 `y` 不同的機器上，傳送 `t1 <- c(t2)` 也不會阻塞。

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

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

## 唯讀視圖

在某些程式語言（如 Oz\E 和 AmbientTalk）中 ，可以獲得未來的「唯讀視圖」，該視圖允許在 resolve 後讀取其值，但不允許 resolve 它：

* 在 Oz 語言中，

!! 運算子用於獲得唯讀視圖

* 在 E 語言和 AmbientTalk 中，future 由一對稱為「promise/resolver 對」的值表示。promise 表示唯讀視圖，需要 resolver 來設定 future 的值。
* 在 C++11 中，`std::future` 提供了一個唯讀視圖。該值通過使用 `std::promise` 直接設定，或使用 `std::packaged_task` 或 `std::async` 設定為函式呼叫的結果。
* 在 Dojo Toolkit 的 1.5 版本的 Deferred API 中，「僅限 consumer 的 promise 物件」表示唯讀視圖。
* 在 Alice ML 中，future 提供「唯讀視圖」，而 promise 包含 future 和 resolve future 的能力
* 在.NET 4.0 中，`System.Threading.Tasks.Task<T>` 表示唯讀視圖。解析值可以通過 `System.Threading.Tasks.TaskCompletionSource<T>` 來完成。

對唯讀視圖的支援符合最小特權原則，因為它允許將值設定為僅限於需要設定該值的主體。在同樣支援管線的系統中，非同步訊息的傳送方（包括結果）接收結果的唯讀承諾 promise，訊息的目標接收 resolver。

## 針對特定執行緒的 future

某些語言（如 Alice ML ）定義了與計算 future 值的特定執行緒相關聯的 future。 這種計算可以在建立 future 時及早開始，或者在首次需要其值時懶惰地開始。在延遲計算的意義上，懶惰的 future 類似於 thunk 。

Alice ML 還支援可由任何執行緒解決的 future，並呼叫這些「promise」。 「promise」的這種使用不同於上文所述的在 E 語言中的使用。在 Alice 中，promise 不是唯讀視圖，並且不支援 promise 管線操作。相反，對於 future 未來，包括與 promise 相關的 future，管線是自然而然地發生的。

## 阻塞與非阻塞語意

如果 future 的值是非同步存取的，例如通過向它傳送訊息，或者通過使用類似於 E 語言中的 `when` 的構造顯式地等待它，那麼在收到訊息或完成等待之前，推遲到 future 得到 resolve 沒有任何困難。這是在純非同步系統（如純演員語言）中唯一需要考慮的情況。

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

* 存取權限可能會阻塞當前執行緒或行程，直到 future 得到 resolve（可能需要逾時）。這是 Oz 語言中「資料流變數」的語意。
* 嘗試同步存取總是會發出錯誤訊號，例如丟擲異常 。這是 E 語言中遠端 promise 的語意。
* 如果 future 已經 resolve，則存取可能成功，但如果未 resolve，則發出錯誤訊號。這樣做的缺點是引入了不確定性和潛在的競爭條件，這似乎是一種不常見的設計選擇。

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

## 相關結構

「future」是 Event（同步原語）的特例，只能完成一次。通常，event 可以重設為初始空狀態，因此可以根據需要多次完成。

「I-var」（如在語言 Id 中）是具有上面定義的阻塞語意的 future。「I-structure」是包含 I-var 的資料結構。可以使用不同值多次設定的相關同步構造稱為「M-var」。M-var 支援「採用」或「放置」當前值的原子操作，其中取值還將 M-var 設定回其初始「空」狀態。 

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

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

## 不同形式 future 的表達能力之間的關係

通過在建立 future 的同時建立一個計算值的執行緒，可以在非執行緒特有的 promise 中直接實現及早求值的執行緒特有的 future。在這種情況下，future 將唯讀視圖返回給客戶端，以便僅讓新建立的執行緒能夠解決這個 future。

 
要在非執行緒特有的 promise 中實現隱式延遲執行緒特有的 promise（比如由 Alice ML 提供），需要一種機制來確定何時首先需要 future 的值（例如，Oz 中的 `WaitNeeded` 構造 ）。
如果所有值都是物件，那麼實現透明轉發物件的能力就足夠了，因為傳送給轉發器的第一條訊息表明需要 future 的值。

假定系統支援訊息傳遞，通過讓 resolve 執行緒向 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>` 的表達式由它對 `Eval` 訊息（環境為 E，客戶為 C）的回應方式定義：future 表達式通過向客戶 C 傳送新建立的演員來回應 `Eval` 訊息 F（計算 `<Expression>` 的回應的代理）作為返回值，「與此同時 " 向 `<Expression>` 傳送環境 E 和客戶 C 的 `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` 是否大於其自身的請求。

## 歷史

「future」與「promise」構造首先在諸如 MultiLisp 和 Act 1 之類的程式語言中實現。在並行邏輯編程語言中使用邏輯變數進行通信非常類似於 future。這些開始於「Prolog with Freeze」和「IC Prolog」，並成為真正的並行原語，包括關係語言、Concurrent Prolog、守衛霍恩子句（GHC）、Parlog、Strand、Vulcan、Janus、Oz-Mozart、Flow Java 和 Alice ML。來自資料流程式語言的單一賦值「I-var」，源自 Id 並包含在 Reppy 的「Concurrent ML」中，非常類似於並行邏輯變數。

promise 管線技術（使用 future 來克服延遲）是 Barbara Liskov 和 Liuba Shrira 於 1988 年發明的，由 Mark S. Miller、Dean Tribble 和 Rob Jellinghaus 在大約 1989 年的 Xanadu 專案中獨立發明。

「promise」一詞是由 Liskov 和 Shrira 創造的，儘管他們通過名稱「call-stream」參照了管線機制，現在很少使用它。

Liskov 和 Shrira 的論文中描述的設計以及 Xanadu 中的 promise 管線的實現都有一個限制，即 promise 值不是一等的：一個參數，或者一個 call 或 send 返回的值不能直接成為一個 promise （所以前面給出的 promise 管線的例子，它使用一個傳送的結果作為另一個傳送的參數的承諾，在 call-stream 設計或 Xanadu 實現中不能直接表達）。似乎 promise 和 call-stream 從未在 Argus 的任何公開發布中實現， Liskov 和 Shrira 論文中使用的程式語言。Argus 的開發在 1988 年左右停止了。 Xanadu 實現的 promise 管線僅在 1999 年 Udanax Gold 的原始碼發布時才公開發布，並且在任何已發布的文件中都沒有解釋過。 Joule 和 E 的後續實現支援完全一等的 promise 和 resolver。

一些早期的演員語言，包括 Act 系列， 支援並列訊息傳遞和管線訊息處理，但不支援 promise 管線。（雖然技術上可以在前兩個中實現最後一個功能，但沒有證據表明 Act 語言這樣做了。）

2000 年之後，由於訊息傳遞的請求 - 回應模型，future 和 promise 在使用者介面回應和 web 開發中的應用重新引起了人們的興趣。現在有幾種主流語言對 future 和 promise 都有語言支援，最著名的是 Java 5 中的 `FutureTask`（2004 年公布）以及.NET 4.5 中的 `async` 和 `await` 結構（2010 年發布，2012 年發布）很大程度上受到 F# 的「非同步工作流程」（可追溯到 2007 年）的啟發。 隨後被其他語言採用，特別是 Dart（2014），Python（2015）， Hack（HHVM）以及 ECMAScript 7（JavaScript）、Scala 和 C++ 的草案。

## 實現列表

支援 future、promise、並行邏輯變數、資料流變數或 I-vars 的語言，無論是通過直接語言支援還是在標準庫中，包括：

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

基於非標準庫的 future 實現：

### 協程

future 可以用協程或生成器實現， 從而產生相同的評估策略（例如，協同多工或延遲評估）。

### 通道

future 可以很容易地用通道實現：future 是一個單元素的通道，而 promise 是一個傳送到通道，實現 future 的過程。 這允許 future 在支援通道（如 CSP 和 Go）的並行程式語言中實現。由此產生的 future 是顯式的，因為它們必須通過從通道讀取而不是僅僅通過評估來取得。

## 參見

* 纖程
* Futex

## 參考資料

## 外部連結

* Concurrency patterns presentation（頁面存檔備份，存於網際網路檔案館） given at scaleconf（頁面存檔備份，存於網際網路檔案館）
* Future Value（頁面存檔備份，存於網際網路檔案館） and Promise Pipelining（頁面存檔備份，存於網際網路檔案館） at the Portland Pattern Repository
* Easy Threading with Futures（頁面存檔備份，存於網際網路檔案館） in Python