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.