العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolFUTURES AND PROMISES
(Redirected from Future (programming))
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
[1]. 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.
The denotational semantics of programming languages can be used to provide a definition of futures: An expression of the form ''future''
:
★ When 'F' receives a request 'R', then it checks to see if it has already received a return value from evaluating
::#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
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 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)
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 are on the same machine, only one packet needs to be sent to the remote machine and only one packet needs to be received containing the replies.
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.
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.
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 in 1988 and in the Project Xanadu (circa 1989).
Languages supporting futures, promises, concurrent logic variables, dataflow variables, or I-vars include:
★ Act 1, 2 and 3 [1][1]
★ Id
★ Glasgow Haskell
★ Alice ML
★ Io [5]
★ Oz
★ MultiLisp
★ Java (explicit futures only)
Languages also supporting promise pipelining include:
★ Joule
★ E
★ Delay (programming)
★ Lazy evaluation
1.
2.
3.
4.
5. Io, The Programming Language Steve Dekorte
★ Future Value and Promise Pipelining at the Portland Pattern Repository
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
[1]. 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 |
| Definition |
| Pipelining |
| Generalizations |
| Distinction between futures and promises |
| Implementations |
| See also |
| References |
| External links |
Definition
The denotational semantics of programming languages can be used to provide a definition of futures: An expression of the form ''future''
:
★ When 'F' receives a request 'R', then it checks to see if it has already received a return value from evaluating
::#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
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 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)
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 are on the same machine, only one packet needs to be sent to the remote machine and only one packet needs to be received containing the replies.
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.
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.
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 in 1988 and in the Project Xanadu (circa 1989).
Languages supporting futures, promises, concurrent logic variables, dataflow variables, or I-vars include:
★ Act 1, 2 and 3 [1][1]
★ Id
★ Glasgow Haskell
★ Alice ML
★ Io [5]
★ Oz
★ MultiLisp
★ Java (explicit futures only)
Languages also supporting promise pipelining include:
★ Joule
★ E
See also
★ Delay (programming)
★ Lazy evaluation
References
1.
2.
3.
4.
5. Io, The Programming Language Steve Dekorte
External links
★ Future Value and Promise Pipelining at the Portland Pattern Repository
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
