How does the prime numbers example from the Kotlin Coroutines documentation work?

Question

I'm going through the coroutines documentation for Kotlin and was following along pretty well until this example. I'm having a really difficult time understanding how it's calculating when it finds a prime number, and specifically how the return from the filter function is both being returned and assigned to cur, as well as still producing numbers from the numbersFrom method.

I've added debugging statements to try and follow the various coroutines that are running, but I'm still lost on the logical flow of when it starts new coroutines and receives numbers from others.

https://github.com/Kotlin/kotlinx.coroutines/blob/master/coroutines-guide.md#prime-numbers-with-pipeline

The code:

fun log(msg: String) = println("[${Thread.currentThread().name}] $msg")

fun main(args: Array<String>) = runBlocking<Unit> {
    var cur = numbersFrom(context, 2)
    for (i in 1..10) {
        val prime = cur.receive()
        println(prime)
        cur = filter(context, cur, prime)
    }
}

fun numbersFrom(context: CoroutineContext, start: Int) = produce<Int>(context) {
       var x = start
    while (true) {
        log("NumbersFrom Send: ${x}")
        send(x++)
    } // infinite stream of integers from start
}

fun filter(context: CoroutineContext, numbers: ReceiveChannel<Int>, prime: Int) = produce<Int>(context) {
    for (x in numbers) {
        log("filter ${x}, prime ${prime}")
        if (x % prime != 0) {
            send(x)
        }
    }
}

Outout:

[main @coroutine#2] NumbersFrom Send: 2
[main @coroutine#2] NumbersFrom Send: 3
2
[main @coroutine#3] filter 3, prime 2
[main @coroutine#2] NumbersFrom Send: 4
[main @coroutine#2] NumbersFrom Send: 5
3
[main @coroutine#3] filter 4, prime 2
[main @coroutine#3] filter 5, prime 2
[main @coroutine#4] filter 5, prime 3
[main @coroutine#2] NumbersFrom Send: 6
[main @coroutine#3] filter 6, prime 2
5
[main @coroutine#2] NumbersFrom Send: 7
[main @coroutine#2] NumbersFrom Send: 8
[main @coroutine#3] filter 7, prime 2
[main @coroutine#3] filter 8, prime 2
[main @coroutine#4] filter 7, prime 3
[main @coroutine#2] NumbersFrom Send: 9
[main @coroutine#2] NumbersFrom Send: 10
[main @coroutine#5] filter 7, prime 5
[main @coroutine#3] filter 9, prime 2
[main @coroutine#3] filter 10, prime 2
7
[main @coroutine#4] filter 9, prime 3
[main @coroutine#2] NumbersFrom Send: 11
[main @coroutine#2] NumbersFrom Send: 12
[main @coroutine#3] filter 11, prime 2
[main @coroutine#3] filter 12, prime 2
[main @coroutine#4] filter 11, prime 3
[main @coroutine#2] NumbersFrom Send: 13
[main @coroutine#2] NumbersFrom Send: 14
[main @coroutine#5] filter 11, prime 5
[main @coroutine#3] filter 13, prime 2
[main @coroutine#3] filter 14, prime 2
[main @coroutine#6] filter 11, prime 7
[main @coroutine#4] filter 13, prime 3
[main @coroutine#2] NumbersFrom Send: 15
[main @coroutine#2] NumbersFrom Send: 16
11
[main @coroutine#5] filter 13, prime 5
[main @coroutine#3] filter 15, prime 2
[main @coroutine#3] filter 16, prime 2
[main @coroutine#6] filter 13, prime 7
[main @coroutine#4] filter 15, prime 3
[main @coroutine#2] NumbersFrom Send: 17
[main @coroutine#2] NumbersFrom Send: 18
[main @coroutine#7] filter 13, prime 11
[main @coroutine#3] filter 17, prime 2
[main @coroutine#3] filter 18, prime 2
13
[main @coroutine#4] filter 17, prime 3
[main @coroutine#2] NumbersFrom Send: 19
[main @coroutine#2] NumbersFrom Send: 20
[main @coroutine#5] filter 17, prime 5
[main @coroutine#3] filter 19, prime 2
[main @coroutine#3] filter 20, prime 2
[main @coroutine#6] filter 17, prime 7
[main @coroutine#4] filter 19, prime 3
[main @coroutine#2] NumbersFrom Send: 21
[main @coroutine#2] NumbersFrom Send: 22
[main @coroutine#7] filter 17, prime 11
[main @coroutine#5] filter 19, prime 5
[main @coroutine#3] filter 21, prime 2
[main @coroutine#3] filter 22, prime 2
[main @coroutine#8] filter 17, prime 13
[main @coroutine#6] filter 19, prime 7
[main @coroutine#4] filter 21, prime 3
[main @coroutine#2] NumbersFrom Send: 23
[main @coroutine#2] NumbersFrom Send: 24
17
[main @coroutine#7] filter 19, prime 11
[main @coroutine#3] filter 23, prime 2
[main @coroutine#3] filter 24, prime 2
[main @coroutine#8] filter 19, prime 13
[main @coroutine#4] filter 23, prime 3
[main @coroutine#2] NumbersFrom Send: 25
[main @coroutine#2] NumbersFrom Send: 26
[main @coroutine#9] filter 19, prime 17
[main @coroutine#5] filter 23, prime 5
[main @coroutine#3] filter 25, prime 2
[main @coroutine#3] filter 26, prime 2
19
[main @coroutine#6] filter 23, prime 7
[main @coroutine#4] filter 25, prime 3
[main @coroutine#2] NumbersFrom Send: 27
[main @coroutine#2] NumbersFrom Send: 28
[main @coroutine#7] filter 23, prime 11
[main @coroutine#5] filter 25, prime 5
[main @coroutine#3] filter 27, prime 2
[main @coroutine#3] filter 28, prime 2
[main @coroutine#8] filter 23, prime 13
[main @coroutine#4] filter 27, prime 3
[main @coroutine#2] NumbersFrom Send: 29
[main @coroutine#2] NumbersFrom Send: 30
[main @coroutine#9] filter 23, prime 17
[main @coroutine#3] filter 29, prime 2
[main @coroutine#3] filter 30, prime 2
[main @coroutine#10] filter 23, prime 19
[main @coroutine#4] filter 29, prime 3
[main @coroutine#2] NumbersFrom Send: 31
[main @coroutine#2] NumbersFrom Send: 32
23
[main @coroutine#5] filter 29, prime 5
[main @coroutine#3] filter 31, prime 2
[main @coroutine#3] filter 32, prime 2
[main @coroutine#6] filter 29, prime 7
[main @coroutine#4] filter 31, prime 3
[main @coroutine#2] NumbersFrom Send: 33
[main @coroutine#2] NumbersFrom Send: 34
[main @coroutine#7] filter 29, prime 11
[main @coroutine#5] filter 31, prime 5
[main @coroutine#3] filter 33, prime 2
[main @coroutine#3] filter 34, prime 2
[main @coroutine#8] filter 29, prime 13
[main @coroutine#6] filter 31, prime 7
[main @coroutine#4] filter 33, prime 3
[main @coroutine#2] NumbersFrom Send: 35
[main @coroutine#2] NumbersFrom Send: 36
[main @coroutine#9] filter 29, prime 17
[main @coroutine#7] filter 31, prime 11
[main @coroutine#3] filter 35, prime 2
[main @coroutine#3] filter 36, prime 2
[main @coroutine#10] filter 29, prime 19
[main @coroutine#8] filter 31, prime 13
[main @coroutine#4] filter 35, prime 3
[main @coroutine#2] NumbersFrom Send: 37
[main @coroutine#2] NumbersFrom Send: 38
[main @coroutine#11] filter 29, prime 23
[main @coroutine#9] filter 31, prime 17
[main @coroutine#5] filter 35, prime 5
[main @coroutine#3] filter 37, prime 2
[main @coroutine#3] filter 38, prime 2
29
[main @coroutine#10] filter 31, prime 19
[main @coroutine#4] filter 37, prime 3
[main @coroutine#2] NumbersFrom Send: 39

Answer 1

The point of the example is to implement the Sieve of Eratosthenes. In other words, to find prime numbers by filtering out numbers that can't be prime because of their divisibility. Anything left is a prime.

Let's look at what we have. I'm going to ignore all of the context variables for now, it just makes things easier to talk about.

First, we have a function called numbersFrom, which is just an endless sequence of integers starting at 2 (in this case).

We also have function called filter, which takes in a channel, and a number which is presumably prime. Looking at the return type, we can see that this function returns a new producer. In order to produce results (Ints in this case), the send function can be called. Looking at the body of the function, filter will accept numbers off the channel (via send) and REJECT anything that is evenly divisible by the prime number (by doing nothing).

For example, if the channel produces a 4 and the prime is a 2, that is rejected. On the other hand, if the channel produces a 5 and the prime is a 2, it will send that number along. It should now become obvious that filter does what its name says - read inputs, find the ones it likes, send them along to its output.

Now let's look at the main function. First we create a stream of numbers starting at 2 (what a coincidence, the first prime!) and assign that to cur. So far, so good.

Next, we start a loop. I reduced the 10 to a 3 to make things easier to understand, but essentially that number means how many primes the main method will calculate. If you want the first 100 primes, set it to 100.

In the loop, we take the first number off the numbers list, by calling receive() on cur. This is a suspending function. And as I mentioned above, it will get a 2 as its first prime value.

And now here is the fun part. We take that 2, and use it as the basis for a call to filter, along with cur, which is currently the stream of Ints, and reassign that to cur. So what does that mean? cur now represents a stream of Ints, filtered to NOT be divisible by 2!.

In the next loop, we take the first number off the cur channel, and it's a 3. The next prime. Why is it a 3? Because filter(2) allowed it to pass (3 % 2 != 0). This is the fun part. Now we take cur (a filtered list of numbers that are not divisible by 2) and pass it into a filter function, along with 3 (our most recent prime). Now cur represents a stream of numbers not divisible by 2 or 3. See where this is going?

Essentially at this point we have this:

numbers -> filter(2) -> filter(3)

Or, read another (less precise wrt coroutines but easier to picture):

filter(3, filter(2, numbers))

Any number that makes it to the head of cur is prime, because it passed through all of the filters.

Thanks for asking this question! "Go learn Kotlin Coroutines" has been on my research list for a couple of weeks and I had a good morning reading about them and figuring this out.

Answer 2

Make sure you understand the logic of Sieve of Eratosthenes algorithm.

Look at the animation: filter(2) is shown in red color. filter(3) is green, filter(5) is blue, etc.