-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathpl.html
54 lines (54 loc) · 9.03 KB
/
pl.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
<h1 id="promises">Promises</h1>
<h2 id="relevant-reading">Relevant Reading</h2>
<ul>
<li><p><em>Promises: linguistic support for efficient asynchronous procedure calls in distributed systems</em>, Liskov and Shrira, PLDI 1988 <span class="citation">Liskov and Shrira (1988)</span>.</p></li>
<li><p><em>Multilisp: A language for concurrent symbolic computation</em>, Halstead, TOPLAS 1985 <span class="citation">Halstead Jr (1985)</span>.</p></li>
</ul>
<h2 id="commentary">Commentary</h2>
<p>Outside of early mentions from Friedman and Wise on a <em>cons</em> cell with placeholder values <span class="citation">Friedman and Wise (1978)</span> and Baker and Hewitt’s work on incremental garbage collection <span class="citation">Baker and Hewitt (1977)</span>, <em>futures</em> originally appeared as one of the two principal constructs for parallel operations in MultiLisp. MultiLisp attempted to solve a main challenge of designing a language for parallel computation: how can parallel computation be introduced into a language in a way that fits with the existing programming paradigm. This problem is motivated by the fact that computer programmers will need to introduce concurrency into applications because automated analysis may not be able to identify all of the points for parallelism. Halstead decides there is quite a natural fit with a Lisp/Scheme: expression evaluation can be done in parallel. MultiLisp introduces two main concepts: <em>pcall</em>, to evaluate the expressions being passed to a function in parallel and introduce concurrency into evaluation of arguments to a function, and <em>futures</em>, to introduce concurrency between the computation of a value and the use of that value. Halstead also notes that futures closely resemble the “eventual values” in Hibbard’s Algol 68, however were typed distinctly from the values they produced and later represented. <span class="citation">Halstead Jr (1985)</span></p>
<p>In 1988, Liskov and Shrira introduce the concept of a <em>promise</em>: an efficient way to perform asynchronous remote procedure calls in a type-safe way <span class="citation">Liskov and Shrira (1988)</span>. Simply put, a promise is a placeholder for a value that will be available in the future. When the initial call is made, a promise is created and the asynchronous call to compute the value of the promise runs in parallel with the rest of the program. When the call completes, the value can be “claimed“ by the caller.</p>
<p>An excerpt motivation from <em>Promises: linguistic support for efficient asynchronous procedure calls in distributed systems (Liskov and Shrira, PLDI 1988)</em>:</p>
<blockquote>
<p>“Remote procedure calls have come to be the preferred method of communication in a distributed system because programs that use procedures are easier to understand and reason about than those that explicitly send and receive messages. However, remote calls require the caller to wait for a reply before continuing, and therefore can lead to lower performance than explicit message exchange.”</p>
</blockquote>
<p>The general motivation behind the work by Liskov and Shrira can be thought as the following critiques of two models of distributed programming.</p>
<ul>
<li><p>The Remote Procedure Call (RPC) paradigm is preferable by programmers because it is a familiar programming model. However, because of the synchronous nature of RPC, this model does not scale in terms of performance.</p></li>
<li><p>The message passing paradigm is harder for programmers to reason about, but provides the benefit of decoupling of request and response, allowing for asynchronous programming and the subsequent performance benefits.</p></li>
</ul>
<p><em>Promises</em> attempts to bridge this gap by combining the remote procedure call style of building applications, with the asynchronous execution model seen in systems that primarily use message passing.</p>
<p>The first challenge in combining these two programming paradigms for distributed programming is that of order. Synchronous RPC imposes a total order across all of the calls in an application: one call will fully complete, from request to response, before moving to the next call, given a single thread of execution. If we move to an asynchronous model of RPC, we must have a way to block for a given value, or result, of an asynchronous RPC if required for further processing.</p>
<p>Promises does this by imagining the concept of a <em>call-stream</em>. A <em>call-stream</em> is nothing more than a stream of placeholder values for each asynchronous RPC issued by a client. Once a RPC is issued, the <em>promise</em> is considered <em>blocked</em> asynchronous execution is performed, and once the value has been computed, the <em>promise</em> is considered <em>ready</em> and the value can be <em>claimed</em> by the caller. If an attempt to <em>claim</em> the value is issued before the value is computed, execution blocks until the value is available. The stream of placeholder values serves as an implicit ordering of the requests that are issued; in the Argus system that served as the implementation platform for this work, multiple streams were used and related operations sequenced together in the same stream<a href="#fn1" class="footnoteRef" id="fnref1"><sup>1</sup></a>.</p>
<h2 id="impact-and-implementations">Impact and Implementations</h2>
<p>While promises originated as a technique for decoupling values from the computations that produced them, promises, as proposed by Liskov and Shrira mainly focused on reducing latency and improving performance of distributed computations. The majority of programming languages in use today by practitioners contain some notion of <em>futures</em> or <em>promises</em>. Below, we highlight a few examples.</p>
<p>The Oz <span class="citation">Henz, Smolka, and Würtz (1993)</span> language, designed for the education of programmers in several different programming paradigms, provides a functional programming model with single assignment variables, streams, and promises. Given every variable in Oz is a dataflow, and therefore every single value in the system is a promise. Both Distributed Oz <span class="citation">Haridi, Van Roy, and Smolka (1997)</span> and Derflow (an implementation of Oz in the Erlang programming language) <span class="citation">Bravo et al. (2014)</span> provide distributed versions of the Oz programming model. The Akka library for Scala also provides Oz-style dataflow concurrency with Futures.</p>
<p>More recently, promises have been repurposed by the JavaScript community to allow for asynchronous programs to be written in direct style instead of continuation-passing style. ECMAScript 6 contains a native Promise object, that can be used to perform asynchronous computation and register callback functions that will fire once the computation either succeeds or fails.</p>
<div id="refs" class="references">
<div id="ref-Baker:1977:IGC:872734.806932">
<p>Baker, Henry C., Jr., and Carl Hewitt. 1977. “The Incremental Garbage Collection of Processes.” <em>SIGPLAN Not.</em> 12 (8). New York, NY, USA: ACM: 55–59. doi:<a href="https://doi.org/10.1145/872734.806932">10.1145/872734.806932</a>.</p>
</div>
<div id="ref-Bravo:2014:DDD:2633448.2633451">
<p>Bravo, Manuel, Zhongmiao Li, Peter Van Roy, and Christopher Meiklejohn. 2014. “Derflow: Distributed Deterministic Dataflow Programming for Erlang.” In <em>Proceedings of the Thirteenth ACM SIGPLAN Workshop on Erlang</em>, 51–60. Erlang ’14. New York, NY, USA: ACM. doi:<a href="https://doi.org/10.1145/2633448.2633451">10.1145/2633448.2633451</a>.</p>
</div>
<div id="ref-1675100">
<p>Friedman, D. P., and D. S. Wise. 1978. “Aspects of Applicative Programming for Parallel Processing.” <em>IEEE Transactions on Computers</em> C-27 (4): 289–96. doi:<a href="https://doi.org/10.1109/TC.1978.1675100">10.1109/TC.1978.1675100</a>.</p>
</div>
<div id="ref-halstead1985multilisp">
<p>Halstead Jr, Robert H. 1985. “Multilisp: A Language for Concurrent Symbolic Computation.” <em>ACM Transactions on Programming Languages and Systems (TOPLAS)</em> 7 (4). ACM: 501–38.</p>
</div>
<div id="ref-haridi1997overview">
<p>Haridi, Seif, Peter Van Roy, and Gert Smolka. 1997. “An Overview of the Design of Distributed Oz.” In <em>Proceedings of the Second International Symposium on Parallel Symbolic Computation</em>, 176–87. ACM.</p>
</div>
<div id="ref-henz1993oz">
<p>Henz, Martin, Gert Smolka, and Jörg Würtz. 1993. “Oz-a Programming Language for Multi-Agent Systems.” In <em>IJCAI</em>, 404–9.</p>
</div>
<div id="ref-liskov1988promises">
<p>Liskov, Barbara, and Liuba Shrira. 1988. <em>Promises: Linguistic Support for Efficient Asynchronous Procedure Calls in Distributed Systems</em>. Vol. 23. 7. ACM.</p>
</div>
</div>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>Promises also provide a way for stream composition, where processes read values from one or more streams once they are <em>ready</em>, fulfilling placeholder <em>blocked</em> promises in other streams. One classic implementation of stream composition using <em>promises</em> is the Sieve of Eratosthenes.<a href="#fnref1">↩</a></p></li>
</ol>
</div>