diff options
| -rw-r--r-- | _bibliography/futures.bib | 132 | ||||
| -rw-r--r-- | _layouts/chapter.html | 1 | ||||
| -rw-r--r-- | chapter/2/futures.md | 170 |
3 files changed, 230 insertions, 73 deletions
diff --git a/_bibliography/futures.bib b/_bibliography/futures.bib index 13e2f19..8cb712b 100644 --- a/_bibliography/futures.bib +++ b/_bibliography/futures.bib @@ -25,7 +25,7 @@ pages = {727-739}, } -@article{1, +@article{Multilisp, author = {Halstead,Jr., Robert H.}, title = {MULTILISP: A Language for Concurrent Symbolic Computation}, journal = {ACM Trans. Program. Lang. Syst.}, @@ -44,24 +44,7 @@ address = {New York, NY, USA}, } -@inproceedings{2, - author = {Liskov, B. and Shrira, L.}, - title = {Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems}, - booktitle = {Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation}, - series = {PLDI '88}, - year = {1988}, - isbn = {0-89791-269-1}, - location = {Atlanta, Georgia, USA}, - pages = {260--267}, - numpages = {8}, - url = {http://doi.acm.org/10.1145/53990.54016}, - doi = {10.1145/53990.54016}, - acmid = {54016}, - publisher = {ACM}, - address = {New York, NY, USA}, -} - -@article{3, +@article{Promises88, author = {Liskov, B. and Shrira, L.}, title = {Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems}, journal = {SIGPLAN Not.}, @@ -80,6 +63,17 @@ address = {New York, NY, USA}, } +@article{Argus88, + title={Distributed programming in Argus}, + author={Liskov, Barbara}, + journal={Communications of the ACM}, + volume={31}, + number={3}, + pages={300--312}, + year={1988}, + publisher={ACM} +} + @article{4, author = {Eriksen, Marius}, title = {Your Server As a Function}, @@ -208,7 +202,7 @@ url = {http://stackoverflow.com/questions/14541975/difference-between-future-and-promise} } -@misc{23, +@misc{whatisthis, title={Welcome to Thunk.org!}, url = {https://thunk.org/} } @@ -329,7 +323,7 @@ keywords = {Compiling, Lisp, functional combinations, multiprocessing, recursion, suspensions, suspensions, Compiling, functional combinations, Lisp, multiprocessing, recursion}, } -@techreport{36, +@techreport{Hewitt77, author = {Baker,Jr., Henry G. and Hewitt, Carl}, title = {The Incremental Garbage Collection of Processes}, year = {1977}, @@ -338,7 +332,7 @@ address = {Cambridge, MA, USA}, } -@inproceedings{37, +@inproceedings{ELang, author = {Miller, Mark S. and Tribble, E. Dean and Shapiro, Jonathan}, title = {Concurrency Among Strangers: Programming in E As Plan Coordination}, booktitle = {Proceedings of the 1st International Conference on Trustworthy Global Computing}, @@ -354,6 +348,49 @@ address = {Berlin, Heidelberg}, } +@article{PromisePipe07, + title={The Promise System}, + author = {Miller, Mark S. and Tribble, E. Dean and Jellinghaus, Rob}, + journal={Presentation}, + url = {http://web.archive.org/web/20071023111712/http://www.sunless-sea.net/Transcripts/promise.html}, + year={2007} +} + +@techreport{Joule, + title={Joule: Distributed application foundations}, + author={Tribble, E. Dean and Miller, Mark S. and Hardy, Norm and Krieger, David}, + number={ADd003.4P}, + institution={Agorics, Inc.}, + url={http://www.erights.org/history/joule/MANUAL.BK2.pdf}, + year={1995} +} + +@misc{Twisted, + author = {Glyph Lefkowitz}, + title = {Twisted}, + year = {2002}, + publisher = {GitHub}, + journal = {GitHub repository}, + howpublished = {\url{https://github.com/twisted/twisted}} +} + +@misc{Qjs, + author = {Kris Kowal}, + title = {Q.js}, + year = {2009}, + publisher = {GitHub}, + journal = {GitHub repository}, + howpublished = {\url{https://github.com/kriskowal/q}} +} + +@online{JQueryPromises, + author = {Valerio Gheri}, + title = {JavaScript Promises and Why JQuery Implementation is Broken}, + year = 2013, + url = {\url{https://thewayofcode.wordpress.com/tag/jquery-deferred-broken/}}, + urldate = {2017-01-06} +} + @INPROCEEDINGS{38, author = {Didier Le Botlan and Guido Tack and Andreas Rossberg and Andreas Rossberg and Didier Le and Botlan Guido Tack and Thorsten Brunklaus and Thorsten Brunklaus and Gert Smolka and Gert Smolka}, title = {Alice through the looking glass}, @@ -369,6 +406,38 @@ url = {https://speakerdeck.com/heathermiller/futures-and-promises-in-scala-2-dot-10} } +@article{SIP14, + title={Futures and promises}, + author={Haller, Philipp and Prokopec, Aleksandar and Miller, Heather and Klang, Viktor and Kuhn, Roland and Jovanovic, Vojin}, + journal={Scala Documentation}, + url = {http://docs.scala-lang.org/overviews/core/futures.html}, + year={2013} +} + +@article{PromisesAPlus, + title={Promises/A+ Specification}, + author={Promises/A+}, + journal={Promises/A+ Specification}, + url = {https://promisesaplus.com/}, + year={2013} +} + + +@article{PromisesA, + title={CommonJS Promises/A Specification}, + author={Kris Zyp}, + journal={Promises/A Specification}, + url = {http://wiki.commonjs.org/wiki/Promises/A}, + year={2009} +} + +@misc{Ecmascript15, + title={ECMAScript Language Specification}, + author={ECMAScript, ECMA and European Computer Manufacturers Association and others}, + year={2015} +} + + @misc{40, title={Futures and promises}, url = {https://en.wikipedia.org/wiki/Futures_and_promises} @@ -409,3 +478,22 @@ title={futures}, url = {https://www.ps.uni-saarland.de/alice/manual/futures.html} } + +@article{Thunks, + author = {Ingerman, P. Z.}, + title = {Thunks: A Way of Compiling Procedure Statements with Some Comments on Procedure Declarations}, + journal = {Commun. ACM}, + issue_date = {Jan. 1961}, + volume = {4}, + number = {1}, + month = jan, + year = {1961}, + issn = {0001-0782}, + pages = {55--58}, + numpages = {4}, + url = {http://doi.acm.org/10.1145/366062.366084}, + doi = {10.1145/366062.366084}, + acmid = {366084}, + publisher = {ACM}, + address = {New York, NY, USA}, +} diff --git a/_layouts/chapter.html b/_layouts/chapter.html index 78257b4..95e963e 100644 --- a/_layouts/chapter.html +++ b/_layouts/chapter.html @@ -98,7 +98,6 @@ Random post: <a href="{{ site.baseurl }}{{ site.categories.blog[random].url }}">{{ site.categories.blog[random].title }}</a> {% endif %} </div> - <!-- {{ site.categories.blog.size > 3}} --> </div> <div class="col-sm-4"></div> </div> diff --git a/chapter/2/futures.md b/chapter/2/futures.md index 0075773..84d7254 100644 --- a/chapter/2/futures.md +++ b/chapter/2/futures.md @@ -1,84 +1,154 @@ --- layout: page -title: "Futures" -by: "Kisalaya Prasad and Avanti Patil" +tag: futures and promises +title: "Futures and Promises" +subtitle: "Futures and promises are a popular abstraction for asynchronous programming, especially in the context of distributed systems. We'll cover the motivation for and history of these abstractions, and see how they have evolved over time. We’ll do a deep dive into their differing semantics, and various models of execution. This isn't only history and evolution; we’ll also dive into futures and promises most widely utilized today in languages like JavaScript, Scala, and C++." +by: "Kisalaya Prasad, Avanti Patil, and Heather Miller" --- -# Introduction +## Introduction -As human beings we have an ability to multitask ie. we can walk, talk and eat at the same time except when you sneeze. Sneeze is like a blocking activity from the normal course of action, because it forces you to stop what you’re doing for a brief moment and then you resume where you left off. Activities like multitasking are called multithreading in computer lingo. In contrast to this behaviour, computer processors are single threaded. So when we say that a computer system has multi-threaded environment, it is actually just an illusion created by processor where processor’s time is shared between multiple processes. Sometimes processor gets blocked when some tasks are hindered from normal execution due to blocking calls. Such blocking calls can range from IO operations like read/write to disk or sending/receiving packets to/from network. Blocking calls can take disproportionate amount of time compared to the processor’s task execution i.e. iterating over a list. +As human beings we have the ability to multitask _i.e._ we can walk, talk, and eat at the same time except when sneezing. Sneezing is a blocking activity because it forces you to stop what you’re doing for a brief moment, and then you resume where you left off. One can think of the human sense of multitasking as multithreading in the context of computers. +Consider for a moment a simple computer processor; no parallelism, just the ability to complete one task or process at a time. In this scenario, sometimes the processor is blocked when some blocking operation is called. Such blocking calls can include I/O operations like reading/writing to disk, or sending or receiving packets over the network. And as programmers, we know that blocking calls like I/O can take a disproportionately more time than a typical CPU-bound task, like iterating over a list. -The processor can either handle blocking calls in two ways: -- **Synchronous method**: As a part of running task in synchronous method, processor continues to wait for the blocking call to complete the task and return the result. After this processor will resume processing next task. Problem with this kind of method is CPU time not utilized in an ideal manner. -- **Asynchronous method**: When you add asynchrony, you can utilize the time of CPU to work on some other task using one of the preemptive time sharing algorithm. This is not blocking the processor at any time and when the asynchronous call returns the result, processor can again switch back to the previous process using preemption and resume the process from the point where it’d left off. +The processor can handle blocking calls in two ways: -In the world of asynchronous communications many terminologies were defined to help programmers reach the ideal level of resource utilization. As a part of this article we will talk about motivation behind rise of Promises and Futures, how the current notion we have of futures and promises have evolved over time, try to explain various execution models associated with it and finally we will end this discussion with how this construct helps us today in different general purpose programming languages. +- **Synchronously**: the processor waits until the blocking call completes its task and returns the result. Afterwards, the processor will move on to processing the next task. _This can oftentimes be problematic because the CPU may not be utilized in an efficient manner; it may wait for long periods of time._ +- **Asynchronously**: When tasks are processed asynchronously, CPU time spent waiting in the synchronous case is instead spent processing some other task using a preemptive time sharing algorithm. That is, rather than wait, process some other task instead. Thus, the processor is never left waiting at any time. +In the world of programming, many constructs have been introduced in order to help programmers reach ideal levels of resource utilization. Arguably one of the most widely-used of which are futures and/or promises. -<figure> - <img src="./images/1.png" alt="timeline" /> -</figure> +In this chapter, we'll do a deep dive into futures and promises, a popular abstraction for doing both synchronous and asynchronous programming. We'll go through the motivation for and history of these abstractions, understand what sort of scenarios they're useful for, and cover how they have evolved over time. We'll cover the various models of execution associated with these abstractions, and finally we'll touch on the futures and promises most widely utilized today in different general purpose programming languages such as JavaScript, Scala, and C++. + +## The Basic Idea + +As we'll see in subsequent sections, what we choose to call this concept, and its precise definition tends to vary. We will start with the widest possible definition of the concept of a future/promise, and later zoom in and cover the many semantic differences between different languages' interpretations of these constructs. + +In the broadest sense, + +<blockquote> + <p>A <i>future or promise</i> can be thought of as a value that will <i>eventually</i> become available.</p> +</blockquote> + +Or said another way, it is an abstraction which encodes a notion of time. By choosing to use this construct, it is assumed that your value can now have many possible states, depending on the point in time which we request it. The simplest variation includes two time-dependent states; a future/promise is either: + +1. **_completed_/_determined_**: the computation is complete and the future/promise's value is available. +2. **_incomplete_/_undetermined_**: the computation is not yet complete. + +As we'll later see, other states have been introduced in some variations of futures/promises to better support needs like error-handling and cancellation. + +Importantly, futures/promises typically enable some degree of concurrency. That is, in one of first defitions of futures: + +<blockquote> + <p>The construct <code>( future X )</code> immediately returns a future for the value of the expression <code>X</code> and <strong>concurrently</strong> begins evaluating <code>X</code>. When the evaluation of <code>X</code> yields a value, that value replaces the future.</p> + <footer>{% cite Multilisp --file futures%}</footer> +</blockquote> + +Some interpretations of futures/promises have a type associated with them, others not. Typically a future/promise is single-assignment; that is, you it can only be written to once. Some interpretations are blocking (synchronous), others are completely non-blocking (asynchronous). Some interpretations must be explicitly _kicked off_ (i.e., manually started), while in other interpretations, computation is started implicitly. -# Motivation +Inspired by functional programming, one of the major distinctions between different interpretations of this construct have to do with _pipelineing_ or _composition_. Some of the more popular interpretations of futures/promises make it possible to _chain_ operations, or define a pipeline of operations to be invoked upon completion of the computation represented by the future/promise. This is in contrast to callback-heavy or more imperative direct blocking approaches. -The rise of promises and futures as a topic of relevance can be traced parallel to the rise of asynchronous or distributed systems. This seems natural, since futures represent a value available in Future which fits in very naturally with the latency which is inherent to these heterogeneous systems. The recent adoption of NodeJS and server side Javascript has only made promises more relevant. But, the idea of having a placeholder for a result came in significantly before than the current notion of futures and promises. As we will see in further sections, this idea of having a *"placeholder for a value that might not be available"* has changed meanings over time. +## Motivation and Uses -Thunks can be thought of as a primitive notion of a Future or Promise. According to its inventor P. Z. Ingerman, thunks are "A piece of coding which provides an address". {% cite 23 --file futures %} They were designed as a way of binding actual parameters to their formal definitions in Algol-60 procedure calls. If a procedure is called with an expression in the place of a formal parameter, the compiler generates a thunk which computes the expression and leaves the address of the result in some standard location. +The rise of promises and futures as a topic of relevance has for the most part occurred alongside of the rise of parallel and concurrent programming and distributed systems. This follows somewhat naturally, since, as an abstraction which encodes time, futures/promises introduce a nice way to reason about state changes when latency becomes an issue; a common concern faced by programmers when a node must communicate with another node in a distributed system. +However promises and futures are considered useful in a number of contexts as well, both distributed and not. Some such contexts include: -The first mention of Futures was by Baker and Hewitt in a paper on Incremental Garbage Collection of Processes. They coined the term - call-by-futures to describe a calling convention in which each formal parameter to a method is bound to a process which evaluates the expression in the parameter in parallel with other parameters. Before this paper, Algol 68 also presented a way to make this kind of concurrent parameter evaluation possible, using the collateral clauses and parallel clauses for parameter binding. +- **Request-Response Patterns**, such as web service calls over HTTP. A future may be used to represent the value of the response of the HTTP request. +- **Input/Output**, such as UI dialogs requiring user input, or operations such as reading large files from disk. A future may be used to represent the IO call and the resulting value of the IO (e.g., terminal input, array of bytes of a file that was read). +- **Long-Running Computations**. Imagine you would like the process which initiated a long-running computation, such as a complex numerical algorithm, not to wait on the completion of that long-running computation and to instead move on to process some other task. A future may be used to represent this long-running computation and the value of its result. +- **Database Queries**. Like long-running computations, database queries can be time-consuming. Thus, like above, it may be desirable to offload the work of doing the query to another process and move on to processing the next task. A future may be used to represent the query and resulting value of the query. +- **RPC (Remote Procedure Call)**. Network latency is typically an issue when making an RPC call to a server. Like above, it may be desirable to not have to wait on the result of the RPC invocation by instead offloading it to another process. A future may be used to represent the RPC call and its result; when the server responds with a result, the future is completed and its value is the server's response. +- **Reading Data from a Socket** can be time-consuming particularly due to network latency. It may thus be desirable to not to have to wait on incoming data, and instead to offload it to another process. A future may be used to represent the reading operation and the resulting value of what it reads when the future is completed. +- **Timeouts**, such as managing timeouts in a web service. A future representing a timeout could simply return no result or some kind of empty result like the `Unit` type in typed programming languages. -In their paper, Baker and Hewitt introduced a notion of Futures as a 3-tuple representing an expression E consisting of (1) A process which evaluates E, (2) A memory location where the result of E needs to be stored, (3) A list of processes which are waiting on E. But, the major focus of their work was not on role of futures and the role they play in Asynchronous distributed computing, and focused on garbage collecting the processes which evaluate expressions not needed by the function. +Many real world services and systems today make heavy use of futures/promises in popular contexts such as these, thanks to the notion of a future or a promise having been introduced in popular languages and frameworks such as JavaScript, NodeJS, Scala, Java, C++, amongst many others. As we will see in further sections, this proliferation of futures/promises has resulted in futures/promises changing meanings and names over time and across languages. -The Multilisp language, presented by Halestead in 1985 built upon this call-by-future with a Future annotation. Binding a variable to a future expression creates a process which evaluates that expression and binds x to a token which represents its (eventual) result. It allowed an operation to move past the actual computation without waiting for it to complete. If the value is never used, the current computation will not pause. MultiLisp also had a lazy future construct, called Delay, which only gets evaluated when the value is first required. +## Diverging Terminology - This design of futures influenced the paper of design of Promises in Argus by Liskov and Shrira in 1988. Both futures in MultiLisp and Promises in Argus provisioned for the result of a call to be picked up later. Building upon the initial design of Future in MultiLisp, they extended the original idea by introducing strongly typed Promises and integration with call streams. Call streams are a language-independent communication mechanism connecting a sender and a receiver in a distributed programming environment. It is used to make calls from sender to receiver like normal RPC. In addition, sender could also make stream-calls where it chooses to not wait for the reply and can make further calls. Stream calls seem like a good use-case for a placeholder to access the result of a call in the future : Promises. Call streams also had provisions for handling network failures. This made it easier to handle exception propagation from callee to the caller and also to handle the typical problems in a multi-computer system. This paper also talked about stream composition. The call-streams could be arranged in pipelines where output of one stream could be used as input on next stream. This notion is not much different to what is known as promise pipelining today, which will be introduced in more details later. +_Future_, _Promise_, _Delay_ or _Deferred_ generally refer to roughly the same synchronization mechanism where an object acts as a proxy for as-of-yet unknown result. When the result is available, some other code then gets executed. Over the years, these terms have come to refer to slightly different semantic meanings between languages and ecosystems. +Sometimes, a language may have _one_ construct named future, promise, delay, deferred, etc. -E is an object-oriented programming language for secure distributed computing, created by Mark S. Miller, Dan Bornstein, and others at Electric Communities in 1997. One of the major contribution of E was the first non-blocking implementation of Promises. It traces its routes to Joule which was a dataflow programming language. E had an eventually operator, * <- * . This created what is called an eventual send in E : the program doesn't wait for the operation to complete and moves to next sequential statement. Eventual-sends queue a pending delivery and complete immediately, returning a promise. A pending delivery includes a resolver for the promise. Further messages can also be eventually send to a promise before it is resolved. These messages are queued up and forwarded once the promise is resolved. The notion of promise pipelining in E is also inherited from Joule. +However, in other cases, a language may have _two_ constructs, typically referred to as futures and promises. Languages like Scala, Java, and Dart fall into this category. In this case, +- A `Future` is a read-only reference to a yet-to-be-computed value. +- A `Promise` (or a `CompletableFuture`/`Completer`/etc) is a single-assignment variable which the `Future` refers to. -Among the modern languages, Python was perhaps the first to come up with something on the lines of E’s promises with the Twisted library. Coming out in 2002, it had a concept of Deferred objects, which were used to receive the result of an operation not yet completed. They were just like normal objects and could be passed along, but they didn’t have a value. They supported a callback which would get called once the result of the operation was complete. +In other words, a future is a read-only window to a value written into a promise. You can get the `Future` associated with a `Promise` by calling the `future` method on it, but conversion in the other direction is not possible. Another way to look at it would be, if you _promise_ something to someone, you are responsible for keeping it, but if someone else makes a _promise_ to you, you expect them to honor it in the _future_. +In Scala, they are defined as follows: -Promises and javascript have an interesting history. In 2007 inspired by Python’s twisted, dojo came up with it’s own implementation of of dojo.Deferred. This inspired Kris Zyp to then come up with the CommonJS Promises/A spec in 2009. Ryan Dahl introduced the world to NodeJS in the same year. In it’s early versions, Node used promises for the non-blocking API. When NodeJS moved away from promises to its now familiar error-first callback API (the first argument for the callback should be an error object), it left a void for a promises API. Q.js was an implementation of Promises/A spec by Kris Kowal around this time. FuturesJS library by AJ ONeal was another library which aimed to solve flow-control problems without using Promises in the strictest of senses. In 2011, JQuery v1.5 first introduced Promises to its wider and ever-growing audience. The API for JQuery was subtly different than the Promises/A spec. With the rise of HTML5 and different APIs, there came a problem of different and messy interfaces which added to the already infamous callback hell. A+ promises aimed to solve this problem. From this point on, leading from widespread adoption of A+ spec, promises was finally made a part of ECMAScript® 2015 Language Specification. Still, a lack of backward compatibility and additional features provided means that libraries like BlueBird and Q.js still have a place in the javascript ecosystem. +<blockquote> + <p>A future is a placeholder object for a result that does not yet exist. + A promise is a writable, single-assignment container, which completes a future. Promises can complete the future with a result to indicate success, or with an exception to indicate failure. + </p> + <footer>{% cite SIP14 --file futures%}</footer> +</blockquote> +An important difference between Scala and Java (6) futures is that Scala futures are asynchronous in nature. Java's future, at least till Java 6, were blocking. Java 7 introduced asynchronous futures to great fanfare. + +In Java 8, the `Future<T>` interface has methods to check if the computation is complete, to wait for its completion, and to retrieve the result of the computation when it is complete. `CompletableFutures` can be thought of as something of a promise, since their value can be explicitly set. However, `CompletableFuture` also implements the `Future` interface allowing it to be used as a `Future` as well. Promises can be thought of as a future with a public set method which the caller (or anybody else) can use to set the value of the future. + +In the JavaScript world, JQuery introduces a notion of `Deferred` objects which are used to represent a unit of work which is not yet finished. The `Deferred` object contains a promise object which represents the result of that unit of work. Promises are values returned by a function. The deferred object can also be canceled by its caller. + +Like Scala and Java, C# also makes the distinction between the future and promise constructs described above. In C#, futures are called `Task<T>`s, and promises are called `TaskCompletionSource<T>`. The result of the future is available in the read-only property `Task<T>.Result` which returns `T`, and `TaskCompletionSource<T>.Task<TResult>` has methods to complete the `Task` object with a result of type `T` or with an exception or cancellation. Important to note; `Task`s are asynchronous in C#. + +And confusingly, the JavaScript community has standardized on a single construct known as a `Promise` which can be used like other languages' notions of futures. The Promises specification {% cite PromisesAPlus --file futures %} defines only a single interface and leaves the details of completing (or _fulfilling_) the promise to the implementer of the spec. Promises in JavaScript are also asynchronous and able to be pipelined. JavaScript promises are enabled by default in browsers that support ECMAScript 6 (EC6), or are available in a number of libraries such as [Bluebird](http://bluebirdjs.com/docs/getting-started.html) and [Q](https://github.com/kriskowal/q). + +As we can see, concepts, semantics, and terminology seem to be a bit mixed up between languages and library implementations of futures/promises. These differences in terminology and semantics arise from the long history and independent language communities that have proliferated the use of futures/promises. + + +## Brief History + +Here's a brief glimpse at a timeline spanning the history of futures and promises as we know them today: + + +<figure style="margin-left: 0px; width: 110%;"> + <img src="./images/1.png" alt="timeline" /> +</figure> -# Different Definitions +The first concept which eventually led to futures/promises appeared in 1961, with so-called _thunks_. Thunks can be thought of as a primitive, sequential notion of a future or promise. According to its inventor P. Z. Ingerman, thunks are: +<blockquote> + <p>A piece of coding which provides an address</p> + <footer>{% cite Thunks --file futures %}</footer> +</blockquote> -Future, promise, Delay or Deferred generally refer to same synchronisation mechanism where an object acts as a proxy for a yet unknown result. When the result is discovered, promises hold some code which then gets executed. +Thunks were designed as a way of binding actual parameters to their formal definitions in Algol-60 procedure calls. If a procedure is called with an expression in the place of a formal parameter, the compiler generates a thunk which computes the expression and leaves the address of the result in some standard location. Think of a thunk as a continuation or a function that was intended to be evaluated in a single-threaded environment. -In some languages however, there is a subtle difference between what is a Future and a Promise. -“A ‘Future’ is a read-only reference to a yet-to-be-computed value”. -“A ‘Promise’ is a pretty much the same except that you can write to it as well.” +The first mention of Futures was by Baker and Hewitt in a paper on Incremental Garbage Collection of Processes {% cite Hewitt77 --file futures %}. They coined the term, _call-by-futures_, to describe a calling convention in which each formal parameter to a method is bound to a process which evaluates the expression in the parameter in parallel with other parameters. Before this paper, Algol 68 **{% cite missingref --file futures%}** also presented a way to make this kind of concurrent parameter evaluation possible, using the collateral clauses and parallel clauses for parameter binding. +In their paper, Baker and Hewitt introduced a notion of Futures as a 3-tuple representing an expression `E` consisting of: -In other words, a future is a read-only window to a value written into a promise. You can get the Future associated with a Promise by calling the future method on it, but conversion in the other direction is not possible. Another way to look at it would be, if you Promise something, you are responsible for keeping it, but if someone else makes a Promise to you, you expect them to honor it in Future. +1. A process which evaluates `E`, +2. A memory location where the result of `E` needs to be stored, +3. A list of processes which are waiting on `E`. -More technically, in Scala, “SIP-14 – Futures and Promises” defines them as follows: -A future is a placeholder object for a result that does not yet exist. -A promise is a writable, single-assignment container, which completes a future. Promises can complete the future with a result to indicate success, or with an exception to indicate failure. +Though importantly, the focus of their work was not on role of futures and the role they play in asynchronous distributed computing. Instead, it was focused on garbage collecting the processes which evaluate expressions that were not needed by the function. -An important difference between Scala and Java (6) futures is that Scala futures were asynchronous in nature. Java's future, at least till Java 6, were blocking. Java 7 introduced the Futures as the asynchronous construct which are more familiar in the distributed computing world. +The Multilisp language {% cite Multilisp --file futures %}, presented by Halestead in 1985 built upon this call-by-future with a future annotation. In Multilisp, binding a variable to a future expression would in turn create a new process which evaluates that expression and binds it to the variable reference which represents its (eventual) result. That is, Multilisp introduced a way to compute arbitrary expressions concurrently in a new process. This made it possible to move past the actual computation and continue processing without waiting for the future to complete. If the result value of the future is never used, the initiating process will not block, thus eliminating a potential source of deadlock. MultiLisp also included a lazy future variant, called _delay_, which would only be evaluated the first time the value is required elsewhere in the program. +This design of futures in Multilisp in turn influenced a construct dubbed _promises_ in the Argus programming language {% cite Promises88 Argus88 --file futures %} by Liskov and Shrira in 1988. Like futures in MultiLisp, promises in Argus intended to be a placeholder for the result of a value that will be available in the future. Unlike Multilisp which was focused on single-machine concurrency, however, Argus was designed to facilitate distributed programming, and in particular focused on promises as a way to integrate _asynchronous_ RPC into the Argus programming language. Importantly, promises were extended beyond futures in Multilisp through the introduction of types to promises. Therefore, in Argus, when a call to `promise` is made, a promise is created which immediately returns, and a type-safe asynchronous RPC call is made in a new process. When the RPC completes, the returned value can be claimed by the caller. -In Java 8, the Future<T> interface has methods to check if the computation is complete, to wait for its completion, and to retrieve the result of the computation when it is complete. CompletableFutures can be thought of as Promises as their value can be set. But it also implements the Future interface and therefore it can be used as a Future too. Promises can be thought of as a future with a public set method which the caller (or anybody else) can use to set the value of the future. +Argus also introduced call streams, which can be thought of as a way to enforce an ordering of concurrently executing calls. A sender and a receiver are connected by a stream, over which it is possible make normal (synchronous) RPC calls, or _stream calls_, in which the sender may make more calls before receiving the reply. The underlying runtime however ensures that, despite the non-blocking stream calls fired off, that all calls and subsequent replies happen in call order. That is, call-streams ensure exactly-once, ordered delivery. Argus also introduces constructs to _compose_ call-streams, in order to build up pipelines of computation, or directed acyclic graphs (DAGs) of computation. These semantics are an early precursor to what we refer to today as _promise pipelining_. +E is an object-oriented programming language for secure distributed computing {% cite ELang --file futures %}, created by Mark S. Miller, Dan Bornstein, and others at Electric Communities in 1997. A major contribution of E is its interpretation and implementation of promises. It traces its routes to Joule {% cite Joule --file futures %}, a dataflow programming language predecessor to E. Importantly, E introduced an _eventually_ operator, `* <- *` which enabled what is called an eventual send in E; that is, the program doesn't wait for the operation to complete and moves to next sequential statement. This is in contrast to the expected semantics of an _immediate call_ which looks like a normal method invocation in E. Eventual sends queue a pending delivery and complete immediately, returning a promise. A pending delivery includes a resolver for the promise. Subsequent messages can also be eventually sent to a promise before it is resolved. In this case, these messages are queued up and forwarded once the promise is resolved. That is, once we have a promise, we are able to chain make several pipelined eventual sends as if the initial promise was already resolved. This notion of _promise pipelining_ {% cite PromisePipe07 --file futures %} has been adopted by a majority of contemporary futures/promises interpretations. -In Javascript world, Jquery introduces a notion of Deferred objects which are used to represent a unit of work which is not yet finished. Deferred object contains a promise object which represent the result of that unit of work. Promises are values returned by a function, while the deferred object can be canceled by its caller. +Futures and promises remained primarily an academic fascination until the early 2000s, upon the rise of web application development, networked system development, and an increased need for responsive user interfaces. +Among the mainstream programming languages, Python was perhaps the first, in 2002, to get a library which introduced a construct along the same lines as E’s promises in the Twisted library {% cite Twisted --file futures %}. Twisted introduced the notion of _Deferred_ objects, are used to receive the result of an operation not yet completed. In Twisted, deferred objects are just like normal first-class objects; they can be passed along anywhere a normal object can, the only difference is that deferred objects don't have values. Deferred objects support callbacks, which are called once the result of the operation is complete. -C# also makes the distinction between futures and promises. In C#, futures are implemented as Task<T> and in fact in earlier versions of the Task Parallel Library futures were implemented with a class Future<T> which later became Task<T>. The result of the future is available in the readonly property Task<T>.Result which returns T. Tasks are asynchronous in C#. +Perhaps most famous in recent memory is that of promises in JavaScript. In 2007, inspired by Python’s Twisted library, the authors of the Dojo Toolkit came up a JavaScript implementation of Twisted's deferred objects, known as `dojo.Deferred`. This in turn inspired Kris Zyp to propose the CommonJS Promises/A spec in 2009 {% cite PromisesA --file futures %}. The same year, Ryan Dahl introduced NodeJS. In it’s early versions, Node used promises in its non-blocking API. However, when NodeJS moved away from promises to its now familiar error-first callback API (the first argument for the callback should be an error object), it left a void to fill for a promises API. [Q.js](https://github.com/kriskowal/q) is an implementation of Promises/A spec by Kris Kowal around this time {% cite Qjs --file futures %}. The [FuturesJS](https://github.com/FuturesJS/FuturesJS) library by AJ O'Neal was another library which aimed to solve flow-control problems without using Promises in the strictest of senses. In 2011, JQuery v1.5 introduced Promises to its wider and ever-growing audience. However, JQuery's promises API was subtly different than the Promises/A spec {% cite JQueryPromises --file futures %}. With the rise of HTML5 and different APIs, there came a problem of different and messy interfaces which added to the already infamous callback hell. The Promises/A+ spec {% cite PromisesAPlus --file futures %} aimed to solve this problem. Following the broad community acceptance of the Promises/A+ spec, promises were finally made a part of the ECMAScript® 2015 Language Specification {% cite Ecmascript15 --file futures %}. However, a lack of backward compatibility and additional features missing in the Promises/A+ spec means that libraries like [BlueBird](http://bluebirdjs.com/docs/getting-started.html) and [Q.js](https://github.com/kriskowal/q) still have a place in the JavaScript ecosystem. -# Semantics of Execution +## Semantics of Execution Over the years promises and futures have been implemented in different programming languages. Different languages chose to implement futures/promises in a different way. In this section, we try to introduce some different ways in which futures and promises actually get executed and resolved underneath their APIs. -## Thread Pools +### Thread Pools Thread pools are a group of ready, idle threads which can be given work. They help with the overhead of worker creation, which can add up in a long running process. The actual implementation may vary everywhere, but what differentiates thread pools is the number of threads it uses. It can either be fixed, or dynamic. Advantage of having a fixed thread pool is that it degrades gracefully : the amount of load a system can handle is fixed, and using fixed thread pool, we can effectively limit the amount of load it is put under. Granularity of a thread pool is the number of threads it instantiates. @@ -129,7 +199,7 @@ As we mentioned, Futures require an ExecutionContext, which is an implicit param ForkJoinPool is ideal for many small computations that spawn off and then come back together. Scala’s ForkJoinPool requires the tasks submitted to it to be a ForkJoinTask. The tasks submitted to the global ExecutionContext is quietly wrapped inside a ForkJoinTask and then executed. ForkJoinPool also supports a possibly blocking task, using ManagedBlock method which creates a spare thread if required to ensure that there is sufficient parallelism if the current thread is blocked. To summarize, ForkJoinPool is an really good general purpose ExecutionContext, which works really well in most of the scenarios. -## Event Loops +### Event Loops Modern systems typically rely on many other systems to provide the functionality they do. There’s a file system underneath, a database system, and other web services to rely on for the information. Interaction with these components typically involves a period where we’re doing nothing but waiting for the response back. This is single largest waste of computing resources. @@ -167,7 +237,7 @@ getData = function(param, callback){ }); } -getData(0, function(a){ +getData(0, function(a){ getData(a, function(b){ getData(b, function(c){ getData(c, function(d){ @@ -246,7 +316,7 @@ We haven’t talked about error handling, but it gets handled the same exact way Event loops have proven to be surprisingly performant. When network servers are designed around multithreading, as soon as you end up with a few hundred concurrent connections, the CPU spends so much of its time task switching that you start to lose overall performance. Switching from one thread to another has overhead which can add up significantly at scale. Apache used to choke even as low as a few hundred concurrent users when using a thread per connection while Node can scale up to a 100,000 concurrent connections based on event loops and asynchronous IO. -## Thread Model +### Thread Model Oz programming language introduced an idea of dataflow concurrency model. In Oz, whenever the program comes across an unbound variable, it waits for it to be resolved. This dataflow property of variables helps us write threads in Oz that communicate through streams in a producer-consumer pattern. The major benefit of dataflow based concurrency model is that it’s deterministic - same operation called with same parameters always produces the same result. It makes it a lot easier to reason about concurrent programs, if the code is side-effect free. @@ -260,7 +330,7 @@ Any expression in Alice can be evaluated in it's own thread using spawn keyword. Alice also allows for lazy evaluation of expressions. Expressions preceded with the lazy keyword are evaluated to a lazy future. The lazy future is evaluated when it is needed. If the computation associated with a concurrent or lazy future ends with an exception, it results in a failed future. Requesting a failed future does not block, it simply raises the exception that was the cause of the failure. -# Implicit vs. Explicit Promises +## Implicit vs. Explicit Promises We define Implicit promises as ones where we don’t have to manually trigger the computation vs Explicit promises where we have to trigger the resolution of future manually, either by calling a start function or by requiring the value. This distinction can be understood in terms of what triggers the calculation : With Implicit promises, the creation of a promise also triggers the computation, while with Explicit futures, one needs to triggers the resolution of a promise. This trigger can in turn be explicit, like calling a start method, or implicit, like lazy evaluation where the first use of a promise’s value triggers its evaluation. @@ -311,7 +381,7 @@ p.complete(new Foo) Here, we create a Promise, and complete it later. In between we stack up a set of computations which get executed once the promise is completed. -# Promise Pipelining +## Promise Pipelining One of the criticism of traditional RPC systems would be that they’re blocking. Imagine a scenario where you need to call an API ‘a’ and another API ‘b’, then aggregate the results of both the calls and use that result as a parameter to another API ‘c’. Now, the logical way to go about doing this would be to call A and B in parallel, then once both finish, aggregate the result and call C. Unfortunately, in a blocking system, the way to go about is call a, wait for it to finish, call b, wait, then aggregate and call c. This seems like a waste of time, but in absence of asynchronicity, it is impossible. Even with asynchronicity, it gets a little difficult to manage or scale up the system linearly. Fortunately, we have promises. @@ -368,7 +438,7 @@ Promise.race([p1, p2]).then(function(value) { In Scala, futures have a onSuccess method which acts as a callback to when the future is complete. This callback itself can be used to sequentially chain futures together. But this results in bulkier code. Fortunately, Scala api comes with combinators which allow for easier combination of results from futures. Examples of combinators are map, flatmap, filter, withFilter. -# Handling Errors +## Handling Errors If world would have run without errors we would rejoice in unison, but it is not the case in programming world as well. When you run a program you either receive an expected output or an error. Error can be defined as wrong output or an exception. In a synchronous programming model, the most logical way of handling errors is a try...catch block. @@ -548,18 +618,18 @@ function check(data) { ``` -# Futures and Promises in Action +## Futures and Promises in Action -## Twitter Finagle +### Twitter Finagle Finagle is a protocol-agnostic, asynchronous RPC system for the JVM that makes it easy to build robust clients and servers in Java, Scala, or any JVM-hosted language. It uses Futures to encapsulate concurrent tasks. Finagle introduces two other abstractions built on top of Futures to reason about distributed software : -- ** Services ** are asynchronous functions which represent system boundaries. +- **Services** are asynchronous functions which represent system boundaries. -- ** Filters ** are application-independent blocks of logic like handling timeouts and authentication. +- **Filters** are application-independent blocks of logic like handling timeouts and authentication. In Finagle, operations describe what needs to be done, while the actual execution is left to be handled by the runtime. The runtime comes with a robust implementation of connection pooling, failure detection and recovery and load balancers. @@ -584,7 +654,7 @@ def timeoutFilter(d: Duration) = ``` -## Correctables +### Correctables Correctables were introduced by Rachid Guerraoui, Matej Pavlovic, and Dragos-Adrian Seredinschi at OSDI ‘16, in a paper titled Incremental Consistency Guarantees for Replicated Objects. As the title suggests, Correctables aim to solve the problems with consistency in replicated objects. They provide incremental consistency guarantees by capturing successive changes to the value of a replicated object. Applications can opt to receive a fast but possibly inconsistent result if eventual consistency is acceptable, or to wait for a strongly consistent result. Correctables API draws inspiration from, and builds on the API of Promises. Promises have a two state model to represent an asynchronous task, it starts in blocked state and proceeds to a ready state when the value is available. This cannot represent the incremental nature of correctables. Instead, Correctables have a updating state when it starts. From there on, it remains in updating state during intermediate updates, and when the final result is available, it transitions to final state. If an error occurs in between, it moves into an error state. Each state change triggers a callback. <figure> @@ -592,14 +662,14 @@ Correctables were introduced by Rachid Guerraoui, Matej Pavlovic, and Dragos-Adr </figure> -## Folly Futures +### Folly Futures Folly is a library by Facebook for asynchronous C++ inspired by the implementation of Futures by Twitter for Scala. It builds upon the Futures in the C++11 Standard. Like Scala’s futures, they also allow for implementing a custom executor which provides different ways of running a Future (thread pool, event loop etc). -## NodeJS Fiber +### NodeJS Fiber Fibers provide coroutine support for v8 and node. Applications can use Fibers to allow users to write code without using a ton of callbacks, without sacrificing the performance benefits of asynchronous IO. Think of fibers as light-weight threads for NodeJs where the scheduling is in the hands of the programmer. The node-fibers library doesn’t recommend using raw API and code together without any abstractions, and provides a Futures implementation which is ‘fiber-aware’. -# References +## References {% bibliography --file futures %} |