Sequences: Yield vs. Return & How Pausing Functions Work

An introduction to the sequence method, an explanation of yield vs. return, a look into how to implement functions which can pause using continuations, and how this relates to suspend functions and coroutines.

— — — — — — — — — — — — — — —

THE CURRENT VERSION OF THIS ARTICLE IS PUBLISHED HERE.

— — — — — — — — — — — — — — —

Tags: #FUNDAMENTAL CONCEPT

This article is part of the Kotlin Primer, an opinionated guide to the Kotlin language, which is indented to help facilitate Kotlin adoption inside Java-centric organizations. It was originally written as an organizational learning resource for Etnetera a.s. and I would like to express my sincere gratitude for their support.

It is recommended to read the Introduction before moving on. Check out the Table of Contents for all articles.

sequence

fun <T> sequence(
    block: suspend SequenceScope<T>.() -> Unit
): Sequence<T>

The sequence method is a unique way you can build up a Sequence by sequentially generating each element (or collection of elements). Even from it’s signature, you can see it’s a different — we’ve never encountered the suspend keyword until now.

The key difference between generateSequence, which we discussed in the previous article, and sequence is that in this case, the values are not produced by returning them from a lambda, but by calling yield (for producing a single element), or yieldAll (for producing all elements in a collection). Crucially, neither of those calls need to be at the end of a function, like a return statement — you can call them whenever you want to, which allows us to solve certain problems much more elegantly.

Let’s take a look at an example:

Both of the above implement the sequence of Fibonacci numbers.

In the first version, where we’re constrained to returning from a function, it’s more difficult to deal with state (notice that we have to keep the state outside of the lambda defining the sequence), more difficult to update state after we produce the value (notice that we need to save the value in an intermediate variable so we can return it) and involves other nuisances as well. For example, since the state is kept track of separately, there’s no input to the lambda in generateSequence. However, this means that we’re using the generateSequence variant that produces Sequences constrained to run only once! In a way, this is actually a good thing, since if we ran it multiple times, we would get nonsensical results — both runs would be accessing the same terms variable — but it’s certainly not something we want to deal with in a scenario as simple as generating a mathematical sequence of numbers.

The yielding version solves all of these problems nicely. The fundamental reason this is so is because it gives us complete control over the flow of execution.

Yielding vs. Returning

When using constructs like generateSequence, the order in which certain things happen are prescribed, and cannot be changed. For instance, in generateSequence, the prescribed flow of execution is:

1. run function,
2. use produced value as element in sequence,
3. pass produced value as input to next run of function,
4. repeat.

These steps are set in stone, and it is impossible to e.g. wedge an additional step between “use produced value as element in sequence” and “pass produced value as input to next run of function”, which is ideally what we want to do when generating a Fibonacci sequence. We also don’t have control over the manner in which these steps are repeated — there is obviously some sort of loop or iteration involved, but it’s hidden inside the implementation of generateSequence.

When we produce values by calling a function (commonly called yielding) instead of returning, we can do whatever we want, including updating state after producing a value (which saves us from having to define a temporary variable), and implementing the loop manually (which allows us to include the state inside the generating lambda, but still keep it outside the loop, which is why we couldn’t do the same thing with generateSequence).

Now, if you’ve been paying attention, you should be thinking Waaait a second…how can that even work? After all, the defining feature of sequences is that all operations get applied as soon as an element is produced — indeed, sequences can be infinite. But in the approach above, we’re not producing an element at the end of the execution of the lambda, but in the middle of it. In essence, this amounts to being able to instruct the function to produce a value and pause, and having it continue from the same spot when the next value is requested.

That sounds crazy — how could that possibly work? How can a function just decide to pause (or temporarily suspend its execution) in the middle of a run, and resume later? And what is that suspend thing?

The answer to the second question is: actually, it doesn’t really pause. It just looks like does, which is a trick made possible by the Kotlin compiler.

Implementing a Pausing Function

Let’s try to demonstrate the essence of how to implement a “pausing” function without taking advantage of Kotlin-specific compiler-fu, so you get a very rough idea of what the compiler is doing behind the scenes. The actual technical implementation uses the framework upon which Kotlin coroutines are built, which is also where that suspend keyword comes from.

The above is a simplified builder for Iterators producing values of some non-nullable type T via a yield “pausing” function. It uses a simple state machine to determine if a new value has already been produced and is available, or is not yet available and must be produced. To keep things as simple as possible, we’re completely ignoring any type of error handling except for the basic “no more elements” scenario, and also don’t support producing nullable values.

The fundamental principle that makes this work is the fact that yield accepts a callback, which contains everything that should happen after the function is “resumed”. When yield is called, this callback is saved in nextPart, and gets called once the state machine determines that we need to produce a new value. These types of callbacks are called continuations (they continue with executing the rest of the code), and they allow for some of the more powerful techniques in programming.

Once you think about it like that, you’ll see that there isn’t actually any pausing involved — it’s a trick. Instead, you break up your function into nested callbacks (or, to use a more technical term, rewrite it in continuation-passing style) and pass each callback to some sort of logic that decides when to call them. It is then trivial to call each successive callback whenever you feel like it — now, later, whenever.

In the above, the state machine controls when the function gets “resumed” (it gets resumed when hasNext is called), but you could do anything you want. The actual implementation of sequence uses something similar, but much more robust (deals with errors, allows nullable values, and so on).

“But we’re not writing any such code when building sequences!” I hear you exclaim. “There are no callbacks, no nested lambdas, nothing like that!”. That’s because the compiler is doing all this for us, behind the scenes. To simplify things greatly, that suspend keyword you saw at the beginning tells the compiler to take the following:

val seq = buildUsingYield<Int> {
  println("Yielding 1 and pausing")
  yield(1)
  println("Resumed after 1, yielding 2 and pausing")
  yield(2)
  println("Resumed after 2, yielding 3 and pausing")
  yield(3)
  println("Resumed after 3, and finishing")
}

And transform it by adding a hidden Continuation parameter to yield, and change the calling code to something that distantly resembles the following:

val seq = buildUsingYield<Int> {
      println("Yielding 1 and pausing")
      yield(1) {
          println("Resumed after 1, yielding 2 and pausing")
          yield(2) {
              println("Resumed after 2, yielding 3 and pausing")
              yield(3) {
                  println("Resumed after 3, and finishing")
              }
          }
      }
  }

Just so we understand each other, theContinuation instance is not a functional or SAM type— you can’t pass a lambda where a Continuation is expected. In the above, I’m simply demonstrating what the Continuation represents — a thing you can call to continue executing the rest of the program — by writing a lambda instead of it. You can see that that can’t be exactly what’s happening, because you couldn’t translate our Fibonacci example, where yield is part of a while loop, into a similar form. However in principle, this — i.e. rewriting yield to accept a Continuation— is what happens.

By the way, this is the fundamental principle the entire coroutines framework is built upon, but that’s a story for another day.

It’s worth mentioning that there is a builder for instances of Iterator that permits the same syntax:

fun <T> iterator(
    block: suspend SequenceScope<T>.() -> Unit
): Iterator<T>

Example

Go back to Sequences: How They Work & How To Use Them, jump to the Table of Contents, or continue to Sequences: Iterable vs. Sequence vs. Java Stream.