-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathtutorial_introduction.html
441 lines (361 loc) · 17.1 KB
/
tutorial_introduction.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
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
<!DOCTYPE html>
<html>
<head><title>Introduction to StreamPy</title></head>
<body>
<center><h1>Introduction to StreamPy</h1></center>
<h1>Streams</h1>
<p> A stream is a sequence of values. The individual elements in a
stream are called values or messages. The only way in which a stream
can be modified is that values can be appended to the end of a
stream. A value in a stream cannot be modified, and values within a
stream cannot be reordered. </p>
<p>An example of a stream is a sequence of measurements made by a
sensor; as time progresses the sensor may make additional measurements
and send more values containing the newly measured values. The sensor
cannot retract or modify values that it has sent. </p>
<p> The values in a stream are arbitrary objects; values in a Python
stream need not belong to a special class. Values in NumPy streams,
JSON streams, and Java streams do belong to specified types; we will
discuss typed streams later. </p>
<p> The value of a stream, at a point in time, is a Python list, a
NumPy array, or a JSON list (or a Java list for the Java
version). This list or array is extended when values are appended to
the stream. If at some point, the value of a stream is the list [3,
5], then from that point onwards, the value of that stream will be a
list that begins with [3, 5]. For example, at a later point in time
the stream can be [3, 5], or [3, 5, 2], or [3, 5, 2, 6], but not [3,
4] or [1, 5, 2]. </p>
<p> Values in a stream may get out of order due to congestion in
communication networks or other reasons. Once a value is in a stream,
however, the value and its position in the stream do not change. An
incorrect value, or a value that is out of order, is corrected by
sending later correction values along the stream. </p>
<p>For the time being, we restrict attention to Python streams. A
stream is an instance of the class <b>Stream</b>. Values are
appended to a stream in exactly the same way as values are appended to
a list, i.e., by using <i>append</i> to append a single value and
<i>extend</i> to extend the list by a list of values.<p>
<p>We will describe implementation of the
<a
href="https://github.com/StreamPy/StreamPy/blob/master/Stream.py">Stream
class</a> later. An understanding of the implementation is not
necessary to use streams.</p>
<h1>Sources of streams</h1>
A <b>source</b> is a function that appends values to a stream without
reading other streams. A source may obtain values to append to a
stream from a file, database, random number generator or sensor.
<p><b>Note about examples. Please look at, run, modify and then rerun
the example files</b>. In the examples, <code>np</code> refers to
<b>NumPy</b>. </p>
<h4>Example of a source: <i>source_stream.py</i></h4>
<p>
<i>source_stream.py</i> appends values to a stream where the
values are specified by a function and arguments passed to
<i>source_stream.py</i>. The example illustrates that the statements
for appending to a list and appending to a stream are identical. The
function appends a value to a stream or a list periodically where the
period is a function parameter. Appending values to a list forever
causes memory overflow eventually whereas appending values to a stream
forever does not result in memory overflow. Earlier values of a stream
that are no longer accessed are garbage collected, i.e., they are
stored in secondary storage or discarded so that the amount of main
memory occupied by a stream is bounded. Stream implementation is
discussed later.</p>
<p> See <i>TutorialExamplesSource.html</i> for examples of sources of
streams. </p>
<h1>Encapsulators: From data at rest to data in motion</h1>
<p> The phrase "data at rest" refers to data that doesn't change; for
example, data in a list or an array. Data in motion refers to streams
and other data structures that change with time. Data at rest is often
a snapshot of data in motion. Most open-source and proprietary
programs operate on data at rest. StreamPy has a library of
encapsulators, or "wrappers" that encapsulate programs that operate on
data at rest to obtain programs that operate on streams. We will
develop programs that operate on streams by wrapping programs that
operate on standard data structures such as lists and arrays.</p>
<h1>Agents</h1>
<p>An agent is a program that has input streams and zero or more
output streams. An agent waits for data to arrive on its input
streams, processes the incoming data, and puts values on its output
streams. The simplest way to create an agent is to wrap
(i.e. encapsulate) a program that operates on lists or arrays.</p>
<p>An agent may have state or it may be stateless. We begin with the
stateless case and the simplest wrapper - the element wrapper.</p>
<p>We will describe implementation of the
<a
href="https://github.com/StreamPy/StreamPy/blob/master/Agent.py">Agent
class</a> later. An understanding of the implementation is not
necessary to use streams.</p>
<h1>The element wrapper</h1>
<p>We begin by describing the required parameters of a wrapper
function and postpone discussion of optional parameters. The element
wrapper function has the form:
<center><code>
stream_agent(inputs, outputs, f_type='element',f)
</code></center>
where:
<ul>
<li><code>inputs</code> is either a stream or a list of streams.</li>
<li><code>outputs</code> is either <code>None</code> a stream or a list of
streams.</li>
<li><code>f_type</code> is the string 'element' to indicate that the
wrapper is an element wrapper. Different wrappers are specified by
different values of <code>f_type</code>.</li>
<li>For the element wrapper, <code>f</code> is a function that maps
elements of input streams to elements of output streams.</li>
</ul>
<h4>Inputs to function <code>f</code></h4>
<ul>
<li> If <code>inputs</code> is a single stream then the input to <code>f</code>
is a single element of <code>inputs</code>.</li>
<li> If <code>inputs</code> is a list of streams then the input to <code>f</code>
is a list with one element from each stream in <code>inputs</code>.</li>
</ul>
<h4>Outputs of function <code>f</code></h4>
<ul>
<li> If <code>outputs</code> is a single stream then <code>f</code> returns a
single element of <code>outputs</code>.</li>
<li> If <code>outputs</code> is a list of streams then <code>f</code> returns a
list with one element for each stream in <code>outputs</code>.</li> If
<code>outputs</code> is <code>None</code> then <code>f</code> returns <code>None</code>.
</ul>
<p>
Function <code>f</code> specifies the j-th outputs for each output stream as
a function of the j-th elements of all the input streams, for all
j. The operation of an agent is as follows. For step j of the agent,
where j = 0, 1, 2,.., the agent waits until it reads the j-th elements
of each of its input streams and then applies <code>f</code> to compute the
j-th output to each of its output streams.
</p>
<p>
On each step of the agent, the agent may place a single element, or no
element, or multiple elements on an output stream. So, the length of
an agent's output stream may be smaller than, equal to, or greater
than the lengths of its input stream. We begin with the case where the
agent places a single element on each output stream at each step.
</p>
See <i>TutorialExamplesElementWrapper.html</i> for a collection of examples
of the element wrapper.
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<h3>Examples of element wrappers</h3>
<h4>Example of <i>stream operator</i>: single input stream, single output
stream.</h4>
<p> <b>Problem</b>: <code>x</code> and <code>y</code> are streams. Write
an agent that sets the <code>j</code>-th element of <code>y</code> to the <i>sine</i> of the
<code>j</code>-th element of <code>x</code>, for all <code>j</code>.</p>
<p> <b>Solution</b> see <i>tutorial_sine.py</i>:
<center><code>
stream_agent(inputs=x, outputs=y, f_type='element', f=np.sin)
</code></center>
</p>
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<h4>Example of <i>merge</i>: multiple input streams, single output
stream.</h4>
<p> <b>Problem</b> <code>list_of_stream</code> is a list of streams, and <code>y</code>
is a stream. Write an agent that sets the <code>j</code>-th
element of <code>y</code> to the sum of the <code>j</code>-th element of all streams in
<code>list_of_stream</code>. </p>
<p><b>Solution</b> see <i>tutorial_merge.py</i>:
<p>
<center><code>
stream_agent(inputs=list_of_streams, outputs=y,f_type ='element', f=sum)
</code></center>
</p>
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<h4>Example of <i>split</i>: single input streams, multiple output
streams.</h4>
<p> <b>Problem</b> <code>squareroot_stream</code>,
<code>square_stream</code> and <code>input_stream</code> are
streams. You are given the function:</p>
<center><code>
def squareroot_and_square(v): return (math.sqrt(v), v*v)
</code></center>
(where <code>math</code> was imported earlier). Write an agent that sets the
<code>j</code>-th element of the stream <code>squareroot_stream</code> to
the square root of the <code>j</code>-th element of <code>input_stream</code> and sets the
<code>j</code>-th element of the stream <code>square_stream</code> to
the square of the <code>j</code>-th element of <code>input_stream</code> </p>
<p><b>Solution</b> see <i>tutorial_split.py</i>:
<p>
<pre>
<code>
stream_agent(inputs=x, outputs=[squareroot_stream, square_stream],
f_type='element', f=squareroot_and_square)
</code>
</pre>
</p>
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<h4>Example of <i>many to many</i>: multiple input streams, multiple output
streams.</h4>
<p> <b>Problem</b> <code>list_of_streams</code> is a list of streams, and
<code>max_stream</code> and <code>max_stream</code> are streams. You are
given the function:</p>
<center><code>
def max_and_min(lst): return (max(lst), min(lst))
</code></center>
<p>Write an
agent that sets the <code>j</code>-th element of
<code>max_stream</code> to the max of the <code>j</code>-th
element of each stream in <code>list_of_streams</code> and sets the
<code>j</code>-th element of <code>min_stream[1]</code> to the min of
the <code>j</code>-th element of each stream in <code>list_of_streams</code>.
</p>
<p><b>Solution</b> see <i>tutorial_many_to_many.py</i>:
<p>
<center><code>
stream_agent(inputs=list_of_streams, outputs=[max_stream, min_stream],
f_type ='element', f=max_and_min)
</code></center>
</p>
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<!------------------------------------------------------------>
<h2>Placing no value on a stream</h2>
<p>In some cases we want an agent to append <code>None</code> to an output
stream and in other cases we want the agent to append no element. In
the former case <code>f</code> returns <code>None</code>, and in the latter case,
we want <code>f</code> to return an object that indicates that the agent
should append no elements to the output stream. We use a special
object <code>_no_value</code> for this purpose. The effect of appending the
object <code>_no_value</code> to a stream is that no value gets appended to
the stream.</p>
<h4>Example of <i>_no_value</i>: Filter</h4>
<p> <b>Problem</b>: <code>input_stream</code> and <code>output_stream</code> are streams and
<code>boolean_func</code> is a function from elements of <code>input_stream</code> to
Booleans. Write a function <code>filter_stream_1</code>:
</p>
<center><code>
filter_stream_1(input_stream, output_stream, boolean_func)
</code></center>
that creates an agent that places elements of
<code>input_stream</code> that satisfy <code>boolean_func</code> on
<code>output_stream</code>. (We will write a function
<code>filter_stream</code> with the same semantics as
<code>filter_stream_1</code>; the difference is that
<code>filter_stream</code> is implemented with the list wrapper rather
than the element wrapper.
<p><b>Solution: see <i>filter_stream_1.py</i> </b>
<pre>
<code>
from Stream import _no_value
def filter_stream_1(input_stream, output_stream, boolean_func):
def filter_element(element):
return element if boolean_func(element) else _no_value
stream_agent(
inputs=input_stream, outputs=output_stream,
f_type ='element', f=filter_element)
</code>
</pre>
</p>
<h2>Placing multiple values on a stream</h2>
<p>In some cases, we want an agent to append a list or tuple to a
stream; for example, we want the agent to append the list [2, 3], as a
single element, to a stream. In other cases, we want the agent to
append multiple elements to a stream; for example, append the two
elements 2 and 3 as two separate elements rather than as the single
list [2, 3]. If the initial value of the stream is [0, 1], then in the
first case, the value of the stream after [2, 3] is appended is [0, 1,
[2, 3]], whereas in the latter case we want the value of the stream to
be [0, 1, 2, 3]. We use the class <code>_multivalue</code> for this
purpose. If function <code>f</code> returns a list <code>z</code> then the agent
appends the entire list <code>z</code>, as a single element, to an output
stream, and if <code>f</code> returns <code>_multivalue(z)</code> then the agent
appends each element of <code>z</code>, as a separate element, to the output
stream.</p>
<h4>Example of <i>_multi_value</i></h4>
<p> <b>Problem</b>: <code>list_of_streams</code> is a list of streams and
<code>output_stream</code> is a stream. Write a function:
<center><code>
weave_streams(list_of_streams, output_stream)
</code></center>
that creates an agent that sets:
<center><code>
output_stream[n*j + k] = list_of_streams[k][j]
</code></center>
for <code>j = 0, 1, 2, 3, ...</code> and <code>k < n = len(list_of_streams)</code>.
</p>
<p> For example, if <code>list_of_streams = [x, y, z]</code> where <code>x</code>,
<code>y</code> and <code>z</code> are streams, then the sequence of values of
<code>output_stream</code> are:
<br>
<code>x[0], y[0], z[0], x[1], y[1], z[1], x[2], y[2], z[2], ....</code> </p>
<p><b>Solution: see <i>weave_streams.py</i> </b>
<pre>
<code>
from Stream import _multi_value
def weave_streams(list_of_streams, output_stream):
def weave(list_of_elements):
return _multivalue(list_of_elements)
stream_agent(
inputs=list_of_streams, outputs=output_stream,
f_type ='element', f=weave)
</code>
</pre>
</p>
<h1>Agents with state</h1>
<p>
The agents in the previous examples do not have state: the j-th
element of an output stream is a function of the j-th elements of its
input streams, and is independent of earlier elements in its inputs.
An agent has state when the j-th element of an output stream depends
on earlier elements of an input stream.
</p>
<p> A state is an arbitrary object. It can be a number, string, tuple,
or instance of any class. The (j+1)-th state and the j-th element on
each of the output streams is a function <i>f</i> of the agent's j-th
state and the j-th elements on each of its input streams, for all
j. The initial state is the agent's zero-th state. (See "Mealy
machine.") </p>
<p> The wrapper for an agent with state specifies its initial
state.<p>
<center><code>
stream_agent(inputs, outputs, f_type='element',f, state)
</code></center>
<p>
where state is the initial state.
</p>
<h3>Example of element wrappers for agents with state</h3>
<p><b>Problem</b>: <code>input_stream</code> and
<code>output_stream</code> are streams. Write a function:
<pre><code>
average_of_stream(input_stream, output_stream)
</code></pre>
that creates an agent that sets the <code>j</code>-th element of
<code>output_stream</code> to the average of the first <code>j</code>
elements of <code>input_stream</code>.</p>
<p> <b>Solution</b> see <i>tutorial_average_of_stream.py</i>:
The state is a tuple <code>(n, cumulative)</code> where <code>n</code>
is the number of elements of <code>input_stream</code> that have been
processed and <code>cumulative</code> is the sum of these
elements. Initially, the state is (0, 0.0). When an element is
received on <code>input_stream</code>, the next state is computed by
incrementing <code>n</code> by 1 and incrementing
<code>cumulative</code> by the element just received. The element
appended to <code>output_stream</code> is the average:
<code>cumulative/float(n)</code>.
<pre><code>
def average_of_stream(input_stream, output_stream):
def update_average(input_element, current_state):
n, cumulative = current_state
n += 1
cumulative += input_element
next_state = (n, cumulative)
output_element = cumulative/float(n) # the new mean
return (output_element, next_state)
stream_agent(inputs=input_stream, outputs=output_stream,
f_type='element', f=update_average,
state=(0, 0.0))
</code></pre>
</p>
<p>See <i>TutorialExamplesElementWrapper.html</i> for a collection of
examples of agents with state.
</body>
</html>