Futures and promises
From Wikipedia, the free encyclopedia
In computer science, futures and promises are closely related constructs used for synchronization in some concurrent programming languages. They both refer to an object that acts as a proxy for a result that is initially not known, usually because the computation of its value has not yet completed. The term "future" was introduced in 1977 in a paper by Henry Baker and Carl Hewitt [1], although a somewhat similar concept was proposed in 1976 by Daniel P. Friedman and David Wise [2]. However, the Friedman and Wise construct involved "stinging" the value to be computed before retrieving it reflecting a difficulty of efficiently implementing futures on stock hardware. The difficulty is that stock hardware does not deal with futures for primitive data types like integers. E.g., an add instruction does not know how to deal with 3 + future factorial(100000). In the Actor model of computation and programming languages like Smalltalk-72 this problem can be solved by sending future factorial(100000) the message +[3] which asks the future to add 3 to itself and return the result. Note that the message passing approach works regardless of when factorial(100000) finishes computation and that no "stinging" is required.
Contents |
[edit] Definition
The denotational semantics of programming languages can be used to provide a definition of futures: An expression of the form future <Expression> is defined by how it responds to an Eval message with environment E and customer C as follows: The future expression responds to the Eval message by sending the customer C a newly created actor F (the proxy for the value of <Expression>) as a return value concurrently with sending <Expression> an Eval message with environment E and customer F. The behavior of F is as follows:
-
- When F receives a request R, then it checks to see if it has already received a return value from evaluating <Expression> proceeding as follows:
-
- If it already has a return value V, then V is sent the request R.
- If it does not already have a return value, then R is stored in the queue of requests inside the F.
-
- When F receives the return value V from evaluating <Expression>, then then V is stored in F and all of the queued requests are sent to V.
[edit] Pipelining
The use of futures can dramatically reduce latency in distributed systems. For instance, it enables pipelining of messages as in the Actor model, also called promise pipelining [1] [2] in E and Joule.
In a conventional RPC an expression like
- t3 := (x.a()).c(y.b())
which could be expanded to
- t1 := x.a(); t2 := y.b(); t3 := t1.c(t2)
means that t3 is not computed until after the values of t1 and t2 have been computed.
Using futures, the above expression could be written
- t3 := future (future x.a()).c(future y.b())
which could be expanded to
- t1 := future x.a(); t2 := future y.b(); t3 := future t1.c(t2)
meaning that t3 is computed immediately. (This example would be written as "t3 := (x <- a()) <- c(y <- b())" in E.) However any attempt to obtain information from t3 may have to wait.
[edit] Generalizations
A concurrent logic variable is similar to a promise, but is updated by unification, in the same way as logic variables in logic programming. Thus it can be fulfilled more than once with unifiable values. In the Oz programming language, a concurrent logic variable is called a dataflow variable.
A concurrent constraint variable is a generalization of concurrent logic variables to support constraint logic programming: the constraint may be narrowed multiple times, indicating smaller sets of possible values. Typically there is a way to specify a thunk that should be run whenever the constraint is narrowed further; this is necessary to support constraint propagation.
In some languages, for example E, "promise" refers to a read-only view of the value, and a separate object called a resolver is used to fulfill the promise. This allows the ability to set the value to be restricted. In Oz a similar effect can be achieved by using the !! operator to obtain a read-only view of a dataflow variable.
Use of futures or promises may be implicit (any use of the future/promise automatically obtains its value, as if it were an ordinary reference) or explicit (the user must call a function to obtain the value, such as the get method of java.util.concurrent.Future in Java). Explicit futures/promises may be implemented as a library, whereas implicit futures/promises require language support.
[edit] Distinction between futures and promises
Although futures and delays are well defined, the term promise is used ambiguously. When a distinction is made between futures and promises (for example in programming languages such as Alice ML that support both [3] [4]), they are defined as follows:
- a future is associated with a specific thread that computes its value. This computation may be started either eagerly when the future is created, or lazily when its value is first needed. A lazy future is similar to a thunk (in the sense of a delayed computation).
- a promise acts as a single-assignment variable, which may be set or fulfilled by any thread.
A promise can also be called an I-var (as in the Id programming language). An I-structure is a data structure containing I-vars/promises.
Normally a future or promise can only be fulfilled once (a related synchronization construct that can be set multiple times with different values is called an M-var).
The distinction between "future" and "promise" as defined above is not always made consistently, and some sources may use these terms as synonyms. Eager futures can be straightforwardly implemented in terms of promises, by creating a thread to calculate the value at the same time as creating the promise/resolver. 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 fulfill this promise.
To implement implicit lazy futures in terms of promises requires a mechanism to determine when the promise's value is first needed (for example the WaitNeeded construct in Oz). The ability to implement transparent forwarding objects (as supported by E and Joule) is sufficient, since the first message sent to the forwarder indicates that the promise is needed.
Promises cannot be easily implemented in terms of futures, because a future has to be fulfilled by a specific thread. Therefore, the most expressive approach appears to be to provide a combination of promises, read-only views, and either a 'WaitNeeded' construct or support for transparent forwarding.
[edit] Implementations
The future and/or promise constructs were implemented in programming languages such as MultiLisp and Act 1. The use of logic variables for communication in concurrent logic programming languages was quite similar to promises. These started with "Prolog with Freeze" and "IC Prolog", and became a true concurrency primitive with Concurrent Prolog, Flat Concurrent Prolog, Parlog, Vulcan, Janus, Mozart/Oz, Flow Java, and Alice ML. The single-assignment "I-var" from dataflow languages, originating in Id and included in Reppy's "Concurrent ML", is much like the concurrent logic variable.
The pipelining technique (using futures to overcome latency) was first invented for the Actor model and then re-invented by Barbara Liskov in 1988 and in the Project Xanadu (circa 1989).
Languages supporting futures, promises, concurrent logic variables, dataflow variables, or I-vars include:
Languages also supporting promise pipelining include:
[edit] See Also
[edit] References
- ^ Baker, Henry (August 1977). "The Incremental Garbage Collection of Processes". Proceedings of the Symposium on Artificial Intelligence Programming Languages, SIGPLAN Notices 12.
- ^ Friedman, Daniel (1976). "CONS should not evaluate its arguments". S. Michaelson and R. Milner, editors, Automata, Languages and Programming, pages 257-284. Edinburgh University Press, Edinburgh.
- ^ Henry Lieberman. "A Preview of Act 1". MIT AI memo 625.
- ^ Henry Lieberman. "Thinking About Lots of Things at Once without Getting Confused: Parallelism in Act 1". MIT AI memo 626.
- ^ Steve Dekorte (2005). Io, The Programming Language.
