## example: dynamic creation of streams

This example shows how streams can be created dynamically, and illustrates the use of *_no_value* and *state*. 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 filter_multiples(v, state, primes): if state == 0: primes.append(v) return _no_value, (v, True) else: my_prime, last = state if v % my_prime == 0: return _no_value, state elif last: sieve(out_stream, primes) return v, (my_prime, False) else: return v, state filter_multiples(in_stream, out_stream, state=0, primes=primes)

The state of the function *f* is either 0 or a 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* when this function has emitted at least one value on its output stream.

The function *filter_multiples* 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 *then 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. So 2 gets appended to primes and the function returns a new state: ((*my_prime*, *last*) = (*_no_value*, *True*), and so the output stream is not extended, and the state records that this execution of *filter_multiples* is the last one (since *last* = *True*) to have been called.

The next value that arrives on the input stream is 3. Since *state* is not 0, *my_prime*, *last* are extracted from the state to yield *my_prime *=2 and *last *= *True*. Since 3 is not a multiple of 2, and since *last *is *True, *a new sieve is called. The parameters passed to the new call of sieve are the *out_stream *of this *filter_multiples *and the stream *primes* which now has a single element: 2. Next *filter_multiples* 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*.

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.