未来と約束

コンピュータサイエンスにおいて、future、promise、delay、deferred は、一部の並行プログラミング言語でプログラム実行を同期するために使用される構造を指します。これらは、通常は値の 計算がまだ完了していないため、最初は不明な結果のプロキシとして機能するオブジェクトを表します。

約束という用語は、1976年にダニエル・P・フリードマンとデイビッド・ワイズによって提案され、^[1] ピーター・ヒバードはそれを最終的と呼びました。^[2] やや似た概念である未来は、 1977年にヘンリー・ベイカーとカール・ヒューイットの論文で紹介されました。^[3]

future、promise、delay、deferred という用語はしばしば互換的に使用されますが、futureとpromiseの使用上の違いについては以下で説明します。具体的には、使用法が区別されている場合、 future は変数の読み取り専用のプレースホルダー ビューであるのに対し、 promise は書き込み可能な単一の割り当てコンテナーであり、future の値を設定します。特に、future は、どの特定の promise がその値を設定するかを指定せずに定義される場合があり、さまざまな可能な promise が特定の future の値を設定する場合がありますが、これは特定の future に対して 1 回しか実行できません。その他の場合では、future と promise が一緒に作成され、互いに関連付けられます。future は値であり、promise は値を設定する関数であり、基本的には非同期関数 (promise) の戻り値 (future) です。future の値を設定することは、 future を解決、実行、またはバインドとも呼ばれます。

Future と Promise は、関数型プログラミングや関連するパラダイム (論理プログラミングなど) で生まれたもので、値 (Future) とその計算方法 (Promise) を切り離すことで、特に並列化によって計算をより柔軟に実行できるようになりました。その後、分散コンピューティングで使用され、通信の往復による遅延が削減されました。さらに後になって、継続渡しスタイルではなく直接スタイルで非同期プログラムを記述できるようになったため、さらに使用されるようになりました。

フューチャーの使用は、暗黙的（フューチャーを使用すると、通常の参照であるかのように、自動的にその値が取得される）または明示的（ユーザーは、Javaのgetメソッドなど、関数を呼び出して値を取得する必要がある）である場合があります。明示的なフューチャーの値を取得することを、スティンギングまたは強制と呼ぶことができます。明示的なフューチャーはライブラリとして実装できますが、暗黙的なフューチャーは通常、言語の一部として実装されます。 java.util.concurrent.Future

Baker と Hewitt のオリジナルの論文では、暗黙の futures について説明しました。これは、アクター モデルの計算やSmalltalkなどの純粋なオブジェクト指向プログラミング言語で自然にサポートされています。Friedman と Wise の論文では明示的な futures のみについて説明しましたが、これはおそらく、標準のハードウェアで暗黙の futures を効率的に実装することの難しさを反映しているのでしょう。難しいのは、標準のハードウェアでは整数などのプリミティブ データ型の futures を扱えないことです。たとえば、add 命令では の扱い方がわかりません。純粋なアクター言語やオブジェクト言語では、この問題は、futures に自分自身に追加して結果を返すように要求するメッセージを送信することで解決できます。メッセージ パッシング アプローチは が計算をいつ終了するかに関係なく機能し、stinging/forcing は不要であることに注意してください。 3 + future factorial(100000)future factorial(100000)+[3]3factorial(100000)

フューチャーを使用すると、分散システムでのレイテンシを大幅に削減できます。たとえば、フューチャーは、E言語やJoule言語で実装されているプロミスパイプライン[ ^{4] [5]}を可能にします。これは、 Argus言語ではコールストリーム^[6]とも呼ばれていました。

次のような従来のリモート プロシージャ コールを含む式を考えてみましょう。

t3 := ( xa() ).c( yb() )

これは次のように拡張できる。

t1 := xa();
 t2 := yb();
 t3 := t1.c(t2);

各ステートメントでは、次のステートメントに進む前に、メッセージを送信し、応答を受信する必要があります。たとえば、、、およびがすべて同じリモート マシン上にあるとしますx。この場合、3 番目のステートメントの実行を開始する前に、そのマシンへの 2 回の完全なネットワーク ラウンドトリップが実行yされる必要があります。3 番目のステートメントによって、同じリモート マシンへの別のラウンドトリップが発生します。 t1t2

先物を使うと、上記の式は次のように書ける。

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

これは次のように拡張できる。

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

ここで使用される構文は言語 E の構文であり、 はx <- a()メッセージa()を に非同期に送信することを意味しますx。3 つの変数すべてにその結果に対する future がすぐに割り当てられ、実行は後続の文に進みます。 の値を後で解決しようとすると遅延が発生するt3可能性がありますが、パイプライン化により必要なラウンドトリップ数を削減できます。前の例のように、、、、およびがすべて同じリモート マシン上にある場合x、パイプライン実装では3 回ではなく 1 回のラウンドトリップで計算できます。3 つのメッセージはすべて同じリモート マシン上のオブジェクト宛てであるため、送信する必要がある要求は 1 つだけで、結果を含む応答は 1 つだけ受信する必要があります。と が互いに異なるマシン上にある場合、またはまたはに対して異なるマシン上にある場合でも、送信はブロックされません。 yt1t2t3t1 <- c(t2)t1t2xy

Promise パイプラインは、並列非同期メッセージ パッシングとは区別する必要があります。並列メッセージ パッシングはサポートしているがパイプラインはサポートしていないシステムでは、上記の例のx <- a()と のメッセージ送信は並列で処理できますが、、、 が同じリモート マシン上にある場合でも、と の両方が受信されるまで の送信は待機する必要があります。パイプラインの相対的なレイテンシの利点は、多くのメッセージが関係するより複雑な状況ではさらに大きくなります。 y <- b()t1 <- c(t2)t1t2xyt1t2

Promise パイプラインは、アクター システムのパイプライン化されたメッセージ処理と混同しないでください。アクター システムでは、現在のメッセージの処理が完了する前に、アクターが次のメッセージの動作を指定して実行を開始できます。

Oz、E、AmbientTalkなどの一部のプログラミング言語では、未来の読み取り専用ビューを取得できます。これにより、解決されたときにその値を読み取ることはできますが、解決することはできません。

• Oz では、!!演算子は読み取り専用ビューを取得するために使用されます。
• E および AmbientTalk では、未来は、プロミス/リゾルバ ペアと呼ばれる値のペアによって表されます。プロミスは読み取り専用ビューを表し、リゾルバは未来の値を設定するために必要です。
• C++11では、a はstd::future読み取り専用ビューを提供します。値は、 a を使用して直接設定するか、またはまたはstd::promiseを使用して関数呼び出しの結果に設定されます。std::packaged_taskstd::async
• Dojo Toolkitのバージョン1.5以降のDeferred APIでは、コンシューマ専用のPromiseオブジェクトは読み取り専用ビューを表します。^[7]
• Alice MLでは、未来は読み取り専用のビューを提供するのに対し、約束は未来と未来を解決する能力の両方を含む^{[8] [9]}
• .NET ではSystem.Threading.Tasks.Task<T>、読み取り専用ビューを表します。値の解決は を介し​​て実行できますSystem.Threading.Tasks.TaskCompletionSource<T>。

読み取り専用ビューのサポートは、値を設定する権限を、それを設定する必要のあるサブジェクトに制限できるため、最小権限の原則と一致しています。パイプラインもサポートするシステムでは、非同期メッセージ (結果を含む) の送信者は結果の読み取り専用プロミスを受信し、メッセージのターゲットはリゾルバを受信します。

Alice MLなどの一部の言語では、未来の値を計算する特定のスレッドに関連付けられた未来を定義します。^{[9]この計算は、未来が作成されたときに}積極的に開始することも、その値が最初に必要になったときに遅延して開始することもできます。遅延計算の意味で、 遅延未来はサンクに似ています。

Alice MLは、どのスレッドでも解決できる未来もサポートしており、これをプロミスと呼びます。^[8]このプロミスの使い方は、上で説明したEでの使い方とは異なります。Aliceでは、プロミスは読み取り専用ビューではなく、プロミスのパイプライン化はサポートされていません。代わりに、プロミスに関連付けられたものも含め、未来に対してパイプライン化が自然に行われます。

たとえば、メッセージを送信したり、whenE などの構造を使用して明示的に待機したりして、future の値が非同期的にアクセスする場合、メッセージが受信されるか待機が完了する前に、future が解決されるまで遅延させることは困難ではありません。これは、純粋なアクター言語などの完全に非同期的なシステムで考慮すべき唯一のケースです。

ただし、一部のシステムでは、将来の値に 即時または同期的にアクセスしようとすることも可能である可能性があります。その場合は、設計上の選択を行う必要があります。

• アクセスは、将来が解決されるまで（おそらくタイムアウトで）、現在のスレッドまたはプロセスをブロックする可能性があります。これは、言語Ozのデータフロー変数のセマンティクスです。
• 同期アクセスの試みは常にエラーを通知する可能性があり、例えば例外をスローする。これがEにおけるリモートプロミスのセマンティクスである。^[10]
• 潜在的には、未来がすでに解決されている場合はアクセスが成功し、そうでない場合はエラーが通知される可能性があります。これには、非決定性が導入され、競合状態が発生する可能性があるという欠点があり、一般的ではない設計上の選択と思われます。

最初の可能性の例として、C++11では、future の値を必要とするスレッドは、wait()またはメンバー関数を呼び出すことによって、その値が利用可能になるまでブロックできます。また、またはメンバー関数をget()使用して待機時にタイムアウトを指定し、無期限のブロックを回避することもできます。future が の呼び出しから発生した場合、ブロッキング待機 (タイムアウトなし) によって、待機中のスレッドで結果を計算するための関数の同期呼び出しが発生する可能性があります。 wait_for()wait_until()std::async

フューチャーは同期プリミティブ「イベント」の特殊なケースであり、一度だけ完了することができます。一般的に、イベントは初期の空の状態にリセットすることができ、したがって、必要な回数だけ完了することができます。^[11]

I -var（言語Idのように）は、上で定義されたブロッキングセマンティクスを持つフューチャーです。I -structureは、 I-varを含むデータ構造です。異なる値を複数回設定できる関連する同期構造は、M-varと呼ばれます。M-varは、現在の値を取得または設定するためのアトミック操作をサポートしており、値を取得すると、M-varは初期の空の状態に戻ります。^[12]

並行ロジック変数 [^要出典]はフューチャーに似ていますが、論理プログラミングのロジック変数と同じように、ユニフィケーションによって更新されます。したがって、ユニファイ可能な値に複数回バインドできますが、空または未解決の状態に戻すことはできません。Oz のデータフロー変数は並行ロジック変数として機能し、前述のようにブロッキングセマンティクスも持っています。

同時制約変数は、制約ロジック プログラミングをサポートするために同時ロジック変数を一般化したものです。制約は複数回絞り込まれ、可能な値のより小さなセットを示すことができます。通常、制約がさらに絞り込まれるたびに実行されるサンクを指定する方法があります。これは、制約の伝播をサポートするために必要です。

スレッド固有の Eager Future は、Future の作成と同時に値を計算するスレッドを作成することで、スレッド固有ではない Future に簡単に実装できます。この場合、新しく作成されたスレッドだけがこの Future を解決できるように、読み取り専用ビューをクライアントに返すことが望ましいです。

非スレッド固有フューチャーの観点から、暗黙的な遅延スレッド固有フューチャー（例えば、Alice MLによって提供されるもの）を実装するには、フューチャーの値が最初に必要になる時期を決定するメカニズム（例えば、WaitNeededOz ^[13]の構成要素）が必要です。すべての値がオブジェクトである場合、フォワーダーに送信された最初のメッセージがフューチャーの値が必要であることを示しているため、透過的な転送オブジェクトを実装する機能で十分です。

システムがメッセージ パッシングをサポートしていると仮定すると、解決スレッドがメッセージをフューチャー自身のスレッドに送信することで、スレッド固有のフューチャーに非スレッド固有のフューチャーを実装できます。ただし、これは不要な複雑さと見なされる場合があります。スレッドに基づくプログラミング言語では、最も表現力豊かなアプローチは、非スレッド固有のフューチャー、読み取り専用ビュー、およびWaitNeeded構造または透過的な転送のサポートを組み合わせて提供することのようです。

フューチャーの評価戦略はcall by futureとも呼ばれ、非決定的です。フューチャーの値は、フューチャーが作成されてからその値が使用されるまでの間のある時点で評価されますが、正確な時間は事前に決定されておらず、実行ごとに変わる可能性があります。計算は、フューチャーが作成されるとすぐに開始することも (積極的評価)、値が実際に必要になったときにのみ開始することも (遅延評価)、途中で中断することも、1 回の実行で実行することもできます。フューチャーの値が一度割り当てられると、フューチャーへのアクセスでは再計算されません。これは、call by needで使用されるメモ化に似ています。

あ遅延未来は、遅延評価セマンティクスを決定論的に持つ未来です。未来の値の計算は、call by need のように、値が最初に必要になったときに開始されます。遅延未来は、評価戦略がデフォルトで遅延ではない言語で使用されます。たとえば、C++11値を計算する関数とともに std::launch::deferred起動ポリシーを に渡すことで、このような遅延未来を作成できますstd::async

アクター モデルでは、フォームの式は、環境Eと顧客Cfuture <Expression>のメッセージに応答する方法によって次のように定義されます。future 式は、環境Eと顧客Cのメッセージを送信すると同時に、新しく作成されたアクターF ( の評価の応答のプロキシ) を戻り値として顧客Cに送信することで、メッセージに応答します。Fのデフォルトの動作は次のとおりです。 EvalEval<Expression><Expression>Eval

• F はリクエストR を受信すると、<Expression>次のように 評価を進めて、すでに応答 (戻り値またはスローされた例外のいずれか) を受け取っているかどうかを確認します。
  1. すでに応答 Vがある場合、
     • V が戻り値の場合、リクエストRが送信されます。
     • Vが例外の場合、リクエストRの顧客にスローされます。
  2. まだ応答がない場合、R はF内の要求キューに格納されます。
• Fが評価から応答Vを受け取ると<Expression>、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)かどうかを尋ねる要求にfor の未来が応答するまで中断します。m

futureやpromise構造は、 MultiLispやAct 1などのプログラミング言語で最初に実装されました。並行論理プログラミング言語での通信のための論理変数の使用は、 future と非常によく似ています。これらはProlog の FreezeとIC Prologで始まり、 Relational Language、 Concurrent Prolog、 guarded Horn 節(GHC)、Parlog、Strand、Vulcan、Janus、Oz-Mozart、Flow Java、およびAlice MLで真の並行性プリミティブになりました。 Idに由来し、 Reppy のConcurrent MLに含まれているデータフロー プログラミング言語の単一代入I-var は、並行論理変数によく似ています。

プロミスパイプライン技術（レイテンシを克服するためにフューチャーを使用する）は、1988年にバーバラ・リスコフとリウバ・シュリラによって発明され、 ^[6] 1989年頃にはマーク・S・ミラー、ディーン・トリブル、ロブ・ジェリングハウスによってプロジェクト・ザナドゥの文脈で独立して発明されました。 ^[14]

promiseという用語はLiskov と Shrira によって造られましたが、彼らはパイプライン メカニズムをcall-streamという名前で呼んでいましたが、これは現在ではほとんど使用されていません。

Liskov と Shrira の論文で説明されている設計と、Xanadu でのプロミス パイプラインの実装はどちらも、プロミスの値がファーストクラスではないという制限がありました。つまり、呼び出しや送信の引数、または呼び出しや送信によって返される値は、直接プロミスになることはできません (そのため、ある送信の結果のプロミスを別の送信の引数として使用する前述のプロミス パイプラインの例は、呼び出しストリームの設計や Xanadu の実装では直接表現できませんでした)。プロミスと呼び出しストリームは、Liskov と Shrira の論文で使用されているプログラミング言語であるArgus ^{[15]の公開リリースでは実装されなかったようです。Argus の開発は 1988 年頃に停止しました。 [16]プロミス パイプラインの Xanadu 実装は、1999 年に Udanax Gold [17]}のソース コードがリリースされて初めて公開され、公開されたドキュメントでは説明されていませんでした。^[18]その後の Joule と E の実装では、完全にファーストクラスのプロミスとリゾルバがサポートされています。

Actシリーズ^{[19] [20]}を含むいくつかの初期のアクター言語は、並列メッセージパッシングとパイプラインメッセージ処理の両方をサポートしていましたが、パイプライン処理はサポートしていませんでした。（最初の2つでこれらの機能の最後の機能を実装することは技術的には可能ですが、Act言語がそれを実現したという証拠はありません。）

2000 年以降、ユーザー インターフェイスの応答性の向上や、メッセージ パッシングの要求応答モデルによるWeb 開発での使用により、Future と Promise への関心が再び高まりました。現在ではいくつかの主流言語で Future と Promise が言語サポートされています。最も有名なのは、 Java 5 (2004 年発表) ^[21]と.NET 4.5 (2010 年発表、2012 年リリース) ^{[22 ] の}async/await構文です。[ ²³ ] これらは主に、 2007 年にさかのぼるF# ^[24]の非同期ワークフローに触発されています。^[25]その後、これは他の言語にも採用され、特に Dart (2014 年)、^[26] Python (2015 年)、^[27] Hack (HHVM)、ECMAScript 7 (JavaScript)、Scala、C++ (2011 年) のドラフトで採用されています。 FutureTask

一部のプログラミング言語では、直接的な言語サポートまたは標準ライブラリによって、future、promise、並行ロジック変数、データフロー変数、または I-var をサポートしています。

• ABCL/f ^[28]
• アリスML
• AmbientTalk (ファーストクラスのリゾルバと読み取り専用プロミスを含む)
• C++ 、 C++11以降: std::future および std::promise
  • 構成的 C++
• Crystal (プログラミング言語)
• Dart（Future / Completerクラス^[29]とキーワードawaitとasync ^[26]を使用）
• Elm（プログラミング言語）Taskモジュール経由^[30]
• グラスゴーハスケル(I 変数と M 変数のみ)
• Id (I-vars と M-vars のみ)
• イオ^[31]
• Java経由java.util.concurrent.Futureまたはjava.util.concurrent.CompletableFuture
• ECMAScript 2015以降のJavaScript ^[32]およびECMAScript 2017以降のキーワードおよびasync[ ^33]await
• Lucid (データフローのみ)
• いくつかのLisp
  • クロージュア^[34]
  • マルチリスプ
• タスク経由の .NET
  • C#、.NET Framework 4.5以降、^[22]キーワードasyncおよびawait^{[23]を介して}
• Kotlinは、kotlin.native.concurrent.Futureネイティブで実行することを意図したKotlinを書く場合にのみ使用されることが多い^[35]
• ニム
• オキシゲン
• オズバージョン3 ^[36]
• Pythonのconcurrent.futuresは3.2以降で^[37] 、 PEP 3148で提案され、Python 3.5ではasyncとawaitが追加された^[38]。
• R (遅延評価の約束、シングルスレッドのまま)
• ラケット^[39]
• 楽^[40]
• 錆び（通常は.await）^[41]
• scala.concurrent パッケージ経由のScala
• スキーム
• スクイーク・ スモールトーク
• ストランド
• Swift (サードパーティライブラリ経由のみ)
• Visual Basic ^{[明確化が必要]} 11 (キーワードAsyncおよびAwait経由) ^[23]

Promise パイプラインをサポートする言語には次のものがあります。

• え
• ジュール

• Common Lispの場合:
  • ブラックバード^[42]
  • 熱心な未来2 ^[43]
  • 平行^[44]
  • Pコール^[45]
• C++ の場合:
  • ブーストライブラリ^[46]
  • ドリブ^[47]
  • 愚行^[48]
  • HPX ^[49]
  • POCO C++ライブラリ（アクティブな結果）^[50]
  • クォート^[51]
  • シースター^[52]
  • スタブ^[53]
• C#およびその他の.NET言語の場合: Parallel Extensionsライブラリ
• Groovyの場合：GPars ^[54]
• JavaScriptの場合:
  • Cujo.js ^[55] when.js ^[56]はPromises/A+ ^[57] 1.1仕様に準拠したPromiseを提供する。
  • Dojo ToolkitはPromise ^[58]とTwistedスタイルの遅延型を提供する。
  • MochiKit ^[59]はTwistedのDeferredsに触発された
  • jQuery の Deferred Object は、CommonJS Promises/A 設計に基づいています。
  • アンギュラーJS ^[60]
  • ノード-約束^[61]
  • クリス・コワルによるQはPromises/A+ 1.1に準拠している^[62]
  • RSVP.jsはPromises/A+ 1.1に準拠しています^[63]
  • YUIの^[64]プロミスクラス^[65]はPromises/A+ 1.0仕様に準拠しています。
  • ブルーバード、ペトカ・アントノフ作^[66]
  • Closure Libraryの promise パッケージは、Promises/A+ 仕様に準拠しています。
  • Promise/A+ 設計に基づくその他の実装については、Promise/A+ のリストを参照してください。
• Javaの場合:
  • JDeferredは、 JQueryの.Deferredオブジェクトに似たdeferred-promise APIと動作を提供する^[67]
  • ParSeq ^[68]は、非同期パイプラインと分岐に最適なタスクプロミスAPIを提供し、LinkedInによって管理されている。
• Luaの場合:
  • cqueues [1]モジュールにはPromise APIが含まれています。
• Objective-Cの場合: MAFuture、^{[69] [70]} RXPromise、^[71] ObjC-CollapsingFutures、^[72] PromiseKit、^[73] objc-promise、^[74] OAPromise、^[75]
• OCamlの場合: Lazyモジュールは遅延明示的未来を実装します^[76]
• Perlの場合: Future、^[77] Promises、^[78] Reflex、^[79] Promise::ES6、^[80] Promise::XS ^[81]
• PHPの場合：React/Promise ^[82]
• Pythonの場合:
  • 組み込み実装^[83]
  • pythonfutures ^[84]
  • ツイステッドのディファード^[85]
• Rの場合:
  • futureは、遅延同期および即時同期と（マルチコアまたは分散）非同期futureを備えた拡張可能なfuture APIを実装します^{[86] [87]}
• Rubyの場合:
  • 並行Ruby ^[88]
  • プロミスジェム^[89]
  • libuv gem、promiseを実装^[90]
  • セルロイドの宝石、未来を実現する^[91]
  • 未来資源^[92]
• Rustの場合:
  • 先物-RS ^[93]
• Scalaの場合:
  • Twitterのユーティリティライブラリ^[94]
• Swiftの場合:
  • 非同期フレームワーク、C#スタイルのasync非ブロッキングを実装await^[95]
  • FutureKit ^{[96]はApple GCD [97]}のバージョンを実装している。
  • FutureLib、TPLスタイルのキャンセル機能を備えたScalaスタイルのFutureとPromiseを実装した純粋なSwift 2ライブラリ^[98]
  • DeferredはOCamlのDeferredに触発された純粋なSwiftライブラリである^[99]
  • ブライトフューチャーズ^[100]
  • SwiftCoroutine ^[101]
• Tclの場合: tcl-promise ^[102]

フューチャーはコルーチン^[27]またはジェネレータ^[103]で実装することができ、同じ評価戦略（例えば、協調マルチタスクまたは遅延評価）が得られます。

Futureはチャネルで簡単に実装できます。Futureは1要素のチャネルであり、Promiseはチャネルに送信してFutureを実現するプロセスです。^{[104] [105]これにより、CSPや}Goなどのチャネルをサポートする並行プログラミング言語でFutureを実装できます。結果として得られるFutureは明示的であり、評価だけでなくチャネルからの読み取りによってアクセスする必要があります。

• ファイバー（コンピュータサイエンス）
• フューテックス
• ピラミッドオブドゥーム（プログラミング）、Promise によって回避される設計アンチパターン

• scaleconf で行われた並行性パターンのプレゼンテーション
• ポートランドパターンリポジトリにおける将来の価値と約束のパイプライン
• Pythonの Future を使った簡単なスレッド化