Incomputer science,futures,promises,delays, anddeferreds are constructs used forsynchronizing programexecution in someconcurrent programming languages. Each is an object that acts as a proxy for a result that is initially unknown, usually because thecomputation of its value is not yet complete.
The termpromise was proposed in 1976 byDaniel P. Friedman and David Wise,[1]and Peter Hibbard called iteventual.[2]A somewhat similar conceptfuture was introduced in 1977 in a paper byHenry Baker andCarl Hewitt.[3]
The termsfuture,promise,delay, anddeferred are often used interchangeably, although some differences in usage betweenfuture andpromise are treated below. Specifically, when usage is distinguished, a future is aread-only placeholder view of a variable, while a promise is a writable,single assignment container which sets the value of the future. Notably, a future may be defined without specifying which specific promise will set its value, and different possible promises may set the value of a given future, though this can be done only once for a given future. In other cases a future and a promise are created together and associated with each other: the future is the value, the promise is the function that sets the value – essentially the return value (future) of an asynchronous function (promise). Setting the value of a future is also calledresolving,fulfilling, orbinding it.
Futures and promises originated infunctional programming and related paradigms (such aslogic programming) to decouple a value (a future) from how it was computed (a promise), allowing the computation to be done more flexibly, notably by parallelizing it. Later, it found use indistributed computing, in reducing the latency from communication round trips. Later still, it gained more use by allowing writing asynchronous programs indirect style, rather than incontinuation-passing style.
Use of futures may beimplicit (any use of the future automatically obtains its value, as if it were an ordinaryreference) orexplicit (the user must call a function to obtain the value, such as theget method ofjava.util.concurrent.FutureinJava). Obtaining the value of an explicit future can be calledstinging orforcing. Explicit futures can be implemented as a library, whereas implicit futures are usually implemented as part of the language.
The original Baker and Hewitt paper described implicit futures, which are naturally supported in theactor model of computation and pureobject-oriented programming languages likeSmalltalk. The Friedman and Wise paper described only explicit futures, probably reflecting the difficulty of efficiently implementing implicit futures on stock hardware. The difficulty is that stock hardware does not deal with futures for primitive data types like integers. For example, an add instruction does not know how to deal with3 +future factorial(100000). In pure actor or object languages this problem can be solved by sendingfuture factorial(100000) the message+[3], which asks the future to add3 to itself and return the result. Note that themessage passing approach works regardless of whenfactorial(100000) finishes computation and that no stinging/forcing is needed.
The use of futures can dramatically reducelatency indistributed systems. For instance, futures enablepromise pipelining,[4][5] as implemented in the languagesE andJoule, which was also calledcall-stream[6] in the languageArgus.
Consider an expression involving conventionalremote procedure calls, such as:
t3 := ( x.a() ).c( y.b() )
which could be expanded to
t1 := x.a(); t2 := y.b(); t3 := t1.c(t2);
Each statement needs a message to be sent and a reply received before the next statement can proceed. Suppose, for example, thatx,y,t1, andt2 are all located on the same remote machine. In this case, two complete network round-trips to that machine must take place before the third statement can begin to execute. The third statement will then cause yet another round-trip to the same remote machine.
Using futures, the above expression could be written
t3 := (x <- a()) <- c(y <- b())
which could be expanded to
t1 := x <- a(); t2 := y <- b(); t3 := t1 <- c(t2);
The syntax used here is that of the language E, wherex <- a() means to send the messagea() asynchronously tox. All three variables are immediately assigned futures for their results, and execution proceeds to subsequent statements. Later attempts to resolve the value oft3 may cause a delay; however, pipelining can reduce the number of round-trips needed. If, as in the prior example,x,y,t1, andt2 are all located on the same remote machine, a pipelined implementation can computet3 with one round-trip instead of three. Because all three messages are destined for objects which are on the same remote machine, only one request need be sent and only one response need be received containing the result. The sendt1 <- c(t2) would not block even ift1 andt2 were on different machines to each other, or tox ory.
Promise pipelining should be distinguished from parallel asynchronous message passing. In a system supporting parallel message passing but not pipelining, the message sendsx <- a() andy <- b() in the above example could proceed in parallel, but the send oft1 <- c(t2) would have to wait until botht1 andt2 had been received, even whenx,y,t1, andt2 are on the same remote machine. The relative latency advantage of pipelining becomes even greater in more complicated situations involving many messages.
Promise pipelining also should not be confused withpipelined message processing in actor systems, where it is possible for an actor to specify and begin executing a behaviour for the next message before having completed processing of the current message.
In some programming languages such asOz,E, andAmbientTalk, it is possible to obtain aread-only view of a future, which allows reading its value when resolved, but does not permit resolving it:
!! operator is used to obtain a read-only view.std::future provides a read-only view. The value is set directly by using astd::promise, or set to the result of a function call usingstd::packaged_task orstd::async.System.Threading.Tasks.Task<T> represents a read-only view. Resolving the value can be done viaSystem.Threading.Tasks.TaskCompletionSource<T>.Support for read-only views is consistent with theprinciple of least privilege, since it enables the ability to set the value to be restricted tosubjects that need to set it. In a system that also supports pipelining, the sender of an asynchronous message (with result) receives the read-only promise for the result, and the target of the message receives the resolver.
Some languages, such asAlice ML, define futures that are associated with a specific thread that computes the future's value.[9] This computation can start eithereagerly when the future is created, orlazily when its value is first needed. A lazy future is similar to athunk, in the sense of a delayed computation.
Alice ML also supports futures that can be resolved by any thread, and calls thesepromises.[8] This use ofpromise is different from its use in E as describedabove. In Alice, a promise is not a read-only view, and promise pipelining is unsupported. Instead, pipelining naturally happens for futures, including ones associated with promises.
If the value of a future is accessed asynchronously, for example by sending a message to it, or by explicitly waiting for it using a construct such aswhen in E, then there is no difficulty in delaying until the future is resolved before the message can be received or the wait completes. This is the only case to be considered in purely asynchronous systems such as pure actor languages.
However, in some systems it may also be possible to attempt toimmediately orsynchronously access a future's value. Then there is a design choice to be made:
As an example of the first possibility, inC++11, a thread that needs the value of a future can block until it is available by calling thewait() orget() member functions. A timeout can also be specified on the wait using thewait_for() orwait_until() member functions to avoid indefinite blocking. If the future arose from a call tostd::async then a blocking wait (without a timeout) may cause synchronous invocation of the function to compute the result on the waiting thread.
Futures are a particular case of thesynchronization primitive "events," which can be completed only once. In general, events can be reset to initial empty state and, thus, completed as many times as desired.[11]
AnI-var (as in the languageId) is a future with blocking semantics as defined above. AnI-structure is adata structure containing I-vars. A related synchronization construct that can be set multiple times with different values is called anM-var. M-vars support atomic operations totake orput the current value, where taking the value also sets the M-var back to its initialempty state.[12]
Aconcurrent logic variable[citation needed] is similar to a future, but is updated byunification, in the same way aslogic variables inlogic programming. Thus it can be bound more than once to unifiable values, but cannot be set back to an empty or unresolved state. The dataflow variables of Oz act as concurrent logic variables, and also have blocking semantics as mentioned above.
Aconcurrent constraint variable is a generalization of concurrent logic variables to supportconstraint logic programming: the constraint may benarrowed multiple times, indicating smaller sets of possible values. Typically there is a way to specify a thunk that should run whenever the constraint is narrowed further; this is needed to supportconstraint propagation.
Eager thread-specific futures can be straightforwardly implemented in non-thread-specific futures, by creating a thread to calculate the value at the same time as creating the future. In this case it is desirable to return a read-only view to the client, so that only the newly created thread is able to resolve this future.
To implement implicit lazy thread-specific futures (as provided by Alice ML, for example) in terms in non-thread-specific futures, needs a mechanism to determine when the future's value is first needed (for example, theWaitNeeded construct in Oz[13]). If all values are objects, then the ability to implement transparent forwarding objects is sufficient, since the first message sent to the forwarder indicates that the future's value is needed.
Non-thread-specific futures can be implemented in thread-specific futures, assuming that the system supports message passing, by having the resolving thread send a message to the future's own thread. However, this can be viewed as unneeded complexity. In programming languages based on threads, the most expressive approach seems to be to provide a mix of non-thread-specific futures, read-only views, and either aWaitNeeded construct, or support for transparent forwarding.
Theevaluation strategy of futures, which may be termedcall by future, is non-deterministic: the value of a future will be evaluated at some time between when the future is created and when its value is used, but the precise time is not determined beforehand and can change from run to run. The computation can start as soon as the future is created (eager evaluation) or only when the value is actually needed (lazy evaluation), and may be suspended part-way through, or executed in one run. Once the value of a future is assigned, it is not recomputed on future accesses; this is like thememoization used incall by need.
Alazy future is a future that deterministically has lazy evaluation semantics: the computation of the future's value starts when the value is first needed, as in call by need. Lazy futures are of use in languages which evaluation strategy is by default not lazy. For example, inC++11 such lazy futures can be created by passing thestd::launch::deferred launch policy tostd::async, along with the function to compute the value.
In the actor model, an expression of the formfuture <Expression> is defined by how it responds to anEval message with environmentE and customerC as follows: The future expression responds to theEval message by sending the customerC a newly created actorF (the proxy for the response of evaluating<Expression>) as a return valueconcurrently with sending<Expression> anEval message with environmentE and customerC. The default behavior ofF is as follows:
<Expression> proceeding as follows:<Expression>, thenV is stored inF andHowever, some futures can deal with requests in special ways to provide greater parallelism. For example, the expression1 + future factorial(n) can create a new future that will behave like the number1+factorial(n). This trick does not always work. For example, the following conditional expression:
if m>future factorial(n)then print("bigger")else print("smaller")suspends until the future forfactorial(n) has responded to the request asking ifm is greater than itself.
Thefuture and/orpromise constructs were first implemented in programming languages such asMultiLisp andAct 1. The use of logic variables for communication inconcurrentlogic programming languages was quite similar to futures. These began inProlog with Freeze andIC Prolog, and became a true concurrency primitive with Relational Language, ConcurrentProlog, guardedHorn clauses (GHC),Parlog,Strand,Vulcan,Janus,Oz-Mozart,Flow Java, andAlice ML. The single-assignmentI-var fromdataflow programming languages, originating inId and included in Reppy'sConcurrent ML, is much like the concurrent logic variable.
The promise pipelining technique (using futures to overcome latency) was invented byBarbara Liskov andLiuba Shrira in 1988,[6] and independently byMark S. Miller, Dean Tribble and Rob Jellinghaus in the context ofProject Xanadu circa 1989.[14]
The termpromise was coined by Liskov and Shrira, although they referred to the pipelining mechanism by the namecall-stream, which is now rarely used.
Both the design described in Liskov and Shrira's paper, and the implementation of promise pipelining in Xanadu, had the limit that promise values were notfirst-class: an argument to, or the value returned by a call or send could not directly be a promise (so the example of promise pipelining given earlier, which uses a promise for the result of one send as an argument to another, would not have been directly expressible in the call-stream design or in the Xanadu implementation). It seems that promises and call-streams were never implemented in any public release of Argus,[15] the programming language used in the Liskov and Shrira paper. Argus development stopped around 1988.[16] The Xanadu implementation of promise pipelining only became publicly available with the release of the source code for Udanax Gold[17] in 1999, and was never explained in any published document.[18] The later implementations in Joule and E support fully first-class promises and resolvers.
Several early actor languages, including the Act series,[19][20] supported both parallel message passing and pipelined message processing, but not promise pipelining. (Although it is technically possible to implement the last of these features in the first two, there is no evidence that the Act languages did so.)
After 2000, a major revival of interest in futures and promises occurred, due to their use inresponsiveness of user interfaces, and inweb development, due to therequest–response model of message-passing. Several mainstream languages now have language support for futures and promises, most notably popularized byFutureTask in Java 5 (announced 2004)[21] and theasync/await constructions in .NET 4.5 (announced 2010, released 2012)[22][23] largely inspired by theasynchronous workflows of F#,[24] which dates to 2007.[25] This has subsequently been adopted by other languages, notably Dart (2014),[26] Python (2015),[27] Hack (HHVM), and drafts of ECMAScript 7 (JavaScript), Scala, and C++ (2011).
Some programming languages are supporting futures, promises, concurrent logic variables, dataflow variables, or I-vars, either by direct language support or in the standard library.
std::future andstd::promiseFuture/Completer classes[29] and the keywordsawait andasync[26])java.util.concurrent.Future orjava.util.concurrent.CompletableFutureasync andawait since ECMAScript 2017[33]System.Threading.Tasks.Taskkotlin.native.concurrent.Future is only usually used when writing Kotlin that is intended to run natively[35]async andawait[38]std::future::Future, promise achieved via.await)[41]Languages also supporting promise pipelining include:
async/non-blockingawait[95]Futures can be implemented incoroutines[27] orgenerators,[103] resulting in the same evaluation strategy (e.g.,cooperative multitasking or lazy evaluation).
Futures can easily be implemented inchannels: a future is a one-element channel, and a promise is a process that sends to the channel, fulfilling the future.[104][105] This allows futures to be implemented in concurrent programming languages with support for channels, such as CSP andGo. The resulting futures are explicit, as they must be accessed by reading from the channel, rather than only evaluation.