PRE-SIP: Suspended functions and continuations

Scala Improvement Process
#16

The proposal exclusively seeks a direct style. Maybe we can do that with colored functions or context types. LOOM is JVM only, but Scala is multi-platform. LOOM currently does not provide functions like continuation, and it’s focused on virtual threads. We think depending on LOOM for this feature is fine if we have alternatives for Scala JS and Scala Native from which we can construct functions like continuation.

If the impl is not dependent on LOOM, we can solve the HOF problem by having a contextual type Suspend that works alongside the implicit system. The compiler could then treat lambdas and function bodies with this context type as candidates for CPS. This would probably require instrumenting both declarations and call sites, and not sure of the implications on bin compact but it would not require an additional suspend keyword.

#17

Would it work If instead of a suspend keyword we have just Suspend ?=> A. Context functions carry implicits in a way that composition with HOFs and others work as is today. The missing part is CPS over the body to create the suspension points state machine and loops

class Suspend

val x : Suspend ?=> Int = 1

val res = List(1, 2).map(_ + x) // this is ok

given Suspend = new Suspend

println(res)  //List(2, 3)
#18

I think such integration may look like this https://github.com/47deg/TBD/pull/30

There are better integrations for IO or any data type if its ADT has support for the particular case of suspension. In that case, it could also suspend instead of requiring the integration to run unsafeToCompletableFuture or a similar terminal function.

#19

I think overall, what is missing from this proposal is a clear description of:

  1. What does this provide to a user that Loom does not? All your user facing examples can be implemented with Loom with no compiler support. Are there user-facing code snippets that cannot work on Loom, that you can get working with this proposal? The internal machinery like the continuation function isn’t that interesting, because unless we can show improvements to user-facing code, it’s just a new syntax for library authors to implement the same thing they could already implement

  2. What’s the plan for Scala.js and Native? You repeatedly list being “cross platform” is an advantage of your proposal over Loom, but AFAICT the only current implementation relies on Loom, and the whole cross-platform design is hand-waved away as “we’ll figure something out”. If you want to claim that being cross platform is an advantage of your design, you actually have to provide a design that works cross-platform. Loom is probably more than a person-decade of work at this point, so figuring out an equivalent for Scala.js and Native is not something we can take for granted

  3. What are the limitations of this proposal? Every other implementation of this in any language has significant user-facing limitations. Even hardcoded-into-the-runtime implementations like Loom or Go’s lightweight threading hit issues with FFI calls into C code or OS-level blocking syscalls. We need a clear picture of what trade-offs this proposal makes, and where in the solution space this fits.

I’m fully in support of the stated motivation: direct-style code is what everyone learns in programming 101. If we can express monads and stuff in a direct style, without all this map/flatMap inner-platform-effect noise, while preserving all the other benefits of using monads, that’s great. But it’s a tough problem to crack

14 Likes
#20

TLDR: This pre-SIP proposal to add “suspended functions and continuations” to Scala 3 needlessly imports problemmatic legacy Kotlin approaches to solving a problem that Loom already solves in a theoretically more performant and user-friendly fashion.

In this discussion, I’m going to ignore “side-effects” since it is my firm belief that “side-effect tracking” is not commercially relevant, and if it were (which it’s not), it would have another solution that is not connected to the challenges around async programming.

Kotlin attempted to solve the async problem by introducing language-level coroutines, which are implemented by specially translating functions marked by suspend into computations that may asynchronously suspend through (essentially) “saving” JVM stack to the heap.

This solution allows Kotlin to support async programming without the level of ceremony and boilerplate common in “reactive” solutions, including those based on monads. More importantly, it allows Kotlin to support direct imperative style, which is familiar to nearly all programmers and requires no training.

Unfortunately, what was once an advantage for Kotlin has become a liability and legacy decision: Kotlin chose to solve the async problem by modifying the Kotlin language, rather than the Kotlin runtime.

This means that information on which functions are async leaks into the programming language syntax itself. Kotlin has re-invented the colored functions problem, with all of its well-known drawbacks.

An alternative solution to the async problem would have been to bake async into the Kotlin runtime, rather than the language, essentially by reinventing virtual threads, which would have allowed Kotlin developers to write Kotlin code that is obvlious to whether it is async or sync.

Unfortunately for Kotlin, the JVM innovated at a rapid pace that few could predict, and now Loom has given us full async programming in a direct imperative style, without the need to mark any functions. Loom also transparently works with all legacy code, making it fully modern and asynchronous (with a few exceptions such as synchronzied and file IO).

Kotlin is now in a weird situation where its (at the time) forward-looking support for async programming has become legacy–a solution that is inferior in terms of maximum theoretical performance, as well as user-friendliness, to the virtual threading solution powered by the Loom advancement of the JVM.

Scala 3 can already support fully async programming with no additional syntax or compiler passes, merely by running on a post-Loom JVM! In this world, we are able to write fully asynchronous code in a direct imperative style, without introducing introducing the two-colored functions problem, or importing Kotlin’s (now legacy) solution to the problem.

Now, in the spirit of fairness, I should point out that advancements in Loom do not help Scala.js or Scala Native. For all of the good that Loom does, its benefits are restricted to the JVM. Currently, the vast majority of all commercially relevant Scala development occurs on the JVM. While I love Scala.js and Scala Native and support their development, these markets are tiny and will remain so for the foreseeable future. The JVM is where all the commercial dollars are going and where Scala’s strengths remain.

In my view, the Scala.js and Scala Native markets are insufficient to justify any language-level changes to the async problem. If those markets were commercially relevant, then that might be an argument to invest resources in solving the problem, but it should be solved in the way that Loom solved it, which is a substantially and objectively superior solution (transparent runtime support) to the way Kotlin solved it (two-colored functions). Under no circumstances would I recommend that Scala 3 copy the Kotlin model to support the Scala.js and Scala Native communities.

In summary, there is no reason to pollute the Scala 3 language with two-colored functions when Loom already solves the async problem in a way that is significantly better than the way Kotlin solved it.

Notes on Proposal

  • Addition of continuations is not necessary or helpful to achieve structured concurrency; indeed, the JDK itself will be getting structured concurrency primitives
  • Being able to eliminate Either is a non-goal given Scala 3 can leverage exceptions, which are compatible with direct imperative style
  • Union types and flow typing provide a nice way to reduce the need of Option and keep things simple
  • Non-blocking sleep and generators are already free with Loom
17 Likes
#21

Implementing continuations at the compiler-level, as you noted, benefits all compiler targets, such as Scala.js and Scala Native.

Personally, I don’t care about native compilation (even as I realize that many other people do), but I care about JavaScript — it is my opinion that, given the trends, JavaScript will dominate the market for scripting. And it’s already giving the JVM a run for its money. The appeal of languages like Scala or Clojure is the benefit one gets from using a mature runtime and ecosystem of libraries, such as those of the JVM or JavaScript/Node.js. And if the language is designed to leach off a host, might as well target multiple hosts. Because it’s awesome to use the same language and the same base libraries on both the server and the client (the major appeal of JavaScript, actually). Also, Java++ will always be the next Java.

There’s also something to be said about Java’s timeline. The next LTS may support Loom, but many companies are still on Java 8 (2014), and I predict another 2 decades at least for the Scala language and libraries to be able to comfortably target and rely on Loom.

Not sure what you mean by two-colored functions being undesirable — isn’t that the whole point of types and effect systems? What are IO data types, if not much needed coloring? And why can’t Loom be used as an optimization only?

Personally, I like Kotlin’s continuations due to Arrow Fx.

There are downsides to usage of suspend in Kotlin, versus IO, such that IO is no longer a data structure with a custom interpreter, which reduces its compossibility (via flatMap). However, suspend does suspend side effects, and has better performance, and I can’t see why it couldn’t interface with our IO data types. But in spite of all that, I believe it has a better UX in the context of Scala.

Truth be told, if the compiler did this, then our IO data types become a tougher sell for your average programmer.

7 Likes
#22

I agree that Javascript has become hugely important, including for scripting, but the bulk of backend development occurs in traditionally server-side languages such as Python, Java, C#, C++, etc.

The Javascript ecosystem is quite well-established and mature, and features (via Typescript) an extremely capable and industry-supported solution for static typing.

In my view, it would be a mistake to bet Scala’s future on the possibility of “winning” the unproven Javascript market. If anything, we should double down on what’s working: bread & butter APIs (REST + GraphQL), microservices, and data engineering.

In any case, even if we all agreed that Javascript is the future of Scala (which I do not ascent to, I have no confidence in that whatsoever), I would strongly advocate for taking Loom’s approach to async programming rather than Kotlin’s approach, which would involve zero language-level changes to Scala 3. Rather, it would be an internal implementation detail in Scala.js (actually, a rather large number of them, which would ultimately mean Scala.js could support all the java.util.concurrent.* machinery).

That proposal (which is not this proposal), I could certainly get behind (assuming I were not footing the bill, because quite honestly, and in my opinion, there are much more pressing concerns to solve than async on Javascript!), because it would solve the async problem in the correct way, without permanently marring Scala 3 language syntax and semantics on account of niche platform-specific limitations.

2 Likes
#23

Would it work If instead of a suspend keyword we have just Suspend ?=> A

It’s mean that function f: suspended A=>B. will have type. A => (Suspend? => B) ?

If yes, let we have List[A] and method map[B](f: A=>B):List[B].
Than List.map(x => f(x)). will have type. List[Suspended?=>Int]. Is it what we want ?

val result = List(1,2,3).map(f)
if (result.head == 1) then 
   // never will be here ?  or will ?
#24

I think we need to distinguish two questions:

  • Should the sync/async distinction be reflected in types?
  • How does async get implemented?

I believe the answer to the first question is “yes, but not in the traditional way”. The traditional way leads to the colored function problem: We need to duplicate large bodies of code in sync and async versions. Or, alternatively, we have to sprinkle a lot of type variables around just to accommodate the
possibility that everything can be async. I believe we can do much better by switching the viewpoint
from effects to capabilities. An async computation would then be a computation that references the
Suspend capability. It turns out that this change in viewpoint gives a much better solution to the effect polymorphism problem.

The second question, how async is implemented, is largely orthogonal to the first. It could be by mapping to a monad, which is the most common solution for Scala today. Or by mapping to state machines, provided we can extend that to higher-order functions. Or by building on a runtime with support for coroutines and continuations, which (hopefully) Loom will provide. Once we buy into capabilities, we’ll have another interesting option: duplicate every function that can take a suspendable argument into sync and async versions. This may look like it reintroduces function coloring but doesn’t really since it is all codegen instead of source. Also, the capability type system tells us what we need to duplicate, so it’s hopefully not pervasive.

We are just starting a large scale (7 persons over 5 years) project to research these things. The aim is to find a unified approach to resources and effects that could become a high-level analogue to what Rust is for lower-level systems programing. The sync/async problem is one of the fundamental problems we study. We will work on a concrete type system for suspendability, and will look into different implementation strategies and compare them.

Here is a slide deck that describes the project. Btw, I am still looking to fill some roles in this project. Here’s a job add for a post doctoral scientist: https://recruiting.epfl.ch/Vacancies/2452/Description/2. Another ad for a research engineer will follow.

17 Likes
#25

I strongly disagree with this position.

The async/sync distinction disappears in a language with green threads. Literally the only reason we have the async/sync distinction is because the JVM (unlike Go, etc.) chose not to give us green threads, but rather, to give us operating system level threads, which was a mistake given the highly concurrent nature of modern applications (perhaps foreseeable, perhaps not).

In a perfect world, Thread.sleep() (etc.) would always be efficient. It is only when Thread is an OS-level thread that it becomes impossible to make it so, at least, due to the way OS threads are implemented and handled. Loom brings us that perfect world, more or less, and with time it will be more and more true.

Tracking sync/async distinction is absolutely not remotely relevant to software development in any language with green threads (see also: Go, Haskell, Erlang, etc.), and is a bit like using the type system to track whether MOVAPS is being used to copy floating-point values (that’s an implementation deal that should be dealt with by your language, e.g. compiler + runtime).

We are just starting a large scale (7 persons over 5 years) project to research these things.

Given this research project, I hope it’s crystal clear that now is not the time to import legacy Kotlin syntax + semantics into the Scala 3 language, since any attempt to do so would be both indadvised in light of Loom, and premature in light of Scala 3 research topics.

4 Likes
#26

It’s a fair question: what do we want to track in types? I agree it’s a tradeoff that has to be analyzed carefully, and that different people might make different choices.

In the particular case of suspension / delays. it seems to me that the main reason you want to track it is that a computation might hang on to some other critical resource that you also want to track. In that case it makes a difference whether the resource is only blocked for a short time, or indefinitely, until the suspended computation resumes. You might argue that even non-suspending long-running computations have the same problem. True, but I remember that Microsoft at some point decreed that any computaton running longer than 40ms (? or whereabouts) had to be wrapped in a future.

6 Likes
#27

I most agree with JDG here. Lots of things are worth tracking in types, but I don’t think sync/async distinctions is one of them.

Let’s go back to the fundamentals; why dont people just spawn threads? One thread per Future? One thread per Actor? A lot of early Scala libraries did this. Why didn’t it work?

The basic issue with this approach here is one of performance and resource footprint: threads are expensive, context switching is expensive, so you typically won’t want to have more than O(1,000) threads in an application that may have O(100,000,000) objects. Thus people invented async to try and multiplex workflows onto a small number of threads, to reduce the performance and resource footprint concerns.

But in the end, the problem with threads is not semantics, but performance! All the libraries and frameworks around async is to try and make “async code” look exactly like “direct style” threaded code, because semantically that’s what people want. People invented “async backpressure”, because they no longer can rely on blocking to slow down upstream producers. Everyone wants the semantics of threads, but without their cost issues.

Consider another data point: threads are avoided in the JVM in high performance IO-bound use cases in favor of async, but they’re not avoided in languages like Python, where they are the preferred mechanism for IO bound operations. Why? Because everything else in Python is so expensive enough that threads are comparatively cheap! Again, this emphasises that avoiding threads is a performance/cost/footprint issue, and not an issue of programming semantics

Loom, by and large, fixes the cost of threads, and makes them cheap. You can now spawn O(10,000,000) threads without issue. Suddenly the whole reason for async goes away! Futures are still useful as a programming model, as are Actors, but they no longer need to be async. They can have a thread each, they can block sometimes, no problem at all. No need for async.

Thus, given the JVM has Loom, I wouldn’t think it’s worth it to integrate a compiler-level async functionality at this point. Async was important in the past, in some high performance use cases. That use case has largely been satisfied by Loom, in a much better way. Even without Loom, I would argue that it doesn’t quite meet the threshold of building into the language, and anyway all the implementations/proposals presented so far (including this one!) have so many limitations around HOFs as to be mostly un-adoptable. I say this as someone who tried in earnest to adopt Scala-Continuations back in 2012

Scalajs is cool - I am literally the world’s biggest proponent of Scalajs - but I don’t think such a major investment just for Scalajs is worth ir. Furthermore, if we’re willing to invest 7pax times 5 years of effort in Scalajs, there are a million other things the project could benefit from more than an async CPS tranformation.

16 Likes
#28

In the particular case of suspension / delays. it seems to me that the main reason you want to track it is that a computation might hang on to some other critical resource that you also want to track. In that case it makes a difference whether the resource is only blocked for a short time, or indefinitely

There is a total isomorphism between async and sync computation. In particular, for Future.never, the synchronous equivalent is while(true){}. Everything that you want or need with synchronous computation, you want and need with asynchronous computation, and visa versa.

Literally the only distinction between sync and async is efficiency (which is an implementation detail, pushed to the language level or lower, as in modern languages like Go or Kotlin), and even that is not set in stone (perhaps one could imagine an OS + CPU such that sync, i.e. OS threads, would be faster than async, i.e. virtual threads in the language runtime).

Tracking complexity, efficiency, and performance, be that O(n) or time bounds, might indeed be interesting, such that developers would have a better handle on the runtime behavior of their code, but I would view that as theoretically orthogonal to sync versus async (and practically, nearly so, especially post Loom). Whether or not such tracking of complexity, efficiency, or performance should be done in the type system or at the level of the runtime, and exposed to users via tooling, is perhaps a subject more suited to research than commercial programming.

I will suggest, however, that (a) the overhead of any sort of static complexity, efficiency, or performance tracking would have to be extremely small to justify its pervasive use in software (because the benefit is marginal—not zero, however), and (b) the obsession of JVM programmers with the async/async distinction is not shared by developers who use languages with green threads (i.e. it’s a historical artifact that will disappear in a post-Loom world).

2 Likes
#29

Yes, but does that mean that Future[String] should no longer exist as a separate type from () => String? That’s the crux of the matter, as I see it. One can answer either way. but I think it’s a reasonable position to say that one wants to see in the type whether a computation can suspend or not.

1 Like
#30

This is the whole point: there is no difference (aside from efficiency) between “long async suspension” and “slow synchronous code”, or “short async suspension” and “fast synchronous code”.

If you call InputStream#read, it may not return for 1 minute (or even longer!). All async does is take that same 1 minute computation and make it vastly more efficient.

In reality, Future[String] is not guaranteed to take more or less time than () => String. If you are using Future properly, then in a pre-Loom world, Future[String] will be more efficient than () => String. Post-Loom, however, () => String is more efficient than Future[String], even if async is involved.

Post-Loom, the successor to Future is actually java.lang.Thread (specifically, VirtualThread). That’s because () => String does not give you a “handle” on the running computation (like Future), whereas VirtualThread does give you such a handle, and over time Loom will evolve more capabilities to interact with virtual threads (currently you can interrupt them, get their stack trace, and so forth, which is actually more than you can do with Future!).

3 Likes
#31

What you describe is already false today. Futures have nothing to do with suspending, and not all Futures can be suspended. And normal threaded code can be suspended already; that’s the whole point of threads and pre-emptive multitasking! They’re just a bit expensive

Will Future-based async programming be much less useful with Loom? I say yes, in which case Future[String] could conceivably be large relaxed by String. or () => String. Maybe not 100%, but mostly. Even blocking systems have callbacks sometimes.

Futures and async play a small-sized role in Scala today. “Most” Scala systems are too small to worry about it. At my employer, one of the largest Scala shops around, only a small number of systems need to be Async. My OSS projects, almost nothing is async. The Scala compiler and broader tooling ecosystem, no async. With Loom, we can expect Async’s importance to diminish further. That leaves Scala.js as a use case.

If Async was so important in the Scala ecosystem, we would have seen Lightbend having much more adoption and importance than they do today, since “async everything” is their thing. But they aren’t all that widely adopted, despite a massive marketing and evangelism effort on their part, which is the market telling us that Async isn’t really necessary for the vast majority of developers and systems. You can see that truth in how much async Scala code you yourself write in Dotty and surrounding systems

Overall, not a strong case for baking Async into the language or compiler

4 Likes
#32

I would also add to this that post-Loom, any callback API can be trivially converted into an ordinary API by using, for example, java.util.concurrent.CompletableFuture, whose get method is non-blocking on virtual threads.

e.g.:

def callbackAPI[A](cb: A => Unit): Unit = ???

def loomAPI(): A = {
  val cf = new CompletableFuture[A]()
  callbackAPI(cf.complete(_))
  cf.get
}

Essentially, Loom allows you to instantly convert callback-based APIs into “synchronous-looking” code, without using any infectous wrapper types such as Future.

I honestly think that post-Loom, there is no reason for scala.concurrent.Future to exist.

2 Likes
#33

One thing that Future[T] lets you do that normal T doesn’t is reason about completion: you can ask a Future[T] if it is done computing or not, and make decisions based on that fact. That can be useful sometimes.

Not something people do often, but it is a “unique” capability of Future, and so there will continue being reason for it to exist. But Futures won’t be nearly as common as they are today, and even today they are uncommon at best.

And in a post-Loom world, even Future doesn’t need to be async, and you can spawn a (virtual) thread per Future and block on things just fine. So even if Future remains, the need for an “async transform” goes away

3 Likes
#34

I agree this is useful, which is why I view Thread (or VirtualThread) as the successor to Future, since it gives you—among other things, such as interruption and stack traces, which Future does not give you—the similarly useful method Thread.isAlive.

2 Likes
#35

I agree, that’s more or less what I’ve been trying to say with the whole “futures don’t need to be async anymore”. With Loom, a Future can basically be implemented using blocking threads that block on each other, and Future[T] more or less isomorphic to (() => T, java.lang.Thread) with some helper methods to make them more ergonomic. The ergonomics do have some value, and removing the async constraint could allow us to make Future much more ergonomic than it is today.

2 Likes