-
Notifications
You must be signed in to change notification settings - Fork 3
/
index.html
321 lines (270 loc) · 13.2 KB
/
index.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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8" />
<title>Coroutine Event Loops in Javascript</title>
<link rel="stylesheet" type="text/css" href="normalize.css" />
<link rel="stylesheet" type="text/css" href="prettify.css" />
<script src="prettify.js"></script>
<link rel="stylesheet" type="text/css" href="index.css" />
<script src="jquery-1.8.2.min.js"></script>
<script src="callback-dragging.js"></script>
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-26533561-1']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>
</head>
<body onload="prettyPrint(); initDragging($('#box1'), false); initDragging($('#box2'), true);">
<h1>Coroutine Event Loops in Javascript</h1>
<p>ECMAScript 6 introduces a <code>yield</code> keyword for implementing generators and coroutines.<p>
<p>An intriguing use of coroutines is to implement event loops as an alternative to callback functions.
This is particularly relevant to Javascript, where the use of callbacks is pervasive.</p>
<p><big><strong>If you're in a hurry:</strong></big>
try the <a href="#demo">interactive demo</a> contrasting coroutines and callbacks.</p>
<h2 id="the-basics">The Basics</h2>
<p>A coroutine is a function, marked by the <code>function*</code> syntax,
which can suspend itself anywhere in its execution using the <code>yield</code> keyword.</p>
<p>It can then be resumed by <em>sending</em> it a value. The sent value will appear as the return value of <code>yield</code> and execution will resume until the next <code>yield</code>.</p>
<p>For example we can create a simple coroutine which will yield twice and print out the values that are sent to it after each yield:</p>
<pre class="prettyprint">
function* test() {
console.log('Hello!');
var x = yield;
console.log('First I got: ' + x);
var y = yield;
console.log('Then I got: ' + y);
}
</pre>
<p>To initiate an instance of a coroutine you just call the function, which returns a coroutine object:</p>
<pre class="prettyprint">var tester = test();</pre>
<p>So far none of the function will have executed, so we must execute the function until it hits a <code>yield</code>, by calling:</p>
<pre class="prettyprint">tester.next(); // prints 'Hello!'</pre>
<p>Now <code>tester</code> is paused at the first <code>yield</code>, and we can resume the coroutine by sending a value to the <code>yield</code> where it is paused:</p>
<pre class="prettyprint">tester.next('a cat'); // prints 'First I got: a cat'</pre>
<p>Now <code>tester</code> is paused at the second <code>yield</code>, and we can send another value:</p>
<pre class="prettyprint">tester.next('a dog'); // prints 'Then I got: a dog'</pre>
<p>That's about all there is to coroutines—they are functions which can suspend themselves using the <code>yield</code> keyword,
and you can communicate with them by sending values, which will be returned as the value of <code>yield</code> and resume execution.</p>
<h2 id="the-convenient-coroutine-wrapper">The Convenient <code>coroutine</code> Wrapper</h2>
<p>Every time you use a coroutine you always do three things:</p>
<ol>
<li>Call the function and store the resulting coroutine object.</li>
<li>Call <code>next()</code> on the coroutine object, to execute until the first <code>yield</code>.</li>
<li>After that all you can do is call <code>next(...)</code> to run the coroutine and send it values.</li>
</ol>
<p>We can put all of this functionality into a wrapper function:</p>
<pre class="prettyprint">
function coroutine(f) {
var o = f(); // instantiate the coroutine
o.next(); // execute until the first yield
return function(x) {
o.next(x);
}
}
</pre>
<p>This sets up the coroutine and returns a function which we can call directly instead of calling <code>next</code> on the coroutine object.</p>
<p>Using this wrapper, our earlier example becomes:</p>
<pre class="prettyprint">
var test = coroutine(function*() {
console.log('Hello!');
var x = yield;
console.log('First I got: ' + x);
var y = yield;
console.log('Then I got: ' + y);
});
// prints 'Hello!'
test('a dog'); // prints 'First I got: a dog'
test('a cat'); // prints 'Then I got: a cat'
</pre>
<h2 id="a-coroutine-loop">A Coroutine Loop</h2>
<p>Our first example coroutine yields twice and then ends. Let's make a never-ending coroutine instead.</p>
<p>Here's a coroutine that never ends, and each time you resume it, it alternates between ticking and tocking:</p>
<pre class="prettyprint">
var clock = coroutine(function*() {
while (true) {
yield;
console.log('Tick!');
yield;
console.log('Tock!');
}
});
clock(); // prints 'Tick!'
clock(); // prints 'Tock!'
clock(); // prints 'Tick!'
</pre>
<p><em>Note that in Javascript, calling <code>clock()</code> with no argument is the same as calling <code>clock(undefined)</code>,
which in this case is fine since this coroutine doesn't even look at the values being sent to it.</em></p>
<p>Now let's make the clock tick/tock once every second. It's very easy:</p>
<pre class="prettyprint">setInterval(clock, 1000);</pre>
<p>This resumes the coroutine once every 1000ms, and it will tick and tock for eternity.</p>
<h2 id="a-coroutine-event-loop">A Coroutine Event Loop</h2>
<p>In the same way that we used the <code>clock</code> function above as a timer callback,
we can use coroutines as callbacks for events,
and the event object will be sent to the running coroutine.</p>
<p>For example suppose we want to implement this little demo. Try dragging the box around:</p>
<div class="space">
<div id="box1" class="box"></div>
</div>
<p class="clear">This program needs to repeat the following steps:</p>
<ol>
<li>wait for a <code>mousedown</code> on the box</li>
<li>process any <code>mousemove</code> events, and actually move the box</li>
<li>until we see a <code>mouseup</code> event</li>
</ol>
<p>We can implement this as a coroutine that receives events from <code>yield</code>:</p>
<pre class="prettyprint">
var loop = coroutine(function*() {
while (true) { // wait for a mousedown
var event = yield;
if (event.type == 'mousedown') {
while (true) { // process mousemoves until a mouseup
var event = yield;
if (event.type == 'mousemove') move(event);
if (event.type == 'mouseup') break;
}
}
}
});
</pre>
<p><em>Note that the <code>move</code> function is defined elsewhere, and just moves the div.</em></p>
<p>We can be slightly more concise by noticing that event objects are always 'truthy',
so we can change the while loops to:</p>
<pre class="prettyprint">while (event = yield) { ... }</pre>
<p>This form of infinite loop is the heart of a coroutine event loop. We end up with:</p>
<pre class="prettyprint">
var loop = coroutine(function*() {
var event;
while (event = yield) { // wait for a mousedown
if (event.type == 'mousedown') {
while (event = yield) { // process mousemoves until a mouseup
if (event.type == 'mousemove') move(event);
if (event.type == 'mouseup') break;
}
}
}
});
</pre>
<h2 id="coroutines-as-state-machines">Coroutines as State Machines</h2>
<p>Let's return to the <code>clock</code> example earlier.
We can implement it using coroutines as above,
or we can of course implement it without coroutines, using a function and a variable:</p>
<div class="figure left">
<pre class="prettyprint">
var clock = coroutine(function*() {
while (true) {
yield;
console.log('Tick!');
yield;
console.log('Tock!');
}
});
</pre>
<p>clock as a coroutine</p>
</div>
<div class="figure left">
<pre class="prettyprint">
var ticking = true;
var clock = function() {
if (ticking)
console.log('Tick!');
else
console.log('Tock!');
ticking = !ticking;
}
</pre>
<p>clock as a function and a variable</p>
</div>
<div class="clear"></div>
<div class="figure right">
<img src="clock.svg">
<p>the clock state machine</p>
</div>
<p>Both implementations behave the same, and implement the same simple 2-state machine, as pictured.</p>
<p>The interesting difference between the two implementations
is that the coroutine version involves no <code>ticking</code> variable,
and never explicitly stores any state.</p>
<p>Without using coroutines you <em>must</em> use a variable to store the state of whether the next call should tick or tock.</p>
<p>This variable can only be avoided because <strong>coroutines add an entirely new form of state</strong> to the language,
namely the state of <em>where</em> the coroutine is currently suspended.</p>
<p>One benefit of this 'implicit' coroutine state is that it is guaranteed to be consistent.
This differs from the variable state, which could easily become invalid if we do something like <code>ticking="maybe"</code>.</p>
<div class="clear figure right">
<img src="dragging.svg">
<p>the dragging state machine</p>
</div>
<p>As a slightly more complex example, we can also implement the 2-state machine from the dragging demo using standard callback functions.</p>
<p>Once again the coroutine implementation uses no explicit state, while the callback version must.</p>
<p>Also note that the single event loop is equivalent to three callback functions.</p>
<div class="clear"></div>
<p id="demo">Drag the box, and observe how the two different implementations behave:</p>
<div class="figure left">
<div class="space">
<div id="box2" class="box"></div>
</div>
</div></a>
<div class="clear figure left">
<pre class="prettyprint">
var loop = coroutine(function*() {
var e;
<span class="not-dragging mousemove-1 mousedown-1">while (e = <span class="not-dragging yield">yield</span>) {</span>
<span class="not-dragging mousedown-2">if (e.type == 'mousedown') {</span>
<span class="dragging mousemove-1 mouseup-1">while (e = <span class="dragging yield">yield</span>) {</span>
<span class="dragging mousemove-2">if (e.type == 'mousemove')</span>
<span class="dragging mousemove-3">move(e);</span>
<span class="dragging mouseup-2">if (e.type == 'mouseup')</span>
<span class="dragging mouseup-3">break;</span>
}
}
<span class="not-dragging mousemove-2 mousemove-3">// ignore mousemoves</span>
}
});
$('#box').mousedown(loop);
$(window).mousemove(loop)
.mouseup(loop);
</pre>
<p>draggable box as a coroutine event loop</p>
</div>
<div class="figure left">
<pre class="prettyprint">
var dragging = <span id="dragging" class="dragging not-dragging yield">false</span>;
<span class="not-dragging mousedown-1">function mousedown(e) {</span>
<span class="not-dragging mousedown-2">dragging = true;</span>
}
<span class="dragging not-dragging mousemove-1">function mousemove(e) {</span>
<span class="dragging mousemove-2">if (dragging)</span>
<span class="dragging mousemove-3">move(e);</span>
<span class="not-dragging mousemove-2">else {</span>
<span class="not-dragging mousemove-3">// ignore mousemoves</span>
}
}
<span class="dragging mouseup-1 mouseup-2">function mouseup(e) {</span>
<span class="dragging mouseup-3">dragging = false;</span>
}
$('#box').mousedown(mousedown);
$(window).mousemove(mousemove)
.mouseup(mouseup);
</pre>
<p>draggable box as callbacks and a variable</p>
</div>
<p class="clear">The coroutine implementation above is just a simulation, so that it works in all browsers,
some of which still don't support ECMAScript 6.</p>
<p>But if you're using a recent version of Firefox or Chrome,
you can try the <a href="coroutine-dragging.html">real live coroutine implementation</a>!</p>
<p>These examples of coroutine event loops are no better than their standard callback function equivalents,
but complex state machines could be more elegantly implemented as coroutines,
perhaps for example something involving Ajax requests or something in node.js, where almost everything is a callback.</p>
<p>This writeup was inspired by the section "Coroutines and Event Dispatching" starting on slide 53
of David Beazley's mind-blowing presentation <em><a href="http://www.dabeaz.com/coroutines/Coroutines.pdf">A Curious Course on Coroutines and Concurrency</a></em>.</p>
<p>There was a <a href="http://news.ycombinator.com/item?id=4912413">good discussion</a> of this writeup on Hacker News.</p>
<div class="footer">
<p><a href="/">Harold Cooper</a>, December 2012</p>
<p>view <a href="https://github.com/hrldcpr/javascript-coroutines">the source</a> on github</p>
</div>
</body>
</html>