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!