Generators via Continuations / Suspendable Functions

Hi there, I was wondering if there are any medium/long-term plans of supporting continuations in Scala?

I’ve been looking at languages that do support them (Python, Kotlin, JavaScript, C#), and have realized they are a powerful feature that enables simpler ways to achieve a lot of functionality. I thought I would make a thread to motivate a bit about why I think they’re really cool.

Generators

For those not familiar with generators, they are a way of defining a lazy Iterator-like data structure, where the production of data is written in an imperative, seemingly strict way, but is in fact transformed into a state machine where data is produced one-at-a-time, because at each call to yield (or similar method), control is returned to the caller, and so the statements that follow are not called until the caller invokes the generator’s .next() again. In Scala, it might look something like the following (inspired by this implementation in Kotlin: https://github.com/Kotlin/coroutines-examples/blob/master/examples/generator/generator.kt ):

    val iter: Iterator[Int] = generate[Int] {
      var i = 0
      while (true) {
        println(s"yielding $i")
        yield(i)
        i += 1
      }
    }
    
    iter.next() // "yielding 0" is printed, 0 is returned
    iter.next() // "yielding 1" is printed, 1 is returned
    iter.next() // "yielding 2" is printed, 2 is returned

This is a powerful and simplifying feature that would IMO have far-reaching benefits, but it’s hard to put into words why that is, so instead of describing, I’ll first illustrate how simplifying this mechanism can be. I’ll do this by taking a few implementations of iterators from the standard library, and re-implementing them with generators, resulting in order-of-magnitude simpler code.

filter

In the standard library, both filter and filterNot delegate their implementation to a method called filterImpl which also takes a param isFlipped: Boolean (false if called by filter, true if called by filterNot). Here is the implementation in Iterator.scala

    private[collection] def filterImpl(p: A => Boolean, isFlipped: Boolean): Iterator[A] = new AbstractIterator[A] {
        private[this] var hd: A = _
        private[this] var hdDefined: Boolean = false
    
        def hasNext: Boolean = hdDefined || {
          if (!self.hasNext) return false
          hd = self.next()
          while (p(hd) == isFlipped) {
            if (!self.hasNext) return false
            hd = self.next()
          } 
          hdDefined = true
          true 
        }
    
        def next() =
          if (hasNext) {
            hdDefined = false
            hd
          }
          else Iterator.empty.next()
      }

As you can see, there are uninitialized variables and complicated mutable state that needs to be manually kept track of. Care must be taken to ensure that the all fields are privately scoped, and at all times in a valid state. Now compare to the generator version:

    private[collection] def filterImpl(p: A => Boolean, isFlipped: Boolean): Iterator[A] = generate[A] {
    	while(self.hasNext) {
        val a = self.next()
        if (p(a) != isFlipped)) yield(a)
      }
    }

flatmap

Next up we have flatMap. Note that we again have to manually track our state with ad-hoc private fieldp protocols:

    def flatMap[B](f: A => IterableOnce[B]): Iterator[B] = new AbstractIterator[B] {
        private[this] var cur: Iterator[B] = Iterator.empty
        /** Trillium logic boolean: -1 = unknown, 0 = false, 1 = true */
        private[this] var _hasNext: Int = -1
    
        private[this] def nextCur(): Unit = {
          cur = null
          cur = f(self.next()).iterator
          _hasNext = -1
        }
    
        def hasNext: Boolean = {
          if (_hasNext == -1) {
            while (!cur.hasNext) {
              if (!self.hasNext) {
                _hasNext = 0
                // since we know we are exhausted, we can release cur for gc, and as well replace with
                // static Iterator.empty which will support efficient subsequent `hasNext`/`next` calls
                cur = Iterator.empty
                return false
              }
              nextCur()
            }
            _hasNext = 1
            true
          } else _hasNext == 1
        }
        def next(): B = {
          if (hasNext) {
            _hasNext = -1
          }
          cur.next()
        }
      }

The generator version:

    def flatMap[B](f: A => IterableOnce[B]): Iterator[B] = generate[B] {
      while (self.hasNext) {
        yieldAll(f(self.next()).iterator)
      }
    }

dropWhile

stdlib:

    def dropWhile(p: A => Boolean): Iterator[A] = new AbstractIterator[A] {
        // Magic value: -1 = hasn't dropped, 0 = found first, 1 = defer to parent iterator
        private[this] var status = -1
        // Local buffering to avoid double-wrap with .buffered
        private[this] var fst: A = _
        def hasNext: Boolean =
          if (status == 1) self.hasNext
          else if (status == 0) true
          else {
            while (self.hasNext) {
              val a = self.next()
              if (!p(a)) {
                fst = a
                status = 0
                return true
              }
            }
            status = 1
            false
          }
        def next() =
          if (hasNext) {
            if (status == 1) self.next()
            else {
              status = 1
              fst
            }
          }
          else Iterator.empty.next()
      }

with generators:

    def dropWhile(p: A => Boolean): Iterator[A] = generate[A] {
      while(self.hasNext) {
        val next = self.next()
        if (!p(next)) {
          yield(next)
          yieldAll(self)
          return
        }
      }
    }

In each of these cases the generator version provides a 10-fold improvement in simplicity, readability and writability, and that’s a conservative estimate. By allowing us to use simple imperative control structures to produce elements in a lazy way, we no longer have to resort to using class fields to store our state, with bespoke protocols of encoding our control flow in those fields. The language automates the process of transforming our “push-based” code into a pull-based state machine.

Generators aren’t only useful in the stdlib though. They’d help out in every-day programming tasks. For instance, recently I had to write a little utility which would randomly generate sequences of business domain events. Within one sequence of events, many events would need to refer to the same few entities, by id. For this kind of task, it would be nice to do something like for example:

    generate[Event] {
      val userId: String = randomId()
      
      yield UserCreated(id = userId, name = randomName())
    
      // maybe make this user an admin
      if (randomBoolean()) {
        yield GrandAdminPriviledges(userId = userId) 
      }
    
      // create some posts by the user
      val posts = (0 until randInt(10)).map(_ => randomPostByUser(userId))
    
      posts.foreach(p => yield PostCreated(p))
    
      
      // comment on some of the posts
      randomSelectionOf(posts).foreach {p => 
        yield CommentMade(postId = p.id, userId = userId, body = randomBody()
      }
      
    }

Even this simple generator would be prohibitively complex as a manual custom iterator, and would distract from the real business task at hand. Building up a custom iterator from primitive ones and combinators would not be much simpler either. So what I ended up resorting to was just creating an ArrayBuffer[Event] for each scenario, strictly pushing all events for the scenario, then getting the iterator out of the buffer. This is not what I would have ideally liked to do. I initially set out to generate events one at a time, but the tools available in the language pushed me to generate events in batches to avoid the complexity implied by a lazy implementation.

I know there may be some folks won’t be that enthusiastic about a feature which empowers usage of imperative control structures like yield, while, var. But I would argue that Scala, as a functional-leaning language could provide best-in-class tools for utilization of laziness if and where it is appropriate, and generators are a full league above manual iterators in that domain, and that on the flip side, by empowering lazy imperative code in the small, we are opening the door to more functional code in the medium and large.

Thanks for your time!

14 Likes

I would like coroutines, but if they are baked into the language, can we preserve a good amount of flexibility and extensibilty, especially when it comes to concurrency models? For instance, take a transactional generator:

def dropWhile(p: A => Boolean): TxIterator[A] = generate[A] { implicit txn =>
      while(self.hasNext) {
        val next = self.next()
        if (!p(next)) {
          yield(next)
          yieldAll(self)
          return
        }
      }
    }

So that the next() call here must always take an ongoing transaction:

    def next()(implicit txn: Txn): A

This is just my example, but it could be any context, IO monad etc.

Without that, we would integrate something of quite limited scope into the language.

2 Likes

The big problem with compile-time coroutine transformation is things like this: we would need to compile-time coroutine-transform the def foreach higher-order function as well! But we compiled that earlier, so what can we do?

  1. Pre-compile two copies of everything in anticipation?
  2. Build everything from source and make a closed world assumption?
  3. Do post-compile bytecode transformations like the Quasar Fibers project?
  4. Try to push it into the underlying runtime like the JDK Fibers project?
  5. Define some kind of syntactic/type-driven transform for the callsites of higher-order functions that make them do “the right thing” in most cases?

None of these options are easy. I think (5) is the one promising for the Scala compiler, and I have some ideas/intuition for how it can play out, but it will take effort to spec out and make work. And it’s not just .foreach: idiomatic Scala code uses tons of higher order functions: map, filter, flatMap, fold, takeWhile, getOrElse, getOrElseUpdate, Console.withOut, the whole works.

This is less of a problem in other languages, where higher-order-functions are rarely used, and the program transform just needs to support a finite number of control flow constructs that cover the vast majority of idiomatic code. That is not the case for Scala

This isn’t just an issue for coroutines: it is also a big problem for the usability of async/await syntax in Scala as well, which is just as good as the ones in Python/C#/Javascript/etc., but hampered by Scala’s widespread use of higher-order functions. The old Scala-CPS (continuation-passing-style) compiler plugin also faced this issue, which prevented its usage in any non-trivial Scala code.

If we can figure out the story for how such transforms interact with higher order functions, that would bring us most of the way to making these kinds of syntax transforms possible. Otherwise we’d be basically limiting our transforms to only the most trivial Scala code containing if-else, while-loops, and really not much else. Basically the subset that async/await supports today.

10 Likes

See also the talk by Philipp Haller (@phaller) at Scala Days 2019 in Lausanne, which I think is very relevant:

1 Like

On a different tangent as I have been looking closer at Scala over the past three weeks I haven’t done this much math in in years (or even a decade). It reminds me of my younger years when roughly 22 years ago I started writing smalltalk to control something like this;

http://www.symbolicsound.com/cgi-bin/bin/view/Products/Capybara

When I think of generators I don’t think of spinning through text files as occurs in many big data projects, but musical synthesizers. For example I want to generate a sin wave … or I want to add a sin wave to a square wave, etc. I did some google searches and discovered some interesting historical stuff;

https://wiki.haskell.org/Synthesizer

I just wanted to suggest this because it makes for fun presentations, for example here is a white noise generator with a ostinato of six notes where the keyboard keys are subtracting the white noise away using narrow band filters.

)http://argon-evolution.com/ArgonMP3/argon-evolution.com_Heros.mp3
http://argon-evolution.com/ArgonMP3/argon-evolution.com_Heros.mp3

Wow that still sounds weird.

Hopefully this will inspire the design of the generators in a positive way :slight_smile:

4 Likes

Ah yeah, you’re absolutely right. It works in Kotlin:

generate<Int,Unit> {
    listOf(1, 2, 3).forEach { i ->
        yield(i)
    }
}

But that’s only because forEach is defined as an inline function:

public inline fun <T> Iterable<T>.forEach(action: (T) -> Unit): Unit {
    for (element in this) action(element)
}

if you define your own non-inline foreach, it doesn’t work with generators, because generate takes a suspend function:

fun <T, R> generate(block: suspend GeneratorBuilder<T, R>.(R) -> Unit): Generator<T, R> {
  ...

So yeah, we would have to either:

  1. go full suspendable+inline functions, and make a lot of the collection methods inline
  2. implement a special yieldAll which would allow us to do yieldAll(posts.iterator.map(p => PostCreated(p))
2 Likes

Possibly relevant: http://storm-enroute.com/coroutines/

1 Like

Yeah, the coroutines library has been around for a long time, and used to have a good deal of excitement behind it, but as far as I know it’s not active, and I don’t think it’s even been updated for 2.13. Might be an interesting starting point for someone to explore, though…

2 Likes

I think you should definitely try Dsl.scala. It just implemented all the features that you mentioned (and more).

4 Likes

Since nobody has pointed out the obvious yet: https://github.com/scala/scala-continuations

Extremely hard to understand and basically undocumented, but it does exactly what you’re asking for. The restrictions of not being able to cps-transform any normal methods (most importantly the usual Scala collections methods) together with the high complexity prevented mainstream adoption. While you can build higher-level abstractions (like coroutines and generators) using delimited continuations, the underlying complexity cannot be hidden from users.

The successor, scala-async, is more limited and easier to understand but still suffers from the same basic problem of only being usable with primitive, iterative code.

In the long run, fibers on the JVM will provide a solution for this without the complexity of delimited continuations or being limited to a subset of the library.

3 Likes

I was trying to use the scala-continuations library and was disappointed to find that it is no longer supported for scala 2.12 and higher. :frowning:

Also I found it difficult to fight with types and continuations. What I’m used to in Scheme is that once I call a continuation, the call-site does not return, thus its type should not influence the type of the function that calls it. I don’t know how this relates to well-typed functions. But in practice it made working with continuations difficult.

I more like the Dart way,with sync* and async*

what’s the Dart way, any pointers?

async – function returns Future (as in async/away)
async* — function returns Stream and yield emit value to this stream.

Details:
https://dart.dev/tutorials/language/streams

1 Like

Btw, writing initial part of cps-async on top of tasty macroses was surprisingly easy. (https://github.com/rssh/dotty-cps-async ).

5 Likes

Thank you; from a cursory glance however it looks like Dart’s system has exactly the same problems; you need to annotate any function that can yield with async, and so for example they have to duplicate the collection methods for each operation that should be able to execute asynchronously. The examples also just use plain while loops, and I don’t see how asynchronous methods compose (stream nested inside a stream)…

1 Like

Having an async return type is a different contract though. How would you distinguish callers that just want to get the value from callers that want a future/promise? You’ll just move the declaration load to them.

In any case, how about the js style:
function *() {
yield * list.map(some_func_without_yield)
}

And for the async case:
async function*() {
for await (const _ of list.map(some_async_function)) {
yield _
}
}

Project Loom removes the distinction between sync and async in type signatures (waits and sleeps become yields, threads can be replaced by fibers, so in the end you can create separate fiber for every task and sleep and wait inside it without blocking). Continuation is said to be a low-level primitive on which you could implement generators. Cooperation is probably done by:

  • launching two continuations on separate virtual threads which will be mounted on a single shared real thread
  • continuation.run() and Continuation.yield(...) would be used to interleave execution of both continuations in controlled manner
  • that’s only my guess :slight_smile:
2 Likes

Each supports for loops by replacing foreach to something else. That’s an ugly solution. The better solution is to transform for loops to another function, which is an extension function instead of member function. Since it’s an extension, the implementation can be switched by import statements.