Futures and promises
From Wikipedia, the free encyclopedia
 |
This page is a candidate to be copied to Wikibooks using the Import process. If the page can be re-written into an encyclopedic article, please do so and remove this message. Before you move this content to Wikibooks, verify that it conforms to Wikibooks policies of acceptable content at What is Wikibooks? Often content unacceptable to Wikipedia may not be acceptable on Wikibooks either; facilitate the copying of this article by listing it on Wikibooks:Requests for Import. |
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 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, futures enable pipelining of messages as in the Actor model, also called promise pipelining [1] [2] in E and Joule.
In a conventional remote procedure call, an expression like
- t3 := (x.a()).c(y.b())
which could be expanded to
- t1 := x.a(); t2 := y.b(); t3 := t1.c(t2)
Each statement requires a message to be sent and a reply received before the next statement can proceed. Suppose, for example, that x, y, t1, and t2 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 := 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)
(The former expression would be written as "t3 := (x <- a()) <- c(y <- b())" in E.) All three variables are immediately assigned futures for their results, and execution proceeds to subsequent statements. Later attempts to resolve the value of t3 may cause a delay; however, pipelining can reduce the number of round-trips required. If, as in the previous example, x, y, t1, and t2 are all located on the same remote machine, a pipelined implementation can compute t3 with one round-trip instead of three. Because all three messages are destined for objects which are on the same remote machine, only one packet needs to be sent and only one packet needs to be received containing the replies.
[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 programming 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 and Liuba Shrira 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. Also available as Indiana University Department of Computer Science Technical Report TR44.
- ^ 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.
