Futures and promises

The term promise was proposed in 1976 by Daniel Friedman and David Wise, ^[1] and Peter Hibbard called it eventual . ^[2] A similar concept called the future was proposed in 1977 in an article by Henry Baker and Carl Hewitt. ^[3]

The terms future , promise and delay are often interchangeable, but the difference between future and promise is described below. The future usually means a read-only representation of a variable, and a promise is a modifiable container with a single assignment that conveys the value of the future . ^[4] Future can be determined without specifying from which promise the value will be derived. Also several promises can be associated with one future , but only one promise can assign a future value. In other cases, future and promise are created together and linked to each other: the future is the value, and the promise is the function that assigns the value. In practice, the future is the return value of the promise asynchronous function. The process of assigning a future value is called resolving , fulfilling, or binding .

Some sources in Russian use the following translations of terms: for future - future results ^[5] , futures ^{[6] [7] [8]} ; promise for promise ^{[9] [5]} ; for delay - the delay.

It should be noted that innumerable (“ future ”) and double-word (“ future meaning ”) translation options have very limited applicability (see discussion ). In particular, the Alice ML language endows futures first-class properties, including providing first-class futures ML modules — future modules and future type modules ^[10] future type modules all these terms are untranslatable using these options. A possible translation of the term in this case turns out to be “ future ” - respectively, giving the group of terms “ first-class future ”, “ module-level future ”, “ future structures ” and “ future signatures ”. A free translation of “ perspective ” is possible, with a corresponding terminological set.

Using the future can be implicit (any reference to the future returns a reference to the value) and explicit (the user must call a function to get the value). An example is the get method of the java.util.concurrent.Future class in the Java language . Getting a value from an explicit future is called stinging or forcing . Explicit futures can be realized as a library, while implicit fronts are usually implemented as part of the language.

The article by Baker and Hewitt describes implicit futures that are naturally supported in the computational model of actors and purely object-oriented languages, such as Smalltalk . The Friedman and Wise article described only explicit futures, most likely due to the complexity of implementing implicit futures on ordinary computers. The difficulty lies in the fact that at the hardware level it will not be possible to work with the future as with a primitive data type, like integers. For example, using the add instruction will fail to process 3 + future factorial (100000) . In purely objective languages ​​and languages ​​that support the model of actors, this problem can be solved by sending the future factorial (100000) message + [3] , in which the future will be reported to add 3 and return the result. It is worth noting that the message passing approach works regardless of how long factorial (100000) takes to calculate, without needing to use stinging or forcing.

With the future, delays in distributed systems are significantly reduced. For example, with the future, you can create a pipeline from promise ^{[11] [12]} , which is implemented in languages ​​such as E and Joule , as well as in Argus called call-stream .

Consider an expression using traditional remote procedure calls :

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

which can be revealed as

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

In each statement, you must first send a message and get an answer to it before proceeding to the next. Suppose that x , y , t1 and t2 are on the same remote machine. In this case, to complete the third statement, you first need to perform two data transfers over the network. Then the third statement will perform another data transfer to the same remote machine.

This expression can be rewritten using the future.

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

and disclosed as

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

This uses the syntax from the E language, where x <- a () means "asynchronously send a () message to x ". All three variables become future, and program execution continues. Later, when trying to get the value of t3 , there may be a delay; however, using a conveyor can reduce it. If, as in the previous example, x , y , t1 and t2 are located on the same remote machine, then it is possible to implement the calculation of t3 using a conveyor and a single transfer of data over the network. Since all three messages are for variables located on the same remote machine, to get the result, you need to execute just one request and get one answer. It is worth noting that the transfer of t1 <- c (t2) will not be blocked, even if t1 and t2 were on different machines relative to each other or to x and y .

The use of a promise pipeline should be distinguished from parallel asynchronous message passing. In systems that support parallel message transfer, but do not support pipelines, sending the x <- a () and y <- b () messages from the example can be done in parallel, but to send t1 <- c (t2) you will have to wait until t1 is received and t2 , even if x , y , t1 and t2 are on the same remote machine. The advantage in time delay when using the pipeline becomes more significant in difficult situations where sending multiple messages is required.

It is important not to confuse the conveyor from the promise with the conveyor message in the actor systems, where it is possible for the actor to specify and start executing the behavior for the next message until the end of the previous one.

In some programming languages, such as Oz , E and AmbientTalk , it is possible to get an immutable representation of the future, which allows you to get its value after resolve, but does not allow you to resolve:

• In Oz, an operator is used to get a fixed representation ! .
• In E and AmbientTalk, the future is a pair of promise / resolver values. A promise is an immutable representation, and a resolver is needed to assign a future value.
• In C ++ 11, std::future is an immutable representation. The value is assigned directly using std::promise or is obtained from the result of executing the function std::packaged_task or std::async .
• In the Dojo Toolkit Deferred API 1.5, a consumer-promise object is an immutable representation. ^[13]
• In Alice ML future, they provide only an immutable representation , and the promise contains the capabilities of the future and the ability to resolve ^{[14] [15]}
• In .NET 4.0, System.Threading.Tasks.Task<T> is an immutable representation. Resolve values ​​can be performed using System.Threading.Tasks.TaskCompletionSource<T> .

Support for immutable views is consistent with the principle of least privilege , since access to a value can be granted only to those objects that need it. In systems that support pipelines, the sender of the asynchronous message (with the result) receives an unchangeable promise of the result, and the recipient of the message receives the resolver.

In some languages, such as Alice ML , future bind to a specific thread that calculates a value. Calculation can begin immediately when creating a future or lazily , that is, when necessary. The "lazy" future resembles thunk (in terms of deferred calculation).

Alice ML also supports future, which can be resolved by any thread, and there it is also called promise . ^[14] It is worth noting that in this context, promise does not mean that, in the example in E, discussed above , the promise in Alice is not an immutable representation, and the creation of promise pipelines is not supported in Alice. But conveyors naturally work with the future (including those that are tied to the promise).

If asynchronous access is made to the future value, for example, when sending a message to it or waiting using the when in E, then it is easy to wait for the future to be resolved before receiving the message. This is the only point that needs to be taken into account in purely asynchronous systems, such as actor-model languages.

However, in some systems it is possible to access the future value immediately and synchronously . This can be achieved in the following ways:

• when accessing, the current thread or process is blocked until the future is resolved (possibly with the use of wait). These are semantics of stream variables in the Oz language.
• an attempt to synchronously gain access always gives an error, for example, throwing an exception . These are the semantics of remote promises in E. ^[16]
• theoretically, such a situation is possible that access will be obtained if the future is allowed, otherwise an error will be caused. This approach is not good, because the program becomes non-deterministic, and a potential race condition arises.

The first method, for example, is implemented in C ++ 11 , where the thread in which the future value is required can be blocked until the wait() or get() member functions are called. Using wait_for() or wait_until() , you can explicitly specify a wait time to avoid permanent blocking. If the future is obtained as a result of executing std::async , then with a blocking wait (without timeout) on the waiting thread, the result of executing the function can be obtained simultaneously.

The i-variable (in the Id language) is a future with the blocking semantics described above. I-structure - a data structure consisting of I-variables. A similar construction used for synchronization, in which a value can be assigned several times, is called an M-variable . M-variables support atomic operations of getting and writing the value of a variable, where getting the value returns the M-variable to the empty state. ^[17]

A parallel logical variable is similar to the future, but it is updated during unification in the same way as logical variables in logical programming . Therefore, it may be associated with more than one unified value (but cannot return to the empty or unresolved state). Stream variables in the Oz language work as parallel logical variables with blocking semantics described above.

A parallel variable with constraints is a generalization of parallel logical variables with support for logical programming with constraints : the constraint can narrow the set of acceptable values ​​several times. There is usually a way to specify the thunk, which will be executed at each narrowing; This is necessary to support the propagation of the constraint .

Energetically calculated flow-specific future can be realized directly in terms of non-flow-specific future, by creating a stream to calculate the value at the time of the future. In this case, it is desirable to return a view with read-only access to the client, so that only the created thread can execute this future.

To implement implicit lazy thread-specific futures (for example, as in the Alice ML language) in terms of non-thread-specific future, a mechanism is needed to determine the first point of using the future value (for example, the WaitNeeded construction in Oz ^[18] ). If all values ​​are objects, then it is enough to implement transparent objects to send the value, since the very first message to the sending object means that it is necessary to calculate the future value.

Non-thread specific future can be realized through thread-specific future assuming that the system supports message passing. A thread requiring a future value may send a message to the future stream. However, this approach introduces excessive complexity. In thread-based programming languages, the most expressive approach is probably a combination of non-thread-specific future, read-only views, and either the 'WaitNeeded' construct or support for transparent forwarding.

The strategy of calculating “call by purpose” ( eng. Call by future ) is non-deterministic: the value of the future will be calculated at some point in time after creation, but before use. The calculation can be started immediately after the creation of the future (“energetic calculations” - eager evaluation ), or only at the moment when the value is required ( lazy calculations , delayed calculations). After the result of the future is calculated, no re-calculation takes place on subsequent calls. Thus, the future will provide both call by need and memoization .

The lazy future concept (lazy future) provides the deterministic semantics of lazy calculation: the calculation of the future value starts when the value is first used, as in the "call by need" method. Lazy future is useful in non-lazy computing programming languages. For example, in C ++ 11, a similar construct can be created by specifying the launch policy std::launch::sync for std::async with the transfer of the function that calculates the value.

In the Actors model, the expression ''future'' <Expression> is determined by the response to the Eval message in the E environment for consumer C in the following way: The future expression responds to the Eval message by sending the new created actor F to the consumer C (a proxy for the answer with the calculation <Expression> ) as a return value, at the same time as sending the <Expression> expression of an Eval message in environment E to customer C. The behavior of F is defined as:

• When F receives a R request, it checks whether a response (return value or exception) was previously received from the <Expression> calculation:
  1. If the answer was V , then
     • If V is a value, send it in response to an R request.
     • If V is an exception, send it to the sender of the request R.
  2. If a response has not been received previously, R is stored in the request queue within F.
• When F receives the answer V from the <Expression> calculation, that answer is saved in F and
  • If V is a value, all requests from the queue receive V.
  • If V is an exception, it is forwarded to all requestors stored in the queue.

Some future implementations may otherwise process requests to increase the degree of concurrency. For example, the expression 1 + future factorial (n) can create a new future that will behave like the number 1 + factorial (n) .

The future and promise designs were first implemented in the programming languages MultiLisp and Act 1 . The use of logical variables for interaction in competitive logic programming languages ​​is quite similar to the future. Among them are Prolog with Freeze and IC Prolog , a full-fledged competitive primitive implemented Relational Language , Concurrent Prolog , Guarded Horn Clauses (GHC), Parlog , Strand , Vulcan , Janus , Mozart / Oz , Flow Java and Alice ML . Single I-var assignments from data flow programming languages ​​( dataflow ), originally appeared in Id and included in Reppy Concurrent ML , are similar to competitive logic variables.

Техника конвейера из promise, использующая futures для преодоления задержек, была предложена Барбарой Лисков и Liuba Shrira в 1988 году ^[19] , и, независимо от них, Mark S. Miller , Dean Tribble и Rob Jellinghaus в рамках Project Xanadu около 1989 ^[20] .

Термин promise был предложен Лисков и Shrira, хотя они назвали механизм конвейеризации call-stream (сейчас это название используется редко).

В обоих работах и в реализации конвейера promise в Xanadu, значения promise не являлись объектом первого класса : аргументы функций и возвращаемые значения не могли являться непосредственно promise (что усложняет реализацию конвейера, например в Xanadu). promise и call-stream не были реализованы в публичных версиях Argus ^[21] (языка программирования, использованных в работах Лисков и Shrira); Argus прекратил развитие в 1988 году. ^[22] Реализация конвейера в Xanadu стала доступна только с выходом Udanax Gold ^[23] в 1999, и не объяснялась в опубликованной документации. ^[24]

Реализации promise в Joule и E поддерживают их в качестве объектов первого класса.

Несколько ранних Actor-языков, в том числе языки Act, ^{[25] [26]} поддерживали параллельную передачу сообщений и конвейерную обработку сообщений, но не конвейер promise. (Несмотря на возможность реализации конвейера promise через поддерживаемые конструкции, нет свидетельств подобных реализаций в языках Act.)

Концепция Future может быть реализована в терминах каналов : future является одноэлементным каналом, а promise является процессом, посылающим значение в канал, выполняя future ^[27] . Таким образом реализуются future в таких конкурентных языках с поддержкой каналов как CSP и Go . Реализуемые в них future являются явными, поскольку доступ к ним производится через чтение из канала, а не в рамках обычного вычисления выражений.

• Future Value и Promise Pipelining в энциклопедии C2 ( Portland Pattern Repository ) (англ.)
• Easy Threading with Futures в языке программирования Python (англ.)
• http://scrutator.me/post/2012/06/03/parallel-world-p2.aspx