## example: dynamic creation of streams

This example illustrates three features: how streams can be created dynamically, how the state can be used, and the use of *_no_value*. The example is the sieve of Eratosthenes.

In the following, *primes* is a list and *in_streams* is a stream, and we will design a function *sieve*(*x*, *primes*) such that if *x* is the sequence [2, 3, …, n], and *primes* is initially the empty stream, then the function terminates with *primes* containing the list of prime numbers up to *n*.

def sieve(in_stream, primes): out_stream = Stream() @map_e def f(v, state, primes): my_prime, last = state output = _no_value if my_prime == 0: my_prime = v primes.append(v) else: if v % my_prime != 0: output = v if last: last = False sieve(out_stream, primes) return output, (my_prime, last) f(in_stream, out_stream, state=(0, True), primes=primes)

The state of the function *f* is initially 0 and later becomes the pair (*my_prime*, *last*). The state is 0 before the function is called for the first time. After the function is called at least once, *my_prime* becomes the first value received by the function on its input stream. *last *is a Boolean where *last* is initially True and *last* becomes *False* after *sieve* calls itself. The diagram below shows the sequence of sieves generated by the program.

The function *f* always returns two values: the next element of the output stream and the next state. When the next element of the output stream is *_no_value* the output stream is not extended.

*Skip the remainder of the section if the code is self evident.*

Let’s look at the very first call to *filter_multiples*. The value that arrives on the input stream is 2. At this point *state* is 0 and *primes* is the empty stream. The incoming value, 2, gets appended to primes and the function returns a new state: (*my_prime*, *last*) = (*_no_value*, *True*). Since the output element is *_no_value *the output stream is not extended. The state records that this execution of *f* has not yet called sieve because *last* = *True*.

The next value that arrives on the input stream is 3. Because *state* is not 0, *my_prime*, *last* are extracted from the state to yield *my_prime *=2 and *last *= *True*. Because 3 is not a multiple of 2, and *last *is *True, *a new *sieve* is called. The parameters passed to the new call of *sieve* are the *out_stream *of this *f *and the stream *primes* which now has a single element: 2. Next *f* returns *v*, (*my_prime*, *False*), i.e., the next element *v* = 3 of its output stream and the next state (2, *False*) which identifies *my_prime *as 2, and *last* as *False*. *last* is *False b*ecause f has called *sieve*.

The next value that arrives on the input stream is 4. Since *state* is not 0, *my_prime*, *last* are extracted from the state to yield *my_prime *=2 and *last *= *False*. Since 4 is a multiple of 2, the function returns (*_no_value*, *state*) = (*_no_value*, (2*, False*)). So, the output stream is not extended and *my_prime *and* last *remain unchanged.