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 because 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.