In [this blog post](my previos post), I discussed how Kotlin uses suspendable functions for asynchronous programming and functions similar to generators. Unlike Kotlin, languages like JavaScript, Python, and C# use separate constructs for these two concepts (e.g., async-await vs. yield).

Kotlin uses the sequence and yield functions to create functionality that behaves like generators in other languages. Here’s an example:

1
2
3
4
5
6
7
8
9

val cities = sequence {
    yield("Paris")
    yield("Lyon")
    yield("Bordeaux")
}

for (city: String in cities) {
    println(city)
} 

This link points to the sequence function ([documentation here](Sequence Builder)), which accepts a “suspendable block” that operates on a SequenceScope. The yield function (documentation here) is a suspendable function that belongs to the SequenceScope class. Here are their signatures:

1
2
3
4

fun sequence(
    block: suspend SequenceScope.() -> Unit
): Sequence 
abstract suspend fun yield(value: T)

Using suspendable functions for generator-like behavior initially surprised me. A suspendable function is typically called once, may suspend multiple times, and returns a single result. Generators, on the other hand, are called repeatedly, producing a value with each call.

The key to understanding this lies in how the compiler transforms suspendable functions into state machines. Each suspension point in the function represents a state. When a suspendable function calls another suspendable function (suspension point), it returns a COROUTINE_SUSPENDED value to its caller, signaling suspension. Upon completion of the awaited asynchronous operation, the coroutine resumes the suspended function through its associated Continuation. Finally, the suspendable function returns its result instead of COROUTINE_SUSPENDED.

For generator-like behavior, we call an iterator.next() method. If the iterator invokes a suspendable function that doesn’t rely on asynchronous calls, the suspendable function stores the generated value and returns COROUTINE_SUSPENDED. The iterator can then retrieve this value. Subsequent calls to iterator.next() resume the suspendable function, generating the next value, and so on.

Examining Kotlin’s source code (SequenceBuilder.kt) confirms this approach. The SequenceBuilderIterator class plays a crucial role, acting as a SequenceScope, an Iterator, and a Continuation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

private class SequenceBuilderIterator : SequenceScope(), Iterator, Continuation {
    private var state = State_NotReady
    private var nextValue: T? = null
    private var nextIterator: Iterator? = null
    var nextStep: Continuation? = null

    override fun hasNext(): Boolean {
        ...
    }

    override fun next(): T {
        ...
    }

 
    override suspend fun yield(value: T) {
        ...
    }

    override suspend fun yieldAll(iterator: Iterator) {
        ...
    }

    // Completion continuation implementation
    override fun resumeWith(result: Result) {
       ...
    }

    override val context: CoroutineContext
        get() = EmptyCoroutineContext
} 

Here’s how it works:

1. When calling the sequence() function with a suspendable function (block) that uses a SequenceScope as its receiver, the function creates a SequenceBuilderIterator. This iterator stores a Continuation object for the suspend function in its nextStep property. This continuation, in turn, stores the SequenceBuilderIterator (which is also a SequenceScope) in its state.
2. The sequence() function wraps the SequenceBuilderIterator in a Sequence object, where the iterator() method simply returns the SequenceBuilderIterator.

To iterate over the Sequence, we call its iterator() method, which returns the SequenceBuilderIterator instance. Calling .next() on this iterator invokes the Continuation for the suspend function stored in the nextStep property. This suspend function then calls the yield() function. Since yield() is another suspend function that receives the SequenceBuilderIterator (our SequenceScope) as its receiver, it sets the next value to be returned in the SequenceBuilderIterator’s nextValue property.

The versatile SequenceBuilderIterator acts as the glue that connects these elements. It has a next() method for iteration, returning the value set by the yield() function in the nextValue property. It also has the nextStep property, which points to the continuation that encapsulates the main suspend function.

Interestingly, the CoroutineContext associated with a SequenceBuilderIterator is an EmptyCoroutineContext. While we’ve seen that Continuations usually have a CoroutineContext containing a Job and a Dispatcher, these components are unnecessary for our generator-like functionality.